ALGORITMO GENÉTICO COM INTERAÇÃO SOCIAL N-PESSOAS (NpSIGA)

RESUMO: Este trabalho apresenta um estudo extensivo sobre Algoritmo Genético com Teoriados Jogos para N-pessoas, o que aumenta a variabilidade da população e diminui aprobabilidade do algoritmo ficar preso em um ótimo local. Os indivíduos da populaçãoapresentam dois cromossomos, sendo: um para a solução do problema em questão, que nocaso desse trabalho são instâncias do Problema do Caixeiro Viajante (PCV); e o outro para acodificação genética do comportamento, necessária para definir a estratégia a ser utilizada por eles durante as disputas dos jogos. Para a realização dos experimentos, o processo deimplementação foi definido e construído cronologicamente da seguinte forma:Implementaçãodo algoritmo genético clássico (AG); Combinação do AG com a fase deinteração social (SIGA), utilizaçãodo Paradigma do Dilema do Prisioneiro Clássico (2-pessoas); Aplicação do conceito de N-pessoas, onde os indivíduos possuem uma taxa detolerância à traição. Além disso, foram ainda implementadas as seguintes funcionalidades: emcada geração, a população é composta por indivíduos únicos; elitismo; a possibilidade dospais selecionados para cruzamento não gerarem descendentes e, assim, posteriormente,sofrerem ou não mutação; uma mutação com memória a qual pode ou não ocorrer.Finalmente, foram realizados 16 testes paraa instância denominada de BR-26, que define adistância entre todas as capitais brasileiras interligadas por estradas. Os resultadosencontrados demonstram a viabilidade da metodologia e, ainda, apontam para muitas outraspossibilidades de aplicação e expansão.

Palavras-chave: NpSIGA, Computação Evolucionária, Algoritmos Genéticos, Teoria dosJogos N-Jogadores, Paradigma do Dilema do Prisioneiro.

Autor(es): Lilian de Jesus Chaves Dias, Pedro Victor Pontes Pinheiro, Roberto Yuri da Silva Franco.