Akademik Veri Yönetim Sistemi
Tezin Türü: Yüksek Lisans
Tezin Yürütüldüğü Kurum: Marmara Üniversitesi, Fen Bilimleri Enstitüsü, Türkiye
Tezin Onay Tarihi: 2008
Tezin Dili: İngilizce
Öğrenci: BERNA KİRAZ
Danışman: Haluk Rahmi Topcuoğlu
Özet:STATİK VE DİNAMİK GENELLEŞTİRİLMİŞ ATAMA PROBLEMLERİ İÇİN YARDIMLI BULUŞSAL YAKLAŞIMLAR 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. ABSTRACT HYPER-HEURISTIC BASED APPROACHES FOR STATIC AND DYNAMIC GENERALIZED ASSIGNMENT PROBLEMS 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.