Geri Dön

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ı

  1. Tez No: 82978
  2. Yazar: DİLEK ŞEN
  3. Danışmanlar: DOÇ. DR. UĞUR AKMAN
  4. Tez Türü: Yüksek Lisans
  5. Konular: Kimya Mühendisliği, Chemical Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 1999
  8. Dil: İngilizce
  9. Üniversite: Boğaziçi Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Kimya Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

  1. 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

    Türkçe

    2014

    İşletmeKara Harp Okulu Komutanlığı

    Harekat Araştırması Ana Bilim Dalı

    PROF. DR. ORHAN TÜRKBEY

  2. 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

    İngilizce

    2012

    Endüstri ve Endüstri MühendisliğiKoç Üniversitesi

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

    YRD. DOÇ. ONUR KAYA

  3. 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

    İngilizce

    2021

    Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik Üniversitesi

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

    PROF. DR. SİNAN GÜREL

  4. 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

    İngilizce

    2008

    Endüstri ve Endüstri MühendisliğiBoğaziçi Üniversitesi

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

    DOÇ. DR. NECATİ ARAS

  5. 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

    İngilizce

    2016

    Endüstri ve Endüstri MühendisliğiÇukurova Üniversitesi

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

    PROF. DR. RIZVAN EROL