Representação de Genótipo
Uma das decisões mais importantes a se tomar ao implementar um algoritmo genético é decidir a representação que usaremos para representar nossas soluções. Observou-se que a representação inadequada pode levar ao mau desempenho do AG.
Portanto, a escolha de uma representação adequada, tendo uma definição adequada dos mapeamentos entre o fenótipo e os espaços genotípicos é essencial para o sucesso de um AG.
Nesta seção, apresentamos algumas das representações mais comumente usadas para algoritmos genéticos. No entanto, a representação é altamente específica para o problema e o leitor pode descobrir que outra representação ou uma mistura das representações mencionadas aqui pode se adequar melhor ao seu problema.
Representação Binária
Esta é uma das representações mais simples e amplamente utilizadas em AGs. Nesse tipo de representação, o genótipo consiste em cadeias de bits.
Para alguns problemas quando o espaço de solução consiste em variáveis de decisão booleanas - sim ou não, a representação binária é natural. Veja, por exemplo, o problema da mochila 0/1. Se houver n itens, podemos representar uma solução por uma string binária de n elementos, onde o x- ésimo elemento diz se o item x é escolhido (1) ou não (0).
Para outros problemas, especificamente aqueles que lidam com números, podemos representar os números com sua representação binária. O problema com esse tipo de codificação é que bits diferentes têm significados diferentes e, portanto, os operadores de mutação e de cruzamento podem ter consequências indesejadas. Isso pode ser resolvido até certo ponto usandoGray Coding, já que uma mudança em um bit não tem um efeito massivo na solução.
Representação de valor real
Para problemas em que queremos definir os genes usando variáveis contínuas em vez de variáveis discretas, a representação com valor real é a mais natural. A precisão desses números reais de valor ou de ponto flutuante é, entretanto, limitada ao computador.
Representação Inteira
Para genes de valor discreto, nem sempre podemos limitar o espaço de solução para 'sim' ou 'não' binário. Por exemplo, se quisermos codificar as quatro distâncias - Norte, Sul, Leste e Oeste, podemos codificá-las como{0,1,2,3}. Nesses casos, a representação inteira é desejável.
Representação de Permutação
Em muitos problemas, a solução é representada por uma ordem de elementos. Em tais casos, a representação de permutação é a mais adequada.
Um exemplo clássico dessa representação é o problema do caixeiro viajante (TSP). Nela, o vendedor deve fazer um tour por todas as cidades, visitando cada cidade exatamente uma vez e voltar à cidade de origem. A distância total do passeio deve ser minimizada. A solução para este TSP é naturalmente uma ordenação ou permutação de todas as cidades e, portanto, usar uma representação de permutação faz sentido para este problema.
