**Applications** ## Applications and examples:
**Basic Representation for K-coloring** ## Configuration C = a vector of labels/colors **The conflict number**** **of C:
## K-coloring problem ≈ find configuration C* minimizing the conflict number
**The Landscape for K-colouring** ## The set of **all possible configurations** has cardinal *K|V|* ~ a space of dimension *|V|* ## The neighbourhood relation: - We pass from a
- configuration C to C’
- by changing just one
- colour in a
**conflicting** - vertex of C
**Related Works** ## Exact algorithms: |V| <100 ## Inexact algorithms - Metaheuristics (working on landscape):
- Local Search: Tabu Search, Simulated Annealing [Hertz et Al, A variable neighborhood search for graph coloring, 2003], [Zufferey et. al, A graph coloring heuristic using partial solutions and a reactive tabu scheme, 2007]
- Evolutionary algorithms [Fleurent et. Al, Genetic and hybrid algorithms for graph coloring, 1996], [Hao et Al, Hybrid Evolutionary Algorithms for Graph Coloring, 1999][Galinier et Al, An adaptive memory algorithm for graph coloring,2004]
- Sequential construction: DSatur Algorithm, RLS
**Steepest Descent** ## It starts from a random configuration - At each step, we move to the best neighbouring configuration
- We stop when it is no longer possible to find better neighbouring configurations (in a
*local minimum*)
**Steepest Descent: Cases**
**Tabu Search** ## A steepest descent that can perform “up moves” - We can move to a worse configuration when there is no possible move not increasing the number of conflicts
- =>
**Tabu list = a list of temporary forbidden moves**
**Tabu Search: evolution of the number of conflicts**
**Tabu Search: evolution of the number of conflicts**
**Tabu Search: evolution of the number of conflicts**
**Tabu List Length** ## The role of the tabu list is to restrain the algorithm from cycling in a local plateau - Tabu List Length:
*tl = RandomInt(0,10) + f* - Each time we perform move
*m, *we forbid the algorithm from re-applying *m* on next *tl moves*
## *tl = 2* enough to break a cycle of length 2
## The same tabu list length = 2 is NOT enough to break larger cycles ## We can find both very small or very large plateaus small or large cycles ## Long tabu list for large plateaus and small tabu list for small plateaus
**Adaptive Tabu List Length ** ## We double the tabu list length when we stayed X moves at the same conflict number - A constant very long tabu list length would forbid a move (an assignment of a color) for much too long!
**New Evaluation Function** ## In most algorithms, all configurations are compared and assessed with the *classical evaluation function ***f** ## Not all conflicts are as difficult to solve ## We can have: - Edges with
__easy conflicts__ **(V3-V4)** - We can simply change the color in one end
- Edges with
__hard conflicts __**(V3-V2)** - We cannot change a color without generating new conflicts
**Degree-based Evaluation** *{i,j}* Easy conflict in C1*{i,k}* Hard conflict in C2
## Vertex *j*: degree=*1* Vertex *k*: degree=*6* ## ## Each edge has a weight, according to the degree of each vertex
## RTS gains one colour on 75% of the Dimacs graphs - in comparison with the same algorithm without the two improvements ## RTS gains one colour in 50% of graphs in comparison with the best of all Tabu algorithms ever written ## The new evaluation function gains one colour in 25% of cases vs classical evaluation function
**RTS vs Best Algorithms** ## The best algorithms are often population-based hybrid algorithms ## RTS is able to find the best colorings ever reported for 75% of the Dimacs graphs (28 out of the 38) ## We obtained the best results of *previous local search algorithms* in almost 100% of cases (2 exceptions)
**Conclusions** ## Two simple techniques are enough to make a basic local search provide very competitive results. ## Tabu Search can now attain the best results ever found in 75% of the Dimacs graphs
**Dostları ilə paylaş:** |