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

Resumo

O documento apresenta os conceitos básicos dos algoritmos genéticos, como mutação, cruzamento, elitismo e critérios de parada. Mostra depois a aplicação destes algoritmos ao Problema do Caixeiro Viajante (TSP), com os passos principais do método. Por fim, introduz a inteligência por enxame e as suas vantagens na resolução de problemas.

Pontos-chave

A mutação simula erros que ocorrem com pequena probabilidade na duplicação de cromossomos.
O cruzamento (crossover) combina informações genéticas de dois pais para gerar novos indivíduos, podendo ser de um ponto, multi-pontos ou uniforme.
O elitismo garante a passagem da melhor solução, ou das melhores soluções, para a geração seguinte.
O TSP procura o circuito de menor distância total que visita cada cidade uma única vez e regressa à cidade inicial.
Os algoritmos genéticos resolvem o TSP em menor tempo, mas não garantem encontrar a solução ótima.
Na inteligência por enxame, o comportamento coletivo dos indivíduos produz soluções coerentes e simples.

Teste-se

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

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.
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.
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.
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.

Perguntas frequentes

O que é o Problema do Caixeiro Viajante?

É o problema de encontrar um circuito que minimize a distância total percorrida, visitando todas as cidades, com cada cidade visitada apenas uma vez. O circuito começa e termina na cidade inicial.

Os algoritmos genéticos garantem a solução ótima para o TSP?

Não. Os algoritmos genéticos podem resolver o TSP em menor tempo, mas não há garantia de encontrar a melhor solução.

Quais são as abordagens de cruzamento mencionadas?

O texto refere três abordagens: cruzamento de um ponto, cruzamento de múltiplos pontos e cruzamento uniforme.