A multi-level search framework for asynchronous cooperation of multiple hyper-heuristics

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.

REFERENCES

• 1: Enrique Alba, Parallel Metaheuristics: A New Class of Algorithms, Wiley-Interscience, 2005
• 2: 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.
• 3: 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.
• 4: 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.
• 5: Jacques Ferber, Multi-Agent Systems: An Introduction to Distributed Artificial Intelligence, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 6: 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.
• 7: Ender Özcan , Burak Bilgin , Emin Erkan Korkmaz, A comprehensive analysis of hyper-heuristics, Intelligent Data Analysis, v.12 n.1, p.3-23, January 2008
• 8: 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.
• 9: Michael L. Pinedo, Scheduling: Theory, Algorithms, and Systems, Springer Publishing Company, Incorporated, 2008
• 10: Soubeiga, E. Development and application of hyper-heuristics to personnel scheduling. Ph.D. Thesis, University of Nottingham, UK, 2003.
• 11: Taillard, E. D. Benchmarks for basic scheduling problems. European Journal of Operational Research, 64 (1993), 278--285.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence

General Terms:
Algorithms, Experimentation, Performance

Keywords:
cooperative search, hyper-heuristics, multi-agent systems, permutation flow shop scheduling