Algoritmos

Genticos

Apostila EPAC Encontro Paranaense de Computao

Autor: Andr Luiz Brun

2

ndice

Evoluo 3

Seleo Natural 4

Histrico 6

Introduo 7

Quando Utilizar um Algoritmo Gentico? 9

Algoritmo Gentico Bsico 10

Tipos de Codificaes para os Algoritmos Genticos 11

Codificao Real X Clssica (Binria) 11

Inicializao 13

Clculo da aptido 13

Codificao Binria 13

Codificao Real 14

Seleo dos indivduos 14

Cruzamento 16

Codificao Binria 16

Codificao Real 18

Mutao 20 Codificao Binria 20

Codificao Real 21

Elitismo 22

Parmetros genticos 23

Aplicaes 24

Bibliografia 26

3

Os Algoritmos Genticos (AGs) so uma classe ou famlia de modelos

computacionais inspirados na evoluo defendida por DARWIN (1859). Foram

inicialmente propostos por HOLLAND (1975). So considerados tambm algoritmos de

busca que se valem do paradigma gentico/evolucionrio.

Para que haja uma melhor compreenso do surgimento e evoluo dos AGs

baseados nas idias evolucionistas de Darwin, idias que ficaram conhecidas como

darwinismo, ser visto uma breve introduo sobre evoluo natural.

Evoluo

O mundo sofreu uma revoluo acerca da evoluo natural com o lanamento de

dois livros de autoria de Charles Darwin (1809 1892): On the Origin of Species by

Means of Natural Selection (1859) e A The descent of man, and selection in relation to

sex (1871). Livros estes em que DARWIN defendia que o homem, assim como os outros

seres vivos, era resultado da evoluo.

Em seus estudos, DARWIN concluiu que nem todos os organismos que nascem,

sobrevivem ou reproduzem-se. Os indivduos mais propensos sobrevivncia so aqueles

mais adaptados para enfrentar determinadas condies ambientais. Logo estes indivduos

teriam maior chance de se reproduzir e assim deixar seus descendentes. Assim, com o

passar dos anos, as variaes favorveis tendem a permanecer e as desfavorveis tendem a

serem destrudas.

Um exemplo clssico da teoria Darwiniana a girafa. Inicialmente (h muito tempo

atrs) existiam girafas com caractersticas bastante divergentes, algumas com pescoo

longo, pescoo mdio e por fim, as girafas com pescoo comprido. Segundo Darwin, no

incio, todos os tipos de girafas conviviam normalmente, porm, com o passar do tempo, a

vegetao mais baixa foi tornando-se mais escassa, visto que todas as girafas podiam dela

se alimentar. Chegou ento um momento em que restou apenas a vegetao mais alta, onde

as girafas de pescoo mais curto no alcanavam. Logo, devido falta de alimento, estas

girafas, menos privilegiadas, foram morrendo, restando apenas as girafas mais aptas ao

meio (as de pescoo comprido). Ento, estas tiveram uma chance maior de reproduo e

4

conseqentemente maior chance de gerar descendentes, compondo assim a atual populao

de girafas apenas com indivduos de pescoo longo.

A Figura 1 ilustra o exemplo da evoluo das girafas, onde a seleo natural fez

com que apenas as girafas de pescoo comprido conseguissem gerar seus descendentes com

o passar do tempo. No primeiro quadro da figura ( esquerda), a populao era composta

pelos diversos tipos de girafas, no segundo quadro (ao centro) pode verificar que os

indivduos menos aptos, os de pescoo mais curto, foram sendo extintos. Restando assim,

apenas os indivduos de pescoo comprido, conforme o terceiro quadro da figura ( direita).

Figura 1: Populao composta por girafas de pescoo curto e pescoo comprido ( esquerda); Girafas de pescoo curto sofrendo extino natural (ao centro); Populao composta apenas por girafas de pescoo longo ( direita).

Seleo Natural

Segundo DARWIN (1859), a seleo natural um processo seletivo lento que

ocorre ao longo das geraes, atravs da qual as espcies podem se diversificar, tornando-

se mais adaptadas ao meio em que vivem. A seleo determinada, em certa parte, pelos

fatores ecolgicos do ambiente.

Atravs da seleo natural, a freqncia de um gene vantajoso, que apresenta

caractersticas positivas, aumenta gradativamente na populao. A vantagem conferida pelo

gene pode se refletir em diversos fatores que faam com que as espcies que o apresente

sejam mais aptas. Por exemplo, o gene pode refletir em um maior tempo de vida de um

5

elemento, aumentando assim a probabilidade do mesmo de se reproduzir. O gene pode

aumentar a sua freqncia se ele fornecer ao indivduo maior capacidade de se proteger.

Um exemplo bastante conhecido de seleo natural o caso das mariposas de

Manchester na Inglaterra, ocorrido durante a revoluo industrial. Onde, antes da

industrializao e conseqentemente pouca poluio do ar, a populao de mariposas era

em sua maioria, composta por indivduos de cor branca. Porm com a industrializao, a

poluio atmosfrica aumentou e, com o tempo o ambiente no qual a populao de

mariposas vivia foi alterado. Depois de anos, constatou-se que as mariposas que

representavam a maioria de seu conjunto eram agora as pretas. Este fato ocorreu devido ao

poder de camuflagem que as mariposas pretas apresentaram com a poluio que tornava as

superfcies escuras. J as mariposas brancas tornaram-se presas fceis uma vez que eram

