Uma das vantagens de um algoritmo genético é a simplificação que eles permitem na formulação e solução de problemas de otimização. AG's simples normalmente trabalham com descrições de entrada formadas por cadeias de bits de tamanho fixo. Outros tipos de AG's podem trabalhar com cadeias de bits de tamanho variável., como por exemplo AG's usados para Programação Genética. AG's possuem um paralelismo implícito decorrente da avaliação independente de cada uma dessas cadeias de bits, ou seja, pode-se avaliar a viabilidade de um conjunto de parâmetros para a solução do problema de otimização em questão. O AG é indicado para a solução de problemas de otimização complexos, NP-Completos, como o "caixeiro viajante", que envolvem um grande número de variáveis e, consequentemente, espaços de soluções de dimensões elevadas. Além disso, em muitos casos onde outras estratégias de otimização falham na busca de uma solução, os AG's convergem. Os AG's são numericamente robustos, ou seja, não são sensíveis a erros de arredondamento no que se refere aos seus resultados finais.
Existem três tipos de representação possíveis para os cromossomos: binária, inteira ou real. A essa representação se dá onome de alfabeto do AG. De acordo com a classe de problema que se deseje resolver pode-se usar qualquer um dos três tipos.
Uma implementação de um algoritmo genético começa com uma população aleatória de cromossomos. Essas estruturas são, então, avaliadas e associadas a uma probabilidade de reprodução de tal forma que as maiores probabilidades são associadas aos cromossomos que representam uma melhor solução para o problema de otimização do que àqueles que representam uma solução pior. A aptidão da solução é tipicamente definida com relação à população corrente.
A função objetivo de um problema de otimização é construída a partir dos
parâmetros envolvidos no problema. Ela fornece uma medida da proximidade da
solução em relação a um conjunto de parâmteros. Os parâmetros podem ser
conflitantes, ou seja, quando um aumenta o outro diminui. O objetivo é
encontrar o ponto ótimo. A função objetivo permite o cálculo da aptidão
bruta de cada indivíduo, que fornecerá o valor a ser usado para o
cálculo de sua probabilidade de ser selecionado para reprodução.
cromossomo (genótipo) - cadeia de bits que representa uma solução possível para o problema.
gene - representação de cada parâmetro de acordo com o alfabeto utilizado (binário, inteiro ou real).
fenótipo - cromossomo codificado
população - conjunto de pontos (indivíduos) no Espaço de Busca
geração - iteração completa do AG que gera uma nova população
aptidão bruta - saída gerada pela função objetivo para um indivíduo da população
aptidão normalizada - aptidão bruta normalizada, entrada para o algoritmo de seleção.
aptidão máxima - melhor indivíduo da população corrente
aptidão média - aptidão média da população corrente
Deve ser observado que cada cromossomo, chamado de indivíduo no AG,
corresponde a um ponto no espaço de soluções do problema de otimização. O
processo de solução adotado nos algoritmos genéticos consiste em gerar,
através de regras específicas, um grande número de indivíduos,
população, de forma a promover uma varredura tão extensa quanto
necessária do espaço de soluções.
Operações Básicas de um AG
simples
A estrutura básica do algoritmo genético
é mostrada na figura abaixo:
FIGURA 1: ESTRUTURA BÁSICA DE UM
AG SIMPLES
Com referência ao diagrama da
figura figura 1, observa-se que cada iteração do algoritmo genético
corresponde à aplicação de um conjunto de quatro operações básicas: cálculo de
aptidão, seleção, cruzamento e mutação. Ao fim destas operações cria-se uma
nova população, chamada de geração que, espera-se, representa uma melhor
aproximação da solução do problema de otimização que a população anterior. A
população inicial é gerada atribuindo-se aleatoriamente valores aos genes de
cada cromossomo. A aptidão bruta de um indivíduo da população é medida por uma
função de erro, também chamada de função objetivo do
problema de
otimização. A aptidão bruta é em seguida normalizada (aptidão normalizada),
para permitir um melhor controle do processo de seleção. Como critérios de
parada do algoritmo em geral são usados a aptidão do melhor indivíduo em
conjunto com a limitação do número de gerações. Outros critérios podem
envolver, por exemplo, um erro abaixo de um valor especificado pelo projetista
para um determinado parâmetro do problema.
INICIALIZAÇÃO
Uma população de n individuos é gerada
aleatoriamente. Cada um dos indivíduos da população representa uma possível
solução para o problema, ou seja, um ponto no espaço de soluções.
CÁLCULO DA APTIDÃO
Geralmente a aptidão do indivíduo é
determinada através do cálculo da função objetivo, que depende das
especificações de projeto. Neste trabalho, cada indivíduo é uma entrada para
uma ferramenta de análise de desempenho, cuja saída fornece medidas que
permitem ao algoritmo genético o cálculo da aptidão do indivíduo. Ainda nesta
fase os indivíduos são ordenados conforme a sua aptidão.
SELEÇÃO
Nesta fase os indivíduos mais aptos da geração atual
são selecionados. Esses indivíduos são utilizados para gerar uma nova
população por cruzamento.Cada indivíduo tem uma probabilidade de ser
selecionado proporcional à sua aptidão. Para visualizar este método considere
um círculo dividido em n regiões (tamanho da população), onde a área de
cada região é proporcional à aptidão do indivíduo (figura 2). Coloca-se sobre
este círculo uma "roleta" com n cursores, igualmente espaçados. Após um giro
da roleta a posição dos cursores indica os indivíduos selecionados. Este
método é denominado amostragem universal estocástica. Evidentemente, os
indivíduos cujas regiões possuem maior área terão maior probabilidade de serem
selecionados várias vezes. Como consequência, a seleção de indivíduos pode
conter várias cópias de um mesmo indivíduo enquanto outros podem desaparecer.
FIGURA 2 : AMOSTRAGEM ESTOCÁSTICA UNIVERSAL
CRUZAMENTO ("CROSS-OVER")
Os indivíduos selecionados na
etapa anterior são cruzados da seguinte forma: a lista de indivíduos
selecionados é embaralhada aleatoriamente criando-se, desta forma, uma segunda
lista, chamada lista de parceiros. Cada indivíduo selecionado é então cruzado
com o indivíduo que ocupa a mesma posição na lista de parceiros. A forma como
se realiza este cruzamento é ilustrada na figura figura 3. Os cromossomos de
cada par de indivíduos a serem cruzados são particionados em um ponto, chamado
ponto de corte, sorteado aleatoriamente. Um novo cromossomo é gerado
permutando-se a metade inicial de um cromossomo coma metade final do outro.
Deve-se notar que se o cromossomo for representado por uma cadeia de bits,
como na figura figura 3, o ponto de corte pode incidir em
qualquer posição
(bit) no interior de um gene, não importando os limites do gene. No caso de
genes representados por números reais, a menor unidade do cromossomo que pode
ser permutada é o gene.
FIGURA 3 : CRUZAMENTO DE DOIS INDIVÍDUOS NUM AG SIMPLES
MUTAÇÃO
A operação de mutação é utilizada para garantir uma
maior varredura do espaço de estados e evitar que o algoritmo genético
convirja muito cedo para mínimos locais. A mutação é efetuada alterando-se o
valor de um gene de um indivíduo sorteado aleatoriamente com uma determinada
probabilidade, denominada probabilidade de mutação, ou seja, vários indivíduos
da nova população podem ter um de seus genes alterado aleatoriamente.
Escolha dos parâmetros do AG
Além da forma como o cromossomo é codificado, existem vários
parâmetros do algoritmo genético que podem ser escolhidos para melhorar o seu
desempenho, adaptando-o às características particulares de determinadas
classes de problemas. Entre eles os mais importantes são: o tamanho da
população, o número de gerações, a probabilidade de cross-over e a
probabilidade de mutação. A influência de cada parâmetro no desempenho do
algoritmo depende da classe de problemas que se está tratando. Assim, a
determinação de um conjunto de valores otimizado para estes parâmetros
dependerá da realização de um grande número de experimentos e testes. Na
maioria da literatura os valores encontrados estão na faixa de 60 a 65% para a
probabilidade de cross-over e entre 0,1 e 5% para a
probabilidade de
mutação. O tamanho da população e o número de gerações dependem da
complexidade do problema de otimização e devem ser determinados
experimentalmente. No entanto, deve ser observado que o tamanho da população e
o número de gerações definem diretamente o tamanho do espaço de busca a ser
coberto. Existem estudos que utilizam um AG como método de otimização para a
escolha dos parâmetros de outro AG, devido à importância da escolha correta
destes parâmetros.
Os AG's possuem uma larga aplicação em muitas áreas científicas, entre as quais podem ser destacadas:
-- Síntese de circuitos analógicos: para uma certa entrada e uma saída desejada, por exemplo tensão, o AG gera a topologia , o tipo e o valor dos componentes do circuito.
-- Síntese de protocolos: determinação de quais funções do protocolo devem ser implementadas em hardware e quais devem ser implementadas em software para que um certo desempenho seja alcançado.
-- Programação Genética: gera a listagem de um programa, numa determinada linguagem especificada, para que um determinado conjunto de dados de entrada forneça uma saída desejada.
-- Gerenciamento de redes: supervisão do tráfego nos links e das filas nos "buffers" de roteadores para descobrir rotas ótimas e para reconfigurar as rotas existentes no caso de falha de algum link
-- Computação Evolutiva: gera programas que se adaptam a mudanças no sistema ao longo do tempo.
-- Otimização evolutiva multi-critério: otimização de funções com múltiplos objetivos que sejam conflitantes.
-- Problemas de otimização complexos: problemas com muitas variáveis e espaços de soluções de dimensões elevadas. Ex: problema do caixeiro viajante, gerenciamento de carteiras de fundos de investimento.
-- Ciências biológicas: modela processos biológicos para o entendimento do comportamento de estruturas genéticas.
-- Autômatos auto-programáveis.
Até o presente momento todos os fundamentos apresentados basearam-se na nos
algoritmos genéticos simples. Existem outros tipos de algoritmos genéticos que
foram desenvolvidos para problemas mais específicos.
GENITOR
Genitor (Whitley 1988; 1989) é um algoritmo cujos melhores pontos
encontrados são preservados na população. Este procedimento é denominado de
elitismo. Na prática isto resulta numa busca mais agressiva, que na
prática é geralmente bastante efetiva. No entanto existe o perigo de uma
convergência prematura para mínimos locais. Cada indivíduo selecionado e
cruzado com seu parceiro é colocado no lugar do pior indivíduo da população
anterior. A aptidão é atribuída de acordo com um "ranking", ou seja, a aptidão
de cada indivíduo assume valores discretos.
CHC
Outro AG que coleciona os melhores indivíduos da população atual é o CHC
(Cross generational elitist selection, heterogeneous recombination and
Cataclysmic mutation). Após o cruzamento, feito aleatoriamente, os N
melhores indivíduos são coletados levando-se em consideração a população atual
e a população gerada após o cruzamento. Remove-se os indivíduos duplicados.
Este método impõe uma busca mais agressiva, assim como no Genitor. Repare que
a seleção está implícita no algoritmo, a partir do momento que escolhe os
melhores indivíduos de cada população (anterior e atual). Normalmente usa-se
populações pequenas, com 50 indivíduos, por exemplo. O ponto de cross-over é
sempre a metade do cromossomo. Para se solucionar o problema de convergência
prematura para mínimos locais é utilizada uma alta taxa de mutação, sempre
preservando o melhor indivíduo da população. A partir da primeira seleção
aleatória, utiliza-se o cross-over diretamente nas populações subsequentes.
ALGORITMOS HÍBRIDOS
Muitos autores consideram que os AG's nem sempre são a melhor solução para
problemas de otimização específicos. Desta forma, os algoritmos híbridos
utilizam os AG's como ponto de partida para métodos de otimização
tradicionais, como o "Simulated Annealing", método de Powel, entre outros. A
desvantagem destes algoritmos é a introdução de um "overhead" computacional
devido à busca baseada em populações, característica dos AG's. A mistura das
técnicas tradicionais com os AG's introduzem uma espécie de aprendizado no AG,
pois os cromossomos utilizados foram resultado da técnica denominada
"hill-climbing", utilizada nos métodos de otimização tradicionais, que
utilizam derivadas.
Conclusões
Os AG's são apropriados para problemas de otimização complexos, que
envolvem muitas variáveis e um espaço de soluções de dimensão elevada.
Abrangem um grande número de aplicações.
O controle sobre os
parâmetros do algoritmo é de fundamental importância para uma convergência
rápida.
Para problemas específicos é aconselhável a utilização de
algoritmos híbridos, que misturam as técnicas dos AG's com os métodos de
otimização tradicionais.
Devido ao grande número de variáveis que um AG
trata e às populações elevadas e alto número de gerações para a cobertura do
espaço de soluções, os AG's possuem um custo computacional elevado.
Referências
M. Mitchell, An Introduction to Genetic Algorithms. MIT Press, 1996.
H. Horner, "A C++ class library for genetic programming: The Vienna University of Economics - genetic programming kernel", Internet Draft, maio de 1996. http://www.wu-wien.ac.at/usr/h88/h8850092.
Darrel Whitley, "A Genetic Algorithm Tutorial", Computer Science Department, Colorado State University.
Grefentette, J.J. (1993) Foundations of Genetic Algorithms -2-, D. Whitley, ed., Morgan Kaufmann. pp: 75-91.
Muhlenbein, H. (1992) How genetic algorithms really work: I. Mutation and Hillclimbing, Paralell Problem Solving from Nature -2-, R. Manner and B. Manderick, North Holland.
Nix, A. and Vose, M. (1992) Modeling Genetic Algorithms with Markov Chains.
Annals of Mathematics and Artificial Intelligence. 5:79-88.