UMA VARIANTE DO SIMULATED ANNEALING APLICADA A UM
PROBLEMA DE LAYOUT
André Camatta
Universidade Federal do Espírito Santo
Departamento de Informática
29060-900, Vitória, ES, Brasil, +55-27-3335-2135
[email protected]
André Renato Sales Amaral
Universidade Federal do Espírito Santo
Departamento de Informática
29060-900, Vitória, ES, Brasil, +55-27-3335-2133
[email protected]
Resumo
Neste artigo, propomos a seguinte modificação para o simulated annealing: Em vez de escolher
aleatoriamente uma nova solução dentro da vizinhança da solução atual, introduzimos um critério de
seleção de soluções baseado em uma estratégia de lista de candidatos. Portanto, a vizinhança é
particionada em m subconjuntos, e um candidato é escolhido aleatoriamente em cada subconjunto. Em
particular, apresentamos uma implementação desta variante aplicado ao problema NP-árduo de
encontar um layout de facilidades de mínimo custo. Sugerimos escolhas para a função que determina
como diminuir o parâmetro temperatura, o critério de parada, além de métodos para se gerar uma
solução inicial e soluções vizinhas. Para os exemplares do problema publicados na literatura, o método
proposto tipicamente alcançou as melhores soluções conhecidas.
Palavras chaves: Simulated Annealing, Estratégia de Lista de Candidatos, Layout de Facilidades em
uma Dimensão
Abstract
In this paper, we propose the following modification to Simulated Annealing: Instead of choosing
randomly a new solution within the neighborhood of the current solution, we introduce a solution
selection criterion based on a candidate list strategy. Therefore, a neighborhood is partitioned into m
subsets, and a candidate is chosen randomly in each subset. In particular, we present an
implementation of this variant applied to the NP-hard problem of finding a layout of facilities of
minimum cost. We suggest choices for a function that determines the lowering of the temperature
parameter, stopping criterion, besides methods to generate the initial solution and neighbor solutions.
For the problem instances published in the literature, the proposed method typically achieved the bestknown solutions.
Keywords: Simulated Annealing, Candidate List Strategy, One-dimensional Facility Layout.
1. Introdução
O simulated annealing é um método que procura o mínimo global de uma função evitando ficar
preso a mínimos locais.Vários trabalhos têm mostrado que este método é de grande utilidade,
especialmente, para funções contendo muitos mínimos locais. Para diversos problemas, tais como,
escalonamento, problema do caixeiro viajante, coloração de grafos, problema quadrático de alocação,
entre outros, o método tem sido bem sucedido, encontrando soluções ótimas ou sub-ótimas de boa
qualidade.
Neste artigo, propomos modificar o método simulated annealing, incorporando um critério de
seleção de soluções, baseado em uma estratégia de lista de candidatos. Esta nova variante do simulated
annealing é então aplicada ao problema do layout de facilidades em uma dimensão, que é NP-árduo.
Na próxima secção, fornecemos maiores detalhes sobre o problema do layout de facilidades. Na
secção 3, revisamos o método simulated annealing. Na secção 4, descrevemos o procedimento
proposto. Os experimentos computacionais são então apresentados na secção 5, seguidos pelas
conclusões.
2. Layout de facilidades em uma dimensão
No problema do layout de facilidades em uma dimensão, devemos arranjar n facilidades em uma
linha reta de forma a minimizar os custos de comunicação entre as facilidades. Mais precisamente,
dados (i) o fluxo de material entre cada par de facilidades e (ii) o comprimento de cada facilidade, o
objetivo é minimizar uma função objetivo definida como a soma dos produtos da distância entre cada
par de facilidades e o fluxo entre elas. A distância entre duas facilidades é tomada como a separação
entre os seus centros. Claramente, o problema do layout de facilidades em uma dimensão pode ser
visto como ordenar segmentos de reta ao longo de uma reta. O problema é NP-árduo, pois é uma
generalização do problema de ordenação linear que foi provado NP-árduo. Picard & Queyranne
(1981) discutem várias aplicações práticas do problema.
Entre os métodos exatos para o problema podemos citar, por exemplo, um algoritmo branchand-bound (Simmons, 1969), um modelo de programa inteiro misto (Love & Wong, 1976) e um
algoritmo de programação dinâmica (Picard & Queyranne, 1981). Contudo, sendo o problema de
difícil resolução, a maioria das abordagens são heurísticas.
Hall (1970) sugeriu que, através dos autovalores e dos autovetores da matriz de fluxo, seria
possível extrair uma seqüência pela qual as facilidades podem ser colocadas no layout. Neghabat
(1974) propôs uma heurística que adiciona uma facilidade por vez à solução do problema. Heragu
(1992) compara a performance de sete heurísticas diferentes para o problema, entre elas, as heurísticas
MP (modified penalty) e MST (modified spanning tree). Heragu & Alfa (1992) propuseram um
algoritmo simulated annealing híbrido que refina uma solução usando uma implementação de
simulated annealing. Kumar et al (1995) propuseram uma heurística construtiva que provê soluções
boas em termos de qualidade e também de tempo computacional.
3. O método simulated annealing
Métodos de busca local são flexíveis e aplicáveis a uma vasta gama de problemas de otimização. A
fim de utilizar um método de busca local, o problema a ser resolvido precisa ser formulado de forma
que estejam bem definidos:
Ω : Conjunto de Soluções Factíveis do Problema
x : uma solução em Ω
N(x) : Conjunto de todas as soluções vizinhas de x
H( ) : Função de custo que avalia os elementos de Ω
Os métodos de busca local conhecidos como procedimentos de descida (descent procedures)
aceitam somente soluções de menor custo logo, estes podem terminar em um indesejável ótimo local.
Em contraste, o simulated annealing (SA), proposto independentemente por Kirkpatrick (1983) e
Cerny (1985), aceita um número limitado de soluções correspondendo a um aumento no valor da
função de custo.
O SA é baseado em uma analogia entre um sistema físico e um problema de otimização
combinatória. Os estados de um sistema correspondem às diferentes soluções factíveis de um
problema de otimização combinatória e a energia do sistema corresponde à função a ser minimizada.
O estado de mínima energia corresponde à solução ótima, isto é, a solução que minimiza a função
objetivo.
Dado um valor do parâmetro de controle T, a fim de determinar se uma solução y será aceita a
partir de uma solução corrente x, o SA avalia a probabilidade P de aceitação, dada por:
1484
 H ( y) − H ( x) 
