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: Belirtilmemiş.
- 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ı: 153
Ö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
- Bulanık kontrolör ile yeni bir global eniyileme yöntemi
A New method of global optimization by using fuzzy controller
BURAK BERK ÜSTÜNDAĞ
Doktora
Türkçe
2000
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiPROF.DR. ATİLLA BİR
- 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
- 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
- Jenerik denizaltı geometrisinin katsayı tabanlı manevrakarakteristiklerinin had ve analitik çözüm yöntemleri ile analizi
Analysis of coefficient-based maneuvering characteristics of generic submarine geometry by CFD and analytical solution method
OĞUZHAN KIRIKBAŞ
Doktora
Türkçe
2024
Gemi Mühendisliğiİstanbul Teknik ÜniversitesiGemi İnşaatı ve Gemi Makineleri Mühendisliği Ana Bilim Dalı
PROF. DR. ŞAKİR BAL