A Survey and applications in simulated annealing and nevral networks in combinatorial optimization

Abstract

VI TAVLAMA BENZETİMİ VE SİNİRSEL ŞEBEKELERİN KOMBİNATORYEL ENİYİLEME PROBLEMLERİNDE KULLANIMI KONUSUNDA BİR LİTERATÜR ARAŞTIRMASI VE UYGULAMALAR ÖZET Tavlama Benzetimi (T.B.), kombinatoryel eniyileme problemlerinde kullanılan rassal bir arama yöntemidir. Her türlü eniyileme problemine uygulanabilir. T.B. `de arama sırasında amaç fonksiyonunun değerini arttıran adımlar da kabul edildiğinden yerel minimumlara takılma şansı azalır. Tavlama Benzetiminde İstatistiksel Mekanik ilkeleri kullanılır. T.B. 'de ana fikir, eniyilenen problemin parametreleriyle hayali bir fiziksel sistemin parçacıkları arasında bir analoji kurulmasıdır. Eniyilenen problemin amaç fonksiyonu, fiziksel sistemin enerjisi olarak düşünülebilir. Fiziksel sistemler tavlandıklarında, yani yüksek sıcaklıklardan yavaş yavaş düşük Bıçaklıklara indirildiklerinde en düşük enerji konfigürasyonlarma ulaşırlar. T.B.'de fiziksel sistemin tavlama anındaki evrimi, istatistiksel olarak modellenir ve bu model eniyileme problemine uygulanır. Bu durumda hayali fiziksel sistemin en düşükvıı enerjili konfigürasyonları, eniyileme probleminim global eniyi konfigürasyonlarma karşılık gelmektedir. Beynin kombinatoryel problemlerde çok güçlü bir hesaplama kapasitesine sahip olması, örneğin daha önce karşılaşılan bir cismin eksik görüntüsünün birkaç milisaniye içinde tamamlanıp tanılanması, beyinde bulunan milyarlarca paralel işlemci (sinir) sayesindedir. Hopfield, yukarıda bahsedilen problemin matematiksel modelini geliştirmiş ve bu modelde, beyindeki sinirsel şebekenin bir amaç fonksiyonunu maksimum gradyant yöntemiyle eniyiledigini göstermiştir. Bu modelden esinlenilerek Kombinatoryel Eniyileme Problemlerinin de yapay sinirsel şebekeler sayesinde çözülebileceği anlaşılmıştır. Kombinatoryel problemlerin sinirsel şebeke modelleriyle çözülmesinde kullanılan temel yaklaşım, bir ceza fonksiyonunun maksimum gradyant yöntemiyle paralel işlemciler üzerinde eniyilenmesidir. Bu çalışmada Tavlama Benzetimi ve Sinirsel Şebekelerin, kombinatoryel eniyileme problemlerine uygulanımı konusunda bir literatür taraması yapılmıştır. Sinirsel Şebekelerle bilgisayar benzetimi yoluyla üç deney yapılmıştır: Doğrusal Programlama Yapan Şebeke, Gezgin Satıcı Problemi Çözen Şebeke ve Çağrışımsal Bellek Şebekesi. Ayrıca T.B. Algoritmasının paralel işlemcilerde de çalıştırılabileceği tek işlemcili bir bilgisayarda yapılan bir Gezgin Satıcı Problemi çözümü simulasyonu ile gösterilmiş ve sonuçlar klasik yöntemlerin verdiği sonuçlarla ve Sinirsel Şebekelerin sonuçlarıyla karşılaştırılmıştır.

IV A SURVEY AND APPLICATIONS IN SIMULATED ANNEALING AND NEURAL NETWORKS IN COMBINATORIAL OPTIMIZATION Abstract Simulated Annealing (SA) is a general stochastic search method that can be used in all kinds of (combinatorial) optimization problems. Because uphill steps are allowed in a minimization problem, SA has a lesser tendency to get stuck in local minima. SA uses principles of Statistical Physics. There is an equivalence between the numerous parameters of the system being optimized and the particles in an imaginary physical system. The objective function of the optimization problem corresponds to the energy of the physical system. States of low energy in the imaginary physical system are thus the near-global optimum configurations sought, in the optimization problem. The trick to find these is to model statistically the evolution of the physical system at a series of temperatures which allow it to anneal into a state of high order (low entropy) and very low energy. Neural Networks, on the other hand, are also being used as a tool for solving optimization problems. The brain has a tremendous computational power in combinatorial problems. Identification of noisy images is one such problem. The brain solves this problem within milliseconds, thanks to the parallel processing neurons. What Hopfield and others have shown is that the neurons are minimizing an `energy` function along the well-known maximum gradient trajectory. In the case of theTSP, the energy function consists of penalty functions to get rid of infeasible solutions plus a total distance term. In this thesis, a literature survey is done on the applications of Simulated Annealing and Neural Networks in combinatorial optimization. Also, three experiments have been done with simulated Neural Networks, namely the Linear Programming Network, the Travelling Salesman Network, and a Content Addressable Memory Network. Furthermore, simulation of the Simulated Annealing Algorithm solving the Travelling Salesman Problem on parallel processors has been made on a sequential computer. The results have been compared to those of Neural Networks and conventional optimization methods. *