facilmente descobertas por seus predadores.

Observando-se a Figura 2 fica bastante evidente a inverso entre o tamanho das

populaes das mariposas brancas e escuras. O segundo quadro ( direita) demonstra a

situao das mariposas em seu ambiente antes do processo que introduziu as indstrias na

cidade de Manchester. bastante difcil detectar a presena da mariposa de cor clara

(presente dentro do crculo amarela), j a mariposa escura facilmente identificada, o que a

tornava presa fcil aos seus predadores (principalmente pssaros). J o primeiro quadro (

esquerda) demonstra como o ambiente das mariposas sofreu com a poluio atmosfrica e

tambm superficial aps o processo de industrializao. Aps esta mudana no ambiente as

borboletas escuras passaram a ser os elementos camuflados, visto que a poluio fez com

que seu ambiente fosse alterado devido liberao de fuligem das indstrias, tornando

agora as mariposas brancas os alvos fceis, visto que no podiam mais se camuflar.

De maneira rudimentar, os AGs so tcnicas de busca baseadas nas teorias da

evoluo, nas quais as variveis so representadas como genes em um cromossomo.

Combinam a sobrevivncia dos mais aptos com a troca de informao de uma estrutura,

com a seleo natural, cruzamento e mutao dos elementos a fim de encontrar os

elementos mais aptos a determinada caracterstica do meio. No caso da computao a

melhor ou conjunto de melhores solues para o problema.

6

Figura 2: Borboleta clara camuflada pela superfcie de rvores e construes j a borboleta escura alvo dos predadores ( direita). Com a industrializao a superfcie foi alterada, favorecendo as mariposas escuras ( esquerda) colocando as mariposas brancas na mira dos predadores.

Histrico

O princpio de que a variabilidade entre indivduos de uma mesma populao que se

reproduz sexualmente produzida por dois fatores: a mutao e a recombinao gentica.

Este princpio foi desenvolvido durante os anos 30 e 40, por bilogos e matemticos de

importantes centros de pesquisa. Nos anos 50 e 60, muitos bilogos comearam a

desenvolver simulaes computacionais de sistemas genticos.

A seguir, John Holland dedicou-se ao estudo de processos naturais adaptveis, tendo

inventado os AGs em meados da dcada de 60. Ele desenvolveu os AGs em conjunto com

seus alunos e colegas da Universidade de Michigan nos anos 60 e 70, com o objetivo de

estudar formalmente o fenmeno da adaptao como ocorre na natureza, e desenvolver

modelos em que os mecanismos da adaptao natural pudessem ser importados para os

sistemas computacionais. Em 1975, Holland publicou seu livro intitulado Adaptation in

Natural and Artificial Systems e, em 1989, David Goldberg edita Genetic Algorithms in

Search, Optimization and Machine Learning [GOL89], hoje considerados os livros mais

importantes sobre AGs. Desde ento, estes algoritmos vm sendo aplicados com sucesso nos mais diversos problemas de otimizao e aprendizado de mquina.

7

Introduo

Toda tarefa de busca e otimizao geralmente composta por trs componentes

bsicos: a codificao do problema em questo (geralmente um dos passos mais complexos

do processo), o espao de busca, onde so consideradas todas as possibilidades de soluo

de um determinado problema e a funo de avaliao (funo fitness), que uma maneira

de avaliar os membros do espao de busca (varia de acordo com o problema). Existem

muitos mtodos de busca e funes de avaliao.

As tcnicas de busca e otimizao tradicionais iniciam-se com um nico candidato

que, iterativamente, manipulado utilizando algumas heursticas (estticas) diretamente

associadas ao problema a ser solucionado. Geralmente, estes processos heursticos no so

algortmicos e sua simulao em computadores pode ser muito complexa. Apesar destes

mtodos no serem suficientemente robustos, isto no implica que eles sejam inteis. Na

prtica, eles so amplamente utilizados, com sucesso, em inmeras aplicaes. Por outro

lado, as tcnicas de computao evolucionria operam sobre uma populao de candidatos

em paralelo. Assim, elas podem fazer a busca em diferentes reas do espao de soluo,

alocando um nmero de membros apropriado para a busca em vrias regies.

Os AGs diferem dos mtodos tradicionais de busca e otimizao, principalmente

em quatro aspectos:

Trabalham com uma codificao do conjunto de parmetros e no com os prprios parmetros;

Trabalham com uma populao e no com um nico ponto; Utilizam informaes de custo ou recompensa e no derivadas ou outro conhecimento

auxiliar;

Utilizam regras de transio probabilsticas e no determinsticas.

AGs so algoritmos de otimizao global baseados nos mecanismos biolgicos de

seleo natural e da gentica. Eles empregam uma estratgia de busca paralela (onde cada

indivduo de uma populao uma soluo potencial) e estruturada, mas aleatria, que

voltada em direo ao reforo da busca de pontos de "alta aptido", ou seja, pontos nos

8

quais a funo a ser minimizada (ou maximizada) tem valores relativamente baixos (ou

altos). Para realizar o processo so utilizados valores estatsticos.

Apesar de aleatrios, eles no so caminhadas aleatrias no direcionadas, pois

exploram informaes histricas para encontrar novos pontos de busca onde so esperados

melhores desempenhos. Isto feito atravs de processos iterativos, onde cada interao

chamada de gerao.

Durante cada iterao, os princpios de seleo e reproduo so aplicados a uma

