Otimização Não-Diferenciável:
Algoritmo Genético e
Simulated Annealing
DAS-6651 - MSPO
Eduardo Camponogara
1
0. Agenda



2
Otimização Black-Box
Algoritmo Genético
Simulated Annealing
1. Black-Box Optimization

Problema de Interesse
(P) Minimize f(x)
x  Rn
onde nada se assume sobre f(x).
3
1. Black-Box Optimization

Problema de Interesse
(P) Minimize f(x)
x  Rn
onde nada se assume sobre f(x).

4
f(x) pode representar:
–
O valor estimado do custo de produção para um dado
conjunto de parâmetros (por meio de simulação).
–
O valor da função objetivo de um problema de otimização,
onde f(x) =  se x é infactível.
–
O prêmio recebido em um certo jogo quando o participante
segue a estratégia induzida por x.
1. Técnicas de Otimização

Algoritmo Genético (GA)
–

Simulated Annealing (SA)
–
5
O AG tem suas raízes na Teoria da Evolução de Charles Darwin.
Se inspira no processo físico de obtenção de estruturas cristalinas
através do super-aquecimento e resfriamento lento da substância, o
que induz o sistema a atingir o nível mais baixo de energia possível.
2. Genética e Evolução

A percepção de que certas características são hereditárias—i.e.,
transmitidas geneticamente—data de vários décadas passadas.
Charles Darwin
Hereditariedade  evolução  seleção natural
6

A Teoria da Evolução é considerada um dos maiores avanços
científicos até esta data.

Ela tem implicações em várias áreas naturais, científicas e sociais
como, por exemplo, Biologia, Matemática, Física e Sociologia.
2. Adaptação Biológica

Estudaremos maneiras pelas quais o processo de evolução
natural pode ser empregado para se “evoluir” soluções
computacionais (Algoritmo Genético) e até mesmo programas
ou algoritmos (Programação Genética) para problemas
interessantes.

A propriedade de adaptação é descrita pela seguinte expressão:
Adaptação = Variedade + Hereditariedade + Seleção
7
2. Adaptação Biológica

8
Variação
– Variação se refere a como os indivíduos diferem uns dos outros,
portanto só pode ocorrer se existirem múltiplos indivíduos, implicando
em paralelismo e multiplicidade espacial (População).
2. Adaptação Biológica

9
Hereditariedade
– Hereditariedade é uma forma de persistência temporal que se
propaga de pai para filho, um processo iterativo que se repete
(Processo Iterativo).
2. Adaptação Biológica

10
Seleção Natural
–
A capacidade de reprodução
é exponencial, extremamente
maior do que a quantidade
de recursos disponíveis
(limitada).
–
Surge, portanto, a frase “a
sobrevivência dos
reprodutores”.
–
Levando em conta esta
capacidade exponencial,
somos um grupo seleto de
indivíduos.
2. Adaptação Biológica

A frase mais conhecida é “a sobrevivência do mais dotado”.
Entretanto, a teoria diz que o que importa é a reprodução, o que
implica na frase “a sobrevivência do reprodutor”.

Segundo a teoria da evolução, as características de uma pessoa
(bonita, alta, inteligente, etc.) só importam se aumentam a
capacidade de reprodução.

A evolução das espécies pode levar a processos cíclicos.
Leões
11
Gazelas
2. Hereditariedade Como Evolução
Simulada

Idéia Básica
–

12
Da mesma forma que em sistemas biológicos, as equações de
adaptação biológica podem ser utilizadas para “evoluir”
soluções de um problema (Algoritmo Genético) e até mesmo
algoritmos (Programação Genética).
Algoritmo Genético
–
Ele representa soluções como estruturas semelhantes ao
DNA, as quais expressam alguma forma de aptidão.
–
Estruturas de DNA aparecem em organismos com capacidade
de se acasalarem, e onde haja mutação e cross-over do
material genético.
2. Desenvolvimento do Algoritmo
Genético
13

A teoria de Darwin foi complementada pelos trabalhos de Gregor
Mendel (pai da Genética) e posteriormente pela descoberta da
estrutura de dupla hélice do DNA.

Estes outros trabalhos mostram que as características
transmitidas são discretas, não são contínuas como anteriormente
assumido.

Mendel mostrou em seus experimentos que, se controlarmos o
ambiente, as características são bem distintas (flores altas ou
baixas).

A linguagem da natureza é um alfabeto discreto.
2. AG para Solução de Problemas
14

O AG expressa uma solução como uma cadeia de símbolos
(usualmente 0s e 1s) de tamanho fixo, da mesma forma que o
DNA codifica as características de um indivíduo.

