Keywords: Multi-agents, recherche coopérative, optimisation combinatoire, intensification, diversification, métaheuristique Multi-agent, cooperative search, combinatorial optimization, intensification, diversification, metaheuristics

State of the art

Combinatorial optimization problems (COPs) have been widely used in a number of application areas, such as transportation, production planning, design and data fitting, automatic control systems, signal processing, communications and networks, product and shape design, truss topology design, electronic circuit design, data analysis and modelling, statistics and financial engineering, etc. The resolution of these problems can be very complex because the number of candidate solutions can grow exponentially with the size of the problem. Heuristic and metaheuristic methods are often used to generate high quality solutions in reasonable computing time. Recent studies integrate other techniques to develop an intelligent optimization process. Multi-agent system is an efficient technique of artificial intelligence. Recently, due to their characteristics, multi-agent system has been applied to solve optimization problems. This chapter describes the necessary background for our contributions. In the first section, we make a review of the most popular heuristic and metaheuristic approaches. In the second section, we present the multi-agent system and we provide a review of multi-agent based optimization approaches.

A Multi-Agent based Optimization Method for combinatorial optimization problems

This chapter presents a new Multi-Agent based Optimization Method for Combinatorial Optimization Problems (MAOM-COP). A multi-agent system (MAS) is typically composed of a group of interacting agents where each agent has one or more basic skills. The agents can collectively find solutions to a difficult problem even if each agent alone can not solve it. These agents explore several optimization techniques like local search algorithms, crossover operators and perturbation techniques. The selection of each one of these techniques is made in an intelligent way based on reinforcement learning. MAOM-COP is evaluated on a number of classical combinatorial optimization problems.

I would like to express my special appreciation and thanks to my advisors: Professor Jin-Kao Hao and Professor Khaled Ghédira. You have been a tremendous mentor for me. I would like to thank you for encouraging my research and for allowing me to grow as a research scientist. Your advice on both research as well as on my career have been priceless. This thesis would not have been possible without your help, support and patience.

Furthermore, I would like to thank Doctor Inès Ben Jaafar for the useful comments, remarks and engagement through the learning process of this thesis.

Profuse thanks go to Professor Patrick Siarry (Université Paris-Est Créteil) and to Doctor Wided Lejouad Chaari (Université La Manouba) for their participation to my thesis committee. I am glad they accepted to be members of the jury of this thesis. I appreciate particularly the precise and efficient reviewing of the complete thesis they performed to improve this thesis.

I would like to extend my gratitude to Professor David Lesaint for honouring my jury by presiding it.

I thank also the LERIA Laboratory of the Université d'Angers for providing me the material, the means and the expertise. Besides, I would like to extend my gratitude to its staff who welcomed me nicely.

I would like to dedicate my thesis and to express my deepest appreciation to my mother and father for all the sacrifices that you've made on my behalf. Your prayer for me was what sustained me thus far.

List of Figures

General Introduction

Context of work

This thesis deals with combinatorial optimization problems (COP) and their resolution strategies. Heuristic methods, which have been used for COP, aim to produce high quality solutions in reasonable computing time for hard problems. Recently, research studies have integrated techniques of diversification, in order to escape bad quality local optima.

An example of these methods is memetic algorithm which is an hybrid algorithm combining local search and evolutionary algorithms. These hybrid approaches aim at moving the optimization process from one local optimum to another. However, they do not have an efficient way to know when activating the suitable techniques according to the search process. Therefore, we can assume that existing methods do not integrate an intelligent mechanism to control the resolution process.

These methods use the centralisation model to solve the combinatorial optimization problems. Other types of solution methods are based on distributed model. In fact, the decomposition of an entire system into smaller subsystems and optimizing them in a distributed way to reach the system level optimum is one of the emerging approaches to deal with the growing complexity encountered in hard optimization problems. The multi-agent system is one of these emerging approaches.

In this thesis, we present a new generic approach to solve the limitation of heuristics. The proposed approach can be considered as an hyper heuristic method because it uses the multi-agent system to select the appropriate operators of metaheuristic methods using learning techniques.

Objectives

The main objective is to develop a generic approach that makes the search strategy more intelligent and informative. For this purpose, we adopt some ideas from multi-agent systems. In a multi-agent system, the rational behavior of agents is very important to achieve the best possible local goal. The agents work collectively to achieve the best possible global or system objective. The proposed approach aims at solving hard combinatorial optimization problems. The result is a Multi-Agent based Optimization Method for Combinatorial Optimization Problems (MAOM-COP).

This method explores the multi-agent system as an intelligent tool to activate the search operator needed by the optimization process in a distributed environment.

The distributed search combines some distinguishing characteristics of several wellestablished metaheuristics including variable neighborhood search, tabu search, and evolutionary algorithms. The intelligent selection is made by learning techniques.

Contributions

The main contributions of this thesis are summarized as follows:

A Multi-Agent based Optimization Method for Combinatorial Optimization Problems:

We elaborate a multi-agent based and distributed method for Combinatorial Optimization Problems. MAOM-COP is composed of decision-maker agent, intensification agents and diversification agents. The crossover agents and the perturbation agent are designed for the purpose of diversification. The tabu search agents are responsible for intensification. With the help of a learning mechanism, MAOM-COP dynamically decides the most suitable agent to activate according to the state of search process.

Under the coordination of the decision-maker agent, the other agents fulfill dedicated search tasks of intensification and diversification. The performance of the proposed approach is assessed on the following classical combinatorial optimization problems: the Quadratic Assignment Problem (QAP), the Graph Coloring Problem (GCP), the Winner Determination Problem (WDP) and the Multidimensional Knapsack Problem (MKP). For each of these problems, we tested the proposed approach and we compared it with the current state of the art approaches using the corresponding benchmark instances.

The results showed that our MAOM-COP algorithms are very competitive in terms of solution quality with the current best performing algorithms from the literature. These contributions led to two papers describing the application of MAOM-COP to the Quadratic Assignment Problem (QAP) (Sghir & al., 2015a) and the Graph Coloring Problem (GCP) (Sghir & al., 2015b). Other applications of the proposed approach will be submitted.

A Recombination-Based Tabu Search Algorithm for the WDP:

We propose a dedicated tabu search algorithm (TSX_WDP) for the Winner Determination Problem (WDP) in combinatorial auctions. TSX_WDP integrates two complementary neighborhoods designed respectively for the purpose of intensification and diversification. To escape deep local optima, TSX_WDP employs a backbone-based recombination operator to generate new starting points for tabu search and to displace the search into unexplored promising regions. The recombination operator operates on elite solutions previously found which are recorded in a global archive. The performance of the proposed algorithm is assessed on a set of 500 well-known WDP benchmark instances. Comparisons with five state of the art algorithms demonstrated the effectiveness of our approach. The proposed algorithm was presented in [START_REF] Sghir | A Recombination-Based Tabu Search Algorithm for the Winner Determination Problem[END_REF].

Thesis plan:

This thesis is organized as follows:

Chapter 1 provides the necessary background for this work and the relevant literature review. In the first section of this chapter, we introduce the combinatorial optimization problems. Then, we review the most popular heuristic and metaheuristic approaches proposed in the literature for hard combinatorial optimization problems. In the second section, we present the multi-agent system and we provide a review of multi-agent based optimization approaches.

Chapter 2 presents the proposed approach, named a Multi-Agent based Optimization Method for Combinatorial Optimization Problems.

In the third chapter, we apply the proposed method to the quadratic assignment problem. We give an overview of current state of the art QAP approaches. We present the characteristic of each agent of the method. Then, we test it using the QAP benchmarks and we compare it with the best performing approaches from the literature.

The fourth chapter solves the graph coloring problem by exploring the proposed method. We start from an overview of the state of the art GCP approaches. We present the components of MAOM-GCP. Then, we show experimental results obtained by our algorithm for popular GCP instances, and we compare these results with those obtained by the current best-performing GCP algorithms from the literature.

In the fifth chapter, we propose the application of MAOM-COP to the winner determination problem. We introduce the problem and the state of the art research solving it. We describe the tasks of each agent composing this method to be adapted to the WDP. Experimental results of the proposed algorithm show that it can realize good quality results when they are compared with the best performing approaches for the WDP. Another elaborated algorithm is presented in the appendix of this thesis. This algorithm is named as a Recombination-Based Tabu Search Algorithm for the WDP (TSX_WDP). It includes several techniques of diversification which improve the tabu search.

In the sixth chapter, we study the multidimensional knapsack problem. We review the approaches solving this problem. We describe MAOM-MKP which is the application of the proposed approach to MKP. Then, we evaluate its performance by comparing it with the best approaches of the literature for this problem.

In the last chapter, we summarize our contributions in this thesis and we underline some possible future research topics.

Combinatorial optimization problems and heuristic methods

In this section, we define combinatorial optimization problems. Furthermore, we give a brief overview of popular heuristic and metaheuristic approaches for such problems.

Combinatorial optimization problems

A mathematical optimization problem uses a function which is either maximized or minimized relative to a given set of alternatives. This is called the objective function and the set of alternatives is called the feasible region (or constraint region). An optimization problem aims to find the best solution among the feasible solutions. [START_REF] Papadimitriou | Combinatorial Optimization : Algorithms and Complexity[END_REF] proposed the following definitions for an optimization problem and for an instance of an optimization problem:

-An optimization problem is a set I of instances of an optimization problem.

-An instance of an optimization problem is a pair (S, f ), where S is a set of feasible solutions, and f an objective function or mapping f : S → R 1 . Given a minimization problem, the objective is to find an optimal solution s ∈ S (also called global optimum) for which f (s) < f (s ′ ), ∀s ′ ∈ S.

The optimization problems can be divided into two categories: problems with continuous variables and problems with discrete variables, named combinatorial optimization problems. In the continuous problems, solutions are a set of real numbers. In the combinatorial optimization problems (COP), solutions are objects (e.g., integer, permutation, graph) from a finite or possibly countable infinite set.

Heuristic methods for combinatorial optimization problems

In this section, we present an overview of some heuristic and metaheuristic methods including greedy algorithms, neighborhood search algorithms, and evolutionary algorithms.

Greedy algorithms

Greedy algorithms generate feasible solutions from scratch. In each step, a value is assigned to a decision variable. The choice of this value depends on the decisions and their values made in the previous steps. This choice can influence the quality of final solution. We find different problems that have been solved with greedy heuristics, like GRASP solved time constrained vehicle scheduling problem [START_REF] Atkinson | A greedy randomized search heuristic for time-constrained vehicle scheduling and the incorporation of a learning strategy[END_REF], GRASP applied to quadratic assignment problem [START_REF] Fleurent | Improved constructive multistart strategies for the quadratic assignment problem using adaptive memory[END_REF], and the nearest neighbor heuristic for the travelling salesman problem [START_REF] Reinelt | The Traveling Salesman, Computational Solutions for TSP Applications[END_REF].

Local search algorithms

Local search corresponds to move from a solution to another one in its neighborhood according to some well-defined rules. A local search algorithm begins from an initial solution x 1 ∈ X. Then, at each step n, a new solution x 0 is generated in the neighborhood V (x n ) of the current solution x.

Formally, V (x) ⊆ X is called the neighborhood of x where x ∈ X. For instance, if X is a set of binary vectors and x ∈ X, a neighborhood V (x) of x can be defined as bit-flip mapping for these binary vectors. This bit-flip neighborhood can be presented as the set of all solutions x ∈ X realized from x by flipping a single coordinate from 0 to 1 or reversely.

Formally, the set of all the possible solutions generated with a single bit-flip move is given as:

V (x) = {x ′ ∈ X | x ⊕ bit -f lip(u), ∀u ∈ {1, ..., n}}
where ⊕ is used to denote the move operator which presents the transition from the current solution x to the new neighboring solution x 0 .

1.1.2.2.a Descent/ascent local search

Descent/ascent local search is the simplest form of local search (Algorithm 1.1). For a maximization problem, it is called ascent or hill climbing algorithm. In each iteration of this algorithm, a better solution is chosen among the neighbors of the current solution. For the next generation, the new solution is the new starting point. These operations are repeated until no better solution exists in the neighborhood. In the literature, there is two main types of descent algorithms, first improvement and best improvement. In the first improvement, the first better solution found in the neighborhood is selected. The best improvement explores the entire neighborhood, to find the best neighboring solution. Descent search can easily be trapped into local optima. Select a neighboring solution s ′ ∈ N (s best )

4: if f (s ′ ) < f (s best ) then 5: s best ← s ′ 6:
end if 7: end while 1.1.2.2.b Simulated Annealing (SA) [START_REF] Kirkpatrick | Optimization by simulated annealing[END_REF] proposed the simulated annealing algorithm (Algorithm 1.2). It is a randomized local search algorithm that has an explicit strategy to escape local minima. Iteratively, the current solution is modified by randomly selecting a move from the neighborhood. If this solution improves the current solution, it is directly accepted as a new current solution. Otherwise, it will be accepted, but with a certain probability based on the control parameters which are the temperature and the cost increase (for minimization). When the temperature is high and the cost increase is low, the move may be accepted with certain probability. According to predefined cooling schedule, the temperature is progressively decreased. When the temperature is adequately low, the method stops at a local optimum by allowing only improving moves. A great number of different simulated annealing algorithms have been proposed in the literature to solve optimization problems like the multidimensional knapsack problem [START_REF] Drexl | A simulated annealing approach to the multiconstraint zeroâone knapsack problem[END_REF], the graph coloring problem [START_REF] Lim | Meta-heuristics for robust graph coloring problem[END_REF] Select a random neighboring solution s ′ ∈ N (s best )

5: △f = f (s) -f (s ′ ) 6: if △f ≥ 0 or exp(△f /T (n)) > random[0, 1] then 7: s ← s ′ 8:
end if

n = n + 1 13: end while 1.1.2.2.c Tabu search (TS)
The tabu search algorithm (Algorithm 1.3) was proposed by Glover [START_REF] Glover | Future paths for integer programming and links to artificial intelligence[END_REF]. Tabu search (TS) is a neighborhood search method which employs flexible memory to avoid being trapped at local optimum. The visited solutions, which are maintained in this memory, are declared tabu to restrict the search space and avoid cyclic behavior. A short term or a long term memory can be used, in order to improve the exploration quality. When a tabu move can result in a solution better than any visited so far, this solution can be accepted. This is the aspiration criterion. In [START_REF] Taillard | Robust taboo search for the quadratic assignment problem[END_REF], Taillard et al. proposed the robust tabu search (Ro-TS) for the quadratic assignment problem. [START_REF] Carlton | Solving the Traveling Salesman Problem with Time Windows Using Tabu Search[END_REF] applied reactive TS to solve the travelling salesman problem. Hertz et al. [START_REF] Hertz | Using tabu search techniques for graph coloring[END_REF] The Variable Neighborhood Search algorithm (VNS) (Algorithm 1.4) was proposed by Mladenovic and Hansen ( Mladenovic & al., 2010). VNS is a local search algorithm which exploits the idea of neighborhood change. VNS is extended into many forms of algorithms like Variable Neighbor Descent, Reduced VNS, Basic VNS, Skewed VNS, etc. Different algorithms have been proposed using VNS like VNS for the graph coloring problem [START_REF] Avanthay | A Variable Neighborhood Search for Graph Coloring[END_REF], VNS for the multidimensional knapsack problem (Puchinger & Raidl, 2005), VNS methodology for the vertex separation problem on generic graphs [START_REF] Duarte | Variable Neighborhood Search for the Vertex Separation Problem[END_REF]

s ′ ← Random_solution(N k )) 7: s ′′ ← Local_search(s ′ ) 8: if f (s ′′ ) < f (s ′ )) then 9:
s ← s ′′ 10:

else 11: k ← k + 1 12: end if 13: if f (s ′′ ) < f (s best )) then 14: s best ← s ′′ 15:
end if

16:

until k = k max 17: until stopping condition is not reached

1.1.2.

2.e Iterated Local Search (ILS)

Iterated Local Search (ILS) algorithm (Algorithm 1.5) has been introduced by Baum [START_REF] Baum | Towards practical 'neural' computation for combinatorial optimization problems[END_REF]. Starting from a local optimum, ILS performs some perturbation moves to transform it to an intermediate solution. Then, the perturbed solution is used as an initial solution to apply local search procedure, in order to obtain a new local optimum.

If the perturbation is too weak, the search will often return to visited solutions. If the perturbation is too strong, ILS becomes a simple random restart algorithm. Consequently, the perturbation strategy should either be randomized or adaptive. ILS is applied to several optimization problems like the flow shop problem [START_REF] Stützle | Applying iterated local search to the permutation flow shop problem[END_REF], the quadratic assignment problem [START_REF] Misevicius | Iterated tabu search: An improvement to standard tabu search[END_REF], the graph coloring problem (Chiarandini & Stützl, 2002), the graph bipartitioning problem [START_REF] Martin | Combining simulated annealing with local search heuristics[END_REF] s ′ ← solution_P erturbation(s, history)

5:

s ′′ ← local_Search(s ′ ) 6: end while

Population based algorithms

Among population based algorithms, we present the genetic algorithm and the ant colony optimization algorithm.

1.1.2.3.a Genetic Algorithms (GA)

Genetic algorithm (Algorithm 1.6) was developed by Holland [START_REF] Holland | Adaption in natural and artificial systems[END_REF]. The genetic procedure is based on different operators such as mutation and recombination. The reproductive success is formulated with a fitness function.

The genetic algorithm performs the following basic process: a set of solutions, called population, are maintained. Some solutions are selected from this population to be recombined to form new solutions. The new solutions can be mutated to create other solutions. The population is updated with new solutions generated. The process is repeated until a given stop condition is satisfied.

We cite some examples of genetic algorithms solving the quadratic assignment problem [START_REF] Tate | A genetic approach to the quadratic assignment problem[END_REF][START_REF] Misevicius | An improved hybrid genetic algorithm: New results for the quadratic assignment problem[END_REF], the vehicle routing problem (Braysy, 2011), the multidimensional knapsack problem [START_REF] Chu | A genetic algorithm for the multidimensional knapsack problem[END_REF], etc.

Algorithm 1.6. Genetic algorithm 1: t = 0 2: P (0) ← initial_P opulation 3: evaluate_P opulation(P (0)) 4: while stopping condition not reached do 5:

P ′ ← Select_P arents(P (t)) P ′ ← Select_P arents(P (t)) (two or more parents are selected from the population)

7:

s 0 ← Recombine(P ′ ) (one or more offspring can be generated from the parents)

8:

s ← local_Search(s 0 ) (the offspring can be improved by local search) 9:

P (t + 1) ← U pDate_population(P (t), s) (population is evaluated and updated with the new solutions) 10:

(S * , f * ) ← U pDate_Best_solution(S * , f * , P ) (the best solution is retained)

11:

t = t + 1 12: end while 1.1.2.3.b Ant Colony Optimization (ACO)
Ant colony optimization (ACO) was proposed by [START_REF] Dorigo | Positive feedback as a search strategy[END_REF]. In each iteration, a number of artificial ants is used in a greedy way, to generate solutions. Then, each ant chooses the amount of pheromone to be included into the current partial solution. When a complete solution is generated, the procedure is repeated with updated pheromone levels, until reaching a stopping criterion. Many works have been developed using ACO like the graph coloring problem [START_REF] Dorigo | Positive feedback as a search strategy[END_REF], the job shop scheduling problem [START_REF] Colorni | Ant system for job-shop scheduling[END_REF], the vehicle routing problem [START_REF] Bell | Ant colony optimization techniques for the vehicle routing problem[END_REF] and the multidimensional knapsack problem [START_REF] Changdar | An Ant colony optimization approach for binary knapsack problem under fuzziness[END_REF].

Hybridizing metaheuristics with (meta-) heuristics

Recently, researchers have combined metaheuristics to solve optimization problems. Generally, it consists on merging local search methods and population based methods. Population based methods can determine the promising regions of the search space. Local search methods determine quickly the best solutions. One of the successful hybrid algorithms is memetic algorithm (Algorithm 1.7), which is proposed by Moscato [START_REF] Moscato | On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms[END_REF].

Multi-agent based optimization approaches

Multi-agent system (MAS) technology becomes a popular paradigm used for the conceptualization, design, analysis and implementation of many approaches and solutions. In this section, we present multi-agent systems, then, we focus on studies using this technique for optimization.

Multi-agent system

An agent is a physical or virtual entity that: [START_REF] Ferber | Multi-agent systems: an introduction to distributed artificial intelligence[END_REF] -can act in an environment; -can communicate with other agents; -is moved by a set of tendencies which can be an individual objective or a satisfaction function; -has its appropriate resources; -can perceive its environment with limit; -has skills and provides services; -can reproduce; -has behaviors to satisfy objectives using its resources and its skills based on its perceptions, its representations and its communications with other agents. A multi-agent system (MAS) is a system composed of agents which interact, most of the time, according to cooperation and competition modes. In fact, in a MAS, each agent has a partial view point to solve a problem because it has limited information about this problem. Each agent is only responsible for its knowledge, its actions and its communications with other agents. Nevertheless, it has no global view of the whole system. Therefore, a MAS is a distributed system where the tasks to be realized and the skills to make are distributed by agents. The agents interact in a MAS according to the following types of interaction including the cooperation to solve a common purpose, the coordination and the negotiation.

In a MAS, we distinguish three types of agents [START_REF] Ferber | Multi-agent systems: an introduction to distributed artificial intelligence[END_REF]:

-Cognitive agent: it has a capacity of reasoning and knowledge to execute its tasks and to manage the interactions with other agents. -Reactive agent: it does not have a representation of his environment, but it acts with a behavior of stimulus answer and it reacts in a present state of its environment. This type of agent does not consider the past and does not plan the future.

-Hybrid agent: it has reactive and cognitive components to improve its capacity of reasoning. Analogically with the human interactions in a social organization, in a MAS, agents have to communicate because a single agent is an isolated, deaf and mute individual. The MAS is applied to several domains like optimization and decision problems, modeling and simulation. Furthermore, it can be used in distributed applications such as management of industrial systems, control of the aerial traffic, telecommunication networks, e-commerce, robotics, image segmentation, etc.

