Algoritmos Gen ticos

Algoritmos Genéticos
Aplicação ao problema do caixeiro viajante
Aluno: Francis Silveira Andrade

O que é um algoritmo genético?
• É uma técnica de busca utilizada na ciência da computação para achar soluções aproximadas em problemas de otimização e busca.
• Fundamentado principalmente pelo americano John Henry Holland.
• São uma classe particular de algoritmos evolutivos que usam técnicas inspiradas pela biologia evolutiva como hereditariedade, mutação, seleção natural e recombinação (ou crossing over).

O que é um algoritmo genético?
• Uma simulação de computador em que uma população de representações abstratas de solução é selecionada em busca de soluções melhores.
• A cada geração, a adaptação de cada solução na população é avaliada, alguns indivíduos são selecionados para a próxima geração, e recombinados ou mutados para formar uma nova população.

População
• A população é um conjunto de soluções gerada aleatoriamente.
• A partir da população o algoritmo vai aplicar combinar os indivíduos e obter uma nova população criando assim uma nova geração.
• Quanto maior a população maior a probabilidade de se achar uma ótima solução.
• No problema do caixeiro viajante um individuo da população será uma rota entre as cidades.

Máximo de gerações
• A quantidade de gerações define quantas vezes o algoritmo vai ser executado e consequentemente quantas vezes haverá os processos de recombinação, mutação e etc.
• Quanto maior a quantidade de gerações maior é a probabilidade de achar uma ótima solução.

Porcentagem de mutação
• A porcentagem de mutação é responsável por quantificar qual a probabilidade de durante uma recombinação existir uma mutação aleatória. • Caso o índice de mutação seja muito alto uma boa solução pode ser descartada por uma mutação que a tornou ruim.

Tamanho do grupo de analise
• A cada geração o algoritmo pega um grupo aleatório de indivíduos para serem analisados.
• Os dois melhores indivíduos vão ser selecionadas para serem pais de dois novos