问题标签 [tabu-search]

考虑到商业和劳动法的限制，我正在开发一种工具来为员工生成长达一个月的时间表。与类似问题的挑战和区别很少：

• 班次概念包含长达半小时的休息时间。
• 没有完整 8 班次的概念作为提到的类似问题。例如，早上 8 点需要 2 个资源，下午 3 点需要 2.5 个资源（例如，休息半小时）..
• 和常规限制，例如每天几个小时，休息前几个小时，休息时间......

可能的解决方案是依靠使用求解器，即 OR-Tools 和 Optaplanner。任何提示？

美好的一天编码大师，我正在研究项目，我正在尝试了解禁忌搜索。下面是我基于对这个主题的一点了解编写的简单实现。这个实现正确吗？

从数学上讲，这将分解为以下问题：

最大天数

st (x _i - x _j ) ² + (y _i - y _j ) ² >= d ²对于 1<=i<=j<=n

(x _i ,y _i ) ∈ C 对于 1<=i<=n

这里，C 是面积 > 0.5 的单位正方形 [0,1]x[0,1] 的闭子集。

我想这是包装问题的一般表述？C 的内部是非空的并且是连通的并且不一定是凸的。是否可以使用像禁忌搜索这样的元启发式搜索方法来解决这个问题？任何朝着正确方向的轻推将不胜感激。

我正在尝试为我正在开发的元启发式实现一个禁忌列表，该列表将禁止将 Patient 对象移动到 Room 对象。我认为最简单的方法是实现一个字典，我将在其中添加要禁用的病房对。我反驳的问题是，如果我希望禁忌列表长度为 30 个键，并且我希望能够在每次需要添加新键值对时删除最后一个键值对，我必须采用索引方式字典中的“最旧”条目。

有没有人对我如何以更聪明的方式做到这一点有任何建议？

谢谢！

我正在寻找在 Java 中的禁忌搜索启发式中逐步编码分解和重建步骤，但我不明白粗体字。

这是什么以及如何在 java 编码中解释它

在将初始解决方案划分为路线或子问题的子集之后。每个路线子集都由禁忌搜索处理。为每个子问题找到的最佳路线简单地合并在一起，形成分解和重建步骤的下一个解决方案。在 D&R 循环之后，将记录最终路线。

分解是基于与每条路线的重心相关的极角。使用这些极角，域被划分为包含大致相同数量的路由的扇区。请注意，通过选择不同的起始角度来创建扇区，分解从一个 D&R 变为下一个，从而允许 CROSS 交换启发式利用新的路由对。

预先感谢

经常看到Tabu Search用于解决旅行购买者/旅行推销员，我想研究一下但总是无法弄清楚进展和停止条件，谁能解释一下如何实现?

我正在使用 OptaPlanner 来解决一些规划问题。我阅读了文档，但我不太确定爬山和禁忌搜索算法究竟是如何工作的。我不确定的是：

• 爬山选择是否只移动具有比当前更好的最佳分数的移动，或者它是否允许选择具有不比当前更差的最佳分数的移动？
• 禁忌搜索是否允许选择得分比当前得分更差的动作，如果没有动作导致解决方案的得分高于或等于当前得分？

我是 VB.Net 的初学者。作为我学习的一部分，我正在编写一种称为禁忌搜索的迭代算法来解决优化问题。在每次迭代中，当前最佳解决方案的一个或几个变量都会改变，以针对同一问题开发新的解决方案。根据这一举措找到的解决方案的质量，我们可能希望在未来的迭代中停止重复它或促进推进它。一个称为禁忌列表的列表记录了迄今为止执行的移动质量以及应该避免或促进这些移动的未来迭代次数。

我已将禁忌列表定义为字典。我的问题是： 如何在每次迭代时更新字典的大小？

假设我只想保留添加到这本字典的最后 30 个项目。因此，当添加第 31 项时，应将第 1 项从字典中删除。

这是我的代码的一部分。

公开课搬家

部分主要算法**

Dim MoveTabuDic As New Dictionary(Of Move, UShort) '****removed steps**** Dim aMove as new Move '****removed steps**** MoveTabuDic .add(aMove,IterationID)

谢谢！

我正在尝试在https://archive.ics.uci.edu/ml/datasets/ILPD+(Indian+Liver+Patient+Dataset)上的 UCI 存储库中提供的印度患者肝病分类数据集上实施禁忌搜索，但面临问题。以下是我使用的代码

错误：

部分数据

如果有人可以帮助我

我试图找出最好的技术或资源来帮助我解决优化问题。问题在于将会议参与者与预定义角色进行最佳匹配。在会议之前，与会人员为每个角色决定他或她是否：

• 如果可能的话，积极寻求填补这个角色（“A”）
• 愿意担任该角色，但对此感觉不强烈（“W”）
• 不愿意担任这个角色（“U”）。

例如，一个可能的输入矩阵是：

目标是在以下限制条件下，最大限度地增加角色标记为“A”的与会者的匹配次数：

• 所有角色仅由一名与会者担任
• 禁止参加者标记为“U”的比赛

对于此示例，最佳解决方案如下，其中 4/5 角色使用“A”匹配填充。

有谁知道是否有比蛮力更好的方法来解决这类问题（对于较大的矩阵来说，这很快变得不可行）？我愿意接受我自己实现的优化算法的一般建议（即禁忌搜索、遗传算法、分支定界等），甚至是指向现有包（如OptaPlanner ）中的功能的指针。

谢谢！