问题标签 [simulated-annealing]

有没有人知道我可以检查和适应的 Visual Basic 中模拟退火的合理记录示例？

我需要一个有据可查的用于放置和布线的模拟退火源代码（在 c++ 或 java 中）。谁能帮我？

我正在使用模拟退火来解决 NP 完全资源调度问题。对于任务的每个候选排序，我计算了几个不同的成本（或能量值）。一些例子是（尽管细节可能与问题无关）：

• global_finish_time：计划跨越的总天数。
• split_cost：每个任务由于其他任务的中断而延迟的天数（这是为了阻止任务一旦开始就被中断）。
• deadline_cost：每个错过的最后期限逾期的天数的平方和。

传统的接受概率函数如下所示（在 Python 中）：

到目前为止，我通过简单地将前两个成本合并为一个，这样我就可以将结果输入acceptance_probability. 但我真正想要的是deadline_cost永远优先global_finish_time，并且global_finish_time优先split_cost。

所以我对 Stack Overflow 的问题是：我如何设计一个接受概率函数，它考虑了多种能量，但始终认为第一种能量比第二种能量更重要，等等？换句话说，我想传入old_cost和new_cost作为几个成本的元组并返回一个合理的值。

编辑：在对提议的解决方案进行了几天的试验后，我得出结论，唯一对我来说足够好的方法是 Mike Dunlavey 的建议，尽管这会给具有不同单位的成本组件带来许多其他困难。我几乎被迫将苹果与橙子进行比较。

因此，我付出了一些努力来“规范化”这些值。首先，deadline_cost是平方和，因此它呈指数增长，而其他分量呈线性增长。为了解决这个问题，我使用平方根来获得类似的增长率。其次，我开发了一个计算成本线性组合的函数，但会根据目前看到的最高成本成分自动调整系数。

例如，如果最高成本的元组是 (A, B, C)，输入成本向量是 (x, y, z)，则线性组合是 BCx + Cy + z。这样，无论 z 值有多高，它都不会比 x 值 1 更重要。

当发现新的最大成本时，这会在成本函数中产生“锯齿”。例如，如果 C 上升，那么对于给定的 (x, y, z) 输入，BCx 和 Cy 都会更高，成本之间的差异也会如此。更高的成本差异意味着接受概率会下降，就好像温度突然降低了额外的步骤一样。但实际上这不是问题，因为最大成本在开始时仅更新几次，以后不会更改。我相信这甚至可以在理论上被证明会收敛到一个正确的结果，因为我们知道成本会收敛到一个较低的值。

仍然让我有些困惑的一件事是，当最大成本为 1.0 或更低（例如 0.5）时会发生什么。对于 (0.5, 0.5, 0.5) 的最大向量，这将给出线性组合 0.5*0.5*x + 0.5*y + z，即优先顺序突然颠倒。我想处理它的最佳方法是使用最大向量将所有值缩放到给定范围，以便系数始终相同（例如，100x + 10y + z）。但我还没有尝试过。

我正在 Beowulf 集群上使用 MPI 进行并行编程。我们为模拟退火编写了并行算法。它工作正常。我们预计执行速度比串行代码快 15 倍。但是我们在不同的架构和操作系统上执行了一些串行 C 代码，这样我们就可以有不同的数据集来进行性能测量。我们在代码中使用了这个 Random 函数。我们在 windows 和 ubuntu linux 上都使用 GCC。我们发现在 linux 上执行需要更长的时间，我们不知道为什么。有人可以使用 gcc 在 linux 和 windows 上编译此代码并尝试向我解释。

如果我使用 100 000 000 作为 NUM_ITERATIONS 的参数执行它，我在 linux 上的执行速度比在 windows 上慢 20 倍。在具有双引导 win + ubuntu linux 的相同架构的机器上进行了测试。我们需要帮助，因为这个 Random 函数是我们想要用数据显示的瓶颈。

