Seminário de Teoria da Computação

    Fundamentos de Algoritmos Genéticos e sua 
 aplicação para o problema do Caixeiro Viajante


             Silvana Livramento

       Sexta-feira, 11 de abril de 2003
        Auditório do IC (IC1), 13:00hs



Algoritmos Genéticos (AGs) são métodos adaptativos que podem ser
udados para resolver problemas de otimização e de busca. Eles são
baseados nos processos genéticos dos organismos biológicos. Através de
muitas gerações, populações naturais evoluem de acordo com os
princípios da seleção natural e da ``sobrevivência do mais apto'',
discutidos por Charles Darwin em \emph{The Origin of the Species}.
Imitando este processo, algoritmos genéticos são capazes de
``evoluir'' para boas soluções para problemas do mundo real, se forem
codificados apropriadamente.

Iremos mostrar sua aplicação para o problema do Caixeiro Viajante (TSP), por
vários motivos. Primeiro TSP é conceitualmente muito simples, e é a
mãe de todos os problemas. O espaço de busca do TSP é a permutação de
$n$ cidades, onde $n$ é o número de cidades que o caixeiro deve
visistar. Qualquer permutação de $n$ cidade é uma solução para o
problema.

Durante as últimas décadas, muitos algoritmos foram criados para
aproximar a solução ótima do TSP. TSP também se tornou alvo para a
comunidade do AG, e vários algoritmos baseados em genética foram
criados. Esses algoritmos tentam produzir uma solução próxima da
solução ótima mantendo uma população de soluções potenciais que sofrem 
algumas
transformações binárias e unárias, de acordo com um esquema de
seleção baseado na aptidão de cada indivíduo.