蟻群算法(ACO)原理梳理及應用細節 - 附求解VRPTW c++代碼

文章目錄

• 1、Introduction
• 2、ACO元啟發式算法
• • 2.1 ACO中螞蟻的行為細節
  • 2.2 ACO構造解的過程
  • 2.3 資訊素的消失和維持
• 3、ACO應用于VRPTW問題
• 4、ACO算法的改進方法
• • 4.1 精英政策-elitist strategy
  • 4.2 等級螞蟻體系-rank-based version of Ant System( A S r a n k AS_{rank} ASrank​)
  • 4.3 資訊素重置
  • 4.4 ACO和LS結合
  • 4.5 候選清單-candidate lists
• 5、ACO求解VRPTW代碼已上傳值GitHub

1、Introduction

\qquad 蟻群算法(Ant Colony Optimization)是一種求解組合優化問題的元啟發式算法。蟻群算法的思想起源于螞蟻依靠共享資訊素(pheromone)資訊來尋找最短路徑的現象，在ACO中，蟻群中的螞蟻依靠資訊素為指導來構造和改進解方案。

\qquad 目前蟻群算法在靜态優化問題和動态優化問題之中都有廣泛的應用。蟻群算法作為構造算法(construction heuristic)的一種拓展算法，在構造的過程中将資訊素資訊考慮進去來構造解方案。

2、ACO元啟發式算法

\qquad ACO算法在疊代構造解的過程之中應用到的資訊包括以下兩個方面：1) 算例的啟發式資訊(如路徑問題中的距離)；2) 反應螞蟻路徑搜尋軌迹的資訊素。

2.1 ACO中螞蟻的行為細節

\qquad 給定一個圖網絡 G = ( C , L ) G=(C,L) G=(C,L)，其中 C C C表示圖的組成成分(節點)， L L L表示圖的邊。在執行ACO算法構造解的過程中，可以使用**“hard way”來構造的解，所有的解均不可以違反限制，也可以使用“soft way”**來構造解，某些解可以違反某些限制，但是這種解需要根據違反限制的程度來添加懲罰項(penalization)。

\qquad 定義資訊素 τ \tau τ（ τ i \tau_i τi​若資訊素和網絡中的節點相關聯， τ i j \tau_{ij} τij​若資訊素和網絡中的邊相關聯；啟發式資訊 η \eta η（ η i \eta_i ηi​若和節點相關聯， η i j \eta_{ij} ηij​若和邊相關聯）。在ACO中，系統之中的每一個螞蟻 k k k具有以下特點：

\qquad 1）它通過探索網絡 G = ( C , L ) G=(C,L) G=(C,L)來構造費用最小的解方案；

\qquad 2）每一個螞蟻 k k k會有一個記錄自己通路過路基的記憶 M k M^k Mk，這個記憶資訊可以用來繼續構造可行解，來評判已經得到的解的優劣和更新資訊素。

\qquad 3）當螞蟻 k k k在狀态 x r = < x r − 1 , i > x_r=<x_{r-1}, i> xr​=<xr−1​,i>将要向節點 j ∈ N i k j \in N_i^k j∈Nik​移動時（ N i k N_i^k Nik​表示螞蟻 k k k在節點 i i i時的可行鄰域），産生的新的狀态 < x r , j > <x_r,j> <xr​,j>可以可行或者不可行。

\qquad 4）每一個螞蟻通過機率選擇函數來選擇移動方向，其中機率選擇函數中包含的資訊有：資訊素，啟發式資訊，螞蟻目前記憶資訊和問題限制資訊。

\qquad 5）當終止條件滿足時，終止螞蟻的解方案建構。若不允許産生不可行解方案，則當構造不可行時，停止構造。

\qquad 6）“步進資訊素更新”（step-by-step pheromone update），表示每一次添加新的節點到某個螞蟻的解之中，都需要對這個螞蟻的資訊素進行更新。

\qquad 7）“線上延遲資訊素更新”（online delayed pheromone update），表示在一個解方案構造完畢之後，在回溯整個解方案進行資訊素的更新。

2.2 ACO構造解的過程

\qquad 一個蟻群之中的螞蟻并發地向網絡 G G G中的鄰域狀态進行拓展來分别構造各自的路徑，他們移動的方向收到機率選擇函數的指導，通過不斷的移動，每一個螞蟻都向着構造組合優化問題的解方向靠近。一旦某個螞蟻構造成功一個解方案，這個螞蟻評估構造的解方案的優劣并進行資訊素的更新。更新完畢的資訊素又會通過機率選擇函數指導後續螞蟻的解方案構造過程。

