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: Optimizasyon problemi, Tavlama benzetimi, Optimization problem, Simulated annealing
  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ı: Belirtilmemiş.

Ö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. Tez No

    23584

    Channel and switchbox routing by simulated annealing

    Tavlama benzetimi ile kanal ve anahtar kutusu izgeleme

    ADNAN AÇAN

    Doktora

    İngilizce

    İngilizce

    1992

    Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik Üniversitesi

    PROF. DR. ZAFER ÜNVER

  2. Tez No

    33499

    Mopping and FPGA global routing using mean field annealing

    Orta alan tavlama metodu kullanılarak eşleme ve FPGA'lerdeki kaba rotalama problemlerinin çözümü

    İSMAİL HARİTAOĞLU

    Yüksek Lisans

    İngilizce

    İngilizce

    1994

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. CEVDET AYKANAT

  3. Tez No

    8162

    A Design method for data transmission filters

    Başlık çevirisi yok

    CEVAT GÖKÇEK

    Yüksek Lisans

    İngilizce

    İngilizce

    1990

    Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik Üniversitesi

    Elektrik-Elektronik Mühendisliği Ana Bilim Dalı

    DOÇ. DR. ZAFER ÜNVER

  4. Tez No

    66838

    GT yöntemlerinin sınıflandırması, performans ölçütleri, üretimle ilgili verileri kullanan yeni yöntemlere örnekler ve genetik algoritmalar

    Taxonomy of GT methods, performance measures,some new GT methods that is able to incorporate pertinent manufacturing data and genetic algorithms

    HATİCE DERİCİ

    Yüksek Lisans

    Türkçe

    Türkçe

    1997

    Endüstri ve Endüstri Mühendisliğiİstanbul Teknik Üniversitesi

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

    DOÇ. DR. M. BÜLENT DURMUŞOĞLU

  5. Tez No

    58580

    Generating short term observation schedules for space mission projects

    Uzay projelerinin kısa dönemli gözlem çizelgelemesi

    KEMAL KILIÇ

    Yüksek Lisans

    İngilizce

    İngilizce

    1997

    Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent Üniversitesi

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

    YRD. DOÇ. DR. SELİM AKTÜRK

Geri Dön