Universit� de Gen�ve
April 18, 2008, 14:15, Room MA A3 30 (click here for the map)
<p>Part 1: Variable Space Search (joint work with A. Hertz and M. Plumettaz) </p> <p> Three ingredients must be defined when designing a Local Search procedure LS (e.g. a descent method, simulated annealing, tabu search) for a particular problem: a search space S, an objective function f that measures the quality of each solution s in S, and a neighborhood structure N. In 1997, for a given objective function f, a solution space S and a local search procedure LS, Mladenovic and Hansen proposed the Variable Neighborhood Search (VNS) algorithm that uses several neighborhoods N1, …, Nr. VNS was already efficiently applied to many problems. In 2005, for a given objective function f, a neighborhood structure N and a local search procedure LS, Mladenovic, Plastria and Urosevic proposed the Reformulation Descent (RD) algorithm that uses several solutions spaces S1, …, Sr. RD was efficiently applied to circle packing problems. In 2007, we propose to generalize VNS and RD as follows. Consider a set of search spaces {S1, …, Sr} with their respective objective functions {f1, …, fr}. For each search space Si, consider a set Ni = {N(i,1), …, N(i,q)} of neighborhoods which can be used in Si for minimizing fi. Consider finally a set of translators T(i,j) that transform any solution in Si into a solution in Sj. The resulting Variable Space Search (VSS) algorithm successively performs a local search LSi in the different search spaces Si, always using the associated neighborhoods in Ni and the objective function fi. VSS was efficiently applied to the graph coloring problem. </p> <p> Part 2: Ant Local Search (joint work with M. Plumettaz and D. Schindl) </p> <p> We propose a new kind of ant algorithm called Ant Local Search. In most ant algorithms, the role of each ant is to build a solution in a constructive way. In contrast, we propose to consider each ant as a local search, where at each step and in concordance with all ant algorithms, each ant modifies the current solution by the use of the greedy force and the trail systems. We also propose ways to reduce the computational effort associated with each ant decision. Such a new and general ant methodology is then applied to the well-known k-coloring problem, which is NP-hard. Computational experiments give evidence that our algorithm is competitive with the best coloring methods. It is actually the first time that an ant algorithm is competitive with the best coloring methods. </p>