Inteligência Computacional
Simulated Annealing (SA)
Aplicado ao Problema
de K-Dispersão Discreta (PKD)
Gilmax de Oliveira Araújo
Luciana Batista de Lima
O Problema
K – Dispersão Discreta
“Dado um conjunto de n possíveis candidatos sobre os nós
de um grafo, deve-se em selecionar k facilidades dentre
as n possíveis, de tal modo que a distância mínima entre
qualquer par das k facilidades selecionadas seja
maximizada.”
Aplicações
1.
2.
3.
4.
5.
6.
7.
Localização de reservatórios de combustível;
Alocação de agentes competitivos como franquias etc;
Distribuição de depósitos de lixo;
Localização de silos de mísseis e instalações nucleares;
Prisões e instalações militares;
Tratamento de águas residuais;
Distribuição de freqüências em sistemas de
comunicações;
8. Experimentos estatísticos;
9. Exploração de madeira etc.
Metaheurística Simulated
Annealing (Têmpera Simulada)
•
•
•
Admite soluções de piora para escapar de
ótimos locais;
As soluções de piora são aceitas com uma
certa probabilidade, a qual depende de um
parâmetro, chamado de temperatura;
O final do processo se dá quando a
temperatura se aproxima de zero e nenhuma
solução de piora é mais aceita, situação que
evidencia o encontro de um ótimo local;
Caso:
 No Grafo abaixo, obter 3 cidades entre as 6
cidades possíveis, de tal forma que a menor
distância entre ela seja maior que as menores
distâncias dos possíveis polígonos formados:
6
2
5
4
3
8
5
9
1
4
9
9
10
8
01
5
5
Metodologia Aplicada
 Geração de uma solução aleatória
inicial:
A partir da tabela a seguir,que
representa a matriz distância, obter um
vetor de 6 elemento com valores
booleanos 0 e 1.
Cidade escolhida => “1”
Cidade não escolhida => “0”
Ex: s = [ 1 1 1 0 0 0 ]
Tabela representativa da matriz
distância:
0
1
2
3
4
5
0
0
10
9
5
13
5
1
10
0
5
11
9
9
2
9
5
0
6
12
4
3
5
11
6
0
8
12
4
13
9
12
8
0
8
5
5
9
4
12
8
0
Função objetivo:
 Consiste na obtenção da menor
distância das arestas do polígono
formado:
Ex: dist (0,1) = 10
dist (0,2) = 9
dist (2,3) = 5
Menor distância = 5
Refinando a solução – Simulated
Annealing
 Gera um vizinho qualquer :
– Troca de posição de dois elemento
quaisquer do vetor solução:
Ex:
s = [1 1 1 0 0 0]
s’= [1 0 1 1 0 0]
 Calcula a função objetivo
 Verifica se f(s’) > f(s) se verdadeiro
f(s) <- f(s’)
Refinando...
 Caso contrário o programa aceita a solução
de piora com um probabilidade de:
P = e ( Δ/T)
 Até que a solução ótima seja encontrada ou
o número máximo de interações (SAmax)
seja atingido;
Solução ótima encontrada:
 S = [0 1 0 1 0 1]
 Menor distância entre as arestas do
polígono = 9
Conclusão:
 Solução satisfatória;
 Comparação com o Problema da
k-dispersão resolvido pelo Lingo