populao de candidatos que pode variar, dependendo da complexidade do problema e dos

recursos computacionais disponveis.

A vantagem principal dos AGs ao trabalharem com o conceito de populao, ao

contrrio de muitos outros mtodos que trabalham com um s ponto, que eles encontram

segurana na quantidade. Tendo uma populao de pontos bem adaptados, a possibilidade

de alcanar um falso timo torna-se menor. Os AGs conseguem grande parte de sua

amplitude simplesmente ignorando informao que no constitua parte do objetivo,

enquanto outros mtodos apiam-se fortemente nesse tipo de informao e, em problemas

nos quais a informao necessria no est disponvel ou se apresenta de difcil acesso,

estes outros mtodos falham.

O conceito de mximo local (ou falso timo) acontece quando o algoritmo converge

para uma soluo local e a explora at que encontre seu melhor valor, ignorando, porm o

restante do espao de busca.

A Figura 3 retrata um exemplo onde o AG encontrou um mximo local, tambm

conhecido como falso timo. O algoritmo convergiu para a regio em vermelho, que

representa um mximo local, visto que para aquela regio ela a melhor soluo, porm

no melhor soluo dentro do espao de busca. A melhor soluo do espao de busca

representada pela figura em azul. O fato do timo local ocorre pois o algoritmo tende a

buscar aquele ponto, ignorando as demais regies pois as solues mais prximas so

piores (so os vales laterais ao pico, que representa a melhor soluo local).

Os AGs so ditos mtodos de busca cega, pois no tem conhecimento especfico do

problema a ser resolvido, tendo como guia apenas a funo objetivo. So mtodos

codificados, pois no trabalham diretamente com o domnio do problema e sim com

representaes dos seus elementos. Apresentam ainda caractersticas estocsticas

9

(aleatrias) pois combinam em proporo varivel regras probabilsticas e determinsticas.

Esse conceito refere-se tanto fase de seleo quanto fase de transformao.

Figura 3: Representa o espao de busca (todas as possveis solues). O quadro em vermelho representa um mximo local (ou falso timo). O quadro em azul representa a soluo tima do espao de busca.

Quando Utilizar um Algoritmo Gentico?

Pesquisas realizadas sobre os AGs descrevem uma vasta gama de aplicaes nas

quais estas tcnicas obtiveram pleno sucesso, mas existem tambm inmeros casos onde a

performance dos AGs no conseguiu obter bons resultados. Como podemos fazer para

verificar se um problema pode ou no ser resolvido atravs dos AGs?

Normalmente (na maioria das vezes), os AGs tm sido mais usados para soluo de

funes de otimizao, nas quais eles vm se mostrando bastantes eficientes e confiveis.

Porm, como de se esperar, nem todos os problemas podem ter resultados satisfatrios ou

mesmo ser representados adequadamente para o uso de tcnicas de AG. Geralmente

necessrio levantar as seguintes caractersticas relativas ao problema a ser resolvido, antes

de se tentar utilizar os AGs:

O espao de busca (possveis solues) do problema em questo deve estar delimitado dentro de uma certa faixa de valores.

10

Deve ser possvel definir uma funo de aptido (fitness) que nos indique quo boa ou ruim uma determinada resposta. Funo esta que servir de mtrica para a soluo do

problema.

As solues devem poder ser codificadas de uma maneira que resulte relativamente fcil a sua implementao no computador.

A literatura geralmente cita que os AGs podem ser utilizados para praticamente

todo tipo de problema, porm sempre interessante considerar as caractersticas citadas

acima para que o desenvolvimento do processo no seja invivel ou mesmo atingir solues

consideradas ruins.

Algoritmo Gentico Bsico

GOLDBERG (1989) apresenta a estrutura bsica do funcionamento de um AG e de

que maneira cada fase do mesmo realizada. Na Figura 4 apresentada uma explanao

mais detalhada. Cada fase do algoritmo ser vistam mais detalhadamente.

Basicamente o AG trabalha da seguinte forma:

Inicialmente gerada uma populao formada por um conjunto aleatrio de indivduos que podem ser vistos como possveis solues do problema.

Durante o processo evolutivo, esta populao avaliada: para cada indivduo dado um nota, ou ndice, refletindo sua habilidade de adaptao a determinado ambiente.

Uma porcentagem dos indivduos mais adaptados so mantidas, enquanto os outros so descartados.

Os membros mantidos pela seleo podem sofrer modificaes em suas caractersticas fundamentais atravs de mutaes e cruzamentos (crossover) ou

recombinao gentica gerando descendentes para a prxima gerao.

Este processo, chamado de reproduo, repetido at que uma soluo satisfatria seja encontrada. Embora possam parecer simplistas do ponto de vista biolgico, estes

algoritmos so suficientemente complexos para fornecer mecanismos de busca adaptativos

poderosos e robustos.

11

Figura 4: representao de um AG bsico (segundo GOLDBERG, 1989) contendo os passos presentes dentro

do processo.

Tipos de Codificaes para os Algoritmos Genticos

Atualmente existem 3 abordagens distintas que so utilizadas para realizar o

processo de codificao dos AGs. A codificao clssica (ou binria) que trabalha com

strings de bits, a codificao Real que trabalha diretamente com valores reais e a

codificao inteira, que trabalha apenas com valores inteiros.

O presente trabalho abordar somente a Codificao Binria e a Codificao Real,

