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
100>
Dostları ilə paylaş: |