ESTUDOS DOS ALGORITMOS GENÉTICOS USANDO TÉCNICAS COMPUTACIONAIS

INSTITUTO DE ESTUDOS SUPERIORES DA AMAZÔNIA

CURSO: ENGENHARIA DA COMPUTAÇÃO

ÁUREA CELESTE DA COSTA RIBEIRO

MONICA CHIEKO HOSOGOSHI

ESTUDOS DOS ALGORITMOS GENÉTICOS

USANDO TÉCNICAS COMPUTACIONAIS

BELÉM

2005



ÁUREA CELESTE DA COSTA RIBEIRO

MONICA CHIEKO HOSOGOSHI

ESTUDOS DOS ALGORITMOS GENÉTICOS

USANDO TÉCNICAS COMPUTACIONAIS

Monografia de Conclusão de Curso, apresentado como requisito parcial para obtenção do grau de Bacharel em Engenharia de Computação.

Orientador Prof. Dr. Felipe Almeida

BELÉM

2005



ÁUREA CELESTE DA COSTA RIBEIRO MONICA CHIEKO HOSOGOSHI

ESTUDOS DOS ALGORITMOS GENÉTICOS USANDO TÉCNICAS COMPUTACIONAIS

Esta monografia foi julgada adequada para a obtenção do título de Bacharel em Engenharia da Computação e aprovada na sua forma pelo Instituto de Estudos Superiores da Amazônia.

Data:__/__/____

Conceito:________

____________________________________________

Prof. Dr. José Felipe Almeida Orientador

____________________________________________

Prof. Dr. Dionne Cavalcante Monteiro Coordenador de Engenharia da Computação

______________________________________________

Prof. Msc. Rodrigo Melo e Silva de Oliveira UFPA

BELÉM

2005

Para nossa família, nossa eterna gratidão.

AGRADECIMENTOS

A Deus, que sempre iluminou a nossa caminhada.

Ao nosso Orientador Prof. Dr. Felipe Almeida pela paciência e dedicação.

Ao nosso Coordenador do Curso Prof. Dr. Dionne Monteiro pelo estímulo e atenção que nos concedeu durante o curso.

Ao nosso amigo Rodrigo Oliveira pelo apoio e colaboração para a realização deste.

Aos nossos Colegas e amigos em especial a Cristina, Carlos Cristiano, Shirlen e Thais do IESAM pela amizade, companheirismo e troca de experiências.

A todos nossos familiares e amigos pelo apoio e colaboração.

“Transportai um punhado de terra todos os dias e fareis uma montanha”. Confúcio

LISTAS DE ILUSTRAÇÕES

P. Figura 1 - Fluxograma de um algoritmo genético tradicional..................................................... 19 Quadro1 - Medida de aptidão de cada indivíduo na população corrente.................................. 21 Figura 2 - Amostragem estocástica universal............................................................................ 22 Quadro 2 - População de strings e seus valores de fitness....................................................... 23 Figura 3 - Esquema gráfico do processo de cruzamento.......................................................... 24 Figura 4 - Crossover de 1 ponto................................................................................................ 25 Figura 5 - Crossover de 2 pontos.............................................................................................. 25 Figura 6 - Crossover uniforme................................................................................................... 25 Figura 7 - Esquema do processo de mutação........................................................................... 26 Figura 8 - Gráfico da função de Schaffer .................................................................................. Figura 9 – Codificação binária...................................................................................................

28 29

Figura 10 - Primeiro teste com o ga1.f....................................................................................... 30 Figura 11 - Segundo teste com o ga1........................................................................................ 31 Figura 12 - Terceiro teste com o ga1.f....................................................................................... 31 Figura 13 - Quarto teste com o ga1.f......................................................................................... 32 Figura 14 - Quinto teste com o ga1.f......................................................................................... 32 Figura 15 - Primeiro teste com o ga2.f....................................................................................... 33 Figura 16 - Segundo teste com o ga2.f...................................................................................... 33 Figura 17 - Terceiro teste com o ga2.f....................................................................................... 34 Figura 18 - Quarto teste com o ga2.f......................................................................................... 34 Figura 19 - Quinto teste com o ga2.f......................................................................................... 35 Figura 20 - Primeiro teste com o ga3.f....................................................................................... 35 Figura 21 - Segundo teste com o ga3.f...................................................................................... 36 Figura 22 - Terceiro teste com o ga3.f....................................................................................... 36 Figura 23 - Quarto teste com o ga3.f......................................................................................... 37 Figura 24 - Quinto teste com o ga3.f......................................................................................... 37 Figura 25 - Primeiro teste com o ga4.f....................................................................................... 38 Figura 26 - Segundo teste com o ga4.f...................................................................................... 38 Figura 27 - Terceiro teste com o ga4.f....................................................................................... 39 Figura 28 - Quarto teste com o ga4.f......................................................................................... 39 Figura 29 - Quinto teste com o ga4.f......................................................................................... 40 Quadro 3 – Erro médio do cruzamento...................................................................................... 45

SUMÁRIO .P

