Representação de Genótipo

Uma das decisões mais importantes a serem tomadas ao implementar um algoritmo genético é decidir a representação que usaremos para representar nossas soluções. Foi observado que uma representação inadequada pode levar a um desempenho ruim da AG.

Portanto, escolher uma representação adequada, ter uma definição adequada dos mapeamentos entre os espaços fenótipo e genótipo é essencial para o sucesso de um AG.

Nesta seção, apresentamos algumas das representações mais usadas para algoritmos genéticos. No entanto, a representação é altamente específica do problema e o leitor pode achar que outra representação ou uma mistura das representações mencionadas aqui pode se adequar melhor ao seu problema.

Representação binária

Essa é uma das representações mais simples e mais usadas nos AGs. Nesse tipo de representação, o genótipo consiste em cadeias de bits.

Para alguns problemas quando o espaço da solução consiste em variáveis de decisão booleanas - sim ou não, a representação binária é natural. Tomemos, por exemplo, o problema da mochila 0/1. Se houver n itens, podemos representar uma solução por uma sequência binária de n elementos, em que o x é o elemento que indica se o item x é escolhido (1) ou não (0).

Representação binária

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 significado diferente e, portanto, operadores de mutação e crossover podem ter consequências indesejadas. Isso pode ser resolvido em certa medida usando o Gray Coding, pois uma alteração em um bit não afeta enormemente a solução.

Representação com Valor Real

Para problemas em que queremos definir os genes usando variáveis contínuas em vez de discretas, a representação com valor real é a mais natural. A precisão desses números com valores reais ou de ponto flutuante é, no entanto, limitada ao computador.

Representação com Valor Real

Representação Inteira

Para genes de valor discreto, nem sempre podemos limitar o espaço da solução ao binário 'yes' ou 'no'. Por exemplo, se queremos 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 Inteira

Representação de Permutação

Em muitos problemas, a solução é representada por uma ordem de elementos. Nesses casos, a representação de permutação é a mais adequada.

Um exemplo clássico dessa representação é o problema do vendedor ambulante (TSP). Nisso, o vendedor precisa fazer um tour por todas as cidades, visitando cada cidade exatamente uma vez e retornando à cidade inicial. 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, o uso de uma representação de permutação faz sentido para esse problema.

Representação de Permutação