We will present a review of multi-agent based optimization algorithms and their applications. These studies are divided into two types of frameworks based on agents functionality. Some frameworks use agents which explore the same search space, but with various strategies of resolution. They can be called as strategy based agents frameworks. In other frameworks, each agent handles a part of search space. It consists in decomposing the global problem to different sub-problems. This decomposition can concern the variables, the constraints and the objective functions. This category of frameworks can be called as sub-problems based agents frameworks.

Strategy based agents frameworks

In strategy based agents frameworks, agents are responsible for actions and behaviors. These agents explore learning or improving certain functionality. The asynchronous team (A-Team) (Talukdar & al., 1993(Talukdar & al., , 1996) ) is the first conceptual framework that uses autonomous and cooperated agents to solve optimization problems. A-Team is based on features from a number of systems like insect societies, cellular communities, genetic algorithms, simulated annealing, local search, and brainstorming. A-Team is composed of a set of interconnected memories to create a strongly cyclic network. Each memory, which saves solutions produced by each agent, is dedicated to one problem, in order to form a population. In this network, each agent is in a closed loop. All agents work in parallel way and no one of them waits for results from another agent. This cooperation between agents is called asynchronous cooperation.

These agents are divided into two types: construction agents which add solutions to population and destruction agents which delete solutions from population. Each agent defines three components: an operator or an algorithm that generates solutions, a selector that selects which solutions are maintained, and a scheduler which organizes behaviors (when solutions have to be selected and with what resources). The intelligence of the agents is realized by their selector and their schedulers. Their skills are resident in their operators. The A-Team has been applied to several optimization problems like travelling salesman [START_REF] De Souza | Asynchronous Organizations for Multi-Algorithm Problems[END_REF], control of electric networks [START_REF] Talukdar | A Multi-Agent Technique for Contingency Constrained Optimal Power Flows[END_REF][START_REF] Avila-Abascal | Cooperative Algorithms and Abductive Causal Networks for the Automatic Generation of Intelligent Substation Alarm Processors[END_REF], job-shop-scheduling [START_REF] Chen | Job-Shop-Scheduling by a Team of Asynchronous Agents[END_REF], trainscheduling [START_REF] Tsen | Solving Train Scheduling Problems Using A-Teams[END_REF], and steel and paper mill scheduling [START_REF] Rachlin | Forest View: A System For Integrated Scheduling In Complex Manufacturing Domains[END_REF][START_REF] Lee | Primary Production Scheduling at Steel making Industries[END_REF].

In [START_REF] Milano | MAGMA: a multiagent architecture for metaheuristics[END_REF] [START_REF] Je ¸drzejowicz | Jade-based A-team environment[END_REF] elaborated the JADE-A-Team (JABAT) which is based on the A-Team architecture. JA-BAT is composed of two types of Optimization agents (called OptiAgent) and Solu-tionManagers agents. Each OptiAgent implements improvement algorithms (simulated annealing, tabu search, genetic algorithm, local search heuristics). Solution-Managers agents have the common memory which contains solutions generated by OptiAgents. SolutionManagers agents are responsible for updating the common memory and sending individuals to OptiAgents. All agents act in parallel way. JA-BAT has no intelligence communication between agents.

In (Barboucha & Je ¸drzejowicz, 2007), Barbucha et al. applied the JABAT framework to the vehicle routing problem (VRP). They integrate four instances of OptiAgents which consist in four local improvement procedures: OA 2-Opt agent is an implementation of the 2-opt local search algorithm for VRP which operates on a single route, OA StringCross agent exchanges two strings (routes) of customers by crossing two edges of two different routes. OA 2-Lambda agent executes the local search algorithms based on λ-interchange local optimization algorithm. This agent solves only the instances in which the customers are uniformly arranged on the plane. OA 2-LambdaC agent explores the same algorithm of OA 2-Lambda agent, but it concentrates on instances in which the customers are clustered.

In addition, JABAT framework has been implemented for multi-mode resourceconstrained project scheduling problem with minimal and maximal time lags problem (MRCPSP-GPR)(Je ¸drzejowicz & Ratajczak-Ropel, 2013). They created five instances of OptiAgents whose two agents (optiLSAm and optiTSAe) explore two local search algorithms with different neighborhood structures, one agent called op-tiTSAe applies tabu Search algorithm, one agent named optiCA executes crossover algorithm, and one agent named optiPRA employs path relinking algorithm.

In [START_REF] Barbucha | Solving Instances of the Capacitated Vehicle Routing Problem Using Multi-agent Non-distributed and Distributed Environment[END_REF], JABAT is applied to the capacitated vehicle routing problem. In this work, they used four instances of OptiAgents which can be divided into two groups operating on one (intra-route) or two (inter-routes) routes and include: modified implementations of 3-opt procedure [START_REF] Lin | Computer solutions of the traveling salesman problem[END_REF] and λ-interchange local optimization method (Osman, 1993)(λ=2), and two dedicated local search methods, based on moving/exchanging selected nodes or edges between routes.

In [START_REF] Xu | A Multi-Agent Particle Swarm Optimization Framework with Applications[END_REF], Xu et al. proposed a multi-agent based particle swarm optimization (HMAS) for cluster analysis. In this framework, a group of agents forms a swarm and a group of swarms agents forms sub-populations. In these swarms, agents have the ability of self-organization, learning and detecting local environment.

The framework of [START_REF] Bae | Multi-agent based traffic simulation and integrated control of freeway corridors: Part 2 integrated control optimization[END_REF] uses the multi-agent system to simulate the traffic signal system. The agents are the driver agent and the vehicle agent. It is the vehicle agent that is responsible for optimization tasks by exploring the simulated annealing method.

The EMAS proposed by [START_REF] Hanna | Evolutionary Multi-Agent Systems: An Adaptive and Dynamic Approach to Optimization[END_REF]) explores the A-Team architecture using a group of strategy agents which execute genetic algorithms. In each iteration, all agents are activated and perform actions based on their genetic sequence, in order to product solutions. Then, the considered agents are evaluated according to the new solutions generated. The solutions provide a basis for increasing or decreasing an agent's fitness. The evaluation of agents is based on the average solution quality in a memory. The memory is made by saving new solution found by each agent. In fact, reproduction phase is applied only for selected parents based on their fitness and new agents are created. During the selection phase the weakest individuals (agents with low fitness value) are removed from the population. This approach was applied to the travelling salesman problem. [START_REF] Meignan | Coalition-based metaheuristic: a self-adaptive metaheuristic using reinforcement learning and mimetism[END_REF] proposed the Coalition-Based Metaheuristic (CBM). It is a framework that used the multi-agent paradigm to select between the intensification techniques and the diversification techniques according to the search state. Each technique is manipulated by an agent. All agents are guided by a decision process to choose the appropriate actions which are dynamically adapted during the search using reinforcement learning. These agents are always in coalition state because they are in competition to find the best solution. There is no communication between them. The proposed approach is applied to the vehicle routing problem.

The multi-agent approach presented in [START_REF] Guo | A Multi-agent Based Self-adaptive Genetic Algorithm for the Long-term Car Pooling Problem[END_REF] is composed of several agents which explore the genetic algorithm. The learning mechanism, which is built for each agent, guides the agents to choose the most appropriate genetic operators during each generation. The genetic operators are the crossover operators and the mutation operators. In fact, there is an operator pool that stores these operators to be selected. In this pool, the crossover operators and the mutation operators are saved in pairs. Each pair corresponds to one crossover operator and one mutation operator. At the beginning of each generation, two operators have the same intensification or diversification search tendency. After applying a decision making heuristic, one of these operators is selected for each agent. The decision making heuristic is performed to learn adaptively and concurrently the behavior of all agents, in order to predict the most suitable operator. The proposed approach aims at solving the long-term car pooling problem.

Sub-problems based agents frameworks

For sub-problems based agents frameworks, we will present briefly two wellknown frameworks that have been the results of various works: Probability Collectives (PC) approaches and Distributed Constraint Optimization Problems approaches (DCOP).

Probability Collectives approaches Probability Collectives (PC) in the framework of Collective Intelligence (COIN) was first proposed by David Wolpert in 1999 [START_REF] Wolpert | An introduction to Collective Intelligence[END_REF]. It is an extension from distributed optimization methodology for modelling and controlling distributed MAS, inspired from a sociophysics viewpoint with deep connections to game theory, statistical physics, and optimization [START_REF] Wolpert | An introduction to Collective Intelligence[END_REF][START_REF] Wolpert | Information Theory-The Bridge Connecting Bounded Rational Game Theory and Statistical Physics[END_REF]. In PC, each variable is an independent agent. The action of these agents is assigned via probability distributions which are updated independently according to their local goal and to the global or system objective [START_REF] Wolpert | An introduction to Collective Intelligence[END_REF][START_REF] Bieniawski | Distributed Optimization and Flight Control Using Collectives[END_REF][START_REF] Wolpert | Information Theory-The Bridge Connecting Bounded Rational Game Theory and Statistical Physics[END_REF]. The process is repeated until reaching equilibrium. This equilibrium concept is referred to Nash equilibrium [START_REF] Basar | Dynamic Non-Cooperative Game Theory[END_REF]. The PC approach has been applied to unconstrained problems like: [START_REF] Bieniawski | Distributed Optimization and Flight Control Using Collectives[END_REF][START_REF] Kulkarni | Probability Collectives for Decentralized, Distributed Optimization: A Collective Intelligence Approach[END_REF], 2009;[START_REF] Bhadra | Min-cost selfish multicast with network coding[END_REF][START_REF] Wolpert | Information Theory-The Bridge Connecting Bounded Rational Game Theory and Statistical Physics[END_REF][START_REF] Huang | A Comparative Study of Probability Collectives Based Multiagent Systems and Genetic Algorithms[END_REF][START_REF] Vasirani | Collective-Based Multiagent Coordination: A Case Study[END_REF][START_REF] Huang | Probability Collectives Multi-agent Systems: A Study of Robustness in Search[END_REF][START_REF] Smyrnakis | Sequentially Updated Probability Collectives[END_REF], as well as constrained problems like: [START_REF] Wolpert | An introduction to Collective Intelligence[END_REF][START_REF] Bieniawski | Distributed Optimization and Flight Control Using Collectives[END_REF][START_REF] Sislak | Automated Conflict Resolution Utilizing Probability Collectives Optimizer[END_REF][START_REF] Wolpert | Fleet Assignment Using Collective Intelligence[END_REF][START_REF] Autry | University Course Timetabling with Probability Collectives[END_REF][START_REF] Kulkarni | A Probability Collectives Appraoch with a Feasibility-based Rule for Constrained Optimization[END_REF], 2010).

1.2.3.0.a Distributed constraint optimization approaches

Several optimization problems can be classified as Constraint Satisfaction Problems (CSP) such as the graph coloring problem, the scheduling problem, the asset allocation problem, etc. Solving a CSP is equivalent to finding an assignment of values to all variables such that all constraints are satisfied. The Distributed Constraint Satisfaction Problem resolution is the distributed version of constraint satisfaction problems resolution (CSP). In DCOP, each variable is allocated to an agent which has control of its value. Below, we present some representative DCOP algorithms.

ADOPT [START_REF] Modia | Adopt: asynchronous distributed constraint optimization with quality guarantees[END_REF] is the first asynchronous complete algorithm for optimally solving the Distributed Constraint Optimization Problem (DCOP). Each agent must optimize a global objective function, so it must exchange the choice of variable's values to other agents. DCOP uses only local communication with neighboring agents. The global objective function corresponds to the set of constraints and each agent knows about the constraints in which its variables are involved. ADOPT uses the distributed backtrack search via a novel search strategy and backtrack thresholds. These techniques help agents to explore locally and asynchronously partial solutions. In order to guarantee a good quality solution in a reasonable time, ADOPT employs the bounded-error approximation algorithm.

In [START_REF] Yeoh | BnB-ADOPT: An Asynchronous Branchand-Bound DCOP Algorithm[END_REF], they proposed a Branch-and-Bound ADOPT (BnB-ADO-PT). It is a memory-bounded asynchronous DCOP search algorithm that employs the message-passing and the communication framework of ADOPT [START_REF] Modia | Adopt: asynchronous distributed constraint optimization with quality guarantees[END_REF]. In BnB-ADOPT algorithm, the best-first search was replaced by the depth-first branch-and-bound search. Like ADOPT algorithm, the agents in BnB-ADOPT algorithm are implemented in asynchronous and concurrent way. The communication is only between agents that share constraints. The agents are ordered via a pseudo-tree.

Distributed stochastic algorithm (DSA) [START_REF] Fabiunke | Parallel distributed constraint satisfaction[END_REF]) is a uniform algorithm. In each step, each agent sends its variable value, to its neighboring agents. When it modifies this value, in the previous step, and it receives the state value from its neighbors, it can decide, randomly, to keep its current value or change to a new one. But, the neighbors have to maintain their values. The modification of variable value aims at reducing violated constraints. The DSA uses a probability p to select how frequently neighboring agents change values. p is called the degree of parallel executions. DSA has been used in several DCOP with various extensions [START_REF] Fabiunke | Parallel distributed constraint satisfaction[END_REF][START_REF] Fitzpatrick | An experimental assessment of a stochastic, anytime, decentralized, soft colourer for sparse graphs[END_REF] like graph coloring problem [START_REF] Zhang | Distributed stochastic search for distributed constraint satisfaction and optimization: Parallelism, phase transitions and performance[END_REF], scheduling problem [START_REF] Zhang | An Analysis and Application of Distributed Constraint Satisfaction and Optimization Algorithms in Sensor Networks[END_REF], etc.

Conclusion

In this chapter, we described combinatorial optimization problems and heuristic methods which are used to solve them. Heuristic methods can generate high quality solutions in reasonable computing time. They are improved by techniques of diversification and techniques of intensification, in order to escape local optimum. Other studies explore multi-agent system to create distributed algorithms for solving optimization problems. In the second section, we introduced the agent paradigm and their applications to optimization problems. These methods are motivated by specific features offered by MAS like distributed computing, agent cooperation and dynamic decision making. Indeed, multi-agent systems have been successfully applied to solve many challenging and various problems encountered in various settings. The review above aims to describe some recent MAS-related studies to illustrate the interest of MAS for building expert and intelligent systems for problem solving. Our work shares similarities with these previous studies in the sense that it is based on the generic framework of multi-agent systems. The proposed work, as described in the next chapter, distinguishes itself by some particular features including the distributed and collaborative architecture, the design of both intensification and diversification agents as well as the decision making method based on reinforcement learning. In our work, we investigate a new solution approach for the combinatorial optimization problems based on the principles of multi-agent systems (MAS).

Introduction and motivation

As we have presented in the first chapter, several metaheuristic methods and multi-agent based optimization methods have been proposed in the literature to tackle optimization problems. In this work, we present a generic Multi-Agent based Optimization Method for Combinatorial Optimization Problems (MAOM-COP). MAOM-COP is generic and it can be applied to classical optimization problems. In a search algorithm, one of the most important issues is to find the right balance between diversification and intensification. MAOM-COP distinguishes itself by its learning based distributed computing model, in order to know if the search needs exploration or exploitation, in an intelligent way.

In our framework, we add a cooperative dimension to the evolutionary process. Cooperation between individuals is modeled by embodying each strategy in an autonomous and learning agent which can communicate. The team of agents navigates the search space cooperatively. Some agents of MAOM-COP, which are called intensification agents, employ local search algorithms to reach high quality local optima. Other agents, which are called diversification agents, are trigged, when the search needs to be diversified. These last agents explore perturbation techniques and crossover operators.

In the following section, we will present the architecture of MAOM-COP. Then, we will explain the behavior of each agent. In next chapters, we will apply and evaluate the performance of MAOM-COP on a number of classical combinatorial optimization problems.

MAOM-COP architecture

The proposed MAOM-COP architecture contains the following agents: decisionmaker agent, intensification agents and diversification agents. The intensification agents are composed of agents which perform local search algorithms. The diversification agents are composed of two types of agents which are perturbation agent and crossover agents. Figure 2.1 illustrates the generic MAOM-COP architecture, whose components are detailed in the following sections. Algorithm 2.1 describes the generic procedure of the proposed method. In addition to the above agents, MAOM-COP relies on reinforcement learning based on decision matrices for decision making. By linking a set of conditions and a set of actions, such a matrix helps an agent to know the agents with which it will communicate, according to the state of the search process.

Decision-maker Agent

The common archive

Decision matrix with reinforcement learning

In the proposed MAOM-COP, some agents (decision-maker agent and intensification agents) need to decide when to activate other agents and which agents to activate. Such decisions are made based on a decision matrix which is dynamically adjusted by a reinforcement learning process. This technique allows to adapt the search strategy according to the experiences acquired during the search process. For instance, after the application of an intensification action, if the search is observed to be stagnating (e.g., captured by the condition 'the best solution is not improved for a high number of iterations'), the applied action should be avoided for the next search step and an action ensuring more diversification should be favored. Inversely, if the applied action leads to a search progress (e.g., captured by the condition 'the best solution is just improved'), the same action should be given a high chance to be applied again (notion of reward).

We use a pair (condition, action) to represent the decision rules. The condition part corresponds to the necessary prerequisite to trigger an associated action, the action part indicates which action is to be performed. Let C be the set of conditions and A the set of actions to perform. For a condition C i , a weight W ij (initialized to 0) is associated to each action A j . The conditions are defined based on the improvement situation occurred at the end of each search generation (i.e., one while iteration in Algorithm 2.2). The decision matrix W is used to dynamically influence the probability of applying each action under each condition.

Figure 2.3 -An example of reinforcement learning with the decision matrix

