# Applications and examples

Yüklə 265 Kb.
 tarix 30.10.2018 ölçüsü 265 Kb. #76092

• ## K-coloring problem ≈ find configuration C* minimizing the conflict number

• The problem is solved if C* has no conflicts

• ## The neighbourhood relation:

• We pass from a
• configuration C to C’
• by changing just one
• colour in a conflicting
• vertex of C

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

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

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

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

• ## 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!

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

• ## Tabu Search can now attain the best results ever found in 75% of the Dimacs graphs

Yüklə 265 Kb.

Dostları ilə paylaş:

Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©genderi.org 2024
rəhbərliyinə müraciət

Ana səhifə