P = exp −

T


O cálculo de P fornece um meio para que, em algumas ocasiões, um movimento desfavorável
(movimento que piora o valor da função objetivo) possa ser feito. Desta forma, pode-se aceitar uma
solução y cujo valor na função objetivo H ( y ) é pior do que o valor objetivo atual H ( x ) , embora
com uma probabilidade cada vez menor, à medida que o valor desfavorável aumenta.
Inicialmente para valores maiores de T (comumente chamado de temperatura) movimentos
com valores desfavoráveis grandes serão aceitos. A medida que T diminui, apenas movimentos com
valores desfavoráveis pequenos serão aceitos, de forma que quando T tende a zero, nenhum
movimento com valor desfavorável será aceito. A determinação da temperatura inicial, da razão na
qual a temperatura é reduzida, e do número de iterações em cada temperatura é conhecida como
estratégia de resfriamento.
O SA evita as desvantagens dos métodos de descida; no entanto, mantém sua flexibilidade e
aplicabilidade geral.
3.1 Variantes do simulated annealing
Diversas variantes do algoritmo simulated annealing original foram propostas na literatura, as quais se
mostraram úteis na adaptação do para vários problemas. Algumas destas não geram um vizinho
aleatório, mas requerem uma amostragem cíclica, i.e. todos os vizinhos são tentados uma vez antes de
qualquer um ser considerado pela segunda vez. Connoly (1990) afirma que esta abordagem aplicada
ao problema quadrático da alocação funcionou melhor que o simulated annealing padrão. Entretanto,
há também relatos de alguns autores que tiveram experiências mal-sucedidas com esta abordagem
(Dowsland, 1993).
Na formulação do simulated annealing supõe-se que a estrutura de vizinhança é bem definida
e invariável até o término do algoritmo. Na prática, dependendo do problema em mãos, outros
esquemas podem funcionar melhor. Desta forma, Schen et al (1988) propuseram uma modificação do
simulated annealing que reajusta a estrutura de vizinhança a medida que a temperatura diminui.
Dueck & Scheuer (1990) propuseram uma simplificação do algoritmo simulated annealing
onde o critério de aceitação de soluções não depende de probabilidades. Eles consideram um limiar
determinístico, t, de forma que eles aceitam uma solução pior se a diferença entre seu valor e o valor
de uma incumbente for menor ou igual ao limiar t. Este novo procedimento foi denominado threshold
accepting (muitas vezes também é chamado de deterministic annealing).
Hu, Kahng, & Tsau (1995) propuseram um método, que utiliza um limiar não-monotônico,
denominado old bachelor acceptance. Segundo os autores, este método produz resultados superiores
ao método threshold accepting.
4. O procedimento proposto
De maneira geral, uma estratégia de lista de candidatos consiste em se gerar uma partição da
vizinhança em m subconjuntos. Seja y um elemento do conjunto N(x). Para o problema do layout de
facilidades em uma dimensão, por exemplo, y representa o estado obtido do estado x após uma troca
de posição entre duas facilidades. Esta modificação da solução x é chamada de um movimento de x
para y. Cada y ∈ N(x) possui um ganho associado (H(y) - H(x) ). Particionamos o conjunto N (x) em
subconjuntos indexados Nπ(1) (x), Nπ(2) (x), ..., Nπ(m) (x) de forma aleatória. Claramente, os subconjuntos
Nπ(i ) (x) para i ∈ π= (1,..., m) identificam todos os movimentos que transformam x em algum vizinho
y, logo podemos nos referir à partição como subconjuntos de movimentos. Glover (1995) sugere que
os subconjuntos de movimentos sejam examinados fazendo-se uma varredura com reordenação
aleatória por blocos (Block-Random Order Scan): divide-se π em blocos sucessivos. A medida que o
início de um determinado bloco é atingido, os elementos deste bloco, antes de serem examinados, são
aleatoriamente reordenados, o que muda a sequência daquela secção de π. Alternativamente, Glover
(1995) sugere uma varredura com reordenação aleatória total (Full-Random Order Scan), o que
corresponde aproxidamente a selecionar um bloco de tamanho m. Todos os elementos são
1485
potencialmente reordenados. Uma versão bem simples desta varredura consiste em reordenar
aleatoriamente π sujeito a colocar o último elemento que forneceu um movimento favorável na
posição final de π, e então varrer os elementos em sequência.
Portanto, o procedimento aqui proposto funciona da seguinte forma: Um vizinho y é escolhido
por vez, aleatoriamente, em cada subconjunto e sua aceitação, ou não, ocorre de acordo com a
estratégia simulated annealing padrão: Se o ganho associado ao vizinho y representa um
melhoramento na solução, y é prontamente aceito; caso contrário, y pode ser selecionado com uma
certa probabilidade. Se uma solução y ∈ Nπ(i ) (x ) não for aceita, o próximo vizinho de x será escolhido
aleatoriamente em Nπ(i+1) (x). Desta forma, os subconjuntos são examinados em sequência, sendo que
todos são examinados antes de retornamos para o primeiro subconjunto. O usuário deve decidir se
usará uma varredura com reordenação aleatória por blocos ou com reordenação aleatória total ou
nenhuma reordenação. Uma função de redução da temperatura e um critério de parada devem ser
definidos pelo usuário.
Claramente, o método proposto se beneficia de elementos de memória implícita discutidos por
Glover(1995).
O procediemento Proposto
Gere uma solução inicial x;
Selecione uma temperatura inicial T0;
T ÅT0;
Repita
num_iteracoes Å 0;
Repita
num_iteracoes Å num_iteracoes + 1;
Selecione uma solução y pela estratégia de lista de candidatos;
Se (H (y) - H(x) < 0 ) Então y Å x;
Senão Gere p , aleatoriamente, a partir de
uma distribuição uniforme no intervalo [0, 1);
Se (P ≥ p ) Então y Å x;
Fim { Se}
Até que (num_iteracoes = n_rep)
Efetue a atualização de temperatura;
Até que (condição de parada seja verdadeira).
1486
5. Experimentos Computacionais
Para os testes computacionais foram usados 13 problemas de tamanhos variados. Com 5 ≤ n ≤ 11,
foram tomados o problema P3 de Simmons (1969) e os problemas P2, P3H, P4, P5 e P6 usados por
Heragu & Alfa (1992). Foram, também, utilizados, sete problemas de larga escala ( 15 ≤ n ≤ 30). Dois
destes, os de tamanhos n= 20 e n=30, são conhecidos na literatura (Heragu e Kusiak, 1991). Outros
três problemas n = 15, 17, 18, foram gerados excluindo-se facilidades do problema n = 20. Os
problemas restantes: n = 27, 28 foram gerados excluindo-se facilidades do problema n = 30. Os
experimentos foram realizados em um computador Athlon 2200Mhz e 256Mb de RAM.
Foram testadas duas estratégias para obtenção de uma solução inicial. Uma consiste em gerar
soluções aleatoriamente. A outra consiste em usar uma heurística construtiva: o grafo correspondente à
matriz de fluxo é particionado com a utilização do programa pMeTis ( Karypis & Kumar,1995). A
seguir, o layout é montado de tal forma que as facilidades que sejam mais “conexas” entre si fiquem
próximas umas as outras.
Para cada um dos 13 problemas foi gerada uma solução usando a heurística construtiva, sendo
que o tempo de particionamento não ultrapassou 0,01 segundos em todos os casos. Essa solução foi
usada por todos os algoritmos como soluções iniciais para 20 execuções de cada problema, de forma
que os valores médios, piores e melhores para a solução encontrada e o tempo de CPU, nas tabelas,
referem-se a essas 20 execuções. No caso das sementes aleatórias, elas foram geradas uma a uma a
cada execução.


