Converging preferred regions in multi-objective combinatorial optimization problems
Çok amaçlı bileşi optimizasyonu problemlerinde tercih edilen bölgeye yakınsama
- Tez No: 286259
- Danışmanlar: PROF. DR. MURAT KÖKSALAN
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Etkileşimli yaklaşım, Tam sayılı programlama, Çok amaçlı birleşi problemleri, Çok amaçlı karar verme, Çok amaçlı programlama, Intereactive approach, Integer programming, Multiobjective combinatorial optimization, Multiobjective decision making, Multiobjective programming
- Yıl: 2011
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Bölümü
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Çok amaçlı bileşi problemleri için etkin çözümleri bulmak zor olduğu gibi; tümünü bulmaya çalışmak pratik bir yaklaşım da değildir. Çünkü bu problemler için etkin çözüm sayısı problem büyüklüğü arttıkça üstsel bir büyüme gösterir. Bu nedenle bu tezde, sadece belirli bir bölgedeki etkin çözümleri bulan bir algoritma geliştirdik. Bu algoritmayı etkin çözümlerin bulunduğu bölgeleri yaklaşık olarak tanımlayan sezgisel bir yaklaşım ile birleştirdik. Karar verici ile etkileşim kurarak, sezgisel yöntem önce karar vericinin ilgi alanı olan bölgeyi yaklaşık olarak tanımlamaktadır. Daha sonra, kesin çözümleri bulan algoritmamız bu bölgedeki tüm etkin çözümleri bulmaktadır. Algoritmalarımızın performansını rastgele yarattığımız farklı çok amaçlı bileşi problemleri üzerinde (Çok Amaçlı Atama Problemi, Çok Amaçlı Sırt Çantası Problemi ve Çok Amaçlı En Kısa Yol Problemi) değerlendirdik ve yaklaşımımızın iyi çalıştığını gösterdik.Tüm etkin çözümler içinde her bir kriterin aldığı en kötü değere, kriterlerin doğru ölçeklenmesinde de kullanıldığı için bir çok algoritma tarafından gereksinim duyulur. Bu değerlerden oluşan nokta nadir noktası olarak tanımlanır ve özellikle iki amaçtan daha fazla amaçlı büyük boyuttaki problemler için bu noktanın bulunması kolay değildir. Biz bu tezde, çok amaçlı tamsayı programlama problemleri için nadir noktasını bulan bir metot geliştirdik. Algoritmamız nadir noktasının kesin değerini bulabilmesine ek olarak, tercih edilirse eğer performans garantisi ile nadir için alt ve üst sınır da bulabilmektedir. Algoritmamızın iyi çalıştığını yine Çok Amaçlı Atama Problemi, Çok Amaçlı Sırt Çantası Problemi ve Çok Amaçlı En Kısa Yol Problemi üzerinde yaptığımız deneyler ile gösterdik.Bunlara ek olarak, karar vericinin tercihlerinin bir kuvazi konkav değer fonksiyonu ile uyumlu olduğunu varsayarak; çok amaçlı tamsayı programlama problemlerini çözmek için etkileşimli bir algoritma geliştirdik. Karar vericinin ikili karşılaştırmalarından elde ettiğimiz konveks konileri baz alarak; algoritmamız daha az tercih edilen bölgedeki çözümleri engelleyen kısıtlar üretmektedir. Bu algoritmamız en çok tercih edilen çözümü bulmayı garantilemektedir. Çok Amaçlı Atama Problemi, Çok Amaçlı Sırt Çantası Problemi ve Çok Amaçlı En Kısa Yol Problemi üzerinde yaptığımız deneyler; yöntemimizin makul sayıda ikili karşılaştırma gerektirdiğini, ve makul sürede sonuca ulaştığını göstermiştir.
Özet (Çeviri)
Finding the true nondominated points is typically hard for Multi-objective Combinatorial Optimization (MOCO) problems. Furthermore, it is not practical to generate all of them since the number of nondominated points may grow exponentially as the problem size increases. In this thesis, we develop an exact algorithm to find all nondominated points in a specified region. We combine this exact algorithm with a heuristic algorithm that approximates the possible locations of the nondominated points. Interacting with a decision maker (DM), the heuristic algorithm first approximately identifies the region that is of interest to the DM. Then, the exact algorithm is employed to generate all true nondominated points in this region. We conduct experiments on Multi-objective Assignment Problems (MOAP), Multi-objective Knapsack Problems (MOKP) and Multi-objective Shortest Path (MOSP) Problems; and the algorithms work well.Finding the worst possible value for each criterion among the set of efficient solutions has important uses in multi-criteria problems since the proper scaling of each criterion is required by many approaches. Such points are called nadir points. It is not straightforward to find the nadir points, especially for large problems with more than two criteria. We develop an exact algorithm to find the nadir values for multi-objective integer programming problems. We also find bounds with performance guarantees. We demonstrate that our algorithms work well in our experiments on MOAP, MOKP and MOSP problems.Assuming that the DM's preferences are consistent with a quasiconcave value function, we develop an interactive exact algorithm to solve MIP problems. Based on the convex cones derived from pairwise comparisons of the DM, we generate constraints to prevent points in the implied inferior regions. We guarantee finding the most preferred point and our computational experiments on MOAP, MOKP and MOSP problems show that a reasonable number of pairwise comparisons are required.
Benzer Tezler
- Toplu taşıma hatlarının optimizasyonu için bir model önerisi: Sivas örneği
A model proposal for the optimization of public transportation lines: The case of Sivas
İSMAİL ÖZÇELİK
Yüksek Lisans
Türkçe
2026
Ulaşımİstanbul Teknik Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
DOÇ. DR. HÜSEYİN ONUR TEZCAN
- Avrupa Merkez Bankası'nın oluşumu, para politikası, uygulama sorunları ve Türkiye etkileri
Formation of European Central Bank, its monetary policy, application problems and its effects on Turkey
ALİ POLAT
- Çok amaçlı karar vermede yeni bir yöntem ve uygulaması
Application working on trade banking of a new multiple objective decision making method
A.COŞKUN DÜNDAR
Doktora
Türkçe
1995
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiPROF.DR. RAMAZAN EVREN
- Cam sektöründe talep tahmin yöntemlerinin uygulanması ve değerlendirilmesi
Application and assessment of the demand forecasting methods in the glass sector
NESLİHAN DEMİRCİ
Yüksek Lisans
Türkçe
2015
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. MURAT BASKAK
- Sağlık örgütlenmesi yaklaşımları ve Türkiye'de hastane binalarını prefabrikasyon teknolojilerine göre planlama sorunu üzerinde bir araştırma
An approach to health organizations and a research on the problem of planning hospital buildings with prefabrication technologies in Turkey
GAYE OĞULTEKİN
Yüksek Lisans
Türkçe
2001
Mimarlıkİstanbul Teknik ÜniversitesiMimarlık Ana Bilim Dalı
PROF. DR. EROL KULAKSIZOĞLU