X. Codificação



Introdução

A codificação dos cromossomas é a primeira questão a ser feita quando começamos a resolver um problema utilizando AG. A codidicação depende muito do problema.

Neste capítulo, algumas codificações que já foram utilizadas com sucesso serão apresentadas.





Codificação Binária

Codificação Binária é a mais comum principalmente porque foi a que os primeiros pesquisadores de AG usaram e devido à sua relativa simplicidade.

Na Codificação Binária, cada cromossoma é uma série de bits - 0 or 1.

Cromossoma A 101100101100101011100101
Cromossoma B 111111100000110000011111

Exemplo de cromossomas com codificação binária

Codificação Binária permite muitos possíveis cromossomas, mesmo com pequenos número de alelos. Por outro lado, esta codificação não é natural para muitos problemas e algumas vezes é necessário fazer correções antes dos cruzamentos e/ou mutações.


Exemplo de Problema: Problema da Mochila
O problema: É dada uma lista de coisas com preços e tamanhos. É fornecido o valor da capacidade da mochila. Escolha as coisas de forma a maximizar o valor das coisas que cabem dentro da mochila, sem ultrapassar sua capacidade.
Codificação: Cada bit é usado para dizer se a coisa correspondente está ou não na mochila.





Codificação por Permutação

A Codificação por Permutação pode ser usada em problemas que envolvem ordenação como o "Problema do Caixeiro-Viajante" ou problemas de ordenação de tarefas.

Na Codificação por Permutação, cada cromossoma é uma série de números que representa uma posição em uma seqüência>.

Cromossoma A 1  5  3  2  6  4  7  9  8
Cromossoma B 8  5  6  7  2  3  1  4  9

Exemplo de cromossoma com codificação por permutação

A Codificação por Permutação é útil para solução de problemas de ordenação. Para alguns tipos de cruzamentos e mutações, são necessárias correções para que os cromossomas fiquem consistentes (isto é contenham seqüências reais) para alguns problemas.


Exemplo de Problema: Problema do Caixeiro Viajante (Travelling Salesman Problem - TSP)
O problema: São dadas cidades e as distâncias entre elas. O caixeiro viajante tem que visitar todas elas, sem viajar mais do que o necessário. A solução do problema consiste em encontrar a seqüência de cidades em que as viagens devem ser feitas de forma que a distância percorrida seja a mínima possível.
Codificação: Os cromossomas descrevem a ordem em que o caixeiro visitará as cidades.




Codificação de Valores

A codificação direta dos valores pode ser usada em problemas em que são usados valores mais complicados tais como números reais. Usar codificação binária para esse tipo de problema seria muito difícil.

Na Codificação de Valores, cada cromossoma é uma seqüência de alguns valores. Esses valores podem ser qualquer coisa relacionada com o problema, tais como: números reais, caracteres ou qualquer outro objeto.

Cromossoma A 1.2324  5.3243  0.4556  2.3293  2.4545
Cromossoma B ABDJEIFJDHDIERJFDLDFLFEGT
Cromossoma C (atrás), (atrás), (direita), (frente), (esquerda)

Exemplo de cromossoma com codificação de valores

Codificação de Valores é uma boa escolha para alguns problemas especiais. Entretanto, para essa codificação, é frequentemente necessário desenvolver um método de cruzamento e mutação específico para o problema.


Exemplo de Problema: Cálculo de Pesos para uma Rede Neural
O problema: É dada uma rede neural com arquitetura definida. Encontre os pesos entre os neurônios da rede de forma a obter a resposta desejada da rede.
Codificação: Valores reais dos cromossomas representam os pesos da rede neural.




Codificação em Árvore

Codificação em Árvore é usada principalmente para desenvolver programas ou expressões, isto é, para programação genética. Na Codificação em Árvore cada cromossoma é uma árvore de alguns objetos, tais como funções ou comandos de uma linguagem de programação.

Cromossoma A

Cromossoma B

( +  x  ( /  5  y ) )

( do_until  step  wall )

Exemplo de cromossoma com codificação em árvore

A Codificação em Árvore é útil para desenvolver programas ou qualquer outra estrutura que pode ser codificada em árvores. A programação na linguagem LISP é frequentemente utilizada para este propósito uma vez que os programas em LISP são diretamente representados na forma de árvores e podem ser facilmente processados como uma árvore, de forma que o cruzamento e a mutação podem ser realizados com relativa facilidade.


Exemplo de Problema: Encontrar uma função que aproxime um dado par de valores
O problema: São dados os valores de entrada e de saída. A tarefa é encontrar uma função que forneça a melhor saída (isto é, a que dê o resultado mais próximo do desejado) para todas as entradas.
Codificação: Cromossomas são funções representadas em uma árvore.



prev             next


(c) Marek Obitko, 1998
Versão em Português do Brasil (c) Hermelindo Pinheiro Manoel
- Terms of use