Algoritmos evolutivos: Optimal Repovoamento Quebras

Question

É realmente tudo no título, mas aqui está uma repartição para qualquer um que esteja interessado em algoritmos evolutivos:

Em um EA, a premissa básica é que você gerar aleatoriamente um certo número de organismos (que são realmente apenas conjuntos de parâmetros), executá-los contra um problema, e em seguida, deixar os melhores desempenhos sobreviver.

Você, então repovoar com uma combinação de cruzamentos dos sobreviventes, mutações dos sobreviventes, e também um certo número de novos organismos aleatórios.

Do que surgem vários milhares de vezes, e organismos eficientes.

Algumas pessoas também fazer coisas como introduzir várias "ilhas" de organismos, que são populações separadas que estão autorizados a cruzar vez em quando.

Então, minha pergunta é: quais são as percentagens ideal repovoamento

I tem sido manter os melhores desempenhos de 10%, e repovoamento com 30% mestiços e 30% mutações. Os restantes 30% é de novos organismos.

Eu também tentei a teoria ilha múltipla, e estou interessado em seus resultados em que tão bem.

Não é perdido em mim que este é exatamente o tipo de problema uma EA poderia resolver. Você está ciente de qualquer um que tenta isso?

Agradecemos antecipadamente!

Answer 1

I inicialmente tentou modelar o que eu pensava sistemas orgânicos como eram. decidiu em última instância que não era bom, e foi mais agressivo, com 10% mantido, 20% mutado, 60% mestiços e 10% aleatória.

Em seguida, notei que a minha top 10% eram todos mais ou menos idênticos. Então eu aumentei o aleatório para 30%. Isso ajudou um pouco, mas não muito.

Eu tentei múltipla ilha, e os resultados, e reseeding-pular geração, que deu melhor, mas ainda altamente insatisfatória muito pouca variação, no top 10%, números loucos longo das gerações para obter qualquer resultado. Principalmente o código aprenderam a cortar o meu avaliação da aptidão.

É realmente fácil de obter melhor desempenho, por isso não se preocupar em manter muitos deles ao redor. Mestiços ajuda a aparar traços positivos e negativos, por isso eles são úteis, mas realmente o que você deseja obter uma grande quantidade de boa aleatório criado no. Concentre-se em mutações e novas randoms para trazer recursos, e deixar que os mestiços e artistas de topo apenas manter a par das melhores e refiná-los mais lentamente. IE: o material com base na última geração é apenas encontrar uma maxima melhor local, randoms encontrar maxima global melhor

.

Eu ainda acredito respostas ótimas para sua pergunta pode ser encontrada por observação de fenômenos naturais, como em um recente artigo sobre aleatoriedade das rotas de voo fruto-mosca, para que possa deslocar para fora.

Provavelmente a melhor resposta é apenas para executá-lo e ajustá-lo, não tenha medo de ajustá-lo muito fortemente, as populações são robustos. Certifique-se de implementar uma maneira de salvar e continuar.

Answer 2

Os melhores recursos que eu me deparei para GA e EA foram os livros de John Koza sobre Genetic Programming . Ele cobre o tema em profundidade -. Técnicas para a codificação do genoma, mutação aleatória, reprodução, ajuste a função de fitness

Pessoalmente eu só escrevi um pequeno punhado de simuladores para fins pedagógicos. O que descobri foi que como eu sintonizado essas porcentagens estava relacionada com as particularidades da função de fitness que eu estava usando, quanto aleatória mutação eu tinha introduzido e como 'inteligente' que eu tinha tentado fazer a mutação e reprodução - Achei que a menos 'inteligente' Eu tentei fazer o modificador e a lógica cross-over, o mais rápido da população melhorou sua pontuação fitness - Eu também achei que eu tinha sido muito conservador na probabilidade de mutação - minhas corridas iniciais atingiu máximos locais e tinha uma dificuldade em sair deles.

Nada disso lhe dá respostas concretas, mas eu não acho que há respostas concretas, GA é imprevisível, por sua natureza e ajustar esses tipos de parâmetros ainda pode ser um pouco de uma arte. Claro que você pode sempre tentar uma meta-GA, utilizando parâmetros como um cromossomo, em busca de configurações que produzem uma aptidão mais rápido na base GA você está executando.

depende de como 'meta' você deseja obter.

Answer 3

Esta é uma acaloradamente debatido (na literatura e Melanie, et al livros ) tópico que parece ser específico domínio de muito. O que funciona para um problema de um tipo com parâmetros n quase nunca trabalho para um outro problema, um outro domínio, ou outro conjunto paramétrica.