We suppose that the current condition is C3 (e.g., the local best solution has been improved in recent 20 generations). At this condition, action A1 (e.g., activate intensification agents) must be reinforced for the current generation. Then, reinforcement is applied by increasing the weights W 31 to augment the chance of selecting the applied action under this condition (e.g. W 31 = 3 × 0.5 + 1 = 2.5). Nevertheless, the weights W 32 is decreased by µ (e.g. W 32 = 1 × 0.5 = 0.5

Given the decision matrix W (Figure 2.2), we use the following equation [START_REF] Guo | A Multi-agent Based Self-adaptive Genetic Algorithm for the Long-term Car Pooling Problem[END_REF] to calculate the probability P (C i , A j ) of applying action

A j ∈ A under condition C i ∈ C. P (C i , A j ) = W ij j∈A W ij (2.1)
At the beginning of each generation, the improvement situation is assigned to a default condition. Then, according to the decision matrix, the appropriate action for this condition is selected according to the probability given in Eq. ( 2.1). At the end of each generation, the performed action is evaluated with respect to its condition and the concerned weight value is increased if an improvement in solution quality is obtained in this generation. We use a credit assignment to perform the reinforcement learning in order to identify the beneficial experiences and determine a reward for them. Here, an experience is represented as a triplet (condition C i , action A j , improvement V ). When a new best local or global solution is found, the weight value W ij which is related to the action of this generation is reinforced by adding a reward rate σ to W ij . Before adding the reinforcement value, all the weight values W ij in the decision matrix corresponding to the related condition, are decreased with an evaporation value µ, in order to enlarge the influence of the new reward obtained in the current generation. The reinforcement with reward σ is then performed using the following equations:

W ′ ij = µ × W ′′ ij (2.
2)

W ij = µ × W ′ ij + σ (2.3)
where W ′ ij is the weight value before adding the reinforcement σ, W ′′ ij is the weight value before the evaporation µ, and σ is the learning factor.

Figure 2.3 shows an illustrative example of this reinforcement learning process (More information about the example are given in section 2.4.1). In the proposed MAOM-COP, such a matrix is used by the decision-maker agent (section 2.4) and the intensification agents (section 2.5). The respective conditions and actions used by these agents are provided in these sections.

MAOM-COP process

The MAOM-COP procedure is summarized in Algorithm 2.1. The decisionmaker agent initiates the search with a random feasible solution. Based on a decision matrix W explained in the previous subsection, it decides to trigger either the intensification agents or the crossover agents belonging to diversification agents (lines 1-9 of Algorithm 2.2). As a result, one of the two following cases occurs.

-Case 1: Intensification agents are triggered:

This case corresponds to the situation where the decision-maker agent decides that a more intensified search is needed considering the current search state. For this, it triggers the intensification agents by sending them the current solution (lines 10-11 of Algorithm 2.2). Each intensification agent looks for the best solution in the predefined neighborhood for q iterations by applying a local search procedure. Each agent uses a different neighborhood structure and starts with the solution received from the decision-maker agent (lines 6-11 of Algorithm 2.3).

After an iteration (i.e., one while iteration in Algorithm 2.3) of the intensification agent concerned, each intensification agent decides whether it needs to communicate with the other intensification agent or it can continue its process without information exchange. This decision depends on another decision matrix Q (see section 2.5). Q has the same mechanism as the decision matrix W of the decision-maker agent, but here, the actions to be performed are either to trigger another intensification agent (for intensification) or a perturbation agent (for diversification).

When the search needs to be intensified, the agent concerned calls another intensification agent and remains blocked until it receives the best solution sent by the other intensification agent. Thereafter, the requesting agent completes its search starting with the solution received. When the desired action is about diversification, the perturbation agent is triggered (lines 17-23 of Algorithm 2.3). This agent performs one of two types of perturbations (reduced and strong perturbations) with the purpose of helping the intensification agents to move towards new search areas. According to whether the requesting intensification agent needs a small or large diversification, either a reduced perturbation or strong perturbation is performed.

The new solution from the perturbation is passed to the intensification agent to continue its search. The intensification agents execute for a number of iterations by exchanging information as we just explained (lines 27-28 of Algorithm 2.3). The best solutions obtained are forwarded to the decisionmaker agent (line 38 of Algorithm 2.3). The decision-maker agent records the solutions received in an archive that represents a common memory shared by all agents in the algorithms (lines 17-26 of Algorithm 2.2).

-Case 2: Crossover agents are triggered:

If the crossover agents are activated (lines 13-15 of Algorithm 2.2), they are applied to two parent solutions (which are selected from the archive) to create offspring solutions (section 2.7). These new solutions are sent back to the decision-maker agent which stores them in the shared archive if they are of good quality. The best offspring solution is taken as the new starting point, to continue the search.

The decision-maker agent uses the current best solution found so far to start the next cycle (generation) of the algorithm. The values of the decision matrix are updated according to the new state reached by the last generation, in order for the decisionmaker agent to activate the appropriate agents for the next generation. This search process is repeated until a stop condition is satisfied (e.g., a maximum number of generations) and the best solution discovered is retained as the final result. if an intensification agent requests help from the perturbation agent then 5: perturbation agent is activated and the intensification agent is blocked until it receives information from perturbation agent (section 2.6) 6:

perturbation agent is killed after sending information to the corresponding intensification agent the intensification agents are killed after sending information to decisionmaker agent 12: end if 13: if decision-maker agent decides to trigger crossover agents then 14:

the crossover agents are activated and decision-maker agent waits for new information from the crossover agents (section 2.7) 15:

the crossover agents are killed after sending information to decision-maker agent 16: end if 17: Return best information found

Decision-maker agent

The decision-maker agent is the coordinating agent. According to the decision making matrix W (section 2.2.1), the decision-maker agent decides whether it triggers the intensification agents (for more intensification) or crossover agents (for more diversification). It records the high-quality solutions which are discovered during the search in the shared memory (archive) (Algorithm 2.2).

The decision-maker agent thus exchanges information with the intensification agents or the crossover agents. The decision-maker agent stays alive until reaching a stop criterion (a cutoff time limit, an allowed number of generations). During its life, it is blocked when other agents are activated. So, it has only one life cycle.

Conditions and actions

During the search process of our algorithm, three types of solutions are used to define conditions for agent activation: the local current solution obtained by each agent, the local best solution obtained by each agent and the global best solution obtained among all agents in the process. The decision matrix of the decision-maker agent is composed of four different conditions which cover significant situations that may occur during the search process:

-C 1 = The algorithm does not reach g 0 generations (cycles); -C 2 = The local or global best solution is improved in the recent g 1 generations and this improvement is a small improvement in the objective function value F ; -C 3 = The local or global best solution is improved in the recent g 1 generations and this improvement is a large improvement in the objective function value F ; -C 4 = The global best solution does not have been improved in the recent g 2 generations. This solution is a deep local optimum or an optimum solution. where g 0 , g 1 and g 2 are parameters set by the user according to the total allowed generation number or total run time.

The set of actions are:

-A 1 = Activating the intensification agents; -A 2 = Activating the crossover agents. At the beginning of the search or when there is a large improvement obtained by the application of an action between two successive generations (this corresponds to the situations of C 1 and C 3 ), the search progresses well and, in this case, it is appropriate to make intensified search by triggering the intensification agents. If the decision-maker agent observes no improvement or an insignificant improvement (this corresponds to the situations of C 2 and C 4 ), the search is stagnating and needs to be diversified by activating the crossover agents.

After each generation (i.e., when the activated agents return their found solution), the decision-maker agent updates its decision matrix as explained in section 2.2.1. Figure 2.3 illustrates how the decision matrix is changed by the reinforcement learning procedure. We suppose that in iteration i of Algorithm 2.2, the current con-dition C 3 is verified (i.e., the local best solution is greatly improved in the recent g 1 = 20 generations). Under this condition, action A 1 which corresponds to activating intensification agents is applied for the current generation. Reinforcement learning is applied by increasing the weight W 31 to augment the chance of selecting the corresponding action under this condition. In Figure 2.3, we show for this example, the initial decision matrix (left), and the matrix (right) after the update with a reward value σ = 1 and an evaporation value µ = 0.5.

Archive of elite solutions

The decision-maker agent records the best solutions discovered during the search in an archive. These solutions are generated and submitted by the intensification agents and the crossover agents. Even if the archive is shared by all the agents of the model, only the decision-maker agent is responsible to update it. Each time the decision-maker agent receives a new solution, it adds the solution in the archive, if it is of good quality and is not present already in the archive.

Intensification agents

The intensification agents are designed for intensification. During its life time, an intensification agent employs a neighborhood to generate improved solutions. During the search, each intensification agent can decide, with the help of a decision matrix, to exchange information with other alive intensification agents or with the perturbation agent depending on its state of search. At the end of each intensification agent run, the best solution found by the agent is sent to the decision-maker agent (Algorithm 2.3). Below, we explain the conditions and the actions employed by intensification agents.

Conditions and actions

As explained at the beginning of this section, each intensification agent can decide, with the help of a decision matrix, to exchange information with other alive intensification agents or with the perturbation agent depending on its state of search. In this section, we present the conditions and the actions employed by the intensification agents. The decision matrices are managed by the same technique of the decision matrix of decision-maker agent (section 2.2.1).

The set of the conditions are:

-C 1 = The local best solution is improved in recent q 3 generations and this improvement is a small improvement; -C 2 = The local best solution is not improved in recent q 4 generations; -C 3 = The local best solution is not improved in recent q 5 generations and q 5 > q 4 . where q 3 , q 4 and q 5 are parameters set by the user according to the total generation number or total run time. The set of actions are:

-A 1 = Activating other intensification agents; -A 2 = Activating the reduced perturbation behavior of the perturbation agent; -A 3 = Activating the strong perturbation behavior of the perturbation agent. Each condition promotes a certain action. Thus, when the condition C 1 is met, one pursues an intensified search by activating other intensification (A 1 ). When C 2 (resp. C 3 ) is satisfied, the search needs to be diversified by triggering the perturbation agent with reduced (resp. strong) behavior (A 2 or A 3 ). The choice of the most suitable action is controlled by the corresponding decision matrix of each intensification agent.

Perturbation agent

The perturbation agent is triggered by intensification agents under specific conditions (C 2 and C 3 of section 2.5.1). Basically, this agent disrupts a solution sent by an intensification agent. The disruption is achieved by either a reduced perturbation behavior or strong perturbation behavior. Then, the resulting solution is sent back to the intensification agent which uses the perturbed solution as its new current solution. Since the perturbation agent can be called many times, it can have several life cycles.

Reduced perturbation technique

The perturbation agent can be triggered when an intensification agent observes a slight search stagnation (condition C 2 of section 2.5.1). From the solution received from the intensification agent, the perturbation agent performs a number of random moves to generate a new solution.

Strong perturbation technique

The second case where the perturbation agent can be activated is when it receives a request for strong perturbation from an intensification agent. The perturbation agent then employs the common archive of elite solutions to create a new solution.

Crossover agents

Crossover agents are agents for diversification. Each crossover agent performs a different crossover operation to generate one offspring solution. Offspring solutions are transmitted to the decision-maker agent to be a new starting point for the search process. In both cases, parents are selected from the common archive.

Algorithm 2.3. Intensification agent behavior

Require: Solution S 0 received from decision-maker agent, parameters: maximum iterations iteration_max, improvement threshold interval, consecutive non-improving iterations max_opt_LS Ensure: A best solution S best_LS 1: S ← S 0 {S is the current solution found by each intensification agent} 2: Q ← 0 {Q is the decision matrix, section 2.5.1} 3: opt = 0 {opt is the counter for consecutive non-improving local optima} 4: S 1 ← S 0 {S 1 records the solution obtained in generation iteration-1}

Discussion

This chapter presented a multi-agent based optimization method for solving combinatorial optimization problems. Our method is able to select if the search needs to be intensified or diversified. This is realized by a group of agents which concurrently explore the search space but cooperate to coordinate the search and improve their behaviors. These agents are reinforced by a learning mechanism, in order to know which techniques to trigger. The intensification agents of MAOM-COP can as well be related to the VNS and the ILS methods because they use several neighborhood strategies and different perturbation techniques throughout the optimization process. The change of neighborhoods offers an adaptive mechanism for tracking the optimum in the search space. In addition, switching between several perturbation strategies aims to escape poor optima. In contrast with these two metaheuristics and due to distributed and parallel behaviors of MAOM-COP, intensification agents and perturbation agent can exchange solutions during the search.

Like memetic algorithms, MAOM-COP integrates crossover agents. Crossover agents are triggered only when a local optimum is reached. These agents can be considered as another technique of diversification that directs the search towards more promising regions of the search space. Among multi-agent based optimization methods, MAOM-COP is the first one that considers all these techniques which cover the optimization process. Other existing methods (like (Je ¸drzejowicz & Wierzbowska, 2006)), use only one metaheuristic in each agent and there is no efficient exchange with them.

Conclusion

Our work is motivated by appealing features of a MAS which could be advantageously used to elaborate intelligent computing systems. Compared with existing studies on the COP, this work has the following main contributions: it integrates a set of collaborative agents (tabu search agents, crossover agents, perturbation agent) which are managed dynamically by a distributed model to ensure a suitable balance of intensification and diversification of the given search space. Decision making is based on reinforcement learning which is used to adjust the probability of applying dedicated actions to trigger specific agents under specific conditions. The proposed approach is generic and could be adapted to design distributed intelligent systems for complex search problems.

MAOM-COP can be applied to different combinatorial optimization problems. In the next chapters, we will see that only neighborhood relations for intensification agents, evaluation functions, perturbation moves for perturbation agent and crossover operators for crossover agents, will be changed according to the considered problem. The learning mechanism, used to indicate which agents to activate, is the same for all problems. This includes the update of decision matrices and the definition of the conditions and actions in these matrices.

A Multi-Agent based Optimization Method for the Quadratic Assignment Problem

In this chapter, we apply the proposed method explained in chapter 2 to the Quadratic Assignment Problem (QAP). We will present the QAP and the most effective algorithms for this problem. Then, we will describe MAOM-QAP, i.e., the adaptation of MAOM-COP to the QAP by describing the behaviors of the agents. MAOM-QAP is evaluated using various benchmark instances. The comparison with the current state of the art approaches, shows that the proposed algorithm performs well in terms of solution quality. The content of this chapter is presented in (Sghir & al., 2015b

Problem definition

The Quadratic Assignment Problem (QAP) is known as one of the most popular combinatorial optimization problems with a number of practical applications like backboard wiring in electronics, analysis of chemical reactions for organic compounds, design of typewriter keyboards balancing turbine runners [START_REF] Burkard | Locations with spatial interactions: The quadratic assignment problem[END_REF][START_REF] Duman | The quadratic assignment problem in the context of the printed circuit board assembly process[END_REF].

Given a flow f ij from facility i to facility j for all i, j in {1, 2, ...n} and a distance d ab between locations a and b for all a, b in {1, 2, ...n}, the QAP is to assign the set of n facilities to the set of n locations while minimizing the sum of the products of the flow and distance matrices. Let Π be the set of the permutation functions π: {1, 2, ...n} → {1, 2, ...n}. The QAP is mathematically formulated as follows:

M inimize π ∈ Π F (π) = n i=1 n j=1 f ij d π i π j (3.1)

State of the art approaches for the QAP

In this section, we present a brief summary of some of the most representative heuristic algorithms for the QAP. These algorithms will be used as reference algorithms for our computational study. Note that none of these QAP approaches can be considered as the most effective method for all QAP benchmark instances, due to the differences in structures of the benchmark instances.

The robust tabu search (Ro-TS) algorithm, proposed by [START_REF] Taillard | Robust taboo search for the quadratic assignment problem[END_REF], is an early and influential heuristic. Ro-TS employs the swap move which exchanges two elements of a solution (a permutation). The tabu list forbids the reverse exchange of a swap move during the next h iterations. The tabu tenure h varies randomly within a given interval. The most important new feature introduced in Ro-TS is that a complete swap neighborhood is explored in O(n 2 ) instead of O(n 3 ) as in previous algorithms. We use this technique in our algorithm.

The improved hybrid genetic algorithm (IHGA) is proposed by [START_REF] Misevicius | An improved hybrid genetic algorithm: New results for the quadratic assignment problem[END_REF]. IHGA integrates a robust local improvement procedure and a new optimized crossover. The optimized crossover uses M runs of an uniform crossover to produce a child that has the best fitness value. The offspring is then improved with a tabu search procedure and a solution reconstruction procedure. The reconstruction is attained by performing a number of random swaps. IHGA uses also a shift mutation, which simply consists in shifting all the items in a wrap-around fashion by a predefined number of positions.

Misevicius [START_REF] Misevicius | Iterated tabu search: An improvement to standard tabu search[END_REF] later proposed an iterated tabu search (ITS). It applies a traditional tabu search. When it reaches local optima, it triggers a perturbation phase in order to escape the attained local optimum. The found solution becomes a new starting point for the basic TS procedure. The perturbation mechanism adaptively changes the number of random perturbation moves in some interval.

The particular population-based iterated local search (PILS) proposed by [START_REF] Stützle | Iterated local search for the quadratic assignment problem[END_REF]) is an extension of iterared local search (ILS). The algorithm applies the don't look bit strategy, inspired from the local search algorithms for the TSP. When a local optimum is attained, ILS executes a perturbation move that consists of exchanging k randomly chosen items. In PILS, the population contains p solutions and in each iteration q new solutions are generated. The new population of p solutions is created from the p former solutions and the q new solutions.

The cooperative parallel tabu search algorithm (CPTS), which is proposed by [START_REF] James | A Cooperative Parallel Tabu Search Algorithm for the Quadratic Assignment Problem[END_REF], applies the parallel execution on multiple processors based on several tabu search (TS) runs. The TS procedure is the same as Ro-TS [START_REF] Taillard | Robust taboo search for the quadratic assignment problem[END_REF], but it uses different stopping conditions and the tabu tenure parameters for each processor participating in the algorithm. The cooperation and information exchange between TS processes are realized with the help of a global reference set.

The Breakout Local Search (BLS) proposed by [START_REF] Benlic | Breakout local search for the quadratic assignment problem[END_REF]) is based on a local search phase and a dedicated perturbation phase. The local search phase aims to reach new local optima, while the perturbation phase is used to discover new promising regions. The perturbation mechanism of BLS dynamically determines the number of perturbation moves and adaptively chooses between two types of moves of different intensities depending on the current search state. The types of perturbation are a guided perturbation using a tabu list and a random perturbation. BLS is later integrated into the memetic search framework in [START_REF] Benlic | Memetic search for the quadratic assignment problem[END_REF]. BMA combines BLS as local optimizer, a crossover operator, a pool updating strategy, and an adaptive mutation mechanism. BMA outperforms its local search component (BLS).

Our proposed algorithm distinguishes itself by its multi-agent based distributed computing model which is described in the next section.

A multi-agent based optimization method for the QAP (MAOM-QAP)

In this section, we present the Multi-Agent based Optimization for the QAP (MAOM-QAP), which is an adaptation of our generic MAOM-COP method to the QAP. We consider the following agents: the decision-maker agent, two tabu search agents which are intensification agents, the perturbation agent and two crossover agents. In particular, we show the problem dependent ingredients such as the neighborhood relation manipulated by tabu search agents, the crossover operators used by crossover agents and the perturbation moves explored by perturbation agent.

Decision-maker agent

The Decision-maker agent selects other agents to trigger based on its decision matrix (section 2.2.1) and according to the specific condition (section 2.4.1). If other agents (tabu search agents or crossover operator agents) are trigged, the decisionmaker agent waits high-quality solutions received from these agents, to record them in the shared memory (archive) (Algorithm 2.2). In addition, it generates the initial solution, in order to start the search and sends it to the appropriate agents. For the QAP, this solution consists in a simple random initial facility location assignment.

Tabu search agents

The tabu search agents manage the intensification search of MAOM-QAP. Each tabu search agent uses a tabu search algorithm applying two different strategies to explore the swap-based neighborhood (Algorithm 2.3). Based on their decision matrix (section 2.2.1) and according to the corresponding condition (section 2.5.1), they can request helps from another alive tabu search agent or the perturbation agent. At the end of each tabu search agent run, the best permutation found by the agent is sent to the decision-maker agent. Below, we define the two neighborhood exploration strategies employed by these agents.

Neighborhood

As explained in the introduction, a candidate QAP solution can be conveniently represented by a permutation π of {1, 2, ...n} where π i is the facility assigned to location i. Let swap(i, j) be a move operator which exchanges the facilities located at i and j. Given a candidate solution π, let π ′ = π ⊕ swap(i, j) be the neighboring solution of π obtained by exchanging the facilities π i and π j of locations i and j. Then N (π) = {π ′ : π ′ = π ⊕ swap(i, j), i, j ∈ {1, 2, ...n}, i = j} is the set of neighboring solutions induced by the swap operator. To assess the relative quality of a neighboring solution π ′ , i.e., the cost variation δ(π, i, j) = F (π ′ ) -F (π) between π and π ′ (also called the move gain of swap(i, j)), we use the incremental technique proposed in [START_REF] Taillard | Robust taboo search for the quadratic assignment problem[END_REF] which can be achieved in O(n) in the worst case.

Neighborhood exploration strategies

Given this neighborhood, our tabu search agents employ two different strategies to explore the neighboring solutions. Let π be the incumbent solution and N (π) its neighborhood. Our first tabu search agent examines the whole neighborhood N (π) (in O(n 3 )) and retains the best neighboring solution which becomes the new incumbent solution. As such, this tabu search agent realizes a highly aggressive exploitation of the neighborhood, ensuring thus an intensified search. Our second tabu search agent operates slightly differently in two stages. First, it picks at random a location i. Then it seeks the best location j which leads to the highest swap(i, j) move gain. This neighborhood exploration strategy, which is achieved in O(n 2 ), leads to a less aggressive search. Yet, given the random choice of one of the two locations to be exchanged, this strategy provides the tabu search agent with an intensified search while ensuring some degree of diversification at the same time.

Tabu list

Each tabu search agent uses a traditional tabu list to prevent the search from revisiting a previously encountered solution. Each time a facility x i is displaced from location i to a new location by a swap(i, j) move, x i is forbidden to move back to location i during the next h iterations. The iterations h is dynamically determined by h = α × F (S) + rand(10), where rand(10) takes a random number in [1, ...., 10] and α is set to 0.09.

Perturbation agent

When tabu search agents need help from the perturbation agent under specific conditions (C 2 and C 3 of section 2.5.1), they decide to trigger the latter agent. This agent disrupts a solution sent by a tabu search agent. Two parallel behaviors, that are reduced perturbation behavior and strong perturbation behavior, are realized. The resulting solution is used then by the tabu search agent as its new current solution.

Reduced perturbation technique

In order to solve a slight search stagnation (condition C 2 of section 2.5.1), the tabu search agents can activate the perturbation agent with a reduced behavior. The last agent applies a number of random swap moves to generate a new solution, started from the solution received from tabu search agents. This is achieved by exchanging the locations of two facilities chosen randomly. Also, the number of perturbation swap moves is chosen randomly between 1 and n/2 (n being the number of facilities).

Strong perturbation technique

When a strong search stagnation (optimum) is encountered, the perturbation agent can receive a request for strong perturbation from a tabu search agent. The perturbation agent uses the common archive of elite solutions to create a new solution. From this archive, the perturbation agent extracts the number of occurrences of each facility i assigned to location x i . Then, each facility i is assigned to the location having the smallest occurrence number. Additional data structures are employed to avoid the creation of the same solution for future calls to the perturbation agent.

Crossover agents

The decision-maker agent can trigger crossover agents, when it observes that the search is trapped into a deep optimum. For the QAP, we have two crossover agents each one performing a different crossover operation to generate one offspring solution. The two offspring solutions are sent to the decision-maker agent to be a new starting point for the search process. In each crossover agent, the parents are chosen randomly from the common archive. Each crossover agent applies one of the following crossover operators:

-The first operator consists in blending uniformly information from the parents. Given two selected parents, the crossover operator builds one offspring solution by alternatively transmitting location-facility assignments from the parents. Specifically, starting with the parent having the smallest objective value, the first crossover agent transmits the facility of the first location (i.e., with index one) to the first location of the child and then removes the assigned facility from both parents. For the second location of the child, it switches to the other parent and transmits the facility (which may be empty) of the second location (i.e., with index two) to the child. Then, this agent goes back to parent one and repeats this process until reaching the last location. Finally, the unassigned facilities of the offspring are affected to a location randomly chosen among the set of the free locations. -The second crossover operator has the same idea of the first crossover operator, only the first z << n (a parameter) location-facility assignments of each parent are transmitted to the offspring solution. The crossover agent starts from the parent who has the smallest objective value to build the child. It copies the z first location-facility assignments of this parent into the child. Then, it extracts from the other parent, the next z location-facility assignments and copies them to the child from the z + 1 locations. Finally, each unassigned facility is affected to a random unassigned location. Figures 3.1 and 3.2 provide illustrating examples for these two crossover operators.

Experimentation

This section presents experimental results of MAOM-QAP. We campare it with best-known algorithms from the literature, then we give the impacts of the composing agents in terms of solution quality.

Experimental results