É necessário a existência de uma função de aptidão (fitness
function) que mapeie a cadeia em uma forma útil. Por exemplo, a
cadeia pode representar:
–
Um vetor com as variáveis de uma função f(x) que se deseja
minimizar.
–
uma estratégia para competir em um jogo.
2. AG para Solução de Problemas







15
Problema.
Cadeia de símbolos representando uma solução
candidata.
Função de aptidão.
População inicial de soluções candidatas.
Mecanismo de reprodução.
Mecanismo de mutação.
Procedimento de seleção natural.
2. Popularidade do AG
16
Robustez
Evolução natural é tida como um método
bem sucedido, robusto no meio
biológico.
Generalidade
AGs são capazes de tratar problemas
complexos, que possuem um número
grande de componentes, cujas
contribuições para o conjunto não são
bem entendidas.
Paralelização
AGs são naturalmente paralelos, podem
ser implementados em redes de
computadores (assíncronos) e
computadores paralelos (síncronos).
2. Popularidade do AG

17
Antes de procedermos à descrição dos passos do
Algoritmo Genético, assumiremos o seguinte:
–
O problema de otimização a ser resolvido é de maximização,
em vez de minimização. (Para transformar minimização em
maximização, basta substituir “min” por “max” e f(x) por – f(x).)
–
A função objetivo (f(x) se maximização, – f(x) se minimização)
será utilizada como fitness function (fi).
2. Popularidade do AG

18
Antes de procedermos à descrição dos passos do
Algoritmo Genético, assumiremos o seguinte:
–
Quanto mais alto o valor da fitness function (fi) melhor a
qualidade da respectiva solução.
–
Assumiremos que a fitness function assume um valor não
negativo. (Isso pode ser contornado através da adição de uma
constante, i.e., seja m = Min{ fi(x) : x pertence à população},
então basta substituir fi(x) por fi(x) – m para que a fitness
function se torne não negativa.)
2. Detalhes do AG
AG(fi, ft, p, r, m)
fi - fitness function.
ft - fitness threshold
(condição de parada).
p - tamanho da população.
r - fração da população
a ser substituída por
cross-over.
m - taxa de mutação.
 Inicialize a população P: gere p soluções candidatas
randomicamente.
 Avalie: para cada x P, calcule fi(x).
19
2. Detalhes do AG

Enquanto Max{fi(x) : x P} < ft, execute:
–
–
–
–
–
–
20
Seja PS a nova população, iniciando com PS = 
Selecione (1-r)*p elementos de P e adicione a PS com
probabilidade de xi dada por:
Pr(xi) = fi(xi) / fi(xj)
Probabilisticamente selecione r.p/2 pares de elementos de P,
de acordo com Pr(xi). Para cada par (xi, xj) execute cross-over
e adicione os “filhos” a PS.
Execute mutação de m.p elementos de PS.
P  Ps
calcule fi(x) para todo x P.
2. Operador Genético: Cross-Over
Os
operadores genéticos determinam como os membros de uma população
são combinados, ou sofrem mutação, de forma a gerar novos candidatos.
Cross-over
de um ponto
11101001000
11101010101
11111000000
00001010101
21
00001001000
2. Operador Genético: Cross-Over
Os
operadores genéticos determinam como os membros de uma população
são combinados, ou sofrem mutação, de forma a gerar novos candidatos.
Cross-over
de dois pontos
11101001000
00101000101
00111110000
00001010101
22
11001011000
2. Operador Genético: Mutação


23
Cross-over uniforme
11101001000
10011010011
00001010101
Mutação
11101001000
10001000100
01101011001
11101011000
2. Exemplo de Aplicação Elementar

Problema:
–

Método
–
–
–
–
–
24
Encontre o valor máximo da função f(x) = x2 onde x pode assumir
valores do conjunto A = {0, ..., 31}
Utilize 5 bits para representar uma solução candidata.
Defina a função de aptidão fi(x) = f(x).
Gere um conjunto de 4 soluções candidatas randomicamente, para
compor a população inicial. (Tamanho da população p = 4).
Adote o cross-over de um ponto como método de reprodução. (Taxa
de substituição por cross-over r = 50%).
Adote como mecanismo de mutação a troca de um bit de uma
solução candidata. (Taxa de mutação m = 5%).
2. Exemplo de Aplicação Elementar

Método
–
–
–
–
–
25
Utilize 5 bits para representar uma solução candidata.
Defina a função de aptidão fi(x) = f(x).
Gere um conjunto de 4 soluções candidatas randomicamente,
para compor a população inicial. (Tamanho da população p =
4).
Adote o cross-over de um ponto como método de reprodução.
(Taxa de substituição por cross-over r = 50%).
Adote como mecanismo de mutação a troca de um bit de uma
solução candidata. (Taxa de mutação m = 5%).
2. Exemplo de Aplicação Elementar