1 INTRODUÇÃO............................................................................................................... 10 CAPÍTULO 1 – HISTÓRICO............................................................................................. 12 1.1 ORIGEM DOS ALGORITMOS GENÉTICOS.............................................................. 13 1.2 TERMINOLOGIA DOS ALGORITMOS GENÉTICOS ................................................ 15 1.3 ALGORITMOS GENÉTICOS ..................................................................................... 16 CAPÍTULO 2 - DESCRIÇÃO DA TÉCNICA DE ALGORITMO GENÉTICO......... 19 2.1.ALGORITMO GENÉTICO TRADICIONAL....................................................... 19 2.2 COMPONENTES DE UM ALGORITMO GENÉTICO.................................................. 20 2.2.1 Problema.................................................................................................................. 20 2.2.2 Indivíduo.................................................................................................................. 20 2.2.2.1 Representação..................................................................................................... 20 2.3 OPERAÇÕES BÁSICAS.............................................................................................. 20 2.3.1 Inicialização............................................................................................................. 21 2.3.2 Avaliação................................................................................................................. 21 2.3.3 Seleção.................................................................................................................... 21 2.3.4 Reprodução............................................................................................................. 22 2.3.5.Cruzamento.............................................................................................................. 23 2.3.6 Mutação.................................................................................................................... 26 2.3.7 Atualização.............................................................................................................. 27 2.3.8 Finalização............................................................................................................... 2.3.9 Elitismo....................................................................................................................

27 27

CAPÍTULO 3 – RESULTADOS......................................................................................... 28 3.1 TESTES....................................................................................................................... 30 3.1.1 Gráficos do ga1 f em cinco testes, cruzamento de um ponto sem elitismo..... 30 3.1.2 Gráficos do ga2.f em cinco testes, cruzamento de um ponto com elitismo..... 33 3.1.3 Gráficos do ga3.f em cinco testes, cruzamento de dois pontos sem elitismo. 35 3.1.4 Gráficos do ga4.f em cinco testes, cruzamento de dois pontos com elitismo ...........................................................................................................................................

38

3.2 RESULTADOS QUANTO A PRECISÃO E MELHOR GERAÇÃO............................... 40 3.2.1 Testes com o ga1.f ................................................................................................. 40 3.2.2 Testes com o ga2.f.................................................................................................. 41 3.2.3 Testes com o ga3.f.................................................................................................. 42 3.2.4 Testes com o ga4.f.................................................................................................. 43 3.3 CONSIDERAÇÕES SOBRE OS RESULTADOS OBTIDOS....................................... 45 2 CONSIDERAÇÕES FINAIS............................................................................................ 46 3 REFERÊNCIAS............................................................................................................... 47

RESUMO

Este trabalho trata da implementação da Técnica de Computação Evolucionária chamada Algoritmos Genéticos. Dessa forma, é feita uma descrição sobre a parte conceitual do método e os passos usados em seu desenvolvimento. Para a validação do código implementado, usou-se uma função matemática como função - objetivo. O desempenho da técnica é observado em vários testes com a variação dos operadores genéticos em quatro códigos, que simulam dois tipos de cruzamento com e sem elitismo. Após os testes obteve-se a afinação da técnica para chegar ao valor máximo da função.

Palavras Chave: Algoritmos genéticos; Função - objetivo; Valor máximo; Computação

evolucionária.

ABSTRACT

This work describes the implementation of the Evolutionary Computation al Technique called Genetic Algorithms. In that way, it is made a description on the conceptual part of the method and the steps used in its development. For the validation of the implemented code, a mathematical function was used as fitness function. The technique is evaluated in several tests with the variation of the genetic operators in four codes that simulate two crossing types with and without elitism. After the tests it was obtained the tuning of the technique to arrive to the maximum value of the function. Key-words: Genetic algorithms; Function objective; Maximum value; Evolutionary computation.

1 INTRODUÇÃO

A atual tendência é modelar características humanas e naturais de forma

computacional. O homem vem fazendo com que algoritmos computacionais aproximem-se

cada vez mais da natureza e do ser humano seja em forma de aprender ou de pensar. Um

desses ramos da ciência de aproximação natural nos computadores é a computação

evolutiva que nos leva a modelar a teoria da evolução das espécies de Darwin ao longo das

gerações, abstraindo de uma determinada população as melhores informações genéticas

para a perpetuação de classes de indivíduos, fazendo com que para determinados

problemas, chegue-se à solução através desta técnica computacional. Assim, o principal

objetivo deste trabalho é desenvolver um estudo relacionado com a Técnica Computacional

de algoritmos genéticos, fazendo-se um levantamento bibliográfico e revisão da literatura. A

aprendizagem dessa técnica computacional permite obter conhecimento em uma área da

computação evolutiva.

Os Algoritmos Genéticos são métodos de busca e otimização, inspirados no modelo

de evolução de Darwin. Nesta técnica, o problema pode ser codificado em cromossomos, os

operadores genéticos se aplicam sobre esses cromossomos ou sobre a população desses

e, ao final, é apresentada a solução ótima para o problema. Esta técnica de otimização tem

uma vantagem sobre técnicas anteriores, pois trabalha com um conjunto das possíveis

soluções ao invés de uma a uma em seqüência, reduzindo o fator tempo de busca

(GUERVÓS, 2005).

Os Algoritmos Genéticos são aplicados em problemas complexos, com espaço de

busca muito grande ou de difícil formulação matemática. Por isso, são utilizados em

diversas aplicações, por exemplo: na Indústria, na Economia, na Engenharia e em estudos

sobre questões de Meio ambiente, entre outros (PACHECO, 2005).

Na classificação de imagens de sensoriamento remoto, a técnica computacional dos

Algoritmos Genéticos é usada para classificar imagens de satélites. Nesse tipo de problema,

o objetivo é mapear e atualizar os levantamentos da cobertura do solo. Logo, amostras

11

representativas das classes são selecionadas nas imagens multiespectrais e um processo

seletivo, semelhante a evolução das espécies de Darwin, são empregados para se chegar à

solução que fornece conjunto de parâmetros que satisfaz os critérios de busca. Então, com

este resultado, a imagem toda pode ser classificada (CENTENO, 2005). Exemplo em

engenharia da computação: busca e classificação em bancos de dados.

O algoritmo genético é também utilizado para determinar o melhor regime

operacional de uma central hidrelétrica com diversos grupos geradores diferentes entre si.

