Embed Size (px)
Citation preview
CENTRO UNIVERSITÁRIO DO MARANHÃO – UNICEUMA PRÓ-REITORIA ACADÊMICA
COORDENAÇÃO DO CURSO DE SISTEMAS DE INFORMAÇÃO
MATHEUS SOUSA OLIVEIRA
UM ESTUDO SOBRE ALGORITMOS GENÉTICOS
São Luís2007
MATHEUS SOUSA OLIVEIRA
UM ESTUDO SOBRE ALGORITMOS GENÉTICOS
Monografia apresentada ao curso de Sistema de Informação do Centro Universitário do Maranhão - UniCeuma, para obtenção do grau de Bacharel em Sistema de Informação.
Orientador: Prof. Marcelo Mendonça
São Luís2007
1
MATHEUS SOUSA OLIVEIRA
UM ESTUDO SOBRE ALGORITMOS GENÉTICOS
Monografia apresentada ao curso de Sistema de Informação do Centro Universitário do Maranhão - UniCeuma, para obtenção do grau de Bacharel em Sistema de Informação.
Aprovada em / /
BANCA EXAMINADORA
___________________________________________Prof. Marcelo Nunes Mendonça (Orientador)
___________________________________________1º Examinador
___________________________________________2º Examinador
2
Aos meus pais Mardônio e Maria das Graças, minha irmã Mychelle, minha prima Larisse e a minha namorada Rayllany.
3
AGRADECIMENTOS
Em especial aos meus pais Maria das Graças e Mardônio pela dedicação,
apoio e incentivo que me deram desde a hora em que me colocaram no mundo.
A minha irmã Mychelle, pela preocupação e palavras de apoio que me deu
ao decorrer da elaboração deste trabalho.
A minha namorada Rayllany, pelas palavras carinhosas e de apoio nas
horas mais precisas.
Ao amigo e orientador Marcelo Mendonça que me guia desde os meus
primeiros passos na área não somente em meio acadêmico, mas socialmente
também.
A todos os colegas de curso onde nos apoiamos uns nos outros para
vencermos mais esta barreira dentre os quatro longos anos letivos em que
convivemos, nas horas boas e nas horas difíceis.
Não menos importante, a todos que ajudaram diretamente e
indiretamente, pelo incentivo, compreensão e apoio nos momentos mais difíceis no
decorrer deste trabalho.
4
“Existe uma coisa que uma longa existência me ensinou: toda a nossa ciência, comparada à realidade, é primitiva e inocente; e portanto, é o que temos de mais valioso”.
Albert Einstein
5
RESUMO
Abordagem sobre Algoritmos Genéticos. Ressalta-se sua origem, sua forma de
organização e elaboração, bem como suas aplicabilidades. Fala-se também um
pouco sobre a biologia, pois foi a partir dela que originou a idéia para criação dos
algoritmos genéticos, mais precisamente a partir da Lei da Evolução das Espécies,
criada por Charles Darwin. Tem-se ainda a utilização de alguns de seus termos em
analogia aos da informática, pela similaridade com a área biológica; seu
funcionamento tenta produzir os mesmos processos encontrados na natureza como:
Seleção, Cruzamento (Crossover), Mutação, etc. Os GAs são algoritmos de
otimização onde seu objetivo é otimizar problemas tentando tornar sua resolução
mais ideal possível. Através de suas aplicabilidades, os algoritmos genéticos
mostram com eficiência seu potencial e poderio, atuando os mesmos em diversas
áreas do conhecimento. Por tal motivo, este trabalho procura apresentar de forma
superficial algumas delas.
Palavras-chave: Algoritmos Genéticos. GAs. Bioinformática. Inteligência Artificial.
Algoritmos Genéticos Simples.
6
ABSTRACT
Approach about genetic algorithms. Stand out in its origin, its form of collation and
elaboration, just like its applicabilities. It talks too a little about the biology, cause it
was from it the original idea to the genetic algorithms, more precisely from the
evolutionary theory, created by Charles Darwin. It has too the utilisation of some of
his terms in analogy to the informatics ones, by the similarity with the biologic area;
its functioning try produce the same processes found in nature, like: Selection,
Crossover, Mutation, et cetera. The GAs are optimization algorithms whose goal is to
optimize problems trying to make their resolution the more ideal possible. Through its
applicabilities, the genetic algorithms show with efficiency their potencial and power,
acting in many knowledge areas. For such motive, this work try to present some of
them in a superficial way.
Keywords: Genetic algorithms. GAs. Bioinformatics. Artificial intelligence. Simple
Genetic Algorithms.
7
LISTA DE FIGURAS
Figura 1 - Estrutura representativa do DNA de dupla fita......................................18
Figura 2 - Representação do Dogma Central........................................................20
Figura 3 - Pseudo-Código do comportamento padrão dos algoritmos
evolucionários........................................................................................................24
Figura 4 - Diagrama representativo dos algoritmos evolucionário como técnica de
busca.....................................................................................................................25
Figura 5 - Função Hipotética com um máximo local e outro global.......................26
Figura 6 - Exemplo de pontos de corte..................................................................38
Figura 7 - Representação do processo de cruzamento de um ponto....................39
Figura 8 - Representação de cruzamento de dois pontos.....................................40
Figura 9 - Representação de cruzamento uniforme..............................................40
Figura 10 - Exemplo ilustrativo de mutação..........................................................42
Figura 11 - Descrição da operação do operador de crossover de um ponto e
mutação.................................................................................................................42
8
LISTA DE TABELAS
Tabela 1 - Faz uma comparação entre os termos utilizados em linguagem
natura (na biologia) com a utilizada no GA............................................................30
Tabela 2 - Esboço do algoritmo genético em forma de etapas.............................31
Tabela 3 - Exemplo de como ocorre o processo de seleção atentando para não
cair no efeito de convergência genética................................................................37
Tabela 4 - Contem a área cientifica assinalando com a utilização do GA.............44
9
LISTA DE SIGLAS
GA Algoritmos Genéticos
GAs Algoritmos Genéticos Simples
DNA Sigla em inglês para o "ácido desoxirribonucléico"
RNA Sigla em inglês para o "ácido ribonucléico"
API Interface de Programação de Aplicativos
NP É o acrônimo em inglês para Tempo polinomial não determinístico
10
SUMÁRIO
LISTA DE FIGURAS..........................................................................................8
LISTA DE TABELAS.........................................................................................9
LISTA DE SIGLAS.............................................................................................10
1 INTRODUÇÃO...................................................................................................12
2 BIOLOGIA BÁSICA...........................................................................................15
2.1 Teoria da Evolução..........................................................................................15
2.2 Genética Básica..............................................................................................17
2.3 Historia dos Algoritmos Genéticos...................................................................20
3 CONCEITOS BÁSICOS EM GÁS......................................................................23
3.1 Entendendo Algoritmos evolucionários...........................................................23
3.2 O que são algoritmos genéticos?....................................................................26
3.3 Entendendo as terminologias para GÁS.........................................................28
4 ENTENDENDO UM GA SIMPLES.....................................................................31
4.1 Como escolher parâmetros do GA..................................................................32
4.2 Representação de um cromossomo................................................................33
4.3 Inicialização Cromossomial.............................................................................34
4.4 Função Para Cálculo da Aptidão.....................................................................35
4.5 Seleção............................................................................................................36
4.6Cruzamento ("Crossover")................................................................................37
4.7 Mutação...........................................................................................................41
5 APLICABILIDADES...........................................................................................43
6 CONSIDERAÇÕES FINAIS...............................................................................46
REFERÊNCIAS.................................................................................................48
11
1 INTRODUÇÃO
Desde a Pré-História o homem vem buscando e adquirindo conhecimento
com o intuito de facilitar seus afazeres do dia a dia, como uma das suas primeiras
descobertas veio a utilização do fogo no preparo de seus alimentos, onde com uma
pedra afiada teve a idéia de cortá-los, não precisando mais fazê-lo com os dentes. A
partir daí, as idéias forma evoluindo cada vez mais. O homem passou a interagir mais
com a natureza que o cercava, ao observá-la, teve várias idéias e também o
aperfeiçoamento de outras, como por exemplo, podemos citar que ao analisar o modo
de voar de algumas aves onde as mesma utilizam correntes de ar quente para
planarem veio à criação da asa delta e assim sucessivamente várias outras idéias
surgiram, ou seja, ao analisar a natureza o homem pode criar novas tecnologias
baseando-se na mesma.
Várias décadas se passaram e, junto com a evolução, surgiram também
problemas, tais problemas ganharam uma complexidade cada vez maior com o
decorrer dos tempos, consequentemente, o homem cada vez mais desenvolvia seu
intelecto ao tentar solucioná-los.
A partir da criação do computador, foram desenvolvidas várias tecnologias,
uma delas foi o algoritmo, que consiste em uma seqüência finita e não ambígua de
instruções computáveis para solucionar um problema.
Temos como objetivo, fazer uma abordagem acerca da ramificação,
denominada algoritmos genéticos, onde os mesmos constituem uma parte da
computação evolutiva, a qual está rapidamente crescendo como uma subdivisão da
Inteligência Artificial.
Para tal finalidade, apoiamo-nos em alguns trabalhos de estudiosos da área,
procurando de forma simples alcançar nosso objetivo. Para tanto, procuramos utilizar
uma linguagem clara e de fácil compreensão, pois esta foi uma preocupação que
tivemos ao analisarmos alguns destes trabalhos, inicialmente tivemos algumas
dificuldades em seu entendimento dado à linguagem que alguns pesquisadores
utilizavam.
12
O presente trabalho se justifica pela necessidade de estimular reflexões e
debates sobre a importância do assunto hora abordado, tendo em vista que trata-se de
um assunto relativamente novo e pouco conhecido. O mesmo apresenta como
conteúdo uma abordagem quanto ao surgimento dos algoritmos genéticos e um pouco
sobre a biologia, pois são utilizados termos análogos quando nos referenciamos aos
algoritmos genéticos e a genética, também encontraremos conceitos básicos, algumas
aplicabilidades e etc., levando assim, a um melhor entendimento sobre o assunto.
Sua estrutura está composta da seguinte maneira: o primeiro capítulo
corresponde à Introdução, na qual se delimita o problema, justifica a realização da
pesquisa e expõe os seus objetivos e metodologia do estudo, bem como suas
justificativas. No segundo capítulo, discorre-se sobre uma breve introdução a biologia,
dando ênfase maior à Teoria da Evolução e Genética Básica isso se origina da
similaridade que existe entre os algoritmos genéticos e os mesmo, também falamos
sobre a historia dos GA, buscando não só contextualizar sua origem, mas através da
mesma analisar e com isso entenderemos a idéia de sua criação. No terceiro, examina-
se seus conceitos básicos, bem como o entendimento dos algoritmos evolucionários e
também suprir com conhecimento a indagação sobre o que é um algoritmo genético e
suas terminologias. No quarto capítulo, falaremos sobre a importância da escolha dos
parâmetros do GA, dando dicas para o mesmo, pois dependerá diretamente dela os
resultados que serão obtidos na resolução dos problemas, falaremos um pouco sobre
as representações cromossomiais com a finalidade de aumentar o nosso
conhecimento, não ficando apenas na representação binária, pois é a mais utilizada na
maioria dos trabalhos pesquisados, também entenderemos como ocorre o processo do
funcionamento de um GA simples através dos métodos: Inicialização cromossomial,
função para o calculo da aptidão, seleção, etc. No quinto capítulo, apresentaremos
algumas aplicabilidades citando as áreas e as aplicações nas mesmas e algumas
ferramentas comercias que utilizam algoritmos genéticos. Finalmente, nas
considerações finais, faz-se uma reflexão sobre tudo até agora falado, exaltando a
importância da utilização dos algoritmos genéticos e como o mesmo podem ajudar na
elucidação de problemas que para algoritmos normais possa ser demasiadamente lento
e trabalhoso.
13
Esperamos, pois, que este trabalho venha contribuir para fundamentar
estudos posteriores, uma vez que este é apenas introdutório na área dos algoritmos
genéticos. Embora, não temos a pretensão de esgotar o assunto, pois o mesmo é vasto
e de graus de complexidade variados. Que o mesmo seja um ponto de partida para
aguçar a sede de conhecimento sobre o tema objeto deste trabalho monográfico.
14
2 BIOLOGIA BÁSICA
Tentando buscar um melhor entendimento acerca do assunto abordado,
resolvemos escrever este capitulo com a intenção de explicar as origens dos GAs,
como surgiram, a partir de que seus criadores tiveram a idéia de criá-los (não menos
importante) para termos uma idéia de como ocorre seu funcionamento através da
biologia.
2.1 Teoria da Evolução
Os algoritmos genéticos foram criados baseados na teoria da evolução, então
podemos começar citando o Big-Bang, pois segundo alguns autores, foi a partir dele
deu-se o inicio de tudo.
Foi à teoria que revolucionou o modo de pensar na biologia, tendo como seu
criador Charles Darwin um naturalista, que mais adiante vai ser considerado o pai da
evolução onde em sua teoria afirmava que os seres vivos evoluíram de um ancestral
comum, tendo herdado pequenas modificações, que poderiam ou não se propagar,
através de seleção natural.
O homem é um produto da evolução, sendo assim, muitos dos problemas
relacionados a ele podem ser entendidos apenas quando o homem é considerado
como um organismo evoluído e em evolução. O conhecimento profundo dos princípios
e mecanismos da evolução é, portanto, um pré-requisito para entender o homem
(MAYR apud MARQUES, 1977 Disponível: <http://www.brasilescola.com/biologia/teoria-
da-evolucao.htm>).
Para Darwin mutações seriam variações genéticas que provavelmente são
produzidas sucedendo outras visando um aperfeiçoamento das mesmas. Efetivamente
ele considera que a chave da origem de todas as raças atuais são frutos da seleção
natural e acumulação sendo exercidas nas diversas variações sucessivas fornecidas
pela natureza.
Os cientistas mais conceituados até o século XIX acreditavam ao menos em
uma das teorias do criacionismo (“Deus criou o universo da forma que ele é hoje”
15
LINDEN, 2006, p. 24) também da geração espontânea (“a vida surge de essências
presentes no ar” LINDEN, 2006, p. 24). Darwin em varias de suas viagens visitou vários
lugares e sua grande habilidade em observar a natureza permitiu-lhe perceber que
animais de uma espécie eram ligeiramente diferentes que seus parentes em outros
ecossistemas, sendo os mesmos mais adaptáveis as necessidades e oportunidades
encontradas em seu ecossistema específico. Ao fazer um levantamento de vários
dados e a análise dos mesmos, Darwin chegou a uma conclusão de suas dúvidas
assim criando a teoria da evolução das Espécies, dando assim, origem a sua grande
obra em 1859, chamada de “A Origem das Espécies”. Por ser uma idéia inovadora para
a época, seu livro foi amplamente combatido, mas atualmente é aceito por praticamente
toda a comunidade acadêmica mundial.
Na natureza dentro de um mesmo ecossistema todos os indivíduos
competem entre si por recursos limitados, isso é o que diz a teoria da evolução, como
exemplo podemos citar água e comida por serem mais vitais para a manutenção do
organismo. Os indivíduos (animais, vegetais, insetos, etc.) dentro de uma mesma
espécie que não obtém êxito têm a tendência de ter uma prole menor, levando assim a
uma pequena probabilidade de terem seus genes propagados ao longo de sucessivas
gerações, este processo conhecemos por seleção natural.
Os indivíduos que se perpetuam com suas sucessivas combinações de suas
características podem produzir um novo indivíduo bem mais adaptado as necessidades
que o seu meio ambiente o proporciona, ao mesclar essas características positivas de
cada um dos reprodutores, este individuo tem chances maiores de sobrevivência em
relação aos outros. Este processo da se a várias combinações de indivíduos sendo as
mesmas variações de seus pais. Sendo assim, o individuo descendente é ligeiramente
diferente do seu progenitor, podendo esta diferença ser positiva ou negativa conforme
preceitua LINDEN:
[...] um elefante só pode nascer do ventre de outro elefante. A pergunta razoável que se pode levantar é: de onde surgiu o primeiro elefante? De uma outra coisa parecida com, mas não muito diferente de, um elefante, ou seja, um outro animal parecido com o elefante como nós conhecemos atualmente (LINDEN, 2006, p. 25).
16
Com isso, podemos deduzir que nossas características são passadas de
geração pra geração.
A evolução natural não é um processo dirigido, com o objetivo de levar um
melhoramento ideal das espécies. Na verdade, não podemos afirmar que descendentes
de pais muito bem adaptados herdem todas as suas características sendo assim
indivíduos idênticos. Pais fortes podem produzir filhos com doenças terríveis ou
fraquezas inerentes. Sendo assim, é um mecanismo que leva a conseqüências naturais
de transmissão de informação.
A evolução é um processo onde os seres vivos são alterados por um conjunto
de modificações que herdam de com as passagens de gerações, podendo sendo
explicadas por fatores como mutação gênica, recombinação gênica, seleção natural e
isolamento. Para Darwin na época por não dispor de todas essas informações não pode
obter um melhor aproveitamento de suas pesquisas, mas graças a ele outros poderão
continuá-la.
2.2 Genética Básica
Darwin afirmar que a evolução e a seleção natural das espécies faziam com
que as mesmas fossem se adaptando naturalmente de acordo com o seu ecossistema,
por falta de mais informação ele não sabia quais eram os mecanismos básicos através
dos quais essas adaptações aconteciam, pois o processo de transmissão de
informação genética ainda era desconhecido. No inicio do século XX, Gregor Johann
Mendel que era um monge agostiniano, botânico e meteorologista austríaco,
compreendeu que o processo de transmissão de características positivas, estava
associado a uma unidade básica de informação, conhecida por gene através de
pesquisas.
Durante muito tempo, mais ou menos quase um século foi necessário para a
conclusão do processo que levou à descoberta de como estas características eram
fisicamente armazenadas dentro da célula. O bioquímico Friedtich Mieschner em 1869,
concluiu que os núcleos celulares possuíam varias substancias especificas, podendo
ser separadas em duas categorias principais: proteínas e moléculas acidas. Ate aquele
17
momento estas informações eram desconhecidas, elas foram denominadas de “ácidos
nucléicos”.
Na Rússia em 1909, um químico natural conhecido por Phoebus A. T.
Levene, em suas pesquisas identificou a ribose como açúcar de um dos dois tipos de
ácidos nucléicos, o acido ribonucléico, e certos componentes do outro acido nucléico, o
acido desoxirribonucléico este ultimo foi descoberto em 1929. Ele também identificou
corretamente a estrutura básica do DNA que continha adenina, guanina, timina,
citosina, desoxirribose, e um grupo fosfato, ou seja, fosfato-açucar-base. Na época era
praticamente um consenso o fato de que as proteínas eram a base do processo de
armazenamento de informação genética.
Fredrick Griffith e Oswald T. Avery dois bacteriologiastas fizeram a correção
desta suposição, onde após exaustivas pesquisas chegaram a conclusão de que a
molécula que armazenava as informações relativas a hereditariedade era o DNA, e não
as proteínas ou o RNA. No entanto, naquela época não se entendia como o processo
funcionava, o que só ficou claramente entendido após descobertas feitas por Francis
Crick e James Watson em seus trabalhos, onde os mesmos desenvolveram a dupla
hélice do DNA e a forma como os ácidos nucléicos interagiam dentro desta molécula.
Atualmente, com as descobertas da estrutura do DNA por Crick e Watson podemos
observar o funcionamento do mesmo, como unidade básica de armazenamento e
transmissão de informação genética, onde concluímos o entendimento deste processo
ao saber como funciona em nível molecular. A da Figura 1 mostra a estrutura do DNA.
Figura 1 - Estrutura representativa do DNA de dupla fita (TICONA, 2003, p. 8).
18
Todos os indivíduos seja ele animal, vegetal ou até mesmo organismos
inferiores como vírus e bactérias, basicamente são formados por uma ou mais células,
onde dentro de cada uma delas o organismo possui uma copia completa do conjunto de
um ou mais cromossomos que descrevem o organismo, este conjunto é denominado
genoma.
O cromossomo é composto por pares, sendo que o numero de pares (n) varia
de espécie para espécie. Nós seres humanos possuímos 23 pares de cromossomos
por célula, mas não somos os portadores do maior numero de pares da natureza, os
burros, por exemplo, tem 31 pares de cromossomos e as carpas, 52. Um cromossomo
é composto por genes, onde os mesmos são blocos de seqüência de DNA, sendo
assim, cada gene é uma região do DNA tendo uma posição especifica no cromossomo,
esta é chamada de lócus, e controla uma característica hereditária especifica, como
por exemplo: cor do cabelo, altura, cor dos olhos dentre tantas outras que podemos
citar, ou seja, características estas que nos torna o que somos. Geralmente a
seqüência das bases que compõe o gene corresponde a uma ou mais proteínas ou
RNA complementar.
Proteínas são a base do funcionamento das células, sendo estas compostas
por cadeias de aminoácidos e responsáveis praticamente por todo o trabalho realizado
nas células. Dentre os vários tipos de proteínas podemos destacar as enzimas a
hemoglobina, certos hormônios e o colágeno dos ossos, tendões e pele, tendo funções
fundamentais para a sobrevivência. Nelas podemos encontrar as mais diversificadas
funções, incluindo entre outras coisas, a regulação da contração muscular, produção de
anticorpos expansão e contração dos vasos sanguíneos para manter a pressão normal
etc.
Portanto definimos o DNA como grande armazenador de informações
genéticas de um organismo, e as proteínas tendo o papel de verdadeiras trabalhadoras
celulares. O DNA e as proteínas têm uma relação pelo dogma central da biologia.
Afirmando que uma seqüência de DNA, que contem toda a informação necessária para
se auto-replicar, é transcrita em RNA e esta por sua vez é traduzida para uma proteína.
A representação do Dogma Central está representada pela Figura 2.
19
Figura 2 - Representação do Dogma Central (TICONA, 2003, p. 9).
2.3 História dos Algoritmos Genéticos
A descoberta dos algoritmos genéticos deu se na década de 40, quando os
cientistas ao observar a natureza se inspiraram no seu processo tentando assim imita-
lo criando assim o ramo da inteligência artificial. A pesquisa desenvolveu-se mais no
ramo cognitivo e na compreensão dos processos de raciocínios e aprendizado até o
final da década de 50, quando deu inicio a busca de modelos de sistemas genéricos
que gerassem soluções candidatas para resolução de problemas muito complexos
sendo assim de difícil resolução computacional.
Foi em 1957 que foram feitas as primeiras tentativas de se associar a
evolução natural a problemas de otimização, o mesmo foi apresentado por Box em seu
esquema de operações evolucionarias. Seu método era perturbar de forma sistêmica
duas ou três variáveis de controle de uma instalação, onde de forma semelhante
podemos comparar a atualmente com operadores de mutação e seleção. Com o passar
do tempo vários pesquisadores também desenvolveram suas pesquisas, na década de
1960 dois pesquisadores tiveram grande êxito ao começarem a trabalhar com genes,
Bledsoe e Bremmerman usaram tanto a representação binária quanto a inteira e a real,
desenvolvendo os precursores dos operadores de recombinação (crossover).
É chegada a primeira metade da década de 60, I. Rechenberg fez a primeira
tentativa na utilização de processos evolutivos para resolver problemas de desenhos
aerodinâmicos de asas, onde através de suas pesquisas ele desenvolveu as
estratégias evolucionárias (evolution strategies). Onde mantinha uma população de dois
20
indivíduos com cromossomos compostos de números reais em cada instante, onde um
dos dois era filho do outro, onde era gerado através da aplicação exclusiva do operador
de mutação. Rochenberg descreve que o processo tinha ampla fundamentação teórica,
pois a mutação era aplicada a partir de uma distribuição gaussiana dos parâmetros e foi
utilizado com sucesso em vários problemas práticos. As pesquisas de Rochenberg
atualmente não são amplamente aceitas, tais como populações maiores e operador de
crossover, mas seu trabalho pode ser considerado pioneiro, por ter introduzido a
computação evolucionaria as aplicações práticas.
Trabalhos posteriores as estratégias evolucionarias conseguiram de forma
efetiva suprir estas falhas, onde foram feitas inclusões de conceitos de população e
operador de crossover. De maneira interessante ao aplicar a este operador onde ao
incluir a idéia de utilizar a media como operador alem de poder envolver muitos pais,
idéias estas de grande importância pois as mesmas podem ser utilizadas em algoritmos
genéticos quando usamos cromossomos com uma representação contínua. Entretanto,
mesmo não sendo o primeiro investigador da área, aquele que seria considerado o pai
dos algoritmos genéticos só foi finalmente descoberto no final da década de 60, quando
John Holland desenvolve os Algoritmos Genéticos, embora concentrado
eminentemente na codificação discreta. Holland ao estudar formalmente a evolução das
espécies propôs uma hipótese de modelo computacional que ao ser implementado
poderia oferecer boas soluções para problemas extremamente difíceis que eram
insolúveis computacionalmente ate aquela época. Foi em 1975 que Holland publicou
sua obra, “Adaptation in Natural and Artificial Systems”, no qual aborda um estudo
sobre os processos evolutivos, ao invés de projetar novos algoritmos, como a maioria
cogita. Seu trabalho apresenta os algoritmos genéticos como uma metáfora para os
processos evolutivos, de forma que ele estudasse a adaptação e a evolução no mundo
real e assim simular dentro de computadores. Mas, os algoritmos genéticos acabaram
por ampliar consideravelmente seu papel originalmente imaginado por Holland e
transformaram-se em uma poderosa ferramenta onde se é utilizada de forma
disseminada por cientistas da computação.
Podemos citar um fato interessante no trabalho de Holland e sua influência na
área de GA, onde ele utilizou originalmente cromossomos binários, cujos genes eram
21
apenas zeros e uns. Pesquisadores da área acabaram por abolir esta limitação, mesmo
assim vários cientistas ainda sim insistem em utilizar a representação binária, mesmo
existindo outras que podem se mostrar muito mais eficientes na resolução do problema
em questão.
A partir de então os algoritmos genéticos começaram a se expandir por toda
a comunidade científica, com a sua utilização puderam resolver problemas
extremamente importantes que talvez não fossem abordados de outra maneira. Como
bem assevera LINDEN:
É bem provável que alguém inventasse outra maneira de resolve-los, mas talvez esta não fosse tão eficiente e/ou interessante quanto os algoritmos genéticos. (LINDEN, 2006, p. 33)
Desta forma, com seu desenvolvimento veio também a utilização para fins
comerciais onde nos anos 80 surgiu pacotes comerciais utilizando algoritmos genéticos.
Evolver é considerado o primeiro pacote comercial por vários artigos, que já estava
disponível desde 1988 e que incluía um programa adicional para o Excel e uma API
(Interface de Programação de Aplicativos) para o desenvolvimento de programas que
acessassem dados provenientes de diferentes aplicativos. Atualmente podemos
encontrar vários aplicativos que tem as mesmas características.
Com isso vieram as primeiras conferências cientificas dedicadas
exclusivamente a estes tópicos na década de 80, ocasionado pelo progresso dos
algoritmos evolucionários e sua popularização no meio cientifico. Atualmente os
algoritmos genéticos obtiveram benefícios muito da interdisciplinaridade, pois cada vez
mais cientistas da computação buscam idéias em outras áreas de pesquisa para
compor suas inspirações de forma ao absorverem suas idéias possam fazer com que
os GAs sejam mais eficientes e inteligentes na resolução de problemáticas.
22
3 CONCEITOS BÁSICOS EM GAs
Neste capítulo tentaremos explicar de forma sucinta os conceitos associados
aos algoritmos genéticos, de onde vem à inspiração para seu desenvolvimento e uma
representação de como são desenvolvidos. Apresentaremos vários conceitos básicos,
mas de grande importância para um melhor entendimento a cerca do tema abordado no
presente trabalho onde facilitaram melhor a compreensão dos demais capítulos que
virão a seguir.
3.1 Entendendo Algoritmos evolucionários
Estes vieram com a finalidade de resolver problemas com respeito à evolução
genética para o estudo e a análise de diversos indivíduos de diversas populações que
associadas aos genes em um cromossomo assumindo valores correspondentes aos
alelos. Os Algoritmos evolucionários através de modelos computacionais dos processos
naturais de evolução resolvem problemas utilizando estes processos como uma
ferramenta. Mesmo existindo vários modelos computacionais propostos, todos eles
utilizam o conceito de simulação da evolução das espécies através de seleção,
mutação e reprodução existindo assim algo em comum entre os mesmos, estes
processos dependem do “desempenho” dos indivíduos desta espécie dentro do
“ambiente”.
Operadores genéticos em sua essência tentam reproduzir fenômenos vistos
na natureza computacionalmente, como a reprodução sexuada, a mutação genética e
qualquer outro que a mente de um programador possa reproduzir.
Através do pseudo-código encontrado em fontes de pesquisa (Figura 3)
podemos mostrar de forma resumida e não muito detalhada o comportamento padrão
dos algoritmos evolucionários:
23
T:=0 // Inicializamos o contador de tempoInicializada_Populacao P(0) // Inicializamos a população aleatoriamenteEnquanto não terminar faça // condição de termino: por tempo, por avaliação, etc.
Avalie_População P(t) // Avalie a população neste instanteP’:=Selecione_Pais P(t) // Selecionamos sub-população que gerará nova
geração P’:=Recombinação_e_mutação P’ // Aplicamos os operadores genéticosAvalie_População P’ // Avalie esta nova populaçãoP(t+1)=Selecione_sobreviventes P(t), P’ // Selecione sobreviventes desta geraçãoT:=t+1 // Incrementamos o contador de tempo
Fim enquantoFigura 3 – Pseudo-Código do comportamento padrão dos algoritmos evolucionários (LINDEN, 2006, p. 38)
Podemos entender o funcionamento básico dos algoritmos evolucionários no
algoritmo acima (Figura 3) onde consiste em buscar dentro da atual população aquelas
soluções que possuem as melhores características (função Selecione_Pais) e tentar
combiná-las de forma a gerar soluções ainda melhores (função
Recombinação_e_mutação), sendo assim repete-se o processo até que tenha se
passado tempo suficiente ou que tenha-se obtido uma solução satisfatória para nosso
problema.
Em cada repetição do loop principal (Figura 3, o “enquanto“ em negrito)
podemos denominar como uma geração do algoritmo. Como já foi citado acima que os
algoritmos evolucionários imitam de certa forma os processos da natureza, este
conceito é semelhante ao conceito de geração existente na vida real, mas com a
exceção de que muitas vezes nos algoritmos evolucionários duas gerações não
convivem, como veremos adiante ao estudar o primeiro tipo de algoritmo genético.
Podemos perceber ao analisar o pseudo-código (Figura 3) que os algoritmos
evolucionários são exatamente dependentes de fatores probabilísticos, tanto na fase de
inicialização da população quanto na fase de evolução (associe principalmente ao
processo de seleção dos pais). Sendo assim os seus resultados são dificilmente
reprodutíveis, tornando assim um caso raro destes resultados serem perfeitamente
iguais. Contudo mesmo o nome algoritmos evolucionários indicar o contrario, são
heurísticas “Heurística são algoritmos polinomiais que não têm garantia nenhuma
sobre a qualidade da solução encontrada, mas que usualmente tendem a encontrar a
24
solução ótima ou ficar bem próximos dela.” (LINDEN, 2006, p. 38) sendo assim, não
asseguram que seus resultados obterão uma resolução ideal em todas as suas
execuções.
Sendo assim podemos deduzir que se você tem um algoritmo com o tempo
de execução curto o suficiente para a solução de um problema, não haverá a
necessidade da utilização de um algoritmo evolucionário. Uma melhor aplicabilidade
para um algoritmo evolucionário que descobrimos em nossas pesquisas, seria quando
na resolução de um problema um algoritmo for demasiadamente lento, como em
problemas NP-completos, que “[...] é o subconjunto dos problemas de decisão em
NP[...]“ (WIKIPÉDIA, 2007, Disponível: http://pt.wikipedia.org/wiki/NP-completo) ou
incapaz de achar uma solução como em problemas de maximização de funções multi-
modais, então ai entraria os algoritmos evolucionários.
Vários termos foram citados até agora, as vezes até de difícil compreensão,
mas os algoritmos evolucionários são de simples implementação.
Vamos agora tentar entender melhor como os algoritmos evolucionários se
posicionam como técnicas de busca através de um esquema apresentado na Figura 4.
Existe um ramo de busca chamado de “Técnicas Aleatórias-Guiadas” onde os
algoritmos evolucionários fazem parte, isto é, eles tem componentes aleatórios, mas
utilizam informações do estado corrente para guiar a pesquisa, tendo assim uma
diferença de métodos puramente aleatórios como a técnica de Random Walk. Ao
analisar a figura podemos entender como os algoritmos evolucionários se dividem em
vários tipos distintos (marcados em cinza).
25
Figura 4 - Diagrama representativo dos algoritmos evolucionário como técnica de busca (LINDEN, 2006, p. 39).
3.2 O que são algoritmos genéticos?
GA ou Algoritmo Genético é o ramo dos algoritmos evolucionários e como tal
são definidos como uma técnica de busca baseada numa metáfora do processo
biológico de evolução natural.
Pelo fato de os algoritmos genéticos nem sempre encontrarem a solução
ideal e que dificilmente conseguiram repetir o mesmo resultado consideramos os
mesmo como técnicas heurísticas de otimização global. Esta questão que diz respeito a
otimização global opõe aos métodos como gradiente (hill climbing), que tem como
objetivo encontrar o maximo de uma função ficando facilmente retidos em máximos
locais, entenderemos melhor ao visualizar a Figura 5, onde o método de hill climb uma
técnica gradiente se inicia em qualquer um dos pontos de inicio marcados seguirá o
gradiente, ou seja, direção de maior crescimento e acabará presa no ponto maximo
local onde a derivada é 0. Os algoritmos genéticos não tem dependência forte dos
valores inicias como no citado a pouco.
26
Figura 5 - Função Hipotética com um máximo local e outro global (LINDEN, 2006, p. 40).
Anteriormente vimos que o método de hill climbing é diferente dos GAs pois
os algoritmos genéticos não ficam estagnados simplesmente pelo fato de terem
encontrado um máximo local. Na verdade quando nos referimos a este ponto, os GAs
se parecem com a evolução natural, pois ao encontrar um individuo que é
instantaneamente o melhor de um certo grupo ele não para de “procurar” outros
indivíduos ainda melhores. Isto também ocorre na evolução natural ao existirem
circunstancias que mudam de um momento para outro, como organismos que se
encontram em um determinado ambiente ao se depararem com um desequilíbrio os
mais fortes sobreviverão, ou seja, se adaptarão as diversidades, podemos citar o vírus
da gripe como um exemplo real disto.
Para os algoritmos genéticos o ambiente geralmente é um só. Mas temos que
ter cuidado ao fazer qualquer afirmação, pois ao se passarem as gerações e os
operadores genéticos vão atuando, faz-se uma grande busca pelo espaço de soluções,
fazendo uma analogia entre os GAs e a Natureza, esta busca seria realizada pela
evolução natural se elas ficassem permanentemente em um ambiente imutável.
A evolução natural não é um processo dirigido à obtenção da solução ideal como
muitos costumam pensam. Na verdade o processo consiste na adaptação do melhor
individuo, pois ao competirem entre si só os mais fortes, ou melhor, os mais adaptáveis
se sobressaem e assim sobrevivem. Como os GAs tentam imitar a natureza os mesmo
por sua vez tem o mesmo comportamento que a evolução natural, posto que é “[...] a
27
competição entre os indivíduos é que determina as soluções obtidas.” (LINDEN, 2006,
p. 41). Sendo assim, os indivíduos mais adaptáveis prevalecerão, mas podem
acontecer casos em que a atual geração ser muito pior que a lhe antecedeu, sendo que
isto não é muito provável de acontecer logo não é muito comum este tipo de caso.
Novamente frisamos que GAs, apesar de seu nome implicar no contrário, não
constituem um algoritmo de busca da solução ideal de um problema, mas sim uma
heurística que encontra boas soluções a cada execução, mas não quer dizer que
encontrará a mesma todas às vezes, pois podem ser encontrado máximos ou mínimos
locais, próximos ou não do maximo global, nós atentamos a este detalhe pois o autor
em que baseamos nosso trabalho sempre nos alerta para este pequeno detalhe mas de
grande importância para o entendimento do algoritmo genético.
Um ponto crucial dentro dos algoritmos genéticos é a codificação da
informação em cromossomos, pois em conjunto com a função de avaliação torna-se o
fator predominante que liga o GA ao problema a ser resolvido. Sendo assim uma boa
codificação feita de forma inteligente já incluirá as idiossincrasias do problema, ou seja,
um bom levantamento a cerca do mesmo levando em conta todos os detalhes que
implicam a problemática (restrições sobre quando podemos ligar ou desligar um carro
etc.) sendo assim evitaremos testes de viabilidade de cada uma das soluções geradas.
A solução deve ser decodificada ao termino da execução do nosso algoritmo para
assim podermos utilizá-la na prática.
Nos GAs não diferente de como ocorre na natureza a informação deve ser
codificada dentro dos cromossomos ou genomas e a reprodução será a encarregada de
fazer com que a população evolua, lembrando que esta reprodução é baseada na
sexuada pois é a utilizada por todos os animais superiores garantindo assim uma
diversidade biológica, lembremos que a reprodução assexuada não cria diversidade,
visto que cada filho é idêntico ao pai sendo assim não nos interessará.
Iremos aplicar a reprodução e a mutação em indivíduos selecionados dentro
da nossa população. Devemos fazer a seleção de uma forma em que os indivíduos
mais aptos sejam selecionados frequentemente do que aqueles menos aptos, sendo
assim teremos um melhor aproveitamento, pois iremos colher as melhores
características levando a uma população de soluções bem mais selecionada e
28
preparada. Não é necessário os indivíduos menos aptos serem descartados da
população reprodutora, pois caso isso ocorresse causaria uma rápida convergência
genética de todas as soluções para um mesmo conjunto de características e com isso
nosso espaço de soluções iria ser reduzido consideravelmente. Em uma convergência
genética podemos dizer que temos uma baixa diversidade genética por possuir genes
similares, que não conseguem evoluir, a não ser pela ocorrência de mutações
aleatórias que sejam positivas. Isso nós leva a outro conceito interessante que é a
perda de diversidade onde o número de indivíduos que nunca são escolhidos pelo
método de seleção de pais “Quanto maior for a perda de diversidade, mais rápida será
a convergência genética de nosso GA.” (BLICKLE apud LINDEN, 1997, p. 43).
3.3 Entendendo as terminologias para GÁS
Para um melhor entendimento do assunto que o nosso trabalho aborda
decidimos escrever este capitulo com a finalidade de nos familiarizarmos com as
terminologias utilizadas na área dos algoritmos genéticos. Pela grande familiaridade
que os GAs tem com a genética e a teoria da evolução das espécies, pois foi de onde
surgiu a inspiração para sua criação, há uma grande analogia entre os termos da
biologia e os termos usados no campo dos Algoritmos Genéticos Simples.
Tomamos por base os sistemas naturais onde um ou mais cromossomos se
combinam formando assim as características genéticas básicas de um individuo. Ao
estudarmos GAs termos como cromossomos e individuo serão constantemente vistos
sendo os mesmos intercambiáveis. Em nossos estudos observamos que a
representação binária é muito utilizada em vários textos básicos da área, muitas vezes
pode-se escrever string (de bits) tendo o mesmo significado que cromossomo.
Os genes são formados por vários cromossomos, podendo ter um
determinado valor entre vários possíveis, estes chamados de alelos. Onde o locus
(plural: loci) é a posição do gene. Pela grande familiaridade os termos biológicos
também podem ser aplicados na área de GAs, mas podemos utilizar o termo
características para significar gene, valores para alelos e posição locus.
29
Termos como genoma, genótipo e fenótipo também são de grande
importância para nosso estudo. Onde genótipo é a estrutura do cromossomo, podemos
trocar o termo pela palavra estrutura dentro da área de GA. Podemos entender por
conjunto de parâmetros do algoritmo a palavra fenótipo onde na biologia corresponde à
interação do conteúdo genético com o ambiente. Já o genoma não possui um termo
análogo na área de GA, mas para a biologia seu significado corresponde ao pacote
genético.
Durante o estudo foram observadas duas tabelas e, a partir delas foi criada
uma tabela própria (Tabela 1) com os termos que seriam mais concernentes de serem
citados, entende-se que assim alguém ao se deparar com estes termos terá um melhor
aproveitamento deste trabalho, ao fazer esta recompilação de dados decidiu-se
compartilhar este conhecimento adquirido e assim resumir tudo o que já foi citado.
Linguagem natural GA
cromossomo individuo, string, cromossomo, árvore
gen características
alelo valor
locus posição
genótipo estrutura
fenótipo conjunto de parâmetros
população conjunto de pontos (indivíduos) no Espaço de Busca
geração iteração completa do GA que gera uma nova população
aptidão brutasaída gerada pela função objetivo para um individuo da
população
aptidão normalizada Aptidão bruta normalizada, entrada para o algoritmo de
30
seleção
aptidão máxima melhor individuo da população corrente
aptidão media aptidão media da população corrente
Tabela 1 - Faz uma comparação entre os termos utilizados em linguagem natura (na biologia) com a utilizada no GA.
Utilizaremos mais os termos que corresponde aos GAs, pois os mesmos
correspondem mais a nossa área podendo os termos da área biológica serem utilizados
de vez em quando pois em nossas pesquisas em varias fontes estes termos também
são utilizados então entendemos que serão de grande importância para um melhor
aproveitamento do nosso trabalho.
4 ENTENDENDO UM GA SIMPLES
Começaremos este capitulo fazendo uma breve apresentação entre os
leitores deste singelo trabalho e os algoritmos genéticos, todos os passos até aqui
apresentados são de grande importância para o entendimento do assunto abordado.
Devemos ficar atentos quando se diz respeito a escolha dos parâmetros nos
algoritmos genéticos pois os mesmos estão diretamente ligados a quão bom será os
resultados que iremos obter. Mais adiante será explicado melhor como ocorrerá esta
escolha bem como a sua importância.
Logo abaixo apresentaremos um esboço do algoritmo genético (Tabela 2)
onde o mesmo é composto por varias etapas que iremos explicar adiante. Atentamos a
questões importantes que talvez nos indaguem ao inicializarmos a construção do nosso
algoritmo, questões estas como:
Como criaremos cromossomos e qual tipo de codificação utilizaremos?
Como escolheremos os pais para a realização do crossover?
31
Com a criação de uma nova população a partir de duas outras pode
causar a perda da melhor solução?
[Início] Gera-se aleatoriamente uma população de n cromossomos
[Adaptação] Verifica-se a função objetiva f(x) de cada cromossomo x
[População] Uma nova população será gerada através da repetição a seguir:
[Seleção] Selecionamos um par de cromossomos da população conforme a adaptação de cada um (os mais aptos tem maior chance de serem escolhidos)
[Crossover] Através dos cromossomos dos pais geram-se dois descendentes (filhos) por crossover. Lembremos que o ponto para se realizar o crossover deve ser aleatório.
[Mutação] Com certa probabilidade, o descendente sofre mutação em cada locus (posição no cromossomo).
[Aceitação] Colocamos os descendentes gerados em uma nova população, juntamente com a melhor solução da antiga geração]
[Troca] Substituímos a antiga população pela nova geração.
[Teste] Se a condição de finalização é satisfatória, então pare, e assim retornaremos a melhor solução da população atual, caso contrário entraremos no laço
[Adaptação]
[Laço] Voltaremos a uma nova seleção.Tabela 2 - Esboço do algoritmo genético em forma de etapas.
Atente que está é apenas uma forma simplificada que serve apenas para o
entendimento da criação do GA, pois ainda fica implícito para nós ao visualizarmos ela
toda a complexidade do processo de obtenção dos de alguns elementos. De acordo
Ricardo Linden os processos acima citados são os seguintes:
[...] uma representação cromossomial que seja adequada ao problema; uma função de avaliação que penalize soluções implausíveis para nosso problema e que avalie satisfatoriamente o grau de adequação de cada individuo como solução do problema em questão (LINDEN, 2006, p. 52)
Sendo o GA altamente genérico, vários de seus componentes não mudam de
um problema para outro. Isso irá facilitar a sua implementação em uma linguagem
orientada a objetos, pois assim permitirá o reaproveitamento do código podendo ser
utilizado na resolução de muitos outros problemas.
4.1 Como escolher parâmetros do GA
32
Achamos interessante incluir este capitulo por a escolha dos parâmetros de
um GA ser crucial, pois a mesma poderá implicar no resultado final do resultado do
algoritmo genético.
Existem vários parâmetros que podemos escolher para melhorar o
desempenho do algoritmo genético, um deles é a forma como o cromossomo é
codificado e com isso adaptamos o GA as características particulares que cada classe
de problema traz. Dentre vários podemos citar os mais importantes como: tamanho da
população, número de gerações, probabilidade de crossover e probabilidade de
mutação. Estes parâmetros podem influenciar muito o resultado que será obtido pelo
algoritmo genético e sua influência depende da classe de problemas que se está
tratando.
Portanto, ao determinar um conjunto de valores otimizados para os
parâmetros dependerá da realização de um grande numero de experimentos e testes.
Em nossas pesquisas constatamos que vários dos valores encontrados na maioria das
literaturas estão na faixa de 60 a 65% quando se diz respeito a probabilidade de
crossover e entre 0,1 e 5% quando nos referenciamos a probabilidade de mutação.
Como acima citamos, algum dos fatores decisivos que afetam as respostas
encontradas para os problemas de GA é o tamanho da população e o número de
gerações, pois os mesmos definem diretamente o tamanho do espaço da busca a ser
descoberto, ou seja, a quantidade de soluções que podemos encontrar. Existe técnicas
que utilizam um GA como método de otimização para escolher os parâmetros, pois
devido a grande importância da escolha correta dos mesmos implicar na resposta que
os algoritmos genéticos irão encontrar.
4.2 Representação de um cromossomo
A representação cromossomial é vital para um algoritmo genético, pois é uma
maneira básica de traduzir a informação de um problema em uma maneira que possa
ser tratada pelo computador. Por ela ser completamente arbitraria, ou seja, varia de
acordo com a vontade de cada programador não havendo qualquer tipo de obrigação
33
para se adotar qualquer tipo de representação, portanto este é um outro ponto
importante a ressaltar. A grande maioria de pesquisadores frequentemente utiliza a
representação binária por a mesma ser a mais simples, na verdade, muitas pessoas
quando imaginam um GA, rapidamente fazem uma associação em cromossomos
binários. Entretanto, esta associação não é obrigatória e sim deve se adotar a que for
mais adequada a nossos propósitos.
De acordo com o pesquisador Ricardo Linden uma pergunta pode nos ocorrer
quando se diz respeito à representação cromossomial, sendo esta uma indagação de
quando a representação binária não será a mais adequada.
A representação binária tem dificuldades ao lidar com múltiplas dimensões de variáveis continuas, especialmente quando uma grande precisão é requerida. Isto decorre do fato de que um grande número de bits será necessário para atingir tal precisão e os cromossomos se tornarão extremamente grandes, dificultando a operação do GA. Além disto, há uma discretização inerente nos valores reais quando cromossomos binários são usados. É claro que podemos ignorar o efeito desta discretização quando usamos bits suficientes, mas esta quantidade pode fazer com que nossos cromossomos se tornem grandes demais (HERRERA apud LINDEN, 1998, p. 165)
Existem outros tipos de representações além do binário onde as mesmas são
pouco utilizadas, mas igualmente interessantes e eventualmente mais poderosas e
adequadas para problemas específicos. Dentre elas podemos citar como as mais
comuns:
Binário (EX: 010111);
Numérico (Ex: 5,8; 9,3);
Seqüencial (Ex: 3, 5, 4, 1, 2);
Lembremos que uma representação é de grande importância, pois ela poderá
ser a mais adequada a algum problema que viermos a resolver: Qualquer estrutura de
dados que pudermos imaginar!
Devemos entender que os operadores genéticos devem ser modificados para
serem adequados à representação apropriada.
4.3 Inicialização Cromossomial
34
Uma boa inicialização ou podemos também falar representação, é
fundamental para um algoritmo genético. Ela basicamente consiste em pegarmos a
informação do problema e traduzirmos o mesmo em uma maneira viável de ser tratada
pelo computador. Se conseguirmos adequá-la ao nosso problema, sendo esta
adequação feita da melhor forma possível, maior será a qualidade dos resultados que
obteremos. De acordo com Ricardo Linden temos que tomar cuidado quanto a esta
problemática, pois muitos programadores ficam tentados a adequar o problema a sua
representação sendo assim poderá levar a não obtenção do resultado ideal.
Chamamos de gene cada pedaço indivisível da representação, pois como já
foi dito anteriormente existe uma analogia com a biologia, mais precisamente as partes
que compõe um cromossomo biológico.
Lembremos que ao fazermos uma representação cromossomial não
precisamos seguir nenhuma regra pré-definida, pois a mesma irá variar de acordo com
o gosto do programador e da sua adequação ao problema. Porém, de acordo com
Ricardo Linden existe algumas regras gerais que é interessante segui-las:
a) A representação deve ser a mais simples possível; b) Se houver soluções proibidas ao problema, então elas não devem ter uma representação; c) Se o problema impuser condições de algum tipo, estas devem estar implícitas dentro da nossa representação. (LINDEN, 2006, p. 54)
Assim, percebemos que uma representação mais praticada entre os
programadores da área dos algoritmos genéticos sendo a mesma também a mais
simples, é a representação binária, pois um cromossomo é uma seqüência em forma de
bits tendo cada gene como um bit. Este bit ou conjunto de bits onde sua representação
é de grande importância e esta diretamente ligada ao problema.
Existem também outras formas de representar um cromossomo e podem até
obter resultados melhores.
4.4 Função Para Cálculo da Aptidão
Esta função é a maneira de os GAs calcularem a aptidão do indivíduo, ou
seja, determinar a qualidade de um individuo como solução para o problema. Se
35
pensarmos que esta função irá representar a nota dada ao individuo como resolução
para o problema teremos assim um melhor entendimento sobre o papel desta função
dentro dos GAs. Sendo que esta nota irá servir para a escolha de seleção de pais que
veremos a seguir, onde através dela iremos diferenciar as boas e as más soluções para
um problema.
Dentro dos GAs a função que calcula a aptidão de um individuo, em muitos
casos, é a única ligação verdadeira do programa com o problema, pois a mesma só
julga a qualidade da solução que esta sendo apresentada por aquele individuo e não
armazena informação sobre as técnicas de resolução do problema.
Em nossas pesquisas encontramos duas formas que podemos chamar esta
função: função de avaliação ou função de custo, onde sua finalidade é calcular um valor
numérico que reproduzirá quão bons os parâmetros representados no cromossomo
resolverão o problema. Através dos parâmetros, ou seja, os valores armazenados no
cromossomo que ela utiliza para produzir um valor numérico, onde seu significado
representa uma maneira de compararmos os resultados e assim obtermos uma
qualidade da solução obtida. Sendo os GAs técnicas de maximização, a função de
avaliação ou função de custo tem o objetivo de obter o resultado maximo, sendo assim
ao compararmos dois cromossomos onde o primeiro representa uma solução melhor
que o segundo a função de avaliação do primeiro deve ser maior do que a do segundo
cromossomo.
Portanto devemos atentar para a importância que esta função deve refletir os
objetivos a serem alcançados em uma resolução, pois ela é gerada diretamente pelas
condições impostas apresentadas no problema.
4.5 Seleção
Como um mecanismo de seleção natural o método de seleção de pais deve
simulá-lo, pois o mesmo segue a idéia que acontece na lei da evolução das espécies
onde há a seleção natural das espécies biológicas. Consiste em que os pais capazes
geram filhos, igualmente os pais menos aptos também podem gerar descendentes.
Logo devemos dar maior importância para os indivíduos com maior função de
36
avaliação, mas não menos importante vêm os indivíduos com função de avaliação
extremamente baixa onde devem também ser mantidos mesmo em menor quantidade.
Isto se deve ao fato desta decisão ser razoável, pois os indivíduos com péssima
avaliação podem ter características genéticas que sejam de grande valor a criação de
um novo individuo onde no mesmo pode conter uma melhor solução para o problema
que será resolvido, se por acaso deixarmos de lado estes indivíduos podemos correr o
risco de perder uma solução ideal, pois neles pode haver características não
encontradas em nenhum outro cromossomo da nossa população e com isso essas
características podem ser perdidas.
Portanto devemos ficar atentos sobre a questão de deixarmos apenas os
melhores indivíduos se reproduzirem, pois a população ficará composta de indivíduos
cada vez mais semelhantes e com isso acaba diminuindo a diversidade da população
prejudicando a evolução, pois a mesma não irá seguir de forma satisfatória. Devido a
este fato acaba resultando em um efeito denominado convergência genética, mas se
selecionarmos os indivíduos menos aptos conseguiremos evitar este efeito, ou no
mínimo minimiza-lo. Na natureza ocorre que os indivíduos mais fracos também geram
filhos, mesmo que isto seja com uma ocorrência menor comparando com os indivíduos
mais aptos, ou podemos chamá-los também de mais fortes. Sendo assim como os GAs
são desenvolvidos a partir de como se ocorre na natureza é interessante também
reproduzir esta possibilidade. Podemos implementar este efeito ou características
através do método da roleta viciada em nossos GAs. Mostrando de uma forma mais
visual podemos criar uma tabela onde mostrará uma população e sua respectiva
avaliação da aptidão (Tabela 3).
Indivíduo Avaliação da Aptidão
1000 1
0111 9
1010 16
1010 36
Total 62
Tabela 3 - Exemplo de como ocorre o processo de seleção atentando para não cair no efeito de convergência genética (tabela meramente ilustrativa).
37
Onde de um lado colocamos os indivíduos e do outro a sua avaliação. Cada
individuo possui suas características em seus respectivos cromossomos.
O cromossomo é representado pelo número binário ‘0001’ e o número ‘1’ uma
característica desse cromossomo, então o cromossomo ‘0001’ tem a pior avaliação mas
atentemos ao detalhe que ele possui uma boa característica que é representada pelo
numero ‘1’ na ultima posição do cromossomo pois nos dois melhores indivíduos ou seja
os indivíduos de melhor avaliação, não possuem esta característica. Sendo assim se
utilizássemos apenas os dois melhores indivíduos para reprodução, nossa resolução
não poderá ser a ideal.
4.6 Cruzamento ("Crossover")
Existem vários operadores de cruzamento ou crossover, alguns simples
outros mais complexos. Damos inicio falando sobre um dos operadores mais simples,
denominado de crossover de um ponto. Por ser um operador extremamente simples é
bem conveniente começarmos por ele para um melhor entendimento. Ao termino do
processo de seleção os pais já foram escolhidos. É chamado de ponto de corte a
interseção entre dois genes em um cromossomo, cada individuo de n genes contem n-1
pontos de corte, onde este ponto de corte separa os genes uns dos outros onde
compõe o material genético de cada pai. Em nossos estudos nos deparamos com a
Figura 6 onde representa um exemplo de pontos de corte onde o cromossomo é
formado de 5 genes e consequentemente por 4 pontos de corte possíveis.
38
Figura 6 - Exemplo de pontos de corte (LINDEN, 2006, p. 67)
É feito da seguinte forma, o ponto de corte é sorteado aleatoriamente logo em
seguida separam-se os pais em duas partes, a direita ficando de um lado e a esquerda
do outro. È importante fresarmos que essas partes necessariamente não precisam ser
do mesmo tamanho.
[...] vamos perceber que se o numero de genes for impar, é impossível que as duas partes de cada pai tenha exatamente o mesmo tamanho [...] (LINDEN, 2006, p. 67)
Um filho é composto pela junção da parte esquerda de um pai com a parte
direita do outro e o outro filho é composto pelas as partes restantes. O exemplo deste
processo pode ser visto através da Figura 7, sendo o mesmo parecido com o que
acontece na natureza, onde dois cromossomos dão origem a outros dois novos
cromossomos conhecido por formação cromossomial de um individuo pertencente a
uma mesma espécie que utiliza a reprodução sexuada. Uma diferença é que na
natureza não existe restrição a apenas um ponto de corte.
Existem crossover de um ponto, de dois pontos, consequentemente existe de
três, o de quatro e assim por diante, em nossas pesquisas também constatamos a
existência de um operador complexo chamado de crossover uniforme. Por enquanto
ficaremos apenas no de um ponto.
39
Figura 7 - Representação do processo de cruzamento de um ponto.
Como já aviamos falado o cruzamento de vários pontos ou cruzamento
multiponto como também é conhecido, onde existem vários pontos de cruzamento que
podem ser utilizados. Entendemos melhor ao visualizarmos a Figura 8 onde
representaremos o cruzamento de dois pontos.
Figura 8 - Representação de cruzamento de dois pontos
No cruzamento uniforme não se utiliza pontos de cruzamento, mas se
determina por meio de uma mascara, onde os genes de cada cromossomo o filho irá
herdar. Um valor “1” que se encontra na mascara ira ser o gene correspondente no pai
40
que o filho ira herdar isso para os dois cromossomos pais e filhos, através da Figura 9
encontramos um exemplo onde podemos entender de forma melhor.
Figura 9 - Representação de cruzamento uniforme
4.7 Mutação
Ao termino da composição dos filhos executaremos o operador de mutação.
Onde o mesmo é operado da seguinte forma. Como este operador tem uma
probabilidade extremamente baixa da ordem de 0,5%, nós sorteamos um numero entre
0 e 1. Se por acaso este número for menor que a probabilidade predeterminada, então
o operador atuará sobre o gene em questão alterando-lhe o valor randomicamente.
Então repetiremos o processo para todos os genes que fazem parte dos dois filhos.
O que decide se o operador de mutação será ou não aplicado é um dos
parâmetros do GA sendo o mesmo um valor probabilístico onde simplesmente a
experiência pode determinar. Quanto ao valor probabilístico o seu conceito fundamental
é que ele deve ser baixo, pois caso ele seja muito alto, o algoritmo genético ficará
análogo com uma técnica chamada random walk, onde sua solução é determinada de
41
foram aleatória, ou seja, simplesmente sorteando-se elementos não utilizando
informações correntes ou passadas.
Se a taxa de mutação for colocada em 100%, ou seja, se todos os genes do
cromossomo forem alterados, os algoritmos genéticos se comportarão de forma
estranha. Sendo assim todos os bits do cromossomo serão invertidos, pois quando um
número for selecionado será sempre menor do que um, a probabilidade
predeterminada. Então a qualidade da população rapidamente será modificada para
pior e dificilmente o GA apresentará uma solução ideal para o problema.
Quando a taxa de mutação é baixa previne que a busca fique parada em sub-
regiões do espaço de busca. Então, possibilitará que qualquer ponto do espaço de
busca seja atingido. Sendo assim ao termos uma taxa muito alta a busca se tornará
essencialmente aleatória. Um exemplo de como ficará o cromossomo após a mutação
pode ser visto na Figura 10.
Figura 10 - Exemplo ilustrativo de mutação
O processo consiste em aplicarmos em dois pais escolhidos o operador de
crossover através do método da roleta viciada e logo após aplicarmos o operador de
mutação. Através da Figura 11 podemos olhar melhor como funciona.
42
Figura 11 - Descrição da operação do operador de crossover de um ponto e mutação (LINDEN, 2006, p. 69)
5 APLICABILIDADES
Podemos dizer que a aplicabilidade dos GAs é praticamente infinita, pois
sempre que houver a necessidade de buscar ou otimizar um problema para que sua
resposta seja a ideal os utilizaremos como ferramenta de solução, também podemos
incluir a solução de equações como uma utilizadora de GAs. Lembremos que ao
utilizarmos algoritmos genéticos simples devemos limitar sua aplicação principalmente
quando existir um algoritmo exato capaz de resolver o problema em um tempo
relativamente curto, dentro de uma memória finita. Pelo número de problemas com
estas características serem grandes o suficiente, podemos justificar a introdução de
uma nova resolução.
43
O maior problema que podemos encontrar ao utilizarmos um algoritmo
genético para resolver problemas está em torná-lo adequado aos requisitos de GAs, ou
seja, devemos encontrar uma representação cromossomial para cada aspecto do
problema considerado. Em nossas pesquisas encontramos algumas indagações que
através das mesmas podemos entender como um problema é resolvido, mas é
importante falarmos que nem todos os problemas recebem estas considerações. São
elas:
● Qual a representação adotada?● Para esta representação, qual é o mecanismo dos operadores genéticos?● Qual foi a função de avaliação utilizada?● Qual é o critério de termino utilizado?. (LINDEN, 2006, p. 285)
Os GAs possuem uma larga aplicação em muitas áreas cientificas, dentre
elas podemos citar: Síntese de Circuitos Analógicos, Programação Genética,
Gerenciamento de Redes, Problemas de otimização complexos, Bioinformática, Setor
Elétrico, Filogenética, etc. A tabela a baixo (Tabela 4) traz algumas áreas cientificas e a
utilização do GA para as mesmas.
ÁREA CIENTIFICA UTILIZAÇÃO DO GASíntese de Circuitos Analógicos É utilizado para produzir uma certa entrada e
uma saída desejada, como na tensão existente em circuitos analógicos, onde o GA gera a topologia, o tipo e o valor dos componentes do circuito.
Síntese de Protocolos È utilizado para determinar quais as funções do protocolo devem ser executadas em hardware e quais devem ser executadas em software para que seja alcançado um maior desempenho.
Alocação de Capacitores Como o próprio nome sugere, é utilizado para melhor alocar os capacitores melhorando assim a regulação e a voltagem fornecida como também aumenta a capacidade de liberação de energia do sistema, pois a extensão dos benefícios conseguidos depende fortemente de
44
como os capacitores são colocados e controlados.
Escalonamento de Horários É utilizado na definição de horários das matérias, de acordo com a preferência dos professores, a necessidade de que duas turmas com alunos em comum não tenham horários coincidentes, que alunos estudem sempre em um único bloco da faculdade e muitas outras restrições possíveis. Sendo assim seu espaço de busca é praticamente infinito, pois o numero de combinações também depende do numero de turmas e salas.
Escala de Tarefas É utilizado para o problema de escala de tarefas (job shop scheduling problem) onde cada tarefa consiste em uma seqüência de operadores, que tem que ser processadas e um conjunto fechado e limitado de maquinas (Computadores), de forma que o conjunto dessas tarefas seja realizado no menor tempo possível.
Filogenética Sua utilização consiste em avaliar os relacionamentos evolucionários entre uma serie de n organismos, ou seja, a relação de parentesco entre esses organismos.
Ciências biológicas - Bioinformática
É utilizado para transformar a imensa massa bruta de informação em processos biológicos de forma a permitir a compreensão destes processos e, eventualmente, o desenvolvimento de novos remédios que garantam o progresso e a melhoria das condições de vida da humanidade.
Tabela 4 – Contem a área cientifica assinalando com a utilização do GA.
A quantidade de aplicativos que atualmente utilizam GAs é tão grande que
seria inviável elaborar e apresentar aqui uma lista de produtos disponíveis no mercado.
Alguns softwares que citaremos estão disponíveis para compra e/ou licenciamento. São
eles:
Evolver, onde o mesmo é uma ferramenta para auxiliar o Microsoft
Excel na resolução rápida com problemas complexos de otimização
em finanças, distribuição, a programação, produção, orçamentos,
engenharia, e muito mais, para maiores detalhes o mesmo está
disponível em: http://www.palisade.com/evolver/.
45
OptiGA, é um controle de ActiveX (OCX) utilizado na implementação
de Algoritmos Genéticos para aplicações em Visual Basic. O mesmo
está disponível em: http://www.optiwater.com/optiga.html.
GeneticServer, é um componente ActiveX que pode ser facilmente
usado para construir aplicações genéticas personalizadas em Visual
Basic, para maiores informações visite: http://www.nd.com/genetic/.
Como já havíamos falado existem muitos outros produtos alem dos acima
citados, também encontraremos muitos deles não comercias onde os mesmos podem
ser encontrados na internet.
6 CONSIDERAÇÕES FINAIS
É sabido que a partir dos conhecimentos adquiridos no decorrer dos séculos
o homem obteve grandes avanços em diversas áreas do conhecimento, ressaltando a
área da inteligência artificial, mais precisamente os algoritmos genéticos, uma vez que
é o objeto de estudo do nosso trabalho. Atrelado ao desenvolvimento do intelecto do
ser humano, sugiram problemas próprios da complexidade trazidas pelos mesmos,
46
levando o homem a tentar soluciona-los, alguns de formas simples outros de forma
complexa, ou seja, de diferentes formas sendo característico de cada um.
Quando nos referimos aos algoritmos genéticos, os mesmo vieram com o
propósito de solucionar problemas onde os algoritmos normais não o conseguiam ou
eram demasiadamente lentos na obtenção da solução. Como foi mostrado no trabalho
os GA são uma importante e poderosa ferramenta para efetuar buscas em espaços
praticamente infinitos, porém, sua aplicabilidade é basicamente limitada a este tipo de
problema. Desta forma, afirmamos que não se trata de uma técnica que revolucionará
toda a ciência da computação, mas é importante entendermos que, como ferramenta de
busca, os mesmos se mostram muito eficientes, encontrando ótimas soluções para
problemas que talvez não pudessem ser solucionados de forma diversa.
Com base no exposto acima, podemos citar como principais vantagens na
utilização de GAs, como solução de problemas específicos: são extremamente simples
de implementar e modificar, uma vez que não é necessário conhecimento matemático
aprofundado do problema, apresenta um bom desempenho em problemas de
otimização de grande escala, na otimização multiobjetivo fornecem uma lista de
parâmetros ótimos e não uma só solução, ou seja, nem sempre o algoritmo genético
trará a mesma solução mas pode apresentar varias soluções ideais dependendo dos
parâmetros escolhidos, dentre outras.
É importante ressaltar ainda, que os GAs não oferecem nenhuma garantia de
desempenho, pois os mesmos são diretamente dependentes dos parâmetros
escolhidos pelo programador, podendo assim um mesmo problema ser resolvido de
varias formas, porem, quando estes parâmetros são ajustados da forma mais perfeita
possível, ai sim, poderemos encontrar a solução ideal. Apesar do GA não ser o método
mais preciso por ser um método heurístico, no momento é o mais eficiente.
Esperamos, pois, que o nosso trabalho monográfico venha contribuir para
melhorar o conhecimento acerca da aplicabilidade dos GAs em nossa área, pois é
interessante conhecer o processo para a obtenção do mesmo antes de pensarmos em
começar alguma implementação e com isso o algoritmo genético poderá chegar ao seu
total objetivo tendo um melhor desempenho.
47
Por fim, afirmamos que existem varias áreas em aberto dentro da pesquisa
teórica dos algoritmos genéticos, por tal motivo, tivemos como objetivo sinalizar
caminhos e não dar explicações de forma acabada com intuito de estimular outras
pesquisas. Ademias, devemos enfatizar que não há nenhum motivo plausível para
pararmos de aprender com a natureza, apesar de os GAs funcionarem muito bem na
atualidade, mas certamente a inclusão de técnicas utilizadas na natureza podem
melhorar demasiadamente o desempenho de tais algoritmos.
48
REFERÊNCIAS
ALVES, Ricardo Arantes. Algoritmos Genéticos. São Paulo: EDIÇÕES INTELIGENTES, 2005.
CARVALHO, André Ponce de Leon F. de. Algoritmos Genéticos. Disponível em: <http://www.icmc.usp.br/~andre/research/genetic/index.htm#intro>. Acessado em: 24 abril 2007.
CASTRO, Leandro de; ZUBEN, Fernando Von. Algoritmos Genéticos (AG’s). Disponível em: <ftp://ftp.dca.fee.unicamp.br/pub/docs/vonzuben/ia707_02/topico9_02.pdf>. Acessado em: 24 abril 2007.
CORTES, Maria Bernadete de Sousa. Algoritmos Genéticos Em Problemas de Programação Não Linear Contínua. Disponível em: < http://www.eps.ufsc.br/teses96/cortes/index/index.htm>. Acessado em: 24 abril 2007.
FURTADO, João Carlos; LORENA, Luiz Antonio Nogueira. Algoritmo Genético Construtivo na otimização de problemas combinatoriais de agrupamentos. Disponível em: < http://www.lac.inpe.br/~lorena/sbpo98/agc-clust.pdf>. Acessado em: 24 abril 2007.
LINDEN, Ricardo. Algoritmos Genéticos – Uma importante ferramenta da Inteligência Computacional. Rio de Janeiro: Brasport, 2006.
LOPES, Vanessa Meneses. Algoritmos Genéticos. Disponível em: < http://www.zemoleza.com.br/trabalho_ver.asp?codTrabalho=33541&carreira=11>. Acessado em: 24 abril 2007.
LUCAS, Diogo C.. Algoritmos Genéticos: uma Introdução. Disponível em: < http://www.inf.ufrgs.br/~alvares/INF01048IA/ApostilaAlgoritmosGeneticos.pdf>. Acessado em: 24 abril 2007.
MIRANDA, Marcio Nunes de. Algoritmos Genéticos – Fundamentos e Aplicações. Disponível em: <http://www.gta.ufrj.br/~marcio/genetic.html#Introdução>. Acessado em: 24 abril 2007.
NARCISO, Marcelo Gonçalves. Uso de Algoritmos Genéticos em Sistema de Apoio a Decisão para Alocação de Recursos no Campo e na Cidade. Disponível em: < http://www.lac.inpe.br/~lorena/marcelo/PLC-CT.pdf>. Acessado em: 24 abril 2007.
NEITZEL, Luís Carlos. Aplicações práticas de Algoritmos Genéticos. Disponível em: < http://www.geocities.com/Athens/Sparta/1350/ia/IA3_aplica/index.htm>. Acessado em: 24 abril 2007.
48
PACHECO, Marco Aurélio Cvalcanti. ALGORITMOS GENÉTICOS: PRINCÍPIOS E APLICAÇÕES. Disponível em: <http://www.ica.ele.puc-rio.br/cursos/download/CE-Apostila-Comp-Evol.pdf>. Acessado em: 24 abril 2007.
REZENDE, Solange Oliveira (org). Sistemas Inteligentes Fundamentos e Aplicações. São Paulo: EDITORA MANOLE, 2005.
RIBEIRO, Elder. Algoritmos Genéticos – Fundamentos e Aplicações. Disponível em: <http://www.zemoleza.com.br/trabalho_ver.asp?codTrabalho=24575&carreira=11>. Acessado em: 24 abril 2007.
SILVA, Paulo Ricardo da; ZAMBONI, Rafael Régis; MARQUES, Ana Flavia. Teoria da Evolução. Disponível em: <http://www.brasilescola.com/biologia/teoria-da-evolucao.htm>. Acessado em: 25 julho 2007.
SOARES, Gustavo Luís. Algoritmos Genéticos: Estudo, Novas Técnicas e Aplicações. Disponível em: <http://www.cpdee.ufmg.br/~joao/TesesOrientadas/VAS1997_1.pdf>. Acessado em: 25 julho 2007.
TICONA, Waldo Gonzalo Cancino. Aplicação de Algoritmos Genéticos Multi-Objetivo para Alinhamento de Seqüências Biológicas. Disponível em: < http://www.jeo.org/emo/tesis_waldo_msc_final.pdf.gz>. Acessado em: 24 abril 2007.
WIKIPEDIA, The Free Encyclopedia. Algoritmo. Disponível em: < http://pt.wikipedia.org/wiki/Algoritmo>. Acessado em: 25 Agosto 2007.
WIKIPEDIA, The Free Encyclopedia. Algoritmo genético. Disponível em: < http://pt.wikipedia.org/wiki/Algoritmo_gen%C3%A9tico>. Acessado em: 25 Agosto 2007.
WIKIPEDIA, The Free Encyclopedia. Algoritmo evolutivo. Disponível em: < http://pt.wikipedia.org/wiki/Algoritmo_evolutivo>. Acessado em: 25 Agosto 2007.
WIKIPEDIA, The Free Encyclopedia. Ingo Rechenberg. Disponível em: < http://en.wikipedia.org/wiki/Ingo_Rechenberg>. Acessado em: 25 julho 2007.
WIKIPEDIA, The Free Encyclopedia. NP-completo. Disponível em: < http://pt.wikipedia.org/wiki/NP-completo>. Acessado em: 25 julho 2007.
WIKIPEDIA, The Free Encyclopedia. Charles Darwin. Disponível em: < http://pt.wikipedia.org/wiki/Charles_Darwin>. Acessado em: 25 Agosto 2007.
WIKIPEDIA, The Free Encyclopedia. Evolução. Disponível em: < http://pt.wikipedia.org/wiki/Evolu%C3%A7%C3%A3o>. Acessado em: 25 Agosto 2007.
WIKIPEDIA, The Free Encyclopedia. Genética. Disponível em: < http://pt.wikipedia.org/wiki/Gen%C3%A9tica>. Acessado em: 25 Agosot 2007.
49
WIKIPEDIA, The Free Encyclopedia. Gregor Mendel. Disponível em: < http://pt.wikipedia.org/wiki/Gregor_Mendel>. Acessado em: 25 Agosto 2007.
WIKIPEDIA, The Free Encyclopedia. John Henry Holland. Disponível em: < http://en.wikipedia.org/wiki/John_Henry_Holland>. Acessado em: 25 Agosto 2007.
WIKIPEDIA, The Free Encyclopedia. Programação genética. Disponível em: < http://pt.wikipedia.org/wiki/Programa%C3%A7%C3%A3o_gen%C3%A9tica>. Acessado em: 25 Agosto 2007.
50
