禁忌搜索
可能会在遗传算法
中使用。
遗传算法可能需要很多代才能获得成功,因此高性能运行对它们来说很重要。禁忌搜索用于增强避免局部最大值,并具有良好的内存机制,以便通过迭代获得更好的成功。然而,除了它的好处之外,禁忌搜索还使算法像往常一样变得更慢。
我的问题是:
是否有关于何时使用遗传算法禁忌搜索以及何时不使用禁忌搜索的研究?
最佳答案
一般来说,遗传算法花费大量时间对不太理想的点进行采样。假设您正在优化一个看起来像几个驼峰的函数。 GA 最初会将点倾倒在各处,然后慢慢收敛到驼峰顶部的点。然而,即使是非常简单的局部搜索算法也可以采用 GA 在驼峰斜坡上生成的点,并将其直接推到驼峰的顶部。如果你让 GA 生成的每个点都经过这个简单的局部优化,那么你最终会得到 GA 只搜索局部最优空间的结果,这通常会大大提高你找到最佳解决方案的机会。问题是,当您开始解决实际问题而不是驼峰时,简单的局部搜索算法通常不足以找到真正好的局部最优值,但可以使用禁忌搜索之类的东西来代替它们。
有两个缺点。第一,每一代 GA 的运行速度都要慢得多(但通常需要的代数要少得多)。第二,你会失去一些多样性,这可能会导致你更频繁地收敛到次优解决方案。
实际上,只要有可能,我总是在 GA 中包含某种形式的本地搜索。 《没有免费的午餐》告诉我们,有时你会让事情变得更糟,但在专业进行 GA 和本地搜索研究十年左右之后,我几乎总是会贴出一张全新的 100 美元钞票,上面写着本地搜索将改善情况对于您真正关心的大多数情况。它不一定是禁忌搜索;它也可以是禁忌搜索。您可以使用模拟退火、VDS,或者只是一个简单的下一次爬山程序。
关于performance - 何时使用禁忌搜索与遗传算法结合使用,何时不使用?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5911479/