Este método considera a vazão como parâmetro hidráulico, os custos de investimento e de

operação e manutenção e a receita decorrente da venda da energia elétrica gerada. Como

resultado obtém-se um conjunto de melhores soluções possíveis para a implementação

(ALMEIDA, 2005).

Este trabalho trata da implementação computacional da Técnica dos Algoritmos

Genéticos. Para isto foi feito um código usando-se a linguagem de programação em

FORTRAN. O desempenho dessa técnica foi validado com modificações nos parâmetros da

formulação do método conhecido como Cruzamento. Assim, este trabalho foi dividido nos

seguintes Capítulos: no Capítulo 1, é apresentado um histórico sobre os Algoritmos

Genéticos e suas terminologias; no Capítulo 2, é feita uma descrição dessa técnica

computacional, e por fim, são apresentados, no Capítulo 3, os resultados do Código

desenvolvido.

12

CAPÍTULO 1 - HISTÓRICO

A teoria da evolução foi descrita por Charles Darwin, 20 anos depois de sua viagem

pela ilha de Galápos. Estas idéias são apresentadas no livro “A origem das espécies por

meio da seleção natural”. Este livro foi bastante polêmico na época e em qualquer caso é

uma descrição incompleta da evolução (SOARES, 1997).

As hipóteses de Darwin foram apresentadas junto com Walace e chegaram às

mesmas conclusões, independentemente. Observaram, portanto, que pequenas mudanças

hereditárias nos seres vivos e a seleção natural são os dois fatores que provocam a

mudança nas gerações de espécies. Mas, Darwin não sabia qual era a base da herança,

pensava que os traços de um ser vivo eram como um fluido, e que os “fluidos” dos pais se

inseriam na descendência. Essa hipótese tinha o problema que ao final de certo tempo, uma

população tinha os mesmos traços em intervalos. Amabis; Martho (1997).

Foi Mendel que descobriu que as características são herdadas de forma discreta, e

que partiam do pai ou da mãe, dependendo da característica dominante ou recessiva. A

essas características que podiam tomar diferentes valores, Mendel chamou de genes, e aos

valores que podiam tomar alelos. Na realidade as teorias de Mendel foram esquecidas e não

voltaram à tona até o princípio do século XX. Soares (op. cit.).

Em 1930 o geneticista inglês Robert Aylmer não relacionou ambas as teorias,

demonstrando que os genes mendelianos eram os que proporcionavam o mecanismo

necessário para a evolução. Mais ou menos pela mesma época, o biólogo alemão Walther

Flemming descobriu os cromossomos, como certos filamentos nos quais se agregava a

cromatina do núcleo celular durante a divisão, mais adiante descobriram que as células de

cada espécie vivente tinham um número fixo e característico de cromossomos, até nos anos

50, quando Watson e Crick descobriram que a base molecular dos genes está no DNA. Os

cromossomos são compostos de DNA, e, portanto, os genes estão nos cromossomos

Soares (op.cit.).

13

Todas essas descobertas, nos dias atuais, formam a teoria do neodarwinismo, que

afirma que a história da maioria das espécies está relacionada por uma série de processos

que atuam dentro das populações: reprodução, mutação, competição e seleção. Amabis;

Martho (op. cit.). É necessário compreender os mecanismos de mudança para entender os

algoritmos evolutivos, esse trata de imitar estes mecanismos para resolver os problemas

complexos. Os mecanismos de mudança alteram a proporção de alelos de um tipo

determinado em uma população e dividem-se em dois tipos, os que diminuem a

variabilidade genética e os que a aumentam sua freqüência. Amabis; Martho (op. cit.).

Dentre os que diminuem a variabilidade genética, encontra-se principalmente a

Seleção natural, onde os indivíduos que tenham alguma característica que os façam menos

adaptados para realizar tarefas necessárias a sua sobrevivência, terão menos probabilidade

de reproduzir-se, logo seu schemas patrimônio genético terá menos probabilidade de ser

repassado a outras gerações. Essa seleção sucede-se a muitos níveis: competição entre

indivíduos da mesma espécie, competição entre diferentes espécies e competição entre

presa e predador. Amabis; Martho (op. cit.).

O principal mecanismo que aumenta a variabilidade genética é a mutação, essa

representa uma alteração do código genético, que pode acontecer por múltiplas razões, são

totalmente aleatórias e é o mecanismo básico de geração de variabilidade genética, apesar

de que se pensa habitualmente, as maiorias das mutações ocorrem de forma natural,

existem substâncias mutagênicas que aumentam sua freqüência. Amabis; Martho (op. cit.).

1.1 ORIGEM DOS ALGORITMOS GENÉTICOS

John Holland desde pequeno, perguntava-se como a natureza conseguia criar seres

cada vez mais perfeitos, não sabia a resposta, mas tinha certa idéia de como achá-la, então

fez alguns pequenos modelos da natureza com características iguais as reais e observou

seu comportamento, para fazer suas conclusões deste feito, desde pequeno fazia

simulações de batalhas, copiava mapas e os cobria de pequenos exércitos que se

enfrentavam entre si. (GUERVÓS, 2005).

14

Nos anos 50, quando entrou em contato com os primeiros computadores, pode levar

a prática algumas de suas idéias, mas não encontrou um ambiente fértil para divulgá-las. Foi

no princípio dos anos 60, na universidade de Michigan, que dentro de um grupo de lógica

computacional (logic of computers), suas idéias começaram a ser testadas e a darem frutos.

Lendo livros sobre a teoria evolucionista, começou a descobrir meios de por em prática seus

propósitos de entender a natureza. Aprendeu que a evolução era uma forma de adaptação

mais poderosa que uma simples aprendizagem, e tomou a decisão de aplicar as idéias da

evolução em programas de computadores para determinados fins.

