×

zbMATH — the first resource for mathematics

A cooperative hyper-heuristic search framework. (English) Zbl 1198.90203
Summary: 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 strengths of one low level heuristic to compensate for the weaknesses of another. We propose an agent-based cooperative hyper-heuristic framework composed of a population of heuristic agents and a cooperative hyper-heuristic agent. The heuristic agents perform a local search through the same solution space starting from the same or different initial solution, and using different low level heuristics. The heuristic agents cooperate synchronously or asynchronously through the cooperative hyper-heuristic agent by exchanging the solutions of the low level heuristics. The cooperative hyper-heuristic agent makes use of a pool of the solutions of the low level heuristics for the overall selection of the low level heuristics and the exchange of solutions. Computational experiments carried out on a set of permutation flow shop benchmark instances illustrated the superior performance of the cooperative hyper-heuristic framework over sequential hyper-heuristics. Also, the comparative study of synchronous and asynchronous cooperative hyper-heuristics showed that asynchronous cooperative hyper-heuristics outperformed the synchronous ones.

MSC:
90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
68T42 Agent technology and artificial intelligence
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Software:
Hyperheuristics
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alba, E.: Parallel Meta-heuristics: A New Class of Algorithms. Wiley, New York (2005) · Zbl 1094.90052
[2] Aydin, M.E.: Meta-heuristic agent teams for job shop scheduling problems. In: Lecture Notes in Computer Science, vol. 4659, pp. 185–194. Springer, Berlin (2007)
[3] Ayob, M., Kendall, G.A.: A Monte Carlo hyper-heuristic to optimise component placement sequencing for multi-head placement machine. In: Proceedings of the International Conference on Intelligent Technologies, Chiang Mai, Thailand, pp. 132–141 (2003)
[4] Bai, R., Burke, E.K., Kendall, G.: Heuristic, meta-heuristic and hyper-heuristic approaches for fresh produce inventory control and shelf space allocation. J. Oper. Res. Soc. 59(10), 187–197 (2008) · Zbl 1155.90304 · doi:10.1057/palgrave.jors.2602463
[5] Blum, C., Roli, A.: Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Comput. Surv. 35(3), 268–308 (2003) · doi:10.1145/937503.937505
[6] Burke, E.K., Hart, E., Kendall, G., Newall, J., Ross, P., Schulenburg, S.: Hyper-heuristics: an emerging direction in modern search technology. In: Glover, F., Kochenberger, G. (eds.) Handbook of Meta-heuristics, pp. 457–474. Kluwer Academic, Dordrecht (2003a) · Zbl 1102.90377
[7] Burke, E.K., Kendall, G., Soubeiga, E.: A tabu search hyper-heuristic for timetabling and rostering. J. Heuristic 9(6), 451–470 (2003b) · doi:10.1023/B:HEUR.0000012446.94732.b6
[8] Burke, E.K., Kendall, G., Landa-Silva, D., O’Brien, R., Soubeiga, E.: An ant algorithm hyper-heuristic for the project presentation scheduling problem. In: Proceedings of the IEEE Congress on Evolutionary Computation, Edinburgh, Scotland, pp. 2263–2270 (2005)
[9] Burke, E.K., Petrovic, S., Qu, R.: Case based heuristic selection for timetabling problems. J. Sched. 115–132 (2006) · Zbl 1154.90423
[10] Burke, E.K., McCollum, B., Meisels, A., Petrovic, S., Qu, R.: A graph-based hyper-heuristic for educational timetabling problems. Eur. J. Oper. Res. 176(1), 177–192 (2007) · Zbl 1137.90602 · doi:10.1016/j.ejor.2005.08.012
[11] Burke, E.K., Hyde, M., Kendall, G., Ochoa, G., Özcan, E., Qu, R.: A survey of hyper-heuristics. School of Computer Science, University of Nottingham, Computer Science Technical Report No. NOTTCS-TR-SUB-0906241418-2747 (2009)
[12] Cavalcante, C.C.B., Cavalcante, V.C., Ribeiro, C.C., de Souza, C.C.: Parallel cooperative approaches for the labor constrained scheduling problem. In: Ribeiro, C.C., Hansen, P. (eds.) Essays and Surveys in Meta-heuristics, pp. 201–225. Kluwer Academic, Dordrecht (2001) · Zbl 1006.90041
[13] Clearwater, S.H., Huberman, B.A., Hogg, T.: Cooperative problem solving. In: Huberman, B. (ed.) Computation: The Micro and the Macro View, pp. 33–70 (1992)
[14] Cowling, P., Chakhlevitch, K.: Hyperheuristics for managing a large collection of low level heuristics to schedule personnel. In: Proceedings of the IEEE Congress on Evolutionary Computation, pp. 1214–1221 (2003)
[15] Cowling, P., Kendall, G., Han, L.: An investigation of a hyper-heuristic genetic algorithm applied to a trainer scheduling problem. In: Proceedings of the IEEE Congress on Evolutionary Computation, Hawaii, pp. 1185–1190 (2002)
[16] Crainic, T.G., Gendreau, M.: Cooperative parallel tabu search for capacitated network design. J. Heuristics 8(6), 601–627 (2002) · Zbl 02003758 · doi:10.1023/A:1020325926188
[17] Crainic, T.G., Toulouse, M.: Parallel strategies for meta-heuristics. In: Glover, F., Kochenberger, G. (eds.) Handbook in Meta-heuristics, pp. 475–513. Kluwer Academic, Dordrecht (2003) · Zbl 1053.90138
[18] Crainic, T.G., Toulouse, M.: Explicit and emergent cooperation schemes for search algorithms. In: Learning and Intelligent Optimization (LION II) Conference. Lecture Notes in Computer Science, vol. 5313, pp. 95–109. Springer, Berlin (2008)
[19] Crainic, T.G., Toulouse, M., Gendreau, M.: Parallel asynchronous tabu search for multi-commodity location allocation with balancing requirements. Ann. Oper. Res. 63, 277–299 (1995a) · Zbl 0851.90033 · doi:10.1007/BF02125458
[20] Crainic, T.G., Toulouse, M., Gendreau, M.: Synchronous tabu search parallelization strategies for multi-commodity location allocation with balancing requirements. OR Spectrum 17(2–3), 113–123 (1995b) · Zbl 0843.90067
[21] Crainic, T.G., Toulouse, M., Gendreau, M.: Towards a taxonomy of parallel tabu search algorithms. INFORMS J. Comput. 9(1), 61–72 (1997) · Zbl 0891.90094 · doi:10.1287/ijoc.9.1.61
[22] Dowsland, K.A., Soubeiga, E., Burke, E.K.: A simulated annealing hyper-heuristic for determining shipper sizes. Eur. J. Oper. Res. 179(3), 759–774 (2007) · Zbl 1127.90007 · doi:10.1016/j.ejor.2005.03.058
[23] Ferber, J.: Multi-agent Systems: An Introduction to Distributed Artificial Intelligence. Addison-Wesley, Reading (1999)
[24] Fisher, H., Thompson, G.L.: Probabilistic learning combinations of local job shop scheduling rules. In: Muth, J.F., Thompson, G.L. (eds.) Industrial Scheduling, pp. 225–251. Prentice Hall, Englewood Cliffs (1963)
[25] Gaw, A., Rattadilok, P., Kwan, R.S.K.: Distributed choice function hyper-heuristics for timetabling and scheduling. In: Proceedings of the 5th International Conference on the Practice and Theory of Automated Timetabling, pp. 495–498 (2004)
[26] Hogg, T., Williams, C.P.: Solving the really hard problems with cooperative search. In: Proceedings of AAAI, pp. 213–235 (1993)
[27] James, T., Rego, C., Glover, F.: A cooperative parallel tabu search algorithm for the quadratic assignment problem. Eur. J. Oper. Res. 195(3), 810–826 (2009) · Zbl 1156.90400 · doi:10.1016/j.ejor.2007.06.061
[28] Kendall, G., Mohamad, M.: Channel assignment in cellular communication using a great deluge hyper-heuristic. In: Proceedings of the 12th IEEE International Conference on Networks, Singapore, pp. 769–773 (2004)
[29] Landa-Silva, D., Obit, E.J.: Great deluge with nonlinear decay rate for solving course timetabling problems. In: Proceedings of the IEEE Conference on Intelligent Systems, pp. 8.11–8.18 (2008)
[30] Le Bouthillier, A., Crainic, T.G.: A cooperative meta-heuristic for the vehicle routing problem with time windows. Comput. Oper. Res. 32, 1685–1708 (2005) · Zbl 1074.90006 · doi:10.1016/j.cor.2003.11.023
[31] Montgomery, D.C.: Design and Analysis of Experiments. Wiley, New York (2000)
[32] Nawaz, M., Enscore, E.E., Ham, I.: A heuristic algorithm for the m machine, n job flow shop sequencing problem. Omega 11, 91–95 (1983) · doi:10.1016/0305-0483(83)90088-9
[33] Nareyek, A.: Choosing search heuristics by non-stationary reinforcement learning. In: Resende, M.G.C., de Sousa, J.P. (eds.) Meta-heuristics: Computer Decision-Making, pp. 523–544. Kluwer Academic, Dordrecht (2003)
[34] OR: http://mscmga.ms.ic.ac.uk/jeb/orlib/flowshopinfo.html . Accessed January 2008
[35] Ouelhadj, D., Petrovic, S.: A cooperative distributed hyper-heuristic framework for scheduling. In: Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics, Singapore, pp. 1232–1238 (2008)
[36] Ouelhadj, D., Petrovic, S.: Asynchronous cooperative hyper-heuristic search. In: Proceedings of the International Conference on Artificial Intelligence, Las Vegas, pp. 78–84 (2009) · Zbl 1198.90203
[37] Özcan, E., Bilgin, B., Korkmaz, E.E.: A comprehensive analysis of hyper-heuristics. Intell. Data Anal. 12(1), 3–23 (2008)
[38] Pinedo, M.: Scheduling: Theory, Algorithms and Systems. Prentice Hall, Englewood Cliffs (1995) · Zbl 1145.90393
[39] Ross, P.: Hyper-heuristics. In: Burke, E.K., Kendall, G. (eds.) Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques, pp. 529–556. Springer, Berlin (2005)
[40] Ross, P., Schulenburg, S., Marin Blazquez, J.G., Hart, E.: Hyper-heuristics: learning to combine simple heuristics in bin-packing problems. In: Proceeding of the Genetic and Evolutionary Computation Conference, New York, USA, pp. 942–948 (2002)
[41] Ruiz, R., Maroto, C.: A comprehensive review and evaluation of permutation flow shop heuristics. Eur. J. Oper. Res. 165(2), 479–494 (2005) · Zbl 1066.90038 · doi:10.1016/j.ejor.2004.04.017
[42] Soubeiga, E.: Development and application of hyper-heuristics to personnel scheduling. Ph.D. Thesis, University of Nottingham, UK (2003)
[43] Taillard, E.D.: Benchmarks for basic scheduling problems. Eur. J. Oper. Res. 64, 278–285 (1993) · Zbl 0769.90052 · doi:10.1016/0377-2217(93)90182-M
[44] Taillard, E.D.: Summary of best known lower and upper bounds of Taillard’s instances. http://ina.eivd.ch/collaborateurs/etd . Accessed January 2008
[45] Talbi, E., Bachelet, V.: COSEARCH: A parallel cooperative metaheuristic. J. Math. Model. Algorithms 5, 5–22 (2006) · Zbl 1099.68742 · doi:10.1007/s10852-005-9029-7
[46] Toulouse, M., Crainic, T.G., Sanso, S.: An experimental study of the systemic behavior of cooperative search algorithms. In: Voß, S., Martello, S., Osman, I., Roucairol, C. (eds.) Meta-heuristics: Advances and Trends in Local Search Paradigms for Optimization, pp. 373–392. Kluwer Academic, Dordrecht (1999) · Zbl 0970.90084
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.