Applications and examples

Yüklə 445 b.
ölçüsü445 b.


  • 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 problem is solved if C* has no conflicts

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
  • Risk : to repeat a set of moves again and again

    • => 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

Tabu List Length

  • 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 vs. Other Tabu Algorithms

  • 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)


  • 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ş:

Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur © 2019
rəhbərliyinə müraciət

    Ana səhifə