用模拟退火进行图着色

Question

我正在尝试用模拟退火算法来解决一个图着色问题。这是一般的在线算法，但是当我看到它时，我无法理解如何将这个算法应用到这个问题上。图中的每个节点必须具有与其邻接颜色不同的颜色。

如何使用模拟退火算法来解决这个问题。

这个问题的“温度”、“时间表”是什么？

请帮我理解一下。谢谢

Answer 1

图的适当着色是将颜色分配给图的顶点，这样两个相邻的顶点就没有相同的颜色。

要解决这个问题，假设有一个有N个节点的图G，那么需要以下方法：

• assignColor(图)：关于第一个结果
• assignColor(图，节点)：为nod设置新的颜色
• isColoringValid(图)：检查当前着色是否有效
• lossFunction(图)：计算使用的颜色数
• getProbability( oldValue，newValue，温度)：计算新状态是否被接受

最后，将递归方法编写为simulatedAnnealing(图，临时)，其中包含一个主循环，用于更改每个节点的颜色，然后检查isColoringValid()是否可以计算损失函数()和getProbability()。因为在较高的温度下，你可以接受值的答案，但在较低的温度下，只有更好的答案才能被接受，并且在方法结束时降低温度并调用simulatedAnnealing(图，温度)。

您可以在我的集散地中找到完整的解决方案。

Answer 2

正确设置启动温度和冷却调度参数是一件痛苦的事情，因为在获得好的结果之前，需要对两者都有一个很好的值。如果其中一个是关闭的，那么您可能不会注意到您正在朝着好的方向改变另一个。

这就是为什么我要根据其他参数(启动温度)和时间梯度(开始时为0.0，到达时限后为1.0 )计算冷却调度的原因。将1参数调到一个好值要容易得多。

通常，我建议从你所有移动中的平均分数差的起始温度开始。