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

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

  

-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

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 , ...

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.