Geri Dön

Birleşi eniyileme problemleri için oto-kontrollü yerel arama yöntemi

Self-controlled local search method for combinatorial optimization problems

  1. Tez No: 155688
  2. Yazar: ÇİĞDEM ALABAŞ
  3. Danışmanlar: PROF.DR. BERNA DENGİZ
  4. Tez Türü: Doktora
  5. Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
  6. Anahtar Kelimeler: combinatorial optimization, heuristic optimization, local search vehicle routing, scheduling, quadratic assignment, topological design
  7. Yıl: 2004
  8. Dil: Türkçe
  9. Üniversite: Gazi Ü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ı: Belirtilmemiş.

Özet

BIRLEŞI ENIYILEME PROBLEMLERİ İÇİN OTO-KONTROLLÜ YEREL ARAMA YÖNTEMİ (Doktora Tezi) Çiğdem ALABAŞ GAZİ ÜNİVERSİTESİ FEN BİLİMLERİ ENSTİTÜSÜ Haziran 2004 ÖZET Kabul edilebilir bir zaman sınırı içinde eniyi çözümü bulunamayan NP-zor birleşi problemler için sezgisel yöntemlerin kullanılması kaçınılmaz olmaktadır. Genel amaçlı sezgisel yöntemler, arama sürecini yerel optimum tuzaklarından kurtaran çeşitli stratejileri sayesinde optimum veya optimuma yakın çok daha kaliteli çözümleri üretebilmektedirler. Günümüzde genel amaçlı sezgisel yöntemler sınıfında genetik algoritmalar, tabu arama, tavlama benzetimi, yapay sinir ağları ve karınca kolonileri sayılabilir. Bu sezgisel yöntemler yüksek kaliteli çözümlere ulaşabilmelerine rağmen bu çözümlere ulaşmak için genellikle çok daha uzun bir zaman harcamaktadırlar. Çözüm kalitesi ve çözüm zamanı arasındaki ödünleşim tüm problem sınıflarında ortaya çıkmaktadır. İhtiyaç duydukları sürenin yanı sıra genel amaçlı sezgisellerin bir başka dezavantajı, genellikle bir çok parametre tarafından kontrol edilmeleridir. En iyi parametre kümesinin farklı problem sınıfları için yeniden belirlenmesinin yanı sıra, aynı problem sınıfında ancak farklı boyutlarda olan problemler için hatta aynı boyuttaki farklı girdi verilerine sahip problemler için yeniden belirlenmesi gerekebilmektedir. Bu durum genel amaçlı sezgisel yöntemlerin farklı problemlere uygulanmasını zorlaştırmaktadır. Sonuç olarak, kaliteli çözümleri makul zaman sınırları içinde bulan daha basit ve daha az parametreli11 sezgisel yöntemlerin geliştirilmesi kaçınılmaz bir ihtiyaçtır. Bu çalışmada söz konusu ihtiyaçlara cevap veren yeni bir sezgisel yöntem önerilmektedir. Oto- kontrollü yerel arama olarak adlandırılan bu sezgisel yöntem kullandığı tek parametreyi arama esnasında ilgilenilen problemin cevap yüzeyi yapısına bağlı olarak dinamik bir şekilde belirlemekte ve böylece kullanıcı tarafından belirlenmesi gereken hiçbir parametre kullanmamaktadır. Kullanıcı bu algoritmayı dilediği probleme parametre eniyilemesi yapmaksızın doğrudan uygulayabilmektedir. Oto-kontrollü yerel arama algoritmasının performansı araç rotalama, permütasyon akış atölyesi çizelgeleme, kareli atama ve topoloji tasarımı olmak üzere dört farklı sınıftaki birleşi eniyileme problemi üzerinde test edilmiş ve diğer yerel aramaya dayalı genel amaçlı sezgisel algoritmaların temel durumlarından üstün bir performansa sahip olduğu gösterilmiştir. Oto- kontrollü yerel arama algoritmasının aynı zamanda, literatürdeki rakipleriyle ya başabaş rekabet edebildiği ya da onlardan daha iyi çözümlere makul zaman dilimleri içinde ulaşabildiği belirlenmiştir. Bilim Kodu Anahtar Kelimeler Sayfa Adedi Tez Yöneticisi :919 : birleşi eniyileme, sezgisel eniyileme, yerel arama araç rotalama, çizelgeleme, kareli atama, topolojik tasarım :225 : Prof. Dr. Berna DENGİZ

