Algoritimos Genéticos [AG] VI


Amigos estamos de volta (: para fazer a continuação de algoritimos genéticos V .

Cruzamento e Mutação

Cruzamento e Mutação são os dois operadores básicos de AG. O desempenho do AG depende muito deles. O tipo e a implementação desses operadores dependem da codificação e também do problema Há diversas maneiras de como fazer o cruzamento e a mutação. Neste capítulo descreveremos brevemente alguns exemplos e sugestões de como fazê-los para diversos tipos de codificação.

Codificação Binária
Cruzamento
Ponto de Cruzamento Único - um ponto de cruzamento é escolhido, a série binária desde o começo do cromossoma até o ponto de cruzamento é copiada do primeiro pais e o resto copiado do outro pai.





11001011+11011111 = 11001111

Dois pontos de cruzamento - são definidos dois pontos de cruzamento, a série binária desde o início do cromossoma até o primeiro ponto de cruzamento é copiada do primeiro pai, a parte do primeiro ponto de cruzamento até o segundo ponto é copiada do outro pai e o resto do cromossoma é copiado do primeiro pai novamente






11001011 + 11011111 = 11011111


Cruzamento Uniforme - os bits são copiados aleatóriamento do primeiro ou segundo pai





11001011 + 11011101 = 11011111

Cruzamento Aritmético - é realizada uma operação aritmética para obter a nova geração





11001011 + 11011111 = 11001001 (AND)

Mutação

Inversão de Bit - determinados bits são invertidos





11001001 => 10001001
Codificação por Permutação

Cruzamento

Ponto de Cruzamento Único - um ponto de cruzamento é selecionado e a permutação é copiada atéone crossover point is selected, the permutation is copied do primeiro pai até o ponto de cruzamento, daí o outro pai é rastreado e se o número ainda não estiver na descendência, é adicionado
Nota: há outras maneiras de obter o resto após o ponto de cruzamento

(1 2 3 4 5 6 7 8 9) + (4 5 3 6 8 9 7 2 1) = (1 2 3 4 5 6 8 9 7)

Mutação

Mudança de Ordem - dois números são escolhidos e trocados entre si

(1 2 3 4 5 6 8 9 7) => (1 8 3 4 5 6 2 9 7)

Codificação de Valores

Cruzamento

Todos os cruzamentos de codificação binária podem ser usados

Mutação

Adicionando um número pequeno (para codificação de valores reais) - um número pequeno é adicionado a (ou subtraído de) valores selecionados

(1.29 5.68 2.86 4.11 5.55) => (1.29 5.68 2.73 4.22 5.55)
Codificação em Árvore

Cruzamento

Cruzamento de Árvores - um ponto de cruzamento é escolhido em ambos os pais, os pais são divididos nesse ponto e as partes abaixos do ponto de cruzamento são trocadas para produzir a descendência








Mutação

Mudando o operador - os nós escolhidos são mudados

Problema do Caixeiro Viajante
O problema do caixeiro viajante já foi mencionado em capítulos anteriores. Relembrando, são dadas cidades e as distâncias entre elas. O caixeiro viajante tem que visitar todas elas, mas não quer viajar demais. A tarefa consiste em encontrar a seqüência de cidades que faz com que a distância percorrida seja a menor possível. Em outras palavras, o problema é achar a rota mínima Hamiltoniana num gráfico de N nós.

Implementação

Foi usada uma população de 16 cromossomas. Para codificá-los foi utilizada Codificação por Permutação - você pode encontrar no capítulo sobre codificação, como codificar a permutação das cidades para o Problema do Caixeiro Viajante. O problema é selecionado completando o gráfico (isto é, cada nó é conectado ao outro) com distâncias euclidianas. Note que depois de adicionar ou excluir uma cidade é necessário criar novos cromossomas e reiniciar completamente o algoritmo.

Você pode escolher o tipo de cruzamento e de mutação. Veja a seguir uma descrição dos seus significados:

Cruzamento

* Ponto único - parte do primeiro pai (isto é, parte da seqüencia das cidades) é copiada e o resto das cidades é copiada na mesma seqüência do segundo pai
* Dois pontos - duas partes do primeiro pai são copiadas e o restante (que está entre essas duas partes) é colocada na mesma ordem que estão no segundo pai
* Nenhum - sem cruzamento, a descendência é uma cópia exata dos pais

Mutação

* Aleatória Normal (Normal Random Mutation) - umas poucas cidades são escolhida e trocadas
* Aleatória se Melhora (Random, only improving) - umas poucas cidades são escolhidas aleatóriamente somente se elas melhoram a solução (isto é, aumentam a adequação)
* Sistemática se Melhora (Systematic, only improving) - cidades são escolhidas sistematicamente e trocadas somente se melhoram a solução (aumentam a adequação)
* Aleatória Melhorada (Random improving) - o mesmo que "Aleatória se Melhora", porém antes que a mutação aleatória normal seja executada
* Sistemática Melhorada (Systematic improving) - o mesmo que "Sistemática se Melhora", porém antes que amutação aleatória normal seja executada
* Nenhuma (None) - sem mutação


Exemplo

O applet seguinte mostra o AG otimizado para o problema do caixeiro viajante. O botão "Change View" muda a vista de toda a população para a melhor solução e vice versa. Você pode adicionar e retirar cidades clicando no gráfico. Depois de adicionar ou excluir uma cidade, uma rota aparecerá entre elas, assim como uma nova população de cromossomas aleatórios também é criada. Repare também que estamos resolvendo o problema em um gráfico completo.
Experimente executar o AG com diferentes tipos de cruzamento e mutação e repare como o desempenho (e a velocidade - adicione mais cidades para perceber) do AG muda. Veja o exemplo aqui!
Recommendações

Parâmetros dos AG
Neste capítulo são dadas recomendações básicas caso você tenha decidido implementar algoritmos genéticos. Essas recomendações são genéricas. Você provavelmente precisará experimentar com seu próprio AG para um problema específico, porque não existe uma teoria geral que possa ser aplicada no auxílio da sintonia dos parâmetros dos AG para qualquer problema.

As recomendações são frequentemente resultado de estudos empíricos dos AG, que em geral, são realizados somente em codificação binária.

* Taxa de Cruzamento
A taxa de cruzamento deve em geral ser alta, cerca de 80%-95%. Entretanto, alguns resultados mostram que para alguns tipos de problemas, uma taxa de cruzamento de cerca de 60% é o melhor.
* Taxa de Mutação
Por outro lado, a taxa de mutação deve ser muito baixa. As melhores taxas parecem estar na faixa de 0.5%-1%.
* Tamanho da População
Pode ser um pouco surpreendente que populações de tamanho muito grande, normalmente não aumentam o desempenho do AG (no sentido de aumentar a velocidade com que são encontradas as soluções). Um bom tamanho para a população é cerca de 20-30, entretanto às vezes tamanhos de 50-100 são relatados como os melhores. Alguns autores também mostram que o melhor tamanho da população depende do tamanho da série codificada (cromossomas). Isto significa que se você tem cromossomas com 32 bits, a população deve ser maior do que se você tivesse cromossomos com 16 bits.
* Seleção
A Seleção através da Roleta pode ser usada, mas mas às vezes a Seleção por Classificação pode ser melhor. Verifique o capítulo sobre seleção para saber as vantagens e desvantagens. Existem também alguns métodos mais sofisticados que mudam os parâmetros de seleção durante a execução do AG. Basicamente, eles tem comportamento similar a tempero falsificado. Elitismo Deve ser usado se você não tem outro método para preservar a melhor solução. Você também pode experimentar a Seleção do Estado Estacionário.
* Codificação
A codificação depende do problema e também do tamanho das instâncias do problema. Veja o capítulo sobre codificação para algumas sugestões ou veja outros recursos.
* Tipos de Cruzamento e Mutação
Os operadores dependem da codificação e do problema. Verifique o capítulo sobre operadores para algumas sugestões. Você pode também verificar outros sites.


Aplicações dos AG

Algoritmos genéticos têm sido utilizados para resolver problemas complexos (tais como os problemas NP-difíceis), para aprendizado de máquinas e também para o desenvolvimento de programas simples. Eles têm sido também usados em algumas aplicações artísticas como pintura e música.

Uma vantagem dos AG é o seu paralelismo. AG percorre o espaço das soluções usando mais indivíduos (e com genótipos em vez de fenótipos) de forma que eles são menos susceptíveis de "enroscar" em um extremo local do que os outros métodos.

Eles também são muito simples de implementar. Uma vez que você implantou a parte básica do AG, você simplesmente precisa escrever um novo cromossoma (apenas um objeto) para resolver outro problema. Com uma codificação, você simplesmente muda a função de adequação e está tudo pronto! Entretanto, para alguns problemas, a escolha e implementação da função de adequação pode ser difícil.

A desvantagem dos AG é o tempo de processamento. Os AG podem ser mais lentos do que os outros métodos. Porém, desde que possamos terminar o cálculo sem restrições severas de tempo, o tempo mais longo é aceitável (principalmente com os computadores cada vez mais rápidos).

Para ter uma idéia sobre os tipos de problemas resolvidos com AG, é apresentada a seguir uma lista de algumas aplicações:

* Sistemas Dinâmicos não Lineares - predição, análise de dados
* Projeto de Redes Neurais, ambos: determinação da arquitetura e dos pesos
* Trajetória de Robôs
* Desenvolvimento de programas em LISP (programação genética)
* Planejamento Estratégico
* Determinação da Forma de Moléculas de Proteinas
* Determinação de Rotas e Sequenciamento de Tarefas
* Determinação de Funções para criação de imagens

Mais informação pode ser encontrada nos links :
Veja a seguir alguns links selecionados para Web Sites ou servidores de arquivos (ftp). Você pode utilizá-los para encontrar mais informações e materiais sobre Algoritmos Genéticos.

ENCORE, the EvolutioNary COmputation REpository network
Rede Repositório de Computação Evolucionária
ftp://alife.santafe.edu/pub/USER-AREA/EC/ (tem também alguns outros nós)

FAQ - The Hitch-Hiker's Guide to Evolutionary Computation
O guia Hitch-Hiker sobre Computação Evolucionária
ftp://alife.santafe.edu/pub/USER-AREA/EC/FAQ/www/index.html

FAQ - Genetic programming
Perguntas mais freqüentes sobre Programação Genética
http://www-dept.cs.ucl.ac.uk/research/genprog/gp2faq/gp2faq.html

The Genetic Algorithms Archive - many links, information about mailing list, some fun stuff
Arquivo de Algoritmos Genéticos - vários links, informações sobre listas, e algum material divertido
http://www.aic.nrl.navy.mil:80/galist/

Artificial Life Online - Vida Artificial Online - links.
Se você está procurando por material introdutório, veja aqui
http://alife.santafe.edu/

Yahoo! Science:Computer Science:Algorithms:Genetic Algorithms - diretório de outros links
http://www.yahoo.com/Science/Computer_Science/Algorithms/Genetic_Algorithms/

Grupos Usenet comp.ai.genetic e comp.ai.alife

e o principal deixa aqui claro que todo este exelente conteudo e seus autores com algumas adaptações minhas!
Estas páginas foram desenvolvidas durante os meses de Agosto e Setembro de 1998 na Universidade de Ciências Aplicadas de Dresden por Marek Obitko, aluno da Universidade Tcheca Técnica em Praga.

A primeira versão dos applets foi escrita durante o semestre do verão de 1998 na Universidade Tcheca Técnica, sob a supervisão do Professor Associado Pavel Slavík. Durante a estadia em Dresden o projeto foi supervisionando pelo Professor Walter Pätzold da Universidade de Ciências Aplicadas de Dresden.

Todas as Páginas e os Applets Java foram criados por Marek Obitko, Copyright © 1998. Se você tiver qualquer comentário, pergunta ou sugestão, envie para o autor.

A versão destas páginas para o Português do Brasil foi feita por Hermelindo Pinheiro Manoel em Setembro/2004 e sua publicação foi autorizada pelo autor (Marek Obitko).

enfim é isso bons estudos
[]'s
Algoritimos Genéticos [AG] VI Algoritimos Genéticos [AG]    VI Reviewed by Kembolle Amilkar on sexta-feira, janeiro 16, 2009 Rating: 5

Nenhum comentário