uma vez que a codificao inteira apresenta uma gama de aplicao muito pequena.

Codificao Real X Clssica (Binria)

A codificao binria, ou clssica foi a primeira a ser construda, porm com o

passar dos anos e com o aumento das aplicaes dos AGs surgiu tambm a codificao

real.

12

Os processos que apresentarem diferenas entre a codificao real e a codificao

clssica sero abordados separadamente para melhor entendimento do texto.

A tcnica clssica de codificao dos algoritmos genticos utiliza strings de bits a

fim de representar os cromossomos. Porm, com a necessidade de maior preciso numrica,

as cadeias de bits se tornam excessivamente longas, o que acarreta na necessidade de um

esforo computacional maior, causando tambm um consumo maior de tempo at a

convergncia dos algoritmos.

Conforme HERRERA, LOZANO e VERDEGAY (1996), o uso de parmetros reais

torna possvel cobrir um domnio bastante abrangente, mesmo para domnios

desconhecidos, das variveis, o que difcil de se conseguir trabalhando com as cadeias

binrias, onde conforme o domnio do problema vai aumentando a preciso vai caindo (no

caso de cromossomos com tamanho fixo).

Outra vantagem em se utilizar parmetros reais a sua capacidade de explorar

gradualmente as funes com variveis contnuas. Esta evoluo gradual se aplica ao fato

de ligeiras (pequenas) mudanas nas variveis corresponderem a ligeiras mudanas na

funo. Ou seja, interessante explorar gradualmente o domnio do problema, pois a

soluo obtida pode ser melhor atravs de uma pequena mudana nos parmetros. J a

codificao real no possui esta opo de evoluir gradualmente.

O fato que acarreta em um consumo maior de tempo em problemas que necessitam

de uma boa preciso a necessidade de se calcular o valor decimal da cadeia binria que

representa o cromossomo na tcnica clssica. Alm de que nas cadeias binrias existe a

necessidade da converso dos bits para um valor numrico.

Segundo HERRERA, LOZANO e VERDEGAY (1996), devido a este problema

foram surgindo novas tcnicas de codificao dos cromossomos, diferentes da tcnica

clssica apresentada por Holland.

Uma soluo que foi proposta com o intuito de evitar esta perda excessiva de tempo

foi a utilizao de valores reais para se representar os cromossomos, tcnica esta que ficou

conhecida como codificao real.

Segundo SANTA CATARINA (2004), no caso de um cromossomo representar mais

que um caracterstico diferente, como o caso deste trabalho, pode ser utilizado vrios

genes dentro de um mesmo cromossomo.

13

Dentro da codificao real os operadores de mutao e cruzamento so realizados

de forma diferente do mtodo utilizado na tcnica tradicional.

Inicializao

Inicialmente uma populao de n indivduos criada. Cada um destes indivduos

representa uma possvel soluo, vivel ou no, para o problema em questo, ou seja, um

ponto no espao de solues.

Geralmente estes indivduos recebem valores aleatrios, mas caso o projetista tenha

um conhecimento considervel do problema a ser abordado ele pode fazer com que estes

indivduos iniciais (populao inicial) receba uma gama de valores direcionados, ou seja,

recebe valores que no se apresentaram absurdos ao contexto do problema. Por exemplo,

digamos que estamos trabalhando com um problema que visa encontrar a menor distncia

entre duas cidades, cada indivduo representa uma distncia, seria indesejvel que os

mesmos recebem distncias negativas j que distncias negativas no so possveis neste

caso. A inicializao realizada da mesma forma para as duas abordagens (binria e real).

Clculo da aptido

Neste passo so calculados os valores de aptido para cada um dos n indivduos da

populao. comum que esta aptido seja calculada atravs da funo objetivo, que

depende diretamente das especificaes do projeto. Aps o clculo os indivduos so

ordenados conforme sua aptido.

Codificao Binria

Caso o projetista esteja trabalhando com strings binrias necessria

transformao do valor binrio obtido em numrico, a fim de obter o valor do fitness. A

Equao 1 pode ser utilizada para calcular o mapeamento de um gene binrio inteiro em

um intervalo dos reais de ponto fixo a fim de realizar o clculo do fitness.

14

