GA – Conceitos B ilaim/IA11.pdf  GA – Conceitos Bsicos Cap­tulo 3 ... indiv­duos desta

  • View
    212

  • Download
    0

Embed Size (px)

Text of GA – Conceitos B ilaim/IA11.pdf  GA – Conceitos Bsicos...

GA Conceitos Bsicos

Captulo 3

Prof. Ricardo Linden

Algoritmos Evolucionrios

Algoritmos evolucionrios usam modelos computacionais

dos processos naturais de evoluo como uma ferramenta

para resolver problemas.

H uma grande variedade de modelos computacionais. Em

comum:

Conceito de simulao da evoluo das espcies

Uso de operadores de seleo, mutao e reproduo

Todos os processos dependem do "desempenho" dos

indivduos desta espcie dentro do "ambiente".

Algoritmos Evolucionrios

Mantm uma populao de estruturas, denominadas indivduos ou cromossomos

Comportam-se de forma semelhante evoluo das espcies.

A estas estruturas so aplicados os chamados operadores genticos, como recombinao e mutao, entre outros.

Cada indivduo recebe uma avaliao que uma quantificao da sua qualidade como soluo do problema em questo.

Baseado nesta avaliao sero aplicados os operadores genticos de forma a simular a sobrevivncia do mais apto.

Algoritmos Evolucionrios

Pseudo-Cdigo

T:=0

Inicializa_Populao P(0)

Enquanto no terminar faa

Avalie_Populao P(t)

P':=Selecione_Pais P(t)

P'=Recombinao_e_mutao P'

Avalie_Populao P'

P(t+1)=Selecione_sobreviventes P(t),P'

t:=t+1

Fim enquanto

Algoritmos Evolucionrios

So extremamente dependentes de fatores estocsticos (probabilsticos), tanto na fase de inicializao da populao quanto na fase de evoluo (durante a seleo dos pais, principalmente).

Seus resultados raramente sejam perfeitamente reprodutveis.

Algoritmos evolucionrios so heursticas que no asseguram a obteno do melhor resultado possvel em todas as suas execues.

Concluso Razovel

Se voc tem um algoritmo com tempo de execuo longo o suficiente para soluo de um problema, ento no hnenhuma necessidade de se usar um algoritmo evolucionrio.

Sempre d prioridade aos algoritmos exatos.Os algoritmos evolucionrios entram em cena para resolver aqueles problemas cujos algoritmos so extraordinariamente lentos (problemas NP-completos) ou incapazes de obter soluo (como por exemplo, problemas de maximizao de funes multi-modais).

AE e Tcnicas de Busca

Tcnicas de Busca

Baseadas em Clculo Aleatrias-Guiadas Enumerativas

Algoritmos Evolucionrios Resfriamento Simulado

Estratgias Evolucionrias Algoritmos Genticos Programao Gentica

Paralelos Seqenciais

Algoritmos Genticos

Algoritmos genticos (GA) so um ramo dos algoritmos evolucionrios

Como tal podem ser definidos como uma tcnica de busca baseada numa metfora do processo biolgico de evoluo natural.

Os algoritmos genticos so tcnicas heursticas de otimizao global

So algoritmos de busca baseados nos mecanismos de seleo natural e gentica.

Algoritmos Genticos

Populaes de indivduos so criados e submetidos aos operadores genticos:

Seleo

Recombinao (crossover)

Mutao.

Estes operadores utilizam uma caracterizao da qualidade de cada indivduo como soluo do problema em questo chamada de avaliao

Geram um processo de evoluo natural destes indivduos

Eventualmente gerar um indivduo que caracterizar uma boa soluo (talvez at a melhor possvel) para o nosso problema.

Algoritmos Genticos

GAs no so mtodos de "hill climbing", logo eles no

ficaro estagnados simplesmente pelo fato de terem

encontrado um mximo local.

Eles se parecem com a evoluo natural, que s por que

encontrou um indivduo que instantaneamente o melhor

de um certo grupo no pra de procurar outros

indivduos ainda melhores.

Na evoluo natural isto tambm decorre de circunstncias

que mudam de um momento para outro.

Ateno

A evoluo natural no um processo dirigido

obteno da soluo tima.

O processo simplesmente consiste em fazer

competir uma srie de indivduos e pelo processo

de sobrevivncia do mais apto, os melhores

indivduos tendem a sobreviver.

Um GA tem o mesmo comportamento que a

evoluo natural: a competio entre os indivduos

que determina as solues obtidas.

Caractersticas dos GAs

Assim como na natureza, a informao deve ser codificada

nos cromossomos (ou genomas)

A reproduo, que no caso dos GAs, equivalente