(GUERVÓS, 2005).

Nesta universidade, Holland ministrava aulas sobre sistemas adaptativos, e com a

participação ativa de seus alunos, criaram as idéias que mais tarde gerariam os algoritmos

genéticos. Os objetivos em sua pesquisa para a criação dos algoritmos genéticos, segundo

Guervós op. Cit. Foram:

- Imitar os processos de evolução dos sistemas da natureza;

- Construir sistemas artificiais que tivessem os mecanismos de evolução dos sistemas

naturais.

Depois de 15 anos, David Goldberg tornou-se aluno de Holland e como Engenheiro

industrial trabalhava com desenhos de pipelines, teve a idéia de aplicar os algoritmos

genéticos em seu trabalho. Holland não acreditava na possibilidade, pois pensava que o

problema era muito complexo para aplicar a técnica (Guervós op. cit.).

Goldberg teve sucesso em sua idéia, escreveu um algoritmo genético em um

computador pessoal, o Aple II. Todas estas e outras aplicações, criadas por estudantes de

Holland, tornaram os Algoritmos Genéticos um campo de estudo, discutido em conferencias

próprias, como a ICGA, a primeira celebrada em 1985 (Guervós op. cit.).

15

1.2 TERMINOLOGIA DOS ALGORITMOS GENÉTICOS

Para um melhor entendimento do funcionamento e os entes envolvidos em um

algoritmo genético, é necessário entender a terminologia envolvida, cita-se as principais:

GENÓTIPO: é a forma (arranjo) de como os genes e cromossomos estão distribuídos, que

correspondem a determinado fenótipo.

FENÓTIPO: é o conjunto das características de certo indivíduo observado ou descrito por

outros métodos, fornecidas pela manifestação do genótipo.

POPULAÇÃO: conjunto de indivíduos da mesma espécie; grupos inteiros de organismos de

um tipo; um grupo intercruzante de animais ou vegetais; grupo amplo do qual podemos

tomar uma amostra.

ESPÉCIE: grupo de indivíduos intercruzante que são isolados reprodutivamente de outros

grupos semelhantes, contendo fenótipos semelhantes.

INDIVÍDUO: é aquele exemplar de uma espécie que interage com o meio ambiente.

CROMOSSOMO: componente genético responsável pelo fenótipo do indivíduo, conjunto de

genes.

GENE: unidade básica do cromossomo que define, de acordo com seu valor e posição, uma

característica; um determinador hereditário que especifica uma função biológica; uma

unidade de herança (DNA) localizada em um lugar fixo no cromossomo.

16

SELEÇÃO NATURAL: mecanismo que garante aos indivíduos mais aptos melhores

chances de reprodução; fertilidade diferencial na natureza favorecendo os indivíduos que se

adaptam melhor e buscando eliminar aqueles indivíduos não adaptados ao meio.

REPRODUÇÃO: é a multiplicação de novos indivíduos a partir de outros que pertencem à

mesma espécie.

AJUSTE OU AVALIAÇÃO: medida que determina o grau de aptidão de um indivíduo ao seu

meio ambiente.

1.3 ALGORITMOS GENÉTICOS

Os Algoritmos Genéticos são técnicas de busca e otimização. Com isso, podem ser

vistos como um conjunto de procedimentos de buscas adaptativas. Um ponto chave deles é

que o processo de adaptação não se dá por incrementação de uma estrutura do algoritmo,

mas mantendo uma população de estruturas a partir das quais se geram novas populações.

Para isto são utilizados os operadores genéticos. Os operadores genéticos correspondem

as seguintes etapas segundo Lucas (2005):

Avaliação: onde a aptidão, o fitness, capacidade das espécies adaptarem-se ao meio, é feita no problema, para estabelecer quão bem as possíveis soluções respondem ao problema; Seleção: Indivíduos selecionados para a reprodução, a probabilidade de serem selecionados é proporcional à sua aptidão; Cruzamento: Características das soluções escolhidas são recombinadas, gerando novos indivíduos; Mutação: características dos indivíduos resultantes do processo de reprodução são alteradas, acrescentando assim variedade a população; Atualização: Os indivíduos criados nesta geração são inseridos na população; Finalização: Verifica se as condições de encerramento da evolução foram atingidas, retornando para a etapa de avaliação em caso negativo e encerrando a execução em caso positivo.

17

Atribuiu-se a forma particular de trabalhar dos Algoritmos Genéticos pelas seguintes

características:

A) Busca Codificada

Pére 2000 (citado por Lucas, 2002, p. 6):

Os Algoritmos Genéticos não trabalham sobre o domínio do problema, mas sim sobre representações de seus elementos. Tal fator impõe ao seu uso uma restrição: para resolver um problema é necessário que o conjunto de soluções viáveis para este possa ser de alguma forma codificada em uma população de indivíduos.

B) Generalidade

Whi 2000 (citado por Lucas, 2002, p. 6):

Os algoritmos genéticos simulam a natureza em um de seus mais fortes atributos: a adaptabilidade. Visto que a representação e a avaliação das possíveis soluções são as únicas partes (de um considerável conjunto de operações utilizadas em seu funcionamento) que obrigatoriamente requisitam conhecimento dependente do domínio do problema abordado, basta à alteração destas para portá-los para outros casos. A preocupação de um programador de Algoritmos Genéticos não é então de que forma chegar a uma solução, mas sim com o que ela deveria se parecer.

C) Paralelismo explícito

Lucas (2002) diz:

O alto grau de paralelismo intrínseco aos Algoritmos Genéticos pode ser facilmente verificado se considerarmos o fato de que cada indivíduo da população existe como um ente isolado e é avaliado de forma independente. Se na natureza todo processo de seleção ocorre de forma concorrente, nos Algoritmos Genéticos essa característica se repete.

