Como nós produzimos a próxima geração?

5

Graças a algumas ótimas respostas em um pergunta anterior , acho que agora tenho um melhor entendimento dos GAs, mas ainda estou confuso em alguns pontos. Vou começar com um aqui.

Eu tenho lido sobre como um algoritmo GA funciona e vi o que parecem ser opiniões conflitantes sobre o que você faz em cada geração:

Alguns artigos parecem dizer que você escolhe os dois melhores cromossomos e os acasala, usando as taxas de cruzamento e de mutação para produzir um filhote. Você então substitui o cromossomo com a menor aptidão com a descendência. Isso só muda um cromossomo por geração, o que eu achava que faria para uma mudança muito lenta no geral, e assim uma abordagem lenta para uma solução. Por que não fazer isso por (digamos) os melhores 50% dos cromossomos e substituir os piores 50% em cada geração? Eu não vi isso sugerido.

A outra abordagem que eu vi é escolher dois cromossomos usando algum processo estocástico, como uma roleta, acasalar-los para produzir uma prole, em seguida, repita até que você tenha gerado toda uma nova população. Você então joga toda a última geração e substitui-a pela nova população. Embora isso obviamente produza mais mudanças por geração do que o método anterior, ele tem a (aparente) desvantagem de jogar fora os melhores cromossomos da geração anterior. É claro que esperamos que a prole seja melhor, mas talvez não, e mesmo se forem em geral, você ainda joga fora o que poderia ser cromossomos ainda melhores.

Desculpe se esta é uma pergunta idiota, mas eu não vi uma explicação clara dessa parte do algoritmo, e não tenho certeza de como isso deve ser feito. Eu escrevi meu primeiro código GA ontem à noite, o que não deu certo, mas não teve o desempenho esperado, e estou pensando se estou fazendo essa parte de forma errada.

Obrigado por qualquer ajuda que você possa dar.

Editar: Após alguns comentários e respostas, aqui estão mais informações sobre o problema que estou tentando resolver. Sendo muito novo nisso, comecei com o problema mais simples que encontrei, o de encontrar uma string de todos os 1s. Eu corrijo o comprimento da corda, digamos 20, e a adequação de qualquer cromossomo será o número de 1s dividido por 20.

Minha primeira definição de desempenho foi o quão perto ficou da solução certa. Dada a natureza fácil deste problema, sei que a solução certa é apenas uma cadeia de vinte 1s.

Eu tive mais um jogo, e descobri que aumentando o número de cromossomos ajudou até 20 cordas de comprimento, mas uma vez que eu fiquei acima disso, nunca passou de uma aptidão de cerca de 0,8, ou seja, dezesseis 1s em a string.

Não sei se isso ajuda. Dos comentários, parece que eu só tenho que continuar jogando (vergonha!).

Edit2: Seguindo todos os excelentes comentários, mas especificamente a explicação de Delioth, tentei manter os 50% da população atual com a maior aptidão, e substituir os 50% mais pobres por novos cromossomos criados pela roleta seleção de roda da população atual. Os resultados foram bastante dramáticos, com o GA encontrando a solução correta em cerca de 200 gerações, mesmo quando eu aumentei o comprimento da corda de forma significativa. Isso se compara a não encontrá-lo depois de 10.000 gerações antes!

Eu tentei jogar com a proporção de cromossomos atuais mantidos, mas descobri que, desde que eu me mantivesse longe dos extremos, não fazia muita diferença.

Obrigado a todos pela ajuda. Essa tem sido uma ótima experiência de aprendizado. Eu tenho mais perguntas, então voltarei!

    
por Avrohom Yisroel 21.12.2016 / 15:21
fonte

2 respostas

2

Algoritmos genéticos são uma daquelas peças no CS onde são menos "ciência" e mais "arte", e muito dependentes dos requisitos. Você pode tentar algumas coisas, ajustar um pouco e ver como isso acontece e, eventualmente, chegar ao seu próprio consenso.

Como regra, existem 4 coisas que você pode fazer em várias combinações para criar uma nova geração:

  • Mating, que geralmente produz dois filhos (xxxxx + yyyyy = > xxyyy + yyxxx ou várias outras possíveis divisões)

  • Mutação, mudando uma coisa de um cromossomo e empurrando-a para frente (xxxxx = > xxxyx)

  • Novo sangue, onde geramos um cromossomo totalmente novo na nova geração

  • Não me lembro do nome, mas encaminhar um cromossomo inalterado para a próxima geração também é uma opção.

Em um algoritmo genético típico, você geralmente usa tudo isso, mas geralmente também é inteiramente aleatório. Nós gostamos de usar algum tipo de seleção tendenciosa para melhorar nossas gerações, mas se pegarmos os primeiros e decidirmos mantê-los, o algoritmo tenderá a estagnar - como um exemplo, suponha que tenhamos 10 cópias de xxxyzz em um conjunto de genes. de 20. Se mantivermos o top 50% como está e acasalarmos e sofrermos mutação para criar mais 8, teremos todo um pool de xxxyzz com dois novos bloods e não estamos fazendo nenhum progresso, já que 90% dos nossos cromossomos são os mesmos (ou um pouco fora do mesmo).

Como tal, um algoritmo genético típico assume que cada geração é inteiramente nova, apesar de alguns dos membros serem os mesmos da geração anterior. Tentamos manter o número de membros "mantidos" no mínimo, já que algumas cópias de uma solução "decente" podem facilmente sobrecarregar uma população se houver muitos sendo mantidos, o que leva à estagnação (e uma vez que você atingiu estagnação suficiente , cada geração não está ajudando muito desde que você esteja contando com um novo sangue da sorte ou com uma boa melhoria incremental).

Em um caso em que existem várias soluções 'corretas' muito diferentes (cromossomos finais), você pode precisar ter uma alta taxa de cromossomos inteiramente novos. Em um caso em que você conhece a estrutura geral do resultado, você pode não querer qualquer novo sangue - você pode apenas querer mudanças incrementais nos cromossomos que você tem (já que o sangue novo poderia lhe dar uma resposta totalmente não funcional) - mas você pode manter sangue novo no algoritmo e pode fazer melhor.

    
por 21.12.2016 / 17:20
fonte
3

Não há resposta correta para isso - cada variação tem seus próprios méritos e desvantagens ... Por exemplo, em alguns problemas que são strongmente restritos você não desejará mudar toda a população, já que nenhum dos novos pode ser alterado. em todos os encaixes, enquanto pequenas variações nos originais teriam sido. Em contraste, alguns problemas com um espaço de pesquisa muito grande podem se beneficiar de muitas alterações.

Em resumo, você precisaria pensar sobre o problema que você tem e experimentar para encontrar a estratégia ideal para cada problema específico. Uma boa maneira de pensar sobre isso é examinando a evolução real - se apenas os melhores fossem favorecidos a cada vez que a diversidade genética fosse reduzida e um problema específico pudesse causar a falência de toda a população. Com isso em mente, é 'geralmente' melhor ter uma boa quantidade de diversidade a cada geração, o que ajuda a evitar ficar preso em máximos / mínimos locais e ter uma melhor chance de encontrar soluções ótimas

    
por 21.12.2016 / 15:32
fonte