Please use this identifier to cite or link to this item: http://hdl.handle.net/10316/95515
Title: An hypervolume dichotomic scheme for multiobjective optimization
Other Titles: An hypervolume dichotomic scheme for multiobjective optimization
Authors: Brito, Alexandre Daniel Pereira
Orientador: Paquete, Luís Filipe dos Santos Coelho
Keywords: Optimização Multiobjectivo; Escalarização de Hypervolume; Procura Dicotomica; Programação Linear Inteira; Multiobjective Optimization; Hypervolume Scalarization; Dichotomic Search; Integer Linear Programming
Issue Date: 15-Jul-2021
Serial title, monograph or event: An hypervolume dichotomic scheme for multiobjective optimization
Place of publication or event: DEI | FCTUC
Abstract: Problemas de otimização multiobjectivo podem facilmente ser encontrados na nossa via diária. Em múltiplas situações nos conseguimos encontrar, sem reparar, a tentar otimizar vários objetivos. Nesta dissertação propomos métodos para resolver problemas de otimização multiobjectivo. Em particular, estes métodos são baseados no conceito de escalarização de hypervolume e estendem o trabalho anterior na seguinte forma: i) descrevemos uma software framework que implementa a procura dicotómica para resolver qualquer problema de otimização biobjetivo que pode ser formulado em termos de escalarização de hypervolume; esta ferramenta é capaz de encontrar o conjunto completo de soluções ótimas, assim como um deste que tem uma garantia de proximidade; também providenciamos a documentação necessária para ajudar o utilizador a implementar a framework, juntamente com um exemplo prático do problema da mochila biobjectivo implementado com scip ii) apresentamos uma versão do esquema dicotómico com paralelização para encontrar o conjunto completo de soluções ótimas; iii) estendemos a abordagem dicotómica para qualquer número de objetivos que funciona sob alguns pressupostos. Para além disso, apresentamos resultados numéricos numa ampla gama de instâncias. Com estes resultados pudemos concluir que a versão com paralelização é significativamente mais rápida, especialmente para números de valores de entrada maiores. Também pudemos concluir que, para a abordagem para qualquer número de objetivos, uma seleção aleatória do próximo subproblema a resolve permite encontrar o conjunto de pontos não dominados resolvendo e gerando um menor número de subproblemas.
Multiobjective optimization problems can easily be found in our daily life. In multiple cases we inadvertently find ourselves trying to optimize several objectives. In this dissertation, we propose methods to solve multiobjective optimization problems. In particular, these methods are based on the concept of hypervolume scalarization and extend previous work on the following manner: i) we describe a software framework that implements a dichotomic search to solve any biobjective optimization problem that can be formulated in terms of hypervolume scalarization; this framework can provide the complete set of optimal solution as well as a subset of it that has an approximation guarantee; we also provide the required documentation to help the user to implement it, with an application example for a biobjective knapsack problem implemented with scip; ii) we present a parallel version of the dichotomic scheme to find the complete set of optimal solutions; iii) we extend the dichotomic approach for any number of objectives that works under some assumptions. In addition, we present numerical results on a wide range of instances. From these results we were able to conclude that the parallel version presented is significantly faster, specially for larger input sizes. We also concluded that, for the approach for any number of objectives, a random selection method of the next subproblem to solve allows to find the complete nondominated set while generating and solving less number of subproblems.
Description: Dissertação de Mestrado em Engenharia Informática apresentada à Faculdade de Ciências e Tecnologia
URI: http://hdl.handle.net/10316/95515
Rights: openAccess
Appears in Collections:UC - Dissertações de Mestrado

Files in This Item:
File Description SizeFormat
Dissertation_Alexandre_Brito_2021.pdf1.02 MBAdobe PDFView/Open
Show full item record

Page view(s)

9
checked on Sep 24, 2021

Download(s)

11
checked on Sep 24, 2021

Google ScholarTM

Check


This item is licensed under a Creative Commons License Creative Commons