D) Busca estocástica

Gey 97, Mic 99 (citado por Lucas, 2002, p. 7):

Ao contrário de outros métodos de busca de valores ótimos, os algoritmos genéticos não apresentam um comportamento determinístico. Não seria correto, no entanto, afirmar que tal busca se dá de forma completamente aleatória — as probabilidades de aplicação dos operadores genéticos fazem com que estes operem de forma previsível estatisticamente, apesar de não permitirem que se determine com exatidão o comportamento do sistema.

18

E) Busca Cega

Gey 97, Pére 2000 (citado por Lucas, 2002, p. 7):

Um algoritmo genético tradicional opera ignorando o significado das estruturas que manipula e qual a melhor maneira de trabalhar sobre estas. Tal característica lhe confere o atributo de não se valer de conhecimento específico ao domínio do problema, o que lhe traz generalidade por um lado, mas uma tendência a uma menor eficiência por outro.

F) Eficiência mediana

Dav 91, Gey 97, Bur 95(citado por Lucas, 2002, p. 7):

Por constituir um método de busca cega, um algoritmo genético tradicional tende a apresentar um desempenho menos adequado que alguns tipos de busca heurística orientada ao problema. Para resolver tal desvantagem, a tática mais utilizada é a hibridização, onde heurísticas provenientes de outras técnicas são incorporadas.

G) Paralelismo Implícito

Gol 89 (citado por Lucas, 2002, p. 7):

Os Algoritmos Genéticos buscam uma solução ótima, partindo de várias soluções, ao mesmo tempo, enquanto que os métodos clássicos de otimização efetuam a busca voltados a uma única solução a cada instante. Assim, pode-se perceber que existe um paralelismo implícito, que permite encontrar a melhor solução ótima dentre todas as possíveis soluções (ótimo global).

H) Facilidade no uso de Restrições

Bar 96 (citado por Lucas, 2002, p. 7):

Ao contrário de muitos outros métodos de busca, os Algoritmos genéticos facilitam a codificação de problemas com diversos tipos de restrição, mesmo que elas apresentem graus diferentes de importância. Neste caso, se dois indivíduos violam restrições, é considerado mais apto àquele que viola as mais flexíveis (soft constraints) em detrimento do que viola as mais graves (hard constraints).

19

CAPÍTULO 2 - DESCRIÇÃO DA TÉCNICA DE ALGORITMO GENÉTICO

2.1.ALGORITMO GENÉTICO TRADICIONAL

O Algoritmo Genético tradicional realiza, segundo Fialho 2005 (citado por Bittencourt,

1998), as seguintes funções:

1.Gera a população inicial de forma aleatória;

2.Avalia cada indivíduo da população;

3.Enquanto critério de parada não for satisfeito faça:

3.1.Seleciona os indivíduos mais aptos de acordo com a avaliação;

3.2.Cria novos indivíduos aplicando os operadores crossover e mutação;

3.3.Armazena os novos indivíduos em uma nova população;

3.4.Avalia cada cromossomo da nova população.

Estas funções são representadas num fluxograma de forma simplificada, conforme

Figura 1.

Figura 1-Fluxograma de um algoritmo genético tradicional Fonte: Lucas, 2000

20

Deve-se notar que a codificação empregada e o algoritmo têm que garantir a restrição do espaço de busca. Isso é fundamental para a convergência do método, os limites estão relacionados ao problema estudado.

2.2 COMPONENTES DE UM ALGORITMO GENÉTICO

Nos tópicos que seguem, são descritos os componentes de um algoritmo genético

segundo Lucas (2002).

2.2.1 Problema

Geralmente, o problema é quando se tem um grande espaço de busca ou problemas

complexos e sem formulação matemática precisa.

2.2.2 Indivíduo

São os responsáveis por codificarem as possíveis soluções para o problema a ser

tratado, e através de sua manipulação que as respostas são achadas.

2.2.2.1 Representação

É fundamental no desempenho de um algoritmo genético e deve: descrever o

espaço de busca relevante ao problema, codificar ”geneticamente” a essência do problema

e ser compatível com os operadores.

Por exemplos:

Vetores de reais (2.345, 4.3454, 5.1)

Cadeias de bits (1101110)

Vetores de inteiros (1,3,4,5,9)

-ou outra estrutura de dado.

2.3 OPERAÇÕES BÁSICAS

As operações básicas de um algoritmo genético são Lucas (2002): inicialização,

avaliação, seleção, reprodução, cruzamento, mutação, atualização e finalização.

21

2.3.1 Inicialização

Na inicialização faz-se o uso de funções aleatórias para gerar os indivíduos, na qual

visa fornecer maior “biodiversidade”, fundamental para garantir uma boa abrangência do

espaço de pesquisa.

2.3.2 Avaliação

Nesta fase, cada indivíduo da população é avaliado a fim de que seja determinado o

seu grau de adaptação, isto é, a nota associada ao indivíduo que avalia quão boa é a

solução por ele representada.

No exemplo, a função matemática f(x) = x2 mede aptidão de cada indivíduo. No

Quadro 1, C1 é um indivíduo mais apto que C2.

Cromossomo x f(x)

C1 0 0 1 0 0 1 9 81

C2 0 0 0 1 0 0 4 16

Quadro 1-Medida de aptidão de cada indivíduo na população corrente

Fonte: Autoria própria, 2005

2.3.3 Seleção

A Seleção é a imitação da seleção natural, onde determina quais indivíduos da

população podem participar da fase de reprodução, normalmente privilegia os indivíduos

mais aptos. Assim, perpetuando as melhores características na espécie. Segundo Daw

(citado por LUCAS, 2002) ela é um processo:

