何時使用帶遺傳算法的禁忌搜索？

Question

Tabu Search可能在Genetic Algorithms處使用。遺傳算法可能需要很多代才能獲得成功，所以在高性能下運行對他們來說很重要。禁忌搜索是爲了增強避免局部最大值和良好的記憶機制以通過迭代獲得更好的成功。然而禁忌搜索使得算法的效果比平常更慢。

我的問題是：

是否有關於何時使用禁忌搜索與遺傳算法，當沒有什麼研究？

Answer 1

我還沒有合併禁忌搜索與遺傳算法，但我有combined it with simulated annealing。這不是真的禁忌搜索，更多增強其他算法與禁忌。

從我的經驗看，檢查是否有禁忌沒有高性能成本。

Answer 2

一般來說，遺傳算法花費大量的時間取樣點，這些取樣點並不理想。假設你正在優化一個看起來像一對駝峯的函數。 GAs最初會把點轉移到這個地方，然後慢慢匯合到峯頂的點上。然而，即使是一個非常簡單的局部搜索算法也可以說明GA在駝峯的斜坡上產生的一點，並立即將它直接推到駝峯的頂部。如果讓GA產生的每一點都經過這個簡單的局部最優化，那麼最終GA只會搜索局部最優點的空間，這通常會大大提高找到最佳解決方案的機會。問題是，當你從真正的問題開始而不是駝峯時，簡單的本地搜索算法往往不夠強大，無法找到真正的本地最優解，但是像禁忌搜索這樣的東西可以用於它們的位置。

有兩個缺點。其一，GA的每一代更慢（但通常需要更少的世代）。二，你失去了一些多樣性，這可能導致你更頻繁地聚合到次優解決方案。

在實踐中，我會總是儘可能包括某種形式的本地搜索。沒有免費的午餐會告訴我們，有時候你會變得更糟糕，但是經過十年左右的時間來做專業的遺傳算法和本地搜索研究，我總是提出一個新的100美元的清單，說本地搜索能夠改善對於你真正關心的大多數情況。它不一定是禁忌搜索;你可以使用模擬退火，VDS，或只是一個簡單的下一登山爬山者。

Answer 3

當您將多個啓發式技術結合在一起時，您就有了所謂的混合啓發式。

在過去十年左右，探索優化「人羣」中混合啓發式的優缺點已成爲一種趨勢。

字面上有數百論文可用，其中很多都是相當不錯的。我已經看到了在每一代遺傳算法中爲每個後代使用本地搜索（登山，而不是禁忌）的論文，以便指導每個後代達到當地的最佳狀態。作者報告了良好的結果。我也看到了使用遺傳算法優化模擬退火算法的冷卻時間表的文件，既適用於特定的問題實例，也適用於一般情況，並且具有良好的結果。我還讀過一篇論文，其中添加了一個禁忌列表到模擬退火算法，以防止它在過去的n次迭代中看到的重新訪問的解決方案，除非某些願望函數得到滿足。

如果您正在制定時間表（正如您的其他評論所暗示的那樣），我建議您閱讀PATAT的一些論文（自動化時間表中的練習和理論），特別是來自EKBurke和P.Brucker，他們非常活躍，在該領域中已知。很多PATAT程序都是免費提供的。

嘗試Google學術搜索是這樣的：

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

這是非常困難的數學證明這些類型的啓發式的收斂。我已經看到了模擬退火的馬爾可夫鏈表示，它顯示了收斂的上界和下界，並且遺傳算法存在類似的情況。通常你可以在單個問題上使用許多不同的啓發式，只有實驗結果會顯示哪個更好。您可能需要進行計算實驗，以查看您的遺傳算法是否可以通過TS或更通用的本地搜索進行改進，但總的來說，混合啓發式似乎是最近的一次。