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ı
- Tez No: 371503
- Danışmanlar: YRD. DOÇ. DR. A. ŞİMA UYAR, YRD. DOÇ. DR. ENDER ÖZCAN
- 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: 2007
- Dil: İngilizce
- Üniversite: İstanbul Teknik Üniversitesi
- Enstitü: Bilişim Enstitüsü
- Ana Bilim Dalı: İleri Teknolojiler Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- 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
- 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
2021
Endüstri ve Endüstri MühendisliğiKonya Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. SAADETTİN ERHAN KESEN
- 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
2024
Peyzaj Mimarlığıİstanbul Teknik ÜniversitesiPeyzaj Mimarlığı Ana Bilim Dalı
PROF. DR. HAYRİYE EŞBAH TUNÇAY
- 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
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
- 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
2007
Kamu Yönetimiİstanbul ÜniversitesiKamu Yönetimi Ana Bilim Dalı
DOÇ.DR. ESRA NEMLİ ÇALIŞKAN
- 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
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Ğ