Dirigido: a seleção é feita de forma determinística, isto é, um indivíduo só

sobreviverá no ambiente e nele se reproduzir se for capaz de responder de forma adequada

a todos os fenômenos de seu meio;

Cumulativo: os benefícios do processo da seleção são mantidos de geração para

geração.

22

Tem-se a seleção proporcional a aptidão (roleta) considera-se 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 conforme a Figura 2. Colocam-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 processo é denominado amostragem universal estocástica.

Evidentemente, os indivíduos cujas regiões possuem maior área terão maior probabilidade

de serem selecionados vários vezes. Como conseqüê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 Fonte: Miranda, 2005

E também seleção torneio onde se escolhe n (tipicamente 2) indivíduos

aleatoriamente da população e o melhor é selecionado.

2.3.4 Reprodução

Uma vez feita à seleção será feita à reprodução na quais os indivíduos são

reproduzidos com base na aptidão, ou seja, os melhores adaptados têm maiores chances

de participar da reprodução. Isto é, os cromossomos ou strings com maiores valores têm

maior probabilidade de formar a próxima geração. Este operador é o modelo artificial da

seleção natural. E a aptidão ou fitness é a habilidade que o indivíduo possui para sobreviver

a predadores, doenças e outros obstáculos. Esta função no meio artificial é que decidirá

quais os cromossomos ou strings que sobreviverão e quais morrerão.

23

Por exemplo, o resultado da decodificação binária da string 10101 representa a sua

aptidão ou fitness e a função objetivo ou payoff poderia maximinizar este valor conforme o

Quadro 2 abaixo:

10101 = 1 x 24 + 0x23 + 1x22 + 0x21 + 1x20 = 21 (fitness)

POPULAÇÃO "FITNESS"

0 0 0 1 1

0 1 1 0 6

1 0 1 0 12

Quadro 2 - População de strings e seus valores de fitness Fonte: Fialho, 2005

2.3.5.Cruzamento

Em seguida o cruzamento que é a troca de gene, responsável pela combinação das

características genéticas dos pais durante a reprodução, permitindo que elas sejam

herdadas pelas próximas gerações. Ou seja, onde se determina aleatoriamente quais

strings que casarão e logo, também aleatoriamente, em que posição da string se processará

o cruzamento ou crossover.

Por exemplo, considerando - se dois strings: A e B, com seguintes decodificações

binárias:

24

"A" = 0 1 1 0 1

"B" = 1 1 0 0 0

Caso seja escolhida a posição de corte K=4 após a quarta posição da string, o

cruzamento terá a seguinte configuração, em decorrência da troca, conforme destacado em

negrito:

"A" = 0 1 1 0 0

"B" = 1 1 0 0 1

Na figura abaixo se visualiza melhor o cruzamento:

Figura 3 - Esquema gráfico do processo de cruzamento (um ponto) Fonte: Fialho, 2005

Têm-se vários tipos de cruzamento como veremos a seguir:

Cruzamento de 1 ponto: Um ponto de corte é escolhido aleatoriamente a série binária

desde o começo do cromossomo até o ponto de cruzamento é copiada do primeiro pai e o

resto copiado do segundo pai.

25

11001011+11011111 = 11001111

Figura 4 - Crossover de 1 ponto Fonte: Manoel, 2004

Cruzamento de 2 pontos: Dois pontos de cruzamento são definidos aleatoriamente, a

série binária desde o início do cromossomo até o primeiro ponto de cruzamento é copiada

do primeiro pai, a parte do primeiro ponto de cruzamento até o segundo ponto é copiada do

segundo pai e o resto do cromossomo é copiado do primeiro pai novamente.

11001011 + 11011111 = 11011111

Figura 5 - Crossover de 2 pontos Fonte: Manoel, 2004

Cruzamento uniforme: os bits são copiados aleatoriamente do primeiro ou segundo pai.

11001011 + 11011101 = 11011111

Figura 6 - Crossover uniforme Fonte: Manoel, 2004

26

2.3.6 Mutação

A mutação é a troca aleatória de um gene, responsável pela introdução e

manutenção da diversidade genética na população, alterando arbitrariamente um ou mais

genes de um cromossomo escolhido aleatoriamente. Ocorrendo a introdução de novos

elementos na população. Assim, todo o processo de busca, influenciando diretamente a

velocidade de convergência e evitando que aconteça a supremacia de uma determinada

sub-população, o que geraria o chamado elitismo.

Por exemplo, pode ser verificado na figura abaixo uma analogia do processo de

mutação, onde é alterada a cor dos strings nas posições "2", "4" e "7", da situação "A" para

a situação "A’" (FIALHO, 2005).

Figura 7 - Esquema do processo de mutação Fonte: Fialho, 2005

27

2.3.7 Atualização

Na atualização os indivíduos resultantes do processo do cruzamento e mutação são

inseridos na população segundo o algoritmo genético tradicional como vimos mais

anteriormente.

2.3.8 Finalização

A finalização é o fim do processo caso se tenha satisfeito a condição de parada

como vimos anteriormente também.

2.3.9 Elitismo

O Elitismo é o método utilizado em Algoritmos Genéticos para melhorar a

convergência e é também uma adição aos métodos de seleção que forçam os Algoritmos

Genéticos a reterem certo número de melhores indivíduos em cada Geração. Tais

indivíduos podem ser perdidos se eles não forem selecionados para a reprodução ou se

eles forem destruídos por cruzamento ou mutação. (CATARINA, 2005)

28

CAPÍTULO 3 – RESULTADOS

Para observar o comportamento de um Algoritmo Genético, utilizaram-se os códigos

ga1.f, ga2.f, ga3.f e ga4.f (Universidade...2005) que modelam um Algoritmo Genético para