Assim, como TraumaPony sugeriu, ajustá-lo a si mesmo para cada problema que você está resolvendo ou escrever algo para otimizá-lo para você. A melhor coisa que você pode fazer é manter o controle de todo o seu "botão de twiddling" e experimentos de sintonia fina para que você pode mapear o terreno solução e ter uma idéia de como otimizar dentro desse espaço rapidamente. Tentar também técnicas alternativas como a colina de escalada que você possa ter uma linha de base de bater.

@Kyle Burton: taxas de mutação cruzamento vs. também são constantemente debatido em cada classe de problemas entregue ao gás e GPs.

Answer 4

Supondo que você tenha um método para quantificar os top X% por cento performers, eu sugiro que em vez de usar um limiar codificado duro você analisar a distribuição de desempenho e fazer o seu em algum lugar de corte na faixa da primeira grande queda no desempenho, e depois ajustar seus crossbreads, mutações e novos organismos para preencher as lacunas. Dessa forma, se você tem um muito run "produtiva", em que muitas variações foram bem sucedidos que você não jogue um número significativo de funcionários de alto desempenho. Além disso, se você tem um "improdutiva" correr você pode desfazer mais dos organismos existentes em favor de organismos mais novos que deve tomar o seu lugar.

Answer 5

Eu tive algum sucesso aumentando a diversidade da população através da criação de mutação e de cruzamento de um par de genes dos cromossomos pais.

Isso funciona até que a taxa de mutação cai para zero; uma vez que é provável que haverá uma pressão evolutiva periódica para fazer isso, você deve tentar e ter certeza de que esses genes têm uma taxa mínima.

Na prática, optei por um genótipo multi-cromossomo. Um cromossomo codificados para a função reprodutiva do outro. Quanto menor 'cromossomo reprodução' tinha taxas fixas sensatas para mutação e crossover.

Eu achei que isso iria parar o planalto clássico e convergência da população.

Como um aparte, que tendem a fazer as duas coisas cruzamento e mutação para cada criança.

Para o gás geracional, eu tento elitismo shun completamente, mas onde povoar a partir de múltiplas ilhas, eu manter os principais elite de cada ilha. Quando as ilhas se reúnem, em seguida, as elites podem produzir juntos.

Answer 6

Não parece ser algumas respostas sugerem usando um 2º GA para determinar os parâmetros ideais para o 1º GA, com nenhuma menção de como determinar os parâmetros ideais para o 2º. Eu não posso ajudar, mas pergunto sobre as crenças religiosas daqueles que sugerem essa abordagem ...

Answer 7

Como já foi mencionado, a mistura ideal seria depender do seu problema específico e outros fatores específicos de problemas, tais como o tamanho do espaço de solução.

Antes de discutir a repartição evolução de uma geração para a próxima, é importante considerar o tamanho de cada geração. Geralmente a minha abordagem é começar com uma população bastante grande (~ 100k-500k indivíduos) de bastante diversos indivíduos, que é algo que Koza sugere, em alguns de seus trabalhos. Para obter essa diversidade desde o início, você poderia dividir o seu espaço de soluções em baldes, e, em seguida, garantir que pelo menos um certo número de indivíduos cai em cada balde. (Por exemplo, se você tem uma representação em árvore para cada indivíduo, assegurar que as quantidades iguais são criados de profundidade 2, 3, ..., max_depth)

Quanto a sua pergunta real, não há nenhuma maneira clara de abordá-lo, mas dependendo do seu problema, você pode querer enfatizar aleatoriedade ou de enfatizar-lo. Quando você quer enfatizar isso, você deve manter menos indivuduals intacto, e introduzir um maior número de novos indivíduos aleatórios. Você, em geral, como fazer isso se há muitos máximos locais de seu espaço de soluções e você quer ter uma pesquisa mais ampla.

Quando você obter uma quebra há algumas coisas a considerar ... por exemplo, a duplicação (um monte de indivíduos idênticos ou recém-idênticos no topo endogamia). Para reduzir isso, você pode querer varrer através de sua população entre as gerações e substituir duplicações com novos indivíduos aleatórios ou os mestiços.

Dito isto, a minha abordagem atual é manter o top 1%, cruzar os 20% em um novo 20%, cruzar o top 40% para o próximo de 20%, cruzar o topo de 90% para gerar o próximo 20% , e gerar aleatoriamente o resto (39%). Se houver duplicatas, eu removê-los e substituí-los por novos indivíduos aleatórios.

Não uso mutações devido ao elevado número de indivíduos aleatórios deve tomar cuidado com a adição de "mutações" durante o próximo cruzamento.

Answer 8

Você sabe que você poderia fazer ... Você poderia escrever um algoritmo genético para determinar que a distribuição ideal.

Mas, geralmente eu manter o top 12% e 28% mestiços; com 30% para cada um dos outros.