问题标签 [tabu-search]

我正在尝试通过禁忌搜索解决 TSP 问题。我了解这种启发式方法的大部分基础。但是我很难弄清楚某些禁忌移动的节奏和禁忌列表的长度之间有什么区别。这两种数据结构在网络上的大多数教程和文档中都有提及。对于这种差异的一些解释，我将不胜感激。

我有一些代码，我正在为我的课程做。这个想法是我用禁忌搜索来解决旅行推销员搜索。我在我的代码中已经做的是随机生成一个城市列表（基于用户的输入——他想要多少个城市，程序在开始时提出的问题）和他们自己的一组坐标（X 和Y），我可以计算它们之间的距离（我假设，那个推销员可以直接从一个城市直接到另一个城市）。

我的问题是禁忌搜索。我的想法是有一个默认路径，只需按顺序访问所有城市，它们就会生成（第 47 行，变量名：domyslne）。然后我明白了，我在上面交换了两个随机城市，并计算了那条路线的长度。这是棘手的部分：我无法理解我想要的禁忌和所有条件（它可能是一组嵌套循环）。我想获得 2 个表：禁忌（我存储 X 最后检查的组合）和 tabulen（存储禁忌表中相应路径的长度）。接下来我渲染一条新路线并计算它的长度。如果禁忌已经达到它的最大大小 X，并且新路线的长度更小，那么当前存储的最大值，我们从禁忌列表中删除该最大值，并将其替换为新的，即 i' 我刚刚渲染。最后，在此类命令的 Y 循环之后（当前默认设置为 6，但我正在考虑像城市数量的平方或其他东西一样），我从禁忌表中获得最短路线并将其作为解决方案呈现. 我不知道如何使它正常工作，我希望我能在这里得到一些帮助。非常感谢你！

我正在开发一个自动化的员工调度应用程序，使用带有约束的禁忌搜索。

我已经受到了很多工作限制（员工的最短工作时间、每班所需的员工人数、不得一起工作的员工……）。

自动计划器在每次迭代中尝试不同的移动（添加/删除/交换员工），评估所有生成的解决方案的约束（每次移动 1 个解决方案）并选择惩罚最小的解决方案。

我现在正在尝试实施一个约束，例如“如果员工 A 被安排在轮班，那么员工 B 也必须被安排在同一个班次”。

我的问题是我不知道如何实现这一点。

假设当前的举措是将员工 A 安排在无人值班的轮班 S。如果评估了我试图创建的约束，那么该解决方案将立即受到惩罚，因为员工 A 被安排在没有员工 B 的 S 上。因此，这解决方案可能永远不会被选中，即使它是一个好的解决方案，而且员工 A 或 B 都不会开始工作。

有人知道吗？

谢谢

我想在 matlab 中实现禁忌搜索以优化 Ackley 基准函数，因为我对如何为这个连续函数生成邻域感到困惑。统一的随机数是否足够，或者我必须选择步长？谢谢帮助

我在 Java 中开发了一种启发式算法来解决具有真实数据和附加属性（例如项目的条形码）的 VRP 变体。现在我需要一个禁忌搜索框架来使用禁忌搜索技术。我尝试使用 OpenTS，但没有重要示例，并且该框架尚未更新，所以我问：是否可以使用 OptaPlanner 在我的应用程序中运行禁忌搜索算法？

我正在使用带有约束的 CodeIgniter 和禁忌搜索算法为中学制作这个自动时间表系统

但是我不知道如何开始，我已经得到了科目、教师、课时和班级的数据。在我得到这些数据后，我不知道下一步我应该做什么，还有限制。

有人对我应该做什么有任何想法或建议吗？或者我可以访问的关于 php 或 codeigniter 代码中的禁忌搜索算法的教程有什么链接？

先感谢您。

晚上好，

作为数据分析课程的一部分，我们被投入到元启发式领域......我真的很难理解如何在 R 中实现禁忌搜索，因为我的编程背景相当有限。

我也没有在 Google 或 youtube 上找到任何R示例Python，所以我真的很祈祷我能在这里找到一些东西。

我遇到的问题类似于优化中的“位置问题”。我需要找到集线器的最佳组合，以最小化集线器和节点之间的总距离。

我需要找到5 hubs，每个人的总容量是120

我的策略是创建一个distance matrix，然后我将创建另一个 50 x 50 矩阵来表示节点是否成为集线器，最后我将两者相乘并添加所有距离以获得总距离。

我创建了数据框：

我创建了距离矩阵

我创建了节点需求矩阵：

我创建了一个空矩阵来显示 a 是否变为nodeahub "1""0"

然后创建初始解决方案，我随机分配Hubs并计算距离和需求。

这个想法是尝试“1”和“0”的不同组合以最小化总距离，但我遇到以下问题：

• 我不知道如何进行本地搜索并从初始解决方案中进行排列。

• 我不知道如何防止 R 在一段时间内使用最佳解决方案，即禁忌列表

• 我不知道如何处理每个节点的供应限制（每个节点的总需求 < 120），我可以通过循环来做到这一点，但因为在这种情况下我正在乘以矩阵，所以我很迷茫。

谁能帮我一把？？？

非常感谢！

我想在 Python 中实现禁忌搜索来解决与图形相关的问题（查找树、着色问题和那种东西）。我已经用 Python 编写了基本代码，这是我第一次编写类似的代码。我知道算法是如何工作的（理论上），但我在实现它时遇到了一些麻烦。

生成随机解决方案以便我可以启动算法的最佳方法是什么？我想从初始图生成一棵随机树：

我正在使用这些函数来查看边缘和孤立节点：

而这个找到路径：

我需要的是找到一棵树作为随机解决方案，这样我就可以更改它，直到我拥有的图表中最大的可能。

最好的方法是什么？谢谢你。

当试图了解禁忌搜索如何应用于旅行推销员时，我很难理解邻域是如何生成的。如果我们从维基百科看这个伪代码：

我最好的候选人从最近邻算法生成的路径开始，这条路径的邻居是什么？

假设我的路径是 A,B,D,C,A 是每个索引的所有可能性的邻域吗？例如 [B,D,C], [A,C,D] 等？

然后我们消除每个索引的禁忌列表中的邻居？

如果不是，我的邻居是什么？

同样在伪代码中，禁忌列表只添加了新的最佳候选者，那么我们下次如何选择不同的邻域呢？

维基百科源代码：

https://en.wikipedia.org/wiki/Tabu_search

我想知道像禁忌搜索这样的元启发式算法的计算复杂度是多少。为什么在原论文中没有讨论算法的时间和空间复杂度，甚至没有讨论迭代禁忌搜索和反应禁忌搜索等算法的改进？

我想和其他人一起分析旅行商问题的算法。