Özet (Çeviri)

Ill SELF-CONTROLLED LOCAL SEARCH METHOD FOR COMBINATORIAL OPTIMIZATION PROBLEMS (Ph.D. Thesis) Çiğdem ALABAŞ GAZI UNIVERSITY INSTITUTE OF SCIENCE AND TECHNOLOGY June 2004 ABSTRACT Heuristic methods must be employed for finding approximate solutions to NP- hard optimization problems because the optimum solutions cannot be obtained within acceptable computation times utilizing the exact methods. General purpose heuristics named metaheuristics guide the search process to escape from the local optimum tracks and find more qualified solutions close to global optimum. Genetic algorithms, tabu search, simulated annealing, artificial neural networks and ant colonies are in the class of metaheuristic algorithms. Metaheuristics have two main drawbacks: The first is that the longer the computing time, the higher the prospect of finding the qualified solutions and the second is dependence of the solution quality upon a set of control parameters of the algorithms. The best set of the parameters should be re determined for the each different type, size and input data of the problems. The parameter optimization hardens the application of metaheuristics to real-life combinatorial problems. As a result, there is an obvious need for simple, robust and parameter-free heuristic methods which can reach high quality solutions within acceptable solution times. Self-controlled local search method proposed in this study is capable to meet these requirements. Only one parameter of the method is calculated as dynamically using the responce surface information of the problem and the performance measure of the method during the search process. The user can apply self-controlled local search to any combinatorialIV problem without the parameter optimization. Self-controlled local search algorithm was tested on a suite of test problems from the four different application areas as known vehicle routing, permutation flow-shop scheduling, quadratic assignment and topological design. The results indicate that the algorithm has better solution quality than the basic forms of the other local search-based metaheuristics. At the same time, self-controlled local search usually outperforms its competitors in the literature or competes with those respect to solution quality and solution times. Science Code : 919

Benzer Tezler

  1. Tez No

    112573

    Parameter selection for genetic algorithm-based simulation optimization

    Genetik algoritmalara bağlı benzetim eniyileme uygulamalarında parametre seçimi

    ONUR BOYABATLI

    Yüksek Lisans

    İngilizce

    İngilizce

    2001

    Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. İHSAN SABUNCUOĞLU

  2. Tez No

    105375

    Rastgele markov alanları ve hücresel sinir ağları ile görüntü işleme

    Image processing with markow random fields and cellular neural networks

    MAHMUT ŞAMİL SAĞIROĞLU

    Yüksek Lisans

    Türkçe

    Türkçe

    2001

    Elektrik ve Elektronik Mühendisliğiİstanbul Üniversitesi

    Elektronik Mühendisliği Ana Bilim Dalı

    DOÇ. DR. OSMAN NURİ UÇAN

  3. Tez No

    143063

    Topology and bandwidth adaptation in optical WDM backbone networks with dynamic traffic

    Değişken veri trafikli optik WDM omurga ağlarında topoloji ve bant genişliği uyarlama

    AYŞEGÜL GENÇATA

    Doktora

    İngilizce

    İngilizce

    2003

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

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

    PROF. DR. MEHMET BÜLENT ÖRENCİK

  4. Tez No

    39285

    Solving image procesing problems by using nonstandart regularization

    Standart olmayan düzgünleştirme kullanarak görüntü işleme problemlerinin çözümü

    TOLGA ACAR

    Yüksek Lisans

    İngilizce

    İngilizce

    1994

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    DOÇ.DR. MUHİTTİN GÖKMEN

  5. Tez No

    11659

    Two new algorithms for the linear assignment problem

    Başlık çevirisi yok

    OYA EKİN

    Yüksek Lisans

    İngilizce

    İngilizce

    1990

    Matematikİhsan Doğramacı Bilkent Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DOÇ. MUSTAFA AKGÜL

Geri Dön