PARALELIZAÇÃO E SINTONIA DO MÉTODO SIMULATED ANNEALING
APLICADO À OTIMIZAÇÃO DE TOPOLOGIAS LÓGICAS DE REDES ÓPTICAS
Michael André Gonçalves
Instituto Federal do Espírito Santo (IFES)
Rodovia, ES-010 – Km 6.5, Manguinhos, Serra – ES, 29164-231
[email protected]
Sérgio Nery Simões
Instituto Federal do Espírito Santo (IFES)
Rodovia, ES-010 – Km 6.5, Manguinhos, Serra – ES, 29164-231
[email protected]
RESUMO
O projeto de topologias lógicas de redes ópticas é um problema de otimização de grande
complexidade computacional, sendo comum a utilização de heurísticas para viabilizar a
determinação de boas soluções. Este trabalho aborda a paralelização e a sintonia da metaheurística Simulated Annealing (SA), utilizada na otimização de topologias lógicas de redes
ópticas, objetivando a minimização do processamento eletrônico de tráfego. O SA paralelo
implementado baseou-se no modelo N-ary Speculative Computation, em que todos os processos
realizam paralelamente as etapas de perturbação, avaliação e decisão. Após a implementação do
SA paralelo, foi realizada a sintonia dos parâmetros de perturbação e temperatura inicial, com o
objetivo de garantir a convergência para boas soluções, considerando um conjunto de
experimentos com dados heterogêneos. Neste procedimento, variou-se a perturbação em
{1,2,4,8,16}, sendo cada um destes valores o percentual de enlaces alterados aleatoriamente, em
uma dada solução, para gerar uma nova. A temperatura inicial foi variada em
{0.1,0.4,1.6,6.4,25.6}, parâmetro que determina a chance de se substituir a solução atual por uma
nova solução que apresente um valor pior para a função objetivo, evitando o aprisionamento em
mínimos locais. A sintonia destes parâmetros foi realizada considerando uma rede de 10 nós com
graus lógicos em {4,6} e matrizes de tráfego com três padrões de distribuição de tráfego
diferentes. Para avaliar as soluções do SA paralelo para a topologia lógica da rede, foi utilizado o
resolvedor linear GLPK para minimizar o processamento eletrônico de tráfego com um modelo
de programação linear. Cada combinação de valores adotados para a perturbação e para a
temperatura inicial constituiu um experimento. Cada experimento foi repetido 10 vezes para
avaliar estatisticamente a convergência. Os resultados foram comparados com valores ótimos
obtidos pela solução de um problema MILP, utilizando o resolvedor linear CPLEX. A qualidade
das soluções é expressa por erros percentuais, que significam o quanto se excedeu o valor ótimo
do processamento eletrônico de tráfego. Foram analisados dois erros percentuais, o
correspondente ao valor mínimo obtido (erro mínimo) e o referente ao valor médio (erro do valor
médio) de cada conjunto de 10 resultados obtidos pela repetição dos experimentos. Variando-se
os percentuais de perturbação, observou-se uma queda abrupta do erro mínimo e do erro do valor
médio para os valores entre 1% e 2%, e uma tendência de crescimento após 8%. O melhor valor
obtido para a perturbação, em todos os casos, foi de 4%. Temperaturas muito baixas,
especialmente 0.1, produziram os melhores resultados. Com um valor de temperatura tão baixo,
conclui-se que a variação da perturbação tem maior influencia nos resultados que a temperatura e
que um algoritmo de busca mais simples, do tipo GRASP, com pequenas perturbações também
poderia encontrar boas soluções.
Palavras-chave. simulated annealing, paralelização, sintonia.
XLI SBPO 2009 - Pesquisa Operacional na Gestão do Conhecimento
Pág. 3217
PARALLELIZATION AND TUNING OF THE METHOD SIMULATED ANNEALING
APPLIED TO THE OPTIMIZATION OF LOGICAL TOPOLOGIES OF OPTICAL
NETWORKS
ABSTRACT
The design of logical topologies for optical networks is a combinatorial optimization
problem with high complexity. Therefore, heuristic methods are extensively used to
provide good solutions with reasonable computational effort. This work addresses the
parallelization and tuning of the meta-heuristic Simulated Annealing (SA), applied to the
optimization of logical topologies for optical networks, aiming to minimize the electronic
traffic processing at network routers. The parallel SA implemented based on the model
N-ary Speculative Computation, where all processes perform parallel steps of
disturbance, assessment and decision. After the parallel implementation of SA, its tuning
was performed by varying the parameters of disturbance and initial temperature, with the
objective of ensuring convergence to good solutions, considering a series of experiments
with heterogeneous data. In this procedure, the disturbance was varied in {1,2,4,8,16},
being each of these values the percentage of links changed randomly in a given solution
to generate a new one. The initial temperature was varied in {0.1,0.4,1.6,6.4,25.6}, and it
is a parameter that determines the chance to replace the current solution by a new worse
solution, avoiding the trapping in local minimum. The tuning of these parameters was
performed considering a network of 10 nodes with logical level in {4, 6} and traffic
matrices with three different distribution patterns. To evaluate the solutions of the
parallel SA to the logical topology of the network, we used the GLPK linear resolver to
minimize the electronic traffic processing with a linear programming model. Each
combination of values adopted for the disturbance and the initial temperature is an
experiment of the tuning procedure. Each experiment was repeated 10 times to evaluate
the statistical convergence. The results were compared with optimal results obtained by
solving MILP problems with the CPLEX linear resolver. The quality of the solutions is
expressed as percentage errors, which means how much it exceeds the optimal value of
the electronic traffic processing. Two percentage errors were analyzed, one
corresponding to the minimum value obtained (minimum error) and the other referring to
the average value (average error) of each set of 10 results obtained by the experiment
repetition. The results shown an abrupt fall of the minimum error and the average error
for disturbance between 1% and 2%, and a trend of growth beyond 8%. The best value
for the disturbance in all cases was 4%. Very low temperatures, especially 0.1, produced
the best results. With such a reduced temperature obtained by tuning the Parallel SA, and
analyzing the error variation in all cases, it is concluded that the disturbance variation has
a greater influence on the results than the initial temperature and that a simpler search
algorithm, such as GRASP, with small disturbances, could also find good solutions.
Keywords. simulated annealing, parallelization, tuning.
XLI SBPO 2009 - Pesquisa Operacional na Gestão do Conhecimento
Pág. 3218