Memes, Self-generation and Nurse Rostering
This paper presents an empirical study on memetic algorithms in two parts. In the first part, the details of the memetic algorithm experiments with a set of well known benchmark functions are described. In the second part, a heuristic template is introduc
- PDF / 530,957 Bytes
- 20 Pages / 430 x 660 pts Page_size
- 8 Downloads / 172 Views
bstract. This paper presents an empirical study on memetic algorithms in two parts. In the first part, the details of the memetic algorithm experiments with a set of well known benchmark functions are described. In the second part, a heuristic template is introduced for solving timetabling problems. Two adaptive heuristics that utilize a set of constraint-based hill climbers in a co-operative manner are designed based on this template. A hyper-heuristic is a mechanism used for managing a set of low-level heuristics. At each step, an appropriate heuristic is chosen and applied to a candidate solution. Both adaptive heuristics can be considered as hyper-heuristics. Memetic algorithms employing each hyper-heuristic separately as a single hill climber are experimented on a set of randomly generated nurse rostering problem instances. Moreover, the standard genetic algorithm and two self-generating multimeme memetic algorithms are compared to the proposed memetic algorithms and a previous study.
1
Introduction
Genetic Algorithms (GAs), as presented by J. Holland in [28], are very promising for tackling complex problems [24]. There are some shortcomings of generic genetic algorithms, such as premature convergence. The effectiveness of the use of appropriate operators and hybrid approaches is underlined by many researchers to overcome such difficulties. Memetic Algorithms (MAs) embody a class of algorithms that combine genetic algorithms and hill climbing methods [15, 38, 45, 46]. A meme represents a hill climbing method to be used within an MA as the local refinement component. Ning et al. [39] concluded from their experiments that the meme choice in an MA influences the performance significantly. Krasnogor [31] extended his previous studies and suggested a self-generating multimeme MA for solving problems in the existence of multiple choices for the operators. Each meme encodes an operator and its parameters that a candidate solution will employ during the evolution. In this study, a meme denotes a hill climbing method and its related parameters. Each meme is co-evolved with each candidate solution. The evolutionary process offers a learning mechanism to fully utilize the provided hill climbers [32, 34]. In the first part of this study, the multimeme approach proposed by Krasnogor [33] is tested on a set of benchmark functions. The study aims to answer the following questions: E.K. Burke and H. Rudov´ a (Eds.): PATAT 2006, LNCS 3867, pp. 85–104, 2007. c Springer-Verlag Berlin Heidelberg 2007
¨ E. Ozcan
86
– Can the suggested learning mechanism discover useful hill climbers? – Does a set of hill climbers generate a synergy to obtain the optimal solution? In the second part of this study, MAs for solving a nurse rostering problem, ¨ ¨ introduced by Ozcan [41], are considered. Ozcan extended the study by Alkan ¨ and Ozcan [5], and suggested templates designing a set of operators, including a self-adjusting violation-directed and constraint-based heuristics, named as VDHC, within MAs for solving timetabling problems. A new heu
Data Loading...
