ABSTRACT
In this paper, we propose an agent-based multi-level search framework for the asynchronous cooperation of hyper-heuristics. This framework contains a population of different hyper-heuristic agents and a coordinator agent. Each hyper-heuristic agent operates on the same set of low level heuristics, while the coordinator agent operates on top of all the hyper-heuristic agents. Starting from the same initial solution, each hyper-heuristic agent performs a search over the space generated by the low level heuristics. The hyper-heuristic agents cooperate asynchronously through the coordinator agent by exchanging their elite solutions. The coordinator agent maintains a pool of elite solutions and manages the communication between the hyper-heuristics agents.
Preliminary computational experiments have been carried out on a set of permutation flow shop benchmark instances. The results illustrated the superior performance of the multi-level framework for asynchronous cooperation of hyper-heuristics.
- Alba, E. Parallel meta-heuristics: a new class of algorithms. John Wiley & Sons Publishers, 2005. Google ScholarDigital Library
- Burke, E., Hart, E., Kendall, G., Newall, J., Ross, P., and Schulenburg, S. Hyper-heuristics: an emerging direction in modern search technology. In Handbook of Meta-heuristics, F. Glover (ed.), Kluwer, 2003, 457--474.Google Scholar
- Cowling, P. and Chakhlevitch, K. Hyper-heuristics for managing a large collection of low level heuristics to schedule personnel. In Proceedings of the 2003 Congress on Evolutionary Computation, 2003, 1214--1221.Google Scholar
- Crainic, T. G. and Toulouse, M. Parallel strategies for meta-heuristics. In Handbook in Meta-heuristics, F. Glover, G. Kochenberger (eds.), Kluwer Academic Publishers, Norwell, MA, 2003, 475--513.Google Scholar
- Ferber, J. Multi-agent systems: An introduction to Distributed Artificial Intelligence. Addison-Wesley, London, 1999. Google ScholarDigital Library
- Kendall, G. and Mohamad, M. Channel assignment in cellular communication using a great deluge hyper-heuristic. In Proceedings of the 12th IEEE International Conference on Networks, Singapore, 2004, 769--773.Google ScholarCross Ref
- Ozcan, E., Bilgin, B., and Korkmaz, E. E. A comprehensive analysis of hyper-heuristics, Intelligent Data Analysis, 12:1 (2008), 3--23. Google ScholarDigital Library
- Ouelhadj, D. and Petrovic, S. A cooperative distributed hyper-heuristic framework for scheduling. In Proceedings of the IEEE International Conference on Man, Cybernetics, and Systems, Singapore, 1232--1238, 2008.Google ScholarCross Ref
- Pinedo, M. Scheduling: Theory, Algorithms and Systems. Prentice Hall, 1995. Google ScholarDigital Library
- Soubeiga, E. Development and application of hyper-heuristics to personnel scheduling. Ph.D. Thesis, University of Nottingham, UK, 2003.Google Scholar
- Taillard, E. D. Benchmarks for basic scheduling problems. European Journal of Operational Research, 64 (1993), 278--285.Google ScholarCross Ref
Index Terms
- A multi-level search framework for asynchronous cooperation of multiple hyper-heuristics
Recommendations
A cooperative hyper-heuristic search framework
In this paper, we aim to investigate the role of cooperation between low level heuristics within a hyper-heuristic framework. Since different low level heuristics have different strengths and weaknesses, we believe that cooperation can allow the ...
A comparative study of hyper-heuristics for solving the school timetabling problem
SAICSIT '13: Proceedings of the South African Institute for Computer Scientists and Information Technologists ConferenceHyper-heuristics have proven to be an effective means of obtaining generalized solutions to optimization problems. One such domain in which they have been a success is educational timetabling. However, all the research in this area has focused on ...
Selection Hyper-Heuristic Using a Portfolio of Derivative Heuristics
GECCO Companion '15: Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary ComputationGenerally, we distinguish between two classes of hyper-heuristic approaches, heuristic selection and heuristic generation. The former one works with existing heuristics and tries to find their optimal order for solving the instance. The later approach ...
Comments