问题标签 [tabu-search]

你能帮我理解这个禁忌搜索页面 7 的例子吗：

TS是一种数学优化方法，属于基于轨迹的技术类。禁忌搜索通过使用描述访问解决方案的内存结构来增强本地搜索方法的性能：一旦确定了潜在解决方案，它就会被标记为“禁忌”（“禁忌”是同一单词的不同拼写），以便该算法不会重复访问这种可能性。禁忌搜索归因于 Fred W. Glover

我不明白为什么要使用上三角形，为什么会这样：

禁忌结构现在显示，在 3 次迭代中禁止交换模块 4 和 5 的位置。在这一步中，最大的改进是将 3 和 1 交换为 2 的增益。

您能否解释一下为什么是三角形以及为什么是上面的陈述？

？？？

你知道一个好的和最重要的详细禁忌搜索示例吗？

事情并不难，因为我正在理解这个很酷的算法。

我发现这个教程和这个有SAT问题，但不是很详细

我试图用“Drools Planner”包解决部分初始化的数独谜题（报纸上出现的那种）。虽然它可以在 3 秒内从头开始生成（随机）拼图，但它会陷入解决部分初始化拼图的循环中。

问题： 诸如禁忌搜索和模拟退火之类的启发式算法从根本上说是数独的错误选择吗？我说的是完整性（是否会达成解决方案）和效率（是否矫枉过正）。

我的怀疑来自这样一个事实，即数独谜题总是有一个精确和单一的解决方案，而启发式算法（AFAIK）并不是为了“达到它们”而设计的。

我有一个图形着色问题，涉及数千个顶点，每个顶点有 10 到 50 条边。我一直在研究许多图形着色启发式（GA，禁忌搜索......），但我发现它们很难比较并决定哪个最适合我。有没有人有大规模图形着色的经验来推荐一种技术或告诉我该领域当前的状态或最先进的算法？

谢谢。

我了解禁忌搜索的工作原理，即它与爬山有何相似之处，但是会记住搜索空间中的点集。这被称为禁忌列表，因为算法试图避免它们。

然后我遇到了这句话，它可以是真也可以是假的：

“它使用内存数据结构来防止移动到搜索空间中以前访问过的点。”

这似乎是正确的......禁忌搜索如何使用“内存数据结构”？我知道它使用内存结构，但内存数据结构似乎是错误的。我是不是想太多了，还是因为数据结构可能完全意味着其他东西而感到疲倦是对的。

我在 TSPTW 问题中应用了禁忌搜索，但它给我的结果类似于使用交换枢轴规则（2 个城市之间的交换）获得最佳改进，但是在一些论文中，据说禁忌给出接近最优的结果（我有使用另一种算法的具有 0 个约束违反的相同初始解决方案的最佳解决方案）。所以我想确定一下，这个结果正常吗？这是我应用禁忌的伪代码：

}

我有一个读取文本文件中项目的代码。它逐行读取它们。当一个项目被读取时，它将被添加到一个列表中，以防止它再次被重新访问。当列表已满（最大大小）时，它将被清除。但是，需要检查添加到列表中的项目，以防止重新访问此特定项目以获得预定义值，即使列表已被清除。

请帮我弄清楚如何在 C# 2012 中做。

谢谢

我正在比较两个保护区设计工具，即Marxan和ConsNet，它们都使用元启发式算法来解决最小集覆盖问题的一个版本。Marxan 使用模拟退火，ConsNet 使用禁忌搜索。虽然我的背景是生物学，但我认为我能够通过元启发式掌握一些优化的概念。

但是，关于禁忌搜索，我还没有弄清楚两件事。首先是它如何逃避局部最优。我知道它不能逆转它的动作，这会阻止它循环，但我不知道是什么让它在找到它后留下局部最优值。我可以理解模拟退火是如何做到的——它有一定的概率接受一个更糟糕的解决方案，随着时间的推移它会减少，直到它不再接受一个更糟糕的解决方案——但我不知道 TS 是如何做到的。

第二个问题是，在ConsNet手册中，找到如下语句

搜索是完全确定性的，但它可以根据解决方案存档的当前状态或目标的当前状态来决定如何进行

TS 总是确定性的吗？通过阅读一些资料，我了解到移动可能是随机的，就像在 SA 中一样。但是后来有一些论文谈论“确定性禁忌搜索”。确定性禁忌搜索如何知道采取哪些行动以及如何摆脱局部最优？它有时必须接受更糟糕的解决方案，对吧？

提前谢谢了

我试图通过将它与爬山算法一起使用来理解禁忌搜索，以解决旅行商问题。

我了解“纯”爬山算法，但禁忌搜索如何更改此算法对我来说不是很清楚。

爬山示范：

假设我们有 6 个城市A,B,C,D,E,F，我们随机选择一个初始状态：(A,B,C,D,E,F)，旅行成本为 120。

然后我将选择一组相邻状态（通过将第一个元素与第二个、第三个、第四个等交换），并计算每个状态的旅行成本：

现在我们找到了一个局部最优值：(F,B,C,D,E,A)。

禁忌搜索如何改变上述算法？如果您可以演示一两次迭代，我将非常感激。

放宽对“邻居”的标准是否就足够了，还是需要采取其他标准行动？