发布时间 : 星期三 文章基于群体智能的关联规则挖掘及应用更新完毕开始阅读
山东师范大学硕士学位论文
图1 人工蚁群路径搜索实例
Fig 1 The example of artificial ant colony searching path
如图1 (a) 所示,路径DH, BH 和BCD 的路程长度d 为1； C 是路径BCD 的中点。假设在每个单位时间内，有30 只蚂蚁从A 来到B， 30只蚂蚁从E来到D，每只蚂蚁单位时间内行进路程为1，蚂蚁在行进过程中在单位时间内留下1个浓度单位的信息素，1个浓度单位的信息素在一个时间段( t , t + 1) 结束后瞬间完全挥发。如图1(b) 所示,t = 0 时，在B 和D 点各有30只蚂蚁，由于此前路径上没有信息素,它们随机地选择路径， 在DH、DC、BH 和BC上各有15只蚂蚁。如图1(c) 所示， t = 1 时，又有30 只蚂蚁到达B 。它们发现在BH上的信息素浓度为15，BC上信息素浓度为30(是由15只BC走向和15只CB走向的蚂蚁共同留下的)， 因此选择BC路径的蚂蚁数的期望值是选择BH蚂蚁数的2倍。所以，20只蚂蚁选择BC，10只蚂蚁选择BH。同样的情况发生在D点。
这个过程一直持续下去直到所有人工蚂蚁最终选择最短路径BCD(或DCB ) 。具体过程见表1。
表1 人工蚁群路径搜索实例过程表
Tab 1 The table of artificial ant colony searching path
蚁数（取整）/只 步号 BC BH DC DH 1 15 15 15 15 2 20 10 20 10 3 24 6 24 6 4 27 3 27 3 5 29 1 29 1 6 30 0 30 0
蚁群算法中的人工蚂蚁和自然界中的真实蚂蚁相比主要有以下几点区别[20 ] 。(1) 人工蚂蚁具有记忆能力,而真实蚂蚁没有。人工蚂蚁可以记住曾经走过的路径或访问过的节
17
山东师范大学硕士学位论文
点,这样对提高算法效率是有益的。
(2) 人工蚂蚁选择路径的时候并不是完全盲目的,而是按一定算法规律有意识地寻找最短路径(如在旅行商问题中,可以预先知道下一个目标的距离) 。
(3) 人工蚂蚁生活在离散时间的环境中,即问题的求解规划空间是离散的,而真实蚂蚁生活在连续时间的环境中。人工蚁群系统正是有了这些不同于真实蚂蚁的特性,才使得该系统具有更高的智能性,在寻优过程中具有更高的效率,适合于解决更多类型的问题。
2.4.1.2具体描述
由于蚂蚁寻食的过程与旅行商问题(Traveling Salesman Problem ,简称TSP) 的求解非常相似,所以蚁群算法最早的应用就是TSP的求解。下面以求解n 个城市的TSP为例说明蚁群算法。TSP属于一种典型的组合优化问题。其定义是:给定n 个城市的集合,TSP 等价于寻找一条只经过各城一次的具有最短长度的闭合路径。设dij为城市i和j之间的距离，欧几里德空间中, dij= [（xi-xj）2+(yi-yj)2]1/2 。TSP 求解中,蚁群算法中的每只蚂蚁都可认为具有下列特征的简单智能体。
(1) 其选择城市的概率是城市之间的距离和连接支路上所包含的当前信息素余量的函数；
(2) 为了强制蚂蚁进行合法的周游,直到一次周游完成时,才允许蚂蚁游走已访问过的城市(这可由禁忌表tabuF 来加以控制) ；
(3) 当完成一次周游,它在每条访问过的支路( i，j) 上留下一种叫信息素的物质。 在蚁群算法基本的实施步骤中用到的变量和常数有: m，群体中蚂蚁的个数； dij，,表示城市i和j之间的距离，其中i，j?(1 , n) ，?ij(t)，表示t 时刻在ij 连线上残留的信息量。
初始时刻，各条路径上的信息量是相等的，设τ
ij
k (0) =c(c为常数)，蚂蚁k(k=1,2 ,
kij?, m) 在运动过程中,根据各条路径上的信息量决定转移方向。 p(t)表示在t时刻蚂蚁 由位置i转移到位置j的概率，
pkij
18
山东师范大学硕士学位论文
式中, F ={ n - tabuF}为蚂蚁k下一步允许选择的城市；tabuF ( F = 1 , 2 , ?, n) 记录蚂蚁k目前己经走过的城市 s为F中任意的城市；α和β分别表示蚂蚁在运动中所积累的信息及其启发因子在蚂蚁所选择路径中所起作用的不同；η
i j
为由城市i转移到城市
j的期望程度,在这里ηij取1/ dij 。随着时间的推移,以前留下的信息素逐渐消逝,用参数1-ρ表示信息素的消逝程度(ρ为信息素残留系数) ,经过n 个时刻蚂蚁完成一次循环,各条路径上的信息量根据式(2) 进行调整。
τ
ij
(t + n) =ρ×τ
kij
(t) +Δτ
ij
(2)
用??ij表示第k只蚂蚁在本次循环中留在路径上的信息量, 则k只蚂蚁在本次循环中留在路径上的总的信息量就表示为??ij 。确定??ij的方法见式(3) 。
式中, Q 为常数； Lk 为第k 只蚂蚁在本次循环中所走的路径长度。上述方法称为蚁周算法(ant-cyclealgorithm) 。根据??ij的另外两种取法可形成不同类型的蚁群算法:蚁量算法(ant-quantity algorithm)和蚁密算法(ant-density algorithm) ,具体的分析可以参考文献[20] 。
综上所述,蚁群算法的实现步骤如下:
第1 步,初始化相关参数。如蚂蚁的数目、迭代的次数等。 第2 步,将蚂蚁随机或均匀分布到各个城市。
第3 步,每只蚂蚁通过访问各个城市而形成一个解,并在访问的过程中,将已访问到的城市保留在tabuF 中。在城市i的每只蚂蚁要从没有访问的城市中选择访问下一个城市j时须根据概率公式(1) 进行选择,如此循环,直到所有的蚂蚁访问完所有的城市。 第4 步,计算每只蚂蚁行走的总路径长度Lk ，并保存最优解。 第5 步,利用式(2) 进行信息素的调整。
第6 步,判断系统是否满足停止的条件,这里的停止条件可以是最大的迭代次数、计算机
k 19
山东师范大学硕士学位论文
运行时间、或者是系统所要达到的数据精度等。如果不满足,则系统从第2 步开始循环;否则系统退出运行。
总体上说,蚁群算法最主要的特性如下: [1 ]
(1) 正反馈。正反馈机制能够扩大解的质量对个体选择路径的影响,使得算法能够快速地发现较好的解或最优解。
(2) 分布式计算。分布式计算要求个体独立地搜索最优解,而个体之间互不干扰,这对于避免过早收敛有一定的效果。
(3) 启发性。人工蚂蚁能够利用反映可行解质量的启发信息,借以指导自己的搜索方向,这使得算法在搜索过程的早期就能发现质量较好的解,而完全随机的选择路径,会造成早期搜索到的解的质量不高。
(4) 鲁棒性。通过稍加修改,就可以应用到其他类型的问题当中[21] 。
(5) 并行性。由于每个蚂蚁个体是独立地搜索可行解,容易实现该算法的并行化,从而提高算法效率。蚁群算法是一种设计思想独特,拥有较多优良特性的优化算法。近年来对这种算法的研究发展非常迅速。蚁群算法除了成功运用于在组合优化问题(如旅行商问题) 的求解以外,还运用到了其他的典型优化问题的求解中,例如调度问题[22] 、约束优化问题[23 ] 、规划问题[24] 、二次指派问题[25] 、着色问题[26]等。除了这些典型优化问题以外,还在交通、计算机、机器人设计及控制、电力系统、通信、化工及冶金等方面取得了令人满意的效果。
2.4.2微粒群（PSO）算法
微粒群算法与其他进化算法相似,也是根据对环境的适应度将群体中的个体移动到好的区域,不同之处在于它不像其他演化算法那样对个体使用演化算子,而是将每个个体看作寻优空间中的一个没有质量没有体积的微粒,在搜索空间中以一定的速度飞行,通过对环境的学习与适应,根据个体与群体的飞行经验的综合分析结果来动态调整飞行速度。在整个寻优过程中,每个微粒的适应值取决于所选择的优化函数的值,并且每个微粒都具有以下几类信息:微粒当前所处位置;到目前为止由自己发现的最优位置pbest ,以信息视为微粒的自身飞行经验;到目前为止整个群体中所有微粒发现的最优位置gbest ( gbest是在pbest中的最优值) ,这可视为微粒群的同伴共享飞行经验。于是,各微粒的运动速度受到自身和群体历史运动状态信息的影响,并以自身和群体的历史最优位置来对微粒当前的运动方向和运动速度加以影响,很好地协调了微粒自身运动和群体运动之间的关系。
20