Como encontrar os melhores parâmetros para um Algoritmo Genético?

Question

Algumas estruturas algoritmo genético, como http://www.aforgenet.com/ requer muitos parâmetros , tais como taxa de mutação, o tamanho da população, etc

Há melhores números universais para tais parâmetros? Eu acredito que isso depende do problema (atraso função de fitness, atraso mutação, atraso recombinação, a taxa de evolução, etc). Meu primeiro pensamento era usar um GA para configurar outro GA.

Qualquer idéias melhores?

Answer 1

A única vez que eu programado um algoritmo genético que incluiu os valores nos valores de mutação, basicamente, como você disse usando um GA para se configurar. Funcionou surpreendentemente bem, especialmente desde que eu achei que fosse benéfico para esses valores para mudar ao longo dela de computação.

Answer 2

Eu acho que ajuda a pensar nesses problemas como uma paisagem, onde você está tentando encontrar o ponto mais baixo.

Métodos como algoritmos genéticos são usados ??quando a paisagem é muito grande para apenas testar todos os pontos, e a "forma" da paisagem é tal que métodos como gradiente-descendente vai te preso em mínimos locais.

Um exemplo bom é função do Rastrigin ( imagem ref ):
_{(fonte: scientific-computing.com )}
:

As suas opções são:

tamanho Generation:

• Muito grande: você vai ter um tempo de época longa, restringindo quantas possibilidades para cada indivíduo tem explorá-lo do bairro.
• Muito pequeno: você não ficar bom cobertura do espaço de busca.

taxa de mutação:

• Muito alto: o risco dos indivíduos "Saltando" sobre uma solução que eles eram perto de.
• Muito baixo: eles estão todos indo para obter preso em mínimos locais.

Então, ele realmente não depende de seu próprio espaço de busca particular. Experimentar com os parâmetros e tentar encontrar a combinação ideal. Concordo que usando outro GA para otimizar os parâmetros não vai resolver o problema.

Answer 3

Acho que é bastante decepcionante há tantas respostas que assumem que você não pode encontrar os melhores parâmetros para o algoritmo genético automaticamente. Concordo que os parâmetros que dependem do problema, porém existem métodos onde você pode encontrá-los.

Além disso, o Não Free Teorema de modo algum o impede de encontrar os melhores parâmetros, como já houve discussão que as disputas do fato:

• Praticamente não se sustenta
• podem disputar o teorema
• Coevolution pode fazer o teorema irrelevante

Existem dois tipos de ajuste de parâmetros:

• Sintonia dos Parâmetros (search parâmetro off-line - antes da GA é run)
• Controle Parameter (parâmetro ajustes online - durante o GA run)
  • Adaptive
  • auto-adaptativo
  • determinística

Há uma grande quantidade de literatura lá fora, que descrevem como se pode encontrar esses parâmetros ideais, isso depende se você está querendo fazer o off line Pesquisar parâmetro ou online. crença popular é que fora de linha é mais adequado para a maioria dos casos, porque os métodos de controlo de parâmetros on-line gostaria de acrescentar muita complexidade ao longo offline.

Aqui estão alguns exemplos para encontrar as "melhores" parâmetros:

Sintonia dos Parâmetros :

• Simples parâmetro de varredura (tentar tudo)
• Meta-GA ontop de um GA
• Corrida estratégia para encontrar melhores parâmetros
• Meta-GA e Racing juntos

parâmetro de controle :

• Adaptive probabilidades de mutação e de cruzamento
• determinística operadores genéticos

E muito mais, basta procurar a literatura utilizando palavras-chave usadas acima. Existem métodos científicos para encontrar parâmetros adequados para qualquer problema!

Answer 4

Não é fácil.

Por quê? Devido à Almoço Não Free teorema. Isso, basicamente, afirma que não há nenhuma Geral algoritmo de busca que funciona bem para todas problemas.

O melhor que você pode fazer é adaptar a busca de um específica espaço do problema. Você vai ter que ajustar manualmente os parâmetros para ajustar a sua solução. Desculpe.

Usando um GA para encontrar parâmetros GA fica complicado. Como você encontrar os parâmetros ideais para a sua pesquisa GAGA? Outra GA ...?

Answer 5

Não há realmente uma maneira automática de fazer isso por um determinado conjunto de dados. Se houvesse, eles não iria expor esses parâmetros. Usando uma segunda GA para ajustar os parâmetros do primeiro GA é perigoso - você usar um terceiro GA para ajustar os parâmetros do segundo? Mesmo se você fez isso, é uma receita para overfitting de qualquer maneira.

Meu conselho seria para jogar com os parâmetros, e ver como eles afetam o seu distrubution população a cada geração, quantas gerações é preciso para chegar a uma resposta aceitável, etc. Se você tem muito mutação sua população nunca vai estabilizar . Muito pouco e você vai acabar com a homogeneidade.

É um segredo sujo de gás que afinação deles é uma arte, não uma ciência.

Answer 6

Como toda a gente disse, não há uma resposta. Embora haja alguma tendência a usar a taxa de cruzamento em nível de 0,7-0,9 e mutação em 0,1-0,3 ele realmente depende. Depende do problema, pode depender da função de fitness, e definitivamente depende Algoritmo Genético si. Há muitas variações GA, os parâmetros ideais para o mesmo problema pode variar.

Quanto ao uso GA aos parâmetros de ajuste de meta GA existem abordagens como essa, mas, como foi salientado, como parâmetros de som de primeira GA? Tenha em mente, que talvez mutação taxa deve ser maior no início, e que ele deve diminuir enquanto a taxa de mais de cruz deve ser cada vez maior. É questão da exploração contra a exploração. Existem abordagens para deixar GA ser mais adaptável e deixá-lo mudar seus parâmetros como parece para solução. controladores fuzzy são por vezes usadas para manipular parâmetros de GA. Há também outras abordagens.

Se você quiser saber mais sobre isso, comprar alguns livros, ou olhar através de trabalhos de pesquisa acadêmica.
Se você precisa configurar seu próprio GA sem uma extensa pesquisa, tente alguns valores de outros trabalhos e experiência com eles.