Submitted by Pedro Barros (pedro.silvabarros@ufpe.br) on 2018-08-14T18:55:09Z
No. of bitstreams: 2
license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5)
TESE Elliackin Messias do Nascimento.pdf: 4712819 bytes, checksum: a74e4ee711cd8b7a125b8b4404512853 (MD5) / Approved for entry into archive by Alice Araujo (alice.caraujo@ufpe.br) on 2018-08-16T19:59:21Z (GMT) No. of bitstreams: 2
license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5)
TESE Elliackin Messias do Nascimento.pdf: 4712819 bytes, checksum: a74e4ee711cd8b7a125b8b4404512853 (MD5) / Made available in DSpace on 2018-08-16T19:59:21Z (GMT). No. of bitstreams: 2
license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5)
TESE Elliackin Messias do Nascimento.pdf: 4712819 bytes, checksum: a74e4ee711cd8b7a125b8b4404512853 (MD5)
Previous issue date: 2017-02-17 / CNPq / Many-Objective Optimization Problems (MaOPs) são uma classe especial de problemas multiobjetivos que apresentam quatro ou mais objetivos. Algoritmos evolucionários ou de enxame de partículas tradicionais falham ao tentarem resolver MaOPs pois eles se tornam ineficazes ou ineficientes nestes problemas. Em virtude disso, alguns pesquisadores propuseram diferentes estratégias para contornar as dificuldades impostas por MaOPs, sobretudo para Multiobjective Evolutionary Algorithms (MOEAs) tradicionais para esses problemas. Em contrapartida, muito pouco tem sido feito no sentido de adaptar algoritmos de Multiobjective Particle Swarm Optimizations (MOPSOs) para MaOPs. Não obstante, algoritmos baseados em enxames de partículas no geral são reconhecidos pela rápida velocidade de convergência em problemas com um único objetivo e por isso parecem ser também adequados para problemas multiobjetivos e com muitos objetivos. Desta forma, existe a necessidade de se desenvolver MOPSOs para lidar com MaOPs. Sendo assim, o objetivo desta tese foi desenvolver um MOPSO para resolver MaOPs no sentido de promover um maior balanceamento entre convergência para Frente de Pareto e diversidade de soluções nesses problemas. Para isso, o algoritmo proposto nesta tese usa um conjunto de pontos de referência para impor uma pressão de convergência para a Frente de Pareto enquanto permite um maior gerenciamento da diversidade. Além disso, a abordagem proposta usa um arquivo externo em que são armazenadas soluções não-dominadas e do qual são retirados os líderes sociais das partículas de acordo com duas medidas que foram propostas nesta tese, a saber, a medida de convergência e a medida de densidade. O objetivo dessas medidas é promover a convergência para a Frente de Pareto e promover a diversidade ao longo dela simultaneamente. A proposta foi avaliada usando seis problemas da família DTLZ com dois, três, cinco, sete e dez objetivos e usando métricas bem estabelecidas na literatura (distância geracional, distância geracional invertida e hipervolume) para medir a convergência e diversidade do conjunto solução obtido pelo algoritmo; e ele foi comparado com duas abordagens baseadas em enxames (SMPSO e CDAS-SMPSO) e três abordagens evolucionárias (CEGA, MDFA, e NSGA-III) afim de mostrar suas vantagens e pontos de melhorias frente a outros algoritmos bem estabelecidos na literatura. Os resultados mostraram que o algoritmo proposto foi bem sucedido em equilibrar convergência e diversidade nos problemas testados apresentando resultados equivalentes ou superiores ao NSGA-III que é uma das propostas mais bem sucedidas até o momento para lidar com problemas com muitos objetivos. Além disso, o algoritmo proposto foi aplicado em um problema real de projeto de redes ópticas de alta capacidade com o intuito de avaliar sua utilidade prática. / Many-Objective Optimization Problems (MaOPs) are an especial class of multiobjective problems in which four or more objectives are optimized simultaneously. Currently, these problems have attracted attention of the researchers due the two reasons: (i) many real-world applications are naturally many-objective problems and (ii) population-based heuristics presents great difficulties for solving these problems. For example, Paretodominance based algorithms such as Multiobjective Evolutionary Algorithms (MOEAs) and Multiobjective Particle Swarm Optimization (MOPSO) algorithms are ineffective in these problems because almost all solutions in the population become non-dominated solutions, resulting in loss of convergence pressure for the Pareto front. Because of this, researchers have proposed new strategies for dealing with this problems, mainly for MOEAs. However, very little has been done to make the MOPSOs effective in these scenarios. Regardless of this, Particle Swarm Optimization (PSO) algorithms are known by fast speed of convergence in single-objective problems and they seem be suitable for MaOPs. Moreover, to create algorithms that are capable of balancing both convergence and diversity is a research challange. Therefore, there are a necessity to develop PSO-based algorithms for dealing with MaOPs. Thus, this thesis proposes a new algorithm based on PSO whose aim is to promote a better balancing between convergence toward the Pareto front and diversity of solutions. To achieve this aim, the proposed algorithm uses a set of reference points to impose a selection pressure to Pareto front while it allows a better control of the diversity. Furthermore, our algorithm use an external archive where it maintains non-dominated solutions and from which the social leaders are picked in according to two measures proposed for us, namely, the convergence measure and the density measure. The objective of these measures is to promote the convergence toward Pareto Front and to promote the diversity along it simultaneously. To evaluate our algorithm we used three well-known metrics in the literature, namely, generational distance, inverted generational distance, and hypervolume; and six benchmark problems of the DTLZ family with two, three, five, seven and ten objectives. Moreover, the algorithm was compared to two PSObased algorithms (SMPSO and CDAS-SMPSO) and three evolutionary algorithms (MDFA, CEGA and NSGA-III). The results showed that our algorithm was sucessful in balancing the requirements of convergence and diversity in the test problems compared to other algorithms in the literature. Besides, our algorithm was applied in a real-world problem involving the physical topology design of optical network in which it obtained good results.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.ufpe.br:123456789/25629 |
| Date | 17 February 2017 |
| Creators | FIGUEIREDO, Elliackin Messias do Nascimento |
| Contributors | http://lattes.cnpq.br/6321179168854922, LUDERMIR, Teresa Bernarda, BASTOS FILHO, Carmelo José Albanez |
| Publisher | Universidade Federal de Pernambuco, Programa de Pos Graduacao em Ciencia da Computacao, UFPE, Brasil |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Source | reponame:Repositório Institucional da UFPE, instname:Universidade Federal de Pernambuco, instacron:UFPE |
| Rights | Attribution-NonCommercial-NoDerivs 3.0 Brazil, http://creativecommons.org/licenses/by-nc-nd/3.0/br/, info:eu-repo/semantics/openAccess |
Page generated in 0.002 seconds