Algoritmos Genéticos, TSP e Inteligência por Enxame

Mutação em Algoritmos Genéticos

Simula a ocorrência de erros que acontecem com uma pequena probabilidade durante a duplicação de cromossomos.

Cruzamento (Crossover)

Combina as informações genéticas de dois indivíduos (pais) que geram novos indivíduos (filhos). É responsável por gerar novos indivíduos diferentes (sejam melhores ou piores) a partir de indivíduos já promissores.

Abordagens de Cruzamento

• Um-ponto
• Multi-pontos
• Uniforme

Condição de Parada e Finalização

O algoritmo pode terminar a execução quando:

• O número fixo de iterações tiver sido executado.
• O número de iterações tiver decorrido sem ocorrer um melhoramento na solução.
• Tiver decorrido um determinado intervalo de tempo.
• Tiver sido encontrada uma solução satisfatória.

Elitismo

Garante a passagem da melhor solução, ou o conjunto das melhores soluções, para a próxima geração.

O Problema do Caixeiro Viajante (TSP)

O Problema do Caixeiro Viajante consiste na procura de um circuito que minimize a distância total percorrida, visitando todas as cidades. O circuito começa numa cidade e regressa à cidade inicial, sendo que cada cidade só pode ser visitada uma vez.

Solução com Algoritmos Genéticos

Os Algoritmos Genéticos (AGs) podem ser usados para resolver este problema em menor tempo, embora não haja a garantia de encontrar a solução ótima (melhor solução).

Passos Básicos do Algoritmo Genético para TSP

1. Um conjunto aleatório de rotas é gerado, inicializando a população. Este algoritmo cria uma população inicial “gulosa”, que dá preferência em manter conexões entre cidades que estão mais próximas umas das outras.
2. Escolher as duas melhores rotas da população para o cruzamento (crossover) e combiná-las para gerar duas novas rotas filhas. Há grandes chances destas novas rotas filhas serem melhores que os seus pais.
3. As rotas filhas são inseridas na população, substituindo as duas rotas menos aptas existentes. O tamanho da população mantém-se constante.
4. As novas rotas filhas são repetidamente criadas até atingirem um critério de parada desejado (a melhor rota).

Inteligência por Enxame (Swarm Intelligence)

Tipo de computação baseada numa metáfora para resolver problemas de uma forma distinta. O componente coletivo dos indivíduos numa população resulta em soluções coerentes e simples.

Vantagens da Inteligência por Enxame

• Feedback positivo na descoberta rápida de boas soluções.
• Computação distribuída evita a convergência prematura.
• A heurística gulosa ajuda a encontrar uma solução aceitável rapidamente nas fases iniciais do processo de pesquisa.
• Interação coletiva de uma população de agentes.