Tese
Algoritmo memético cultural para otimização de problemas de variáveis reais
Cultural memetic algorithm for optimization of real variable problems
Registro en:
Autor
FREITAS, Carlos Alberto Oliveira de
Institución
Resumen
Technology has made great strides in recent years, but computing resources for certain applications need optimization so that the costs involved in solving some problems are not high. There is a very broad area of research for the development of efficient algorithms for multimodal optimization problems. In the last two decades the use of evolutionary algorithms in multimodal optimization has been shown to be a success. Among these evolutionary algorithms, which are global search algorithms, one can cite the use of Cultural Algorithms. A natural enhancement of the Cultural Algorithm is its hybridization with some other local search algorithm, so as to have the advantages of global search combined with local search. However, the local search Cultural Algorithms used for multimodal optimization are not always evaluated by efficient statistical tests. The objective of this work is to analyze the behavior of the Cultural Algorithm, with populations evolved by the Genetic Algorithm, when the local search heuristics are used: Tabu Search, Beam Search, Climbing and Simulated Annealing. One of the contributions of this work was the updating of the topographic knowledge of the cultural algorithm by the use of the triangular area defined by the best results found in the local search. To perform the analysis, a memetic algorithm was developed by hybridizing the cultural algorithm with the local search heuristics mentioned, being selected one at a time. Real world problems usually have multimodal characteristics, so the evaluations were performed using multimodal benchmark functions, which had their results evaluated by non-parametric tests. In addition, the memetic algorithm was tested on real optimization problems with constraints in the engineering areas. In the evaluations carried out, the developed Cultural Algorithm presented better results when compared to the available results of the researched scientific literature. A tecnologia deu grandes passos nos últimos anos, mas os recursos de computação para certas aplicações precisam de otimização para que os custos envolvidos na solução de alguns problemas não sejam altos. Existe uma área muito ampla de pesquisa para o desenvolvimento de algoritmos eficientes para problemas de otimização multimodal. Nas duas últimas décadas o uso de algoritmos evolutivos em otimização multimodal tem demonstrado ser um sucesso. Dentre esses algoritmos evolutivos, que são algoritmo de busca global, pode-se citar o uso dos Algoritmos Culturais. Um aprimoramento natural do Algoritmo Cultural é a sua hibridização com algum outro algoritmo de busca local, de forma a ter as vantagens da busca global combinada com a busca local. Entretanto os Algoritmos Culturais com busca local usados para otimização multimodal nem sempre são avaliados por testes estatísticos eficientes. O objetivo deste trabalho é analisar o comportamento do Algoritmo Cultural, com populações evoluídas pelo Algoritmo Genético, quando são utilizadas as heurísticas de busca locais: Busca Tabu, Busca de Feixe, Escalada e Recozimento Simulado. Uma das contribuições deste trabalho foi a atualização do conhecimento topográfico do algoritmo cultural pelo uso da área triangular definida pelos melhores resultados encontrados na busca local. Para realizar a análise, um algoritmo memético foi desenvolvido pela hibridização do algoritmo cultural com as heurísticas de busca local citadas, sendo selecionadas uma de cada vez. Os problemas do mundo real costumam ter características multimodais, então as avaliações foram realizadas usando funções de benchmark multimodais, que tiveram seus resultados avaliados por testes não paramétricos. Além disso, o algoritmo memético foi testado em problemas reais de otimização com restrições nas áreas de engenharia. Nas avaliações realizadas, o Algoritmo Cultural Memético desenvolvido apresentou melhores resultados quando comparado com os resultados disponíveis da literatura científica pesquisada.