Algoritmos genéticos são usados para fins de otimização. Um exemplo desse tipo de fim pode ser o aprendizado neuronet, ou seja, a seleção de valores de peso tais que permitam se chegar ao erro mínimo. Além disso, o algoritmo genético é baseado no método de busca aleatória. O principal problema de buscas aleatórias é o fato de que nós não podemos prever quanto tempo será necessário para a resolução do problema. Para evitar perdas de tempo significativas, são aplicados métodos desenvolvidos na biologia. Especificamente, métodos desenvolvidos nos estudos da origem das espécies e da evolução. Apenas os animais mais aptos sobrevivem durante o processo evolucionário. Como resultado disso, a aptidão de uma população cresce, o que lhe permite se ajustar ao ambiente dinâmico.

Um algoritmo do tipo foi proposto pela primeira vez por John H. Holland, da Universidade de Michigan, EUA, em 1975. Ele foi chamado de Plano reprodutivo de Holland, e é a base de quase todos os tipos de algoritmos genéticos. Contudo, antes de examinarmos este plano mais detalhadamente, vamos discutir a questão de como realidades podem ser codificadas para serem usadas em algoritmos genéticos.

Apresentação de objetos

A biologia nos ensina que qualquer organismo pode ser representado como seu fenótipo, que determina, de fato, o que este objeto é no mundo real, e como seu genótipo, que contém toda a informação sobre este objeto em seu conjunto de cromossomos. Além disso, todo gene, ou seja, todo elemento das informações do genótipo, reflete no fenótipo. Portanto, para resolver o nosso problema, nós temos que apresentar cada caractere do objeto de uma forma tal que possa ser utilizada em um algoritmo genético. Os mecanismos do algoritmo genético também funcionarão no nível do genótipo, sem precisarem de informações sobre o padrão interno do objeto, o que torna esses algoritmos amplamente utilizáveis em uma grande variedade de tarefas diferentes.

As sequências de bits são usadas para a apresentação do genótipo do objeto na variação mais comum do algoritmo genético. Além disso, um gene do genótipo do objeto corresponde a todos os atributos do objeto em seu fenótipo. O gene é uma sequência de bits de comprimento fixo que representa o valor desta característica.

Codificação de atributos de números inteiros

A forma mais simples de codificação desse tipo de atributo é a utilização de seu valor de bits. Então se torna bastante simples usar um gene de um certo comprimento suficiente para representar todos os valores possíveis de um atributo do tipo. Mas, infelizmente, essa forma de codificação possui desvantagens. A principal desvantagem é que os números vizinhos diferem uns dos outros por valores de vários bits. Portanto, 7 e 8, em sua representação de bits, diferem em 4 posições, o que torna o funcionamento do algoritmo genético difícil e aumenta o tempo necessário para a sua convergência. Para evitar isso, é melhor usar a codificação na qual os números vizinhos diferem um dos outros por um número menor de posições. Idealmente, pelo valor de um bit. Esse tipo de codificação é representado pelo código de Gray que é recomendado para a realização de um algoritmo genético. Os valores do código de Gray são fornecidos na tabela abaixo:

Codificação binária			Codificação de Gray
Código decimal	Código binário	Código hexadecimal	Código decimal	Código binário	Código hexadecimal
0	0000	0h	0	0000	0h
1	0001	1h	1	0001	1h
2	0010	2h	3	0011	3h
3	0011	3h	2	0010	2h
4	0100	4h	6	0110	6h
5	0101	5h	7	0111	7h
6	0110	6h	5	0101	5h
7	0111	7h	4	0100	4h
8	1000	8h	12	1100	Ch
9	1001	9h	13	1101	Dh
10	1010	Ah	15	1111	Fh
11	1011	Bh	14	1110	Eh
12	1100	Ch	10	1010	Ah
13	1101	Dh	11	1011	Bh
14	1110	Eh	9	1001	9h
15	1111	Fh	8	1000	8h

Tabela 1. Concordância de códigos binários e códigos de Gray

Portanto, ao codificar um atributo de número inteiro, nós o dividimos em tétrades e transformamos cada tétrade de acordo com as regras da codificação de Gray.

