Please use this identifier to cite or link to this item: http://hdl.handle.net/10316/95515
DC FieldValueLanguage
dc.contributor.advisorPaquete, Luís Filipe dos Santos Coelho-
dc.contributor.authorBrito, Alexandre Daniel Pereira-
dc.date.accessioned2021-08-05T22:01:42Z-
dc.date.available2021-08-05T22:01:42Z-
dc.date.issued2021-07-15-
dc.date.submitted2021-08-05-
dc.identifier.urihttp://hdl.handle.net/10316/95515-
dc.descriptionDissertação de Mestrado em Engenharia Informática apresentada à Faculdade de Ciências e Tecnologia-
dc.description.abstractProblemas 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.por
dc.description.abstractMultiobjective 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.eng
dc.description.sponsorshipUniversidade de Coimbra - O trabalho foi financiado através de uma Bolsa de Initiação à Investigação com o n.º de referência UUIDB/00326/2020_L.717537, no âmbito do projeto I&D Centro de Informática e Sistemas da Universidade de Coimbra, com a referência UIDB/00326/2020, com uma duração de três meses.-
dc.language.isoeng-
dc.rightsopenAccess-
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/-
dc.subjectOptimização Multiobjectivopor
dc.subjectEscalarização de Hypervolumepor
dc.subjectProcura Dicotomicapor
dc.subjectProgramação Linear Inteirapor
dc.subjectMultiobjective Optimizationeng
dc.subjectHypervolume Scalarizationeng
dc.subjectDichotomic Searcheng
dc.subjectInteger Linear Programmingeng
dc.titleAn hypervolume dichotomic scheme for multiobjective optimizationeng
dc.title.alternativeAn hypervolume dichotomic scheme for multiobjective optimizationpor
dc.typemasterThesis-
degois.publication.locationDEI | FCTUC-
degois.publication.titleAn hypervolume dichotomic scheme for multiobjective optimizationeng
dc.peerreviewedyes-
dc.identifier.tid202753166-
thesis.degree.disciplineInformática-
thesis.degree.grantorUniversidade de Coimbra-
thesis.degree.level1-
thesis.degree.nameMestrado em Engenharia Informática-
uc.degree.grantorUnitFaculdade de Ciências e Tecnologia - Departamento de Engenharia Informática-
uc.degree.grantorID0500-
uc.contributor.authorBrito, Alexandre Daniel Pereira::0000-0002-4656-7083-
uc.degree.classification18-
uc.degree.presidentejuriPereira, Vasco Nuno Sousa Simões-
uc.degree.elementojuriPaquete, Luís Filipe dos Santos Coelho-
uc.degree.elementojuriSimões, Marco António Machado-
uc.contributor.advisorPaquete, Luís Filipe dos Santos Coelho-
item.fulltextCom Texto completo-
item.languageiso639-1en-
item.grantfulltextopen-
crisitem.advisor.deptFaculty of Sciences and Technology-
crisitem.advisor.parentdeptUniversity of Coimbra-
crisitem.advisor.researchunitCISUC - Centre for Informatics and Systems of the University of Coimbra-
crisitem.advisor.parentresearchunitFaculty of Sciences and Technology-
crisitem.advisor.orcid0000-0001-7525-8901-
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 simple item record

Page view(s)

10
checked on Oct 8, 2021

Download(s)

13
checked on Oct 8, 2021

Google ScholarTM

Check


This item is licensed under a Creative Commons License Creative Commons