A generic method that ties and starting temperature of the simulated annealing algorithm to the problem size

Abstract

Tavlama Benzetimi (TB) yöntemi Metropolis'in 1953 Monte Carlo Algoritmasına kadar uzanmaktadır. Ancak bu metodu kombinatoryel eniyileme problemlerinde uygu layan ilk kişi, 1983'te Kirkpatrick olmuştur. Daha sonra 1986'da, Aarts ve van Laarhoven TB yönteminin ilk paralel uygulamasını gerçekleştirmişlerdir. Bu tezde, bilgimiz dahilinde ilk defa Tavlama Benzetimi yönteminin başlangıç sıcaklığını eldeki kombinatoryel eniyileme probleminin büyüklüğüne bağlayan genelgeçer bir metod önerilmiştir. Önerdiğimiz bu yöntemle bulunan başlangıç sıcaklıklarını, Gez gin Satıcı Problemi'nin tüm şehirlerin bir dama tahtasının çizgilerinin birleştiği nok talarda bulunduğu özel durumunu kullanarak denedik. Paralel işlemcilerde çalışan programımızın, çözüm kalitesini artırırken işlem süresini düşürdüğü gözlemlenmiştir. Gezgin Satıcı Problemi ile sınırlı olmayan yöntemimiz şöyledir: TB yöntemi çok yüksek bir sıcaklıktan başlayarak çalıştırılır ve tüm bir soğutma çizelgesi boyunca, büyüklükleri (N) birbirinden farklı problemlerin maliyet fonksiyonlarının değişkenlik katsayısı gözlenir. Her bir problem için, sıcaklığın bir fonksiyonu olan, çoklu üstlü bir eğri değişkenlik katsayısı dağılımına uydurulur. Daha sonra, bu eğrilerin en yüksek değerlere ulaştığı yerdeki sıcaklıklar belirlenir. Bu sıcaklıklar N'ye karşı gelecek şekilde yerleştirilir. En son olarak, doğrusal olmayan ve N'nin bir fonksiyonu olan bir eğri, bu noktalara uy durulur. Yöntemimizin geçerliliğini göstermek için, Aarts ve van Laarhoven'in Paralel işlemciler için TB Yöntemi 20 işlemcili öbek bilgisayarında çalıştırılmış ve 2025 şehire kadar Gezgin Satıcı Problemi denenmiştir.

Simulated Annealing (SA) can be traced back to Metropolis's 1953 Monte Carlo Algorithm. However, it was Kirkpatrick who first applied it to Combinatorial Opti mization Problems in 1983. Later in 1986, Aarts and van Laarhoven wrote the first parallel implementation of the SA algorithm. To our knowledge, this is the first time a generic method that ties the start ing temperature of the Simulated Annealing Algorithm to the problem size of a given combinatorial optimization problem is proposed. In our parallel implementation, our tests with the special case of the Traveling Salesman Problem, which places cities on checkerboard coordinates show that our proposed starting temperature reduces run time while increasing solution quality. Our method of computing the starting tem perature, which is not limited to the TSP, can be described as follows: SA Algorithm is run starting from a very high temperature and, during a full cooling schedule, the coefficient of variation of the cost function of a number of problem instances, each with a different problem size N, is observed. For each instance, a polynomial curve, which is a function of temperature, is fitted to the coefficient of variation distribution, and the temperature that this fitted curve hits a maximum is determined. Next, these temperatures versus N are plotted. Finally, a nonlinear function of N is fitted to these points. To demonstrate the validity of our method, the Parallel Simulated Annealing Algorithm of Aarts and van Laarhoven was implemented on a PC Cluster with up to 20 PCs, and TSP instances of up to 2025 cities were tested.