Algoritmo Genético

Algoritmo Genético para o caixeiro viajante
Carlos Melies Felipes
Leonardo Antonio Pinheiro
Paulo Eduardo Martins

Problema do caixeiro viajante
O problema do caixeiro viajante consiste em passar por todas as cidades pegando a menor rota sem repetir a mesma cidade.

Problema com algoritmos exatos
Como o problema é de caracter exponencial, resolvê-lo com algoritmos exatos pode demandar tempo, dependendo da entrada o tempo pode ser maior do que o tempo de vida de uma pessoa.

Algoritmo Genético
Uma das formas de resolver o problema do caixeiro de forma é por meio de algoritmos genéticos. Ele pode não entregar a resposta ótima. Porém ele irá lhe dar uma resposta.

Cromossomo
O cromossomo foi criado transformando cada cidade em um numero de 0 a N.
Cada numero é um alelo, sendo que o próximo numero nesse vetor é a próxima cidade visitada. Exemplo:
[0,3,2,1] (Cidade 0 para 3 para 2 para 1 para 0)

Definições
● População Inicial
● Função de aptidão
● Função de escolha dos indivíduos para reprodução ● Função de reprodução
● Função de Mutação

População Inicial
Para a população inicial, é iniciado um cromossomo em ordenado de 0 a N, e logo após este vetor é embaralhado para deixar ele com caracter aleatório.
Exemplo:
Vetor inicial: [0,1,2,3]
Vetor Final: [0,3,1,2]

Função de Aptidão (Fitness)
O Fitness é feito calculado a distancia total da rota deste cromossomo, logo após se divide 1 pelo tamanho da rota (1/tamanhoRota) para que os melhores sejam os que possuírem maior Fitness.

Função de Escolha de Indivíduos
Esta é calculada usando o método da roleta, após calculado o fitness se divide cada um deles pela soma de todos os fitness e cada numero restante entra como uma porcentagem de chance de ser escolhido pela roleta, os com maior fitness terão mais chances.

Função de reprodução
Foi feita se usando de PMX (Partially Mapped
Crossover).

Função de Mutação
A mutação é basicamente alterar aleatoriamente um alelo do cromossomo, para manter consistente esta mudança é