Para formar a lista de canditatos, adotamos m = n _ moves , onde n_moves é o número de
movimentos possíveis (troca de posição entre duas facilidades). Os movimentos são então atribuídos
aleatoriamente aos m subconjuntos da partição. Cada subconjunto recebe n _ moves / m se esse
qüociente for inteiro, caso contrário, os subconjuntos do primeiro ao penúltimo recebem
n _ moves / m  e o último recebe o restante dos movimentos. Foi utilizada a estratégia de seleção de
candidatos sem nenhuma reordenação e uma função de resfriamento monotônica α(T) = .99 T. Após
diversos testes preliminares, adotamos n_rep = 105, e alteramos o critério de terminação do laço
interno para encerrá-lo quando o número de iterações atingir o valor n_rep ou o número de iterações
sem haver movimentos aceitos exceder n_moves. A temperatura inicial foi fixada em T0 = 30 para
todos os problemas. Quanto ao critério de parada, o algoritmo termina quando T < 5.
As Tabelas 1 e 2 apresentam os resultados para o procedimento proposto, com solução inicial
gerada pela heurística construtiva e gerada aleatoriamente, respectivamente. Vemos que em ambos os
casos o método é bastante eficiente, alcançando as melhores soluções conhecidas para todos os
problemas, exceto para o problema Nug30, onde o método chega a uma solução bem próxima da
melhor conhecida. Para todos os problemas, o tempo requerido pelo método foi de apenas alguns
poucos segundos. A tabela 3 apresenta o resultado dos experimentos com sete problemas realizados
por Heragu & Alfa (1992) e Kumar et. al (1995). Em termos de qualidade de solução, quando
comparado com Heragu & Alfa (1992), o método proposto obtém melhor solução em 5 dos sete
problemas da tabela 3. Quando comparado com Kumar et. al (1995), o método aqui proposto obtém
melhor solução em um dos sete problemas, ligeiramente pior em outro, e empata nos cinco problemas
restantes. Não podemos comparar diretamente os tempos de execução, pois os experimentos foram
realizados em computadores diferentes. Contudo, os outros procedimentos parecem necessitar de mais
tempo computacional que o necessitado pelo procedimento aqui proposto.
1487
Tabela 1 – Solução inicial construída a partir do grafo correspondente à
matriz de fluxo
n
Problema
Melhor
Solução
Conhecida
P2
P3
P3H
P4
P5
P6
Nug15
Nug17
Nug18
Nug20
Nug27
Nug28
Nug30
151
801
2324,5
2781,5
6933,5
6933,5
15549
44466,5
5
8
8
10
11
11
15
17
18
20
27
28
30
Valor Objetivo
Melhor
151
801
2324,5
2781,5
6933,5
6933,5
6305
9254
10650,5
15549
58281
61462
44965
Média
151
801
2324,5
2790,5
6944,5
6934
6316,5
9260,4
10650,5
15549
58281,65
61462,8
44965
Pior
151
801
2324,5
2868,5
7149,5
6943,5
6534
9304
10650,5
15549
58291
61466
44965
Tempo (s)
médio
0,03
0,05
0,13
0,05
0,15
0,11
0,80
3,01
5,06
9,65
25,93
32,03
16,04
Pior
0,03
0,05
0,90
0,15
0,38
0,32
2,02
4,59
6,95
10,91
29,85
34,62
17,85
Tabela 2 - Solução inicial aleatória
n
Problema
Melhor
Solução
Conhecida
P2
P3
P3H
P4
P5
P6
Nug15
Nug17
Nug18
Nug20
Nug27
Nug28
Nug30
151
801
2324,5
2781,5
6933,5
6933,5
15549
44466,5
5
8
8
10
11
11
15
17
18
20
27
28
30
Valor Objetivo
Melhor
151
801
2324,5
2781,5
6933,5
6933,5
6305
9254
10650,5
15549
58281
61462
44965
Média
152,7
801
2324,5
2781,5
6933,5
6933,5
6316,45
9256,5
10650,5
15549
58281,1
61462,4
45272
Pior
158
801
2324,5
2781,5
6933,5
6933,5
6534
9304
10650,5
15549
58282
61466
46606
Tempo (s)
médio
0,23
0,39
0,72
0,06
0,28
0,34
2,48
5,83
7,25
13,03
28,17
30,67
17,28
Pior
1,14
2,50
1,59
0,21
1,43
0,91
4,50
8,49
9,78
15,82
30,93
34,53
19,78
Tabela 3 - Resultados publicados na Literatura
Problema
P2
P3H
P4
P5
P6
nug20
nug30
Melhor
Solução
Conhecida
151
2324,5
2781,5
6933,5
6933,5
15549
44466,5
Heragu & Alfa (1992)
n
5
8
10
11
11
20
30
valor
151
2324,5
2781,5
6933,5
6933,5
15602
45111
tempoa (s)
10,351
11,803
19,815
23,103
29,176
663,376
585,947
Kumar et al (1995) Set1 Kumar et Al (1995)
Set2
valor
151
2324,5
2781,5
6953,5
7265,5
15971
45308
tempob (s)
0,01
0,08
0,10
0,12
0,12
5,30
25,80
valor
151
2324,5
2781,5
6953,5
7265,5
15549
44466,5
tempob (s)
0,01
0,08
0,10
0,12
0,12
8,60
91,80
a.Heragu & Alfa (1992) usaram um mainframe VAX 6420.
b. Kumar et Al (1995) usaram computador Sun 3/260.
1488
6. Conclusão
A estratégia de lista de candidatos, ou alguma forma desta, é freqüentemente usada para examinar um
subconjunto da vizinhança corrente por técnicas de busca tabu. Neste artigo, foi apresentada uma
variante do simulated annealing que utiliza uma estratégia de lista de candidatos. O desempenho desta
nova variante foi avaliado na resolução do problema de layout de facilidades em uma dimensão. O
problema é NP-árduo o que justifica o uso de heurísticas.
A partir dos experimentos computacionais, observa-se que o procedimento proposto é bastante
eficiente em ambos os aspectos: qualidade de solução e tempo de execução. Em comparação com
métodos publicados na literatura, o procedimento proposto foi bastante competitivo alcançando
tipicamente as melhores soluções conhecidas para os problemas testados.
Agradecimentos
Este trabalho tem o apoio do Plano Nacional de Ciência e Tecnologia do Setor Petróleo e Gás Natural,
CT-PETRO, por meio do CNPq (CT-PETRO/CNPq).
Referências
Cerny, V. (1985) “A thermodynamical approach to the traveling salesman problem: an efficient simulation
algorithm”, Journal of Optimization Theory and Applications, 45, 41–55.
Connolly, D. T. (1990) “An improved annealing scheme for the QAP”, European Journal of Operational Research,
46, 93 –100.
Dowsland, K.A. (1993) “Simulated Annealing”. In C. Reeves, editor, Modern HeuristicTechniques for
Combinatorial Problems, 20-69, Blackwell Scientic Publications, Oxford.
Dueck, G. & Scheuer, T. (1990) “Threshold Accepting: A General Purpose Optimization Algorithm Appearing
Superior to Simulated Annealing”, Journal of Computational Physics, 90, 161–175.
Glover, F. (1995) “Tabu Thresholding: Improved Search by Nonmonotonic Trajectories,” ORSA Journal on
Computing, Vol. 7, No. 4, pp. 426-442.
Hall, K. M. (1970) “An r-dimensional quadratic placement algorithm”, Management Science, 17/3, 219 - 229.
Heragu, S.S. (1992) “Recent model and techniques for solving the layout problem”, European Journal of
Operational Research, 57, 136-144.
Heragu, S.S. & Alfa, A. S. (1992) “Experiment Analysis of simulated annealing based algorithms for the layout
problem”, European Journal of Operation Research 57/2, 190-202.
Heragu, S.S. & Kusiak, A. (1991), “Efficient models for the facility layout problem”, European Journal of
Operational Research, 53, 1-13.
Hu, T.C.; Kahng, A.B. & Tsao , C.A. (1995) “Old Bachelor Acceptance: A new class of non-monotone
threshold accepting methods”, ORSA Journal on Computing, 7(4), 417– 425.
Karypsis, G. & Kumar, V. (1995) “A fast and high quality multilevel scheme for partitioning irregular graphs”,
Technical Report 95-035, University of Minnesota, Department of Computer Science.
Kirkpatrick, S.; Gellat C.D. & Vecchi, M.P. (1983) “Optimization by simulated annealing”, Science, 220, 671– 680.
Kumar, K. R.; Hadjinicola, G. C. & Lin, T. L. (1995) “A heuristic procedure for the single-row facility layout
problem”, European Journal of Operation Research 87, 65 - 73.
1489
Love, R. F. & Wong, J. Y. (1976) “On solving a one-dimensional space allocation problem with integer
programming”, INFOR, 14, 139-143.
Neghabat, F. (1974) “An efficient equipment layout algorithm”, Operation Research 22/3, 622-628.
Picard, J. & Queyranne, M. (1981) “On the one dimensional space allocation problem”, Journal of Operation
Research 29/2, 371-391.
Schen, C.; Braun, D. & Sangiovanni-Vincetelli, A. (1988) “Thunderbird: A complete standard cell layout
package”. IEEE Journal of Solid-State Circuits, SC-23, 410– 420.
Simmons, D. M. (1969) “One-dimensional space allocation: An ordering algorithm”, Operation Research, 17/5,
812-826.
1490