Integração das principais características de Algoritmos Evolutivos Multiobjetivo aplicado no problema do caixeiro viajante biobjetivo

vinicius henrique moraes de oliveira; Danilo Sipoli Sanches

doi:10.20906/CPS/SICITE2015-0329

Resumo

Algoritmo genético é uma técnica, inspirada nas teorias darwinianas que apareceu em meados dos anos 70, após John H. Holland publicar a obra "Adaptation in Natural and Artificial Systems"[1]. A inspiração darwiniana se deve ao fato de que algoritmos genéticos usam conceitos relacionados a reprodução, crossover, mutação. Os melhores indivíduos, que na verdade são soluções para o problema a ser tratado, são selecionados para reprodução e consequentemente acaba gerando filhos com as características dos pais. O processo de seleção e reprodução ocorre durante N gerações. Existem várias técnicas dentro do algoritmo genético para resolver esse problema. No presente relatório será proposta uma alternativa de resolução, bem como a comparação dessa alternativa com o método NSGA2. Para a comparação será analisado o tempo para encontrar a fronteira de Pareto e a distribuição dos indivíduos ao longo da fronteira. No modelo proposto foi incorporado características de outros algoritmos evolutivos, como a crowdist do NSGA2. O algoritmo genético desenvolvido utiliza duas populações principais. Cada população está ligada a uma variável relacionada ao trajeto de uma cidade para a outra, e os indivíduos dessas populações são avaliados de acordo com suas respectivas variáveis. Os testes realizados com o modelo proposto e sua comparação com o algoritmo NSGA2 mostra que, embora não atendendo as expectativas para encontrar uma fronteira de Pareto dispersa, ele tem a capacidade de encontrar indivíduos pertencentes à fronteira, e que são soluções boas para apenas um objetivo, mas levando em consideração o outro. Foi chegado à conclusão que a forma como os indivíduos são selecionados para reprodução é um fator essencial. É a partir desse fator que determina se os filhos serão ricos em diversidades ou se vão convergir para um pequeno grupo de soluções.

Palavras-chave: Algoritmo genético; Computação evolutiva; Computação bio-inspirada; Inteligência Computacional