Abstract
We present a self-adaptive and distributed metaheuristic called Coalition-Based Metaheuristic (CBM). This method is based on the Agent Metaheuristic Framework (AMF) and hyper-heuristic approach. In CBM, several agents, grouped in a coalition, concurrently explore the search space of a given problem instance. Each agent modifies a solution with a set of operators. The selection of these operators is determined by heuristic rules dynamically adapted by individual and collective learning mechanisms. The intention of this study is to exploit AMF and hyper-heuristic approaches to conceive an efficient, flexible and modular metaheuristic. AMF provides a generic model of metaheuristic that encourages modularity, and hyper-heuristic approach gives some guidelines to design flexible search methods. The performance of CBM is assessed by computational experiments on the vehicle routing problem.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Aydin, M.E.: Metaheuristic agent teams for job shop scheduling problems. In: 3rd International Conference on Industrial Applications of Holonic and Multi-Agent Systems: Holonic and Multi-Agent Systems for Manufacturing, pp. 185–194 (2007)
Aydin, M.E., Fogarty, T.C.: Teams of autonomous agents for job-shop scheduling problems: an experimental study. J. Intell. Manuf. 15, 455–462 (2004)
Blum, C., Roli, A.: Metaheuristics in combinatorial optimization: overview and conceptual comparison. ACM Comput. Surv. 35(3), 268–308 (2003)
Burke, E., Hart, E., Kendall, G., Newall, J., Hart, E., Ross, P., Schulenburg, S.: Hyper-heuristics: an emerging direction in modern search technology. In: Handbook of Meta-Heuristics, pp. 457–474. Kluwer, Dordrecht (2003)
Burke, E.K., Hyde, M.R., Kendall, G.: Evolving bin packing heuristics with genetic programming. In: Runarsson, T.P., Beyer, H.G., Burke, E., Merelo-Guervos, J.J., Whitley, L.D., Yao, X. (eds.) Parallel Problem Solving from Nature—PPSN IX. Lecture Notes in Computer Science, vol. 4193, pp. 860–869. Springer, Berlin (2006)
Burke, E.K., Hyde, M., Kendall, G., Ochoa, G., Ozcan, E., Woodward, J.: A classification of hyper-heuristics approaches. Tech. Rep. Computer Science Technical Report No. NOTTCS-TR-SUB-0907061259-5808, School of Computer Science and Information Technology, University of Nottingham (2009)
Christofides, N., Mingozzi, A., Toth, P.: The vehicle routing problem. In: Combinatorial Optimization pp. 315–338. Wiley, New York (1979)
Cordeau, J.F., Laporte, G., Mercier, A.: A unified tabu search heuristic for vehicle routing problems with time windows. J. Oper. Res. Soc. 52, 928–936 (2001)
Cordeau, J.F., Gendreau, M., Hertz, A., Laporte, G., Sormany, J.S.: New heuristics for the vehicle routing problem. In: Logistics Systems: Design and Optimization, pp. 279–297. Springer, Berlin (2005)
Crainic, T., Toulouse, M.: Parallel strategies for meta-heuristics. In: State-of-the-Art Handbook in Metaheuristics, pp. 475–513. Kluwer, Dordrecht (2003)
Dantzig, G.B., Ramser, J.H.: The truck dispatching problem. Manag. Sci. 6(1), 80–91 (1959)
Dongarra, J.J.: Performance of various computers using standard linear equations software. Tech. Rep. CS-89-85, Computer Science Department, University of Tennessee and Computer Science and Mathematics Division, Oak Ridge National Laboratory (2006)
Dorigo, M., Stützle, T.: The ant colony optimization metaheuristic: algorithms, applications and advances. Tech. Rep. IRIDIA-2000-32, IRIDIA (2000)
Gruer, P., Hilaire, V., Koukam, A., Cetnarowicz, K.: A formal framework for multi-agent systems analysis and design. Expert Syst. Appl. 23(4), 349–355 (2002)
Hansen, P., Mladenović, N.: Variable neighborhood search. In: Handbook of Metaheuristics, pp. 145–184. Kluwer, Dordrecht (2003)
Hinterding, R., Michalewicz, Z., Eiben, A.E.: Adaptation in evolutionary computation: a survey. In: IEEE International Conference on Evolutionary Computation, pp. 65–69 (1997)
Horling, B., Lesser, V.: A survey of multi-agent organizational paradigms. Knowl. Eng. Rev. 19, 281–316 (2005)
Jedrzejowicz, P., Wierzbowska, I.: Jade-based a-team environment. In: 6th International Conference on Computational Science, pp. 28–31 (2006)
Kaelbling, L.P., Littman, M.L., Moore, A.W.: Reinforcement learning: a survey. J. Artif. Intell. Res. 4, 237–285 (1996)
Kennedy, J., Eberhart, R.C.: Particle swarm optimization. In: IEEE International Conference on Neural Networks pp. 1942–1948 (1995). http://www.engr.iupui.edu/~shi/Coference/psopap4.html
Lin, S.: Computer solutions of the traveling salesman problem. Bell Syst. Tech. J. 44, 2245–2269 (1965)
Lourenço, H.R., Martin, O.C., Stützle, T.: Iterated local search. In: Handbook of Metaheuristics, pp. 321–353. Kluwer, Dordrecht (2003)
Meignan, D., Créput, J.C., Koukam, A.: A coalition-based metaheuristic for the vehicle routing problem. In: IEEE Congress on Evolutionary Computation, pp. 1176–1182, (2008a)
Meignan, D., Créput, J.C., Koukam, A.: An organizational view of metaheuristics. In: Jennings, N.R., Rogers, A., Petcu, A., Ramchurn, S.D. (eds.) First International Workshop on Optimisation in Multi-Agent Systems, AAMAS’08, pp. 77–85 (2008b)
Mester, D., Bräysy, O.: Active guided evolution strategies for large scale vehicle routing problems with time windows. Comput. Oper. Res. 32, 1593–1314 (2005)
Mester, D., Bräysy, O.: Active-guided evolution strategies for large-scale capacitated vehicle routing problems. Comput. Oper. Res. 34(10), 2964–2975 (2007)
Milano, M., Roli, A.: Magma: a multiagent architecture for metaheuristics. IEEE Trans. Syst. Man Cybern., Part B 34(2), 925–941 (2004)
Oliver, I.M., Smith, D.J., Holland, J.R.C.: A study of permutation crossover operators on the traveling salesman problem. In: Grefenstette, J.J. (ed.) International Conference on Genetic Algorithms, pp. 224–230, (1987)
Osman, I.H.: Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Ann. Oper. Res. 41(4), 421–451 (1993)
Özcan, E., Bilgin, B., Korkmaz, E.E.: A comprehensive analysis of hyper-heuristics. Intell. Data Analysis 12(1), 3–23 (2008)
Parunak, H.V.D., Brueckner, S., Fleischer, M., Odell, J.: A design taxonomy of multi-agent interactions. Lect. Not. Comput. Sci. 2935(4), 123–137 (2003)
Prins, C.: A simple and effective evolutionary algorithm for the vehicle routing problem. Comput. Oper. Res. 31, 1985–2002 (2004)
Ropke, S., Pisinger, D.: An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Trans. Sci. 40, 421–438 (2006)
Sutton, R.S., Barto, A.G.: Reinforcement learning: Introduction. Tech. rep., Cognitive Science Research Group (1998)
Taillard, E.D., Gambardella, L.M., Gendreau, M., Potvin, J.Y.: Adaptive memory programming: A unified view of metaheuristics. Eur. J. Oper. Res. 135, 1–16 (2001)
Talbi, E.G., Bachelet, V.: Cosearch: a parallel co-evolutionary metaheuristic. In: Int. Workshop on Hybrid Metaheuritics, pp. 127–140, (2004)
Toth, P., Vigo, D.: The granular tabu search and its application to the vehicle routing problem. INFORMS J. Comput. 15, 333–348 (2003)
Voss, S.: Meta-heuristics: the state of the art. In: Local Search for Planning and Scheduling. LNCS, vol. 2148, pp. 1–23 (2001)
Wren, A., Holliday, A.: Computer scheduling of vehicles from one or more depots to a number of delivery points. Oper. Res. Q 23(3), 333–344 (1972)
Yamaguchi, T., Tanaka, Y., Yachida, M.: Speed up reinforcement learning between two agents with adaptive mimetism. In: IEEE International Conference on Intelligent Robots and Systems, vol. 2, pp. 594–600 (1997)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Meignan, D., Koukam, A. & Créput, JC. Coalition-based metaheuristic: a self-adaptive metaheuristic using reinforcement learning and mimetism. J Heuristics 16, 859–879 (2010). https://doi.org/10.1007/s10732-009-9121-7
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10732-009-9121-7