V. Operadores dos Algoritmos Genéticos


Visão Geral

Como vimos em Esboço Básico de Algoritmos Genéticos, o cruzamento e a mutação são as partes mais importantes do algoritmo genético. O desempenho é influenciado principalmente por esses dois operadores. Antes de detalharmos mais cruzamento e mutação, vejamos mais alguma informação sobre cromossomas.




A Codificação de um Cromossoma

Um cromossoma deve de alguma maneira conter a informação da solução que ele representa. A forma mais comum de codificar é uma série (string) binária. Um cromossoma pode então se parecer como isto:

Cromossoma 1 1101100100110110
Cromossoma 2 1101111000011110

Cada cromossoma é representado por uma série binária. Cada bit da série representa alguma característica da solução. Outra possibilidade é que a série toda possa representar um número - isso foi feito basicamente no applet AG.

É claro, há muitas outras formas de codificar. A codificação dependerá principalmente do problema a ser solucionado. Por exemplo, um pode codificar diretamente números inteiros ou reais, algumas vezes é útil codificar algumas permutações, e assim por diante.




Cruzamento

Depois de decidirmos que codificação usaremos, podemos proceder a operação de cruzamento. O cruzamento opera em determinados genes dos cromossomas dos pais e cria novas descendências. A maneira mais simples de fazer isso é escolher aleatóriamente alguns pontos de cruzamento e copiar tudo o que vem antes desse ponto de um dos pais e então copiar tudo o que vem depois desse ponto do outro pai.

O Cruzamento pode ser ilustrado da seguinte maneira: ( | é o ponto de cruzamento):

Cromossoma 1 11011 | 00100110110
Cromossoma 2 11011 | 11000011110
Descendência 1 11011 | 11000011110
Descendência 2 11011 | 00100110110

Há outras maneiras de fazer cruzamento. Por exemplo, nós podemos escolher mais pontos de cruzamento. O cruzamento pode ser um pouco complicado e depender principalmente da codificação dos cromossomas. Cruzamentos especificos feitos para problemas específicos podem melhorar o desempenho dos algoritmos genéticos.




Mutação

Depois que um cruzamento é realizado, acontece a mutação. A mutação tem a intenção de prevenir que todas as soluções do problema dessa população caiam em um ponto ótimo local. A operação de mutação muda aleatóriamente a descendência criada pelo cruzamento. No caso de uma codificação binária, podemos mudar aleatóriamente alguns bits escolhidos de 1 para 0, ou de 0 para 1. A mutação pode então ser ilustrada como a seguir:

Descendência Original 1 1101111000011110
Descendência Original 2 1101100100110110
Descendência Mutada 1 1100111000011110
Descendência Mutada 2 1101101100110110

A técnica da mutação (da mesma forma que a do cruzamento) depende muito da codificação dos cromossomas. Por exemplo, quando codificamos permutações, mutações podem ser realizadas como uma troca de dois genes.



prev             next


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