2.3 資訊素的消失和維持

\qquad 資訊素的消失(evaporation) 是将之前螞蟻更新的資訊素随着疊代次數的增加逐漸減小的過程。資訊素的消失可以有效避免解太快收斂到一個局部最優解，同時可以幫助探索新的求解空間。

\qquad 資訊素維持(daemon) 可以幫助提高算法局部尋優的效果，在實際操作中，可以通過選擇目前解方案最優的解，将目前最優解的資訊素的更新占比加大，來提高最優解對于後續尋優的影響，這個過程也稱為“離線資訊素更新機制”off-line pheromone update。

3、ACO應用于VRPTW問題

\qquad 初始化将每個螞蟻 k k k放在互不相同的一個客戶點上，作為螞蟻 k k k第一個通路的客戶點，并且每個螞蟻需要記錄自己通路的路徑序列，通路時間和載重量資訊(memory)，之後螞蟻 k k k向分别向其他城市進行拓展，在第 t t t次疊代時，位于客戶點 i i i的螞蟻 k k k向客戶點 j j j拓展的機率選擇函數如下所示：

\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad p i j k ( t ) = [ τ i j ( t ) ] α ⋅ [ η i j ] β ∑ l ∈ N i k [ τ i l ( t ) ] α ⋅ [ η i l ] β ,   i f j ∈ N i k (1) p_{ij}^k(t)={[\tau_{ij}(t)]^\alpha·[\eta_{ij}]^\beta \over \sum_{l \in N_i^k} [\tau_{il}(t)]^\alpha · [\eta_{il}]^\beta }, \ if \quad j \in N_i^k \tag{1} pijk​(t)=∑l∈Nik​​[τil​(t)]α⋅[ηil​]β[τij​(t)]α⋅[ηij​]β​, ifj∈Nik​(1)

\qquad 其中， η i j = 1 d i j \eta_{ij} = {1 \over d_{ij}} ηij​=dij​1​是實作可以獲得的啟發式資訊， α \alpha α和 β \beta β是決定資訊素和啟發式資訊影響程度的參數， N i k N_i^k Nik​是螞蟻 k k k的可行鄰域，表示從客戶點 i i i可以拓展的客戶點集合。若将 α \alpha α取值為0，則将不考了資訊素對于後續解方案構造的影響，則距離客戶點 i i i越近的客戶點越容易被選中；若 β \beta β的取值為0，則将隻考慮資訊素的影響來建構解方案，将出現停滞現象(stagnation situation)，即後續蟻群構造的解方案都将相同，不利于向最優解方向進行繼續尋優。

\qquad 當一個螞蟻構造完一個解方案之後，通過更新完的解方案來更新資訊素，更新方式如下所示：

\qquad \qquad \qquad \qquad \qquad \qquad \qquad ∀ ( i , j ) τ i j ( t + 1 ) = ( 1 − ρ ) ⋅ τ i j ( t ) + ∑ k = 1 m Δ τ i j k ( t ) (2) \forall (i,j) \quad \tau_{ij}(t+1)=(1-\rho)·\tau_{ij}(t)+ \sum_{k=1}^{m} \Delta \tau_{ij}^k(t) \tag{2} ∀(i,j)τij​(t+1)=(1−ρ)⋅τij​(t)+k=1∑m​Δτijk​(t)(2)

\qquad 其中， ρ \rho ρ是資訊素消失的速率系數，其值越大，資訊素消失的越快； m m m表示蟻群中螞蟻的個數。 Δ τ i j k ( t ) \Delta \tau_{ij}^k(t) Δτijk​(t)表示螞蟻 k k k在弧 ( i , j ) (i,j) (i,j)上留下的資訊素的數值，其計算方式如下所示：

