Um Algoritmo Auxiliar Paralelo inspirado na Fertilização in Vitro para melhorar o desempenho dos Algoritmos Genéticos

AUTOR(ES)
DATA DE PUBLICAÇÃO

2010

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.

ASSUNTO(S)

engenharia eletrica computação evolucionária algoritmos genéticos otimização combinatória velocidade de convergência metaheurística speed of convergence genetic algorithms otimização optimization metaheuristic evolutionary computation

ACESSO AO ARTIGO

Documentos Relacionados