Unidade VII
Algoritmos Genéticos
Prof. Josué Pereira de Castro Universidade
Estadual do Oeste do Paraná
UNIOESTE - 2000
1. Introdução
• 1.1 O que são Algoritmos Genéticos?
– São algoritmos de busca baseados no
mecanismo de seleção natural e genética.
– Utilizam a representação das soluções através
de cadeias de bits (strings), que são modeladas
à maneira das cadeias de DNA dos seres vivos
orgânicos.
– Foram desenvolvidos por John Holland na
Universidade de Michigan.
2
1. Introdução
• 1.2 Objetivos do algoritmo original
proposto por Holland
– Criar uma abstração para explicar
rigorosamente o processo adaptativo dos
sistemas naturais
– Projetar sistemas de software artificial que
conservassem os mecanismos mais importantes
dos sistemas naturais.
3
1. Introdução
• Principais características dos sistemas
biológicos:
•
•
•
•
•
Auto-reparo
Auto-orientação
Reprodução
Aprendizado
Evolução
– Obs: Estas características nem sempre encontramse presentes nos sistemas artificiais
4
1. Introdução
• 1.3 Algoritmos Genéticos X algoritmos
tradicionais de Otimização e Busca
– Métodos de busca:
• Matemáticos (calculus-based)
• Enumerativos
• Randômicos
5
1. Introdução
– Métodos Matemáticos: Estão divididos em duas
classes principais:
• Métodos indiretos
– buscam extremos locais pela solução de sistemas de
equações usualmente lineares, partindo da assertiva de que
os extremos encontram-se no ponto onde o gradiente da
função tem valor zero
• Métodos diretos
– Realizam a busca caminhando sobre a função na direção
apontada pelo gradiente local (hill climbing - subida de
encosta)
6
1. Introdução
– Características dos Métodos Matemáticos:
• São de escopo local: O ponto ótimo deve estar
localizado na vizinhança do ponto corrente.
• São dependentes da existência de derivadas
(gradiente)
7
Exemplo:
Máximo Global
Máximo Local
Mínimo Global
8
1. Introdução
• Métodos Enumerativos
– Existe uma grande variedade de métodos
enumerativos
– Sua estratégia geral é:
• Dado um espaço de busca finito ou um espaço de
busca infinito discretizado, procurar pelos valores da
função objetivo em todos os pontos do espaço.
– Tem aplicabilidade apenas em espaços de busca
reduzidos
9
1. Introdução
– Otimização
• A Otimização busca melhorar a performance em
direção a algum ponto (ou pontos) ótimo(s)
• Esta definição pode ser dividida em:
– 1) Melhoramento da performance de alguma abordagem
– 2) Localização do “Ponto Ótimo”
10
1. Introdução
– Diferenças entre Algoritmos Genéticos e métodos
Tradicionais
• GA´s trabalham com uma codificação do conjunto de
parâmetros, não com os próprios parâmetros
• GA´s realizam a busca sobre uma população de pontos,
não sobre um único ponto
• GA´s utilizam a informação do resultado da função
objetivo, não derivadas ou qualquer outro
conhecimento auxiliar
• GA´s usam regras de transição probabilísticas, não
regras determinísticas.
11
1. Introdução
• 1.4.Exemplo de um Algoritmo Genético
simples
– População Inicial: Strings de 5 bits
•
•
•
•
01101
11000
01000
10011
f(x) = x2 >> 132 = 169
f(x) = x2 >> 242 = 576
f(x) = x2 >> 82 = 64
f(x) = x2 >> 192 = 361
12
1. Introdução
Operadores aplicáveis
Seleção: Versão artificial do mecanismo de seleção
natural de Charles Darwin: princípio da “sobrevivência
dos mais fortes (adaptados)”
Cruzamento: Versão artificial do mecanismo de
reprodução biológica, em que criaturas da mesma espécie
acasalam-se e dão origem à uma nova criatura
Mutação: Versão artificial do fenômeno de alteração do
código genético que ocorre nos seres vivos
13
1. Introdução
N
º
String
Fitness
%d
ototal
1
01101
169
14,4
2
11000
576
49,2
3
01000
64
5,5
4
10011
361
30,9
T
otal
-----
1170
100,0
14
1. Introdução
– Implementação do mecanismo de seleção
(Selection):
• Seleção aleatória através do algoritmo chamado
“Roleta”
– Este mecanísmo consiste em dividir o intervalo [0,
fitness_total] em regiões baseadas na porcentagem de cada
fitness individual
15
1. Introdução
0|100
1
4
14%
31%
0,14
0,63
5%
2
3
49%
0,63
Seleção por “Roleta”
16
1. Introdução
– Implementação do Mecanismo de Cruzamento
(Cross Over):
• Após a seleção aleatória dos pares, uma posição
aleatória de “corte”, dentro da string de bits é
selecionada, e o cruzamento é efetuado, gerando
dois novos indivíduos.
17
1. Introdução
Pai
A
=
0
1
1
0
1
B
=
1
1
0
0
0
Indice de
corte = 3
Mãe
Filho 1
A
=
0
1
1
0
0
1
B
=
1
1
0
0
1
1
Filho 2
Cruzamento (Cross Over)
18
1. Introdução
– Implementação do Mecanismo de Mutação
(Mutation)
• Após o cruzamento, os filhos podem sofrer
alterações no seu código genético, chamadas de
mutações.
• Estas podem ocorrer em um ou mais alelos (bits), de
acordo com uma probabilidade pré-estabelecida.
– Em virtude da probabilidade de mutação ser, geralmente
baixa nos seres vivos, ela desempenha um papel
secundário na evolução das espécies.
19
1. Introdução
Cromossomo
A
=
0
1
1
0
0
1
Original
Prob. de mutação = 1% = 0,01
Após
A
=
0
1
0
0
0
1
Mutação
I = 1,
M = rand() = 0,45
Sem mutação
I = 1,
M = rand() =0,3
Sem mutação
I = 1,
M = rand() = 0,5
Sem mutação
I = 1,
M = rand() = 0,002
Mutação
I = 1,
M = rand() = 0,2
Sem mutação
20
1. Introdução
• 1.5 Padrões (templates) de Similaridade
(Schematas)
– Schemas: Padrões de similaridade que
descrevem um subconjunto de strings que são
similares em certas posições.
• Exemplo:
– Seja o alfabeto dos cromossomos = {0,1}
– Adiciona-se mais um símbolo (*) à este alfabeto = {0,1,*},
onde * é um simbolo “don´t care”
21
1. Introdução
• Seja então a seguinte população:
• {01110,01111,11110,11111}
–
–
–
–
–
–
–
–
Schema 1: ****0
Strings: {01110,11110}
schema 2: ***1*
Strings: {01110,01111,11110,1111}
Schema 3: {**0*1}
Strings: {}
Schema 4: {*1*10}
Strings: {01110,11110}
22
1. Introdução
Genética Natural
Vocabulário
Cromossomos
Genótipo (conjunto de Cromossomos
de umindivíduo)
Fenótipo (organismo formado pela
interação da carga genética como
meio ambiente)
Genes (elementos que compõemos
cromossomos, são formados por
sequências de DNA)
Alelos (proteínas que compõemo DNA)
Meio-Ambiente
Genética Artificial
Strings
Estruturas (conjuntos de strings)
Decodificação da estrutura emum
conjunto de parâmetros que formam
uma solução emparticular
Parte de uma string que codifica um
determinado parâmetro
Cada umdos bits que compõema
String de uma estrutura
Função Objetivo (Fitness)
23