\qquad \qquad \qquad \qquad \qquad \qquad \qquad Δ τ i j k ( t ) = { 1 / L k ( t ) , 如果螞蟻 k 通路了邊edge(i,j) 0 , otherwise (3) \Delta \tau_{ij}^k(t) = \begin{cases} 1/L^k(t), & \text {如果螞蟻$k$通路了邊edge(i,j)} \\ 0, & \text{otherwise} \end{cases} \tag{3} Δτijk​(t)={1/Lk(t),0,​如果螞蟻k通路了邊edge(i,j)otherwise​(3)

\qquad 其中， 1 / L k ( t ) 1/L^k(t) 1/Lk(t)表示第 k k k個螞蟻通路路徑的長度。通過上式可知，螞蟻建構路徑的長度越短，則這個螞蟻路徑通路過的弧的資訊素的量越大。通常情況下，被許多螞蟻使用的弧和在較短路徑中使用的弧可以獲得更多的資訊素，進而在未來路徑的建構之中更易被選到來建構路徑。

4、ACO算法的改進方法

4.1 精英政策-elitist strategy

\qquad 精英政策的思想在于基于目前最優解額外的資訊素更新權重，在每一次資訊素更新時，對于目前全局最優解中包含的弧給與額外的資訊素權重，通過系數 e e e來實作。應用了精英政策的上式(3)變為如下所示的形式：

\qquad \qquad \qquad \qquad \qquad \qquad \qquad Δ τ i j g b ( t ) = { e / L g b ( t ) , 如果目前最優解的螞蟻 k 通路了邊edge(i,j) 0 , otherwise (4) \Delta \tau_{ij}^{gb}(t) = \begin{cases} e/L^{gb}(t), & \text {如果目前最優解的螞蟻$k$通路了邊edge(i,j)} \\ 0, & \text{otherwise} \end{cases} \quad \tag{4} Δτijgb​(t)={e/Lgb(t),0,​如果目前最優解的螞蟻k通路了邊edge(i,j)otherwise​(4)

\qquad 其中 L g b L^{gb} Lgb表示目前最優解的路徑長度(成本)。

4.2 等級螞蟻體系-rank-based version of Ant System( A S r a n k AS_{rank} ASrank​)

\qquad A S r a n k AS_{rank} ASrank​是精英政策的一種拓展政策，在ACO的所有解構造完成之後，将所有的解按照成本大小從小到大進行排序，值選擇前 w − 1 w-1 w−1個解方案和目前最優解方案進行資訊素的更新。第 r r r個螞蟻的解方案對于資訊素更新的權重取值為： m a x { 0 ,   w − r } max\{0,\ w-r\} max{0, w−r}，目前最優解對于資訊素更新的權重取值為： w w w。在 A S r a n k AS_{rank} ASrank​下的上式(2)的表示形式如下所示：

\qquad \qquad \qquad \qquad ∀ ( i , j ) τ i j ( t + 1 ) = ( 1 − ρ ) ⋅ τ i j ( t ) + ∑ r = 1 w − 1 ( w − r ) Δ τ i j r ( t ) + w ⋅ Δ τ i j g b ( t ) (5) \forall (i,j) \quad \tau_{ij}(t+1)=(1-\rho)·\tau_{ij}(t)+ \sum_{r=1}^{w-1} (w-r)\Delta \tau_{ij}^r(t)+w·\Delta\tau_{ij}^{gb}(t)\tag{5} ∀(i,j)τij​(t+1)=(1−ρ)⋅τij​(t)+r=1∑w−1​(w−r)Δτijr​(t)+w⋅Δτijgb​(t)(5)

\qquad 其中， Δ τ i j r ( t ) = 1 / L r ( t ) \Delta \tau_{ij}^r(t)=1/L^r(t) Δτijr​(t)=1/Lr(t)， Δ τ i j g b ( t ) = 1 / L g b \Delta\tau_{ij}^{gb}(t)=1/L^{gb} Δτijgb​(t)=1/Lgb。

4.3 資訊素重置

\qquad 當連續一定疊代次數沒有對目前解進行優化，或者總疊代次數達到一定的次數時，可以将資訊素重置為初始化水準，進而達到改變求解空間的效果。

4.4 ACO和LS結合

\qquad 在進行ACO的過程之中可以嵌入LS算法來局部優化每一個螞蟻找到的解方案，同時優化之後的解方案被用來進行資訊素的更新操作。

4.5 候選清單-candidate lists

\qquad 當求解問題的鄰域空間較大時，蟻群之中的螞蟻很可能不在同一個求解空間之中，使得ACO的求解效率大大降低。為了彌補這一缺陷，可以使用候選清單的方式。對于VRPTW問題，在實際操作中，對于每一個客戶點 i i i，其候選清單包含 c l cl cl個與之距離最近的客戶點，在建構解方案的過程中，首先選擇候選清單中的客戶點進行解方案的建構，之後再從其餘客戶點中選擇客戶點進行解方案的建構。

5、ACO求解VRPTW代碼已上傳值GitHub

https://github.com/Dragon-wang-fei-long/Huristic-code/tree/Dragon-wang-fei-long-ACO