MAOM-QAP was implemented in Java using the multi-agent platform Jade. The program was run on a computer with a Core I5 2.5 GHz, 8GB of RAM. To assess MAOM-QAP, tests were realized on various benchmark instances from the QAPLIB (http://www.seas.upenn.edu/qaplib/inst.html). The instances size n varies from 12 to 150 (indicated in the instances name).

The QAPLIB archive contains 135 instances that can be divided into four types: 1. Type I: Real-life instances obtained from practical applications; 2. Type II: Unstructured and random instances for which the distance and flow matrices are randomly generated based on a uniform distribution;

3. Type III: Randomly generated instances with structure that is similar to that of real-life instances; 4. Type IV: Instances in which distances are based on the Manhattan distance on a grid.

Following [START_REF] Benlic | Memetic search for the quadratic assignment problem[END_REF], we focus on the set of 21 most challenging instances of types II-IV (the remaining 114 instances including all the real-life instances of Type I are easy and are not included in the paper).

We adjusted the parameters of the proposed algorithms by an experimental study. They depend on the type of the problem. The number of iterations for each local search agent (iter_max) was fixed to 1000. The parameter interval that evaluates the improvement of the solution was fixed to 10000 for the decision-maker agent and the tabu search agents. The parameters g 0 , g 1 , g 2 , q 3 , q 4 and q 5 , which are the numbers of generations responsible for controlling the improvement of the search process (presented in section 2.4.1 and section 2.5.1), were fixed respectively to 2, 10, 2, 20, 20 and 25. The parameter rate µ used in updating the decision matrices was fixed to 0.5. The stopping condition is the elapsed time which we set to 12 hours for all the instances of size n < 100, and to 24 hours for the large instances of size n >= 100. The best-known solutions can be attained before these time limits.

We compare our MAOM-QAP to seven best-known algorithms from the literature cited in the introduction of the paper.

-Improved hybrid genetic algorithm (IHGA) [START_REF] Misevicius | An improved hybrid genetic algorithm: New results for the quadratic assignment problem[END_REF]; -Iterated tabu search (ITS) [START_REF] Misevicius | Iterated tabu search: An improvement to standard tabu search[END_REF]; -Population-based iterated local search (PILS) [START_REF] Stützle | Iterated local search for the quadratic assignment problem[END_REF]; -A hybrid genetic tabu search algorithm (MRT60) [START_REF] Drezner | Extensive experiments with hybrid genetic algorithms for the solution of the quadratic assignment problem[END_REF]; -Cooperative parallel tabu search (CPTS) [START_REF] James | A Cooperative Parallel Tabu Search Algorithm for the Quadratic Assignment Problem[END_REF]; -The Breakout local search (BLS) [START_REF] Benlic | Breakout local search for the quadratic assignment problem[END_REF]; -The population-based Memetic Algorithm (BMA) [START_REF] Benlic | Memetic search for the quadratic assignment problem[END_REF].

Our main purpose of this assessment is to compare our results with the bestknown results ever reported by any existing algorithms of the literature. Note that these best-known results, as well as those of the reference algorithms, have been achieved by different algorithms under various conditions (different stop conditions, computing platforms etc). As a result, the comparisons with the existing methods are included only for indicative information.

Table 3.1 reports our computational results along with those of the seven reference algorithms on the unstructured instances (type II) and real-life like instances (type III). The second column 'BKS' presents for each instance the best-known objective value ever reported in the literature. For each algorithm, column δ shows the percentage deviation of the average solution, obtained with the considered algorithm over a certain number of trials, from the best-known solution. If known, the success rate for reaching the best-known solution over several trials is given in parentheses next to the value of the δ. The CPU time (in minutes) is only given for indicative purposes. The last row indicates the averaged information.

For the unstructured instances (type II), MAOM-QAP finds the best-known solution for 7 out of the 9 instances like other algorithms. We show in Table 1 only the results of 5 most difficult instances because the 4 other instances are easy to solve. The average deviation δ from the best-known solution is 0.341. As to the real-life like instances (type III), MAOM-QAP can attain the best-known solution for all the instances, except for the largest instance tai150b. The difference of deviation δ between them is 0.015 over the 5 instances, which matches the performance of BLS and CPTS. Table 3.2 presents our computational results along with those of the seven reference algorithms on the instances with grid distances (type IV). We observe that MAOM-QAP is able to reach the best-known results for 14 out of the 15 instances with a deviation δ of 0.001 which is the best result with CPTS and BMA. As to the computing times, MAOM-QAP is more computationally expensive due to the perturbation agent whichse impact will be presented in the next section.

Impact of perturbation agent on MAOM-QAP

In the MAOM-QAP algorithm, we use two different perturbation techniques leading to either a reduced or strong perturbation behavior. In this section, we perform an experiment to assess the usefulness of the perturbation agent. For this, we compare MAOM-QAP and MAOM-QAP with its perturbation agent disabled by running them under the same condition as specified in section 3.4 and report the comparative results in Tables 3.3 and 3.4 where MAOM-QAP' is MAOM-QAP without the perturbation agent. These tables disclose that on all the benchmarks, MAOM-QAP without the perturbation agent fails to reach the best-known results of 21 instances. These results show that the perturbation agent reinforces the search performance of MAOM-QAP.

Impact of crossover agents on MAOM-QAP

In order to show the relative effectiveness of the crossover agents which represent a technique of diversification in our algorithm, we compare MAOM-QAP with and without the crossover agents. As before, we run both algorithms under the same condition as specified in section 3.4 and report the comparative results in Tables 3.5 and 3.6 where MAOM-QAP" is MAOM-QAP without the crossover agents. We observe that the algorithm without the crossover agents (MAOA-QAP") performs much worse since it can find the best-known results for only 4 out of the 21 instances. So, we can conclude that the crossover agents are indispensable for the performance of our MAOM-QAP algorithm.

Conclusion

In this chapter, we introduced a multi-agent algorithm for the Quadratic Assignment Problem based on different techniques of intensification and diversification. The decision-maker agent is the central agent which decides the most suitable agent to activate and maintains a shared memory to record the elite solutions discovered during the search. Its decisions are influenced by a learning-based probabilistic strategy which dynamically adjusts the application probability of a particular action under a specific condition. On the other hand, the tabu search agents are introduced to ensure an intensified examination of specific search zones while the perturbation agents and crossover agents are used to diversify the search.

Our computational study shows that the proposed approach performs well on the tested benchmark instances in terms of solution quality.

A Multi-Agent based Optimization Method for the Graph Coloring Problem

In this chapter, we apply the proposed method to the Graph Coloring Problem (GCP). We will start with the problem definition and a brief review of popular graph coloring algorithms. Then, we will define the agents of MAOM-GCP, which adapts the MAOM-COP to the GCP. The proposed algorithm will be evaluated on graph coloring benchmarks. The comparative study shows that MAOM-GCP is able to reach the best known solution of several instances. The content of this chapter is published in (Sghir & al.,

Problem definition

Given an undirected graph G = (V, E) with vertices set V , edges set E and an integer k. A k-coloring of G is represented by S = V 1 , V 2 , ..., V k . The value V (x) of a vertex x defines the color of x. The vertices with color r ( 1 < r < k) correspond to a color class. If two adjacent vertices x and y are colored with the same color r, vertices x and y are declared as conflicting vertices, the edge [x, y] is a conflicting edge, and r is a conflicting color. A coloring graph with no conflicting edge is called a legal k-coloring.

The graph coloring problem (GCP) aims at determining the smallest integer k (called chromatic number of G, ℵ(G)) such that there exists a legal k-coloring of G. There are four different strategies to represent the search space: legal strategy, penalty strategy, k-fixed partial legal strategy, k-fixed penalty strategy. We adopt the k-fixed penalty strategy like many studies. In this strategy, we fix the number k of colors and we accept all possible k-colorings which can be legal or illegal solutions. Given a k-coloring S = {V 1 , V 2 , ..., V k }, the evaluation function f consists in calculating the conflict number induced by S such that:

f (S) = u,v∈E δ uv (4.1)
where

δ uv = 1, if u ∈ V i , v ∈ V j , i = j 0, otherwise
Based on this function, we seek to minimize its value. So, in order to find a legal k-coloring S, the evaluation function f(S) = 0. The GCP can be associated with a variety of real-world applications, such as the frequency assignment [START_REF] Smith | Improving heuristics for the frequency assignment problem[END_REF], the satellite range scheduling (Zufferey & al., 2008), the crew scheduling [START_REF] Gamache | A graph coloring model for a feasibility problem in monthly crew scheduling with preferential bidding[END_REF], the printed circuit testing [START_REF] Garey | An application of graph coloring to printed circuit testing[END_REF], the timetabling [START_REF] Burke | A graphbased hyper heuristic for timetabling problems[END_REF], the register allocation [START_REF] Dewerra | On a graph-theoretical model for cyclic register allocation[END_REF]. The GCP is a well-known NP-complete problem [START_REF] Garey | Computers and intractability: A guide to the theory of NP-completeness[END_REF].

State of the art approaches for the GCP

In this section, we make a review on popular heuristic algorithms solving the GCP. Greedy search is the first heuristic algorithm for the GCP. The largest saturation degree heuristic (DSATUR) and the recursive largest first heuristic (RLF) [START_REF] Leighton | A graph coloring algorithm for large scheduling problems[END_REF] are the most successful algorithms. These algorithms are often employed to generate initial solutions for advanced metaheuristic algorithms.

The GCP can be solved by metaheuristics which can be divided into three types of methods: local search methods, population based methods and hybrid methods.

Several local search methods are applied to GCP, such as simulated annealing [START_REF] Kirkpatrick | Optimization by simulated annealing[END_REF], tabu search [START_REF] Glover | Future paths for integer programming and links to artificial intelligence[END_REF], variable neighborhood search [START_REF] Mladenovic | Variable Neighborhood Search[END_REF], iterated local search (Chiarandini & Stützl, 2002) and large scale neighborhood search [START_REF] Trick | A Large Neighborhood Search Heuristic for Graph Coloring[END_REF]. Hertz and Werra [START_REF] Hertz | Using tabu search techniques for graph coloring[END_REF] were the first who used tabu search (TS) known as Tabucol to find a solution to the graph coloring problem using k-fixed penalty strategy.

Another complete version of Tabucol is obtained by Dorne and Hao [START_REF] Dorne | Tabu Search for graph coloring, T-coloring and Set T-colorings[END_REF]. Zufferey et al. [START_REF] Blochliger | A graph coloring heuristic using partial solutions and a reactive tabu scheme[END_REF] proposed a variant of Tabucol known as Partialcol which integrated a reactive component to adjust the length of the time of the moves. Porumbel et al. (Porumbel & al., 2009) elaborated a new local search algorithm known as position guided tabu search (PGTS) heuristic which adds techniques to avoid local optima. Hertz et al. (Hertz & al., 2008) proposed variable search space (VSS-COL) which alternates different techniques from the three different local search heuristics: Tabucol, Partialcol, and a third tabu search algorithm proposed by [START_REF] Gendron | On edge orienting methods for graph coloring[END_REF].

Population based methods are, also, used to solve GCP as genetic algorithm [START_REF] Holland | Adaption in natural and artificial systems[END_REF], ant colony optimization [START_REF] Dorigo | Positive feedback as a search strategy[END_REF], particle swarm optimization [START_REF] Kennedy | Particle swarm optimization[END_REF].

Hybrid methods are methods which combine different techniques from local search methods and population based methods. Hao and Galinier [START_REF] Galinier | Hybrid evolutionary algorithms for graph coloring[END_REF] proposed an hybrid coloring algorithm (HCA) that is based on tabu search and genetic algorithm. HCA integrates the greedy partition crossover (GPX) operator which combines color classes instead of specific color assignments. Lim and Wang [START_REF] Lim | Meta-heuristics for robust graph coloring problem[END_REF]) used various metaheuristic which are genetic algorithm, simulated annealing and tabu search. Sivanandam et al. [START_REF] Sivanandam | A hybrid parallel genetic algorithm approach for graph coloring[END_REF] elaborated a new permutation based representation of the graph coloring problem. They used a parallelism model for genetic algorithm (PGA) based on Message Passing Interface (MPI) getting three crossover operators. David [START_REF] Chalupa | Population-based and learning-based metaheuristic algorithms for the graph coloring problem[END_REF] proposed two algorithms for GCP. A multi-agent evolutionary algorithm (MEA) based on multi-agent system where an agent represents a tabu search procedure. The second algorithm is a pseudo reactive tabu search (PRTS) integrating a new online learning strategy. Lu and Hao [START_REF] Lu | A memetic algorithm for graph coloring[END_REF] proposed a memetic algorithm (MACOL) integrating several distinguished features such as an adaptive multi-parent crossover (AMPaX) operator which is inspired from GPX crossover operator and a distance-and-quality based replacement criterion for pool updating. It uses the Tabucol as a local search algorithm.

In [START_REF] Titiloye | Graph Coloring with a Distributed Hybrid Quantum Annealing Algorithm[END_REF], Olawale et al. proposed a distributed hybrid quantum annealing algorithm. Quantum simulated annealing is a population of agents cooperating to optimize a shared cost function defined as the total energy between them. This algorithm finds better results than those of any known algorithm, for some graphs. Wu and Hao introduced, in (Wu & Hao, 2012), a forward independent set extraction strategy to reduce the initial graph. From the reduced graph, Algorithm 4.1. The greedy largest saturation degree heuristic (DSATUR): The saturation degree of a vertex as the number of different colors to which it is adjacent (colored vertices). Require: Graph G Ensure: the initial k-coloring S 0 1: while All the vertices are not colored do 2:

Arrange the vertices by decreasing order of degrees.

3:

Color a vertex of maximal degree with color i 4:

Choose a vertex with a maximal saturation degree. If there is an equality, choose any vertex of maximal degree in the uncolored subgraph.

5:

Color the chosen vertex with the least possible (lowest numbered) color.

6:

i = i + 1 7:
return to 4 8: end while between all agents. It is updated by the decision-maker agent with new solutions of good quality.

Tabu search agents

The decision-maker agent can activate two tabu search agents, when it observes that the search process needs to be intensified based on its decision matrix. Each tabu search agent applies a specific strategy based on a particular neighborhood to seek new solutions. During the search, a tabu search agent can exchange its solutions with another alive tabu search agent or with a perturbation agent. These communications depend on a decision matrix, conditions and actions explained in (section 2.2.1) and (section 2.5.1). At the end of each tabu search agent run, the best k-coloring found by each agent is sent to the decision-maker agent. The behavior of the tabu search agent is described in Algorithm 2.3. Below, we define the used neighborhood structures for each tabu search agent.

Neighborhoods

A candidate solution for GCP can be generated by changing the color class of vertices. Different modifications lead to different neighborhood structures. In this work, we explore 3 neighborhoods: the vertex neighborhood which changes the color of some conflicting vertices, the class neighborhood which changes the color of some or all vertices of a conflicting color class, and the non-increasing neighborhood which changes the color of some vertices without increasing the total number of conflicting edges.

Neighborhood exploration strategies

In MAOM-GCP, we use two complementary neighborhood strategies due to the cooperation act realized by each tabu search agent. One of these strategies, performed by our first tabu search agent, changes the colors of conflicting vertices to produce new k-colorings. This is done by moving a conflicting vertex x from its original color class V i to the best possible other color class V j (i = j) (this change or move is denoted by (x, i, j)). The new color class for each conflicting vertex x is chosen among those which are not assigned to vertices adjacent to x. Among these color classes found, the best possible color class (in terms of fitness minimization) is selected for the considered conflicting vertex.

Our second tabu search agent uses the same mechanism of selecting the best color class to be assigned to vertices as the first tabu search agent. The difference is that these vertices are not the set of conflicting vertices, but the vertices that are adjacent to conflicting vertices. The tabu search agent chooses the best color class for each vertex belonging to the set of adjacent vertices of conflicting vertices. The best color allocated must not belong to the color classes allocated to conflicting vertices.

For these two neighborhood strategies, tabu search agents evaluate each move using an incremental evaluation technique. This technique consists in maintaining a special data structure that records the move values for each candidate neighborhood move [START_REF] Dorne | Tabu Search for graph coloring, T-coloring and Set T-colorings[END_REF][START_REF] Fleurent | Genetic and hybrid algorithms for graph coloring[END_REF][START_REF] Galinier | Hybrid evolutionary algorithms for graph coloring[END_REF]. A ∆ matrix is used, in which element ∆(x, j) corresponds to the value gain of changing the current color of node x from color i to color j. Each element can be initialized in O(|V |) operations following this expression:

δ(x, j) = y∈x(I C j (y)-I C i (y)) (4.2)
where for x, N (x) = y ∈ V | (y, x) ∈ E , and I A is the indicator variable of set A, defined as:

I A (x)=
1, if x ∈ A 0, otherwise Based on expression 4.2, the ∆ matrix can be initialized. After that, it can be updated as we describe in Algorithm 4.2.

Tabu list

