Cap 02 - Algoritmos Geneticos - Parte01 (1)

Prévia do material em texto

Algoritmos Genéticos 
Algoritmos Genéticos 
 O que são os Algoritmos Genéticos (AGs) ? 
 É uma ferramenta (de otimização) para a solução de 
problemas de busca. 
 É uma técnica computacional inspirada na natureza. 
 É um algoritmo evolutivo. 
 É uma técnica de otimização estocástica geral. 
 Se baseia na Teoria da Seleção Natural e na Genética. 
Algoritmos Genéticos 
 Qual a relação do AG com a Genética e a Evolução 
Natural ? 
 É uma técnica computacional inspirada na natureza. 
 Se baseia na Teoria da Seleção Natural e na Genética. 
 Evolução 
 Indivíduo 
 Cromossoma 
 Reprodução Sexual 
 Mutação 
 População 
 Gerações 
 Meio-Ambiente 
 Algoritmos Genéticos 
 Solução 
 Representação 
 Operador Cruzamento 
 Operador Mutação 
 Conjunto de Soluções 
 Ciclos 
 Problema 
Algoritmos Genéticos 
 Qual a finalidade do AG ? 
 Solucionar problemas complexos por 
meio de um processo adaptativo e 
paralelo de busca. 
Algoritmos Genéticos 
 Características básicas do funcionamento do 
AG 
• Adaptativo 
– informação corrente influencia a busca futura 
• Paralelo 
– várias soluções consideradas a cada momento 
• Problema Complexo 
– de difícil formulação matemática ou com grande espaço 
de busca (grande número de soluções) 
 Onde utilizar o AG ? 
Problema Complexo 
Exemplo: 
Maximizar f (x) = x2 : encontrar x  (0 ... 2 L -1) para f(x)=máx 
2
L
 Número de Pontos 
no Espaço 
Tempo de Busca 
 
L=3 
 
8 
 
< 1 seg 
 
L=10 
 
1024 
 
< 1 seg 
 
L=30 
 
1 bilhão 
 
1 seg 
 
L=90 
 
10 
27
 
 
15 bilhões de 
anos 
 
Fonte: www.ica.ele.puc-rio.br/strictosensu/index.rails?name=Stricto%20Sensu 
Problema da Cabra Cega 
Fonte: www.ica.ele.puc-rio.br/strictosensu/index.rails?name=Stricto%20Sensu 
xB xA 
yA 
y B 
tesouro y 
x 
B 
C 
D 
E 
cruzamento 
(xB ,yA ) 
F 
A 
G 
(xA ,yB ) 
Algoritmos Genéticos 
 Operações Básicas de um AG 
 Seleção: privilegia os indivíduos mais aptos 
 Reprodução: indivíduos (ex: palavras binárias) 
são reproduzidos com base na aptidão 
 Crossover: troca de genes (pedaços de palavras) 
 Mutação: troca aleatória de um gene (bit da 
palavra) 
Algoritmos Genéticos 
 Como opera um AG em termos computacionais ? 
Algoritmos Genéticos 
 Componentes Básicos de um AG 
 Definição do problema. 
 Representação das variáveis que resolvem o 
problema. 
 Definição de uma medida de avaliação. 
 Definição da forma de seleção a ser utilizada 
 Definição dos operadores genéticos a serem 
utilizados. 
 Definição dos parâmetros do AG. 
Problema 
AGs são indicados para resolver problemas 
de otimização complexos 
 muitas variáveis 
 muitos parâmetros 
 mal estruturados: com condições e restrições difíceis 
de serem modeladas matematicamente 
 grande espaço de busca 
Representação 
 A representação é fundamental na 
modelagem do AG 
 A representação deve: 
 descrever o espaço de busca relevante do problema 
 codificar geneticamente a “essência” do problema 
 A evolução do código genético  evolução da solução 
 ser compatível com os operadores genéticos 
(cruzamento e mutação) 
 
 Uma adequada representação  sucesso no 
