Benzetilmiş tavlama

125 noktayı bağlayan en kısa yolu bulmak için gezgin satıcı probleminin benzetilmiş tavlama ile çözülmesi.

Benzetilmiş tavlama ya da benzetimli tavlama algoritması, eniyileme problemi için tasarlanmış olasılıksal yaklaşımlı bir algoritmadır. Diğer olasılıksal yaklaşımlar gibi (genetik algoritmalar, tabu arama vb.) en iyi çözümün en kısa zamanda üretimini hedefler. Bu sebeple, özellikle matematiksel modellerle çözülmesi maliyetli olan kombinasyonel eniyileme problemlerinde kullanılır. Benzetilmiş tavlama algoritması; elektronik devre tasarımı, görüntü işleme, yol bulma problemi, gezgin satıcı problemi, malzeme fizigi simulasyonu, kesme ve paketleme problemi, akış çizelgeleme ve iş çizelgeleme problemlerinin çözümlerinde başarılı sonuçlar vermiştir.

Problem tanımı

Eniyileme problemi, nicel olarak en iyiyi bulmayı ve bunun yöntemlerini inceler. Arama uzayının büyüklüğü nedeniyle kombinasyonel eniyileme problemlerinin çözümü, eniyileme yöntemlerinden faydalanmayı gerektirir. Büyük bir arama uzayı içinde gerekirci yöntemlerin kullanımı, hemen hemen imkânsızdır. Çünkü bu arama uzayı içinde en iyi çözümlerin bulunması çok zaman alır. Yerel arama yöntemleri de, arama sürecinde yerel en küçük çözümde takılıp, daha iyi bir çözüm değerine ulaşılmasına engel olabilir. Arama algoritmaları için bir dezavantaj sayılan bu durum karşısında daha detaylı arama yapan arama yöntemleri geliştirilmiştir. Benzetilmiş tavlama algoritması, bu yöntemlerden birisidir.

Kaynakça

• Kirkpatrick, S., Gelatt, C.D. ve Vecchi, M.P., 1983. Optimization by Simulated Annealing. Science, New Series, Vol. 220, pp. 671–680.
• Lutfiyya, H., McMillin, B., Poshyanonda, P. ve Dagli, C., 1992. Composite Stock Cutting Through Simulated Annealing. Mathemetical Computing Modelling, Vol. 16(1), pp. 57–74, Great Britain.
• Lai, K.K. ve Chan, J.W.M., 1997. Developing A Simulated Annealing Algorithm for The Cutting Stock Problem. Computers and Industrial Engineering, Vol. 32, pp. 115–127, Great Britain.