问题标签 [simulated-annealing]

我在使用模拟退火和蛮力解决 TSP 方面做了一个简短的工作。正如我们所知，蛮力的 TSP 将通过检查所有可能的路径采取 O(n!) 步骤，我想问的是，如果我们使用模拟退火算法允许这些步骤，它会得到正确的解决方案。（保证它会产生一个迭代次数较少的次优解决方案，但我的问题是，如果我们运行它 n! 次，我们能得到最优解决方案，其中 n 是城市的数量）

我在 C++ 中实现了模拟退火，以(x-2)^2+(y-1)^2在一定范围内最小化。

我得到了各种各样的输出，这对于这种类型的启发式方法是不可接受的。似乎解决方案正在收敛，但从未完全接近解决方案。

我的代码：

我怎样才能让它达到解决方案？

什么确定性算法适合以下资源分配/调度问题？

考虑一组玩家：P1、P2、P3 和 P4。每个玩家从蜂窝塔接收数据（例如在无线网络中）。塔在 1 秒内传输数据。有5个街区。可以安排每个玩家在任意数量的块中接收数据。

现在，每个块中接收的数据量是一个常数（C）除以同一块中调度的其他玩家的数量（因为必须共享带宽）。贪婪的方法会将每个玩家分配到每个块，但随后每个块接收的数据会减少。

我们如何才能找到玩家对时间块的分配，从而使网络传递的数据量最大化？我已经在这个问题上尝试了许多启发式方法（遗传算法，Sim Anneal）并且它们运行良好。但是，我想解决最佳时间表。

我有 X 个学生，其中 X 是 6 的倍数。我现在想将学生分成 6 组。

我有一个函数可以衡量一组 6 人的“好”程度（假设它是一个黑匣子，目前在恒定时间内运行）。通过划分学生，然后在每个组上调用我的函数来衡量它的好坏，然后总结每个组的好坏，我能够衡量一组组的“好”程度。

我正在尝试创建一种算法，该算法将以某种方式对学生进行分组，以使所有组的总优度最大化，并且没有任何组的个体优度低于某个值 y。换句话说，将学生分成 6 人一组，以在所有组的优度高于 y 的约束下最大化总优度。

我希望运行此算法的学生人数（X）约为 36。

这个问题似乎是 NP-Complete，所以我可以接受启发式算法。我对此没有太多经验，但我认为某种遗传算法或模拟退火甚至贪心算法可能会起作用，但我不确定从哪里开始我的研究。

有人可以指出我正确的方向吗？我做了一些研究，问题似乎与旅行商问题几乎相同（问题空间是学生/节点的所有排列）但我认为我不能将 TSP 算法应用于此，因为“节点的数量"（大约 36）对于任何有效的东西来说都是相当大的。

我决定学习模拟退火作为解决这个问题的新方法。它本质上询问如何用 -1、0 或 1 填充网格，以便每一行和每一列的总和都是唯一的。作为一个测试用例，我使用了一个 6x6 的网格，Neil 给出了一个肯定的最优解：

我的代码通常不会在大多数运行中达到最佳情况，甚至返回错误的网格成本（old_cost应该匹配count_conflict(grid)）。我的参数是否设置不正确，我是否执行不正确，或者模拟退火在这里不是可行的方法？

成功编写了遗传算法后，我现在正在编写一个模拟退火程序来与 GA 进行比较，但似乎无法让它达到任何一种最优，更不用说全局最优了。

经过一些测试，我认为问题似乎是将变量传递回while循环。出于测试目的，我已将代码更改为基本上只接受能量增量低于前一个解决方案的解决方案，因此我应该期望存储最佳解决方案的变量仅显示较低的数字，但实际上是波动的并且总是返回最多最近的解决方案是否更好。任何帮助将非常感激。

使用 Python 的（2.7）默认（Mersenne Twister）random() 函数作为 Kernighan-Lin 算法的随机数生成器是一个好主意（就生成的数字的质量和所需的 CPU 时间而言）？有更好的方法吗？

此外，在相同的上下文中， random() 函数如何为模拟退火算法生成 0 到 1 之间的数字？

这个问题参考了在 Encog 存储库中获得的C#'s Lunar Lander Example 。如示例所示，我正在使用 NeuralSimulatedAnnealing 来训练我的多层前馈网络（50 个 epoch）

_

这个例子效果很好，神经飞行员准确地学习了如何在给定的条件下降落宇宙飞船，但是我想要更多的东西！

为此，我创建了一个如下所示的类全局变量，并在 LanderSimulator 类中修改了一行

_

因此，现在取决于fuelConsumption变量，每次推力都会消耗燃料。然后我尝试了三个不同的燃料消耗值，以下是各个网络各自的最佳分数：

当我在彼此上测试这些网络时，结果令人失望：

• 当fuelConsumed 分别为5 和10 时，网络1 的得分为-39591 和-39661。
• 当fuelConsumed 分别为1 和10 时，网络2 的得分为-8832 和-35671。
• 当fuelConsumed 分别为1 和5 时，网络3 的得分为-24510 和-19697。

因此，我尝试为所有三种场景训练一个网络，如下所示：

但结果还是一样

如何创建一个神经飞行员，让我在所有三种情况下都能获得最高分？

编辑：看起来这已经在这里回答了

它没有出现在我的搜索中，因为我不知道正确的命名法。我暂时把问题留在这里，以防有人因为限制而到达这里。

我正在尝试优化一个几乎在所有点上都是平坦的函数（“阶梯函数”，但维度更高）。

目标是优化一组权重，它们的总和必须为一个，并且是我需要最小化的函数的参数。

问题在于，由于函数在大多数点上都是平坦的，梯度技术会失败，因为它们会立即收敛于起始的“猜测”。

我的假设是，这可以通过（a）退火或（b）遗传算法来解决。Scipy 把我送到盆地跳跃。但是，我找不到任何方法来使用 scipy.

实际问题：如何在没有梯度的情况下解决最小化问题，并为输入变量使用约束和范围？

以下是一个玩具示例（显然可以使用渐变来解决这个示例）：

我尝试转换 [ http://www.cleveralgorithms.com/nature-inspired/physical/simulated_annealing.html][1]中给出的 Ruby 代码，以使用模拟退火解决旅行推销员问题，并且两个代码都没有运行任何错误。但是，我发现它们在同一个问题实例（来自 TSPLIB 的 berlin52）上的表现不同。Ruby 代码通常在 9000 到 10000 之间获得最佳解决方案，而 Java 代码在 16000 到 17000 之间获得最佳解决方案。我的 Java 代码中是否有任何部分没有很好地实现？我查过了，但没有找到！提前致谢。

红宝石代码：

Java 代码：