使用模拟退火进行图形着色
Graph Coloring with using Simulated Annealing
我正在尝试使用模拟退火为图形着色问题提出算法。网上有通用的算法，但是看的时候没明白怎么把这个算法应用到这个问题上。图中的每个节点必须具有与其邻居不同的颜色。
如何为此使用模拟退火算法。
本题中的"temperature"、"schedule"是什么？
请帮助我理解这一点。谢谢
正确设置起始温度和冷却调度参数是一件痛苦的事情，因为在获得良好结果之前，您需要为两者都设置一个良好的值。如果其中一个关闭，那么您可能不会注意到您正在朝好的方向改变另一个。
这就是为什么我 applied a trick 根据其他参数（起始温度）和时间梯度（开始时为 0.0，达到时间限制后为 1.0 的数字）计算冷却计划的原因。
将 1 个参数调整到一个好的值要容易得多。
一般来说，我建议从你所有动作（=neighborhood）的平均分数差异的起始温度开始。
图的正确着色是指为图的顶点分配颜色，以便没有两个相邻顶点具有相同的颜色。
要解决此问题，假设您有一个包含 N 个节点的图 G，那么您需要这些方法：
- assignColor(graph): 第一个结果
- assignColor(graph, node): 为点头设置新颜色
- isColoringValid(graph): 检查当前着色是否有效
- lossFunction(graph): 计算使用的颜色数
- getProbability(oldValue, newValue, temperature) : 计算新状态是否被接受
最后编写一个递归方法，如 simulatedAnnealing(graph, temp)，其中包含一个主循环来更改每个节点的颜色，然后检查 isColoringValid() 是否可以计算损失函数() 和 getProbability()。因为在较高温度下您可以接受有价值的答案，但在较低温度下，只会接受更好的答案，并且在方法结束时降低温度并调用 simulatedAnnealing(graph, temp)。
您可以在 my github 中找到完整的解决方案。
我正在尝试使用模拟退火为图形着色问题提出算法。网上有通用的算法，但是看的时候没明白怎么把这个算法应用到这个问题上。图中的每个节点必须具有与其邻居不同的颜色。
如何为此使用模拟退火算法。
本题中的"temperature"、"schedule"是什么？
请帮助我理解这一点。谢谢
正确设置起始温度和冷却调度参数是一件痛苦的事情，因为在获得良好结果之前，您需要为两者都设置一个良好的值。如果其中一个关闭，那么您可能不会注意到您正在朝好的方向改变另一个。
这就是为什么我 applied a trick 根据其他参数（起始温度）和时间梯度（开始时为 0.0，达到时间限制后为 1.0 的数字）计算冷却计划的原因。 将 1 个参数调整到一个好的值要容易得多。
一般来说，我建议从你所有动作（=neighborhood）的平均分数差异的起始温度开始。
图的正确着色是指为图的顶点分配颜色，以便没有两个相邻顶点具有相同的颜色。
要解决此问题，假设您有一个包含 N 个节点的图 G，那么您需要这些方法：
- assignColor(graph): 第一个结果
- assignColor(graph, node): 为点头设置新颜色
- isColoringValid(graph): 检查当前着色是否有效
- lossFunction(graph): 计算使用的颜色数
- getProbability(oldValue, newValue, temperature) : 计算新状态是否被接受
最后编写一个递归方法，如 simulatedAnnealing(graph, temp)，其中包含一个主循环来更改每个节点的颜色，然后检查 isColoringValid() 是否可以计算损失函数() 和 getProbability()。因为在较高温度下您可以接受有价值的答案，但在较低温度下，只会接受更好的答案，并且在方法结束时降低温度并调用 simulatedAnnealing(graph, temp)。
您可以在 my github 中找到完整的解决方案。