·168 智能系统学报 第6卷 陷入局部最优解 r(t+n)=（1-p)·T(t)+△r(t), 2基于蚁群算法求解最小MPR集 △r,()=∑△) 使用图G=(V,E,W)描述本算法，其中V= 式中：p是信息素挥发参数，其中0<p<1;△r(t)表示 {0,1,2,…,n}是所有节点集合；E={(i,j),i≠j, 蚂蚁k在本次循环中在路径(i)上留下的信息量 i,jeV}用于描述采用的邻接表集合；W描述节点j 3)N。为迭代次数，m为蚂蚁数量.CIF:代表从节 的出度；T(t)表示在t时刻节点i和j之间的信息 点i到二跳节点上所有路径上的信息量. 量.实验观察表明，蚂蚁在运动过程中会留下一种信 3 改进的蚁群算法模型 息素，其后面的蚂蚁可根据前边走过的蚂蚁所留下 的信息量选择其要走的路径，一条路径上的信息量 在此对上述蚁群算法的模型进行相应的修改， 越多，蚂蚁选择这条路径的概率就越大).当W。=0 在Ant-Cycle模型中， 时，蚂蚁停止移动也即本次循环停止.数组In_d[] △r(t) (0≤l≤n)用来记录每个节点的入度，如果节点l不 「Q·S,若第k只蚂蚁在本次循环中经过路径(i)； 是二跳节点，那么nd[l]=0.该算法的目标是求 0,其他， 解节点的MPR集，其流程图如图4. 式中：Q表示信息素强度，它在一定程度上影响算法 的收敛速度；S。表示第k只蚂蚁在本次循环中节点 Init(N.NW) 开始 的总出度 在Ant-Quantity模型中， nd0]=> Y(MPR)nodell △r(t)= N rQ·S,第k只蚂蚁时间t和t+1之间经过路径)： 移动m只蚂蚁并依据公 0,其地， 式2)、(3)更新路径信息 在Ant-Density模型中， △r(t)= N=N 「Q,若第k只蚂蚁在时间t和t+1之间经过路径()： L0,其他. MPR覆盖 Y 所有二跳 MINMPR 这3种模型各有优劣，应根据具体的问题来选 节点 择相应的模型.假设蚂蚁的数量为m,节点的数量为 结束 n,循环次数为N。,那么当n足够大时，该蚁群算法 Max(SCIFi) MRP)-nodeli] 的时间复杂度仍然为T(n)=O(N。·n2·m).与基 于贪心策略的启发式算法相比，该算法的收敛速度 图4基于蚊群算法求解最小MPR集的流程图 Fig.4 The flow chart of solving minimal MPR set 较慢Io,但能保证所求MPR集合是最小的. 说明： 在Matlab实验中，采用2种拓扑结构进行实 1)对每个蚂蚁k(k=1,2,…,m)按概率p(t) 验.第1种拓扑结构为圆形分布，即采取与A. 移至下一符合条件的节点方这里的概率P(t)为 Qayyum等人相同的拓扑结构（如图2所示）：共有 50个节点，求节点S的最小MPR集.本实验中，设 [Ty(t)][wa(t)]8 P(t)= (allowed, 定m=20p=0.1、Q=1.2,经过多次实验确定参数 ed =1.5B=2.5(效果比较好)，分别用改进后的蚁 else. 群算法的3种模型进行实验，得出的收敛曲线如图 式中：allowed:表示蚂蚁k下一步允许走过的节点 5所示.第2种拓扑结构是理想的均匀分布（如图3 的集合；α为信息启发因子；B为期望启发因子 所示)，求黑色节点的最小MPR集，在实验中，同样 2)更新路径上的信息强度.为了避免残留信息 设定m=20p=0.1、Q=1.2、a=1.5、B=2.5,再分 素过多引起残留信息淹没启发信息，在每只蚂蚁走 别用改进后的蚁群算法的3种模型进行实验，得出 完n个节点后，要对各路径上的信息量作更新： 的收敛曲线如图6所示