Algoritmos de nuvem de partículas e a otimização com muitos objetivos

Abstract

Resumo: Problemas de otimização multiobjetivo (MOPs) sao problemas que possuem mais de uma função objetivo a ser minimizada ou maximizada. Entre as abordagens mais utilizadas atualmente para resolve-los destaca-se o uso de metaheurísticas populacionais. Esta popularidade se deve principalmente à natureza destas de lidar simultaneamente com diversas soluções (populacao) em uma única execucao. Um algoritmo muito utilizado para lidar com MOPs e chamado otimizacao por nuvem de partículas multiobjetivo (MOPSO), esta e uma abordagem derivada da otimizaçao por nuvem de partículas (PSO), que e uma metaheurística inspirada no comportamento de conjuntos de aves. Devido ao bom desempenho apresentado pelos MOPSOs ao resolver MOPs, esta abordagem vem sendo estendida para a resolucao de problemas de otimizaçao com muitos objetivos (MaOPs). Estes problemas sao caracterizados por apresentarem mais de tres funçoes objetivo e uma alta complexidade causada principalmente porque a proporçao de soluções não dominadas em uma populacao aumenta rapidamente com o número de objetivos, o que diminui a pressao de selecõo em direçao a fronteira de Pareto. Alem disso, o numero de pontos necessúrios para representar a fronteira aumenta exponencialmente de acordo com o numero de objetivos dificultando a obtençao de solucoes diversas o suficiente para cobri-la totalmente. Este trabalho apresenta algumas tecnicas aplicadas para melhorar o desempenho do MOPSO ao resolver MaOPs e tornú-lo menos sensível ao aumento no número de objetivos. Primeiramente estudaram-se duas tecnicas de controle da úrea de dominância das solucoes para aumentar a pressao de seleçõo, normalmente reduzida pelo aumento no numero de objetivos. Outra tecnica estudada foi a alteracao do metodo de selecao de líderes do MOPSO com a realizaçao de um estudo empírico usando seis metodos e os melhores foram destacados. Foi estudada tambem a influencia sofrida por esses metodos devido a alteracao na técnica de controle da área de dominância, e as melhores combinações foram identificadas através de estudos empíricos. Por último um novo MOPSO e proposto usando o conceito de pontos de referencia distribuindo melhor as soluções obtidas e com isso melhorando a convergencia a fronteira real. Estudos empíricos tambem foram realizados para comparar a nova abordagem a abordagem classica. A partir dos trabalhos realizados aqui tres artigos foram publicados, sendo o primeiro um estudo sobre os metodos de selecao de líderes, o segundo propondo um novo MOPSO que usa uma tecnica de controle da area de dominancia, e o terceiro que avalia a influencia das tecnicas de controle da area de dominância no desempenho dos metodos de selecõo de líder e identifica as melhores combinacoes entre tecnica de controle da area de dominância e metodo de seleçao de líder. Em geral todos os estudos realizados apresentaram melhorias de desempenho em relacao ao algoritmo original utilizado, especialmente no contexto de muitos objetivos.

Abstract: Multiobjective optimization problems (MOPs) are problems that have more than one objective function to be minimized or maximized. Among the approaches currently used to solve them we highlight the use of populational metaheuristics. This popularity is mainly due to its nature of dealing simultaneously with many solutions (population) in a single run. An algorithm frequently used to deal with MOPs is called multiobjective particle swarm optimization (MOPSO), this approach is derived from the particle swarm optimization (PSO), which is a metaheuristic inspired by the behavior of bird flocks. Due to the good performance presented by MOPSOs to solve MOPs, this approach has been extended for solving many objective optimization problems (MaOPs). These problems are characterized by presenting more than three objective functions and a high complexity caused mainly because the proportion of non-dominated solutions in a population increases rapidly with the number of objectives, which reduces the selection pressure toward the Pareto frontier, moreover, the number of points to represent the frontier increases exponentially with the number of objectives becoming harder to obtain solutions diverse enough to cover it entirely. This work presents some techniques applied to improve the performance of MOPSO to solve MaOPs and make it less sensitive to the increase in the number of objectives. Firstly were studied the use of two techniques to control the dominance area of solutions to increase the selection pressure, typically reduced by the increase in the number of objectives. The impact of the leader selection method was also studied. Six methods were investigated experimentally and the best were highlighted. It was also studied the influence suffered by these methods due to the change in the control of the domination area of solutions, and the best combinations were identified through empirical studies. Finally a new MOPSO is proposed using the concept of reference points to better spread the solutions and thereby improve the convergence to the true frontier. Empirical studies were also conducted to compare the new approach with the classical one. From the work done here three articles were published, the first being a study on methods of leader selection, the second proposes a new MOPSO that uses a method to control the dominance area of solutions, and the third that assesses the influence of techniques to control the dominance area of solutions in the performance of leader selection methods and identifies the best combination between the technique to control the dominance area of solutions and the leader selection method. In general all studies showed performance improvements compared to the original algorithm used, especially in the context of many objectives.