Please use this identifier to cite or link to this item: https://repositorio.ufu.br/handle/123456789/14267
metadata.dc.type: Tese
metadata.dc.rights: Acesso Aberto
Title: Um Algoritmo Auxiliar Paralelo inspirado na Fertilização in Vitro para melhorar o desempenho dos Algoritmos Genéticos
metadata.dc.creator: Camilo Júnior, Celso Gonçalves
metadata.dc.contributor.advisor1: Yamanaka, Keiji
metadata.dc.contributor.referee1: Soares, Alexsandro Santos
metadata.dc.contributor.referee2: Lima, Luciano Vieira
metadata.dc.contributor.referee3: Julia, Rita Maria da Silva
metadata.dc.contributor.referee4: Souza, Marcone Jamilson Freitas
metadata.dc.description.resumo: Várias são as técnicas aplicadas em problemas de otimização. No entanto, poucas alcançam desempenho satisfatório quando o problema é complexo, por exemplo multimodal ou multiobjetivo. Entre as técnicas para otimização estão as metaheurísticas, algoritmos heurísticos de base empírica que não garantem a ótimo global mas, normalmente, encontram boas soluções. Várias são as metaheurísticas, como exemplo: Simulated Annealing, Busca Tabu, GRASP, VND, VNS e Colônia de Formigas. Entre as metaheurísticas, os algoritmos da Computação Evolucionária são muito usados, dado a eficácia e as características modular e adaptativa. Estratégia Evolutiva, Programação Genética e Programação Evolutiva, são exemplos de Algoritmos Evolucionários. No entanto, o mais popular na literatura é o Algoritmo Genético, apesar das dificuldades de convergência em alguns casos. Algoritmos Genéticos são métodos de otimização e busca inspirados nos mecanismos de evolução de população de seres vivos. Os algoritmos, baseados nesta técnica, seguem o princípio da seleção natural e sobrevivência do mais apto de Charles Darwin. Analisando a evolução do algoritmo, onde várias gerações são produzidas, uma a cada iteração, e considerando que, a cada nova geração, a anterior é descartada, em parte ou na totalidade, percebe-se que os AGs podem estar eliminando informações relevantes, presentes nos indivíduos descartados, que não foram transmitidas ou mesmo avaliadas pelo algoritmo, causando assim uma perda de informação. Por isso e considerando os poucos trabalhos que abordam a melhoria no aproveitamento das informações, além da necessidade de apresentar soluções evolucionárias de aplicabilidade mais ampla, esse trabalho propõe o Algoritmo Auxiliar Paralelo (AAP), que objetiva auxiliar os AGs com bons indivíduos a partir de um melhor tratamento das estruturas presentes nas populações de pais. O AAP é um algoritmo auxiliar executado em um fluxo paralelo aos AGs e que recombina cromossomos para maximizar o aproveitamento das informações presentes nos indivíduos. Como resultado, o módulo pode gerar indivíduos artificiais mais aptos, que são inseridos na nova geração e manipulados pelos AGs na iteração seguinte. Inspirado na Fertilização in Vitro e no Preimplantation Genetic Diagnosis, que analisa e seleciona bons pré-embriões para serem transferidos µa mãe, o AAP segue um fluxo de Coleta, Manipulação, Seleção e Transferência de bons indivíduos. Para testar o desempenho do algoritmo proposto (AAP) e de seus operadores quando acoplados aos AGs, optou-se por dois problemas benchmark. O primeiro, de minimização da função Rastrigin, por ter um grande espaço de busca, ser não linear e ter um alto grau de multimodalidade e, o segundo, o da Mochila Multidimensional (Multidimensional Knap- sack Problem), por ser um problema altamente combinatório e multidimensional. Com isso, foi possível medir o desempenho da proposta em dois tipos diferentes de problema: otimização de função multimodal não restritiva e otimização combinatória restritiva. O AAP foi testado e comparado com o AG canônico, identificando a melhoria de desempenho com o acréscimo da proposta, e com um algorítmo híbrido AG-BT, que tem características de busca local e global. Foram construídos 39 cenários dos problemas abordados para os testes. Os resultados apresentados mostram o AAP com uma boa ferramenta para auxiliar o AG a melhorar o desempenho de convergência. Percebe-se, também, que houve uma considerável melhoria na velocidade de convergência sem prejudicar a qualidade da solução final. Dados os resultados e a estrutura modular do AAP, que permite outras variações e novos operadores, acredita-se que o AAP pode ser útil em várias aplicações e aplicável a outras heurísticas populacionais.
Abstract: There are several techniques applied to optimization problems. However, few achieve satisfactory performance when the problem is complex, for example multi-modal or multi- objective. The metaheuristics, examples of optimization techniques, are heuristic algo- rithms that can not guarantee the global optimum, but usually ¯nd good solutions. There are several metaheuristics, as an example: Simulated Anneling, Tabu Search, GRASP, VND, VNS and Ant Colony. Among the metaheuristics, the algorithms of Evolu- tionary Computation is one of the most used, since the e®ectiveness and modular/adaptive features. Evolution strategy, Genetic programming and Evolutionary programming are examples of evolutionary algorithms, however, the pioneer and the most popular in the literature is the Genetic Algorithm, despite the di±culties of convergence in some cases. Genetic Algorithms (GA) are optimization and search methods inspired by the evolu- tion of living beings population. Algorithms, based on this technique, follow the principle of natural selection and survival of the fittest (Charles Darwin). When we analyze the GA, where several generations are produced, one on each itera- tion, and considering that each new generation the old one is partially or totally discarded, the GA may be removing relevant information within individuals discarded, which were not transmitted or evaluated by the algorithm. Therefore, and considering the few studies that address the improvement in the use of the information, and the need to present evolutionary solutions with wider applicability, this paper proposes the Algoritmo Auxiliar Paralelo (AAP), which aims to assist the GA with good individuals from better treatment of the structures present in parents populations. The AAP is an auxiliary module running on a parallel °ow to the GA and that recombine chromosomes to maximize the use of the information present in individuals. As a result, the module can generate artificial fittest individuals, which are inserted in the new generation and manipulated by the GA in the next iteration. Inspired by In Vitro Fertilization and the Preimplantation Genetic Diagnosis, which reviews and selects good pre-embryos to be transferred to the mother, the AAP following a °ow of Collection, Manipulate, Select and Transfer of good individuals. To test the performance of the proposed algorithm (AAP), and their operators, when linked to the GA, we chose two benchmark problems. The ¯rst, Rastrigin function by ha- ving a large search space, non-linear and have a high degree of multimodality. The second, the Multidimensional Knapsack Problem, as a multidimensional and highly combinatorial problem. Therefore, it was possible to measure the performance of the proposal in two dif- ferent types of problem: non-restrictive multimodal function and restrictive combinatorial optimization. The AAP has been tested and compared with the canonical GA, identifying the performance of the proposal, and with a hybrid algorithm GA-TS (Tabu Search), which has characteristics of global and local search. We constructed 39 sets of the addressed problems for the tests. The results show the AAP as a good tool to assist the GA to improve the convergence performance. It is noticed also that there was a considerable improvement in the speed of convergence without a®ecting the quality of the ¯nal solution. Given the results and the modular structure of AAP, allowing other changes and new operators, we believed that the AAP may be useful in various applications and applicable to other populations heuristics.
Keywords: Velocidade de convergência
Computação evolucionária
Metaheurística
Otimização
Speed of convergence
Genetic algorithms
Evolutionary computation
Metaheuristic
Optimization
Algoritmos genéticos
Otimização combinatória
metadata.dc.subject.cnpq: CNPQ::ENGENHARIAS::ENGENHARIA ELETRICA
metadata.dc.language: por
metadata.dc.publisher.country: BR
Publisher: Universidade Federal de Uberlândia
metadata.dc.publisher.initials: UFU
metadata.dc.publisher.department: Engenharias
metadata.dc.publisher.program: Programa de Pós-graduação em Engenharia Elétrica
Citation: CAMILO JUNIOR, Celso Gonçalves. Um Algoritmo Auxiliar Paralelo inspirado na Fertilização in Vitro para melhorar o desempenho dos Algoritmos Genéticos. 2010. 147 f. Tese (Doutorado em Engenharias) - Universidade Federal de Uberlândia, Uberlândia, 2010.
URI: https://repositorio.ufu.br/handle/123456789/14267
Issue Date: 5-Mar-2010
Appears in Collections:TESE - Engenharia Elétrica

Files in This Item:
File Description SizeFormat 
celso.pdf1.89 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.