Em realizações práticas de algoritmos genéticos, geralmente não há necessidade de transformar os valores de atributo em valores de gene. Na prática, ocorre o problema inverso, quando é preciso encontrar o valor do atributo a partir do valor do gene correspondente.

Logo, a tarefa de decodificar os valores dos genes, que possuem atributos de número inteiro, é trivial.

Codificação de atributos de ponto flutuante

Neste caso, a forma mais simples de se codificar parece ser o uso da representação de bits. Contudo, essa forma possui as mesmas desvantagens que a de números inteiros. É por isso que, na prática, a seguinte sequência de operações será executada:

1. O intervalo inteiro de valores permitidos ao atributo é dividido em partes com a precisão desejada.
2. O valor do gene é considerado um número inteiro que numera o intervalo (através do uso do código de Gray).
3. O número que é o meio deste intervalo é considerado o valor do parâmetro.

Vamos examinar novamente a sequência de operações acima no seguinte exemplo:

Vamos assumir que os valores do atributo estão na faixa de [0,1]. A faixa foi dividida em 256 intervalos para a codificação. Para codificar o seu número, nós vamos precisar de 8 bits. O valor do gene é, por exemplo, 00100101bG (a letra maiúscula G significa que se trata do código de Gray). Primeiramente, usando o código de Grau, vamos encontrar o número do intervalo correspondente: 25hG->36h->54d. Agora vamos ver qual intervalo corresponde com ele. Através de cálculos simples, nós chegamos ao intervalo de [0,20703125, 0,2109375]. Ou seja, o valor do intervalo será (0,20703125+0,2109375)/2=0,208984375.

Codificação de dados não-numéricos

Os dados não-numéricos devem ser transformados em números antes de serem codificados. Este processo é descrito em maiores detalhes nos artigos contidos no nosso website, que descrevem o uso de redes neurais.

Como determinar o fenótipo do objeto a partir do seu genótipo

Para determinar o fenótipo do objeto (ou seja, os valores dos atributos do objeto), nós precisamos saber apenas os valores dos genes que correspondem a esses atributos (ou seja, o genótipo do objeto). Além disso, a integridade de genes que descrevem o genótipo do objeto representa um cromossomo. Em algumas realizações, ela também é chamada de espécime. Portanto, na realização do algoritmo genético, o cromossomo representa uma sequência de bits de comprimento fixo. Além disso, cada intervalo da sequência corresponde a um gene. O comprimento dos genes no interior de um cromossomo pode ser igual ou diferente. Os genes de comprimento igual são usados mais frequentemente. Vamos considerar um exemplo de um cromossomo e as interpretações do seu valor. Vamos supor que o objeto tenha 5 atributos, cada um codificado em um gene de 4 elementos de comprimento. Portanto o comprimento do cromossomo será de 5*4=20 bits:

0010

1010

1001

0100

1101

Agora nós podemos determinar os valores dos atributos.

Atributo			Valor do gene			Valor binário do atributo			Valor decimal do atributo
Atributo 1			0010			0011			3
Atributo 2			1010			1100			12
Atributo 3			1001			1110			14
Atributo 4			0100			0111			7
Atributo 5			1101			1001			9

Os operadores genéticos básicos

Como se sabe, a forma com que as características parentais são passadas à prole é muito importante para a teoria da evolução. Em algoritmos genéticos, o cruzamento é um operador genético usado para variar a programação de um cromossomo, ou vários cromossomos, de uma geração para a outra. Este operador trabalha da seguinte forma:

1. duas unidades são selecionadas em uma população para se tornarem pais;
2. o ponto de parada é determinado (aleatoriamente, por regra);
3. a prole é determinada como a concatenação das partes do primeiro e do segundo pai.

Vamos dar uma olhada no funcionamento deste operador:

Cromossomo_1:			0000000000
Cromossomo_2:			1111111111

Vamos assumir que o ponto de parada está após o terceiro bit do cromossomo, então:

Cromossomo_1:			0000000000			>>			000			1111111			Cromossomo_resultante_1
Cromossomo_2:			1111111111			>>			111			0000000			Cromossomo_resultante_2

