Orientador: Romis Ribeiro de Faissol Attux

Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação

Resumo: Os algoritmos de otimização podem possuir características de busca local, global e multimodal. Em termos simples, os algoritmos de busca local procuram refinar uma solução inicial encontrada, promovendo a sua movimentação para o ótimo local dominante em sua vizinhança. Já os algoritmos de...

Resumo: Os algoritmos de otimização podem possuir características de busca local, global e multimodal. Em termos simples, os algoritmos de busca local procuram refinar uma solução inicial encontrada, promovendo a sua movimentação para o ótimo local dominante em sua vizinhança. Já os algoritmos de busca global possuem estratégias para escapar de ótimos locais, e, desta forma conseguem movimentar seus pontos de forma mais ampla pelo espaço de busca. Por fim, algoritmos multimodais procuram encontrar os vários ótimos no espaço de busca. Neste trabalho foi proposto um algoritmo de otimização multimodal, baseado em PSO, com duas inovações: o raio de repulsão com controlador de passo, e o armazenamento da região promissora. O algoritmo foi chamado de MPSO (Magnetic Particle Swarm Optimization), e possui apenas um parâmetro de configuração, o número de partículas. Ele apresentou resultados bastante interessantes nos experimentos comparativos realizados, tanto em funções benchmark quanto em uma aplicação prática. A segunda proposta foi uma metodologia de busca baseada em clusterização. Nesta metodologia, a modificação proposta translada os centroides das posições de representantes dos clusters, obtidas originalmente pelos algoritmos de clusterização clássicos, para uma região promissora no cluster, ou seja, para uma região melhor avaliada pela função objetivo, que será maximizada ou minimizada. Desta forma, a metodologia toma a forma de um operador que pode ser utilizado como pré-processador de algoritmos de otimização clássicos, sendo capaz de introduzir diversidade na população inicial, o que, como mostram os experimentos realizados, melhorou os resultados obtidos. Outras possibilidades de aplicação da ideia também são expostas e avaliadas

Abstract: Optimization algorithms have local, global and multimodal search features. In simple terms, a local search algorithm refines an initial solution by moving it towards an optimal dominant place in its neighborhood. Global search algorithms have strategies to escape from local optima, and...

Abstract: Optimization algorithms have local, global and multimodal search features. In simple terms, a local search algorithm refines an initial solution by moving it towards an optimal dominant place in its neighborhood. Global search algorithms have strategies to escape from local optima, and thus can move their points more broadly throughout the search space. Finally, multimodal algorithms seek to find several global optima in the search space. In this thesis, we propose a multimodal optimization algorithm based on PSO with two innovations: the repulsion radius with step controller and the storage of promising search directions. The algorithm was named MPSO (Magnetic Particle Swarm Optimization) and has only one configuration parameter, the number of particles. It led to consistent results in benchmark-based comparative experiments and in a practical application. The second proposal was a clustering-based optimization methodology. This proposal moves the centroids from a position representative of a cluster, originally obtained by classical clustering algorithms, to a promising region in terms of an objective function to be maximized or minimized . The methodology was implemented in the form of an operator used as a pre-processor to traditional optimization algorithms. It introduced diversity in the initial population, which, as shown by the experiments,led to significant performance improvements. Other possibilities of applying this new idea are also discussed in the text