Algoritmos Genéticos: Conceitos e Fundamentos

Prévia do material em texto

Algoritmos Genéticos
Conceitos
� Segundo John Holland(1970) algoritmos 
genéticos são modelos computacionais que 
imitam os mecanismos da “evolução natural” 
para resolver problemas de otimização.para resolver problemas de otimização.
2
� Algoritmos genéticos (AG’s) são métodos
computacionais de busca baseados nos mecanismos
Conceitos
computacionais de busca baseados nos mecanismos
de evolução natural e na genética. Num AG uma
população de possíveis soluções para o problema em
questão evolui de acordo com operadores
probabilísticos concebidos a partir de metáforas
biológicas, de modo que há uma tendência de que, nabiológicas, de modo que há uma tendência de que, na
média, os indivíduos representem soluções cada vez
melhores à medida em que o processo evolutivo
continua (Tanomaru, 1995).
3
Motivações
� Como explicar a diversidade dos animais?
� Como explicar sua evolução?
� Qual é a influência das populações anteriores?
� Qual é a influência do meio ambiente?
4
Curiosidades
� O Urso Polar é BRANCO porque vive na 
NEVE?NEVE?
ou
� O Urso Polar vive na NEVE porque é 
BRANCO?
5
� 1809: Jean-Baptiste Lamarck
Lei do uso e do desuso.
História da Teoria da Evolução
� Lei do uso e do desuso.
� pelo uso e desuso de suas aptidões, a natureza força os seres a se 
adaptarem para sobreviverem.
� Lei dos caracteres adquiridos. 
� Os serem mais fortes são mais capazes de “trasmitir” suas aptidões 
às novas gerações.
6
� 1859: Charles Darwin
História da Teoria da Evolução
� 1859: Charles Darwin
� É pela lei da Seleção Natural
que os seres mais adaptados ao 
seus ambientes sobrevivem.
� Contra lei do uso de desuso.
� Os caracteres adquiridos são � Os caracteres adquiridos são 
herdados pelas gerações 
seguintes.
� O homem vem do macaco...
7
� 1865: Gregor Mendel 
Formalizou a “herança de características”, com a 
História da Teoria da Evolução
� Formalizou a “herança de características”, com a 
teoria do DNA (ervilhas). 
� 1901: Hugo De Vries
� Só a seleção natural não é responsável pela 
produção de novas (mais adaptadas) espécies. 
Tem que haver uma mudança genética!Tem que haver uma mudança genética!
� Formalizou o processo de geração de diversidade:
Teoria da Mutação.
8
“...Se variações úteis para qualquer organismo 
devam ocorrer para que ele venha a existir, 
Teoria da Seleção Natural
devam ocorrer para que ele venha a existir, 
certamente indivíduos assim caracterizados 
terão a melhor chance de serem preservados 
na luta por sobrevivência; e do forte princípio de 
hereditariedade, eles tenderão a produzir 
gerações com características similares. Este 
princípio de preservação, eu batizei, para ser princípio de preservação, eu batizei, para ser 
sucinta, de Seleção Natural.”
(Darwin, 1859)
9
Evolução natural
� A evolução natural pode ser vista como um � A evolução natural pode ser vista como um 
processo de otimização no qual:
� Indivíduos e populações competem entre si por 
recursos
� Alimento
� Água� Água
� Abrigo
10
Evolução natural
� Indivíduos mais bem sucedidos na sobrevivência e � Indivíduos mais bem sucedidos na sobrevivência e 
atração de um parceiro terão, relativamente, mais 
descendentes (espalham seus genes).
� Indivíduos mal sucedidos geram poucos ou nenhum 
descendente.descendente.
11
Curiosidades
� O Urso Polar é BRANCO porque vive na 
NEVE?NEVE?
ou
� O Urso Polar vive na NEVE porque é 
BRANCO?
Que teorias poderíamos Que teorias poderíamos Que teorias poderíamos Que teorias poderíamos 
12
Que teorias poderíamos Que teorias poderíamos Que teorias poderíamos Que teorias poderíamos 
inferir?inferir?inferir?inferir?
Lamarck? Darwin?Lamarck? Darwin?Lamarck? Darwin?Lamarck? Darwin?
Algoritmos Evolucionários
Algoritmo Genético Codificação Binária
Ambientação
Teoria de 
Computação 
Evolutiva
Modelo
Biológico
Evolutiva
Modelo
Computacional
Natureza
Teoria de Darwin 14
Algoritmos Genéticos
� Desenvolvido por John Holland e sua equipe 
em 1975 e popularizado por David Goldberg.em 1975 e popularizado por David Goldberg.
� Objetivo:
� Desenvolver sistemas artificiais baseados nos 
mecanismos dos sistemas naturais.
� O processo de evolução executado por um 
algoritmo genético corresponde a um processo algoritmo genético corresponde a um processo 
de busca em um espaço de soluções potenciais 
para alcançar o objetivo proposto.
15
Terminologia Biológica
� Em Algoritmos Genéticos são utilizados termos 
biológicos como analogia com a biologia.biológicos como analogia com a biologia.
� Cromossomo: codificação de uma possível solução –
indivíduo.
� Genes: codificação de uma característica particular.
� Genótipo� Genótipo
� Conjunto de parâmetros representado por um cromossomo.
� Fenótipo
� Produto da interação de todos os genes com o meio. 16
Fundamentos
� Seleção natural
Processo através do � Processo através do 
qual características 
biológicas se tornam 
mais ou menos comuns 
em uma população 
devido a efeitos 
consistentes sobre a consistentes sobre a 
sobrevivência e a 
reprodução de seus 
portadores.
� “Sobrevivência dos 
mais aptos” 17
Fundamentos
� Genótipo
� Conjunto de genes de um � Conjunto de genes de um 
organismo
� Determina as características 
hereditárias (genética herdada)
� Fenótipo
� Conjunto de características 
observáveis de um organismo
� Resultado da iteração do 
genótipo com o ambiente
� Valor de uma caracterísitca.
18
Fundamentos
� Recombinação Genética
Processo através do � Processo através do 
qual uma molécula de 
ácido nucleico é 
quebrada e então unida 
a uma outra.
� Crossing-over
� Troca de material 
genético entre 
cromossomos 
homólogos
� Ocorre durante a 
meiose
19
Fundamentos
� Mutação
� São mudanças súbitas e 
espontâneas na sequência espontâneas na sequência 
genética
� São causadas por radiação, vírus, 
substâncias químicas 
mutagênicas, ou por erros durante 
a meiose ou a replicação do DNA
20
Síndrome de Down:
Distúrbio genético causado pela 
presença de um cromossomo 21 extra, 
total ou parcialmente.
É o distúrbio genético mais comum, 
estimado em 1 a cada 1000 nascimentos.
Curiosidades
... apenas um par de nucleotídeos em mil sofre uma alteração 
aleatória a cada 200 mil anos. Ainda assim, em uma população de 
10 mil indivíduos, cada substituição possível de nucleotídeo terá 
sido "tentada" em mais ou menos 50 ocasiões no curso de um 
milhão de anos, o que não é muito em relação à evolução das 
espécies. Grande parte da variação criada desta forma será 
prejudicial para o organismo e desaparecerá através da seleção 
natural na população. Quando uma rara seqüência variante for 
vantajosa, ela se propagará rapidamente pela seleção natural.
... Conseqüentemente, pode-se esperar que, em qualquer espécie, ... Conseqüentemente, pode-se esperar que, em qualquer espécie, 
as funções da maioria dos genes sejam otimizadas pela mutação 
aleatória e pela seleção.
“ Molecular Biology of the Cell” (Fifth edition) – Publishing: Taylor & Francis
Authors: Bruce Alberts, Alexander Johnson, Julian Lewis, Martin Raff, Keith
Roberts, Peter Walter 21
Estrutura de um AG
22
Genótipo
� População
� Conjunto de N indivíduos� Conjunto de N indivíduos
� Indivíduo
� Caracterizado por seu 
genótipo
� Em geral, um indivíduo 
tem um cromossomo
� Genótipo
� n genes binários
� Número relacionado à 
precisão
23
Fenótipo
� Fenótipo
� Determinado pelo modelo 1 0 1 0 0 1
6 5 4 3 2 1
� Determinado pelo modelo
� Se as variáveis são 
inteiras ou reais, requer 
conversão
� Inteiro
1 0 1 0 0 1
32 16 8 4 2 1
32 0 8 0 0 1 = 41
� Real Qual o maior número que se pode escrever com 
n bits?
24
Conversão
n-1 n-2 ... 3 2 1n
Qual o maior número INTEIRO que se pode escrever com n bits?
1 1 1 ... 1 11
0 0 0 ... 0 00
n-1 n-2 ... 3 2 1n
1
n+1
25
Conversão
a b
0 2n-1x~
x
Para que o espaçamento entre dois pontos não seja maior que 10-6, quando a 
variável está limitada ao intervalo [-1,2], quantos bits devem ser utilizados?
26
Exemplo paran=16 bits:
Transformação binário => base decimal Transformação base decimal (inteiro) => 
número real discreto em um intervalo [a,b]
Aptidão
� Aptidão (ai)
� Para cada indivíduo, � Para cada indivíduo, 
determinada pelo valor da 
função objetivo diante dos 
demais indivíduos
� A população é ordenada 
de acordo com o valor da 
função objetivofunção objetivo
� Para minimização, ordem 
crescente
� Para maximização, ordem 
decrescente
27
Aptidão
Soma das Aptidões
Aptidão Relativa – Probabilidade de um indivíduo ser sorteado
ou selecionado dentre uma população e aptidão estabelecida.
Aptidão Acumulada – Soma das aptidões relativas, que
28
Aptidão Acumulada – Soma das aptidões relativas, que
determina o intervalo que este indivíduo possa vir a ser sorteado,
quando realizado um sorteio aleatório.
Seleção
� Maior aptidão, maior 
chance de reproduçãochance de reprodução
� Roleta
� Convencional: todos os 
números tem a mesma 
chance
� “Genética”: cada � “Genética”: cada 
indivíduo tem chance 
proporcional à sua 
aptidão.
29
Roleta
NN-1
0
N
12
(N(N+1)/2)/S
= S/S = 1
(N(N+1)/2-1)/S
A roleta apresentada é considerada
“viciada”, visto que as casas são
distribuídas conforme a aptidão de
cada indivíduo, onde o círculo verde
1
2
NN-1
N/S
(2N-1)/S
N-1
N cada indivíduo, onde o círculo verde
escuro ao meio apresenta os
indivíduos da população ordenados
de 1 a N conforme as aptidões
situadas no circulo central que estão
ordenados de N até 1. As aptidões
acumuladas estão representadas no
círculo azul claro externo.
3
(3N-3)/S
N-2
30
Obs.: somatório das 
aptidões relativas tem de 
ser igual a 1.
Reprodução
� Cruzamento
Dois tipos principais� Dois tipos principais
� Ponto simples
� Ponto duplo
� Probabilidade de cruzamento
� pcross ~ 85%
� Mutação
� Executada sobre um bit
� pmut ~ 1% 31
Cruzamento (cross-over)
Por ponto simples
1 0 1 0 0 1
1 0 0 1 1 0
1 0 1 0
0 11 0 0 1
1 0
6 5 4 3 2 1
32
Cruzamento (cross-over)
Por ponto duplo
1 0 1 0 0 1
1 0 0 1 1 0
1
0 1 0
0 1
1
0 0 1
1 0
6 5 4 3 2 1
33
Mutação
1 0 1 0 1 0 1 1 1 0 1 0
6 5 4 3 2 1
0 11 0 0 1 0 01 0 0 1
6 5 4 3 2 1
34