螞蟻系統
最早的蟻群算法,其在小規模TSP中性能尚可,再大規模TSP問題中性能下降,容易停滞。其解決旅行商問題(TSP)過程大緻如下:
在初始時刻,m隻螞蟻被随機的放到城市中,在各條路徑上的資訊素初始值相等。
螞蟻按照随機比例規則從允許的城市中選擇下一個城市:
p_j = \frac{(\tau_j)^\alpha (\eta_j)^\beta}{\sum (\tau_j)^\alpha (\eta_j)^\beta}pj=∑(τj)α(ηj)β(τj)α(ηj)β
τ為資訊素,η 為啟發式因子,a_k 為下一步被允許城市的集合。
使用禁忌表記錄螞蟻走過的城市,不允許螞蟻選擇已經通路過的城市。
所有螞蟻完成一次周遊後,計算每隻螞蟻的路徑長度,儲存最短路徑長度。
更新每個城市資訊素:
τ=(1−ρ)τ+∑Δτ, 0≤ρ≤1
Δτ=1/d
由上可知,先揮發資訊素,再增加資訊素。其中d為路徑距離,路徑越短,資訊素增加越多。∑Δτ表示所有本次覓食過程中所有經過此城市的覓食成功的路線的資訊素累加。
清空禁忌表,開始下一次周遊。
精英螞蟻系統
對算法每次循環之後給予最優路徑額外的資訊素。
對于普通路徑中的每個城市:
τ(t+1)=(1−ρ)τ(t)+∑Δτ
對于最優路徑中的每個城市:
τ(t+1)=(1−ρ)τ(t)+∑Δτ+eΔτ^(bs)
Δτ^(bs)=1/L
其中L代表最優路徑長度,e是一個參數,表示權值大小。
最大-最小螞蟻系統
目前解決TSP問題最好的蟻群算法之一,在螞蟻系統的基礎上進行了如下更改:
- 資訊素被限制在[τmin , τmax]。
- 資訊素的初始值被設定為取其上界。
- 隻有最優路徑上的資訊素會被增加,其他城市的資訊素隻揮發。
對于一般城市: τ(t+1)=(1−ρ)τ(t)
對于最優路徑上的城市:τ(t+1)=(1−ρ)τ(t)+∑Δτ