processo de busca por meio da evolução ! 
Tipos de Representação 
Binária: 
Binária codificando um número real: 
decodificação 
 Inteira: 
 Real: 
 Estruturas: vetores, listas, matrizes, strings, 
etc 
0 0 1 1 1 
7 4 1 2 8 
-4,2 1,6 8,9 -1,3 14,7 
Representação Binária codificando um 
número real 
 O número binário é um contador das unidades 
mínimas de precisão 
 Aspectos importantes: 
 variáveis do problema (x1, x2, ... , xn) 
 domínio de valores: xi  (mini, maxi) em R 
 precisão: p casas decimais 
mini maxi Precisão 1/10p 
Domínio de xi 
(maxi – mini) x 10
p 
Representação Binária codificando um número real 
 Representação: k2 bits k3 bits ... kt bits k1 bits 
x1 x2 x3 xt 
onde 
 Decodificando para real: 
Se xibinário = (0 0 0 ... 0)  xiinteiro = 0  xireal = mini 
Se xibinário = (1 1 1 ... 1)  xiinteiro = 2
ki -1  xireal = maxi 
 
Representação Binária 
 Características: 
 simples de criar e manipular 
 facilita a aplicação dos operadores 
genéticos (cruzamento e mutação) 
 fácil decodificação numérica (para 
inteiro e real) 
 facilita a demonstração de teoremas ! 
 porém, nem sempre é a mais adequada 
para o problema 
Decodificação 
 Construir a solução para o problema a partir de um 
cromossomo 
 o cromossomo de cada indivíduo da população representa 
uma possível solução 
CROMOSSOMO DECODIFICAÇÃO SOLUÇÃO 
 Binário p/ Inteiro 
OO11O11 0x26+0x25+1x24+1x23+... x=27 
 Binário p/ Real 
OO11O11 x=(27x(10/27))-1 x=2,1 
 x [0,10] 
 precisão de 1 casa decimal 
ADBCE AD = 3Km SomaDistancias=18Km 
 DB=1Km ADBCEA 
 BC=4Km 
 CE=3Km 
 EA=7Km 
Avaliação 
 Elo entre o AG e o problema 
 Originalmente foi desenvolvida como 
sendo proporcional a aptidão do 
cromossomo 
 A chance de um indivíduo ser selecionado 
é proporcional a sua aptidão (nem sempre 
avaliação é igual a aptidão) 
f(cromossomo) = medida numérica da aptidão 
Avaliação (Exemplo) 
 Problema: 
Achar o valor máximo para f (x) = x2 , x no limite de 0 a 
63. 
 
 Representação da Solução: 
Palavras binárias representando sucessivas potências de 
2. 
 
 011100  Representa 28 
 110101  Representa 53 (uma solução mais apta) 
Avaliação (Exemplo) 
 População 
Cromossoma Palavra 
A 
B 
C 
D 
100100 
010010 
010110 
000001 
X 
36 
18 
22 
 1 
Aptidão (x2 ) 
1296 
324 
484 
1 
 OBS: Avaliação é igual a aptidão 
Seleção 
 População 
Cromossoma Palavra 
A 
B 
C 
D 
100100 
010010 
010110 
000001 
X 
36 
18 
22 
 1 
Aptidão (x2 ) 
1296 
324 
484 
1 
Partic. Seleção 
 = 2105 
0,6156 
0,1539 
0,2301 
0,0004 
Seleção por Roleta proporcional a 
Aptidão 
A 
D 
C 
B 
 Probabilidade 
 de Seleção 
 Aptidão do 
Cromossomo 
 
Operadores Genéticos 
 Atuam no processo de criação de 
novos indivíduos (descendentes) 
 Cruzamento 
 Mutação 
Cruzamento e Mutação: para 
representação binária 
Mutação 
1 0 1 0 1 1 1 0 1 0 0 0 
0 0 1 1 0 0 0 0 1 1 1 1 
Pais Filhos 
Antes 
Depois 
 0 0 1 1 1 1 
 0 0 0 1 1 1 
