Algoritmo Evolutivo baseado na representação Nó-Profunidade aplicado em problemas de projeto de redes

Thiago Henrique Nunes de Souza; Danilo Sipoli Sanches

doi:10.20906/CPS/SICITE2015-0212

Resumo

Os problemas de otimização combinatória em geral, são problemas onde necessita-se de um grande processamento para resolve-los. Neste contexto, este relatório aborda o PCV (Problema do caixeiro-viajante), este problema consiste na procura de um circuito que possua a menor distância, começando em uma cidade qualquer, entre várias, visando passar em cada cidade precisamente uma vez e regressando à cidade de partida. Devido ao grande processamento para se encontrar uma solução ótima para este problema, é proposto na literatura diversas heurísticas para a resolução do mesmo, que otimizam o tempo de resposta e em alguns casos o tornando possível de se resolver. Neste relatório é proposto um método para a resolução do PCV, por meio da RNP (Representação Nó-Profundidade), como um modelo de individuo para um AGM (Algoritmo Genético Modificado), onde em vez de conter, os operadores de cruzamento e mutação, utilizou-se os operadores de modificação da RNP, PAO (do inglês, Preserve Ancestor Operator) e CAO (do inglês, Change Ancestor Operator) devidamente modificados para a sua utilização no PCV. Por fim os autores propõem um terceiro operador, OP3, afim de obter uma maior otimização para este algoritmo, realizando assim experimentos com três bases distintas da TSPLIB (Library of Traveling Salesman Problems). Dentro destas bases já citadas, será feita a análise de cada operador, afim de uma melhor otimização do algoritmo. Palavras-chave: representação nó-profundidade; inteligência artificial; algoritmos genéticos; problema de otimização combinacional, caixeiro-viajante.

Palavras-chave: representação nó-profundidade; inteligência artificial; algoritmos genéticos; problema de otimização combinacional; caixeiro-viajante