问题标签 [simulated-annealing]

很抱歉，如果之前有人问过这个问题，但我不确定我在寻找什么，而且我缺乏正确构建问题的领域知识，这使得答案很难找到！

无论如何，我正在尝试在 Python 中实现一篇论文中的模拟退火算法（IBM J. Res. Dev., 2001; 45(3/4); 545）。作者给出了他在 C++ 中实现的算法的清晰概述，但是在他的定义结束时，他陈述了以下内容

“为了避免重复和可能昂贵的内存分配，S 和 S* 被实现为单个对象，能够在不利的突变后恢复到其初始状态。”

（S 和 S* 表示正在优化的任何东西的原始状态和阶跃变化状态）。

在以前更天真的版本中，我使用两个列表来保存每个状态，但他的评论似乎表明这种方法内存效率低下。因此，我的问题是：

1. 他的评论是 C++ 特定的吗？在 Python 中我可以继续使用列表而不用担心吗？
2. 如果我确实需要担心它，我应该使用什么 Python 数据结构？只需定义一个具有原始和变异属性的类以及一个进行变异的方法，还是我还缺少其他东西？
3. 我仍然需要这两种状态，那么将其包装在一个类中会改变内存分配方式以使类表示更紧凑吗？

以下问题专门用于生物技术应用，但可以说明其他领域类似问题的一般原则。这是一个 NP 难题，可能与旅行商问题有关，我很好奇可以使用哪些算法来得出解决方案。

简要生物背景：蛋白质由 20 种氨基酸组成。DNA 由 4 个碱基组成 - A、C、G、T。蛋白质的 DNA 序列决定了氨基酸的序列 - 每个连续的 3 个 DNA 碱基序列（单位称为密码子）编码一个氨基酸。单个氨基酸可以由多个密码子编码，例如缬氨酸有 4 种编码方式。

并非所有密码子都是平等的——其中一些密码子的处理速度比其他密码子快。此外，并非所有密码子 PAIRS 都是相同的 - 有些密码子对比其他密码子慢。

这意味着对于 100 个氨基酸（300 个 DNA 碱基）的特定基因，有多种编码相同氨基酸序列的方法，但具有非常不同的特性，例如处理速度。

给定具有相应速度值的密码子对表，我们想编写一个算法，可以输出所需速度的序列，例如可能的最快和最慢序列，以及介于两者之间的梯度。输入是编码基因的 DNA 序列，以及密码子对的字典及其各自的速度得分（-1 到 1）。输出是优化的 DNA 序列及其整个速度得分（可以表示为所有密码子对得分的总和）。氨基酸序列必须保持不变。

示例：如果我们有编码 3 个氨基酸的序列 AAATTTGGG，并且我们有带有分数的密码子对：

AAATT = -0.5

TTTGGG = -0.5

那么这个序列的得分可能是-1。

现在，如果我们也有配对选择，我们可以评估不同的可能性：

AAATTG = -0.7 AAATTC = -0.3

TTGGGC = +0.2 TTCGGA = -1.0

人们会发现基于此信息的最佳序列是 AAATTCGGA，因为它给出的总体值为 -1.3。

这个问题的复杂性当然在于密码子对对周围所有密码子对的影响。

完整的密码子对图表将有 61*61 个条目（因为 3 个密码子停止了基因的读取）。

====

问题

我相信这是一个 NP-hard 问题，并且与 TSP 有关。我见过一种方法使用模拟退火算法。我很好奇是否还有其他有见地的方法来考虑这个问题以及相应的算法和启发式方法来产生所需的输出。

如果是动态规划，什么方法是合适的？

此外，我们如何使用该算法来创建速度分数的梯度，而不仅仅是最大值和最小值？

我需要在 C++ 中创建一个算法，以使用蒙特卡洛方法模拟球体上的相互排斥点。到目前为止，我所拥有的是：

我认为这没问题（注意我本质上是在尝试最小化能量函数），但我想让它更准确/让它运行得更快。为此，我认为我应该更改 p 的值、while 循环条件或如何在代码末尾更改 p。（所有这些都在 * ... *中，因为我试图让他们更大胆地让你清楚我的意思。大约是代码的 3/4）。我已经坐了几个小时试图改变这些条件，但没有任何效果。对于 n=12（球体上的 12 个点），我的能量应该在 49.16525306 处出现，但我只能在 50.5 和 54.0 之间得到它。我知道这相对较好，但我希望它更准确（即使确实需要一段时间）。如果可能的话，我还希望提高成功率（我的整体成功率绝对令人震惊）。

如果有人有任何想法，我将非常感谢您的帮助！

谢谢。

（注意：如果你想运行代码，你必须把双 * 去掉。有四个部分用双 * 包围它们）。

The authors of "Numerical Recipes" give in Ch. 10 an implementation of the simulated annealing algorithm that combines the "classical" simulated annealing with the Nelder-Mead downhill simplex method.

What I really like about this algorithm is the way it converges to a classic downhill search as the annealing temperatures reaches 0. However, I have never found any other reference to this algorithm; is it a safe, mature variant of the simulated annealing algorithm (i.e. production-ready) or should it be considered as an experimental idea thrown into the book?

我正在设计一个递归搜索函数，在某些条件下，它将正常递归，而在其他条件下，必须以概率 e^(E/Temperature) 递归。除递归步骤外，所有代码都已完成，因为我无法弄清楚如何根据一定的概率执行某些操作

我在使用模拟退火算法来解决 n 个皇后问题时遇到了一些麻烦。基本上，我让它寻找更好的更多，它工作得很好，但是我运行一个公式来检查它是否应该采取“坏”的举动。据我了解，公式是 e^（板状态计算变化）/CurrentTemperature。该数字应与随机双精度或浮点数进行比较，如果随机数大于等式，则算法应采取“坏”举动。我遇到的问题是公式总是非常接近 1 或超过 1。这是我的一些代码（让我知道是否应该提供更多）：

我尝试了很多方法，例如将检查变量设为负数或取棋盘状态之间差异的绝对值。此外，被调用的计算函数基本上是扫描棋盘并返回有多少皇后发生冲突，这是一个 int。让我知道是否需要更多说明。谢谢

能量变量在模拟退火算法中代表什么？我猜它类似于 GA 中的适应度变量？

我正在使用模拟退火来解决密码分析问题，但我遇到了难题。我一辈子都无法让我的概率函数正确运行，它要么过于频繁地采用更差的解决方案（所以我在 0.03 和 0.2 的分数附近反弹）或者它不经常采用它（所以我被困在0.35)。我环顾了互联网，但我只遇到了问题涉及找到最小值的示例......我的问题需要找到最大值，最差分数是 0，最好是 1。

我需要关于温度的建议以及我应该使用什么概率函数。

成本函数如何为 TSP 工作？假设我有一个距离为 100 的游览，我稍微更改了游览，对原来的游览做了 4 次更改，现在它的距离为 50。

成本函数会给我 4，因为那是变化的数量；还是50，因为距离的变化？或者，也许我错过了一些东西，但两者都没有？

我说模拟退火算法中的能量等于成本变化是否正确？

所以我可以用以下方法计算它：