Cruzamento 
Lembrança: Operações Básicas 
 Seleção: privilegia os indivíduos mais aptos 
 Reprodução: indivíduos (ex: palavras binárias) 
são reproduzidos com base na aptidão 
 Cruzamento: troca de genes (pedaços de 
palavras) 
 Mutação: troca aleatória de um gene (bit da 
palavra) 
Ciclo do Algoritmo Genético 
 
 
Cromossoma Palavra Aptidão 
A 100100 1296 
B 010010 324 
C 010110 484 
D 000001 1 
f( ) 
Pais 
Reprodução Filhos 
Avaliação 
dos Filhos 
Crossover 
Mutação 
Ciclo do Algoritmo Genético 
procedure algoritmo_genético 
begin 
 t = 0 ;primeira geração 
 inicializa P(t) ;população inicial aleatória 
 avalia P(t) ;calcula f(i) p/ cada indivíduo 
 while (not condição_parada) do 
 begin 
 t = t + 1 ;próxima geração 
 seleciona P(t) de P(t-1) 
 altera P(t) ;crossover e mutação 
 avalia P(t) ;calcula f(i) p/ cada indivíduo 
 end 
end 
Desempenho do AG 
Melhor Indivíduo
0
5000
10000
15000
20000
25000
30000
1 7
1
3
1
9
2
5
3
1
3
7
4
3
4
9
Gerações
f(
t)
AG 
 Vantagens 
 
 Técnica de busca global 
(evita mínimos locais) 
Otimização de 
problemas complexos e 
mal estruturados 
Dispensaformulação 
matemática precisa do 
problema 
 Desvantagens 
 
 Precisão na 
representação do 
cromossoma 
 Evolução demorada em 
alguns problemas 
Modelagem depende do 
habilidade do especialista 
em AG 
Parâmetros do AG 
 Tamanho da População 
 Número de Gerações: número de ciclos do AG 
 Número Total de Indivíduos manipulados: 
Tamanho da População x Número de Gerações 
 Taxa de Cruzamento 
 Taxa de Mutação 
 etc 
Algumas Variações no AG 
 Técnica de Inicialização da População: 
aleatória, em domínio específico, com viés, etc 
 Tipo de Seleção: roleta ponderada, 
amostragem estocástica uniforme, torneio, etc 
 Tipo de Cruzamento: um ponto de corte, dois 
pontos de corte, uniforme, etc 
 Técnica de Elitismo: elitismo singular e estado 
estacionário 
 etc 
Implementar o AG: auxílio 
 BEAGLE-A Generic Evolutionary Computation Framework in C++ 
