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

Abstract

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.

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.