Each tabu search agent uses a tabu list to forbid the reverse moves. When a move (x,i,j) is generated, vertex x is forbidden to move back to color class V i for the next h iterations (called tabu tenure). The tabu tenure is dynamically determined by h = f (S)+r( 10), where r( 10) is a random number between 1 and 10 ( [START_REF] Galinier | Hybrid evolutionary algorithms for graph coloring[END_REF]. The stop condition of each tabu search is a fixed number of iterations.

Perturbation agent

The perturbation agent, triggered by tabu search agents, creates a disturbed kcoloring solution by exploring two types of perturbations. The new k-coloring is then sent to the tabu search agent for further improvement.

y ∈ N (x) do 2: if y / ∈ C i then 3: ∆(y, i) = ∆(y, i) -1 4: end if 5: if y / ∈ C j then 6:
∆(y, j) = ∆(y, j) + 1 7:

end if 8:

if y ∈ C j then 9:

for c = 1 to k do 10:

if c = j then 11: ∆(y, c) = ∆(y, c) -1 12: ∆(x, c) = ∆(x, c) -1 13:
end if 14:

end for 15:

end if 16:

if y ∈ C i then 17:

for c = 1 to k do 18: if c = i then 19: ∆(y, c) = ∆(y, c) + 1 20: ∆(x, c) = ∆(x, c) + 1 21: end if 22:
end for 23:

end if 24: end for

Reduced perturbation technique

The reduced perturbation technique can be triggered when a tabu search agent observes a slight search stagnation (condition C 2 of section 2.4.1). From the kcoloring received from the tabu search agent, the perturbation agent makes t moves to create a new solution, where each move changes randomly the color of a conflicting vertex of the incumbent solution. The number t of moves is chosen randomly between 1 and conf (where conf is the number of conflicting vertices).

Strong perturbation technique

The strong perturbation technique is performed when a tabu search agent observes deep search stagnation. The perturbation agent uses the shared archive of elite k-colorings to create a new solution. It extracts the number of occurrences of each vertex x colored by each color class V i . Starting with an uncolored graph, each vertex x is colored with a color class V i which has the smallest occurrence number. Dedicated data structures are employed to avoid the creation of the same solution for future calls to the perturbation agent.

Crossover agents

When the decision-maker agent decides to activate the crossover agents, two crossover agents are created based on two different crossover operators from the literature: the AMPaX operator [START_REF] Lu | A memetic algorithm for graph coloring[END_REF] and the GPX operator [START_REF] Galinier | Hybrid evolutionary algorithms for graph coloring[END_REF]. These operators are among the best crossover operators for GCP. The new k-coloring solutions are sent to the decision-maker agent to continue the search process. We will describe the two crossover operators used by these agents.

GPX operator

The GPX crossover [START_REF] Galinier | Hybrid evolutionary algorithms for graph coloring[END_REF] uses two random parent k-colorings S 1 and S 2 from the archive. In each step, the k classes V 1 , V 2 ,..., V k of the offspring k-coloring S 0 are created. At the first step, the class V 1 is built by selecting the class having the maximum number of vertices in parent S 1 . The second class V 2 of S 0 is built by the same idea but considering the second parent S 2 . Other color classes are built considering two parents S 1 and S 2 successively. Once k color classes are built, each left uncolored vertex is allocated to a random color.

AMPaX operator

The AMPaX operator [START_REF] Lu | A memetic algorithm for graph coloring[END_REF] is an extension of GPX operator. It uses randomly more than 2 parents from the archive to produce offspring. For each class color of the new offspring, the color classes of all parents are considered. In each step, the color class with the maximal cardinality in all m parents individuals, is chosen. Then, all vertices colored with this color class are removed from all m parents individuals. The current parent which has been selected, can be reconsidered only after a few number of steps. This mechanism is integrated to avoid focusing in a single parent, so creating other k-coloring solutions.

Experimentation

In this section, we present experimental results of our MAOM-GCP on wellknown DIMACS coloring benchmarks. Then, we compare the results with other state of the art coloring algorithms from the literature.

The DIMACS graphs are the recognized standard benchmarks in the literature for evaluating the performance of graph coloring algorithms [START_REF] Johnson | Cliques, coloring, and satisfiability: second DI-MACS implementation challenge[END_REF]. The DIMACS graphs are composed from 12 random graphs (DSJC125.x, DSJC250.x, DSJC500.x and DSJC1000.x, x = 1, 5 and 9), 6 flat graphs (flat300 x 0, x=20, 26 and 28; flat1000 x 0, x = 50, 60 and 76), 8 Leighton graphs (le450 15x, le450 25x, x = a, b, c and d), 12 random geometric graphs (R125.x, R250.x, DSJR500.x and R1000.x, x = 1, 1c and 5), 2 huge random graphs (C2000.5 and C4000.5), 2 class scheduling graphs (school1 and school1.nsh) and 1 latin square graph (latin square 10).

These instances can be classified into two categories: easy graphs and difficult graphs. Easy graphs can be solved very easily by most modern coloring heuristics. Difficult graphs can not be solved by all algorithms which can reach chromatic number or the best known results. We only mention our computational results on the set of difficult graphs. [START_REF] Galinier | Hybrid evolutionary algorithms for graph coloring[END_REF][START_REF] Galinier | An adaptive memory algorithm for the k-coloring problem[END_REF][START_REF] Malaguti | A metaheuristic approach for the vertex coloring problem[END_REF] 28 10/10 5 (Hertz & al., 2008;Porumbel al., 2009[START_REF] Porumbel | A Search Space "Cartography" for Guiding Graph Coloring Heuristics[END_REF]) [START_REF] Titiloye | Graph Coloring with a Distributed Hybrid Quantum Annealing Algorithm[END_REF]Wu & Hao, 2012) DSJC500.1 500 12,458 0.10 12 [START_REF] Blochliger | A graph coloring heuristic using partial solutions and a reactive tabu scheme[END_REF][START_REF] Galinier | An adaptive memory algorithm for the k-coloring problem[END_REF] 12 10/10 6 (Hertz & al., 2008;Porumbel al., 2009[START_REF] Porumbel | A Search Space "Cartography" for Guiding Graph Coloring Heuristics[END_REF]) [START_REF] Titiloye | Graph Coloring with a Distributed Hybrid Quantum Annealing Algorithm[END_REF]Wu & Hao, 2012) (Hao & Wu, 2012;[START_REF] Moalic | The new memetic algorithm HEAD for graph coloring: an easy way for managing diversity[END_REF] DSJC500.5 500 62,624 0.50 47 [START_REF] Moalic | The new memetic algorithm HEAD for graph coloring: an easy way for managing diversity[END_REF] ---48 [START_REF] Galinier | Hybrid evolutionary algorithms for graph coloring[END_REF][START_REF] Blochliger | A graph coloring heuristic using partial solutions and a reactive tabu scheme[END_REF] 48 10/10 85 [START_REF] Galinier | An adaptive memory algorithm for the k-coloring problem[END_REF]Hertz & al., 2008;[START_REF] Malaguti | A metaheuristic approach for the vertex coloring problem[END_REF]) [START_REF] Porumbel | A Search Space "Cartography" for Guiding Graph Coloring Heuristics[END_REF][START_REF] Titiloye | Graph Coloring with a Distributed Hybrid Quantum Annealing Algorithm[END_REF]) (Wu & Hao, 2012;Hao & Wu, 2012) DSJC500.9 500 112,437 0.90 126 [START_REF] Blochliger | A graph coloring heuristic using partial solutions and a reactive tabu scheme[END_REF][START_REF] Galinier | An adaptive memory algorithm for the k-coloring problem[END_REF]Hertz & al., 2008) 126 10/10 320 [START_REF] Malaguti | A metaheuristic approach for the vertex coloring problem[END_REF][START_REF] Porumbel | A Search Space "Cartography" for Guiding Graph Coloring Heuristics[END_REF]) [START_REF] Titiloye | Graph Coloring with a Distributed Hybrid Quantum Annealing Algorithm[END_REF]Wu & Hao, 2012) (Porumbel al., 2009;Hao & Wu, 2012;[START_REF] Moalic | The new memetic algorithm HEAD for graph coloring: an easy way for managing diversity[END_REF] DSJC1000.1 1000 49,629 0.10 20 [START_REF] Galinier | Hybrid evolutionary algorithms for graph coloring[END_REF][START_REF] Blochliger | A graph coloring heuristic using partial solutions and a reactive tabu scheme[END_REF][START_REF] Galinier | An adaptive memory algorithm for the k-coloring problem[END_REF] 20 10/10 441 (Hertz & al., 2008;[START_REF] Porumbel | A Search Space "Cartography" for Guiding Graph Coloring Heuristics[END_REF]) [START_REF] Titiloye | Graph Coloring with a Distributed Hybrid Quantum Annealing Algorithm[END_REF]Wu & Hao, 2012) [START_REF] Malaguti | A metaheuristic approach for the vertex coloring problem[END_REF]Hao & Wu, 2012;[START_REF] Moalic | The new memetic algorithm HEAD for graph coloring: an easy way for managing diversity[END_REF] DSJC1000.5 1000 249,826 0.5 82 [START_REF] Moalic | The new memetic algorithm HEAD for graph coloring: an easy way for managing diversity[END_REF] ---83 [START_REF] Galinier | Hybrid evolutionary algorithms for graph coloring[END_REF][START_REF] Malaguti | A metaheuristic approach for the vertex coloring problem[END_REF] 83 10/10 205 [START_REF] Porumbel | A Search Space "Cartography" for Guiding Graph Coloring Heuristics[END_REF]) (Wu & Hao, 2012;Hao & Wu, 2012) DSJC1000.9 1000 449,449 0.90 222 [START_REF] Galinier | Hybrid evolutionary algorithms for graph coloring[END_REF][START_REF] Blochliger | A graph coloring heuristic using partial solutions and a reactive tabu scheme[END_REF]Hertz & al., 2008) 222 4/10 801 [START_REF] Porumbel | A Search Space "Cartography" for Guiding Graph Coloring Heuristics[END_REF][START_REF] Titiloye | Graph Coloring with a Distributed Hybrid Quantum Annealing Algorithm[END_REF]) (Wu & Hao, 2012;Hao & Wu, 2012;[START_REF] Moalic | The new memetic algorithm HEAD for graph coloring: an easy way for managing diversity[END_REF] DSJR500.1c 500 121,275 0.97 85 (Hertz & al., 2008;[START_REF] Titiloye | Graph Coloring with a Distributed Hybrid Quantum Annealing Algorithm[END_REF] 85 10/10 60 (Wu & Hao, 2012) DSJR500.5 500 58,862 0.47 122 (Hertz & al., 2008;[START_REF] Prestwich | Coloration neighbourhood search with forward checking[END_REF] 122 3/10 480 [START_REF] Titiloye | Graph Coloring with a Distributed Hybrid Quantum Annealing Algorithm[END_REF]) (Wu & Hao, 2012;Hao & Wu, 2012) Table 4. 0.17 15 [START_REF] Galinier | An adaptive memory algorithm for the k-coloring problem[END_REF][START_REF] Malaguti | A metaheuristic approach for the vertex coloring problem[END_REF] 15 10/10 40 (Hertz & al., 2008;Porumbel al., 2009[START_REF] Porumbel | A Search Space "Cartography" for Guiding Graph Coloring Heuristics[END_REF]) [START_REF] Titiloye | Graph Coloring with a Distributed Hybrid Quantum Annealing Algorithm[END_REF]Wu & Hao, 2012) le450_15d 450 16,750 0.17 15 [START_REF] Galinier | An adaptive memory algorithm for the k-coloring problem[END_REF]Hertz & al., 2008;[START_REF] Malaguti | A metaheuristic approach for the vertex coloring problem[END_REF] 15 10/10 50 (Porumbel al., 2009[START_REF] Porumbel | A Search Space "Cartography" for Guiding Graph Coloring Heuristics[END_REF][START_REF] Titiloye | Graph Coloring with a Distributed Hybrid Quantum Annealing Algorithm[END_REF]) (Wu & Hao, 2012;Hao & Wu, 2012) le450_25c 450 17,343 0.17 25 [START_REF] Blochliger | A graph coloring heuristic using partial solutions and a reactive tabu scheme[END_REF][START_REF] Malaguti | A metaheuristic approach for the vertex coloring problem[END_REF] 25 10/10 120 (Porumbel al., 2009;[START_REF] Titiloye | Graph Coloring with a Distributed Hybrid Quantum Annealing Algorithm[END_REF]) (Wu & Hao, 2012;Hao & Wu, 2012) le450_ 25d 450 17,425 0.17 25 [START_REF] Blochliger | A graph coloring heuristic using partial solutions and a reactive tabu scheme[END_REF][START_REF] Malaguti | A metaheuristic approach for the vertex coloring problem[END_REF] 25 10/10 42 (Porumbel al., 2009;[START_REF] Titiloye | Graph Coloring with a Distributed Hybrid Quantum Annealing Algorithm[END_REF]) (Wu & Hao, 2012;Hao & Wu, 2012) flat300_26_0 300 21,633 0.48 26 [START_REF] Blochliger | A graph coloring heuristic using partial solutions and a reactive tabu scheme[END_REF][START_REF] Malaguti | A metaheuristic approach for the vertex coloring problem[END_REF] 26 10/10 40 [START_REF] Titiloye | Graph Coloring with a Distributed Hybrid Quantum Annealing Algorithm[END_REF]) (Wu & Hao, 2012;Hao & Wu, 2012) flat300_28_0 300 21,695 0.48 28 (Hertz & al., 2008;Wu & Hao, 2012;Hao & Wu, 2012) 30 5/10 500 flat1000_50_0 1000 245,000 0.49 50 [START_REF] Galinier | An adaptive memory algorithm for the k-coloring problem[END_REF]Hertz & al., 2008;[START_REF] Malaguti | A metaheuristic approach for the vertex coloring problem[END_REF] 50 10/10 40 (Porumbel al., 2009[START_REF] Porumbel | A Search Space "Cartography" for Guiding Graph Coloring Heuristics[END_REF][START_REF] Titiloye | Graph Coloring with a Distributed Hybrid Quantum Annealing Algorithm[END_REF]) (Wu & Hao, 2012;Hao & Wu, 2012) flat1000_60_0 1000 245,830 0.49 60 [START_REF] Galinier | An adaptive memory algorithm for the k-coloring problem[END_REF]Hertz & al., 2008;[START_REF] Malaguti | A metaheuristic approach for the vertex coloring problem[END_REF] 60 10/10 45 (Porumbel al., 2009[START_REF] Porumbel | A Search Space "Cartography" for Guiding Graph Coloring Heuristics[END_REF][START_REF] Titiloye | Graph Coloring with a Distributed Hybrid Quantum Annealing Algorithm[END_REF]) (Wu & Hao, 2012;Hao & Wu, 2012) flat1000_76_0 1000 246,708 0.49 81 (Hao & Wu, 2012;[START_REF] Moalic | The new memetic algorithm HEAD for graph coloring: an easy way for managing diversity[END_REF] ---82 [START_REF] Malaguti | A metaheuristic approach for the vertex coloring problem[END_REF]Porumbel al., 2009) Our MAOM-GCP was implemented in Java using the multi-agent platform Jade. The program was run on a computer with a Core I5 2.5 GHz, 8GB of RAM.

Each instance was solved 10 times independently (5 times for very large graphs). We stopped the algorithm when a legal k-coloring is found or the fixed execution timeout is reached. For all instances, a timeout limit of 240 CPU hours was used except for the large graph C2000.5 where a limit of 500 CPU hours (note that large computing times are usually allowed in the literature on GCP). We adjusted the parameters of the proposed algorithms by an experimental study. The number of iterations for each tabu search agent (iter_max) was fixed to 1000. The parameters max_opt (for decision-maker agent) and max_opt_T S (for tabu search agent), that evaluate the improvement of solutions between generations, were fixed to 20 and 2 for respectively. For interval, we considered the same value 10 for the same agents. The rate µ used in updating the decision matrices was fixed to 0.9.

Table 4.1 and Table 4.2 summarize the computational results of our MAOM-GCP. Columns 2-4 show the features of the tested instances: the number of vertices (n), the number of edges (ne) and the density of the graph (dens). Columns 5 and 6 correspond to the best known results k * ever reported in the literature and the corresponding references. The remaining columns give the computational results of our MAOM-GCP: the smallest number of colors needed to obtain a legal k-coloring, the success rate (#hit) and the average time for reaching the best legal k-coloring (time in minutes).

Table 4.1 and Table 4.2 show that the results obtained by our MAOM-GCP are competitive with respect to many state of the art algorithms in terms of solution quality (i.e., the number of colors used). It can reach previous best known results except for 7 very difficult cases (DSJC500.5, DSJC1000.5, flat300_28_0, flat1000_76_0, latin_sqr_10, C2000.5 and R1000.5) for which very few algorithms are able to attain the best known results. For these 7 instances, MAOM-GCP the deviation between our results and the best-known results is respectively 0.021 (DSJC500.5), 0.012 (DSJC1000.5), 0.034 (flat300_28_0), 0.012 (flat1000_76_0), 0.002 (R1000.5), 0.013 (C2000.5) and 0.01 (latin_sqr_10) respectively.

Conclusion

In this section, we presented a multi-agent based optimization algorithm for the Graph Coloring Problem. MAOM-GCP is based on distributed programming realized by multi-agent system which is reinforced by a technique of learning, in order to manage the search to the right decision. In fact, a decision-maker agent decides if the search process needs to be intensified or diversified based on a decision matrix, so two different types of agents are trigged. Tabu search agents, responsible for intensification search, explore two different neighbor structures, and apply a tabu search algorithm to generate progressively a legal k-coloring.

These last agents can get helps from other agents, when the solution can not be further improved. It is the perturbation agent which applies a reduced perturbation move or a strong perturbation move, in order to create another depart solution for tabu search agents. Crossover agents are trigged, to escape deep local optima, by

A Multi-Agent based Optimization Method for the Winner Determination Problem

In this chapter, we present another application of the proposed method to the Winner Determination Problem (WDP) in combinatorial auctions. In the next section, we will describe the problem. In section 5.2, we will give an overview of algorithms for the WDP. Then, we will apply the proposed method to the WDP. Section 5.4 will contain the experimentations of MAOM-WDP using the WDP benchmarks. In the appendix of this chapter, we will present another algorithm for the WDP. It is a Recombination-Based Tabu Search Algorithm for the WDP (TSX_WDP). TSX_WDP will be evaluated using the same benchmarks. TSX_WDP is presented in [START_REF] Sghir | A Recombination-Based Tabu Search Algorithm for the Winner Determination Problem[END_REF].

Problem definition

The auction consists of an auctioneer wishing to maximize his/her selling revenue and a set of bidders wishing to minimize their cost. Examples of the most widely known auctions are the English auction, the Holland's auction, the Sealed envelope auction and the Vickrey auction [START_REF] Klemperer | Auctions: Theory and Practice Princeton[END_REF]. These auctions typically treat only a single item for each sell. Combinatorial auctions are multi-item auctions, which allow bids on a combination of items [START_REF] Cramton | Combinatorial auctions[END_REF][START_REF] Jawad | Combinatorial auctions[END_REF].

In combinatorial auctions, we have a set of items which are exposed to buyers. Buyers offer different bids. Each bid is defined by a subset of items with a price. Two bids are conflicting, if they share at least one item. The Winner Determination Problem (WDP) is to determine a conflict-free allocation of items that maximizes the auctioneer's revenue defined as the sum of the valuations of the winning bids. The WDP is known to be a NP-hard combinatorial optimization problem with a number of practical applications like the e-commerce, the games theory and the resources allocation in multi-agent systems [START_REF] Vries De | Combinatorial auctions a survey[END_REF][START_REF] Jawad | Combinatorial auctions[END_REF].

Formally, given a set of m items M = {1, 2, ..., m} to sell and a set of n bids N = {1, 2, ...n}. Each bid j is a tuple < S j , P j > where S j is a subset of items covered by bid j, and P j is the price of bid j. Let B be a m × n binary matrix such that B ij = 1 if object i ∈ S j , B ij = 0 otherwise. Furthermore, we define the decision variable x j for each bid j such that x j = 1, if bid j is a winning bid, 0 otherwise. Formally, the WDP can be stated as the following binary integer optimization problem.

M aximize f (x) = j∈N P j x j (5.1) subject to j∈N B ij x j ≤ 1, i ∈ M (5.2)
The objective function (5.1) is to maximize the auctioneer's gain calculated by the sum of prices of the winning bids, while the constraints expressed by formula (5.2) ensure that an item appears at most in one winning bid. We present a simple example to understand better the notations used in the modeling of the WDP. Let us consider a set of five items 1, 2, 3, 4, 5 to sell by auction and four bids. Each bid is represented by a couple < S j , P j > where P j indicates the price of bid j containing a set of items S j . The following bids are:

-Bid1: (1, 2), 250 -Bid2: (1, 2, 3), 400 -Bid3: (3, 4, 5), 500 -Bid4: (4, 5), 200 Bid1 contains a set of two items (1, 2) which the price is 250. Bid3 has as price 500 for the set of three items (3, 4, 5). Bid1 and Bid3 can constitute a winning allocation maximizing the gain of the seller. The total price of the sale is 750.

State of the art approaches for the WDP

Several algorithms were proposed to solve the winner determination problem. These algorithms can be divided into two categories: the exact algorithms and the stochastic algorithms. For the exact algorithms, we can quote: Branch-on-Items (BoI), Branch-on-Bids (BoB) [START_REF] Sandholm | Improved optimal algorithm for combinatorial auctions and genericizations[END_REF], CABoB [START_REF] Sandholm | CABoB: a fast optimal algorithm for combinatorial auctions[END_REF], Combinatorial Auction Structural Search (CASS) [START_REF] Fujishima | Taming the computational complexity of combinatorial auctions: optimal and approximate approaches[END_REF], Combinatorial Auctions Multi-unites Search (CAMUS) (Leyton-Brow & al., 2000). In [START_REF] Rothkopf | Computationally manageable combinatorial auctions[END_REF], an algorithm of dynamic programming for the WDP was introduced. Nisan [START_REF] Nisan | Bidding and allocation in combinatorial auctions[END_REF] proposed a linear programming algorithm for the WDP. Holland and Sullivan [START_REF] Holland | Towards fast vickrey pricing using constraint programming[END_REF] used the constraints programming to solve a particular combinatorial of Vickrey auction. Some stochastic algorithms were proposed for the WDP. Casanova [START_REF] Hoos | Solving combinatorial using stochastic local search[END_REF] is a local search algorithm proposed by Hoos and Boutilier. Casanova begins with an empty allocation where all bids are considered unsatisfied. In each iteration, an unsatisfied bid is selected to be added in the allocation. Any incompatible bid, which can occur in the current allocation, is removed, when new bids are added. The selection of a bid is based on the following strategies:

-With a probability w p (Walk probability), an unsatisfied bid is randomly selected. -With a probability 1-w p , unsatisfied bids are classified according to their profit. The profit is the price of a bid divided by the number of items covered by this bid. Then, with a probability n p (Novelty probability), the best unsatisfied bid, which has the biggest profit value, is selected to be added in the current allocation. Otherwise, with a probability 1-n p , the best second unsatisfied bid is chosen. In [START_REF] Guo | Heuristics for a bidding problem[END_REF], Guo et al. proposed the SAGII algorithm which is a simulated annealing combined with the Branch-and-Bound algorithm for the WDP. SAGII begins with a preprocessing to exclude the bids which can lead to the optimal solutions. The search process is composed of three components:

-A branch-and-Bound algorithm applied to the items subsets of the current allocation; -A simulated annealing algorithm used to select the best unsatisfied bid to be added in the current allocation; -A random movement performed to select randomly an unsatisfied bid to be considered in the current allocation.

SAGII starts from an empty allocation. A penalty function is used to eliminate the incompatible bids. The Branch-and-Bound algorithm is executed with a probability p 1 = 0.2. The simulated annealing algorithm is performed with a probability p 2 = 0.7. The random movement is applied with a probability 1p 1p 2 .

The local search (SLS) proposed by [START_REF] Boughaci | A memetic algorithm for the optimal winner determination problem[END_REF] starts with a possible initial allocation and tries to improve it, by searching for a better solution in the current neighborhood. A Random Key Encoding (RK) is used to generate the initial solution [START_REF] Bean | Genetics and random keys for sequencing and optimization[END_REF]. Then, in each iteration, an unsatisfied bid is selected to be integrated into the current allocation. Any contradictory bid, in the current allocation, is removed. Two criteria are fixed for the bid selection. The first criterion consists in choosing an unsatisfied bid in a random way with a fixed probability w p . The second criterion consists in choosing, with a probability 1-w p , the best unsatisfied bid that maximizes the gain of the seller.

The tabu search (TS) elaborated by [START_REF] Boughaci | A memetic algorithm for the optimal winner determination problem[END_REF] begins with the RK algorithm [START_REF] Bean | Genetics and random keys for sequencing and optimization[END_REF] to generate the initial solution. The best neighbor is selected for the next solution. To produce neighbor solutions, TS performs two moves which are built in the following way:

-the best unsatisfied bid, which maximizes the total profit of the current allocation, when it will be inserted, is selected. All incompatible bids, in the current allocation, are removed; -the search space is composed of the items which are not covered by the bids in the current allocation. The best bid covering such items is chosen. All incompatible bids in the current allocation are removed; After generating all neighbor configurations, the best configuration is selected to be a candidate solution. To escape the visited allocations, a list maintains the bids recently selected.

The memetic algorithm (MA) proposed by [START_REF] Boughaci | Local Search Methods for the Optimal Winner Determination Problem in Combinatorial Auctions[END_REF] starts by the RK algorithm. Then, it selects C individuals from the current population P to participate in the reproduction phase. C contains the best individuals C 1 , which have the highest fitness, and the diverse individuals C 2 , which are the individuals the most diverse in the population P . The diversity is measured using a similarity function which calculates the number of the common bids between two individuals. Two parents are selected randomly from C. They are combined to generate a new individual. To locate more effectively solutions, the mutation phase is replaced by a stochastic local search (SLS). The population is updated with the new individual based on the quality and the diversity criteria.

In [START_REF] Wu | Solving the winner determination problem via a weighted maximum clique heuristic[END_REF], Wu and Hao developed an algorithm for the WDP by recasting the WDP into the maximum weight clique problem (MWCP). They solve the transformed problem using a recent heuristic dedicated to the MWCP. A memetic algorithm (MA) was proposed. The proposed algorithm incorporated a novel selection strategy and a specific crossover operator. The stochastic local search (SLS) was used for the intensification search.

We explore the operators and the techniques used in these reference algorithms in our multi-agent model, in order to create the first multi-agent based optimization algorithm solving the WDP. In the next section, we will present the components of the proposed algorithm.

A Multi-agent based optimization method for the WDP (MAOM-WDP)

In this section, we apply our multi-agent approach to the Winner Determination Problem (MAOM-WDP). We use the following agents: the decision-maker agent, two tabu search agents which are the intensification agents, the perturbation agent and two crossover agents. Below, we describe the behaviors of these agents.

Decision-maker agent

The decision-maker agent generates a simple non conflicting allocation by selecting random items. The decision-maker agent uses a decision matrix (section 2.2.1) which helps it to decide which agents to activate between crossover agents and tabu search agents. It maintains all high-quality solutions, received from other agents, in a shared memory.

Tabu search agents

Two tabu search agents are responsible for the intensification search of MAOM-WDP. During their search, these agents can exchange with another alive tabu search agent or with a perturbation agent based on their decision matrices (section 2.2.1) and according to the corresponding condition (section 2.5.1). They send the best allocation found to the decision-maker agent. Below, we define the used neighborhood strategies for each tabu search agent.

Neighborhood exploration strategies

A candidate solution is represented by an allocation A (a dynamic vector). Each element of this allocation A receives the winning bid. Each bid is an object composed of the list of items and the associated prices. The first tabu search agent explores the neighborhood strategy proposed by [START_REF] Boughaci | A memetic algorithm for the optimal winner determination problem[END_REF]) (section 5.2).

The second tabu search agent performs the following neighborhood strategy:

-The initial candidate (unsatisfied) bids are sorted according to their utility prices; -For each candidate bid B x , a binary gain function is used to verify if the bid can increase the revenue of the current allocation when the bid is inserted; -Let Q be the set of winning bids that are in conflict with the current candidate bid B x , Let f (Q) be the revenue of the set of winning bids Q, and f (B x ) the price of the candidate bid B x . The gain function returns true if f (Q) < f (B x ) and returns false otherwise;

-According to this expression, a candidate bid B x can enter in the current allocation only if its price f (B x ) is higher than the revenue of other winning bids which are conflicting with B x in the current allocation (i.e., the gain function is true); -The gain of B x , when it is selected to be added in the current allocation, is calculated according to the following function:

Gain(B x ) = f (A) -f (Q) + f (B x ) (5.3)
-When a bid B x is inserted in the current allocation A, the bids of Q which are conflicting with B x are removed from A; -The steps mentioned previously are iterated until all the initial candidate bids are visited and possibly added in the current allocation A.

The tabu list and the tabu tenure management

The tabu search agents use a tabu list to forbid recently visited solutions from being revisited. A bid that is chosen to be inserted in the current allocation A is forbidden to be removed for the next tt iterations. This number of iterations, named the tabu tenure, is calculated dynamically by the function:

