正在加载图片...
Vol.28 No.8 许剑等：带有侦察子群的蚁群系统 .795. 式中，心为一个常数，表示蚂蚁完成一次完整的 同时在迭代进程中，若出现停滞现象，可加大Q0 路径搜索后释放的信息素的总量；Lk(t)表示第k 或mg 只蚂蚁环游路径长度， 确定性选择保证大部分蚂蚁会走“主干道”， MMAS与AS的主要区别是：(I)每次迭代中 而侦察子群保证始终有一部分蚂蚁游历在外，在 只允许表现最好的蚂蚁更新路径上的信息素：(2) 搜索过程中动态的调整确定性选择概率、侦察子 为了防止过早的停滞现象，限定了痕迹浓度允许 群的大小和侦察子群随机概率，正是它们的共同 值的上下限[tmin,mm]:(3)在算法启动时将所有 作用才使ASSS具有更强的全局搜索能力， 支路上的痕迹浓度初始化为最大值ax;(4)采用 为了衡量解的多样性，特引入分散度Y,其定 了平滑机制(PTS),痕迹浓度的增加正比于max 义为某一代中每个解到其均值的绝对偏差的平均 和当前浓度(t)之差. 值.第t代解的分散度Y(t)计算公式为： 2带有侦察子群的蚁群系统(ASSS) ()g(! (5) 2.1带有侦察子群的状态转移规则 式中，Lk为第k只蚂蚁的周游长度，avg(t)为第t 现有的蚁群算法都是整个蚁群采用同一个转 代所有蚂蚁周游长度的均值.很明显分散度Y越 移规则，而实际上真实世界的蚁群是有明确分工 大，则说明解的分布越分散，解的多样性越好，反 的，总是有一小部分蚂蚁游历在大部队之外，他们 之亦然 的任务就是探询新的食物源或更好的路径，受此 2.2信息素更新策略 启发，本文提出一种与真实蚁群更加相符的带有 AS是对所有的蚂蚁进行全局更新，MMAS 侦察子群的状态转移规则，也就是说在整个蚁群 是仅对最优的蚂蚁进行更新，最优的蚂蚁可以是 中分出一个探路子群，这个子群以一定概率脱离 一次循环中最优的蚂蚁S,也可以是所有循环中 “主干道”去开辟新的路径，这样在保证算法收敛 最好的蚂蚁S中，只能选择其中之一，选择S有 的同时，增加了解的多样性，有利于算法跳出局部 助于跳出局部最优但降低了收敛速度，选择S中 最优，修改后的状态转移公式如下： 可以提高收敛速度却容易陷入局部最优.鉴于上 P(t)= 述分析，本文提出信息素更新策略为：同时选择 y/∑ k∈S,Q≤Q0,jZ S中和S的路径进行全局信息素更新，且相同的 1任z 边弧只更新一次，修改后的信息素更新公式如 arg max[奇()]”.[专， 0>01.jz 下： 、喻()， 其他 (4) +1)=()+a= 式中，Q是一个[0,1]随机变量，在蚂蚁k选择下 (t)十L驰 (Lh)2 (6) 一个城市之前由随机实验获得，Q0和Q1是事先 设定的阈值且Q0<Q1,Q0,Q1∈[0,1]，S是侦 L9， (i,j)∈T (7) 察子群，子群中蚂蚁可以随机选定或指定，子群大 L曲，(i,j)足T,(i,j)∈Tb 小m,根据整个蚁群规模而定并可适当改变.蚂 式中，T中和Tb分别对应着S中和Sb的环游路 蚁k在选择下一个城市之前先进行一次随机实 径，长度分别为L中和L曲.信息素更新浓度与 验获得Q,如果蚂蚁k属于侦察子群且Q≤Q0, L中成正比，与(L)子成反比，这样即保留了前面 则依式中第一项计算出的概率随机选择下一个城 循环的成果，提高了收敛速度，同时又降低了陷入 市，Q0称为侦察子群随机概率；如果Q>Q1,则 局部最优的风险， 无论蚂蚁k是否属于侦察子群，选择城市时都按 2.3采用LK变异算子 取最大值的情况转移，Q1称为确定概率；其他情 Lin&Kernighan算法是l971年由Lin和 况，则按式(1)的转移概率转移. Kernighan提出的一种解决TSP问题的有效的启 Q0,Q1和m。并不是一成不变，可以随着迭 发式方法，它是在k一opt局部搜索算法(local 代的进程动态调整：在迭代的开始阶段，为了增加 search)的基础上通过改变k来实现的， 解的多样性，可适当增大Q0、减小Q1;随着迭代 由于新的算法引入了侦察子群，增加了每一 的深入，为了加速收敛可适当减小Q0、增大Q1; 代解的多样性，使算法很容易跳出局部最优，但跳式中w 为一个常数表示蚂蚁完成一次完整的 路径搜索后释放的信息素的总量；Lk（ t）表示第 k 只蚂蚁环游路径长度． MMAS 与 AS 的主要区别是：（1）每次迭代中 只允许表现最好的蚂蚁更新路径上的信息素；（2） 为了防止过早的停滞现象限定了痕迹浓度允许 值的上下限［τminτmax ］；（3）在算法启动时将所有 支路上的痕迹浓度初始化为最大值 τmax；（4）采用 了平滑机制（PTS）痕迹浓度的增加正比于 τmax 和当前浓度 τij（ t）之差． 2 带有侦察子群的蚁群系统（ASSS） 2∙1 带有侦察子群的状态转移规则 现有的蚁群算法都是整个蚁群采用同一个转 移规则而实际上真实世界的蚁群是有明确分工 的总是有一小部分蚂蚁游历在大部队之外他们 的任务就是探询新的食物源或更好的路径．受此 启发本文提出一种与真实蚁群更加相符的带有 侦察子群的状态转移规则也就是说在整个蚁群 中分出一个探路子群这个子群以一定概率脱离 “主干道”去开辟新的路径．这样在保证算法收敛 的同时增加了解的多样性有利于算法跳出局部 最优．修改后的状态转移公式如下： P k ij（ t）＝ ηij／∑l∈／z ηil k ∈ SQ ≤ Q0j ∈／Z arg max｛［τ k ij（ t）］ α·［η k ij ］ β｝ Q ＞ Q1j ∈／Z P k ij（ t） 其他 （4） 式中Q 是一个［01］随机变量在蚂蚁 k 选择下 一个城市之前由随机实验获得Q0 和 Q1 是事先 设定的阈值且 Q0＜ Q1Q0Q1∈［01］．S 是侦 察子群子群中蚂蚁可以随机选定或指定子群大 小 ms 根据整个蚁群规模而定并可适当改变．蚂 蚁 k 在选择下一个城市之前先进行一次随机实 验获得 Q如果蚂蚁 k 属于侦察子群且 Q≤ Q0 则依式中第一项计算出的概率随机选择下一个城 市Q0 称为侦察子群随机概率；如果 Q＞ Q1则 无论蚂蚁 k 是否属于侦察子群选择城市时都按 取最大值的情况转移Q1 称为确定概率；其他情 况则按式（1）的转移概率转移． Q0Q1 和 ms 并不是一成不变可以随着迭 代的进程动态调整：在迭代的开始阶段为了增加 解的多样性可适当增大 Q0、减小 Q1；随着迭代 的深入为了加速收敛可适当减小 Q0、增大 Q1； 同时在迭代进程中若出现停滞现象可加大 Q0 或 ms． 确定性选择保证大部分蚂蚁会走“主干道” 而侦察子群保证始终有一部分蚂蚁游历在外在 搜索过程中动态的调整确定性选择概率、侦察子 群的大小和侦察子群随机概率正是它们的共同 作用才使 ASSS 具有更强的全局搜索能力． 为了衡量解的多样性特引入分散度 γ其定 义为某一代中每个解到其均值的绝对偏差的平均 值．第 t 代解的分散度γ（ t）计算公式为： γ（ t）＝ 1 m ∑ m k＝1 ｜Lk—avg（ t）｜ （5） 式中Lk 为第 k 只蚂蚁的周游长度avg（ t）为第 t 代所有蚂蚁周游长度的均值．很明显分散度 γ越 大则说明解的分布越分散解的多样性越好反 之亦然． 2∙2 信息素更新策略 AS 是对所有的蚂蚁进行全局更新MMAS 是仅对最优的蚂蚁进行更新最优的蚂蚁可以是 一次循环中最优的蚂蚁 S ib也可以是所有循环中 最好的蚂蚁 S gb只能选择其中之一选择 S ib有 助于跳出局部最优但降低了收敛速度选择 S gb 可以提高收敛速度却容易陷入局部最优．鉴于上 述分析本文提出信息素更新策略为：同时选择 S gb和 S ib的路径进行全局信息素更新且相同的 边弧只更新一次．修改后的信息素更新公式如 下： τij（ t＋1）＝ρτij（ t）＋ L gb L bestΔτbest ij ＝ ρτij（ t）＋ L gb （ L best ） 2 （6） L best＝ L gb （ ij）∈ T gb L ib （ ij）∈／T gb（ ij）∈ T ib （7） 式中T gb和 T ib分别对应着 S gb和 S ib的环游路 径长度分别为 L gb和 L ib．信息素更新浓度与 L gb成正比与（ L best ） 2 成反比这样即保留了前面 循环的成果提高了收敛速度同时又降低了陷入 局部最优的风险． 2∙3 采用 LK 变异算子 Lin＆Kernighan 算 法 是 1971 年 由 Lin 和 Kernighan 提出的一种解决 TSP 问题的有效的启 发式方法它是在 k—opt 局部搜索算法（local search）的基础上通过改变 k 来实现的． 由于新的算法引入了侦察子群增加了每一 代解的多样性使算法很容易跳出局部最优但跳 Vol．28No．8 许剑等： 带有侦察子群的蚁群系统 ·795·