obter o máximo de uma função, com cruzamentos de 1 e 2 pontos com ou sem elitismo.

Problema:

Maximinizar a função de Schaffer :

F = 0.5 - ((sin((x**2+y**2)**.5) )**2 -.5 )/(1+.001*(x**2+y**2) )**2

Figura 8 - Gráfico da função de Schaffer


A função de Schaffer, como observado na Figura 8, tem vários pontos de pico (

máximos locais), denotados pelas delimitações de cores variadas. O máximo dessa função

é representado pelo ponto central de cor vermelha, que é próximo do ponto (0,0). Essa

situação ilustra a dificuldade de encontrar este resultado.

29

Para modelar o algoritmo Genético utilizou-se uma representação binária, onde a

função aptidão que mede o fitness de cada indivíduo é a própria função de Schaffer. A taxa

de mutação utilizada é de 2 % e a taxa de cruzamento de 100%, com 50 bits (sendo 25 por

parâmetro (x,y)), a precisão de 5 casas decimais entre cada unidade ( 10 elevado a 5) e a

faixa é -100 a 100 para x e y, o método de seleção do tipo roleta, com máximo de 10.000

gerações, sendo que cada contém 200 indivíduos.

Desse modo a codificação binária foi feita da seguinte forma:

Figura 9 – Codificação binária Fonte: Autoria Própria,2005

30

Tipos de cruzamentos observados nos códigos:

ga1.f - Cruzamento de 1 ponto sem Elitismo

ga2.f - Cruzamento de 1 ponto com Elitismo

ga3.f - Cruzamento de 2 pontos sem Elitismo

ga4.f – Cruzamento de 2 pontos com Elitismo

Cada código foi testado cinco vezes cada, a fim de observar o comportamento do

Algoritmo em cada caso.

3.1 TESTES

3.1.1 Gráficos do ga1 f em cinco testes, cruzamento de um ponto sem elitismo

Figura 10 - Primeiro teste com o ga1.f Fonte: Autoria Própria, 2005

31

Figura 11 - Segundo teste com o ga1.f


Figura 12 - Terceiro teste com o ga1.f


32

Figura 13 - Quarto teste com o ga1.f


Figura 14 - Quinto teste com o ga1.f


33

3.1.2 Gráficos do ga2.f em cinco testes, cruzamento de um ponto com elitismo:

Figura Figura 15 - Primeiro teste com o ga2.f

Fonte: Autoria, própria, 2005

Figura 16 - Segundo teste com o ga2.f Fonte: Autoria própria, 2005

34

Figura 17 - Terceiro teste com o ga2.f Fonte: Autoria própria, 2005



35

Figura 19 - Quinto teste com o ga2.f Fonte: Autoria própria, 2005

3.1.3 Gráficos do ga3.f em cinco testes, cruzamento de dois pontos sem elitismo:

Figura 20 - Primeiro teste com o ga3.f Fonte: Autoria própria, 2005

36



37

Figura 23 - Quarto teste com o ga3.f Fonte: Autoria própria, 2005


38

3.1.4 Gráficos do ga4.f em cinco testes, cruzamento de dois pontos com elitismo:

Figura 25 - Primeiro teste com o ga4.f Fonte: Autoria própria, 2005


39




40


3.2 RESULTADOS QUANTO A PRECISÃO E MELHOR GERAÇÃO

3.2.1 Testes com o ga1.f

-teste 1 (figura 9)

Melhor Indivíduo: x = 0.0620305538 y = -0.0569760799

Valor do Máximo: 0.99291569

Melhor geração: 1314

-teste 2 (figura 10)

Melhor Individuo: x = 0.0112771988 y = -0.0149011612

Valor do Maximo: 0.999650478


41






Melhor Indivíduo: x = -2.21600533 y = 2.22252607




Melhor Individuo: x = 0.0459849834 y = 0.0153064728

Valor do Maximo: 0.997650623




Melhor Indivíduo: x = -1.1920929E-05 y = 0.000143051147

Valor do Máximo: 1


Seqüência: 01111111111111111111111101000000000000000000011000


Melhor Indivíduo: x = -3.57627869E-05 y = -0.000160932541

Valor do Máximo: 1.


Seqüência: 01111111111111111111110100111111111111111111100101

42


Melhor Indivíduo: x = 0. y = 5.96046448E-06

Valor do Máximo: 1


Seqüência: 10000000000000000000000001000000000000000000000001


Melhor Indivíduo: x = -5.96046448E-06 y = -5.96046448E-05



Seqüência: 01111111111111111111111110111111111111111111110110


Melhor Indivíduo: x = -6.55651093E-05 y = 0.000131130219

Valor do Máximo: 1


Seqüência: 01111111111111111111101011000000000000000000010110






Seqüência: 10000000000010001100011100111111111111111001110001


Melhor Indivíduo: x = -0.00691413879 y = -0.065112114


43


Seqüência:01111111111111011011110000111111111101010101010100


Melhor Indivíduo: x = -0.0585496426 y = 0.0341773033



Seqüência: 01111111111011001101000011000000000001011001100110


Melhor Indivíduo: x = 2.44756937 y = 1.96464062



Seqüência:10000011001000100000010101000001010000011110001100





Seqüência:10000000000000111010011010111111111101100100110001


.-teste 1 (figura 24)

Melhor Indivíduo: x = -0.000125169754 y = 5.96046448E-06



Seqüência: 01111111111111111111010111000000000000000000000001


44

Melhor Indivíduo: x = -1.05759501 y = -2.95491219



Seqüência:01111110101001010111001010111110000110111101111000


Melhor Indivíduo: x = 8.34465027E-05 y = 5.96046448E-05



Seqüência:10000000000000000000011101000000000000000000001010


Melhor Indivíduo: x = -5.96046448E-05 y = 3.57627869E-05

