Geri Dön

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

Tavlama benzetimi yönteminin başlangıç sıcaklığını problem büyüklüğüne bağlayan genelgeçer bir yöntem

  1. Tez No: 129310
  2. Yazar: SERKAN ÖZGEN
  3. Danışmanlar: YRD. DOÇ. DR. İ. İLKAY BODUROĞLU
  4. Tez Türü: Yüksek Lisans
  5. Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2002
  8. Dil: İngilizce
  9. Üniversite: Boğaziçi Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 103

Özet

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.

Özet (Çeviri)

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.

Benzer Tezler

  1. Tez No

    762801

    Solving hard stable marriage problems using logic-based methods

    Mantık temelli yöntemler kullanarak zor istikrarlı evlilik problemlerini çözme

    SELİN EYÜPOĞLU

    Yüksek Lisans

    İngilizce

    İngilizce

    2022

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSabancı Üniversitesi

    Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı

    PROF. DR. ESRA ERDEM

  2. Tez No

    712172

    Talep tahmini için gri temelli bir yaklaşım

    A grey based approach to demand forecasting

    CEYDA TANYOLAÇ BİLGİÇ

    Doktora

    Türkçe

    Türkçe

    2022

    İşletmeİstanbul Teknik Üniversitesi

    İşletme Mühendisliği Ana Bilim Dalı

    PROF. DR. FERHAN ÇEBİ

  3. Tez No

    439483

    Modeling of the lateral load resistance of masonry infilled frames with innovative steel ties

    Yenilikçi çelik bağlar içeren yığma dolgu duvarlı betonarme çerçevelerin yatay yük direncinin modellenmesi

    MIRSALAR KAMARI

    Yüksek Lisans

    İngilizce

    İngilizce

    2016

    İnşaat Mühendisliğiİstanbul Teknik Üniversitesi

    İnşaat Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. OĞUZ GÜNEŞ

  4. Tez No

    2503

    Genital organ anomalisi gösteren olgularda kromozom ve x kromatini analizi

    Chromosom and x chromatin analysis in the cases have genital organ anomalies

    MUSTAFA SOLAK

    Doktora

    Türkçe

    Türkçe

    1985

    Tıbbi BiyolojiAnadolu Üniversitesi

    DOÇ. DR. NURETTİN BAŞARAN

  5. Tez No

    617998

    Adölesan eroin bağımlılarında çocukluk çağı travmları,stresle başa çıkma yöntemleri ve aile işlevlerinin değerlendirilmesi

    Childhood traumas, coping with stress and evaluation of family functions in adolescent heroin addicts

    ATİLLA ÇİFCİ

    Yüksek Lisans

    Türkçe

    Türkçe

    2019

    Çocuk Sağlığı ve HastalıklarıAnkara Üniversitesi

    Çocuk Sağlığı ve Hastalıkları Ana Bilim Dalı

    PROF. DR. SEVGİ BAŞKAN

Geri Dön