蚁群算法(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