O uso de múltiplos enxames na otimização de problemas com vários objetivos

Abstract

Resumo: A computação bioinspirada permite a resolução de uma gama de problemas computacionais. Dentre as várias meta-heurísticas existentes, o algoritmo PSO (Particle Swarm Optimization) tem sido aplicado eficientemente para resolver problemas de otimização. Inicialmente empregado na resolução de problemas com um objetivo, a técnica tem sido investigada para solucionar problemas multiobjetivo. O principal objetivo desta tese de doutorado é a proposta de estratégias distribuídas para a execução do algoritmo PSO em diversas topologias conectando múltiplos enxames para resolver problemas com vários objetivos. A adoção de múltiplos enxames parte da constatação de que a otimização pode consumir onerosos recursos computacionais. Assim, investigar e propor novos métodos para a execução do algoritmo de forma paralela e distribuída torna-se uma iniciativa relevante. Neste trabalho, os indivíduos do algoritmo PSO são divididos em subpopulações independentes entre si e que ocasionalmente compartilham indivíduos. Diversas topologias e estratégias de comunicação para conectar os enxames foram investigadas, que determinam quais subpopulações trocam informações entre si. A influência exercida pela topologia na otimização de problemas com um objetivo é avaliada. Esta investigação inicial serviu para verificar se o uso de múltiplos enxames é relevante. Considerando os resultados obtidos, pôde-se constatar que esse modelo exerce um efeito positivo no processo de otimização. Foi possível indicar quais topologias apresentam melhor desempenho e qual a configuração, em termos de número de subpopulações, é mais eficiente. Tais constatações foram motivações para conceber estratégias distribuídas para resolver problemas com vários objetivos, incluindo uma estratégia baseada na decomposição de funções. Estudos empíricos são conduzidos para avaliar o impacto da otimização cooperativa, incluindo fatores relacionados à comunicação exigida entre as subpopulações. A partir desses resultados foi possível determinar qual estratégia baseada no algoritmo PSO é mais indicada, considerando as características de diferentes problemas de otimização.

Abstract: Bioinspired computation allows the resolution of a wide variety of computational problems. Among the many existing meta-heuristics, the PSO (Particle Swarm Optimization) algorithm has been effectively applied to solve several optimization problems. First employed for solving single objective problems, there are clearly advantages of using this technique to solve multiobjective problems. The main goal of this thesis is the proposal of distributed strategies for running PSO algorithm on several topologies connecting multiple swarms to solve problems with many objectives. The adoption of multiple swarms derives from the fact that the optimization can consume expensive computational resources. So, the investigation and proposal of new methods for the implementation of parallel and distributed algorithms becomes a relevant effort. The parallelization technique employed in this work consists of grouping PSO individuals in independent subpopulations, which occasionally share individuals. We have investigated the impact of several topologies and communication strategies that dictate how subpopulations exchange information among themselves. The influence of the topology single objective problems is first investigated. This initial research helped to determine whether the use of multiple swarms is relevant. Considering these results, it was noted that this model has a positive effect in the optimization process. It was possible to indicate which topologies are more efficient and the performance evaluation in terms of number of subpopulations. These findings were motivations for designing distributed strategies for solving problems with multiple objectives, including a strategy based on decomposition of functions. Empirical studies were conducted to assess the impact of cooperative optimization, including factors related to communication required between subpopulations. From these results it was possible to determine which optimization strategy based on PSO algorithm is more appropriate, considering the specific characteristics of different optimization problems.