I min)(max12

min 10 += Lbx (1)

onde:

min: menor valor real no intervalo de mapeamento;

max: maior valor real no intervalo de mapeamento;

b10: valor binrio a ser mapeado convertido para base decimal;

L: no de bits utilizados no cromossomo binrio.

Codificao Real

Caso o projetista esteja trabalhando com a Codificao real no h a necessidade de

transformar os valores para que seja realizado o clculo da funo de aptido.

Seleo dos indivduos

Segundo SCHNEIDER (1998) a idia principal do operador de seleo, em um

algoritmo gentico, oferecer aos melhores indivduos da populao corrente preferncia

para o processo de reproduo, permitindo que estes indivduos possam passar as suas

caractersticas s prximas geraes. Isto funciona como na natureza, onde os indivduos

altamente adaptados ao seu ambiente possuem naturalmente mais oportunidades para

reproduzir do que aqueles indivduos considerados mais fracos.

Nesta fase, os indivduos que se mostraram mais aptos da gerao atual so

utilizados para gerar uma nova populao atravs do cruzamento, ao menos teoricamente,

visto que alguns mtodos no necessariamente selecionam apenas os melhores elementos

de cada gerao.

O processo de seleo realizado, geralmente, atravs de trs mecanismos bastante

conhecidos:

15

1. Amostragem direta: o conjunto de indivduos representantes da gerao

selecionado baseados em um critrio fixo. Pode ser visto como escolha a dedo ou os n

melhores;

2. Amostragem aleatria simples ou equiprovvel: todos os elementos possuem a

mesma chance de serem escolhidos para compor o conjunto que gerar a prole seguinte;

3. Amostragem estocstica: a chance de cada indivduo ser selecionado

diretamente proporcional ao valor de seu fitness. Um mtodo de seleo, baseado no

mecanismo de amostragem estocstico, bastante conhecido o Universal ou Por roleta

proposto por GOLDBERG (1989).

O mtodo considerado simples, pois consiste em criar uma roleta na qual cada

cromossomo possui um segmento proporcional sua aptido. Para um melhor

entendimento, ser utilizado um exemplo de uma populao com 7 cromossomos cuja

aptido dada pela converso de binrio para decimal. Como pode ser visto na tabela 1.

Com os valores percentuais obtidos na quarta coluna da Tabela 1, bem como a

terceira coluna da Tabela 2, possvel construir uma roleta constante, conforme a Figura

5. Esta roleta ser girada o nmero de vezes necessrias seleo a fim de que seja

composta a populao auxiliar que ser utilizada na propagao da espcie; neste caso a

roleta ser girada sete vezes. Os indivduos com fitness maior possuem uma rea maior na

roleta, acarretando maior probabilidade de seleo aos elementos mais aptos de cada

gerao.

interessante observar que a tabela abaixo se utilizada da codificao clssica.

Pode-se verificar a presena das cadeias de strings que representam os indivduos. Nota-se

que o campo da tabela chamado aptido obtido atravs da aplicao da Equao 1 aos

elementos do campo string (que representam cada um uma possvel soluo para o

problema). Neste caso, o valor de aptido simplesmente a transformao das cadeias

binrias em valores decimais.

Caso estivssemos trabalhando com a codificao real esta representao (por

tabela) seria um pouco diferente. O campo string seria desnecessrio e o campo aptido

seria composto apenas do valor de cada indivduo. Como representado na Tabela 2.

16

Tabela 1: Ilustrao de 7 indivduos atravs da codificao binria e de seus valores para a seleo por roleta (Monte Carlo).

Tabela 2: Ilustrao de 7 indivduos atravs da codificao real e de seus valores para a seleo por roleta (Mtodo de Monte Carlo).

Cruzamento

Codificao Binria

O processo de cruzamento utilizado aps a realizao da seleo. Nesta fase

ocorre a troca de segmentos entre pares de cromossomos selecionados para originar os

novos indivduos que viro a formar a populao da gerao seguinte.

17

A idia principal do cruzamento propagar as caractersticas positivas dos

indivduos mais aptos da populao atravs da troca de segmentos de informaes entre os

mesmos, o que originar novos indivduos.

As duas formas mais comuns de troca de segmentos nos Algoritmos Genticos so

as de um e de dois pontos de cruzamento.

1. Um ponto de cruzamento (single-point crossover): o ponto onde realizada a

quebra escolhido de forma aleatria, ou a critrio do projetista, dentro da string que o

representa. Baseado neste ponto realiza-se a troca de material cromossmico entre os dois

indivduos. Um exemplo de cruzamento de um ponto representado pela Figura 6;

2. Dois pontos de cruzamento (two-point crossover): realizado similarmente ao

cruzamento de um ponto, porm a troca de segmentos realizada com um nmero maior de

intercalaes, como visto na Figura 7.

Figura 5: Mtodo de seleo pela roleta, tambm conhecido como Mtodo de Monte Carlo

18

Figura 6: Exemplo de cruzamento com 1 ponto, ou single-point crossover (aplicado codificao binria)

Figura 6: Exemplo de cruzamento com 1 ponto, ou two-point crossover (aplicado codificao binria)

Codificao Real

Segundo SANTA CATARINA (2004), utilizam-se operadores de cruzamento

aritmticos para realizar o cruzamento dos cromossomos. Alguns exemplos de operadores

aritmticos so: mdia, mdia geomtrica, aritmtico e heurstico.

O tipo de cruzamento mais simples dentro da codificao real o cruzamento

simples, onde so escolhidos aleatoriamente dois indivduos de uma gerao e estes geram

os dois novos cromossomos. Funciona como o cruzamento de um ponto, porm com

valores reais, onde o ponto de cruzamento escolhido aleatoriamente (desde que no sejam

os pontos extremos do cromossomo). Cada novo cromossomo possuir metade dos genes

de cada pai. Por exemplo, temos dois cromossomos pais cada um com 10 genes diferentes.

Ento obtido um valor aleatrio da posio de cruzamento. Digamos que esta posio seja

5, ento, o primeiro filho ter os genes 1, 2, 3, 4 e 5 do primeiro pai e os genes 6, 7, 8, 9 e

10 do segundo pai. J o segundo filho ter os genes de 1 a 5 provenientes do segundo pai e

o restante dos genes do primeiro pai.

19

No cruzamento discreto os valores do novo cromossomo so randomicamente

escolhidos de uma distribuio uniforme formada a partir de um conjunto de valores

formado pelos pais.

Os cruzamentos da mdia simples e mdia geomtrica so bastante simples pois

consistem em gerar um novo cromossomo usando a mdia simples e a mdia geomtrica de

dois cromossomos pais, respectivamente. Abaixo as frmulas do cruzamento por mdia

simples (Equao 2) e por mdia geomtrica (Equao 3):

Mdia Simples 2

)( 211

PPC += (2)

Mdia Geomtrica 222

11 PPC = (3)

O cruzamento aritmtico realizado atravs da aplicao de duas frmulas:

211 *)1(* PPC += e 212 **)1( PPC += (4) onde c1 e c2 so os cromossomos filhos, p1 e p2 so os cromossomos pais e U(0, 1).

No cruzamento heurstico necessrio ter conhecimento do valor da funo fitness

dos pais. Este mtodo consiste em gerar um cromossomo filho partir de uma interpolao

linear entre os pais usando a informao da aptido. O cruzamento heurstico favorece o pai

com maior fitness. Dados dois cromossomos pais P1 e P2, onde o cromossomo P1 possui o

valor de fitness superior ao P2. O novo cromossomo gerado a partir da seguinte frmula

(Equao 5):

)( 211 PPrPC += onde (P1) > (P2) (5)

onde o valor de r varia de 0 a 1.

Segundo SANTA CATARINA (2004), o cruzamento BLX- consiste em gerar um novo cromossomo a partir da Equao 6:

)( 121 PPPC += (6)

20

onde C o cromossomo gerado, P1 e P2 so os cromossomos pais e U(-, 1 + ). um pequeno valor que estende os limites para a definio de C. Caso o cromossomo

seja formado por mltiplos genes, a Equao 4 aplicada a cada par de genes de P1 e P2.

Alm dos modelos de cruzamento para codificao real citados acima existem

outros apresentados na literatura como o cruzamento BGA linear, o cruzamento FCB

(fuzzy connectives based) entre outros.

SANTA CATARINA e BACH (2003) em seu trabalho implementaram algoritmos

baseados na tcnica clssica, e tambm utilizando a tcnica da codificao real para

encontrar a melhor soluo de uma determinada funo. Atravs da anlise dos resultados

obtidos por eles possvel verificar que ambos os algoritmos, apresentaram uma mesma, ou

muito similar, soluo tima para a funo em questo. Porm, os algoritmos que

utilizaram a codificao real encontraram esta soluo tima com um consumo menor de

tempo. Fato este justificado pelo consumo de tempo em se calcular o valor numrico a

partir da cadeia de bits que representa o valor. interessante citar que no caso em que foi

utilizada a tcnica clssica de implementao dos AGs a string era composta por 18 alelos

(2 para a parte inteira e 16 para a parte fracionria).

Mutao

A mutao geralmente vista como um operador de "background", responsvel pela

introduo e manuteno da diversidade gentica na populao (HOLLAND, 1975). Ela

trabalha alterando arbitrariamente um ou mais componentes de uma estrutura escolhida

entre a descendncia, logo aps o cruzamento, fornecendo dessa forma meios para a

introduo de novos elementos na populao. Assim, a mutao assegura que a

probabilidade de se chegar a qualquer ponto do espao de busca nunca ser zero.

Codificao Binria

O operador de mutao aplicado aos indivduos com uma probabilidade dada por

uma taxa de mutao definida pelo projetista. O cromossomo tem todos seus genes

percorridos. Caso a taxa de mutao seja maior que o valor sorteado pelo gene ento este

sofrer mutao. Geralmente esta taxa bastante baixa, sendo os valores comumente

21

usados dentro da faixa de 0,01 a 0,001. A Figura 7 exibe um exemplo de mutao, onde o

terceiro gene apresentou um valor inferior taxa de mutao e, portanto, sofrer a mutao.

Neste exemplo apenas para o terceiro gene o valor sorteado foi inferior ao valor da taxa de

mutao.

Pode acontecer de um cromossomo possuir vrios genes alterados pela mutao ou

mesmo no apresentar nenhuma alterao, caso o valor sorteado seja sempre maior que a

taxa de mutao fornecida pelo projetista.

Figura 7: Exemplo de Mutao Binria, onde apenas o 3 bit sofreu

mutao

Codificao Real

Segundo SANTA CATARINA (2004), existem diversas formas de se realizar a

mutao quando a codificao real est sendo utilizada, tais como mutao uniforme,

mutao gaussiana, creep, mutao no uniforme e no-uniforme mltipla.

HERRERA, LOZANO e VERDEGAY (1996) em seu trabalho propuseram a

mutao randmica que bastante simples. Os genes do novo cromossomo so obtidos

aleatoriamente de uma distribuio uniforme obtida de um intervalo determinado.

Conforme o mesmo autor a mutao uniforme efetuada atravs da substituio do

gene selecionado do cromossomo por outro gene gerado aleatoriamente, segundo uma

distribuio uniforme, entre os limites mnimo e mximo permitidos. Nesta distribuio

uniforme todos os nmeros possuem a mesma probabilidade de ocorrer, assim como em um

dado, onde qualquer dos valores possui uma probabilidade de 1/6 de ser obtido.

J a mutao gaussiana realizada substituindo-se o gene selecionado por outro

gerado a partir de uma distribuio N(pi, 2), onde pi igual ao valor de gene a ser

substitudo e a varincia definida pelo prprio pesquisador. Pesquisadores citam que o

22

valor da varincia pode ser iniciado prximo de 0,5 e de acordo com o aumento no nmero

de geraes ele pode ser diminudo.

Na mutao creep, acrescenta-se ou subtrai-se um pequeno nmero aleatrio obtido

de uma distribuio N(0, 2) onde a varincia assume um valor pequeno. Segundo o mesmo

autor, esta mutao utilizada para explorar o espao de busca localmente.

A mutao no-uniforme consiste na simples substituio de um gene por um

nmero extrado de uma distribuio no-uniforme, onde os valores possuem uma

probabilidade diferente de ocorrerem. A mutao no-uniforme mltipla consiste em

aplicar a mutao no-uniforme em todos os genes do cromossomo selecionado.

A mutao Discreta modal apresentada pelas Equaes 7 e 8:

=

=

0K

KMK B

(7)

onde,

=)log(

)log( minmB

rang (8)

Bm > 1 um parmetro conhecido como base da mutao e rangmin o menor limite

da faixa de mutao relativa.

Elitismo

O elitismo uma tcnica utilizada para melhorar a convergncia dos algoritmos. A

tcnica consiste em se escolher o melhor (ou melhores) indivduo de cada gerao e pass-

lo gerao seguinte sem que o mesmo (ou mesmos) sofra cruzamento e mutao, para que

conserve suas caractersticas consideradas boas. A utilizao do elitismo faz com que o

algoritmo convirja mais cedo principalmente, pois evita que os elementos mais aptos sejam

perdidos ou modificados.

23

Porm caso sejam utilizados muitos elementos dentro do elitismo o algoritmo pode

convergir precocemente e alcanar assim um mximo local.

O elitismo utilizado da mesma forma, tanto na codificao real quanto na

codificao clssica.

Parmetros genticos

O comportamento dos Algoritmos Genticos influenciado pelos parmetros

utilizados, para tanto, tornou-se necessrio estudar de que maneira os parmetros afetam o

comportamento dos AGs.

Os parmetros genticos afetam da mesma forma a codificao real e a codificao

clssica.

1. Tamanho da Populao: O tamanho da populao estabelece o nmero de

cromossomos na populao, o nmero de elementos de cada gerao. Afeta diretamente o

desempenho geral e a eficincia dos AGs. Trabalhando com uma populao de poucos

indivduos o desempenho pode ser comprometido visto que o espao de busca coberto ser

pequeno. J uma populao grande oferece uma cobertura representativa do domnio do

problema e ainda evita o problema de uma convergncia prematura para solues locais.

Porm, trabalhar com uma populao de tamanho considervel acarreta em uma

necessidade maior de recursos computacionais e tambm de um consumo de tempo maior;

2. Taxa de Cruzamento: A rapidez com que novas estruturas so introduzidas na

populao depende da taxa de cruzamento. Quanto maior for esta taxa, mais rapidamente

novas estruturas sero introduzidas. Porm, se esta for muito alta, a maior parte da

populao ser substituda, e pode ocorrer perda de estruturas de alta aptido. Com um

valor baixo, o algoritmo pode tornar-se muito lento;

3. Taxa de Mutao: responsvel por determinar a probabilidade em que uma

mutao ocorrer. Uma baixa taxa de mutao evita que uma dada posio entre em

estagnao, possuindo sempre o mesmo valor. Com uma taxa muito alta a busca tende a se

tornar estritamente aleatria, alm de aumentar muito a chance de que uma boa soluo do

problema seja destruda. A melhor taxa de mutao varia de acordo com o problema em

24

questo, mas acredita-se que para a maioria dos casos, o valor ideal se encontra entre 0,001

e 0,01;

4. Intervalo da Gerao: Determina a percentagem da populao que ser

substituda na gerao seguinte. Caso o valor do intervalo de gerao seja muito alto,

grande parte da populao poder ser substituda, aumentando assim as chances de se

perder indivduos com alta aptido. Porm, caso o valor seja muito baixo, o algoritmo pode

se tornar muito lento.

Aplicaes

A AIS (Barcelona, Espanha) utilizou um sistema apoiado em AGs e Sistemas Especialistas (SEs) para programar os Jogos Para-olmpicos de 1992 j que nas

Olimpadas os atletas so organizados em duas grandes classes, masculino e feminino, e os

competidores para-olmpicos so divididos em mais de 100 (cem) classes, segundo certas

restries mdicas.

Foi apresentado em 1999 na CEC99 IEEE International Conference on Evolutionary Computation um ambiente interativo, utilizando Algoritmos Genticos, para

a avaliao de msicas (seqncias de acordes) tocadas em arquivos MIDI. O mtodo

emprega o formalismo difuso e colocado como uma otimizao baseada em fatores

relevantes audio de msicas. No caso, os indivduos da populao foram definidos em

grupos de quatro vozes (soprano, contralto, tenor e baixo) ou coros. Cada um avaliado

segundo trs critrios: melodia, harmonia e oitavas. A composio destes trs critrios

definia a aptido (fitness) definida pela funo de seleo, que retorna o melhor indivduo,

ou melhor, coro. Um ciclo gentico operacionalizado, criando novos indivduos dos

anteriores e procurando sempre pelo melhor. Quando um novo grupo selecionado, ele

tocado em MIDI. A durao do ciclo gentico determina o ritmo da evoluo. O sistema

criado foi denominado Vox Populi. (FUKUSHIMA, 1999)

25

Um sistema em construo na New Mexico State University descreve imagens faciais de criminosos a partir de testemunhas do crime, utilizando AGs. O sistema tem se

mostrado mais efetivo na produo de imagens aprimoradas de criminosos do que qualquer

outra tcnica de obteno de informao de imagens.

Segundo Blanchard (1994), o ltimo WCCI'94 World Congress on Computational Intelligence ocorrido em Orlando, na Flrida, mostrou uma srie de

solues promissoras a situaes reais utilizando Algoritmos Genticos. Blanchard mostrou

o caso da US West, uma companhia regional de telecomunicaes do estado do Colorado,

que vem usando um sistema baseado em AGs que possibilita projetar, em duas horas,

redes ticas especializadas, trabalho que levaria seis meses utilizando especialistas

humanos. O sistema produz resultados ainda 10% (dez por cento) melhores que os

realizados pelo homem. A companhia estima que o sistema possibilitar uma economia de

100 milhes de dlares at o final do sculo.

Sponsler (1989) mostrou um sistema prottipo desenvolvido para avaliar a aplicabilidade dos Algoritmos Genticos na otimizao da programao do telescpio

espacial Hubble. Diversos operadores genticos foram avaliados e o melhor AG foi

comparado com um otimizador baseado em Redes Neurais (RN). Neste caso especfico os

AGs no se apresentaram to eficientes quanto as RNs.

Syswerda e Palmucci (1991) relataram a execuo de um otimizador para uma aplicao prtica de programao de recursos no laboratrio SITS System Integration

Test Station Laboratory da Marinha Americana, para o desenvolvimento do jato F-14.

No presente momento, talvez uma das mais populares aplicaes seja a de combinar Algoritmos Genticos com Redes Neurais, ou para trein-las ou para encontrar sua

topologia. Finalmente, importante salientar que ainda incipiente a pesquisa sobre a

aplicabilidade dos Algoritmos Genticos no problema de programao de projetos em

geral. , particularmente, muito pequena na rea de projetos de construo, por exemplo.

26

Multiprocessor Scheduling: A aplicao de AG's no problema de associao tima de processos e processadores. Objetivo e diminuir o custo que deriva da comunicao entre

processos em um ordenador paralelo de memria distribuda. Multiprocessor Scheduling

podem ser relacionados com problemas de robtica.

Biologia Molecular e Fsico-qumica: Existe uma hiptese de trabalho que sustentaria a utilizao de tcnicas baseadas em populaes devido a estrutura da funo

objetivo. Em problemas relacionados com estrutura molecular existem experimentos que

do indcios claros sobre a validez dessa hiptese. Assim fcil observar que so cada vez

mais numerosas as aplicaes de AG's neste campo.

Engenharia em Construes: Os AG's tem ganho aceitao em um grande nmero de problemas de Engenharia. Uma aplicao na otimizao discreta de estruturas.

Compresso de Dados: A compresso de dados em geral, e a compresso de imagens slidas em particular. Esta aplicao consiste em encontrar um mtodo que utiliza

os AG's para encontrar um sistema de funes locais iteradas (LIFS) para a codificao de

imagens. Produzindo como resultado final uma imagem com qualidade similar a utilizao

do mtodo convencional de compresso fractal, com um tempo 30% menor.

BRUN (2004) desenvolveu o trabalho Deteco de Faces Humanas em Imagens Digitais atravs do uso de um Algoritmo Gentico, onde utiliza os AGs para controlar os

fatores de Deslocamento, Escala e Rotao de um modelo de face.

Bibliografia

BRUN, A. L. SILVA I. F. SANTA CATARINA A. Deteco de Faces Humanas em

Imagens Digitais atravs do uso de um Algoritmo Gentico. UNIOESTE, Cascavel,

Brasil, 2004.

27

DARWIN, C. On the origin of species by means of natural selection. London, John

Murray, 1859.

DARWIN, C. The descent of man, and selection in relation to sex. London, 1871.

GOLDBERG, David E. Genetic Algorithms in Search, Optimization and Machine

Learning. Massachusets: Addison-Wesley Co, 1989.

HERRERA, F.; LOZANO, M.; VERDEGAY, J. L. Tackling Real-Coded Genetic

Algorithms: Operators and Tools for Behavioural Analysis. Artificial Intelligence

Review. v. 12, 1998.

HOLLAND, J. H. Adaptation in Natural and Artificial Systems. Ann Arbor:University

of Michigan Press, 1975.

SANTA CATARINA, A. Aplicaes De Algoritmos Genticos em Sistemas de

Informaes Geogrficas. Monografia final do Curso de Introduo ao

Geoprocessamento. INPE, So Jos dos Campos, 2004.

SANTA CATARINA, A., BACH, S. L. Estudo do efeito dos parmetros genticos na

soluo otimizada e no tempo de convergncia em algoritmos genticos com

codificaes binria e real. Acta Scientiarum: Technology. Maring, v. 25, n.2, p. 147-

152, 2003.

SCHNEIDER, A. M. Algoritmo Adaptativo Gentico para Acompanhamento da

Trajetria de Alvos Mveis. - Dissertao de Mestrado - Porto Alegre: Instituto de

Informtica - Universidade Federal do Rio Grande do Sul, 1998.

http://laqqa.iqm.unicamp.br/algoritmosgeneticos.htm

http://www.din.uem.br/ia/geneticos/

28

http://www.geocities.com/Athens/Sparta/1350/ia/ag_aplica.html

http://www.geocities.com/igoryepes/visualizar2.htm

http://www.gta.ufrj.br/~marcio/genetic.html

http://www.icmc.usp.br/~andre/research/genetic/