reproduo sexuada, se encarregar de fazer com que a

populao evolua.

A mutao cria diversidade, mudando aleatoriamente gens

dentro de indivduos.

A reproduo e a mutao so aplicadas em indivduos

selecionados dentro da nossa populao.

Processo de Seleo

A seleo deve ser feita de tal forma que os indivduos mais aptos sejam selecionados mais freqentemente do que aqueles menos aptos

Objetivo: boas caractersticas daqueles passem a predominar dentro da nossa populao de solues.

Indivduos menos aptos nunca devem ser descartados da populao reprodutora.

Isto causaria uma rpida convergncia gentica de todas as solues para um mesmo conjunto de caractersticas e evitaria uma busca mais ampla pelo espao de solues

Terminologia

Nos sistemas naturais um ou mais cromossomos se combinam para formar as caractersticas genticas bsicas do indivduo em questo.

Na rea dos GAs, os termos cromossomo e indivduo so intercambiveis, sendo usados de forma razoavelmente aleatria neste texto.

Como a representao binria dominante em vrios dos textos bsicos da rea, muitas vezes pode-se escrever string (de bits) significando o mesmo que cromossomo

Terminologia

No campo da gentica os cromossomos so formados por

genes, que podem ter um determinado valor entre vrios

possveis, chamados de alelos.

Posio do gene chamada de seu locus (plural: loci).

Os termos biolgicos so aplicveis tambm rea de GA:

caractersticas para significar gene

valores para significar alelos

posio para significar locus.

Terminologia

Gentipo a estrutura do cromossomo, e pode ser

identificada na rea de GA com o termo estrutra.

Fentipo corresponde interao do contedo

gentico com o ambiente, interao esta que se d

no nosso campo atravs do conjunto de

parmetros do algoritmo.

Genoma o significado do pacote gentico e no

possui anlogo na rea de GA.

Resumo de terminologia

Linguagem natural GA

cromossomo indivduo,string, cromossomo,

rvore

gen caracterstica

alelo valor

locus posio

gentipo estrutura

fentipo conjunto de parmetros

Caractersticas dos GAs

GAs so tcnicas probabilsticas, e no tcnicas

determinsticas.

Iniciando um GA com a mesma populao inicial

e o mesmo conjunto de parmetros podemos

encontrar solues diferentes a cada vez que

executamos o programa.

GAs so em geral programas extremamente simples que

necessitam somente de informaes locais ao nosso ponto

Informaes relativas adequabilidade do ponto como

soluo do problema em questo

No necessitam de derivadas ou qualquer outra

informao adicional.

Extremamente aplicveis a problemas do mundo real

que em geral incluem descontinuidades duras.

Caractersticas dos GAs

GAs trabalham com uma grande populao de pontos, sendo uma heurstica de busca no espao de solues.

Um GA diferencia-se dos esquemas enumerativos pelo fato de no procurar em todos os pontos possveis, mas sim em um (qui pequeno) subconjunto destes pontos.

GAs diferenciam-se de esquemas aleatrios por serem uma busca que utiliza informao pertinente ao problema e no trabalham com caminhadas aleatrias (random walks) pelo espao de solues.

GAs trabalham com uma forma codificada dos parmetros a serem otimizados e no com os parmetros propriamente ditos .

Caractersticas dos GAs

Por que GAs?

GA uma tcnica de busca com as seguintes caractersticas positivas, que fazem com que eles devam ser considerados:

Paralela

Global

No totalmente aleatrios

No afetada por descontinuidades na funo ou em suas derivadas

Capaz de lidar com funes discretas e contnuas

Boas tcnicas para atacar problemas de busca com espaos de busca intratavelmente grandes, que no podem ser resolvidos por tcnicas tradicionais.

Teorema da Inexistncia do

Almoo Grtis

Todos os algoritmos de busca tm exatamente o

mesmo desempenho, quando faz-se a mdia

atravs de todos os infinitos problemas possveis

Nenhum algoritmo genrico pode ser melhor do

que um algoritmo desenhado especificamente para

a resoluo de um problema.

Argumento poderoso contra o uso algoritmos

genricos de busca

Conseqncias:

Um bom GA deve embutir o mximo de conhecimento sobre o problema, na representao, nos operadores genticos e na funo de avaliao.

Problemas que j foram resolvidos ou problemas que tenham algoritmos especficos j desenvolvidos no merecem ser atacados usando-se GAs, s porque seria divertido ou porque voc gosta de tcnicas evolucionrias.

GAs devem ser uma ferramenta adicional, no como a nica do seu cabedal de tcnicas e com certeza seus resultados sero ainda melhores.

Teorema da Inexistncia do

Almoo Grtis