在MAX-MIN螞蟻系統（MMAS）中，如果最初的信息素尚未找到，它如何依賴最佳解決方案？

Question

我正在學習如何將max-min ant系統添加到我當前的ant系統中。從我讀過的審判信息素被初始化TMAX，TMAX的計算方法是，

tMax = 1/best tour length 

但究竟會是可能的，如果它依賴於一個旅遊這尚不初始化蹤跡信息素TMAX存在？

tMin還取決於tMax，這也使得它不可能在沒有最佳解決方案的情況下進行初始化。

Answer 1

在MMAS，所有邊緣被初始化爲TAUMAX，但TAUMAX的定義是從您上面說什麼稍有不同：

tauMax <-- 1/(rho * bestTourSoFarLength), 

其中RHO是蒸發率（通常設定到0.5），並且到目前爲止，關注巡迴長度最好是（見下文）。在算法執行過程中，tauMax會重複更新，每次現有最佳遊覽（到目前爲止）都會更新。

對於初始化，啓發式地構建初始可行路線。通常，使用隨機起始城市的最近鄰居遊覽。回想一下，在諸如蟻羣優化（ACO）/ MMAS的隨機優化方法的情況下，我們通常不能證明算法終止時最好的現行解決方案（巡迴）的最優性（然而，我們從實踐中知道ACO/MMAS在一些問題上表現出色，特別是旅行商問題（TSP）的變化）。因此，在這些背景下，「最佳解決方案」一詞不嚴格地表示不同作者的不同含義; 「迄今爲止最好的」，「最好的算法終止」等等，所以在閱讀關於這個主題的文獻時要注意。最後，作爲一個說明，tauMin依賴於---就像你已經注意到---在tauMax上一樣，但通常在初始化之後不會更新。當施加信息素限制時，重要的「動態」部分是單調遞減的tauMax，而大多數邊緣的信息素最終會由於蒸發而落在恆定的tauMin上。 TAUMIN的合適值由可怕表達式（基於經驗數據）

tauMin = tauMax*(1-(0.05)^(1/n))/((n/2-1)*(0.05)^(1/n)).