问题标签 [simulated-annealing]

我正在尝试在 java 中找到旅行推销员问题的解决方案。我通过以下方式应用模拟退火来解决这个问题。这是我实现模拟退火的代码段：

当我用上面的方法完成TSP问题时，我发现图片中有很多交叉，我听说2-Opt Arithmetic可以解决这个问题。基本上，我想创建两个顶点的游览，或者基本上是一组独特的边。现在对于每对独特的边 (x,y) 和 (u,v)，如果 cost(x,y) + cost (u,v) < cost(x,u) + cost(y,v)，那么我将在 (x,u) 和 (y,v) 上使用边 (x,y) 和 (u,v)。我将对每对独特的边重复此过程，直到成本不降低。

但是我如何找到独特的边缘对来应用 2-opt 技术呢？我的意思是如果我之前生成了一个解决方案（如在上面的代码中），我将如何在解决方案中找到交叉边缘（我需要检查以应用 2 opt 的边缘）？

一个人让我用启发式方法解决 MCPP。他指出了模拟退火。我正在做我的研究，就我而言，这个算法不能应用于这个问题。为什么？原因是为了找到解决方案，在 MCPP 的大多数情况下，某些道路（边缘、弧线）必须加倍。这给了我下一条边的无限可能选择，因为我总是可以重新使用以前使用过的边之一（例如，刚才让我到达当前节点的边）。我错了吗？如果是这样，我错过了什么？还是纯模拟退火根本不适合这个问题？

我正在使用 Python 中的启发式方法进行特征选择，谁能告诉我哪个是模拟退火的最佳数据集？

我正在使用 Matlab 的simulannealbnd函数来找到使用模拟退火的函数的最小值。作为参数，可以传递变量的下限和上限。在文档中描述了模拟退火是如何工作的，但没有关于如何强制执行绑定约束。

有人知道（或可以想象）在这种情况下如何做到这一点？

在一些期刊上，我读到 WSAT（步行 SAT）算法在解决 SAT 问题方面比模拟退火算法具有更好的性能。

所以我的问题是，有人可以解释为什么我们得到这个结果吗？可能是因为 SA 更像是一种通用算法？

编辑： 这可能是我读到的最相关的文件。

为什么我的程序会产生越来越差的解决方案并这么早收敛？

我最近一直在阅读优化和各种元启发式技术，最近我决定尝试实施模拟退火，如本文所述。

我相信我对这个理论已经足够了解了。

存在由以下函数引导的接受概率

其中成本增量是当前解决方案的“成本”与新随机生成的建议解决方案的成本之间的差异。成本增量越大，您的新解决方案被接受的可能性就越低，并且随着迭代次数的增加以及您的温度“冷却”并接近 0，新解决方案被接受的变化越来越小。

您的成本取决于您想要最小化或最大化的某个目标函数，并且您的目标函数将根据您的问题而改变。

我实现了帖子和维基百科中提到的模拟退火功能：

以及获取随机邻居的函数：

并根据一些目标函数计算当前状态的成本：

以及测试/运行所有内容的代码：

现在，我的问题是，当我运行所有程序时，当我实际运行我的程序时，我只看到一些状态变化。下面你可以看到我从前 10 次迭代中得到的输出。

到第 65 次迭代时，我的解决方案实际上变得更糟，事情似乎停滞不前：

我在模拟退火算法中对不同的初始温度进行了一些测试，并注意到起始温度对算法的性能有影响。

有什么方法可以计算出一个好的初始温度吗？

我需要找到一种算法，该算法将从 956 个列表中选择 6 个邮政编码（这六个邮政编码稍后将用作销售区域中心）。我很高兴我有一个很好的功能来对可能的解决方案进行排名。我也知道哪些邮政编码彼此相邻。

我的第一个想法是尝试模拟退火。这给出了不一致的，而且真的不是很好的结果。下图显示了六个区域中心，它们正试图最大限度地覆盖总人口（见下文）。

此代码假设减少初始游览的距离： distan(initial_tour) < distan(best) 。你能帮我吗？我已经尝试了一整天了。我需要改变我的交换方式吗？ 出了点问题，模拟退火不起作用：

编辑：更改了代码和措辞以使我的疑问更加明确

很长一段时间以来，我一直在努力使用 OpenMP 并行化 C 中的循环，并想知道我应该如何应对这一挑战。该循环由以下部分组成（如果您想知道该循环是集成在模拟退火算法中的主循环）：

这个循环的问题是迭代的次数不能通过它的条件来计算，所以我想出了一种不同的方法来编写这个循环，以便能够使用 openmp：

但是，由于我不明白的原因，此解决方案与我在输出之前编写的顺序版本不同... openmp 指令是否放置得当？或者我应该以不同的方式使用它们？提前感谢您的任何回答。