Curso Online de ALGORITMOS GENÉTICOS

1

algoritmos genéticos

2

algoritmos evolucionários

algoritmos genéticos

3

algoritmos evolucionários

na última aula nós discutimos como a evolução natural conseguiu obter soluções mais avançadas para o problema da sobrevivência

os algoritmos evolucionários, dos quais os gas são um ramo, procuram usar o mesmo método da natureza na busca de soluções a problemas de difícil solução.
os algoritmos evolucionários funcionam mantendo uma população de estruturas que evoluem de forma semelhante à evolução das espécies.
a estas estruturas são aplicados os chamados operadores genéticos, como recombinação e mutação, entre outros.
cada indivíduo recebe uma avaliação que é uma quantificação da sua qualidade como solução do problema em questão
baseados nesta avaliação serão aplicados os operadores genéticos de forma a simular a sobrevivência do mais apto.

algoritmos genéticos

4

algoritmos evolucionários

t:=0 // inicializamos o contador de tempo
inicializa_população p(0) // inicializamos a população randômicamente
enquanto não terminar faça //condição de término:por tempo, por avaliação, etc.
avalie_população p(t) //avalie a população neste instante
p':=selecione_pais p(t) //selecionamos sub-população que gerará nova geração
p'=recombinação_e_mutação p' //aplicamos os operadores genéticos
avalie_população p' //avalie esta nova população
p(t+1)=selecione_sobreviventes p(t),p' //selecione nova geração
t:=t+1 //incrementamos o contador de tempo
fim enquanto

o esquema básico de um algoritmo evolucionário pode ser visto no pseudo-código abaixo:

algoritmos genéticos

5

ae buscam dentro da atual população aquelas soluções que possuem as melhores características e tentar combiná-las de forma a gerar soluções ainda melhores
o processo é repetido até que tenha se passado tempo suficiente ou que tenhamos obtido uma solução satisfatória para nosso problema.
ae são extremamente dependente de fatores estocásticos (probabilísticos), tanto na fase de inicialização da população quanto na fase de evolução (durante a seleção dos pais, principalmente).
isto faz com que os seus resultados raramente sejam perfeitamente reprodutíveis.
ademais, claramente os algoritmos evolucionários são heurísticas que não garantem a obtenção do melhor resultado possível em todas as suas execuções.

algoritmos evolucionários

algoritmos genéticos

6

algoritmos evolucionários

conclusão: se você tem um algoritmo com tempo de execução razoável para solução de um problema, então não há nenhuma necessidade de se usar um algoritmo evolucionário.

sempre dê prioridade aos algoritmos exatos.

os algoritmos evolucionários entram em cena para resolver aqueles problemas cujos algoritmos são extraordinariamente lentos (problemas np-completos) ou incapazes de obter solução (como por exemplo, problemas de maximização de funções multi-modais, como veremos mais à frente).

algoritmos genéticos

7

algoritmos genéticos

sub-área dos algoritmos evolucionários.
logo, são uma metáfora para a evolução natural.
os algoritmos genéticos são técnicas heurísticas de otimização global.
com isto, raramente eles ficam presos em máximos locais como as técnicas de hill-climbing.
lembrando máximos locais:

algoritmos genéticos

8

algoritmos genéticos

nos algoritmos genéticos populações de indivíduos são criados e submetidos aos operadores genéticos
seleção
crossover
mutação.

estes operadores utilizam uma caracterização da qualidade de cada indivíduo como solução do problema em questão chamada de avaliação deste indivíduo (fitness)

será gerado então um processo de evolução natural destes indivíduos

algoritmos genéticos

9

algoritmos genéticos

ao contrário do que as pessoas costumam pensar, é importante ser ressaltado que a evolução natural não é um processo dirigido à obtenção da solução ótima.

na verdade, o processo simplesmente consiste em fazer competir uma série de indivíduos e pelo processo de sobrevivência do mais apto, os melhores indivíduos tendem a sobreviver.

um ga é similar à evolução natural : a competição entre os indivíduos é que determina as soluções obtidas.

eventualmente, devido à sobrevivência do mais apto, os melhores indivíduos prevalecerão.

algoritmos genéticos

10

algoritmos genéticos

importante sempre ter em mente que, apesar do seu nome, algoritmos genéticos não são algoritmos, mas sim heurísticas.

logo, nem sempre a melhor solução será encontrada.

entretanto, normalmente boas soluções para o problema em questão são encontradas a cada execução.

algoritmos genéticos

11

algoritmos genéticos

passos para a solução de um problema:
encontrar uma maneira de condificar o problema
definir os operadores genéticos
definir uma função de avaliação para medir a capacidade de sobrevivência de cada indivíduo.

vamos devagar, passo a passo!