Como se pode supor, os algoritmos genéticos foram criados tendo como referência a teoria de Darwin sobre a evolução dos seres vivos. Dessa forma, pode-se dizer que soluções obtidas através de algoritmos genéticos são ditas evolutivas.
Um algoritmo genético é um processo repetitivo que mantém uma população de “indivíduos”, que representam as possíveis soluções para um determinado problema. A cada “geração” os indivíduos da população passam por uma avaliação de sua capacidade em oferecer uma solução satisfatória para o problema. Essa avaliação é feita por uma função de adaptação ou função de fitness. De acordo com esta avaliação alguns indivíduos, selecionados
de acordo com uma regra probabilística, passam por um processo de reprodução, gerando uma nova população de possíveis soluções. Pressupõe-se que a população vá gradativamente ficando mais apta para solucionar o problema. A estrutura funcional de um algoritmo genético está representada na Figura 25.
Figura 25 Seqüência de execução de um algoritmo genético
Embora um algoritmo genético nem sempre possa encontrar uma solução ótima para um determinado problema, na maioria das vezes é capaz de encontrar soluções aceitáveis para problemas relativamente complexos.
A partir dos anos 80 os algoritmos genéticos receberam um grande impulso em diversas áreas científicas devido principalmente à versatilidade e aos excelentes resultados apresentados. A popularização dos computadores e o aparecimento de sistemas cada vez mais rápidos e potentes também ajudaram muito o seu desenvolvimento.
O ponto de partida para a utilização de um algoritmo genético na solução de um problema consiste em definir uma representação adequada dos indivíduos (soluções) envolvidos no problema de maneira que o algoritmo possa operá-los. No algoritmo proposto por Holland (1998), cada cromossomo é representado por uma cadeia binária de tamanho fixo, onde cada gene pode assumir o valor um ou o valor zero. Por exemplo:
Cromossomo 1 01001
Cromossomo 2 01110
Cromossomo 3 10000
Cromossomo 4 10110
Apesar da representação binária ser a mais utilizada, dependendo do tipo de aplicação podem existir formas mais eficientes de representar os cromossomos, como a utilização de símbolos ou números reais (Mitchell, 2002, p.156-158).
Feita a escolha de como os indivíduos serão representados, o próximo passo é definir quantos e quais indivíduos farão parte da população inicial. A população inicial pode ser obtida através da geração aleatória de indivíduos, obedecendo a certas condições estabelecidas pelo usuário, ou cada indivíduo pode ser criado individualmente com objetivo de gerar uma população dentro de certo intervalo onde se acredita estar a resposta para o problema.
O tamanho da população (número de indivíduos) pode afetar o desempenho global e a eficiência dos algoritmos genéticos. Populações muito pequenas têm grandes chances de perder a diversidade necessária para convergir para uma boa solução do problema que se deseja resolver. Por outro lado, se a população tiver muitos indivíduos o algoritmo poderá perder grande parte de sua eficiência pela demora no cálculo da função de adaptação de todos os indivíduos a cada iteração.
Para a população inicial e a cada nova geração será necessário calcular o grau de adaptação de cada indivíduo. Esse cálculo é feito através de uma função de adaptação que deve ser definida tendo em vista o tipo de problema a ser resolvido. A função de adaptação (também chamada de função de fitness) deve refletir a qualidade de cada indivíduo em solucionar o problema. Uma função de fitness bastante utilizada é o Coeficiente de Similaridade de Jaccard (van Rijsbergen, 1979). Esta função calcula o valor da similaridade entre duas seqüências binárias e é definida como o número de posições com valor 1 em ambas as seqüências, dividido pelo número de posições com valor 1 em pelo menos uma das seqüências. seqüências das uma menos pelo em 1 com posições de Quantidade seqüências as ambas em 1 com posições de Quantidade
De acordo com a teoria de Darwin, os indivíduos mais adaptados (com maior fitness) ao meio ambiente têm maior chance de se reproduzirem. Para simular a casualidade da seleção natural, um algoritmo genético pode utilizar alguns métodos para selecionar aleatoriamente os indivíduos que deverão se reproduzir. Um dos métodos mais utilizados é chamado de Roleta (Roulette Wheel).
No método da Roleta, para cada indivíduo da população é atribuída uma probabilidade de reprodução proporcional ao seu fitness. Assim, quanto maior o fitness de um indivíduo, maior a possibilidade dele se reproduzir. Por exemplo:
Nº Cromossomo fitness percentual
1 01001 0.05 10%
2 01110 0.10 20%
3 10000 0.12 24%
4 10110 0.23 46%
total 0.50 100%
No exemplo acima, o cromossomo número 4 (10110) é o mais adaptado e sua chance de ser selecionado para reprodução é de 46%. O cromossomo 01001 é o menos adaptado e sua chance de ser selecionado é de apenas 10%.
O processo computacional da seleção assemelha-se a um sorteio feito através de uma roleta onde estão representados todos os indivíduos da população. O tamanho de cada “fatia” da roleta é proporcional ao grau de adaptação (fitness) de cada indivíduo.
A roleta é “girada” 4 vezes, sorteando quatro indivíduos que se reproduzirão. Supondo que os indivíduos selecionados foram: 01110 (2), 10110 (4), 10110 (4) e 10000 (3), observa-se que o cromossomo 4 foi selecionado duas vezes, o que é coerente já que o valor de seu fitness é bastante superior aos demais. O cromossomo 1 não foi selecionado pois possui baixo valor de fitness.
Com a utilização da roleta, existe a probabilidade de o indivíduo com o maior fitness não se reproduzir. Uma estratégia alternativa à roleta é simplesmente manter sempre o indivíduo com maior fitness da geração atual na geração seguinte, estratégia conhecida como seleção elitista. Outros métodos de seleção são apresentados por Mitchell (2002, p. 166-171).
Definido o grupo de indivíduos reprodutores, o próximo passo é realizar a reprodução propriamente dita, ou seja, o crossover. Em termos biológicos, crossover significa efetuar uma recombinação do material genético dos “pais”, gerando novos indivíduos “filhos”. Do grupo de cromossomos reprodutores, dois pares são selecionados aleatoriamente. Para cada par é escolhido (também aleatoriamente) um ponto de divisão. Supondo-se que para o par de cromossomos 01110 e 10110 foi escolhido para realizar crossover a partir do ponto de divisão 1 e para o par 10110 e 10000 o ponto de crossover será o ponto 3.
Pais Filhos 0 1 1 1 0 0 0 1 1 0
1 0 1 1 0 1 1 1 1 0
1 0 1 1 0 1 0 1 0 0
1 0 0 0 0 1 0 0 1 0
Os cromossomos resultantes da reprodução do primeiro par são 00111 e 11110. A reprodução do segundo par resultou nos cromossomos 10100 e 10010.
Nesse exemplo foi utilizado o chamado crossover simples, com apenas um único ponto de divisão. Dependendo do tipo de problema é possível utilizar dois ou mais pontos de divisão.
Durante o processo de reprodução, há uma probabilidade de mutação, que determina a freqüência de ocorrência da mutação. Para cada gene dentro de um cromossomo é decidido se uma mutação deverá ou não ocorrer. Se a mutação for realizada, o valor do gene que está sendo verificado será alterado. Em cadeias binárias, um gene com valor 1 terá seu valor alterado para 0, um gene com valor 0 será alterado para 1. Por exemplo, o algoritmo decide alterar o valor do bit (gene) da posição 4 do cromossomo 11110:
1 1 1 1 0 mutação 1 1 1 0 0
Após a mutação obtém-se um novo conjunto de indivíduos (cromossomos), uma nova população. O cálculo do grau de adaptação de cada indivíduo é calculado e o processo se repete.
Grande parte da capacidade dos algoritmos genéticos provém do fato de existir um conjunto de cromossomos muito diverso. As mutações ajudam a prevenir a estagnação das populações, ajudando a preservar esta diversidade através das gerações.