tt = L + ⋋ + f (A)
where L is randomly chosen from the interval [0, 9] and ⋋ is empirically fixed to 0.6. Notice that we allow a move to be accepted in spite of being tabu if the move leads to a solution better than any found so far. This is called the aspiration criterion.

Perturbation agent

The perturbation agent is activated by a tabu search agent when it needs diversification search under specific conditions (C 2 and C 3 of section 2.5.1). This agent creates a new perturbed solution that manages the search towards other regions. It performs two parallel behaviors which are reduced perturbation behavior and strong perturbation behavior. The resulting solution is sent to the tabu search agent.

Reduced perturbation technique

The reduced perturbation technique is activated when the tabu search agent observes a slight search stagnation (condition C 2 of section 2.5.1). The perturbation agent chooses randomly one candidate unsatisfied bid from the available ones. Then, the selected bid is inserted in the allocation received from the tabu search agent. All the contradictory bids are removed from this allocation.

Strong perturbation technique

The strong perturbation technique is applied, when the tabu search agent observes a strong search stagnation. Based on the archive of elite solutions, the perturbation agent extracts the number of occurrences of each bid appeared in the highquality allocations. Then, the bids, which have the smallest occurrence number, are inserted in the current non conflicting allocation. In order to create a new solution in each call of the perturbation agent, data structures are employed to save the visited solutions.

Crossover agents

Two crossover agents are activated, when the decision-maker agent observes a local optimum reached based on its decision matrix. These two agents apply crossover operations to produce new offspring allocations. The first crossover agent explores the crossover operator which was proposed by [START_REF] Boughaci | Local Search Methods for the Optimal Winner Determination Problem in Combinatorial Auctions[END_REF]) (section 5.2). The second crossover agent employs the recombination operator which is described below.

This operator aims to transform the good properties of the parents towards the offspring. These criteria have to assure that the offspring inherits the properties of the parents. The pseudo-code of the recombination operator is given in Algorithm 5.1. Given two parent allocations I 1 and I 2 from the common archive, these parents share the highest number of bids. The second crossover agent constructs the offspring I 0 in k steps until all the bids of the two parents are visited. This operator is inspired by the idea of backbone used in [START_REF] Benlic | A multilevel memetic approach for improving graph k-partitions[END_REF][START_REF] Wang | Backbone guided tabu search for solving the UBQP problem[END_REF]. In the first step, the set of bids, that are shared by the parents, are identified and directly transmitted to I 0 . Then the following steps are performed:

-Choose the bid with the lowest price from each parent (lines 4 and 5 from Algorithm 5.1); -The two selected bids are candidates bids that can be inserted in the offspring, if they are not conflicting bids. This is by conserving, the best bids, which have the highest revenue (lines 6 and 7 from Algorithm 5.1); -Remove the selected bids from their parents, even if they are not inserted in the offspring (lines 9 and 10 from Algorithm 5.1); -Repeat the previous steps until all the bids of the parents are examined and removed. An example of this recombination operator is provided in Figure . 5.1. The two allocations, generated by the crossover agents, are sent to the decisionmaker agent. They will be the new current allocation for the search process.

Experimentations of MAOM-WDP

We present in this section experimental results of MAOM-WDP on the set of well-known WDP benchmarks. MAOM-WDP was implemented in Java using the platform Jade. The program was run on a computer with a Core I5 2.5GHz, 8GB of RAM. Tests were made on various benchmarks of diverse sizes defined in [START_REF] Lau | An intelligent brokering system to support multiagent web-based for thparty logistics[END_REF]. These benchmarks take into account several factors like the prices, bidders preferences and object distribution on bids. They can be divided into five groups where each group contains 100 instances:

-REL 500-1000: From in101 to in200: m = 500, n = 1000 -REL 1000-1000: From in201 to in300: m = 1000, n = 1000 -REL 1000-500: From in401 to in 500: m = 1000, n = 500

Algorithm 5.1. The recombination operator of the second crossover agent Require: two parent solutions I 1 and I 2 Ensure: An offspring solution I 0 1:

I 0 ← ∅, D 1 ← ∅, D 2 ← ∅ 2:
Sort the bids in each parent according to their prices 3: while I 1 and I 2 are not empty do 4:

D 1 ← f irst_element(I 1 ) 5: D 2 ← f irst_element(I 2 ) 6:
if D 1 and/or D 2 are no conflict bids with the bids in I 0 then We adjusted the parameters of MAOM-WDP by an experimental study. The number of iterations for each tabu search agent (iter_max) was fixed to 500. The parameters max_opt (for decision-maker agent) and max_opt_T S (for tabu search agents), which evaluate the improvement of solutions between generations, were fixed to 20 and 25 respectively. As interval, we considered the same value 1000 for the same agents. The rate µ used in updating the decision matrices was fixed to 0.9.

Experimental results

In Tables 5.1, 5. 2, 5.3, 5.4, and 5.5, we provide the computational results of MAOM-WDP on the set of the five groups of benchmarks. Given that there are 500 instances, we show only some results of each group, like in some recent papers [START_REF] Boughaci | Local Search Methods for the Optimal Winner Determination Problem in Combinatorial Auctions[END_REF]. Columns give the following computational statistics of each tested instance: the maximumrevenue obtained by the MAOM-WDP algorithm over the 10 independent trials Rbest, the averagerevenue over the 10 trials Ravg, the worstrevenue over the 10 trials Rworst and the average CPU time in seconds AvgT ime. These tables show that the values of Ravg are equal to the values of Rbest in all instances. In this section, we show the comparative study of MAOM-WDP with other algorithms from the literature: Casanova [START_REF] Hoos | Solving combinatorial using stochastic local search[END_REF], SAGII [START_REF] Guo | Heuristics for a bidding problem[END_REF], SLS [START_REF] Boughaci | A memetic algorithm for the optimal winner determination problem[END_REF], TS [START_REF] Boughaci | A memetic algorithm for the optimal winner determination problem[END_REF], MA [START_REF] Boughaci | Local Search Methods for the Optimal Winner Determination Problem in Combinatorial Auctions[END_REF], MN/TS [START_REF] Wu | Solving the winner determination problem via a weighted maximum clique heuristic[END_REF].

In Table 5.6, we present the generic comparative results for each group. In this table, rows µ correspond to the average of best objective value of the 100 instances in each group. Rows time represent the average time to reach the best solution. δ(%) is the deviation of the MAOM-WDP algorithm with respect to each reference algorithm. The deviations are calculated respectively as follows: µ M AOM -W DPµ algo_X )/µ M AOM -W DP where algo_X is one of the five reference algorithms. Since the compared algorithms are implemented in different languages and run in different computer, the comparison is focused on solution quality that can be reached by each algorithm. The computing time is provided only for indicative purposes. The results of the reference algorithms are extracted from the corresponding papers except the results of Casanova are given by [START_REF] Guo | Heuristics for a bidding problem[END_REF].

Table 5.6 shows that MAOM-WDP gives an improvement between 32% and 48% in solution quality compared to Casanova in shorter time. MAOM-WDP outperforms TS (the improvement rate is between 4% and 11%), SLS (the improvement rate is between 4% and 10%), MA (the improvement rate is between 2% and 9% ). The results of MAOM-WDP are close to the results of MN/TS. The deviation is between -2% and 0 %.

Conclusion

In this chapter, we proposed a multi-agent based optimization algorithm for the winner determination problem. The proposed algorithm combines different techniques of diversification and techniques of intensification. The tabu search agents are responsible for the intensification search. One of these tabu search agent explores new neighborhood strategy for the WDP. The new strategy of the selection of the best neighbor helps the algorithm to maintain, a diversification of the population what leads to a good compromise between the intensification and the diversification. The use and the update of the tabu tenure, in each iteration of the algorithm, improve the diversification in order to discover other areas in the search space.

The crossover agents employ crossover operators as another tool for the diversification of the search space. One of these agent explores a new technique of crossover for the WDP, that gives the priority to the invariants bids to stay in the new descendant. Then, this agent adds the conflict-free bids from the two parents selected according to their prices. The new crossover strategy aims to take the good information of the parents, then try to find other different efficient solutions. The new descendant solution can change the direction of the search because it is the new starting point for other iterations of the tabu search. The proposed MAOM-WDP is evaluated on a set of 500 benchmark instances. The comparative study with reference algorithms shows that it is able to reach solution of very high quality. Another centralized algorithm, named TSX_WDP, is presented in the appendix of this chapter.

5.A Appendix: A Recombination-based Tabu Search algorithm for the WDP (TSX_WDP)

We propose a dedicated tabu search algorithm (TSX_WDP) for the Winner Determination Problem (WDP) in combinatorial auctions. TSX_WDP integrates two complementary neighborhoods designed respectively for the purpose of intensification and diversification. To escape deep local optima, TSX_WDP employs a backbone-based recombination operator to generate new starting points for tabu search and to displace the search into unexplored promising regions. The recombination operator operates on elite solutions previously found which are recorded in a global archive. In this section, we present these key components. Then, the performance of the proposed algorithm is assessed on a set of 500 well-known WDP benchmark instances. Comparisons with state of the art algorithms demonstrate the effectiveness of TSX_WDP.

5.A.1 TSX_WDP algorithm

The generic TSX_WDP algorithm is formalized in Algorithm 5.2. The algorithm starts with an empty allocation in which no bd is chosen and tries to improve it, by looking for a better solution in the current neighborhood. In each iteration, the best authorized bids are selected among the candidate bids to be included in the current allocation. This is achieved with an intensification move (lines 7-9 of Algorithm 5.2). This intensification move is the neighborhood strategy performed by the second tabu search agent of MAOM-WDP and developed in section 5.3.2.1. When no bit can be found to increase the revenue with the intensification move, TSX_WDP switches to the perturbation move by choosing a random bid from the candidate bids (line 11 of Algorithm 5.2). In both cases, the choice of the bids depends on a status of the tabu list which is updated after each move. Any conflicting bid, being able to occur in the current allocation, when new bids are considered, is removed (lines 13 and 14 of Algorithm 5.2).

The search process is repeated for a fixed number Itermax of iterations. During these Itermax iterations, if the current best solution can not be updated for consecutive p (fixed experimentally) moves, the best local optimum found so far is inserted into the archive P and a recombination operator (Algorithm 5.1 & section 5.3.4) is activated to generate a new starting point for a new round of the tabu search procedure (lines 20-25 of Algorithm 5.2). The tabu search steps starts again with the new offspring. The best solution is the best revenue found during these iterations.

5.A.2 Experimentations of TSX_WDP

This section gives experimental results of TSX_WDP which was implemented in Java. The program was run on a computer with a Core I5 2.5GHz, 8GB of RAM. We adjusted the parameters of the proposed algorithms by an experimental study: The maximum number of iterations (itermax) was fixed to 200 and the parameter Algorithm 5.2. TSX_WDP for the Winner Determination Problem Require: A matrix M , a parameter Itermax, Vector of bids B, Parameter p Ensure: a vector of winning bids A * and its revenue f (A * ) 1: Iter ← 0 {Iteration counter}, Initiate tabu_list 2: A * ← A ← ∅ 3: opt ← 0 {An integer that will be incremented if the current solution doesn't improve in two consecutive iterations opt returns to 0, when it exceeds the value p, after activating the recombination operator} 4: initialize tabu_list 5: P ← ∅ {An archive of the best local optima encountered A * } 6: while (Iter < Itermax) do Iter ← Iter + 1 28: end while 29: Return (A * and f (A * )) In order to further show the effectiveness of the algorithm, we present a comparative study with six state of the art algorithms from the literature: Casanova [START_REF] Hoos | Solving combinatorial using stochastic local search[END_REF], SAGII [START_REF] Guo | Heuristics for a bidding problem[END_REF], SLS [START_REF] Boughaci | A memetic algorithm for the optimal winner determination problem[END_REF], TS [START_REF] Boughaci | A memetic algorithm for the optimal winner determination problem[END_REF], MA [START_REF] Boughaci | Local Search Methods for the Optimal Winner Determination Problem in Combinatorial Auctions[END_REF] and MN/TS [START_REF] Wu | Solving the winner determination problem via a weighted maximum clique heuristic[END_REF].

In Table 5.12, we show the generic comparative results for each group. Table 5.12 discloses that TSX_WDP gives an improvement between 31% and 47% in solution quality compared to Casanova. The TSX_WDP algorithm finds better solutions in shorter time, than Casanova. In addition, it shows good performances of the TSX_WDP algorithm in solving the WDP compared to SLS. The improvement rate is between 4% and 8%. The results of TSX_WDP is better than TS in quality and in time (the improvement rate is between 4% and 9%). TSX_WDP outperforms MA. The deviation is between 2% and 7%. Finally, TSX_WDP produces better results than SAGII which is based on sophisticated Branch-and-Bound and preprocessing tools (The deviation is between 1% and 7%). Compared to MN/TS algorithm, which is the most successful algorithm, the deviation is between -5% and -0.5 %. Thus, we can conclude that the TSX_WDP algorithm discovers good results for the five groups of benchmarks. This chapter shows another application of the proposed method to the Multidimensional knapsack problem (MKP). In the first section, we will present this problem. Then, we will give a brief overview of algorithms for the MKP. Section 6.3 will describe the behaviors of the agents of MAOM-MKP. In section 6.4, MAOM-MKP will be tested using the OR-library benchmarks, then, it will be compared to the current state of the art approaches.

Problem definition

The Multidimensional Knapsack Problem (MKP) consists in selecting a subset of objects (or items), in order to maximize their total profit. The selected objects 93 must not violate a set of knapsack constraints. The Multidimensional Knapsack Problem (MKP) can be formulated as:

M aximize f (x) = n j=1 p j x j (6.1) subject to n j=1 r ij x j ≤ b i (6.2) x j ∈ {0, 1} (6.3)
where i = {1, ...., m} and j = {1, ...., n} According to these expressions, the decision variables x j = 1, if the object j is selected, 0 otherwise. p j is the profit associated to j. Each of the m constraints is called a knapsack constraint. A set of n objects with profit p j > 0 and a set of m resources are given. Each object j consumes an amount r ij ≥ 0 from each resource i. When m = 1, the MKP degenerates to the knapsack problem. It can be solved in pseudo-polynomial time. However, when m > 1, it becomes a strongly NP-hard problem and exact techniques can only be used to solve small instances sizes.

The MKP can formulate many real-world application like capital budgeting problem [START_REF] Markowitz | On the solution of discrete programming problems[END_REF], allocating processors and databases in a distributed computer system problem [START_REF] Gavish | Allocation of databases and processors in a distributed computing system[END_REF], cutting stock problem [START_REF] Gilmore | The theory and computation of knapsack functions[END_REF] and project selection and cargo loading problem [START_REF] Shih | A Branch and Bound Method for the Multiconstraint Zero-One Knapsack Problem[END_REF]. The MKP can be considered as a generic 0-1 integer programming problem with non-negative coefficients.

State of the art approaches for the MKP

We give a brief overview of some of the most representative algorithms for the MKP. The best algorithms will be used to evaluate the proposed algorithm. Exact algorithms and metaheuristic have been developed for the MKP. On the one hand, the branch and bound algorithms [START_REF] Shih | A Branch and Bound Method for the Multiconstraint Zero-One Knapsack Problem[END_REF] were proposed as exact algorithms. For instance, Gavish and Pirkul [START_REF] Gavish | Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality[END_REF] proposed a branch and bound algorithm with tighter upper bounds, combined with relaxation techniques.

On the other hand, several metaheuristics have appeared in the literature. A simulated annealing, based on the add-interchange-drop technique for handling the constraints, was presented by Drexl [START_REF] Drexl | A simulated annealing approach to the multiconstraint zeroâone knapsack problem[END_REF].

Hanafi and Fréville [START_REF] Hanafi | An efficient tabu search approach for the 0â1 multidimensional knapsack problem[END_REF]) elaborated a tabu search algorithm using the surrogate constraints information. A genetic algorithm is proposed by [START_REF] Chu | A genetic algorithm for the multidimensional knapsack problem[END_REF]. [START_REF] Vasquez | A hybrid approach for the 0-1 multidimensional knapsack problem[END_REF] presented a hybrid approach combining the linear programming and the tabu search. This algorithm integrates the drop-add repair operator based on the pseudoutility ratios to generate feasible solutions. [START_REF] Sakawa | Genetic algorithms with double strings for 0â1 programming problems[END_REF] proposed a genetic algorithm with double strings based on a decoding algorithm. [START_REF] Vasquez | Improved results on the 0â1 multidimensional knapsack problem[END_REF] proposed a hybrid method combining the linear programming with an efficient tabu search. Puchinger et al. (Puchinger & al., 2005) presented a cooperative combination of a memetic algorithm and a branch-and-cut algorithm. These algorithms run in parallel and asynchronous way by exchanging information during the optimization process.

Li et al. [START_REF] Li | Genetic algorithm based on the orthogonal design for multidimensional knapsack problems[END_REF]) elaborated a genetic algorithm based on the orthogonal design. A scatter search method was applied in [START_REF] Hanafi | Scatter search for the 0-1 multidimensional knapsack problem[END_REF] for the MKP. [START_REF] Kong | A new ant colony optimization algorithm for the multidimensional knapsack problem[END_REF] presented a binary ant system (BAS) algorithm based on the drop-add repair operator. In [START_REF] Boyer | Heuristics for the 0-1 multidimensional knapsack problem[END_REF], two heuristics were provided. The first one uses surrogate relaxation, and the relaxed problem is solved via a modified dynamic programming algorithm. The second one combines a limited-branch-and-cut procedure with the previous heuristic, and tries to improve the bound obtained by exploring some nodes that have been rejected by the modified dynamic programming algorithm.

Zou et al. [START_REF] Zou | Solving 0-1 knapsack problem by a novel global harmony search algorithm[END_REF] employed a novel global harmony search algorithm to solve MKP. [START_REF] Bonyadi | A new discrete electromagnetism-based metaheuristic for solving the multidimensional knapsack problem using genetic operators[END_REF] proposed a discrete electromagnetism-like mechanism (DEM) which integrates the drop-add repair operator. Langeveld and Engelbrechta [START_REF] Langeveld | Set-based particle swarm optimization applied to the multidimensional knapsack problem[END_REF]) elaborated a set-based particle swarm optimization (SBPSO) algorithm based on the penalty function method to handle the constraints. An ant colony optimization algorithm for binary knapsack problem under fuzziness was proposed by [START_REF] Changdar | An Ant colony optimization approach for binary knapsack problem under fuzziness[END_REF]. A simplified binary version of the artificial fish swarm algorithm applied to the MKP was provided in [START_REF] Kalam Azad | Solving Large 0-1 Multidimensional Knapsack Problems by a New Simplified Binary Artificial Fish Swarm Algorithm[END_REF]. We can find an interesting review of approaches for the MKP in [START_REF] Fréville | The multidimensional 0â1 knapsack problem: an overview[END_REF].

Based on this review, we elaborate the first multi-agent algorithm for the MKP (MAOM-MKP). MAOM-MKP, which is presented in the next section, combines several techniques and operators from existing algorithms for the MKP in an intelligent way using multi-agent system and reinforcement learning.

A multi-agent based optimization method for the MKP (MAOM-MKP)

This section describes the multi-agent based optimization algorithm for the MKP (MAOM-MKP). The agents are the decision-maker agent, two tabu search agents, the perturbation agent and two crossover agents. We explain the specific characteristics of the proposed method to be applied to the MKP.

Decision-maker agent

In MAOM-MKP, the selection of agents to activate, is handled by the decisionmaker agent using its decision matrix (section 2.2.1) under a specific condition (section 2.4.1). The decision-maker agent starts the optimization process by generating an initial solution. This initial solution is a simple feasible configuration which contains random non conflicting objects. This solution is sent to the appropriate agents. Then, when other agents are activated, decision-maker agent waits high-quality so-lutions received from tabu search agents or crossover agents. Decision-maker agent maintains these solutions in the shared memory. (Algorithm 2.2)

Tabu search agents

Tabu search agents apply tabu search algorithm with two different neighborhood strategies (Algorithm 2.3). During their optimization process, they can exchange information with another alive tabu search agent or with the perturbation agent. The triggered agent depends on their decision matrices (section 2.2.1) and the corresponding condition (section 2.5.1). The best solutions generated are sent to the decision-maker agent. Below, we describe the two neighborhood exploration strategies explored by these agents.

Neighborhood

A candidate MKP solution can be represented by binary decision variables x j where x j = 1, if the object j is selected, 0 otherwise. In our algorithm, a solution is a configuration (a dynamic vector) V that contains the selected objects (variables x j = 1). The objective value of a solution is the sum of the prices of the objects selected. Let move(x, x ′ ) be a move operator which changes a small set of components of x giving x ′ . The neighborhood of x is the subset of configurations reachable from x in one move. According to the predefined representation, this move operator is to remove objects from the current configuration and to add other non selected objects to it, at the same time. The neighborhood which satisfies the constraints is the classical add/drop neighborhood.

Neighborhood exploration strategies

In MAOM-MKP, we have two tabu search agents. Each agent applies a strategy to explore the neighboring solutions. The first tabu search agent explores the whole neighborhood by removing an object j from the current configuration and adds the best non selected object j ′ to it. j ′ is chosen from objects that do not belong to the current configuration. The best retained neighboring solution is a feasible configuration that does not violate the capacity constraints.

The second tabu search agent examines a reduced neighborhood by picking a random object j from the current configuration. Then, this object is replaced by the best non selected object j ′ that improves the total profit of the current configuration. This exploration strategy reduces the aggressive exploitation of the first tabu search agent and gives some aspect of diversification.

In order to reduce the complexity search of a neighboring solution, these two strategies employ a matrix δ(x, x ′ ) (Expression 6.4) that stores the move gain, if an object j is replaced by an object j ′ .

δ(x, x ′ ) = (F + f (x ′ )) -f (x) (6.4)
where F is the total profit of the current configuration, f (x) is the profit of an object j and f (x ′ ) is the profit of an object j ′ .

Tabu list

The tabu search agents use a traditional tabu list to store the selected objects of all completed moves. When an object j ′ is added to the new configuration, it is forbidden to be selected during the next h iterations. The iterations h is dynamically determined by h = α × F + rand(10) where rand(10) takes a random number in [1, ...., 10] and α is set to 0.1 fixed by experimentation tests.

