A Simulated annealing algorithm for mixed integer non linear global optimization
Karışık tamsayılı doğrusal olmayan problemlerin global eniyilemesi için tavlama benzetimi algoritması
- Tez No: 82978
- Danışmanlar: DOÇ. DR. UĞUR AKMAN
- Tez Türü: Yüksek Lisans
- Konular: Kimya Mühendisliği, Chemical Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 1999
- Dil: İngilizce
- Üniversite: Boğaziçi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Kimya Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 225
Özet
VI ÖZET Bu tezde, sürekli ve tamsayı değişkenlerin birlikte yer aldığı, doğrusal olmayan kısıtlı eniyileme problemlerinin global çözümü için tavlama benzetimi tekniğine dayalı bir program geliştirilmiştir. Tavlama benzetimi kısıtsız bir eniyileme tekniğidir. Tavlama benzetimi, bir maddenin önce ısıtılıp sonra yavaşça soğutulması şeklinde özetlenebilecek tavlanma süreci ile çok değişkenli eniyileme problemi arasında benzerlik kurar. Tavlama benzetimi, eşitlik ve eşitsizlik kısıtlarım doğrudan içermese de, ceza fonksiyonu yöntemi ile dolaylı olarak bu kısıtlar probleme dahil edilebilir. Ceza fonksiyonu amaç fonksiyonunu kısıt ihlalleri için cezalandırmak sureti ile, kısıtlı bir problemi kısıtsız bir probleme çevirir. Tavlama benzetimi algoritması da ceza fonksiyonu yöntemi ile cezalandırılmış olan fonksiyonun üzerinden eniyilemeyi gerçekleştirir. Önerilen algoritmada, tavlama benzetimine uygun bir ceza fonksiyonu yöntemi ve ceza parametresi formülasyonu kullanılmıştır. Geliştirilmiş olan program, yerel eniyilere takılmadan, global eniyiyi bulma gücüne sahiptir. Yerel-arama algoritmaları bu özelliğe sahip değildirler. Başlangıç noktasına bağlı olarak fonksiyon yüzeyindeki ilk yerel eniyide takılırlar. Tavlama benzetimi, algoritma içinde kullanılan“başarılı adım kabul”kriteri, Metropolis kriteri, sayesinde yerel-arama algoritmalarına göre böyle bir üstünlüğe sahiptir. Bu tezde önerilmiş olan tavlama benzetimi algoritması, sürekli değişkenlerle tamsayı değişkenleri birlikte çözüm içine alabilir ve orijinal problemin ayrıştırılmasını gerektirmez. Tam sayılarla sürekli sayılan aynı anda çözüme götürmek, hesaplama zamanı olarak pahalıdır fakat bir çok problemin çözümünde, problemin algoritmaya kolaylıkla uyarlanmasını sağlar. Ayrıca tavlama benzetimi algoritması, kesikli amaç fonksiyonu ve/veya kısıtlar içeren problemlerin çözümünde de kullanılabilir.vu Önerilen algoritma, yirmibir örnek problem üzerinde sulanmıştır. Kanşık tam ve sürekli doğrusal olmayan problem kategorisinde üç problem kimya mühendisliği problemleridir: i) çok ürünlü proses, ii) keskin olmayan damıtma ve iii) ısı değiştirici ağı. Geliştirilmiş olan tavlama benzetimi algoritması bu problemlerin çözümünde başarılı bulunmuştur. Tavlama benzetimi algoritması, son zamanlarda çıkan türev bazlı gerekirci (rastlantısal olmayan) algoritmalarla karşılaştırıldığında esnek, genele uygulanabilir ve problemlere kısıt getirmeyen hali ile üstündür fakat bu üstünlük daha fazla hesaplama zamanı pahasınadır. Ayrıca tavlama benzetimi algoritması, şu anda literatürde tek olan rastlantısal kanşık tamsayılı doğrusal olmayan problem çözücüsü, M-SIMPSA'dan daha başarılı bulunmuştur.
Özet (Çeviri)
IV ABSTRACT In this thesis, a simulated annealing algorithm for the global solution of constrained Mixed-Integer Non-Linear Programming (MINLP) problems is proposed. Simulated annealing is an unconstrained optimization technique, which draws an analogy between the annealing of a solid and the optimization of a multi variable problem. The algorithm is not capable of handling equality and/or inequality constraints directly, but incorporates them through the penalty-function method. The penalty-function method converts a constrained problem into an unconstrained one by penalizing the objective function value for constraint violations. In the proposed simulated annealing algorithm, a penalty-function method and a penalty-parameter schedule appropriate for the mechanism of simulated annealing is implemented. The developed code is able to find its way towards the global optimum and does not get trapped in local minima that may be present on the function landscape. This is an important advantage over local-search algorithms, which get trapped in the first local minimum on their optimization path. Hence the performance of the local-search algorithms is very dependent on the starting point. Simulated annealing algorithm operates independently of the starting point via its“success-acceptance”criterion, the Metropolis criterion. The proposed algorithm is able to handle integer and/or binary variables together with the continuous variables, and does not require any decomposition of the problem into sub-problems, which have to be iteratively solved for. Handling integer variables simultaneously with the continuous variables is computationally expensive but this provides ease of implementation for many problems. The algorithm is also capable of dealing with functions that may have discontinuities, and requires neither the continuity nor the linearity of the objective function and the constraints.The proposed algorithm was tested on a broad range of examples with increasing level of difficulty. Three examples in the MINLP problem category are specific to chemical engineering: i) multi-product batch-plant problem, ii) nonsharp-distillation problem, and iii) heat-exchanger-network synthesis problem. The proposed algorithm was found to be successful in the solution of these problems. The simulated annealing algorithm that is proposed in the current work is found to be more flexible, more generally applicable, and less restricted, compared to only recently available deterministic, gradient-based, and branch-and-bound based MINLP solvers, but at a computational expense. Besides these advantages, in general, the proposed simulated annealing algorithm performs better than the only available stochastic MINLP solver, M- SIMPSA.
Benzer Tezler
- Bütünleşik tedarik zinciri ağında tesis yeri seçimi problemi için bulanık çok amaçlı programlama modeline sezgisel bir yaklaşım: Tavlama benzetimi algoritması
A heuristic approach to fuzzy multi-objective programming model for facility location problem in an integrated supply chain network: Simulated annealing algorithm
HÜSEYİN ALİ SARIKAYA
Doktora
Türkçe
2014
İşletmeKara Harp Okulu KomutanlığıHarekat Araştırması Ana Bilim Dalı
PROF. DR. ORHAN TÜRKBEY
- A mixed integer location, inventory and pricing model for closed loop supply chains
Kapalı devre tedarik zincirleri için bir karma tamsayılı lokasyon, envanter ve fiyatlandırma modeli
BUŞRA ÜREK
Yüksek Lisans
İngilizce
2012
Endüstri ve Endüstri MühendisliğiKoç ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. ONUR KAYA
- Energy efficient scheduling in flow-shop and parallel machine robotic cells
Akış tipi ve paralel makineli robotik hücrelerde enerji tasarruflu çizelgeleme
ÇİYA AYDOĞAN
Yüksek Lisans
İngilizce
2021
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. SİNAN GÜREL
- New heuristics for competitive and hierarchical facility location problem
Rekabetçi ve hiyerarşik tesis yeri seçimi problemi için sezgisel yöntemler
HALE YEGE
Yüksek Lisans
İngilizce
2008
Endüstri ve Endüstri MühendisliğiBoğaziçi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. NECATİ ARAS
- Coordinated production – inventory – distribution - routing problem on closed loop supply chain with recycling option
Geri kazanım opsiyonlu kapalı döngü tedarik zincirlerinde eşgüdümlü üretim envanter dağıtım rotalama problemi
YUSUF KUVVETLİ
Doktora
İngilizce
2016
Endüstri ve Endüstri MühendisliğiÇukurova ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. RIZVAN EROL