CODEWITHSUNDEEP
javanp-completesimulated-annealinggraph-coloring
M-Razavi
M-Razavi

Reputation: 3467

Graph Coloring with using Simulated Annealing

I am trying to come up with the algorithm for a Graph Coloring problem using Simulated Annealing. There is the general algorithm online, but when i look at it, I couldn't understand how can apply this algorithm on this problem. Each node in graph must had diffrent color from it's neibours.

How can I use the Simulated annealing algorithm for this.
What is the "temperature", "schedule" in this problem?

Please help me understand this. Thanks

Upvotes: 2

Views: 1536

Answers (2)

M-Razavi
M-Razavi

Reputation: 3467

A proper coloring of a graph is an assignment of colors to the vertices of the graph so that no two adjacent vertices have the same color.
To solve this problem assume you have a graph G with N nodes then you need these methods:

  • assignColor(graph): for first result
  • assignColor(graph, node): to set a new color for a nod
  • isColoringValid(graph): to check current coloring is valid or not
  • lossFunction(graph): calculate the number of colors which is used
  • getProbability( oldValue, newValue, temperature) : calculate the new state is accepted or not

Finally write a recursive method as simulatedAnnealing(graph, temp) which contains a main loop to change color for each node then check isColoringValid() if it would ok calculate loss function() and getProbability(). Because in higher temperature you can accept worth answer but in lower temperature, only better answer is accepted and at the end of method reduce the temperature and call simulatedAnnealing(graph, temp).

You can find complete solution in my github.

Upvotes: 0

Geoffrey De Smet
Geoffrey De Smet

Reputation: 27312

Setting the starting temperature and cooling scheduling parameters correctly is a pain, because you need to have a good value for both before you get a good result. If one of them is off, then you might not notice that you're changing the other one in the good direction.

That's why I applied a trick to calculate the cooling scheduling based on the other parameter (the starting temperature) and the time gradient (a number that's 0.0 at the start and 1.0 after the time limit is reached). It's a lot easier to tune 1 parameter to a good value.

Generally, I advice to start with a starting temperature of the average score diff in all your moves (=neighborhood).

Upvotes: 0

Related Questions