A Pheromone-Based Look-Ahead Hyper-heuristic for Time-tabling Problems
Edmund Burke, Moshe Dror, Graham Kendall, Ross O’Brien, David Redrup, Eric Soubeiga
{ekb, mxd, gxk, rob, exs}@cs.nott.ac.uk
Automated Scheduling, optimisAtion and Planning (ASAP) Research Group, School of Computer Science and information Technology, University of Nottingham, Jubilee Campus, Wollaton Road NG8 1BB, England.
Key words:Hyper-heuristics, Look-ahead, Nurse-Rostering, Examination Time-tabling
Hyper-heuristics have been defined to be heuristics which choose heuristics [3]. One of the main goals of some recent hyper-heuristic research is to develop a framework that has little knowledge of the domain of the problem being solved, or any domain knowledge of the (low-level) heuristics it must choose between. Its input is restricted to the evaluation of the current solution being worked upon, or any non-domain-knowledge available, such as the amount of CPU time a low-level heuristic requires to implement.
This is motivated by the goal of attempting to build systems that can operate at a more general level than current systems (many of which are very problem specific). More general systems would of course be cheaper to implement. Since, as a rule, less domain knowledge leads to poorer solutions, the continuing research into hyper-heuristics strives to develop the technology which would (at least in part) lessen the effect of this rule.
The approach which will be explored in this paper is to provide some form of look-ahead in hyper-heuristics, by examining solutions several low-level-heuristic moves ahead (where a move represents the application of a low-level-heuristic) before deciding which low-level heuristic to select (i.e. which low-level heuristic to accept) for use on the current solution. While potentially useful, the computational resources required to look-ahead one move would be increased significantly, and would continue to increase significantly with each further level of look-ahead. It should be noted that the Greedy Hyper-heuristic referred to in [7] is a one-level look-ahead hyper-heuristic.
In our paper, we propose to make use of the pheromone concept employed in the Ant Colony Optimisation (ACO) technique (described in [10]), explored in [2], and used in [13, 14]) to minimise the computational workload generated by the use of look-ahead in a hyper-heuristic. We will also demonstrate the techniques produced upon two timetabling problems: the Examination Time-tabling Problem (i.e. optimising a schedule of university examinations) (e.g. [4, 5, 6, 9, 12]), and the Nurse Rostering Problem (i.e. optimising a timetable of nurse’s work-shifts in a hospital) (e.g. [1, 8, 11]).
Dorigo’s ACO technique made use of pheromone to quantify the quality of routes explored by the ants in the colony; as ants traversed a route they would lay down an amount of pheromone corresponding to its quality, which another ant would be able to detect. A stronger concentration of pheromone corresponded to a better route which would be traversed more often, thereby accumulating more pheromone, while the pheromone quantities on routes of poorer quality would decay, reducing their usage. Good routes would therefore quickly become dominant. To analogise this in the context of this paper, routes are low-level heuristics, and the ants’ exploration and evaluation of routes are the hyper-heuristic.
The low-level heuristics implemented will be simple variations on the idea of adding, removing or swapping events in the schedules of the two problems, and the data sets themselves will be standard benchmarks of the problem type.
The basis of the hyper-heuristic algorithm we will be demonstrating runs as follows:
Initially, all low-level heuristics are assigned a pheromone value of 0. At each decision point the hyper-heuristic performs a look-ahead, evaluating the potential solutions of all the low-level heuristics, and ranks the low-level heuristics according to the solution quality that they produce.
These evaluations are then used to scale the low-level heuristics between two end-point values, one of which is positive, the other negative. The positive end-point is assigned to the low-level heuristic whose performance produced the most improvement, and the negative end-point is assigned to the low-level heuristic whose performance produced the least improvement.
The values produced by this scaling process are then added to the corresponding low-level heuristic’s accumulation of pheromone. In this way, low-level heuristics which perform well have a greater accumulation of pheromone than low-level heuristics which perform less well. At each decision point, the low-level heuristic which produced the greatest improvement (and was therefore assigned the positive end-point in the scaling range, and accumulated the most pheromone at this decision point), is selected and applied to the current solution, and the process is repeated: look-ahead, evaluation, scale and select.
If at any decision point a low-level heuristic has a negative accumulation of pheromone, as a result of its performance being (initially or continually) scaled to a sub-zero position on the scale, the low-level heuristic is “frozen”. It is then removed from the set of heuristics examined in the look-ahead process. Computational resources are no longer allocated to the frozen low-level heuristic, and it is excluded from further evaluations and scaling.
The resulting algorithm is one that greedily accepts the best move at each decision point, only considering low-level heuristics that have continued to perform comparatively well over time, until the last remaining non-frozen low-level heuristic can no longer produce an improvement in the solution. Low-level heuristics are then gradually reintroduced (“thawed”) on the basis of how successful they have been, and this “freezing”/”thawing” process is repeated until a local optima has been found – i.e. none of the heuristics produces an improvement, and a move to a new neighbourhood is required.
Initially we intend to use the following values as end-points: +10 for the positive end-point, -5 for the negative end-point. Assuming an even distribution, one third of all low-level heuristics would be frozen in the first decision iteration and one third would be effectively immune from freezing during the second decision iteration. We intend to experiment with a variety of positive and negative end-points, and also initial pheromone levels, during our investigation.
We also intend to experiment with alternative methods of thawing out low-level heuristics. One possibility is to simply reintroduce one low-level heuristic per decision iteration until one of the currently available selection produces an improvement in the current solution. A second possibility is to allow negative pheromone quantities to decay over time (as is done in ordinary ant colony algorithms), whereupon the low-level heuristic is reintroduced for evaluation and scaling as soon as its pheromone accumulation is no longer negative.
REFERENCES
1.Aickelin & Dowsland, “Exploiting problem structure in a genetic algorithm approach to a nurse rostering problem, Journal of Scheduling vol. 3, pp. 139-153 2000.
2.Bonabeau, Dorigo & Theraulaz, “Swarm Intelligence: From Natural to Artificial Systems”, Oxford University Press 1999.
3.Burke, Hart, Kendall, Newall, Ross & Schulenburg, “Hyper-Heuristics: An Emerging Direction in Modern Search Technology”. In F. Glover and G.A. Kochenberger, editors. Handbook of Metaheuristics, pp. 457-474. Kluwer Academic Publishers, 2003.
4.Burke & Newall, “A Multi-Stage Evolutionary Algorithm for the Timetabling Problem”, IEEE Transactions on Evolutionary Computing, vol. 61 pp. 63-74, 1999.
5.Burke & Newall, “A New Adaptive Heuristic Framework for Examination Timetabling Problems”, to appear in Annals of Operational Research.
6.Burke & Petrovic, “Recent Research directions in Automated Timetabling”, European Journal of Operational Research vol. 140 no2, pp. 266-280, 2002.
7.Cowling, Kendall & Soubeiga. A hyperheuristic approach for scheduling a sales summit. Selected Papers of the Third International Conference on the Practice and Theory of Automated Timetabling, PATAT 2000, Lecture Notes in Computer Science, pp. 176-190, Konstanz, Germany, August 2000, Springer.
8.Cowling, Kendall & Soubeiga. Hyperheuristics: A robust optimisation method applied to nurse scheduling. “Parallel Problem Solving from Nature VII”, PPSN 2002, Lecture Notes in Computer Science, pp. 851-860, Springer-Verlag.
9.Di Gaspero & Schaerf, “Tabu Search Techniques for Examination Timetabling”, Selected Papers of the 3rd International Conference on the Practice and Theory of Automated Timetabling. Lecture Notes in Computer Science vol. 2079, pp. 104-117 Springer-Verlag
10.Dorigo, Maniezzo & Colorni, “The Ant System: Optimization by a colony of cooperating agents”, IEEE Transactions on Systems, Man and Cybernetic-Part B, Vol. 26, No.1, 1996, pp. 1-13.
11.Dowsland, “Nurse Scheduling with Tabu Search and Strategic Oscillation”, European Journal of Operational Research vol. 106 pp. 393-407, 1998.
12.Erben, “A Grouping Genetic Algorithm for Graph Colouring and Exam Timetabling”, Selected Papers of the 3rd International Conference on the Practice and Theory of Automated Timetabling. Lecture Notes in Computer Science, vol. 2079, pp. 132-156 Springer-Verlag
13.Pimont & Solmon, “A Generic Ant Algorithm for Solving Constraint Satisfaction Problems”, Abstract Proceedings of ANTS’2000 from Ant Colonies to Artificial Ants: Second International Workshop on Ant Algorithms pp. 100-108, 2000.
14.Socha, Knowles & Sampels, “A MAX-MIN Ant System for the University Course Timetabling Problem”, Proceedings from ANTS 2002, the Third International Workshop on Ant Algorithms, pp. 1-13, 2002.