Perturbation agent

During their optimization process, tabu search agents can reach specific cases that require diversification tasks (C 2 and C 3 of section 2.5.1). In these cases, it can trigger the perturbation agent to perturb the current configuration. The perturbation agent applies two techniques of perturbation which are reduced perturbation technique and strong perturbation technique. After generating the perturbed solution, the perturbation agent sends it to the requester tabu search agent which uses it as its new current configuration.

Reduced perturbation technique

The perturbation agent triggers the reduced perturbation behavior, when the tabu search agent detects a slight search stagnation (condition C 2 of section 2.5.1). This perturbation consists in performing add/remove random moves to generate a new feasible configuration. L random objects are removed from the received configuration. The removed objects are replaced by S random non selected objects, generating a new configuration that satisfies the constraints.

Strong perturbation technique

In the second case, the perturbation agent can activate the strong perturbation behavior, when the tabu search agent encounters a strong search stagnation. Based on the common archive of elite solutions, the perturbation agent creates a new solution to manage the search towards new regions. It extracts the number of occurrences of each object j which has been selected in a high quality solution belonging to the archive. The new configuration contains the non conflicting objects which have the smallest occurrence number. Like other problems solved in this thesis, we use an additional data structure (matrix that maintains the visited solutions) that avoids the creation of the same solution by the perturbation agent.

Crossover agents

The decision-maker can activate two crossover agents to escape deep local optima. The crossover agents apply two different crossover operators to generate two new solutions which are sent to the decision-maker agent. For these crossover agents, the parents selection is based on diversity criterion. The parents are selected from the common archive as follow:

The diversity of the solutions is measured by a similarity function which calculates the number of common objects between two configurations, in the archive. Based on the similarity values, a random number of diverse solutions are selected. From these solutions, two parents are randomly picked up. Below, we present the two crossover operators explored by the crossover agents:

-The first crossover operator gives priority to one parent to transmit all its objects to the offspring. A parent is selected to give its objects value to the offspring. Starting from the parent having the smallest objective value, the first crossover agent transmits all its objects to the offspring. Then, the non conflicting objects are extracted from the second parent, to be added to the configuration of the offspring. -The second crossover operator gives chance to only one object from each parent to be added to the offspring, at each step. The second crossover agent starts from the parent which has the smallest total profit value to build the offspring. This agent copies the first object of this parent to the offspring. Then, it extracts from other parent, the next object and transmits it to the configuration of the offspring. Each selected object has to be deleted from its parent and from other parent (if another parent contains the selected object). An object, that violates the capacities constraints, is discarded. Notice that the objects, in each parent, are sorted according to their profits.

Experimentation

