Pelo que li, algoritmos genéticos são geralmente (sempre?) Aplicados a cromossomos de bits. Portanto, se um problema envolve maximizar uma função que aceita valores inteiros, os inteiros são primeiro codificados como bits.
Esse mapeamento é necessário? Parece que você pode pegar cromossomos de números inteiros e aplicar crossover e mutação diretamente. Portanto, se eu tenho uma função que aceita 35 entradas inteiras, posso aplicar os operadores genéticos a esses números inteiros, e não nos bits 35xB (onde B é o número de bits necessários para codificar um número inteiro). Existe uma razão para isso não ser feito?
Talvez o algoritmo sofra porque o problema é definido de forma mais grosseira (ou seja, um problema pode ser definido com cromossomos mais curtos se não estivermos usando bits), mas estou curioso para saber se alguém tem uma resposta melhor.
fonte
Respostas:
Codificar os valores como bits não é necessário. Veja o vagão 2d (não perca muito tempo) para ver um exemplo em que o cruzamento é feito com valores inteiros (flutuantes). 'Assembléias' inteiras são cruzadas, isso aumenta o reconhecimento da fonte (parte da estética do jogo), mas faz com que as variações entre um determinado cromossomo e seus pais sejam mais limitadas.
O motivo para considerar o uso de bits em vez de números inteiros tem a ver com o intervalo de dados com o qual o pool é propagado. Ter 35 números inteiros significa que o cruzamento só pode ocorrer em 35 valores que são tomados como valores inteiros. ter 1120 bits (números inteiros de 35 * 32 bits) fornece uma granularidade mais fina (considere o trabalho tradicional dos 'algoritmos genéticos' no ATCG - não os 'valores' inteiros 'de aminoácidos ou proteínas).
Ter bits permite que você tenha mutações 'mais limpas' (vire um pouco) e crossover que ocupa a parte superior de um número inteiro e a parte inferior de outro. Ambas as coisas ajudam a aumentar a variedade potencial de filhos.
Considere o cromossomo de apenas dois bytes (estamos executando bytes em vez de números inteiros para facilitar a visualização):
O cruzamento entre esses dois cromossomos pode acontecer apenas em locais limitados. Você terminará com:
Se isso foi feito como bits:
Agora você pode selecionar os
^sites para dar crossover:Isso fornece um modelo mais rico com mais variações possíveis entre dois cromossomos.
fonte
Contanto que você tenha um crossover e uma mutação, estará no negócio. O tipo subjacente não importa. Eu já vi AGs em estruturas gráficas em que o crossover e o mutate operam diretamente nos gráficos, adicionando ou combinando nós.
Na verdade, eu normalmente codifico tudo para caracteres e, em seguida, forneço crossover e mutações no nível de bytes, em vez de bits. Não é difícil adicionar uma máscara de bits para levá-la ao nível de bits, mas a vida é muito curta.
fonte
No GA, todos os cromossomos são geralmente representados como cadeias de bits. Você pode ter exceções, mas vamos esquecê-las por enquanto.
Um cromossomo é uma solução possível para o seu problema; portanto, se sua solução for um número inteiro, ela deverá ter uma representação binária para ser trabalhada pelas operações genéticas. Felizmente, números inteiros já possuem essa representação binária (na verdade, eles são * cadeias de bits nativas); portanto, você não precisa fazer nada, basta aplicar os operadores sobre os indivíduos da sua população ao longo do processo de evolução.
fonte
O mapeamento não é necessário.
A evolução diferencial (DE) é um "subconjunto" muito bem-sucedido do espaço mais amplo dos algoritmos genéticos.
A primeira grande mudança é que DE está usando números reais / inteiros reais em vez de cadeias de bits (geralmente números reais para otimização numérica, números inteiros em outros campos).
De qualquer forma, é bom poder representar as coisas como números reais.
É uma maneira de usar os recursos do computador com eficiência e também torna a entrada e a saída transparentes para o usuário: os parâmetros podem ser inseridos, manipulados e gerados como números comuns, sem nunca serem reformatados como genes com uma representação binária diferente.
Para o problema de ser "definido de forma mais grosseira" , o DE adota operadores de mutação / crossover modificados que fazem uso da diferença entre dois ou mais vetores inteiros / reais na população para criar um novo vetor (por exemplo, adicionando uma proporção aleatória da diferença para um dos vetores existentes, além de uma pequena quantidade de ruído aleatório).
Da evolução diferencial - uma abordagem prática à otimização global
fonte