我在理解进化算法时遇到了问题。我多次尝试使用这种技术，但我总是遇到同样的问题：退化为模拟退火。

可以说我的初始人口（括号中的健身）是：

A (7), B (9), C (14), D (19)

交配和突变后，我有以下孩子：

AB (8.3), AC (12.2), AD (14.1), BC(11), BD (14.7), CD (17)

在消除最弱的之后，我们得到

甲，乙，乙，交流

下一回合，AB 将再次配对，结果约为 8，将 AC 推出。下一轮，AB 再次将 B 推出（假设突变改变适应度主要在 >1 范围内）。

现在，仅仅几圈之后，池中就充满了最初最适合的候选者（A，B）和这两个的突变（AB）。无论初始池的大小如何，都会发生这种情况，只是需要更长的时间。比如说，初始人口为 50，需要 50 个回合，然后所有其他人都被淘汰，从而将整个设置转变为更复杂的模拟退火。一开始我也和自己交配了候选人，使问题恶化。

那么，我想念什么？我的突变率是不是太小了，如果我增加它们会消失吗？

这是我使用它的项目： http ://stefan.schallerl.com/simuan-grid-grad/ 是的，代码有问题，界面很糟糕，但我现在懒得修复它 - 和小心，它可能会锁定您的浏览器。更好地使用 chrome，即使认为 firefox 一次也不比 chrome 慢（可能图像比较的跟踪得到了回报，耶！）。如果有人感兴趣，可以在这里找到代码。

在这里，我只是放弃了 ev-alg 的想法并进行了模拟退火。

ps：我什至不确定模拟退火——它就像进化算法，只是人口规模为 1，对吧？

基本上我正在尝试为多维背包问题创建模拟退火的实现。我在让系统决定是否接受较低值的状态时遇到问题。退火由这个函数控制：

acceptNext() 函数决定是否接受下一个状态，定义如下：

经过一番测试，我发现 currentBag 字段在调用 acceptNext() 函数之前被赋值为下一个值。我在我的任何代码中都找不到另一个“this.currentBag = next”。为了完整起见，这里是 getNext() 函数：

我看不出是什么使这个值更新。有人在代码中看到任何东西吗？

谢谢

本

我想找到一个确定性退火代码的开源示例。它几乎可以是任何语言：C、C++、MatLab/Octave、Fortran。我已经找到了用于模拟退火的 MatLab 代码，因此最好使用 MatLab。这是描述该算法的论文。

确定性退火是一种尝试找到成本函数的全局最小值的优化技术。该技术旨在能够使用随机性探索大部分成本表面，同时仍使用本地信息执行优化。该过程首先更改成本函数以引入随机性概念，从而允许探索大面积区域。每次迭代的随机量（由香农熵 [2] 测量）都受到约束，并执行局部优化。逐渐地，施加的随机性降低了，因此在终止时，算法优化了原始成本函数，产生了原始问题的解决方案

我正在做一个模拟退火算法来优化给定的学生和项目分配。

这是来自 Wikipedia 的与语言无关的伪代码：

以下是该技术的改编。我的主管说这个想法在理论上是好的。

首先，我从整组随机分配中提取一些分配（即整个学生词典及其分配的项目，包括项目的排名），将其复制并传递给我的函数。我们称之为分配aOld（它是一个字典）。aOld有一个与之相关的权重，称为wOld。权重如下所述。

该函数执行以下操作：

• 让这个分配，aOld成为best_node
• 从所有学生中，选择随机数量的学生并粘贴在列表中
• 剥离（DEALLOCATE）他们的项目++反映项目的变化（allocated参数现在False）和讲师（如果他们的一个或多个项目不再分配，则释放空位）
• 随机化该列表
• 再次尝试分配（REALLOCATE）该列表项目中的每个人
• 计算权重（将排名相加，排名 1 = 1，排名 2 = 2...并且没有项目排名 = 101）
• 对于这个新的分配aNew，如果权重wNew小于wOld我一开始选择的分配权重，那么这就是best_node（由上面的Simulated Annealing算法定义）。将算法应用于aNew并继续。
• 如果wOld < wNew，则再次应用该算法aOld并继续。