Valor do Máximo: 1


Seqüência: 01111111111111111111101101000000000000000000000110


Melhor Indivíduo: x = -0.000125169754 y = 5.96046448E-06

Valor do Máximo: 1


Seqüência:01111111111111111111010111000000000000000000000001

45

3.3 CONSIDERAÇÕES SOBRE OS RESULTADOS OBTIDOS

Observa-se que no caso do ga1, nem sempre se pode encontrar o ponto máximo da

função apenas máximo locais. Quando foi usado o cruzamento de 2 pontos, a resposta foi

encontrada em todos os testes. A aplicação do elitismo garantiu a convergência mais rápida

em todos os casos.

Observando a tabela 1, que coloca a média de erro nos testes de cada caso,

observamos que nos casos sem elitismo o erro médio é maior dos que nos casos com

elitismo e que nos casos sem elitismo, entre os algoritmos sem elitismo o que teve o menor

erro médio foi o de cruzamento de dois pontos sem elitismo.

Ga1.f, Cruzamento 1 pt,

sem elitismo

ga2.f Cruzamento 1 pt,

com elitismo

ga3.f Cruzamento 2

pts, sem elitismo

ga4.f Cruzamento 2

pts, com elitismo

Erro Médio 0,005843008 0 0,0019348502 0 Quadro 3 – Erro médio do cruzamento


46

2 CONSIDERAÇÕES FINAIS

Os testes realizados nos códigos dos Algoritmos genéticos envolvidos no trabalho

apresentaram o refinamento da melhor desempenho entre os casos dos operadores

genéticos aplicados. Dentre os casos analisados, o cruzamento de dois pontos foi o que

apresentou melhor desempenho, pois em todos os testes realizados com este caso,

encontrou-se o ponto máximo da função, de acordo com as Figuras 19 a 28.

Observou-se também que a utilização do Elitismo aumenta a velocidade de

convergência do algoritmo para encontrar o ponto máximo da função, otimizando o fator

tempo, como ilustra as Figuras 24 a 28. Nota-se ganho na precisão da resposta.

A busca pelo conhecimento e do domínio dos processos envolvidos em sistemas, faz

com que o homem busque cada vez mais as melhores respostas ou soluções para cada

problema encontrado. Sua curiosidade e necessidade em dominar fazem que esse

processo fique perene e consiga modelar sistemas, implementá-los e dominar as

variáveis envolvidas, podendo assim suprir suas necessidades.

47

REFERÊNCIAS

ALMEIDA, Roberto A. Determinação do regime operacional de centrais Hidrelétricas

utilizando o algoritmo genético. Disponível em:

<www.unesco.org.uy/phi/libros/hidromecanica/Trab%203.doc>. Acesso em: 5 Mar. 2005.

AMABIS, José Mariano. MARTHO, Gilberto Rodrigues. Fundamentos da biologia

moderna. 2 ed. rev. São Paulo: Moderna, 1997. p.552-558.

CATARINA, Adair S et. al. Utilização de um algoritmo genético na otimização de lucro

de uma propriedade agrícola. Disponível em:

<http://www.ppg.uem.br/Docs/ctf/Agronomia/2002/44_035_02_Adair%20Catarina_Utilizacao

%20de%20um%20algoritmo.pdf>. Acesso em:25 Set. 2005.

CENTENO, J. A. S.; SCHMIT, M. A. R. Uso de algoritmos genéticos para classificação

de imagens de sensoriamento remoto. Disponível em: <http://geodesia.ufsc.br/Geodesia-

online/arquivo/GeoColoq_2001/cbcg2008.pdf>. Acesso em: 5 fev.2005.

FIALHO, Francisco Antônio Perreira et al. Algoritmo Genético – fundamentação.

Disponível em:< http://www.geocities.com/Athens/Sparta/1350/ia/a_genetic.html>. Acesso

em 25 mar. 2005.

GUERVÓS, Juan J. M. Informática Evolutiva: algoritmos genéticos. Disponível em:

<http://geneura.ugr.es/~jmerelo/ie/ags.htm>. Acesso em: 5 mar. 2005.

48

LUCAS, Diogo C. Algoritmos Genéticos: um estudo de seus conceitos fundamentais e

aplicação no problema de grade horária. Disponível em:

<http://www.ufpel.tche.br/prg/sisbi/bibct/acervo/info/2000/Mono-Diogo.pdf> Acesso: 6 mar.

2005.

LUCAS, Diogo C. Algoritmos Genéticos: uma introdução. Disponível em: <

http://www.inf.ufrgs.br/~alvares/INF01048IA/MaterialProva2/ApostilaAlgoritmosGeneticos.pdf

Acesso: 6 mar. 2005.

MANOEL, Hermelindo Pinheiro. Cruzamento e Mutação Disponível em: <.

http://www.cidase.com/webizu/professor/ga/cromu.html>. Acesso em: 29 set. 2005.

MIRANDA, Marcio Nunes de. Algoritmos Genéticos: fundamentos e aplicações. Rio de

Janeiro. Disponível em: < http://www.gta.ufrj.br/~marcio/genetic.html>.Acesso em: 11

jun.2005.

PACHECO, Marco A. C. Algoritmos Genéticos: princípios e aplicações. Disponível em:

<http://www.ica.ele.puc-rio.br>.Acesso em: 8 jul. 2005.

SOARES, José Luís. Biologia: volume único. São Paulo: Scipione, 1997. p.280-282.

UNIVERSIDADE FEDERAL DO PARÁ. Laboratório de Análise Numérica em

Eletromagnetismo. Fortran 77, 2005.

Documents

ESTUDOS DOS ALGORITMOS GENÉTICOS USANDO TÉCNICAS COMPUTACIONAIS