遺傳算法vs模擬退火時間表

Question

我正在開發一個時間表應用程序。遺傳算法相對於模擬退火有哪些相對優勢？

---

我有針對我的情況下，這些點：

1. 在一個單一的時間，我們是最大的 （3位老師X 6小時）X（分配3班×35小時工作）在一次去，我們迭代建立時間表。

2. 將會有不可能的狀態和任何不可能的時間表必須通知沒有應用程序卡住我們希望這個應用程序被推到極限。

3. 它必須返回常數時間的結果或報告它失敗。

Answer 1

首先，我不得不說，它看起來像一個很小的解決方案空間：你確信蠻力並不是你最簡單的方法嗎？第二，你的意思是說你需要一個「相當不錯」的結果，或者你需要算法是O（1）嗎？我不會說這是不可能的，但是......呃，我很確定這是不可能的。

在具體點上，GA和SA之間的主要區別在於SA本質上是一種爬山算法，它從解空間的最後一點搜索「向外」，而GA是概率性的並在解中搜索超平面空間。

你說兩件事讓我覺得SA更適合你的問題：「迭代構建」和「不可能的狀態」。由於GAs在解決方案空間中的超平面上重新組合了「相當不錯」的解決方案，因此他們傾向於在解決方案空間中「重新發現」死區。如果您確信可以從一個非常好的解決方案中迭代構建更好的解決方案，那麼您處於爬山領域並且SA可以更好地適應。

非常普遍，GAs的相對優勢在於它們可以快速處理大量的解決方案空間，但它們依賴於在該解決方案空間內短暫編碼的「好主意」。 SA的相對優勢在於它搜索局部解決方案空間「圍繞」其初始解決方案，這往往會有效地找到局部改進。缺點是SA隨機播種，因此在探索大型解決方案空間時效率不高。