We implemented MAOM-MKP in Java using the multi-agent platform Jade. The code was run on a computer with a Core I5 2.5 GHz, 8GB of RAM. We have tested our algorithm using a large sized benchmark 0â1 MKP test instances. This benchmark was described in [START_REF] Chu | A genetic algorithm for the multidimensional knapsack problem[END_REF] and it was extracted from ORlibrary (http://people.brunel.ac.uk/mastjjb/jeb/info.html). There are instances with 5, 10, and 30 constraints and 100, 250, and 500 variables. The values of the tightness ratio α for resource capacities b k (b k = α n j=1 a kj , k = 1, 2, ..., m) are 0.25, 0.50 and 0.75. For each n × m × α combination, there is ten instances, that is give a total of 270 instances.

According to the experimentations, the parameters of MAOM-MKP were adjusted as follows: the number of iterations for each local search agent (iter_max) was fixed to 1000. The parameter interval which computes the quality of the improvement of the solution between generations was fixed to 200 for both decisionmaker agent and tabu search agents. For controlling the optimization process and updating the decision matrices, the parameters g 0 , g 1 , g 2 , q 3 , q 4 and q 5 were set respectively to 2, 10, 20, 24, 2 and 4. The parameter rate µ used in updating the decision matrices was fixed to 0.9. The stopping condition is set to one hour for all the instances except hard instances (instances of 30 × 500 × 0.75 combination) that have be run for 24 hours.

MAOM-MKP is compared with the best heuristic methods available in the literature presented in 6.2:

-Genetic algorithm (GA) [START_REF] Chu | A genetic algorithm for the multidimensional knapsack problem[END_REF];

-Discrete electromagnetism-like mechanism (DEM) [START_REF] Bonyadi | A new discrete electromagnetism-based metaheuristic for solving the multidimensional knapsack problem using genetic operators[END_REF]; -Set-based particle swarm optimization (SBPSO) [START_REF] Langeveld | Set-based particle swarm optimization applied to the multidimensional knapsack problem[END_REF]; -Simplified binary version of the artificial fish swarm algorithm (newS-bAF-SA) [START_REF] Kalam Azad | Solving Large 0-1 Multidimensional Knapsack Problems by a New Simplified Binary Artificial Fish Swarm Algorithm[END_REF]. The best known solutions for the MKP, as far as we know, were obtained by [START_REF] Vasquez | A hybrid approach for the 0-1 multidimensional knapsack problem[END_REF]. Then, they were improved by [START_REF] Vasquez | Improved results on the 0â1 multidimensional knapsack problem[END_REF]. The performance of the obtained results are evaluated using the percentage (%) gap between the best objective function value and the optimal value of the LP (linear programming) relaxation. The gap is defined as:

Gap% = optimal LP valuebest objective value optimal LP value × 100 (6.5)

In table 6.1, T represents the average computational time (in seconds) of a problem set. n is the number of variables for each instance and m is the number of the capacities constraints. We cite, in this table, the average results obtained in each n × m × α combination. We give some results of the proposed MAOM-MKP in Tables 6.2,6.3,6.4.

From table 6.1 and considered average results, we observe that the DEM approach outperforms other methods. Our proposed algorithm MAOM-MKP reaches better results for the group of instances with 30 constraints and 100 variables. Considering average results, MAOM-MKP gives better results than SBPSO. The percentage average gap is 0.93 %.

Conclusion

In this chapter, we proposed a multi-agent algorithm for the multidimensional knapsack problem. We kept the proposed generic model MAOM-COP and we adapted it to the studied problem. We selected two different neighborhood strategies from the literature for the intensification agents. Two crossover operators are used by the crossover agents. The perturbation agent helps the tabu search agents to diversify their searches by performing two different perturbation techniques. The trigged perturbation technique depends on the state of search according to the decision matrices. The experimental results show that MAOM-MKP gives high quality solutions. Table 6.1 -Comparative results between MAOM-MKP and some of the best performing MKP approaches

General Conclusion Principal contributions

In this thesis, we proposed the Multi-Agent based Optimization Method for Combinatorial Optimization Problems (MAOM-COP). This method is based on multi-agent system and combines some features of several other well-established metaheuristics including tabu search, variable neighborhood search and evolutionary methods. In the first chapter, we made a brief literature review of the most popular heuristic and multi-agent based optimization approaches for combinatorial optimization problems.

In the second chapter, we presented the proposed method MAOM-COP, which explores several techniques of intensification and techniques of diversification. These techniques are manipulated by agents. In fact, tabu search agents perform intensification search by applying different neighborhood strategies. The perturbation agent and the crossover agents aim at escaping the current local optimum. During the optimization process, the decision-maker agent controls the search and decides which and when activating other agents according to the optimization state. The selection of agents to trigger is made dynamically, based on decision matrices whose values are adjusted using the reinforcement learning.

In the third chapter, we explored MAOM-COP to solve the quadratic assignment problem. The resulted MAOM-QAP is composed of the following agents: a decision-maker agent, two tabu search agents, two crossover agents and a perturbation agent. The decision-maker agent saves high quality solutions received from other agents, in an archive. Tabu search agents perform tabu search with two different strategies to explore the neighboring solutions. One of them explores the whole neighborhood swap moves to generate the best solution and the other uses a reduced search space to find an other best solution. These agents can exchange solutions with each other and they can trigger the perturbation agent to escape local optimum. A dynamic tabu tenure is used to control the degree of diversification introduced into the search. The perturbation agent applies two techniques of disturbed moves. A strong perturbation technique is made based on the archive, to create a new solution. A reduced perturbation technique makes some random perturbations in the current assignment. The crossover agents apply two informative recombination operators. The activated agents are adaptively determined based on the current search state and the decision matrices. We evaluated the performance of our algorithm by comparing it with the current best-performing approaches, using the set of QAPLIB instances. The proposed MAOM-QAP attained the best-known 103 result for many instances.

In the forth chapter, we considered the graph coloring problem and we proposed MAOM-GCP to solve it. MAOM-GCP is an other application of MAOM-COP described in chapter 2. MAOM-GCP has the same characteristic of MAOM-COP with necessary adaptation for the GCP. Moreover, the agents have the same features and they communicate in the same way of other applications of the proposed approach. Nevertheless, the differences include the neighborhood strategies, the perturbation moves and the recombination operators. As we mention, tabu search agents are the intensification agents. They apply tabu search with two neighborhood strategies. The first tabu search agent changes the colors of conflicting vertices to produce new k-coloring. A conflicting vertex is colored with the best possible other color class. The new color class is chosen among those which are not assigned to vertices adjacent to the conflicting vertex. The second tabu search agent uses the same mechanism of selecting the best color class to be assigned to vertices as the first tabu search agent. However, the modified vertices are the adjacent of conflicting vertices and not conflicting vertices. The perturbation agent performs two perturbation moves. The reduced perturbation move is applied, when there is a slight search stagnation. From a solution received from a tabu search agent, the perturbation agent makes random moves to create a new solution. It consists in a random change of the color of a conflicting vertex of the received solution. The strong perturbation move is performed when a tabu search agent observes a deep search stagnation. The perturbation agent explores the shared archive to create a new solution. It extracts the number of occurrences of each vertex colored by each color class. Each vertex is affected to a color class which has the smallest occurrence number. The crossover agents use two different recombination operators taken from the literature. We compared the results of MAOM-GCP with best known results using DIMACS coloring benchmarks. The comparative study shows that it is able to reach best known solutions of several instances.

In the fifth chapter, we presented an application of MAOM-COP to the Winner Determination Problem given MAOM-WDP. MAOM-WDP adds the following features comparing with other WDP approaches: the choice of the best neighbor is based on the selection of several bids instead of one bid. The update of the tabu tenure is dynamically adjusted, that improves the diversification. In addition, a new technique of crossover operator, for the WDP, is introduced. This operator gives the priority to the invariants bids to stay in the new solution, in order to take the good information of parents. Tabu search agents and crossover agents explore the proposed neighborhood strategy with the existing one, while the perturbation agent applies two perturbation moves. The reduced move consists in making random modification of the solution received from tabu search agents. The strong move uses the archive to generate a new solution whose bids often appear in high-quality solutions. The computational study on a set of 500 benchmark instances shows that MAOM-WDP finds high quality results on tested benchmark instances. Another representative algorithm (TSX_WDP) is proposed to solve the WDP in the appendix of this chapter.

In the sixth chapter, we applied MAOM-COP to the multidimensional knap-sack problem. As other algorithms elaborated in this thesis, MAOM-MKP has its specific characteristics. Each tabu search agent applies a strategy to explore the neighboring solutions. The first tabu search agent visits the whole neighborhood by removing an object from the current configuration and adds the best non selected object to it. The second tabu search agent selects a random object from the current configuration. Then, it replaces it by the best non selected object that improves the total profit. The perturbation agent performs two perturbations moves. The reduced perturbation move consists in performing add/remove random moves to generate a new feasible configuration, starting from the solution received from the tabu search agent, while, the strong perturbation move consists in generating a new solution.

Based on the common archive, the perturbation agent selects the objects which have been less selected in the configurations belonging to the archive. When the crossover agents are activated, two different recombination operators are performed to introduce a higher degree of diversification. MAOM-MKP is tested using large sized benchmarks from OR-library. According to the comparison results with best MKP approaches, MAOM-MKP was able to reach good quality solutions.

Future research perspectives

Last years, agent paradigm has emerged as an interesting alternative for solving different optimization problems. In fact, specific features of software agents, like autonomy, reactiveness or ability to work in teams, provide a promising tool for solving optimization problems. This thesis focuses on a multi-agent approach, dedicated for solving hard combinatorial optimization problems. The proposed approach belongs to the group of approaches combining metaheuristics, optimization problem solving, multi-agent system and learning paradigms. The main goal of the proposed MAOM-COP is to investigate the multi-agent system to create cooperative multi-search methods. These methods explore several existing metaheuristics and their techniques. The reinforcement learning is used to dynamically select activating agents according to the state of search. Several interesting directions that improve the performance of the proposed approach, can be envisaged in the future.

First, concerning the optimization process, one possibility which was not investigated during this thesis is to exploit other local search algorithms like iterated local search or simulated annealing, for intensification agents. The number of intensification agents and diversification agents depends on the problem solved. We can apply the proposed approach to other problems. Other improvement that relates to search process is to activate several simultaneous independent search agents. Each search agent starts with a different initial solution from the common archive that makes different trajectory in the search space. It is the search space decomposition which is based on the idea of dividing the whole search space into smaller subspaces, solving the resulting subproblems.

Second, we may focus on the reinforcement learning. The proposed approach used intelligent agents that carry out some set of operations based on decision matrices whose values are regulated by reinforcement learning. Indeed, better learning, that can depend on the solved problem, will make the agents more informed and allow them to choose the most appropriate operation to activate.

Finally, the current version of the proposed model can be considered as a proofof-concept implementation. One interesting perspective to improve the computational efficiency of the proposed approach is to envisage a dedicated implementation. Other possibility is to use parallel and distributed programming in the design and the implementation of metaheuristics to speed up the search. Especially reducing the search time is important in case of complex optimization problems where the search time is critical. Ces méthodes explorent plusieurs métaheuristiques. MAOM-COP est composée de plusieurs agents qui sont l'agent décideur, les agents intensificateurs et les agents diversificateurs (agents croisement et agent perturbation). A l'aide de l'apprentissage, l'agent décideur décide dynamiquement quel agent à activer entre les agents intensificateurs et les agents croisement. Si les agents intensificateurs sont activés, ils appliquent des algorithmes de recherche locale. Durant leurs recherches, ils peuvent s'échanger des informations, comme ils peuvent déclencher l'agent perturbation. Si les agents croisement sont activés, ils exécutent des opérateurs de recombinaison. Nous avons appliqué MAOM-COP sur les problèmes suivants : l'affectation quadratique, la coloration des graphes, la détermination des gagnants et le sac à dos multidimensionnel. MAOM-COP possède des performances compétitives par rapport aux algorithmes de l'état de l'art.

Thèse de Doctorat

Abstract

We elaborate a Multi-Agent based Optimization Method for Combinatorial Optimization Problems named MAOM-COP. It combines metaheuristics, multiagent systems and reinforcement learning. Although the existing heuristics contain several techniques to escape local optimum, they do not have an entire vision of the evolution of optimization search. Our main objective consists in using the multi-agent system to create intelligent cooperative methods of search. These methods explore several existing metaheuristics. MAOM-COP is composed of the following agents: the decisionmaker agent, the intensification agents and the diversification agents which are composed of the perturbation agent and the crossover agents. Based on learning techniques, the decision-maker agent decides dynamically which agent to activate between intensification agents and crossover agents. If the intensifications agents are activated, they apply local search algorithms. During their searches, they can exchange information, as they can trigger the perturbation agent. If the crossover agents are activated, they perform recombination operations. We applied MAOM-COP to the following problems: quadratic assignment, graph coloring, winner determination and multidimensional knapsack. MAOM-COP shows competitive performances compared with the approaches of the literature.

2. 1

 1 The architecture of the search using cooperative agents in MAOM-COP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Structure of the decision matrix . . . . . . . . . . . . . . . . . . . . 2.3 An example of reinforcement learning with the decision matrix . . . 3.1 An example for the first operator crossover used by the first crossover agent in MAOM-QAP . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 An example for the second operator crossover used by the second crossover agent in MAOM-QAP(z=2 in this example) . . . . . . . .5.1 An example of the recombination operator of MAOM-WDP algorithmList of Tables 3.1 Results of MAOM-QAP compared to some of the best performing QAP approaches on unstructured instances (type II) and on Reallife like instances (type III). The times are given in minutes. . . . . 3.2 Comparative results between MAOM-QAP and some of the best performing QAP approaches on grid-based (type IV) instances. The times are given in minutes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Impact of perturbation agent on MAOM-QAP on the unstructured instances (type II) and on Real-life like instances (type III): MAOM-QAP is MAOM-QAP with the perturbation agent and MAOM-QAP' is MAOM-QAP without the perturbation agent . . . . . . . . . . . 3.4 Impact of perturbation agent on MAOM-QAP on grid-based (type IV) instances. MAOM-QAP' is MAOM-QAP without the perturbation agent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Impact of crossover agents on MAOM-QAP on grid-based (type IV) instances. MAOM-QAP" is MAOM-QAP without the crossover agents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 Impact of crossover agents on MAOM-QAP on unstructured instances (type II) and on Real-life like instances (type III): MAOM-QAP is MAOM-QAP with crossover agents and MAOM-QAP" is MAOM-QAP" without crossover agents . . . . . . . . . . . . . . . 4.1 Computational results of MAOM-GCP on the difficult DIMACS challenge benchmarks (Part I) . . . . . . . . . . . . . . . . . . . . 4.2 Computational results of MAOM-GCP on the difficult DIMACS challenge benchmarks(Part II) . . . . . . . . . . . . . . . . . . . . 5.1 Some results obtained by MAOM-WDP on REL 500-1000 for benchmarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Some results obtained by MAOM-WDP on REL 1000-1000 instances for benchmarks . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Some results obtained by MAOM-WDP on REL 1000-500 instances for benchmarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Some results obtained by MAOM-WDP on REL 1000-1500 instances for benchmarks . . . . . . . . . . . . . . . . . . . . . . . . 5.5 Some results obtained by MAOM-WDP on REL 1500-1500 instances for benchmarks . . . . . . . . . . . . . . . . . . . . . . . . 11 5.6 Comparative results between MAOM-WDP Casanova, MA, SLS, TS, SAGII, MN/TS on WDP benchmarks: rows µ correspond to the average of the best objective value of the 100 instances in each group. Columns time represent the average time to reach the best solution. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 5.7 Some results obtained by TSX_WDP on REL 500-1000 instances for benchmarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 5.8 Some results obtained by TSX_WDP on REL 1000-1000 instances for benchmarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 5.9 Some results obtained by TSX_WDP on REL 1000-500 instances for benchmarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 5.10 Some results obtained by TSX_WDP on REL 1000-1500 instances for benchmarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 5.11 Results obtained by TSX_WDP on REL 1500-1500 instances for benchmarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 5.12 Comparative results between TSX_WDP and Casanova, MA, SLS, TS, SAGII, MN/TS on WDP benchmarks: rows µ correspond to the average of the best objective value of the 100 instances in each group. Columns time represent the average time to reach the best solution. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 6.1 Comparative results between MAOM-MKP and some of the best performing MKP approaches . . . . . . . . . . . . . . . . . . . . . 100 6.2 Some results obtained by MAOM-MKP on instances with 30 constraints from MKP benchmarks . . . . . . . . . . . . . . . . . . . . 101 6.3 Some results obtained by MAOM-MKP on instances with 10 constraints from MKP benchmarks . . . . . . . . . . . . . . . . . . . . 101 6.4 Some results obtained by MAOM-MKP on instances with 5 constraints from MKP benchmarks . . . . . . . . . . . . . . . . . . . . 102 List of Algorithms 1.1 Descent algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Simulated Annealing algorithm . . . . . . . . . . . . . . . . . . . . 1.3 Tabu search algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Variable Neighborhood Search algorithm . . . . . . . . . . . . . . 1.5 Iterated local search algorithm . . . . . . . . . . . . . . . . . . . . 1.6 Genetic algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.7 Memetic algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1 MAOM-COP generic procedure . . . . . . . . . . . . . . . . . . . 2.2 Decision-maker agent behavior . . . . . . . . . . . . . . . . . . . 2.3 Intensification agent behavior . . . . . . . . . . . . . . . . . . . .. 4.1 The greedy largest saturation degree heuristic (DSATUR): The saturation degree of a vertex as the number of different colors to which it is adjacent (colored vertices). . . . . . . . . . . . . . . . . . . . . 4.2 Incremental evaluation technique for updating the ∆ matrix . . . . . 5.1 The recombination operator of the second crossover agent . . . . . 5.2 TSX_WDP for the Winner Determination Problem . . . . . . . . .

Figure 2 . 1 -

 21 Figure 2.1 -The architecture of the search using cooperative agents in MAOM-COP

Figure 2

 2 Figure 2.2 -Structure of the decision matrix

  an intensification agent requests help from the other intensification agents then 9:the requesting intensification agent is blocked until it receives information from the other intensification agents (Algorithm 2

Figure 3 Iteration 2 :Figure 3 . 2 -

 3232 Figure 3.1 -An example for the first operator crossover used by the first crossover agent in MAOM-QAP

2 -

 2 Comparative results between MAOM-QAP and some of the best performing QAP approaches on grid-based (type IV) instances.

Algorithm 4. 2 .

 2 Incremental evaluation technique for updating the ∆ matrix 1: for

  Table 4.1 -Computational results of MAOM-GCP on the difficult DIMACS challenge benchmarks (Part I)

2 -

 2 Computational results of MAOM-GCP on the difficult DIMACS challenge benchmarks(Part II)

  5.A A Recombination-based Tabu Search algorithm for the WDP 84 5.A.1 TSX_WDP algorithm . . . . . . . . . . . . . . . . . . 84 5.A.2 Experimentations of TSX_WDP . . . . . . . . . . . . . 84

Figure 5

 5 Figure 5.1 -An example of the recombination operator of MAOM-WDP algorithm

δ

  M AOM -W DP/M N/T S (%)

A

  from A based on the intensification move 8:if There exists intensification move then 9:Choose an overall best allowed neighbor A ′ according to max gain criterion and by considering M {to remove from A ′ any conflicting bid) {section 5← A ′ (Move to the selected neighboring solution A ′ ) 14:Update tabu_list {section 5.3.2.2} and B {delete the winner bids from B and add the looser bids in it} 15:if f (A) > f (A * ) then

  based Optimization Method for Combinatorial Optimization ProblemsRésuméNous élaborons une approche multi-agents pour la résolution des problèmes d'optimisation combinatoire nommée MAOM-COP. Elle combine des métaheuristiques, les systèmes multi-agents et l'apprentissage par renforcement. Les heuristiques manquent d'une vue d'ensemble sur l'évolution de la recherche. Notre objectif consiste à utiliser les systèmes multi-agents pour créer des méthodes de recherche coopératives.

  Heuristic methods for combinatorial optimization problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.2 Multi-agent based optimization approaches . . . . . . . . . . 23 1.2.1 Multi-agent system . . . . . . . . . . . . . . . . . . . . 24

	Contents
	1.1 Combinatorial optimization problems and heuristic methods 17
	1.1.1 Combinatorial optimization problems . . . . . . . . . . 17
	1.1.2

1.2.2 Strategy based agents frameworks . . . . . . . . . . . . 25 1.2.3 Sub-problems based agents frameworks . . . . . . . . . 27 1.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 19

  , etc.

	Algorithm 1.2. Simulated Annealing algorithm
	Require: Initial solution s
	Ensure: Improved solution s best
	1: n=0

2: s best ← s 3: while stopping condition not reached do 4:

  used tabu search to solve the graph coloring problem, etc.

	Algorithm 1.3. Tabu search algorithm
	Require: Initial solution s
	Ensure: Improved solution s best
	1: T ← ∅ { T is the tabu list}
	2: s best ← s
	3: while stopping condition not reached do
	4:	Find the best neighbor s ′ ∈ N (s), such that (m ⊕ s = s ′ and (m / ∈ T or
		aspired(m)=true))
	5:	s ← s ′
	6:	Update the tabu list T by adding m
	7:	if f (s) < f (s best ) then
	8:	s best ← s
	9:	end if
	10: end while
	1.1.2.2.d Variable Neighborhood Search (VNS)

  , etc.

	Algorithm 1.5. Iterated local search algorithm

Ensure: Improved solution s ′′ 1: s 0 ← initial_solution_generation 2: s ← local_Search(s 0 ) 3: while stopping condition not reached do 4:

  2.7 Crossover agents . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.8 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.9 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

  Algorithm 2.1. MAOM-COP generic procedure Require: Four types of agents: one decision-maker agent, i intensification agents, one perturbation agent, c crossover agents Ensure: best information (i.e., solution) found 1: decision-maker agent is active until it needs exchanging with intensification agents or crossover agents (Algorithm 2.2) 2: if decision-maker agent decides to trigger intensification agents then

	3:	the intensification agents are activated and decision-maker agent waits for
		new information from them (Algorithm 2.3)

4:

  Algorithm 2.2. Decision-maker agent behavior Require: parameter opt, interval and max_opt Ensure: A best solution S best 1: S ← Random_solution {Random initial solution} 2: S best ← S {S best records the best solution found so far} 3: F best ← F {F best records the best objective value reached so far} 4: opt ← 0 {opt is the counter for consecutive non-improving local optimum} 5: W ← 0 {Initialization of the decision matrix of the decision-maker agent} 6: pop ← ∅ {pop is the archive of elite solutions found during the search} 7: while Stopping condition not reached do

	8:	Update W based on interval, max_opt and opt {interval (matching the
		improvement of solution between two successive iterations), max_opt and
		opt help to identify the current condition, sections 2.2.1 and 2.4.1}
	9:	Action_type ← Select an action (agents) to activate based on W {section
		2.4.1}
	10:	if Action_type = Intensification agents then
	11:	Activate intensification agents and send S to the Intensification agents
	12:	else
	13:	Activate crossover agents and send S to the crossover agents
	14:	opt ← 0
	15:	end if
	16:
	19:	S ← S 1
	20:	else
	21:	S ← S 2
	22:	end if
	23:
	26:	end if
	27:
	30:	else
	31:	opt=opt+1
	32:	end if
	33:	else
	34:	Block this agent {The decision-maker agent waits for solutions from other
		agents}
	35:	end if
	36: end while

S 1 ← ∅, S 2 ← ∅ {S 1 and S 2 are two solutions received from the activated agents, initialized to empty} 17:

if S 1 = ∅ AND S 2 = ∅ then 18: if F (S 1 ) ≥ F (S 2 ) then tr ← Exist(S 1 , S

2 , pop) {Check if S 1 and/or S 2 are in the archive pop} 24:

if tr = f alse then 25:

Add S 1 and/or S 2 to pop {Add both solutions or one of them in pop} Let S ′ be the best solution between S 1 and S 2

28:

if F (S ′ ) ≤ F best then 29:

S best ← S ′ , F best ← F (S ′ ) 37: Return F best and S best

  ). Problem definition . . . . . . . . . . . . . . . . . . . . . . . . 3.2 State of the art approaches for the QAP . . . . . . . . . . . . 3.3 A multi-agent based optimization method for the QAP (MAOM-QAP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.1 Decision-maker agent . . . . . . . . . . . . . . . . . . 3.3.2 Tabu search agents . . . . . . . . . . . . . . . . . . . . 3.3.3 Perturbation agent . . . . . . . . . . . . . . . . . . . . 3.3.4 Crossover agents . . . . . . . . . . . . . . . . . . . . . 3.4 Experimentation . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.1 Experimental results . . . . . . . . . . . . . . . . . . .

	Contents
	3.1

3.4.2 Impact of perturbation agent on MAOM-QAP . . . . . . 3.4.3 Impact of crossover agents on MAOM-QAP . . . . . . . 3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . .

47

Table 3 .

 3 1 -Results of MAOM-QAP compared to some of the best performing QAP approaches on unstructured instances (type II) and on Real-life like instances (type III). The times are given in minutes.

Table 3 .

 3 3 -Impact of perturbation agent on MAOM-QAP on the unstructured instances (type II) and on Real-life like instances (type III): MAOM-QAP is MAOM-QAP with the perturbation agent and MAOM-QAP' is MAOM-QAP without the perturbation agent

	Problem	BKS		MAOM-QAP	MAOM-QAP'
				δ	t(m)	δ	t(m)
	tai40a	3139370		0.099(2)	83.5	4.556(0)	0.00
	tai50a	4938796		0.320(1)	135.2	7.64(0)	20.3
	tai60a	7205962		0.385(2)	178.1	4.71(0)	22.1
	tai80a	13499184		0.426(0)	225	3.898(0)	30.5
	tai100a	21052466		0.470(0)	288	4.74(0)	28.45
	Average			0.341	107.6	5.419	11.26
	tai50b	458821517	0.000(10)	14.3	13.587(0)	0.00
	tai60b	608215054	0.000(10)	38.2	8.758(0)	0.00
	tai80b	818415043	0.000(10)	62.7	11.823(0)	0.00
	tai100b 1185996137	0.000(10)	91.2	14.182(0)	9.16
	tai150b	498896643	0.077(0)	9982	13.542(0)	83.1
	Average			0.015	1030.8	11.447	9.22
	Table 3.4 -Impact of perturbation agent on MAOM-QAP on grid-based (type IV)
	instances. MAOM-QAP' is MAOM-QAP without the perturbation agent
	Problem	BKS	MAOA-QAP	MAOA-QAP'
				δ	t(m)	δ	t(m)
	sko72	66256		0.000(10)	63.3	3.156(0)	0.00
	sko81	90998		0.000(10)	208.5	4.581(0)	12
	sko90	115534		0.000(10)	256.4	5.789(0)	11.2
	sko100a 152002		0.000(10)	321	4.865(0)	15
	sko100b 153890		0.000(10)	322.2	5.889(0)	13.8
	sko100c 147862		0.000(10)	324.8	4.19(0)	14.1
	sko100d 149576		0.000(10)	330	3.86(0)	30
	sko100e 149150		0.000(10)	343.3	4.245(0)	25.4
	sko100f	149036		0.000(10)	320	3.79(0)	15.4
	wil100	273038		0.000(10)	355	5.228(0)	18.1
	tho150	8133398		0.011(0)	523	3.699(0)	45
	Average			0.001	229	4.143	13.33

Table 3 .

 3 5 -Impact of crossover agents on MAOM-QAP on grid-based (type IV) instances. MAOM-QAP" is MAOM-QAP without the crossover agents

	Problem	BKS	MAOM-QAP		MAOM-QAP"
			δ	t(m)	δ	t(m)
	sko72	66256	0.000(10)	63.3	1.99(0)	4.5
	sko81	90998	0.000(10)	208.5	2.457(0)	12.4
	sko90	115534	0.000(10)	256.4	2.75(0)	15.7
	sko100a 152002	0.000(10)	321	2.486(0)	12.3
	sko100b 153890	0.000(10)	322.2	1.25(0)	11.8
	sko100c 147862	0.000(10)	324.8	3.724(0)	13.78
	sko100d 149576	0.000(10)	330	2.785(0)	25.89
	sko100e 149150	0.000(10)	343.3	1.42(0)	15.9
	sko100f	149036	0.000(10)	320	3.75(0)	22.4
	wil100	273038	0.000(10)	355	2.15(0)	28.2
	tho150	8133398	0.011(0)	523	3.489(0)	34
	Average		0.001	229	2.56	31.5

Table 3 .

 3

	Problem	BKS	MAOM-QAP		MAOM-QAP"
			δ	t(m)	δ	t(m)
	tai40a	3139370	0.099(2)	83.5	2.8(0)	2.08
	tai50a	4938796	0.320(1)	135.2	3.78(0)	15.12
	tai60a	7205962	0.385(2)	178.1	2.75(0)	18.4
	tai80a	13499184	0.426(0)	225	3.82(0)	20.1
	tai100a	21052466	0.470(0)	288	3.28(0)	20.5
	Average		0.341	107.6	2.87	8.46
	tai50b	458821517	0.000(10)	14.3	4.78(0)	0.00
	tai60b	608215054	0.000(10)	38.2	5.96(0)	0.00
	tai80b	818415043	0.000(10)	62.7	5.2(0)	5.2
	tai100b 1185996137	0.000(10)	91.2	5.11(0)	8.4
	tai150b	498896643	0.077(0)	9982	6.45(0)	23
	Average		0.015	1030.8	5.29	3.66

[START_REF]3 -Some results obtained by MAOM-MKP on instances with 10 constraints from MKP benchmarks CB OR MOAM[END_REF]

-Impact of crossover agents on MAOM-QAP on unstructured instances (type II) and on Real-life like instances (type III): MAOM-QAP is MAOM-QAP with crossover agents and MAOM-QAP" is MAOM-QAP" without crossover agents

  Problem definition . . . . . . . . . . . . . . . . . . . . . . . . 60 4.2 State of the art approaches for the GCP . . . . . . . . . . . . 60 4.3 A multi-agent based optimization method for the GCP (MAOM-GCP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

	2015a)
	Contents
	4.1 4.3.1 Decision-maker agent . . . . . . . . . . . . . . . . . . 62
	4.3.2 Tabu search agents . . . . . . . . . . . . . . . . . . . . 63
	4.3.3 Perturbation agent . . . . . . . . . . . . . . . . . . . . 64
	4.3.4 Crossover agents . . . . . . . . . . . . . . . . . . . . . 65

4.4 Experimentation . . . . . . . . . . . . . . . . . . . . . . . . . 66 4.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 61

Table 5

 5

	.1 -Some results obtained by MAOM-WDP on REL 500-1000 for bench-
	marks
	Instance	Rbest	Ravg	Rworst	AvgTime
	in101	69585.298 69585.298	69585.298	96
	in102	72518.222 72518.222	72518.222	65
	in103	70999.247 70999.247	70999.247	81
	in104	71327.641 71327.641	71327.641	75
	in105	73351.044 73351.044	73351.044	102
	in106	66440.95	66440.95	66440.95	81
	in107	68796.927 68796.927	68796.927	74
	in108	74867.585 74867.585 74867.585	76
	in109	64662.355 64662.355 64662.355	79
	in110	66549.957 66549.957	66549.957	71

Table 5 .

 5 6 -Comparative results between MAOM-WDP Casanova, MA, SLS, TS, SAGII, MN/TS on WDP benchmarks: rows µ correspond to the average of the best objective value of the 100 instances in each group. Columns time represent the average time to reach the best solution.

		MN/TS	δ M AOM -W DP/SAGII (%)		SAGII	δ M AOM -W DP/M A (%)		MA	δ M AOM -W DP/SLS (%)		SLS	δ M AOM -W DP/T S (%)		TS	δ M AOM -W DP/Casanova (%)		Casanova		MAOM-WDP	Test Set
	µ 71470.93	Time 12.28	7.53	µ 64922.02	Time 38.06	6.37	µ 65740.25	Time 56.64	8.54	µ 64216.14	Time 22.35	7.01	µ 65286.94	Time 91,07	47.22	µ 37053.78	Time 119.46	µ 70215.711	Time 70	100 instances REL-500-1000
	75540.68	0.38	2.14	73922.10	24.46	2.56	73604.62	14.98	4.61	72206.07	5.91	4.7	71985.34	25.84	32.15	51248.79	57.74	75540.68	10	REL-1000-500
	89158.98	3.12	4.08	83728.34	45.37	4.56	83304.20	33.05	5.92	82120.31	14.19	6.48	81633.63	104,30	40.44	51990.91	111.42	87.292.848	53	REL-1000-1000
	89552.18	6.39	5.04	82651.49	68.82	8.49	79644.64	24.51	9.16	79065.08	14.97	10.46	77931.41	223,37	35.19	56406.74	168.24	87041.037	85	REL-1000-1500
	108627.17	2.64	4.1	101739.64	91.78	5.78	99957.96	28.22	6.8	98877.07	16.47	7.79	97824.64	175.68	38.11	65661.03	165.92	106093.955	101	REL-1500-1500

Table 5 .

 5 9 -Some results obtained by TSX_WDP on REL 1000-500 instances for benchmarks

	Instance	Rbest	Ravg	Rworst	AvgTime
	in401	77417.482 77191.182 70628.481	12
	in402	76273.336 76153.051 74469.073	10
	in403	74843.958 74356.247 69989.28	10
	in404	78761.690 78597.224 77939.364	10
	in405	75915.900 75640.510 74899.125	10
	in406	72863.324 72671.474 71424.453	10
	in407	76365.717 76066.503 72325.694	10
	in408	77018.833 76606.838 71892.212	10
	in409	70035.529 69789.998 68800.204	9
	in410	73628.485 73212.462 71107.518	10
	Table 5.10 -Some results obtained by TSX_WDP on REL 1000-1500 instances for
	benchmarks
	Instance	Rbest	Ravg	Rworst	AvgTime
	in501	83738.040 83506.552 82605.443	107
	in502	83297.340 82546.590 76751.565	82
	in503	83718.749 82017.955 78112.719	81
	in504	83944.901 82772.535 77217.558	76
	in505	83071.930 81876.413 78909.275	66
	in506	83059.438 82252.613 78694.650	64
	in507	90288.472 85525.706 83484.521	79
	in508	84033.386 83588.301 80031.616	77
	in509	86045.479 85169.719 79655.527	75
	in510	88163.815 87802.967 77338.362	74
	Table 5.11 -Results obtained by TSX_WDP on REL 1500-1500 instances for
	benchmarks
	Instance	Rbest	Ravg	Rworst	AvgTime
	in601	107246.248 102862.848 96840.461	117
	in602	99668.269	97854.579 91452.904	78
	in603	98577.454	96567.287	95219.36	75
	in604	101713.602 100786.326 99395.413	78
	in605	107919.106 103579.211 92948.474	80
	in606	101496.527 100090.342 91790.496	79
	in607	100336.777	98225.923	95251.78	82
	in608	102231.73 100540.091 95641.925	78
	in609	100697.634 100060.045 90727.512	76
	in690	106754.424 103128.505 95636.147	57

Table 5 .

 5 12 -Comparative results between TSX_WDP and Casanova, MA, SLS, TS, SAGII, MN/TS on WDP benchmarks: rows µ correspond to the average of the best objective value of the 100 instances in each group. Columns time represent the average time to reach the best solution.

	REL-1500-1500	90.61	103178.732	165.92	65661.03	36.36	175.68	97824.64	5.18	16.47	98877.07	4.16	28.22	99957.96	3.12	91.78	101739.64	1.39	2.64	108627.17
	REL-1000-1500	75.92	85577.806	168.24	56406.74	34.08	223,37	77931.41	8.93	14.97	79065.08	7.61	24.51	79644.64	6.93	68.82	82651.49	3.41	6.39	89552.18
	REL-1000-1000	48.98	86786.159	111.42	51990.91	40.09	104,30	81633.63	5.93	14.19	82120.31	5.37	33.05	83304.20	4.01	45.37	83728.34	3.52	3.12	89158.98
	REL-1000-500	9.45	75274.184	57.74	51248.79	31.91	25.84	71985.34	4.36	5.91	72206.07	4.07	14.98	73604.62	2.21	24.46	73922.10	1.79	0.38	75540.68
	100 instances REL-500-1000	Time 74.19	µ 69647.975	Time 119.46	µ 37053.78	46.79	Time 91,07	µ 65286.94	6.26	Time 22.35	µ 64216.14	7.79	Time 56.64	µ 65740.25	5.61	Time 38.06	µ 64922.02	6.78	Time 12.28	µ 71470.93
	Test Set	TSX_WDP		Casanova		T SX/Casanova (%)	TS		δ T SX/T S (%)	SLS		δ T SX/SLS (%)	MA		δ T SX/M A (%)	SAGII		δ T SX/SAGII (%)	MN/TS
						δ

  Contents 6.1 Problem definition . . . . . . . . . . . . . . . . . . . . . . . . 92 6.2 State of the art approaches for the MKP . . . . . . . . . . . . 92 6.3 A multi-agent based optimization method for the MKP (MAOM-MKP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 6.3.1 Decision-maker agent . . . . . . . . . . . . . . . . . . 94 6.3.2 Tabu search agents . . . . . . . . . . . . . . . . . . . . 94 6.3.3 Perturbation agent . . . . . . . . . . . . . . . . . . . . 95 6.3.4 Crossover agents . . . . . . . . . . . . . . . . . . . . . 96 6.4 Experimentation . . . . . . . . . . . . . . . . . . . . . . . . . 96 6.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

Table 6 .

 6 2 -Some results obtained by MAOM-MKP on instances with 30 constraints from MKP benchmarks

	CB	OR	MOAM-MKP	CB	OR	MOAM-MKP
	30.500.00 115868

Table 6 .

 6 4 -Some results obtained by MAOM-MKP on instances with 5 constraints from MKP benchmarks

	CB	OR	MOAM-MKP	CB	OR	MOAM-MKP
	5.100.00		240079	5.250.26 148607	147247
	5.100.01		24112	5.250.27 149772	148268
	5.100.02		23463	5.250.28 155075	153981
	5.100.03		23275	5.250.29 154662	153538
	5.100.04		23789	5.100.00 24381	240079
	5.100.05		24396	5.100.01 24274	24112
	5.100.06		25343	5.100.02 23551	23463
	5.100.07		231548	5.100.03 23534	23275
	5.100.08		24068	5.100.04 23991	23789
	5.100.09		24153	5.100.05 24613	24396
	5.100.10		42382	5.100.25 58959	58737
	5.250.00		58618	5.100.26 61538	61105
	5.250.01		60679	5.100.27 61520	61170
	5.250.02		61751	5.100.28 59453	59202
	5.250.03		58744	5.100.29 59965

Acknowledgements

they trigger a backward coloring process which uses extracted independent sets as new color classes for intermediate subgraph coloring. This algorithm provides new upper bounds for other graphs. This method is, then, improved in (Hao & Wu, 2012). [START_REF] Moalic | The new memetic algorithm HEAD for graph coloring: an easy way for managing diversity[END_REF] proposed a memetic algorithm using tabu search. The main characteristic of this algorithm is to work with a population of only two individuals.

Compared to these popular graph coloring algorithms, MAOM-GCP is the first algorithm which explores the tabu search with other operators in a multi-agent system. We will describe its characteristics in the next section.

A multi-agent based optimization method for the GCP (MAOM-GCP)

We propose a Multi-Agent based Optimization method for the Graph Coloring Problem (MAOM-GCP) based on our generic MAOM-COP presented in chapter 2. In MAOM-GCP, the agents are the learners who can handle various diversification techniques and other intensification techniques to direct the search towards promising areas. We consider the following agents: the decision-maker agent, two tabu search agents, the perturbation agent and two crossover agents.

Decision-maker agent

We name this agent as decision-maker agent because it is the agent which starts the search cycle of the algorithm by generating an initial solution, then, it decides to select other agents to trigger and finally finishes the search. Based on its decision matrix (section 2.2.1) and according to the state of search (section 2.4.1), it decides whether the search process needs to be intensified or diversified. If other agents are trigged, the decision-maker agent waits them, until it receives best solutions generated by tabu search agents or crossover operator agents, then it maintains all these solutions in an archive.

The initial solution

The decision-maker agent creates an initial legal coloring using the greedy largest saturation degree heuristic (DSATUR) (Algorithm 4.1) [START_REF] Brélaz | New methods to color the vertices of a graph[END_REF]. Then, starting with this initial coloring, it randomly displaces the vertices whose color number is higher than the given color number k to a color class between [1, k]. This procedure usually leads to an illegal k-coloring which will be repaired by MAOM-GCP.

Archive of elite solutions

The decision-maker agent saves the best k-coloring, received from tabu search agents and crossover agents, in an archive. The archive represents a shared memory responsible for the tabu tenure ⋋ was fixed to 0.00006. Each instance was solved 40 times independently by the TSX_WDP algorithm with different random seeds.

In Tables 5.8, 5.10 and 5.11, the computational results of the TSX_WDP are presented on the set of the five groups of benchmarks. Given that there are 500 instances, we show only some results of each group, like in some recent papers [START_REF] Boughaci | Local Search Methods for the Optimal Winner Determination Problem in Combinatorial Auctions[END_REF]. According to this table, the values of Ravg are very close to the values of Rbest in most of cases and these two values are even equal for certain instances (for example for in101, in102, in205...). These tables show that the proposed algorithm can consistently reach high quality solutions for the tested problems.