Então um dos cromossomos resultantes é determinado com uma probabilidade de 0,5 como prole.

O outro operador genético serve para manter a diversidade em uma população: Ele é chamado de operador mutação. Este é o operador que altera um ou mais valores do gene em um cromossomo em relação ao seu estado inicial. Conformemente, todo bit em um cromossomo é invertido com uma certa probabilidade.

Além disso, mais um operador é usado, chamado inversão. Ele divide o cromossomo em duas partes, que então invertem posições. Isso pode ser representado esquematicamente da seguinte forma:

000

1111111

>>

1111111

000

Teoricamente, estes dois operadores genéticos são suficientes para criar a função do algoritmo genético. Contudo, na prática, são usados alguns operadores adicionais, assim como modificações desses dois operadores. Por exemplo, pode haver não apenas um cruzamento de ponto único (descrito acima), mas também um de pontos múltiplos. Neste último caso, vários pontos de parada (geralmente dois) são criados. Além disso, em algumas implementações do algoritmo, o operador mutação realiza a inversão de apenas um bit, escolhido aleatoriamente, de um cromossomo.

Fluxograma do algoritmo genético

Agora que sabemos como interpretar os valores do gene, nós podemos discutir como o algoritmo genético funciona. Vamos examinar mais detalhadamente o fluxograma do algoritmo genético em sua representação clássica.

1. Inicialize o tempo de início, t=0. Forme aleatoriamente a população inicial que consiste em k unidades. B0 = {A1,A2,…,Ak)
2. Calcule a aptidão de cada unidade, FAi = fit(Ai) , i=1…k, e a aptidão da população inteira, Ft = fit(Bt). O valor dessa função determina até que ponto a unidade descrita por este cromossomo é adequada para resolver o problema.
3. Selecione a unidade Ac da população. Ac = Get(Bt)
4. Selecione a segunda unidade da população com uma determinada probabilidade (a probabilidade Pc de cruzamento), Аc1 = Get(Bt), e execute o operador cruzamento, Ac = Cruzamento(Ac,Ac1).
5. Execute o operador mutação com uma determinada probabilidade (a probabilidade Pm de mutação), Ac = mutação(Ac).
6. Execute o operador inversão com uma determinada probabilidade (a probabilidade Pi de inversão), Ac = mutação(Ac).
7. Coloque o novo cromossomo obtido na nova população, insert(Bt+1,Ac).
8. Os passos 3 a 7 devem ser repetidos k vezes.
9. Aumente o número do período atual, t=t+1.
10. Caso a condição de parada seja alcançada, encerre o ciclo. Do contrário, vá ao passo 2.

Alguns estágios do algoritmo exigem consideração mais atenta.

Os passos 3 e 4, o estágio de seleção dos cromossomos pais, desempenham o papel mais importante no funcionamento bem sucedido do algoritmo. Podem haver várias alterativas possíveis a ele. O método de seleção usado com maior frequência é chamado roleta. Quando este método é usado, a probabilidade um determinado cromossomo ser selecionado é determinada pela sua aptidão, ou seja, PGet(Ai) ~ Fit(Ai)/Fit(Bt). O uso deste método resulta em um aumento da probabilidade de que atributos pertencentes a unidades mais bem ajustadas se propaguem pela prole. Outro método usado frequentemente é a seleção por torneio. Nele, várias unidades (2, por regra) são selecionadas aleatoriamente entre a população. A unidade mais apta será selecionada como vencedora. Além disso, em algumas implementações do algoritmo, é usada a chamada estratégia do elitismo, o que significa que as unidades mais bem ajustadas possuem a garantia de entrar na nova população. Essa abordagem geralmente permite a aceleração da convergência do algoritmo genético. A desvantagem dessa estratégia é a probabilidade aumentada do algoritmo chegar ao mínimo local.

A determinação dos critérios de parada do algoritmo é outro ponto importante. Usam-se como estes critérios ou a limitação dos períodos de funcionamento do algoritmo ou a determinação da convergência do algoritmo (normalmente através da comparação da aptidão da população em vários períodos para que se pare quando este parâmetro estabilize).