Como evitar ficar preso no local ideal, para algoritmos genéticos

7

Estou programando um algoritmo genético usando evolução gramatical. Meu problema é que alcanço valores ótimos locais (convergência prematura) e, quando isso acontece, não sei o que fazer. Estou pensando em aumentar a taxa de mutação (5% é o valor padrão), mas não sei como decidir quando é necessário.

Os dados que tenho em todas as gerações são uma matriz bidimensional cuja primeira coluna é sua adequação

adn[i][0] ← fitness 
row → is the values of the Grammar
column ↓ Each indiviual result

Se precisar de esclarecimentos, pergunte e terei o prazer de modificar. Note que esta não é a minha língua materna e lamento pelos erros e pelos inconvenientes.

Atendendo a uma solicitação, minhas operações são as seguintes e exatamente nesta ordem:

  • Gero uma população aleatória (uma matriz com números aleatórios)
  • Eu gero uma matriz que contém o resultado desejado. Para fazer isso, implementei algumas funções que possuem adicionalmente +5% de variação, por exemplo: fun (x) = (2 * cos (x) + sen (x) - 2X) * (0,95+ (um número oscilando entre 0 e 0,1) , x contém todos os f (x) com seqüencialmente de 0 a N (sendo N o tamanho da linha), y contém exatamente o mesmo (mais resultados)
  • Inicia o algoritmo (gerações que começam a mudar

As ações que fazem toda geração são:

  • Mutação: Um número aleatório de cada cromossomo pode sofrer mutação em qualquer gene → e [i] [aleatório] = número aleatório (com uma probabilidade de 5% disso acontecer)
  • Crossover: eu cruzo todos os ADNs com outros ADNs (80% é a chance de mutação para cada par). Para o emparelhamento, escolho um número aleatório e enfrento os adN [i] e adn [(i + j) mod NumADNs]
  • Traduzir. Eu recebo uma matriz que contém os valores que f (0 a N) fazem em uma etapa da transcrição e traduzo aplicando a gramática na imagem

    a gramática

-fit: Comparo os valores obtidos com os esperados e atualizo o fitness.

-Elitismo: Depois disso, eu escolho os 4 melhores e vou para o topo, eles serão selecionados

-Seleção: Qualquer usuário não elitista enfrentará um usuário totalmente aleatório, e se sua aptidão for menor (menor é melhor) prevalecerá, sendo uma possibilidade do pior sobrevivente

Kaostias
fonte
11
Seu título pergunta sobre como saber se você está no local ideal - não há mais alterações após algumas iterações, mas o corpo pergunta o que fazer - adicione alguma técnica ideal global. Eu entendi corretamente?
Mal
@EvilJS Sim, está correto, meu algoritmo continua funcionando, mas não há alterações relevantes.
Kaostias 23/03
Portanto, você monitora o número de iterações sem alterações e, quando esse valor é maior que o limite especificado, para a computação. No seu caso, em vez de para, você pode aumentar a taxa de mutação e tentar novamente. Se você tentar apenas a solução para aumentar a taxa de mutação - faça um número de iterações e defina-o como valor padrão.
Mal
Tenho a impressão de que você está confundindo a ordem das operações.
Auberon
Um genoma aleatória em cada lote
T123

Respostas:

9

Parece que você está lidando com convergência prematura .

Em outras palavras, sua população se enche de indivíduos que representam a solução abaixo do ideal e / ou indivíduos que estão (também) próximos da referida solução.

A estrutura básica de um algoritmo genético é a seguinte:

P <- Population of size N with N random individuals.
evaluate fitness of all individuals in P
while (stopping criteria not met) {
    C <- empty Child set of size M
    while (size of C is not M) {
        parent1 <- select an individual from P
        parent2 <- select an individual from P

        child1, child2 <- combine parent1 and parent2 somehow.
        child1, child2 <- mutate children by chance
        evaluate fitness of child1, child2
        C <- C + child1 + child2
    }
    P <- combine P and C. (P remains size N)
}
return individual with best fitness

Observe que (por exemplo) o tamanho da população / crianças não precisa ser constante por si só . Ou você pode combinar um número variável de pais em uma quantidade variável de filhos (por exemplo, um cruzamento entre 5 pais, resultando em 7 filhos). Mas eu manteria simples, a princípio.

Como você pode ver, os principais operadores de um algoritmo genético são, para

  • Seleção : selecione indivíduos da população que serão combinados. Exemplos: seleção de torneios , seleção proporcional , seleção de truncamento , ...
  • Crossover : Combine indivíduos selecionados (pais) com novos indivíduos (filhos). Exemplos: cruzamento de um ponto , cruzamento de n pontos , cruzamento uniforme , corte e emenda , ...
  • Mutação : Por acaso, (não) mude um indivíduo, alterando-o ligeiramente.
  • Recombinação : De alguma forma, insira as crianças no conjunto de pais. Exemplos: adicione todas as crianças à população, classifique a situação por condição física e remova as piores pessoas para que sua população volte a ter o tamanho N; Ordene sua população e largue os piores indivíduos M e adicione todas as crianças; freqüentemente são utilizadas as mesmas técnicas apresentadas na fase de seleção.

Na sua descrição, você está confundindo várias etapas como se fosse uma (por exemplo, você pula a etapa de seleção, mas a incoopera na etapa de crossover ). Você também descreve técnicas como se fosse uma etapa do algoritmo (por exemplo, o elitismo é uma técnica usada na etapa de recombinação para garantir que pelo menos os melhores indivíduos não morram).

Um exemplo em que a convergência prematura pode / ocorrerá quando você selecionar apenas os melhores indivíduos como pais e permitir apenas que os melhores indivíduos sobrevivam (na etapa de recombinação ).

Alguns métodos possíveis para resolver isso:

  • Aumente a taxa de mutação . No entanto, uma mutação é geralmente um processo muito aleatório. Você precisaria de sorte 'pura' para escapar da solução subótima.
  • Redesenhe suas operações genéticas . por exemplo, permita que indivíduos / filhos com problemas de condicionamento físico sobrevivam à geração com mais frequência. Pode ser que você esteja selecionando pessoas boas demais para sobreviver. Não deixe que muitas pessoas más sobrevivam, ou seu algoritmo nunca convergirá para algo bom.
  • (...)

O objetivo é ajustar suas operações genéticas de modo que, a cada próxima geração, a aptidão média da sua população (de preferência) tenha aumentado, mantendo uma variação de aptidão suficientemente grande. Isso não é fácil.

Existem vários outros métodos para evitar a convergência prematura, se o exposto acima não o ajudar. Eu recomendo fortemente experimentar alterar suas operações genéticas antes de fazer isso, no entanto. Termos de pesquisa: pré - seleção , aglomeração , compartilhamento de condicionamento físico , prevenção de incesto , ...

Auberon
fonte
Bem, o termo " ótimo local foi usado em artigos e livros, por exemplo, aqui há muito tempo O termo é um pouco sobrecarregado, mas ele é usado, e significativa..
Mal
Vou tentar as soluções fictícias que sobreviveram um pouco mais (eu a destruí imediatamente quando confrontadas com uma melhor no torneio aleatório). Qual seria uma boa taxa de aprovação para a má solução?
Kaostias 23/03
@ Kaostias Você pode editar sua resposta e descrever suas operações genéticas brevemente (seleção, recombinação, mutação, substituição, ...)? Dessa forma, podemos detectar uma possível causa de convergência prematura.
Auberon
@Auberon done, desculpe pelo inglês ruim, tenho uma grande falta de sinônimos.
Kaostias 24/03
@ Kaostias Alterei minha resposta para o que acho mais interessante para você.
Auberon
1

Se você aumentar a taxa de mutação, poderá saltar do ideal local, pesquise mais possibilidades, mas existe uma troca - com uma taxa de convergência mais alta, a taxa de convergência mudará e, com uma taxa muito alta, ela parará de convergir.
Quando os resultados param de mudar para várias iterações - é quando você para, então é também o momento de iniciar a nova pesquisa.
Eu proporia misturar o GA com o SA para encontrar o melhor global.
A solução hacky em funcionamento é lembrar as ótimas locais e reiniciar (alterar ou reinicializar), mas depois ela descartou a taxa de mutação atrator - queda.

Mal
fonte