Birleşi eniyileme problemleri için oto-kontrollü yerel arama yöntemi
Self-controlled local search method for combinatorial optimization problems
- Tez No: 155688
- Danışmanlar: PROF.DR. BERNA DENGİZ
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2004
- Dil: Türkçe
- Üniversite: Gazi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 145
Ö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 Key Words : combinatorial optimization, heuristic optimization, local search vehicle routing, scheduling, quadratic assignment, topological design Page Number: 225 Adviser : Prof. Dr. Berna DENGİZ
Benzer Tezler
- 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
2001
Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. İHSAN SABUNCUOĞLU
- Zaman pencereli gezgin satıcı problemi için yeni karar modelleri
New decision models for travelling salesman problem with time windows
ÖZGE NİMET KOÇ
Yüksek Lisans
Türkçe
2012
Endüstri ve Endüstri MühendisliğiBaşkent ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. İMDAT KARA
- Primal-dual heuristics for solving the set covering problem
Küme örtüleme problemlerinin çözümü için temel-eşlenik sezgiseller
BELMA YELBAY
Yüksek Lisans
İngilizce
2009
Endüstri ve Endüstri MühendisliğiSabancı ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. Ş.İLKER BİRBİL
YRD. DOÇ. DR. KEREM BÜLBÜL
- An evolutionary algorithm for multiple criteria problems
Çok kriterli problemler için evrimci bir algoritma
BANU SOYLU
Doktora
İngilizce
2007
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. MURAT KÖKSALAN
- FIR filter design by convex optimization using rank refinement
Kerte arıtımı ile dışbükey eniyileme tabanlı FIR süzgeç tasarımı
MEHMET DEDEOĞLU
Yüksek Lisans
İngilizce
2014
Elektrik ve Elektronik Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. ORHAN ARIKAN