Quais são os casos de uso típicos da Programação Genética?

votos
33

Hoje eu li neste blog por Roger Alsing sobre como pintar uma réplica da Mona Lisa usando apenas 50 polígonos semi transparentes.

Eu sou fascinado com os resultados para esse caso particular, então eu queria saber (e esta é a minha pergunta): Como funciona a programação genética e que outros problemas poderiam ser resolvidos pela programação genética?

Publicado 10/12/2008 em 09:58
fonte usuário
Em outras línguas...                            


8 respostas

votos
28

Há algum debate sobre se programa Mona Lisa de Roger é Programação Genética em tudo. Parece ser mais perto de um (1 + 1) Estratégia de Evolução . Ambas as técnicas são exemplos do campo mais amplo de Computação evolutiva, que também inclui algoritmos genéticos .

Programação Genética (GP) é o processo de evolução de programas de computador (geralmente sob a forma de árvores - muitas vezes programas Lisp). Se você está perguntando especificamente sobre GP, John Koza é amplamente considerado como o principal especialista. Seu site inclui lotes de links para mais informações. GP é normalmente muito computacionalmente intensiva (para problemas não triviais que muitas vezes envolve uma grande rede de máquinas).

Se você está pedindo mais geral, algoritmos evolucionários (EAS) são normalmente utilizados para fornecer boas soluções aproximadas para problemas que não podem ser resolvidos facilmente usando outras técnicas (tais como problemas NP-difíceis). Muitos problemas de otimização se enquadram nesta categoria. Pode ser muito computacionalmente intensivas para encontrar uma solução exata, mas às vezes uma solução quase ideal é suficiente. Nestas situações técnicas evolutivas podem ser eficazes. Devido à sua natureza aleatória, algoritmos evolucionários não está garantido para encontrar uma solução óptima para qualquer problema, mas muitas vezes eles vão encontrar uma boa solução, se houver.

Algoritmos evolutivos também pode ser usado para resolver os problemas que os humanos realmente não sabem como resolver. Um EA, livre de quaisquer preconceitos ou preconceitos humanos, pode gerar soluções surpreendentes que são comparáveis a, ou melhor do que, os melhores esforços humanos gerado. É apenas necessário que podemos reconhecer uma boa solução se fosse apresentado para nós, mesmo se não sabemos como criar uma boa solução. Em outras palavras, precisamos ser capazes de formular uma eficaz função de fitness .

Alguns exemplos

EDIT: O livro livremente disponível, Um Guia de Campo para Programação Genética , contém exemplos de onde GP produziu humanos competitivo resultados.

Respondeu 10/12/2008 em 13:21
fonte usuário

votos
9

Curiosamente, a empresa por trás da animação caráter dinâmico usado em jogos como Grand Theft Auto IV e o último jogo Star Wars (The Force Unleashed) utilizado programação genética para desenvolver algoritmos de movimento. O site da empresa é aqui e os vídeos são muito impressionantes:

http://www.naturalmotion.com/euphoria.htm

Eu acredito que eles simularam o sistema nervoso do personagem, em seguida, distribuídos aleatoriamente as conexões em certa medida. Eles então combinaram os 'genes' dos modelos que caminharam mais distante para criar mais e mais capazes 'crianças' em sucessivas gerações. trabalho de simulação realmente fascinante.

Eu também vi algoritmos genéticos utilizados no caminho de encontrar autômatos, com formigas em busca de comida sendo o exemplo clássico.

Respondeu 10/12/2008 em 13:55
fonte usuário

votos
8

algoritmos genéticos pode ser usado para a maioria resolver qualquer problema de otimização. No entanto, em muitos casos, há melhores métodos mais directos para resolvê-los. É na classe de algoritmos de meta-programação, o que significa que é capaz de se adaptar a praticamente qualquer coisa que você pode jogar nele, uma vez que você pode gerar um método de codificação de uma solução potencial, combinando / mutação soluções e decidir qual As soluções são melhores que outros. GA tem uma vantagem sobre outros algoritmos de meta-programação em que ele pode lidar com máximos locais melhor do que um algoritmo hill-climbing puro, como o recozimento simulado.

Respondeu 10/12/2008 em 10:33
fonte usuário

votos
6

Eu usei programação genética na minha tese para simular a evolução das espécies com base no terreno, mas que é, naturalmente, a aplicação A-vida de algoritmos genéticos.

Os problemas GA são bons em são problemas de subida . O problema é que, normalmente, é mais fácil para resolver a maioria desses problemas com a mão, a menos que os fatores que definem o problema são desconhecidos, em outras palavras, você não pode conseguir que o conhecimento de algum modo mais, dizer as coisas relacionadas com as sociedades e comunidades, ou em situações onde você tem um bom algoritmo, mas você precisa ajustar os parâmetros, aqui GA são muito úteis.

Uma situação de sintonia fina que eu fiz foi de afinar vários jogadores Othello IA com base nos mesmos algoritmos, dando cada diferentes estilos de jogo, tornando assim cada oponente única e com seus próprios caprichos, então eu tinha-lhes competem para abater o topo 16 AI de que eu usei no meu jogo. A vantagem foi que eles eram todos muito bons jogadores de mais ou menos a mesma habilidade, por isso foi interessante para o oponente humano, porque não podiam adivinhar o AI tão facilmente.

Respondeu 10/12/2008 em 10:11
fonte usuário

Respondeu 10/12/2008 em 10:10
fonte usuário

votos
5

Você deve perguntar a si mesmo: "Eu (a priori) pode definir uma função para determinar quão boa seja uma solução particular é em relação a outras soluções?"

Na Mona Lisa exemplo, você pode facilmente determinar se a nova pintura parece mais com a imagem de origem do que a pintura anterior, Programação de modo genética pode ser "facilmente" aplicado.

Respondeu 10/12/2008 em 10:30
fonte usuário

votos
4

Eu tenho alguns projetos usando Algoritmos Genéticos. GA são ideais para problemas de otimização, quando você não pode desenvolver um algoritmo totalmente seqüencial, exato não resolver um problema. Por exemplo: qual é a melhor combinação de um CARACTERÍSTICAS carro para torná-lo mais rápido e ao mesmo tempo mais econômica?

No momento eu estou desenvolvendo um GA simples para elaborar listas de reprodução. Meu GA tem de encontrar as melhores combinações de álbuns / canções que são semelhantes (esta similaridade será "calculado" com a ajuda de last.fm) e sugere playlists para mim.

Respondeu 10/12/2008 em 13:59
fonte usuário

votos
2

Há um campo emergente da robótica chamada Evolutionary Robotics ( w: Robotics evolutivos ), que usa algoritmos genéticos (GA) pesadamente.

Veja w: Algoritmo Genético :

Simples geracional pseudocódigo algoritmo genético

  1. Escolha população inicial
  2. Avaliar a aptidão de cada indivíduo na população
  3. Repita até terminação: (limite de tempo ou aptidão suficiente alcançado)
  4. Escolha melhor ranking indivíduos para reproduzir
  5. Raça nova geração por meio de cruzamento e / ou mutação (operações genéticos) e de dar à luz crias
  6. Avaliar as aptidões individuais da prole
  7. Substituir parte pior ranking da população com prole

A chave é a parte de reprodução, o que poderia acontecer sexualmente ou assexuadamente, utilizando operadores genética Crossover e Mutação .

Respondeu 14/12/2008 em 23:38
fonte usuário

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more