Memória Inicial
Solução
Candidata
-------------01101
11000
01000
10011
--------------

26
Fitness Probabilidade
de Reprodução
---------- -------------------169
14,4%
576
49,2%
64
5,5%
361
30,9%
---------- --------------------
Eventualmente, o algoritmo genético gera a solução ótima x* = 11111,
onde f(x*) = 961.
2. Questões Práticas

O fenômeno de crowding ocorre quando um indivíduo com alta aptidão se
reproduz rapidamente, gerando cópias ou filhos muito semelhantes, que venham a
constituir a maior parte da população.

O aspecto negativo é a perda de diversidade, o que acarreta uma convergência
prematura (ótimo local).
População Inicial
Mais
Apto
27
População Resultante
2. Questões Práticas

28
Algumas estratégias para evitar crowding
–
Seleção de pares para reprodução através de torneios, em
vez de seleção probabilística.
–
Utilizar o valor de posição (ranking) no lugar da aptidão para
calcular as probabilidades de selecionar os indivíduos.
–
O valor de aptidão de um indivíduo pode ser reduzido pela
presença de outros indivíduos semelhantes.
2. Questões Práticas

Questão: é possível descrever matematicamente a
evolução da população de um AG em função do
tempo?
–
29
O Schema Theorem de Holland (1975) oferece uma
caracterização.
2. Questões Práticas

O Conceito de Schema
–
–

Caracterização da População
–
30
Uma cadeia de 0s, 1s e *s (curinga) que representa uma
família de indivíduos.
Exemplo: 0*1 representa os indivíduos 001 e 011.
Uma população de cadeias (vetores de bits 0s e 1s) pode ser
vista em termos do conjunto de schemas que ela representa,
e o número de indivíduos associados com cada schema.
2. Schema Theorem

Seja m(s, t) o número de indivíduos no instante t (t-ésima
população) que pertençam ao schema s.

O teorema descreve o valor esperado de m(s,t+1) em termos:
–
–
–
–
31
de m(s,t);
das propriedades de s;
da população; e
dos parâmetros do AG (métodos de recombinação, taxa de
mutação, etc.).
2. Considerando Apenas Seleção

Considerando apenas seleção, o Schema Theorem nos diz que
u(s,t)
E[m(s,t+1)] = -------.m(s,t)
fm(t)
Onde:
– m(s,t) é o número de indivíduos em Pt (t-ésima população) que
pertençam ao schema s.
32
–
fm(t) é o valor médio da função de aptidão dos elementos de Pt.
–
u(s,t) é o valor médio da função de aptidão dos elementos de Pt que
pertençam ao schema s
2. Schema Theorem

Se vemos o AG como um processo virtual paralelo
que:
a) executa uma busca através do espaço de possíveis schemas
e, ao mesmo tempo,
b) executa uma busca através do espaço de indivíduos.
Então a equação indica que schemas de maior aptidão
crescerão em influência com o passar das gerações.
33
2. Versão Completa do Schema
Theorem
u(s,t)
pc.d(s)
E[m(s,t+1)]  -------.m(s,t) . [ 1 - -------- ] . [1 - pm]^o(s)
fm(t)
l-1
Onde:
– pc é a probabilidade do operador cross-over de um ponto a ser
aplicado a um indivíduo arbitrário.
34
–
pm é a probabilidade de que um bit arbitrário de um indivíduo
arbitrário sofra mutação.
–
l é o número de bits das cadeias.
–
o(s) é o número de bits definidos presentes no schema s (bits 0 ou
1).
–
d(s) é a distância entre o bit definido mais à esquerda e o mais à
direita no schema s.
2. Interpretação do Schema
Theorem
u(s,t)
pc.d(s)
E[m(s,t+1)]  -------.m(s,t) . [1 - ----------- ] . [1 - pm]^o(s)
fm(t)
35
Probabilidade de uma
cadeia arbitrária de s
continuar em s após
a aplicação do
operador cross-over
de um ponto.
l-1
Probabilidade de uma
cadeia arbitrária de s
continuar em s após
a aplicação do
operador de mutação.
2. Interpretação do Schema
Theorem
u(s,t)
pc.d(s)
E[m(s,t+1)]  -------.m(s,t) . [1 - -------- ] . [1 - pm]^o(s)
fm(t)
l-1

36
O Teorema nos diz que os schemas de maior aptidão deverão aumentar
sua influência, especialmente
–
aqueles que possuem um pequeno número de bits definidos
(contendo vários ‘*’) e
–
aqueles cujos bits definidos estão próximos uns dos outros.
3. Simulated Annealing
37