分配/数据点表示为“节点”，使得node = (weight, allocation_dict, projects_dict, lecturers_dict)

现在，我只能执行这个算法一次，但我需要尝试一个数字 N（kmax在 Wikipedia 片段中表示）并确保我总是随身携带，previousnode和best_node.

为了不修改我原来的字典（我可能想重置），我做了字典的浅拷贝。从我在文档中阅读的内容来看，它似乎只复制引用，并且由于我的字典包含对象，因此更改复制的字典最终会更改对象。所以我尝试使用copy.deepcopy()。这些字典引用了已经用 SQLA 映射的对象。

Questions:

我已经为所面临的问题提供了一些解决方案，但由于我使用 Python 的超绿色能力，它们对我来说听起来都相当神秘。

1. Deepcopy 不能很好地与 SQLA 配合使用。有人告诉我，ORM 对象上的深拷贝可能存在阻止它按预期工作的问题。显然，我最好“构建复制构造函数，即 def copy(self): return FooBar(....)”。有人可以解释一下这是什么意思吗？

2. 我检查并发现deepcopy存在问题，因为 SQLAlchemy 在您的对象上放置了额外的信息，即_sa_instance_state属性，我不希望在副本中但对于对象来说是必需的。有人告诉我：“有一些方法可以手动清除旧的_sa_instance_state并在对象上放置一个新的，但最直接的方法是创建一个新对象__init__()并设置重要的属性，而不是做一个完整的深拷贝。” 这到底是什么意思呢？我是否创建了一个新的、未映射的类，类似于旧的映射类？

3. 另一种解决方案是我必须“__deepcopy__()在您的对象上实现并确保设置了新的 _sa_instance_state，sqlalchemy.orm.attributes 中有一些函数可以帮助解决这个问题。” 再一次，这超出了我的范围，所以有人可以解释一下这是什么意思吗？

4. 一个更普遍的问题：鉴于上述信息，是否有任何关于如何维护信息/状态的建议best_node（必须始终通过我的 while 循环持续存在）和previous_node，如果我的实际对象（由字典引用，因此节点) 是否由于发生解除分配/重新分配而发生变化？也就是说，不使用副本？

维基百科和这个网站都描述了模拟退火算法中的一个类似步骤，我在这里挑选了它：

维基百科：

Yuval Baror，关于八皇后之谜：

我的问题是：这个随机动作能达到什么目的？

我正在学习模拟退火算法，并且有几个关于如何修改示例算法以解决 0-1 背包问题的问题。

我在 CP 上找到了这个很棒的代码：

http://www.codeproject.com/KB/recipes/simulatedAnnealingTSP.aspx

我很确定我现在了解这一切是如何工作的（除了整个波尔兹曼条件，就我而言，这是黑魔法，尽管我了解逃避局部最优，显然这正是这样做的）。我想重新设计它以解决 0-1 背包-“ish”问题。基本上，我将 5,000 个对象中的一个放入 10 个麻袋中，并且需要针对最少的未使用空间进行优化。我分配给解决方案的实际“分数”有点复杂，但与算法无关。

这似乎很容易。这意味着 Anneal() 函数将基本相同。我必须实现 GetNextArrangement() 函数以满足我的需要。在 TSM 问题中，他只是沿路径交换两个随机节点（即，他在每次迭代中进行非常小的更改）。

对于我的问题，在第一次迭代中，我会选择 10 个随机对象并查看剩余空间。对于下一次迭代，我会选择 10 个新的随机对象吗？还是我最好只换掉一些对象，比如一半或什至其中一个？或者也许我换出的物体数量应该与温度有关？任何这些对我来说似乎都是可行的，我只是想知道是否有人对最佳方法有一些建议（尽管一旦我的代码工作，我可以搞砸改进）。

谢谢！

麦克风