Agent Metaheuristics Framework

AMF (Agent Metaheuristics Framework) aims at analyzing existing algorithms, and facilitating the design of hybrid or new metaheuristics. It proposes an organizational model of metaheuristics that can be used to describe both population-based metaheuristics and trajectory methods. In this model, a metaheuristic is viewed as an organization composed of a set of roles which interact in order to find an optimal solution.

The organizational model of AMF uses the concepts of role, interaction and organization to describe metaheuristics. A role is an abstraction of a behavior or a status defined in an organization. It is associated to an objective to accomplish. In the organizational approach, the concept of role does not match to a particular entity or agent, it can be played by several agents and an agent can play several roles. An interaction links two roles in such a way that an action in the first role produces a reaction in the second. An organization is defined by a set of roles and their interactions associated to the satisfaction of a goal or the execution of a global task.

From these concepts, a metaheuristic is defined as an organization. The goal of this organization is to efficiently explore the search space in order to find high quality solutions in reduced amount of time. This exploration combines intensification and diversification tendencies. To guide the exploration and balance these two tendencies, structured information about the search space is used by subordinate procedures as heuristics. In addition, the strategies used to guide, intensify and diversify may be adapted according to the search experiences. Four roles stems from this definition: Intensifier, Diversifier, Guide and Strategist. The resulting metaheuristic organizational model is described in the figure below.

AMF organizational model of metaheuristics

Main related contributions

D. Meignan, J.-C. Créput and A. Koukam
“Coalition-based Metaheuristic: A Self-adaptive Metaheuristic Using Reinforcement Learning and Mimetism”
Journal of Heuristics, vol. 16, no. 6, pp. 859-879, 2010.
DOI: 10.1007/s10732-009-9121-7

(In French)
D. Meignan, J.-C. Créput and A. Koukam
“Un framework organisationnel et multi-agent pour la conception de métaheuristiques”
Revue d’Intelligence Artificielle, vol. 24, no. 6, pp. 787-816, 2010.
DOI: 10.3166/ria.24.787-816

(In French)
D. Meignan
“Une approche organisationnelle et multi-agent pour la modélisation et l’implantation de métaheuristiques, Application aux problèmes d’optimisation de réseaux de transports”
Université de Franche-Comté et Université de Technologie de Belfort-Montbéliard
 PDF, Also available at TEL