何时使用禁忌搜索与遗传算法结合使用，何时不使用？
禁忌搜索可能会在遗传算法中使用。
遗传算法可能需要很多代才能获得成功，因此高性能运行对它们来说很重要。禁忌搜索用于增强避免局部最大值，并具有良好的记忆机制，以便通过迭代获得更好的成功。然而，除了它的好处之外，禁忌搜索还使算法像往常一样变得更慢。
我的问题是：
是否有关于何时使用遗传算法禁忌搜索以及何时不使用遗传算法的研究？
Tabu Search may be using at Genetic Algorithms.
Genetic Algorithms may need many generations to get a success so running at high performance is important for them. Tabu Search is for enhancement for avoiding local maximums and good with memory mechanism to get better success through the iterations. However Tabu Search makes the algorithm more slower as usual beside its benefits.
My question is:
Is there any research about when to use Tabu Search with Genetic Algorithms and when not?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
一般来说，遗传算法花费大量时间对不太理想的点进行采样。假设您正在优化一个看起来像几个驼峰的函数。 GA 最初会将点倾倒在各处，然后慢慢收敛到驼峰顶部的点。然而，即使是非常简单的局部搜索算法也可以采用 GA 在驼峰斜坡上生成的点，并将其直接推到驼峰的顶部。如果你让 GA 生成的每个点都经过这个简单的局部优化，那么你最终会得到 GA 只搜索局部最优空间的结果，这通常会大大提高你找到最佳解决方案的机会。问题是，当你开始解决实际问题而不是驼峰时，简单的局部搜索算法通常不足以找到真正好的局部最优值，但可以使用禁忌搜索之类的东西来代替。
有两个缺点。第一，每一代 GA 的运行速度都要慢得多（但通常需要的代数要少得多）。第二，你会失去一些多样性，这可能会导致你更频繁地收敛到次优解决方案。
在实践中，只要有可能，我总是会在 GA 中包含某种形式的本地搜索。 《没有免费的午餐》告诉我们，有时你会让事情变得更糟，但在专业进行 GA 和本地搜索研究十年左右之后，我几乎总是会贴出一张全新的 100 美元钞票，上面写着本地搜索将改善情况对于您真正关心的大多数情况。它不一定是禁忌搜索；它也可以是禁忌搜索。您可以使用模拟退火、VDS，或者只是一个简单的下一次爬山程序。
Generally speaking, GAs spend a lot of time sampling points that are trivially suboptimal. Suppose you're optimizing a function that looks like a couple of camel humps. GAs will dump points all over the place initially, and slowly converge to the points being at the top of the humps. However, even a very simple local search algorithm can take a point that the GA generates on the slope of a hump and push it straight to the top of the hump essentially immediately. If you let every point the GA generates go through this simple local optimization, then you end up with a GA searching only the space of local optima, which generally will greatly improve your chances of finding the best solutions. The problem is that when you start on real problems instead of camel humps, simple local search algorithms often aren't powerful enough to find the really good local optima, but something like tabu search can be used in their place.
There are two drawbacks. One, each generation of the GA goes much more slowly (but you need many fewer generations usually). Two, you lose some diversity, which can cause you to converge to a suboptimal solution more often.
In practice, I would always include some form of local search inside a GA whenever possible. No Free Lunch tells us that sometimes you'll make things worse, but after ten years or so of doing GA and local search research professionally, I'd pretty much always put up a crisp new $100 bill that says that local search will improve things for the majority of cases you really care about. It doesn't have to be tabu search; you could use Simulated Annealing, VDS, or just a simple next-ascent hill climber.
当您将多种启发式方法组合在一起时，您就得到了所谓的混合启发式方法。
在过去十年左右的时间里，探索混合启发式算法在优化“人群”中的优缺点已成为一种趋势。
关于这个主题，实际上有数百篇论文，其中很多都非常好。我见过一些论文，在每一代 GA 中对每个后代采用局部搜索（爬山，而不是禁忌）来引导每个后代达到局部最优。作者报告了良好的结果。我还看到过一些论文，其中使用遗传算法针对特定问题实例和一般情况来优化模拟退火算法的冷却时间表，并取得了良好的结果。我还读过一篇论文，它将禁忌列表添加到模拟退火算法中，以便它可以防止重新访问在过去 n 次迭代中看到的解决方案，除非满足某些愿望函数。
如果您正在研究时间表（正如您的其他评论所建议的那样），我建议您阅读 PATAT（自动时间表的实践和理论）的一些论文，特别是 EKBurke 和 P.Brucker 的论文，他们在该领域非常活跃且知名。许多 PATAT 论文集都是免费提供的。
尝试像这样进行学术搜索：
http://scholar.google.com/scholar?q=%22hybrid+heuristics%22+%22combinatorial+optimization%22+OR+timetabling+OR+scheduling&btnG=&hl=en& as_sdt=0%2C5&as_ylo=2006
证明收敛性非常困难这些类型的启发式数学。我见过模拟退火的马尔可夫链表示，它显示了收敛的上限和下限，并且 GA 也存在类似的东西。通常，您可以对一个问题使用多种不同的启发式方法，只有实验结果才能表明哪种方法更好。你可能需要做计算实验来看看你的 GA 是否可以通过 TS 或更通用的本地搜索来改进，但总的来说，混合启发式现在似乎是主流。
When you combine multiple heuristics together, you have what's referred to as a hybrid-heuristic.
It has been a trend in the last decade or so to explore the advantages and disadvantages of hybrid-heuristics in the optimisation "crowd".
There are literally hundreds of papers available on the topic and a lot of them are quite good. I have seen papers which employ a local-search (hill-climbing, not Tabu) for each offspring at each generation of GA to direct each offspring to the local optimum. The authors report good results. I have also seen papers which use a GA to optimise the cooling schedule of a simulated annealing algorithm for both a particular problem instance and also for a general case and have good results. I've also read a paper which adds a tabu list to a simulated annealing algorithm so that it prevents revisiting solutions it has seen in the past n iterations, unless some aspiration function is satisfied.
If you're working on timetabling (as your other comment suggests), I suggest you read some papers from PATAT (practice and theory in automated timetabling), particularly from E.K.Burke and P.Brucker who are very active and well-known in the field. A lot of the PATAT proceedings are freely available.
Try a Scholar search like this:
http://scholar.google.com/scholar?q=%22hybrid+heuristics%22+%22combinatorial+optimization%22+OR+timetabling+OR+scheduling&btnG=&hl=en&as_sdt=0%2C5&as_ylo=2006
It is very difficult to prove the convergence of these sorts of heuristics mathematically. I have seen a Markov chain representation of simulated-annealing which shows upper- and lower-bounds of convergence and there exists something similar for GA. Often you can use many different heuristics on a single problem, and only experimental results will show which is better. You may need to do computational experiments to see if your GA can be improved with a TS or more generic local search, but in general, hybrid heuristics seem to be the go these days.
我还没有将禁忌搜索与遗传算法结合起来，但我有将其与模拟退火相结合。这并不是真正的禁忌搜索，更多的是用禁忌增强其他算法。
根据我的经验，检查某些内容是否属于禁忌不会产生很高的性能成本。
I haven't combined tabu search with genetic algorithms yet, but I have combined it with simulated annealing. It's not really tabu search, it's more enhancing the other algorithm with tabu.
From my experience, checking if something is tabu doesn't have a high performance cost.