(https://code.google.com/p/beagle/) 
 GAlib-C++ Library of Genetic Algorithm Components 
(http://lancet.mit.edu/ga/) 
 GAUL-Genetic Algorithm Utility Library C++ 
(http://gaul.sourceforge.net/) 
 Pyevolve-GAbyPython 
(https://pypi.python.org/pypi/Pyevolve/0.5) 
 DEAP-Distributed Evolutionary Algorithms in Python 
(http://deap.readthedocs.org/en/master/) 
 GALib- Java Genetic Algorithm Library (http://java-
galib.sourceforge.net/) 
 JGAL-Java Genetic Algorithm Library 
(http://jgal.sourceforge.net/) 
http://deap.readthedocs.org/en/master/
http://java-galib.sourceforge.net/
http://java-galib.sourceforge.net/
http://java-galib.sourceforge.net/
Implementar o AG 
 Problema: encontrar o máximo da função 
F6(x,y) 
 Domínio: x,y  [-100, +100] 
 Precisão: 5 casas decimais para x e y 
 Representação: binário codificando real 
 Número de bits para x: 
 
 
F6(x,y) 
F6(x,y) 
Implementar o AG 
 Máximo da função F6(0,0) = 1 
 dificuldade: vários máximos locais 
 dificuldade: mais do que pontos de máximos locais, 
existem ‘regiões’ de máximos locais 
 dificuldade: existe uma “quase” decepção nas 
proximidades do máximo global 
Implementar o AG - Exemplo 
 Cromossoma: 
 00001010000110000000011000101010001110111011 
 Dividido em x e y: 
 0000101000011000000001 1000101010001110111011 
 Convertidos para base 10: 
 165377 e 2270139 
 Multiplicados por: 200/222-1 (nesse caso são 22 bits, para 
precisão de 4 casas decimais) 
 7,885791751335085 e 108,24868875710696 
 Subtraídos de mín: 
 x=-92,11420824866492 e y=8,248688757106959 
 Aplicados a F6(x,y): 
 F6(x,y)=0,5050708 
Implementar o AG - Customização 
 Técnica de Inicialização da População: Aleatória 
 Geração aleatória de palavras de 50 bits 
 Técnica de Eliminação da População: Elimina todos 
 Elimina tam_pop indivíduos da população anterior 
 Técnica de Reprodução: Troca da geração 
 Reproduz tam_pop indivíduos para a nova população 
 Técnica de Aptidão: Aptidão é a avaliação 
 Aptidão é numericamente igual à avaliação 
 Técnica de Seleção de Genitores: Roleta 
 Técnica de Cruzamento: de um ponto de corte 
 taxa de cruzamento = 75% 
 Técnica de Mutação: bit a bit 
 taxa de mutação = 1% 
Implementar o AG - Parâmetros 
 Tamanho da População: fixa 
 100 indivíduos 
 Número de Gerações: critério de parada 
 100 gerações 
 Número total de indivíduos manipulados: 
 100 indivíduos x 100 gerações = 10000 indivíduos 
 Taxa de Cruzamento: 0,75 
 Taxa de Mutação: 0,01 
Implementar o AG - Observação 
 Tamanho da População: fixa 
 1000 indivíduos 
 Número de Gerações: critério de parada 
 10 gerações 
 Número total de indivíduos manipulados: 
 100 indivíduos x 100 gerações = 10000 indivíduos 
 Taxa de Cruzamento: 0,75 
 Taxa de Mutação: 0,01 
Implementar o AG - Observação 
 Tamanho da População: fixa 
 10 indivíduos 
 Número de Gerações: critério de parada 
 1000 gerações 
 Número total de indivíduos manipulados: 
 100 indivíduos x 100 gerações = 10000 indivíduos 
 Taxa de Cruzamento (Tc): 0,75 
 Taxa de Mutação (Tm): 0,01 
 
 OBS: os valores ideais de Tc e Tm são encontrados 
experimentalmente ! 
Vizualização do desempenho do AG 
Seleção pela Roleta 
 Objetivo: Selecionar indivíduos aleatoriamente, 
proporcionando maiores chances de reprodução aos mais 
aptos. 
 Método pelo Computador 
 Crie uma lista de todos os indivíduos da população em ordem 
crescente de posição na população (não é ordenado pela aptidão !), 
com a informação de aptidão associada; 
 Encontre a soma das aptidões de todos os indivíduos da 
população de forma crescente, do primeiro ao último indivíduo (no 
último indivíduo, tem-se o valor total da soma das aptidões AT); 
 Gere um número aleatório, rand, entre 0 e AT; 
 Pegue o primeiro membro da população cuja aptidão somada às 
aptidões dos membros precedentes é maior ou igual a rand. 
Exemplo da Roleta 
1 2 3 4 5 6 7 8 9 10 
8 2 17 7 2 12 11 7 3 7 
8 10 27 34 36 48 59 66 69 76 
Cromossoma 
Aptidão 
Ai 
23 49 76 13 1 27 57 
3 7 10 3 1 3 7 
Número Aleatório 
Indivíduo Selecionado 
Cruzamento 
 Cruzamento de um ponto de corte: Partes de dois 
cromossomas genitores são trocadas a partir de uma 
posição escolhida aleatoriamente 
 Taxa de Cruzamento: Tc = 0,75 (75%) 
• Teste Verdadeiro  efetua cruzamento 
• Teste Falso  copia os genitores 
 (ou faz uma nova seleção!) 
1 0 1 1 0 1 
0 0 1 1 0 0 
1 0 1 1 0 0 
0 0 1 1 0 1 
P1 
P2 
F1 
F2 
Ponto de corte aleatório 
Mutação 
 Mutação: Troca cada gene de um cromossoma se o 
teste de probabilidade for verdadeiro 
 Taxa de Cruzamento: Tc = 0,01 (1%) 
• Teste Verdadeiro  troca bit 
• Teste Falso  mantém bit 
1 0 1 0 
0,81 0,11 0,26 0,35 
1 0 1 1 
Cromossoma 
Número Aleatório 
Novo Cromossoma 
1 1 0 0 
0,21 0,961 0,005 0,84 
1 1 1 0 
Cromossoma 
Número Aleatório 
Novo Cromossoma 
Evolução x Convergência 
 Cruzamento 
 acelerador do processo de busca 
 tira proveito das soluções mais promissoras 
 Mutação 
 operador exploratório 
 dispersa a população pelo espaço de busca 
 Convergência (Causas) 
 população com indivíduos muito similares 
 não há mais evolução 
 ótimo encontrado ou convergência prematura (ótimo local) 
 existência da evolução é sinônimo de diversidade na pop. 
Análise de Desempenho 
 Melhor de um experimento (um valor) 
 Curva dos Melhores indivíduos por geração em um 
experimento 
 Curva da Média do Melhores indivíduos de vários 
experimentos 
 em cada experimento em tenho um Melhor diferente 
 em cada experimento em tenho uma Curva dos Melhores 
diferente 
OBS: o conjunto de experimentos mostra o 
comportamento médio do AG 
Análise de Desempenho 
 AG é um método com forte característica estocástica 
 As curvas de desempenho variam para cada 
experimento 
 A população inicial tem algum impacto no 
comportamento do AG 
 São necessários vários experimento para se conhecer o 
desempenho médio do AG 
 gerar aproximadamente 50 experimentos com a mesma 
população inicial 
 repetir para aproximadamente 50 populações iniciais 
diferentes 
Análise de Desempenho – Média dos 
Experimentos 
Melhores nas Gerações 
Experimentos 
Geração 1º. 2º. 3º. 4º. Média 
Ger. 1 0,6 0,5 0,8 0,5 0,6 
Ger. 2 
 
0,7 0,5 0,8 0,7 0,675 
Ger. 3 
 
0,7 0,6 0,9 0,7 0,725 
Ger. 4 
 
0,8 0,6 0,9 0,8 0,775 
Característica da Curva de Desempenho 
 AG é um método com forte característica estocástica 
 As curvas de desempenho variam para cada experimento 
Mudanças no AG Padrão 
 Medidas de Aptidão 
 Nem sempre a Aptidão é a Avaliação 
 Elitismo 
 Estado Estacionário 
 Parâmetros variando entre gerações 
 Tc, Tm, etc 
Medidas de Aptidão 
 O que ocorre se alterarmos a F6 para: 
 Formato da Curva 3D de F6 = Formato de F6-elevada 
Melhor indivíduo para F6 = Melhor indivíduo paraF6-
elevada 
 Avaliação de F6-elevada = Avaliação de F6 + 999 
 entretanto o AG para F6-elevada tem baixo desempenho 
Aptidão = Avaliação 
Ai = fi ; aptidão do indivíduo i 
 pi = Ai / AT = fi / fj ; chances de seleção do indivíduo i 
 há tam_pop sorteios na roleta 
 Di = pi x tam_pop ; número provável de sorteios de i 
 Di = (fi / fj) x tam_pop = fi x (tam_pop) / fj) 
 Di = fi / fMe ; número provável de descendentes 
 de i na próxima geração 
 fMe é a aptidão média da população 
Aptidão = Avaliação – Um exemplo 
 DMelhor = 1,9046 
 DPior = 0,1284 
 Forte pressão seletiva 
em favor do Melhor 
F6 Avaliação 
Melhor 0,979 
Pior 0,066 
Média 0,514 
 DMelhor = 1,00046 
 DPior = 0,99955 
 Melhor e Pior indivíduos 
irão gerar o mesmo 
número de descendentes 
F6-elevada Avaliação 
Melhor 999,979 
Pior 999,066 
Média 999,514 
Para F6-elevada o efeito da seleção é quase nulo porque 
as avaliações estão relativamente muito próximas 
Medidas de Aptidão: Normalização Linear 
 Objetivo: atribuir valores a Ai baseados no rank do 
indivíduo 
 Coloque os tam_pop indivíduos em ordem decrescente 
de avaliação (i=1 é o menos apto). 
 Crie aptidões, partindo de um valor mín e crescendo 
linearmente até um valor máx. 
 Os valores de máx e mín (ou a constante de incremento) 
são parâmetros da técnica. 
 Quanto maior a constante de incremento, maior a 
pressão seletiva sobre os melhores. 
Normalização Linear: um Exemplo 
 Super Indivíduo: cromossomo 6 
 poucas chance de recombinação com outros indivíduos; elimina 
competidores em poucas gerações; rápida convergência. 
 Competição Próxima: entre cromossomas 3, 4 e 5 
 é preciso aumentar a pressão seletiva sobre os melhores. 
6 5 4 3 2 1 
200 9 8 7 4 1 
200 9 8 7 4 1 
60 50 40 30 20 10 
101 81 61 41 21 1 
Rank dos Indivíduos 
Avaliação original 
Aptidão é a Avaliação 
Normalização Linear: inc=10 
Normalização Linear: inc=20 
Elitismo 
 O Melhor indivíduo da população P(t) é 
copiado para a população P(t+1) 
Garante que o Melhor indivíduo da 
próxima geração é melhor ou igual ao da 
geração anterior 
Reduz o efeito aleatório do processo 
seletivo 
O Melhor de P(t) substitui o Pior de P(t+1) 
Estado Estacionário 
 É a generalização do elitismo 
 Substituição parcial de indivíduos a cada 
geração (mais elitista) 
 Parte da população atual P(t+1) foi copiada da 
geração anterior P(t) 
Bons indivíduos (material genético) são 
preservados, garantindo mais chances de 
reprodução 
 GAP = fração da população que é copiada 
Estado Estacionário 
Método: 
 Crie n filhos (seleção+cruzamento+mutação) para 
P(t+1) 
 Elimine os n (determinado pelo valor de GAP) piores 
indivíduos da população P(t) 
 Copie os tam_pop-n melhores indivíduos da 
população P(t) para P(t+1) juntando com os n filhos 
 o valor de GAP determina a relação entre exploitation e 
exploration 
 Exploration: the action of traveling in or through an unfamiliar 
area in order to learn about it. 
 Exploitation: the action of making use of and benefiting from 
resources (Synonyms: making the most of, making use of). 
Estado Estacionário – Exemplo com duplicados 
I12 67 
I11 58 
I10 44 
I9 42 
I8 36 
I7 22 
I6 20 
I5 19 
I4 17 
I3 10 
I2 8 
I1 5 
I12 88 
I11 67 
I10 58 
I9 44 
I8 42 
I7 36 
I6 36 
I5 22 
I4 20 
I3 19 
I2 17 
I1 6 
F1 36 
F2 6 
F3 88 
F4 17 
I12 67 
I11 58 
I10 44 
I9 42 
I8 36 
I7 22 
I6 20 
I5 19 
F1 36 
F2 6 
F3 88 
F4 17 
População 
P(t) 
n filhos criados Substitui 
os n 
piores 
População 
P(t+1) 
ordenada 
Estado Estacionário sem duplicados 
 Substituição parcial de indivíduos com 
exclusão de duplicados 
Descendentes duplicados são desprezados 
Maior overhead para teste de igualdade 
 Maior eficiência do paralelismo de busca, 
garantindo pop_size indivíduos diferentes 
Tipos de Cruzamento Binário 
 Um Ponto de Corte 
 Dois Pontos de Corte 
 Múltiplos Pontos de Corte 
 Uniforme 
Cruzamento de Dois Pontos de Corte 
 Semelhante ao cruzamento de um ponto de corte 
 Dois pontos de corte são escolhidos aleatoriamente 
1 0 0 1 0 1 
0 1 1 1 0 0 
1 1 1 1 0 1 
0 0 0 1 0 0 
P1 
P2 
F1 
F2 
Pontos de corte aleatórios 
 Cruzamento de 1 ponto não consegue combinar 
todos os padrões de dois genitores 
Cruzamento Uniforme 
 A contribuição de cada genitor é decidida 
aleatoriamente por um padrão 
1 0 0 1 0 1 
0 1 1 1 0 0 
1 1 1 1 0 0 
0 0 0 1 0 1 
P1 
P2 
F1 
F2 
 Capacidade de combinar quaisquer padrões 
0 1 1 0 1 1 Padrão 
Impacto do Cruzamento e da Mutação 
 Operador Cruzamento considera características 
importantes presentes nos pais 
 Aplicado a uma taxa relativamente alta (Tm), mas 
cuidado com efeitos destrutivos  é a exploitation 
 Operador Mutação explora novas características 
nos indivíduos que seriam possivelmente úteis 
 Aplicado a uma taxa relativamente baixa (Tc), mas 
dependendo do problema e da geração use taxas 
mais altas  é a exploration 
Parâmetros x Desempenho 
 Convergência do AG x Diversidade do AG 
 Convergência: pode ser a proximidade dos indivíduos de um 
ótimo local 
 Variar os parâmetros do AG: exemplo – definir uma interpolação 
para Tc, Tm e inclinação da normalização linear (valor inicial, 
valor final, forma de variação e momento de ocorrer a variação) 
Representação por Números Reais 
 Números Reais: 
 Se o problema é de variáveis reais, então essa 
representação trabalhar diretamente no 
espaço de busca (é o caso da F6(x,y)) 
 Nesse caso, da F6(x,y), a representação 
binária trabalha em um espaço de busca 
fictício 
-4,2 1,6 8,9 -1,3 14,7 
Representação por Números Reais - 
Cruzamento 
 Cruzamento de um ponto: 
-4,2 1,6 8,9 -1,3 14,7 
9,3 -5,8 19,4 -2,1 -6,7 P2 
P1 -4,2 -5,8 19,4 -2,1 14,7 
9,3 1,6 8,9 -1,3 -6,7 F2 
F1 
Ponto de corte aleatório 
Representação por Números Reais - 
Cruzamento 
 Cruzamento de dois pontos: 
-4,2 1,6 8,9 -1,3 14,7 
9,3 -5,8 19,4 -2,1 -6,7 P2 
P1 9,3 -5,8 19,4 -1,3 14,7 
-4,2 1,6 8,9 -2,1 -6,7 F2 
F1 
Pontos de corte aleatório 
Representação por Números Reais - 
Cruzamento 
 Cruzamento Uniforme: 
-4,2 1,6 8,9 -1,3 14,7 
9,3 -5,8 19,4 -2,1 -6,7 P2 
P1 -4,2 1,6 8,9 -2,1 -6,7 
9,3 -5,8 19,4 -1,3 14,7 F2 
F1 
0 0 0 1 1 
Padrão 
Representação por Números Reais - 
Cruzamento 
 Cruzamento pela Média Aritmética: 
-4,2 1,6 8,9 -1,3 14,7 
9,3 -5,8 19,4 -2,1 -6,7 P2 
P1 
(-4,2+9,3)/2 (1,6-5,8)/2 (8,9+19,4)/2 (-1,3-2,1)/2 (14,7-6,7)/2 F1 
 Pode-se utilizar o Cruzamento pela Média Geométrica: 
 sqrt(P1*P2) 
Representação por Números Reais - 
Cruzamento 
 Cruzamento Aritmético: é uma combinação 
linear de dois genitores 
-4,2 1,6 8,9 -1,3 14,7 
9,3 -5,8 19,4 -2,1 -6,7 P2 
P1 
{[0,3*(-4,2]+[(1-0,3)*9,3]} ... ... ... {[0,3*14,7]+[(1-0,3)*(-6,7)]} F1 
F1 = [a x P1] + [(1-a) x P2] 
F2 = [a x P2] + [(1-a) x P1] 
 Um exemplo: a = 0,3 ( a é gerado randomicamente entre [0,1]) 
{[0,3*9,3]+[(1-0,3)*(-4,2)]} ... ... ... {[0,3*(-6,7)]+[(1-0,3)*(14,7)]} F2 
Representação por Números Reais - 
Mutação 
 Mutação Randômica Uniforme: substitui cada 
número real em um cromossoma por um número real 
aleatório (se teste da taxa de mutação = verdadeiro) 
-4,2 1,6 8,9 -1,3 14,7 
-4,2 rand 8,9 -1,3 14,7 F1 mutado 
F1 
 Alto poder de dispersão (ação global) 
rand: número aleatório de distribuição 
 uniforme com limites da variável 
Representação por Números Reais - 
Mutação 
 Mutação Randômica Não Uniforme: é 
somado ao valor do gene um valor sorteado a partir de 
uma distribuição especificada centrada em zero (se teste da 
taxa de mutação = verdadeiro) 
-4,2 1,6 8,9 -1,3 14,7 
-4,2 1,6+ rand 8,9 -1,3 14,7 F1 mutado 
F1 
 Poder de dispersão controlado - ação local: um exemploé a distribuição gaussiana com desvio padrão especificado 
(desvio padrão controla a dispersão) 
rand: número aleatório de distribuição 
 especificada com média zero 
Representação por Números Reais - 
Mutação 
 Mutação Creep: busca uma solução próxima 
através de ajustes aleatórios em ambas as direções (+ e -) 
-4,2 1,6 8,9 -1,3 14,7 
-4,2 1,6±  8,9 -1,3 14,7 F1 mutado 
F1 
Ação local: 
Creep   
X 
f() 
x 
Representação por Números Reais – 
Mutação Creep 
 Método de Ajuste da Mutação Creep:  
 max e min são os limites da variável X 
 rand é um número aleatório uniforme  [0,p] , p  1 
 Se p pequeno  ajuste menor 
 Se p grande  ajuste maior 
max min Xt 
Xt-min max-Xt 
Representação por Números Reais – 
Mutação Creep 
 Método de Ajuste da Mutação Creep: o , 
que é o tamanho do ajuste local na variável, 
pode variar com as gerações 
 por exemplo: variar por meio de uma 
exponencial decrescente 
 no início o ajuste é maior e depois vai diminuindo 
Representação Real x Representação 
Binária 
 Representação por números reais (ponto flutuante) é 
mais adequada em problemas de otimização com variáveis 
sobre domínio contínuo 
 Em particular em grandes domínios onde a representação 
binária requer um longo cromossoma (Ex: 100 variáveis, [-
500,500], 4 casas decimais 2400 bits) 
 Representação por reais é mais rápida na execução (não 
há decodificação) 
 Representação por reais oferece maior precisão 
(depende do computador) 
 Desempenho pode ser melhorado com operadores 
específicos ao problema 
 fica mais difícil fazer análise matemática do desempenho 
Representação Real x Representação 
Binária 
 Na representação por reais, dois pontos próximos um ao 
outro no espaço de representação, estão também próximos 
no espaço do problema 
 evita Hamming Cliff (penhasco de Hamming) 
Rep. Binário Valor Real 
I1 = 0 1 1 1 1 1 31 
I2 = 1 0 0 0 0 0 32 
 
 distância de Hamming = 6 
 Rep. Real Valor Real 
I1 = 31 31 
I2 = 32 32 
 
 distância = 1