# Ant Colony Optimization and Constraint Programming

## Christine Solnon

Language: English

Pages: 320

ISBN: 1848211309

Format: PDF / Kindle (mobi) / ePub

Ant colony optimization is a metaheuristic which has been successfully applied to a wide range of combinatorial optimization problems. The author describes this metaheuristic and studies its efficiency for solving some hard combinatorial problems, with a specific focus on constraint programming. The text is organized into three parts.

The first part introduces constraint programming, which provides high level features to declaratively model problems by means of constraints. It describes the main existing approaches for solving constraint satisfaction problems, including complete tree search approaches and metaheuristics, and shows how they can be integrated within constraint programming languages.

The second part describes the ant colony optimization metaheuristic and illustrates its capabilities on different constraint satisfaction problems.

The third part shows how the ant colony may be integrated within a constraint programming language, thus combining the expressive power of constraint programming languages, to describe problems in a declarative way, and the solving power of ant colony optimization to efficiently solve these problems.

Programming Mobile Robots with Aria and Player: A Guide to C++ Object-Oriented Control

Microsoft Dynamics GP 2013 Cookbook

may either consider p1 and p2 as probabilities or as ratios. A very interesting property of randomly generated binary CSPs is that the phase transition region has been clearly located [CLA 96]: the constrainedness κ introduced in section 2.3.1 is defined by the formula: κ= n−1 p1 logm 2 1 1 − p2 . The hardest instances (and therefore those that interest us most when evaluating a solution algorithm) are those for which κ is equal to 1. Let us return to Figure 2.3 which plots the evolution of

a transformation from the Hamiltonian path problem [GEN 98] and by a transformation from the exact cover by 3-sets problem [KIS 04]. Kis also showed that the problem is N P-hard in the strong sense and does not belong to N P in the general case. This comes from the fact that an instance of the car sequencing problem may be encoded by giving, for each different car class, the number of cars belonging to this class and the subset of options required by these cars. With such an encoding, and

program defines the problem in a declarative way. We first declare that Vars is a list of N variables (line 2), and that variables of Vars must be assigned to integer values between 1 and N (line 3). It is then declared that values assigned to Vars must all be different (line 4), and the predicate allDiffDiag is called to declare constraints that ensure there is at most one queen in each diagonal (line 5). The predicate allDiffDiag/2 calls the predicate allDiffDiagForXI/2 for each couple (I,XI)

i++){ for(int j = i+1; j < n; j++){ int k = j - i; Constraint c1 = neq(queens[i], queens[j]); Constraint c2 = neq(queens[i], plus(queens[j], k)); Constraint c3 = neq(queens[i], minus(queens[j], k)); m.addConstraints(c1, c2, c3); } } Solver s = new CPSolver(); s.read(m); s.solveAll(); Figure 7.2. Choco program corresponding to the second CSP model of the n-queens problem be tricky to achieve, however, because of the duality of the goals of CP. (Note that this duality is also observed in CP

solutions with respect to the first objective. The third objective function is then used to break further ties, and so on. However, in many cases, the different objectives of a MOP cannot be ranked or weighted in an a priori way; it is therefore most desirable to propose a set of solutions to the decision maker. This set is called the Pareto set or non-dominated solution set. Example 10.1. When planning trips, we usually want to minimize both traveling times and costs: a journey t with cost c and