Geri Dön

Local search management approaches in memetic algorithms for solving exam timetabling problems

Sınav zamanı çizelgeleme problemlerinin çözümü için memetik algoritmalarda yerel arama yönetimi yaklaşımları

  1. Tez No: 371503
  2. Yazar: ERSAN ERSOY
  3. Danışmanlar: YRD. DOÇ. DR. A. ŞİMA UYAR, YRD. DOÇ. DR. ENDER ÖZCAN
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2007
  8. Dil: İngilizce
  9. Üniversite: İstanbul Teknik Üniversitesi
  10. Enstitü: Bilişim Enstitüsü
  11. Ana Bilim Dalı: İleri Teknolojiler Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 51

Özet

Genetik Algoritmalar (GAs) ile yerel arama tekniklerini birle ştiren Memetik Algoritmalar (MAs), NP-Tam olan sınav zamanlama problemlerinin çözümü için etkili metotlardır. Bununla beraber, çoklu kısıtlamalı sınav zamanlama problemlerinin çözümü için olan MAs çok sayıda yerel arama metodu içerebilir. Bu durumda, algoritmanın ba şarısı, bu metotların yönetilmesine ba ğlıdır. Farklı yöntemler, farklı kalitede sonuçlar do ğurur. Bir kısıtlamanın ihlalinin düzeltilmesi, ba şka bir kısıtlama için ihlaller yaratabilir. Bu çalı şmada, uygun bir tepe tırmanma yönetim mekanizmasının bulunması amaçlanmaktadır. 2 tip ba şlatma metodu, 16 farklı tipi içeren 3 farklı tepe tırmanıcı yönetim mekanizma grubu uygulanmı ştır. Bu mekanismalara hipertepe-tırmanıcıları olarak adlandırılmılardır. Hipertepe- tırmanıcıları her biri farklı bir kısıtlamayı sa ğlamayı çalı şan 3 farklı tepe tırmanıcısını kullanma töntemine göre farklıdır. Đlk grupta, tepe tırmanıcılar önceden belirlenmi ş bir sırayla teker, teker uygulanırlar. Đkinci grupta, tepe tırmanıcıların sıralanması için kısıtlamaların ihlal bilgisi kullanılır. Ek olarak, bir tanesi rasgele tepe tırmanıcılarını sıralayan ve di ğeri de tepe tırmanıcıları yerine karınca sistemi kullanan iki MA bu gruba eklenmi ştir. Son grubun yönetim metotları hiper-sezgisel yöntemleri kullanmaktadır. Bir hiper-ke şifsel önce alt seviye ke şifsel yöntemlerden bir tane ke şifsel yöntem seçer ve uygular. Deney sonuçları hem kendi içlerinde hem de literatürde sunulan di ğer tekniklerin sonuçlarıyla kar şıla ştırılmı ştır. Deneyler gösterir ki, tepe tırmanıcıların yönetimi için hiper-sezgisel stratejilerinin kullanımı sınav zamanlama problemleri için olan Memetik Algoritmalarda daha iyi sonuçlar veriyor.

Özet (Çeviri)

Memetic Algorithms (MAs), that combine Genetic Algorithms (GAs) with local search techniques, are effective methods for solving exam timetabling problems which are NP- complete. Furthermore, MAs for solving multi-constraint examination timetabling problems can have multiple local search methods. In this situation, success of the algorithm is depended on the management of these methods. Different policies are resulted in different quality of solutions. Repairing violations of one constraint can create violations for another constraint. In this study, finding a proper hill climbing management mechanism is aimed. Two types of initializations and three categories of hill climbing management mechanisms that consist of sixteen different types are implemented. These mechanisms are named as hyperhill-climbers . Hyperhill-climbers are different in policy of using three kinds of hill climbers; each one is responsible for satisfying different type of constraints. In the first group, hill climbers are applied one by one in a predetermined order. Violation information of constraints is used for ordering of the hill climbers in the second group. In addition, two MAs, one of which randomly make an apply order of hill climbers and the other executes an Ant System instead of hill climbers, are included into this group. Management methods of last group use hyper-heuristic policies. A hyper-heuristic select and apply a heuristic from a set of low level heuristics. Experimental results are compared within themselves and solutions of other techniques proposed in literature. Experiments show hyper-heuristic strategies for the management of hill climbers give better solutions in MAs for solving examination timetabling problems.

Benzer Tezler

  1. Bütünleşik üretim ve dağıtım çizelgeleme problemleri için çözüm yaklaşımları

    Solution approaches for integrated production and distribution scheduling problems

    ECE ÇETİN YAĞMUR

    Doktora

    Türkçe

    Türkçe

    2021

    Endüstri ve Endüstri MühendisliğiKonya Teknik Üniversitesi

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

    PROF. SAADETTİN ERHAN KESEN

  2. Sürdürülebilir kent parkları için yönetim stratejileri

    Management strategies for sustainable urban parks

    HİLAL ÖZDEMİR ŞAHİN

    Doktora

    Türkçe

    Türkçe

    2024

    Peyzaj Mimarlığıİstanbul Teknik Üniversitesi

    Peyzaj Mimarlığı Ana Bilim Dalı

    PROF. DR. HAYRİYE EŞBAH TUNÇAY

  3. Bulanık çok modlu kaynak kısıtlı proje çizelgeleme problemlerinin çözümü için matematiksel bir model

    A mathematical model for the solution of the fuzzy multi mode resource-constrained project scheduling problems

    ÖMER ATLI

    Doktora

    Türkçe

    Türkçe

    2012

    Endüstri ve Endüstri MühendisliğiHava Harp Okulu Komutanlığı

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

    PROF. DR. CENGİZ KAHRAMAN

  4. Sivil toplum kuruluşlarında stratejik yönetim süreci ve sivil toplum kuruluşlarında stratejik yönetim uygulamalarının incelenmesine yönelik bir alan araştırması

    Strategic management in non governmental organizations and a survey on the application of strategic management in non governmental organizations

    BAVER ALYAKUT

    Yüksek Lisans

    Türkçe

    Türkçe

    2007

    Kamu Yönetimiİstanbul Üniversitesi

    Kamu Yönetimi Ana Bilim Dalı

    DOÇ.DR. ESRA NEMLİ ÇALIŞKAN

  5. Yerel toplulukların afet yönetimine katılım süreci: Vatandaş bilimi yaklaşımıyla bir inceleme

    The process of participation of local communities in disaster management: A study with a citizen science approach

    TUĞÇE UNGAN TÜRKARSLAN

    Yüksek Lisans

    Türkçe

    Türkçe

    2024

    Şehircilik ve Bölge PlanlamaMimar Sinan Güzel Sanatlar Üniversitesi

    Şehir ve Bölge Planlama Ana Bilim Dalı

    DOÇ. DR. KEVSER İSMET ÜSTÜNDAĞ