Um método de otimização bastante geral (como o Algoritmo
Genético).

SA tem demonstrado excelente desempenho em problemas que
apresentam um número muito grande de ótimos locais.

Uma das aplicações mais bem sucedidas de SA é o problema de
localização de componentes eletrônicos em microprocessadores,
no qual procura-se minimizar o comprimento total das conexões.
3. Empacotamento de
Componentes Eletrônicos
38
3. O Processo de Annealing

O processo de annealing se refere ao método por meio do qual líquidos (ou
metais) se resfriam e cristalizam.

Aquecemos a substância até uma temperatura muito alta, depois resfriamos
lentamente. Na natureza, se o resfriamento é bastante lento, a substância assume
uma configuração de menor energia para a temperatura de equilíbrio.
Baixa temperatura,
a substância se
cristaliza
Alta temperatura
39
3. Probabilidade de um Nível de Energia

O algoritmo de minimização da Natureza é probabilístico
Pr(E) ~ exp( - E/kT)
40
–
Para uma dada temperatura T, quanto maior o nível de
energia, menor a probabilidade da configuração.
–
Para um dado nível de energia E, a probabilidade da
configuração diminui com a redução da temperatura.
–
K é a constante de Boltzman
3. Probabilidade de um Nível de Energia

O algoritmo de minimização da Natureza é probabilístico
Pr(E) ~ exp( - E/kT)
41

Mesmo em baixa temperatura, é possível que o sistema esteja em
um nível elevado de energia, embora a probabilidade seja
extremamente pequena.

Em outros palavras, o sistema aumenta o nível de energia
algumas vezes, outras vezes ele diminui, mas a probabilidade de
aumentar diminui exponencialmente com a redução da
temperatura.
3. Probabilidade de um Nível de Energia
Energia do Sistema
42
1 / Temperatura
3. O Algoritmo de Metropolis

Em 1950, Metropolis incorporou as idéias apresentadas em computações
numéricas.

Dado um conjunto de configurações para um sistema, a probabilidade do sistema
assumir a configuração E2 a partir da configuração E1 é dada por:
Pr = exp[ – (E2 – E1) / kT ] se E2 > E1
Pr
Se E2 < E1, então Pr = 1.
43
0
E2 – E1
3. O Algoritmo de Metropolis

44
Para empregarmos o algoritmo de Metropolis em outros sistemas,
não necessariamente termodinâmicos, precisamos de:
1)
Uma descrição das possíveis configurações do sistema.
2)
Um gerador randômico de perturbações do sistema. Essas
perturbações definem as “opções” de configuração.
3)
Uma função objetivo (análoga à energia) cuja minimização
desejamos executar.
4)
Um parâmetro de controle T (análogo à temperatura) e um
procedimento de annealing, que descreve a maneira pela qual T
decresce.
3. Exemplo: Prob. Caixeiro Viajante

O Problema do Caixeiro Viajante (PCV):
–
São dados N cidades e uma matriz de distâncias.
–
Desejamos encontrar uma rota, partindo da cidade 1 que visite as demais
cidades precisamente uma vez e retorne à cidade 1, tal que o caminho
percorrido seja o menor possível.
–
O PCV pertence a família dos problemas NP-Difíceis, o que significa que o
custo computacional para encontrar a solução ótima é da ordem de O(eN).
8
4
1
3
5
6
9
45
2
7
3. Exemplo: Passos para Aplicar SA
1)
2)
Configuração: um vetor com N posições para armazenar uma permutação das
cidades.
Perturbação:
a)
3 5 2 6 8 9 1 47
3 5 8 6 2 9 1 47
b)
3 5 2 6 8 9 1 47
3 6 8 9 5 2 1 47
46
3. Exemplo: Passos para Aplicar SA
3) Função Objetivo:
N-1
E=
||(xi, yi) - (xi+1, yi+1)|| + ||(xN, yN) - (x1, y1)||
i=1
4) Procedimento de Annealing
– Gere várias configurações randômicas, calcule o DE máximo, e
defina T0 (temperatura inicial) como algumas dezenas de vezes o
valor de DE.
– Para cada Tk, execute 100N ou mais reconfigurações, aceitando-as
ou não conforme a probabilidade de Boltzman.
– Faça Tk+1  0,98*Tk.
47
4. Referências
48

T. M. Mitchell, Machine Learning, McGraw-Hill,
1997.

W. H. Press, S. A. Teukolsky, W. T. Vetterling,
B. P. Flannery, Numerical Recipes in C: The Art
of Scientific Computing, Cambridge University
Press, 1993.