A Survey and applications in simulated annealing and nevral networks in combinatorial optimization
Başlık çevirisi mevcut değil.
- Tez No: 7971
- Danışmanlar: DOÇ. DR. M. AKİF EYLER
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 1989
- Dil: İngilizce
- Üniversite: Boğaziçi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Belirtilmemiş.
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
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.
Özet (Çeviri)
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. *
Benzer Tezler
- “Radar mesafe ölçümlerinde cross- correlation tekniklerinin kullanılması”
“Target distance measurement in radars using cross-correlation techniques”
SAMİ ÖZTÜRK
Yüksek Lisans
Türkçe
2001
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolYeditepe ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. SEDAT ŞİŞBOT
- Bir yolcu vagonunun dinamik tasarımı ve titreşim konferunun analizi üzerine bir yaklaşım
Dynamic design verification and vibratory comfort analysis of a passenger coach by using the lumped and the continious systems models
ERDAL ABA
- Optically stimulated luminescence (OSL) and its applications to archaelogical materials: A pilot study
Işık uyarımlı lüminesans (OSL) tarihlendirme yönteminin arkeolojik eserlere uygulanması: Arkeometrik pilot çalışma
EMRE YURDATAPAN
Yüksek Lisans
İngilizce
1997
ArkeometriOrta Doğu Teknik ÜniversitesiArkeometri Ana Bilim Dalı
YRD. DOÇ. DR. GÜLAY ÖKE
- Termaller ve cumuluslerde meteorolojik parametrelerin ölçülmesi, analizi ve konvektif yapının modellenmesi
Measurements and analysis of the meteorological parameters in thermals and cumulus clouds and modelling of the conventive structure
ZAFER ASLAN