《装备制造技术}0 8 2 0年第 l期 1

基于 MA L B的蚁群算法仿真研究 TA 野莹莹’付丽君’程立英，, (. 1沈阳理工大学信息科学与工程学院，辽宁沈阳 1 06; . 1 18 2沈阳师范大学物理科学与技术学院，辽宁沈阳 103 ) 10 4 摘要：介绍了基于 MATL B的蚁群算法仿真研究，罗里达州六城市旅行商问题进行了 MAT A A对佛 L B仿真，计算结果显示，作为新型进化算法，蚁群算法能够解决复杂组合优化问题。 关键词：蚁群算法； MAT A模拟进化算法； L B;优化 中图分类号： P 8 T 1文献标识码： A文章编号：6 2 5 5 2 0 1— 0 0 1 7— 4 X( 0 8)1 0 1 - 2 3

蚁群算法( n Cln l rh是一种新型模拟进化算 A t o yAg i m) o ot 法。2 0世纪 9年代初期，大利学者多戈里等人从生物进化 O意

2蚁群算法的系统模型 下面以解决旅行商问题( S ) T P来建立系统模型。旅行商问题是要求旅行商在个相互连通的城市中，寻找出一条连接所有城市的最短通路的问题作为组合优化领域里典型的易于。 描述却难以处理的 N P完全难题，S T P问题可能的路径数目与

和仿生学的角度出发，研究蚂蚁寻找路径的自然行为，提出蚁群算法[ 1]。目前，蚁群算法已经成为国际智能计算领域关注的 热点和前沿课题。

MA L B是 M tw rs司 1 8 TA ah ok公 9 4年推出的数学软件，其名称是由矩阵实验室 ( tx a oa r ) Mai L br o所合成， r ty因此可知，其最早的理念是提供一套完善的矩阵运算指令，可随着数值运算需求的转变， T A MA L B已经成为各种系统模拟和讯号处理 等方面的标准语言四。

城市数目是呈指数型增长的，求解非常困难。 求解个 n城市的对称旅行商问题的实现过程如下。假设 有 m只蚂蚁，它们随机放入到 n个城市当中。 . - S时刻将 b(￣ t t ) n

位于城市 i的蚂蚁个数，么 m= 。城市 i那∑b和城市之间 =

1

1蚁群算法原理 蚁群算法是受对真实蚁群行为研究的启发而提出的。蚂蚁这种群居动物，虽然个体的行为简单，但群体的行为却极其 复杂。们经过大量的研究，出蚂蚁个体之间通过一

种称为人得

的距离为也(=,,,,)t 12 3… n,时刻在连线上残留的信息量为 )在初始时刻， r ) (。设 =c c为常数 )在各条路径上，信息量相等。蚂蚁 k在运动过程中，根据各条路径上的信息量

决定转移方向。:) P表示在时刻蚂蚁由位置 i转移到位置的 概率：

外激素的物质进行信息传递。蚂蚁在移动过程中会分泌外激 素，且通过感知这种物质的存在及其强度，导自己的移动并指

方向。一般情况下，蚂蚁朝着外激素强度高的方向移动。也就是说，如果某一路径上走过的蚂蚁越多，留在这条路径上的外激素强度越大，么蚂蚁选择该路径的概率也就越大。那这是一种信息正反馈现象。蚂蚁之间就是通过这样的方式进行信息交换，以便快速地搜寻到食物[ 2】。 。

耋 a㈩Ⅱ o w e d 0,其他 .

其中表示由城市 i转移到城市 f的期望程度，一般取 仉 (=t。￡丁 ) ,

I B分别表示蚂蚁在运动过程中所积累的信息及

使用蚁群算法求解现实问题时，首先生成一定数量的人 工蚂蚁蚁群，为每一只人工蚂蚁建立一个解或解的一部分。并

启发式因子，在蚂蚁路径选择中所起到的不同作用。与真实蚂 蚁蚁群不同，工蚁群具有一定的记忆功能， t u∈1,人用 a b, 2 …

每只人工蚂蚁从问题的初始状态出发，根据“外激素”的浓度， 选择下一个要转移到的状态，直到建立起一个解。每只蚂蚁根据所找到的解的好坏程度，在所经过的状态上释放与解的质量成正比的“外激素”之后，。每只人工蚂蚁又重新开始新一轮的求解过程，直到预先确定的寻找过程结束，或者已经寻找到满意解。为了避免寻找过程过早的停滞，陷入局部最优，以可 引人“外激素”更新机制 。 收稿日期：0 8 0— 1 2 0— 8 2

,

m)来记录蚂蚁 k目前已经走过的城市。随着时间的推移， 以

前留下的信息逐渐消逝，参数(一p表示信息消逝的程度，用 1 ) 经过Ⅳ个时刻，蚂蚁完成一个循环。各个路径上的信息量要根据下式作调整： r(=| (+ O f ) D z△+。 )+ () 2

基金项目：阳理工大学青年教师科研启动专项基金资助项目沈 作者简介：野莹莹( 9 7 )女， 17一，辽宁朝阳人，讲师，硕士，研究

方向：智能自动化及应用；丽君 (9 1 )女，宁沈阳人，付 16一，辽副教授，硕士，研究方向：智能自动化及应用；程立英 (9 6 ), 17一女河北衡水人，助教，硕士，主要研究方向：计算机图形学、图像处理，计算机仿真。