Algoritmos Genéticos

Hoje um belo dia de sol de sábado vamos falar um pouco sobre Algoritmos Genéticos. O nome é bonito e a idéia é bem empolgante vamos lá.

Um jardim no mosteiro

Século XIX e Gregor Mendel um religioso que gostava de ervilhas professor da uma faculdade estudava como as características passavam nas gerações de ervilhas caracteríticas como cor das flores tamanho formato das ervilhas etc.

Ele criou o que conhecemos hoje como Genética em seu trabalho com plantas sugeriu a idéia dos genes e das mutações entre os pais para a geração dos decendentes.

Só os melhores sobrevivem

Baseado nas idéias de Darwin e de Mendel os Algoritmos genéticos simulam um esquema de evolução entre as respostas possíveis para um problema. A idéia é colocar várias respostas possíveis em um ambiente de competição onde as respostas mais próximas da ideal tem mais chance de procriar e seu descendentes serão respostas melhores ao problema.

Tá e como se faz genes no computador?

Lembra do problema do cacheiro viajante? (é aquele do cara que vai em várias cidades e o objetivo é achar o menor caminho passando por todas elas uma única vez) Um A.G. para isto poderia ser feito da seguinte forma:

O nosso indivíduo tem em seus genes a ordem na qual as cidades devem ser visitadas a soma dos percursos é inversa a adaptabilidade dele ao ambiente assim quanto menor o percurso mais adaptado ele estará.

1. Produzimos uma geração inicial aleatória com vários indivíduos
2. Escolhemos os melhores indivíduos e eles cruzam (é, eles fazem isso mesmo que vc está pensando)
3. Depois os filhos herdam metade do caminho das cidades de cada um dos seus genitores
4. Esses filhos devem ter leves mutações que proporcionem algo aleatório nas novas gerações.
5. E aí os filhos crescem os pais morrem e aqui entra mais um detalhe alguns membros das gerações anteriores se muito bem adaptados podem sobreviver para cruzar com a nova geração (é os coroas ricos também são pegadores!).

E isso se repete até que se encontre um valor satisfatório. Algo do tipo a distância a ser percorrida deve ser menor que X.

Não vou me estender muito mais. Quer entender AG de verdade? Visite http://www.gta.ufrj.br/~marcio/genetic.html ou http://www.din.uem.br/ia/geneticos/ para demonstrações visuais (com applets e código fonte) e um monte de experimentos com Inteligênica artificial, Vida artificial e Bioinformática sugiro o site do Israelense Ariel Dolan em http://www.aridolan.com/ muito legal!