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.