Hyper-heuristic approaches for static and dynamic generalized assignment problems
Statik ve dinamik genelleştirilmiş atama problemleri için yardımlı buluşsal yaklaşımlar
- Tez No: 233361
- Danışmanlar: DOÇ. DR. HALUK TOPÇUOĞLU
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2008
- Dil: İngilizce
- Üniversite: Marmara Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 85
Özet
Statik optimizasyon problemlerinde uygunluk alanları süreç boyunca değişmezler ve önerilen algoritmaların asıl amacı verilen bir problem için optimum çözümü bulmaktır. Bununla birlikte, dinamik optimizasyon problemlerinde uygunluk fonksiyonu, problemin kısıtları, karar değişkenleri veya parametreler zamanla değişebilmektedir. Dinamik ortamlarda uygunluk alanları değişebildiğinden ana hedef global optimum değeri takip etmektir.Bu projede genelleştirilmiş atama problemlerinin statik ve dinamik versiyonları üzerine çalıştık. Genelleştirilmiş atama problemi NP-tam bir problemdir. Bu problemde amaç, her bir işin iş istasyonların kapasitelerini aşmadan yalnızca bir iş istasyonuna atanacak şekilde minimum maliyeti bulmaktır. Bu problemin dinamik versiyonunda işlerin maliyeti, kaynak tüketimleri ve kapasite kısıtlamaları süreç boyunca değiştirilmektedir.Bu projede ilk olarak statik genelleştirilmiş atama problemi için yardımlı buluşsal yaklaşımlar kullandık. Bir yardımlı buluşsal yöntem düşük seviyedeki sezgisel yöntemleri adaptif olarak kontrol eden yüksek seviyedeki bir sezgisel yöntemdir. Bu projede, önerdiğimiz yardımlı buluşsal yöntemler literatürde verilen iki algoritma ile karşılaştırıldı. Gerçekleştirdiğimiz deneylere göre, yardımlı buluşsal yöntemlerin diğer yöntemlerle benzer sonuçlar verdiğini gözlemledik.Ek olarak, dinamik genelleştirilmiş atama problemi için farklı yardımlı buluşsal yaklaşımlara bellek tabanlı teknik ekleyerek yeni buluşsal yaklaşımlar geliştirdik. Yardımlı buluşsal yaklaşımların diğer bellek tabanlı teknikten çevrimdışı performans metriği açısından daha iyi sonuçlar verdiğini gözlemledik.
Özet (Çeviri)
In a stationary optimization problem, the fitness landscape does not change during the process and the main goal of a proposed algorithm is to find an optimal solution for the given problem. On the other hand, in dynamic optimization problems, the fitness function, problem constraints, decision variables or even environmental parameters may change in time. Since the fitness landscape may change over time, the main motivation in a dynamic optimization problem is to track the global optimum value.In this thesis, we study the static and dynamic versions of the generalized assignment problem. The generalized assignment problem is an NP-complete problem to assign a set of jobs to a set of agents such that each job is assigned to exactly one agent to minimize the total cost without exceeding each agent?s resource capacity. On the other hand, the costs of jobs, resource consumption and the capacity constraints are changed during the process, in dynamic version of the problem.In this thesis, we first present the hyper-heuristic based approaches for the static generalized assignment problem. A hyper-heuristic is a high-level heuristic that adaptively controls a set of simple, predefined low-level heuristics. In this thesis, our proposed hyper-heuristic approaches are compared with three algorithms given in the literature. Based on the experimental study, it is observed that the hyper-heuristic approaches give competitive results with respect to quality of solutions for various problem instances.Additionally, we present new heuristics for the dynamic generalized assignment problem by extending the memory-based technique with various hyper-heuristic approaches. Our hyper-heuristic based approaches significantly outperform memory-based technique for various problem instances with respect to quality of solutions which is expressed with the offline performance metric.
Benzer Tezler
- Dinamik eş zamanlı topla-dağıt araç rotalama problemi için matematiksel model ve sezgisel yaklaşımlar
Mathematical formulations and heuristic approaches for the dynamic vehicle routing problem with simultaneous pickup and delivery
BURAK AYDOĞDU
Doktora
Türkçe
2017
Endüstri ve Endüstri MühendisliğiGazi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. BAHAR ÖZYÖRÜK
- Elektrik güç sistemi koruma analizinde petri ağları kullanımı ve uygulamaları
Usage and applications of petri nets in electric power system protection analysis
NİHAT PAMUK
Doktora
Türkçe
2012
Elektrik ve Elektronik MühendisliğiSakarya ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. YILMAZ UYAROĞLU
- A classification-based heuristic approach for dynamic environments
Dinamik ortamlar için tasarlanmış sınıflandırıcı tabanlı sezgisel bir yaklaşım
ŞEYDA YILDIRIM BİLGİÇ
Yüksek Lisans
İngilizce
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. AYŞE ŞİMA UYAR
- Hyper-heuristics in dynamic environments
Dinamik ortamlarda üst-sezgiseller
BERNA KİRAZ
Doktora
İngilizce
2014
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. AYŞE ŞİMA ETANER UYAR
- Hipersezgisel yöntemlerle lojistik ağ tasarımı ve optimizasyon
Logistic network design and optimization using hyperheuristic methods
VURAL EROL
Doktora
Türkçe
2017
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. MURAT BASKAK
PROF. DR. GÜLGÜN KAYAKUTLU