一种改进的蚁群算法
第２７卷增刊哈尔滨工程大学学报
Ｖｂｌ．２７
Ｓｕｐｐｌ．２００６年７月
Ｊｏｕｍａｌ
ｏｆ
Ｈａｒｂｉｎ
Ｅｎｇｉｎｅｅｒｉｎｇ
ＵｎｉＶｅｒｓｉｔｙ
Ｊｕｌ．２００６
一种改进的蚁群算法
张昕１，一，彭
宏１，郑启伦１
（１．华南理工大学计算机科学与工程学院，广东广州
５１０６４０；２．华南农业大学理学院，广东广州
５１０６４２）
摘要：蚁群算法是一种新的进化算法，其基本思想是模拟蚂蚁的合作行为．蚁群算法已成功地应用于许多优化问题，成为求解组合优化问题的新的进化算法．最新研究表明蚁群算法是一种基于群体的强鲁棒性的进化算法．但是，蚁群算法也有收敛速度慢，容易陷入局部最优的缺点．为了克服这些缺点，吸取微粒群算法的优点，提出了一种改进的蚁群算法．实验结果表明改进算法是有效的，与标准的蚁群算法相比，算法性能得到了明显改善．关键词：蚁群算法；ＴｓＰ问题：信息素：微粒群算法中图分类号：ＴＰ３叭．６
文献标识码：Ａ
文章编号：１００６．７０４３（２００６）增一０５１８．０５
Ａｎｉｍｐｒ０Ｖｅｄａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍ
ＺＨＡＮＧＸｉｎｌ…，ＰＥＮＧＨｏｎ９１，ＺＨＥＮＧ
Ｑｉ—ｌｕｎｌ
（１．ｃ０１１ｅｇｅｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａＩｌｄＥｎｇｉｎｅｅｒｉｎｇ，ＳｏｕｍＣｍｎａｕＩｌｉＶｅｒｓ时ｏｆＴｅｃｈｎｏｌｏｇｙ，ＧｕａＩｌｇｚｈｏｕ５１０６４０，ｃｈｉｎａ；２．ｃｏｌｌｅｇｅｏｆＳｃｉｅｎｃｅｓ，ＳｏｕｍＣｌｌｉｎａ
Ａ鲥ｃｕｌｔｕｍｌＵＩｌｉＶｅｒｓ咄ＧｕａＩｌｇｚｈｏｕ５１０６４２，ＣｌｌｉＩｌａ）
Ａｒｔｉｆｉｃｉａｌａｎｔｃｏｌｏｎｙａｌｇｏｒｉ廿ｌｍ（ＡＣＡ）ｉｓ
ｎｅｗｉｎｔｈｅｅｖｏｌｕｔｉｏｎ
ｃｏｍｐｕｔｉｎｇ．Ｔｈｅｂａｓｉｃｉｄｅａｉｓ
ｔｏ
ｉｍｉｔａｔｅｔｈｅｃｏｏｐｅｒａｔｉＶｅ
ｂｅｈａｖｉｏｒｏｆａｎｔｃｏｌｏｎｉｅｓ．ＡＣＡｈａｓａｃｌｌｉｅｖｅｄｗｉｄｅｓｐｒｅａｄｓｕｃｃｅｓｓ
ｉｎｓｏｌｖｉｎｇ
ｄｉｆ艳ｒｅｎｔｏｐｔｉＩＩｌｉｚａｔｉｏｎｐｒｏｂｌｅｍｓ，ｅｓｐｅｃｉａｌｌｙｉｎ
ｓｏｌｖｉｎｇ
ｃｏｍｂｉｎａｔｏｒｉａｌｏｐｔｉＩＩｌｉｚａｔｉｏｎｐｒｏｂｌｅｍｓ．Ｔｈｅｐｒｉｍａｒｙｓｔｕｄｙｓｈｏｗｓｉｔｉｓ
ａ
ｂｅｔｔｅｒｒｏｂｕｓｔ
ａｌｇｏｒｉｔｌｌｍｂａｓｅｄ
ｏｎ
ｐｏｐｕｌａｔｉｏｎ，ｂｕｔｉｔ
ｈａｓｓｏｍｅｓｈｏｒｔｃｏｒｎｉｎｇｓｓｕｃｈａｓ
ｉｔｓｓｌｏｗ
ｃｏｍｐｕｔｉｎｇｓｐｅｅｄ，ａｎｄｉｔｉｓｅａｓｙ
ｔｏ
ｆａｌｌｉｎｌｏｃａｌｐｅｄｋｉｎｌａ唱ｅｓｃａｌｅｐｒｏｂｌｅｍ．ＴｂｏＶｅｒｃｏｍｅ
ｔｈｅｓｅｄｅｆｉｃｉｅｎｃｉｅｓ，ａｎ
ｉｍｐｍｖｅｄ锄ｔ
ｃｏｌｏｎｙ
ａｌｇ砸ｍｍ
ｉｓ
ｄｅｓｉｇｎｅｄ
ｍｍｕｇｈａｂｓｔｒａｃｔｉｎｇｍｅａｄｖａｎｔａｇｅｓ研ｐａｎｉｃｌｅｓｗａｎｎ
ｏｐｔｉＩＩｌｉｚａｔｉｏｎ（ＰＳ０）．Ｔｈｅ
ｒｅｓｕｌｔｓｏｆ
ｍｅｅｘｐｅｒｉｍｅｎｔｓｕｇｇｅｓｔｍａｔｍｅｉｍｐｒｏｖｅｄａｌｇｏｒｉｔｌｌｍｉｓｅ仃ｅｃｔｉＶｅ．Ｒｅｓｕｌｔｓ
ａｒｅ
ＶｅｒｙｐｒｏｌＩｌｉｓｉｎｇ
ｃｏｍｐａｒｅｄｔｏｍｅｃｏｒｒｅｓｐｏｎｄｉｎｇｒｅｓｕｌｔｓｏｆｍｅｓｔａＩｌｄａｒｄａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｌｌｍ，ｉｎｄｉｃａｔｉｎｇｔｈｅｓｕｐｅｒｉｏｒｉｔｙｏｆｔｌｌｅｎｅｗｓｃｈｅｒｎｅ．Ｋｅｙｗｏｒｄｓ：ａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔＩｌｍ（ＡＣＡ）；ＴＳＰ；ｐｈｅｍｍｏｎｅ；ｐａｒｔｉｃｌｅ
ｓｗａｍ
ｏｐ血１ｌｉｚａｔｉｏｎ（ＰＳＯ）
蚂蚁在寻找食物时，总是能找到较短的路径．ＭａＸ—Ｍｉｎ
ＡＳ（ＭＭＡＳ）‘７１、Ｄ耐ｇｏ，ＧａＩＩｌｂａｒｄｅｌｌａ提出
受此启发，意大利学者ＭａｃｒｏＤｏｒｉｇｏ，ＶＭａＩｌｉｅｚｏｏ，
的ＡＪｌｔＣｏｌｏｎｙＳｙｓｔｅｍ（ＡＣＳ）删、结合Ｑ—Ｌｅａｍｉｎｇ提
Ａ．Ｃｏｌｏｍｉ等于２０世纪９０年代提出了Ａｎｔ
出的Ａｎｔ．Ｑ算法【９］等等．本文吸收微粒群算法的精华Ｓｖｓｔｅｍ（ＡＳ）【ｌＪ．蚁群算法通过由候选解组成的群体的
思想，提出了一种能够避免过早收敛的改进的蚁群进化过程来寻求最优解，特别适合于在离散优化问算法．实验结果表明，该算法具有较好的性能．
题的解空间进行多点非确定性搜索，已应用于旅行商问题、二次分配问题等多个经典离散组合优化问１基本的蚁群算法
题【２。６Ｊ，成为求解组合优化等ＮＰ－ｈａｒｄ问题的一种蚁群算法是对真实蚁群协作过程的模拟．每只非常有潜力的演化算法．但该算法存在进化速度较蚂蚁在候选解的空间中独立地搜索解，在所寻得的慢，容易陷入局部最优的问题．因此，许多学者对蚁解上留下一定的信息量．解的性能越好，蚂蚁留在其群算法提出了改进方法．如Ｓｔｎｔｚｌｅ，Ｈｏｏｓ提出的
上的信息量也越大，而信息量越大的解被再次选择的可能性也越大．在算法的初级阶段，所有解上的信收稿日期：２００６．０３—１１。
息量都是相同的，随着算法的推进，较优解上的信基金项目：国家自然科学基金资助项目（３０２３０３５０）息量逐渐增加，算法最终将收敛到最优解或近似最
作者简介：张昕（１９６８．），男，讲师，博士研究生；
彭宏（１９５８一），男，教授，博士；优解．
郑启伦（１９３８一），男，教授．
万
方数据Ａｂｓｔｒａｃｔ：
增刊张昕，等：一种改进的蚁群算法
・５１９・
以求解平面上，ｚ个城市的ＴＳＰ问题为例说明蚁群系统的基本模型．旅行商问题就是给定，ｚ个城市的位置和两两城市之间的距离，要求确定一条经过各城市当一次且只有一次的最短路线．其图论描述为：给定图（Ｖ，Ａ），其中Ｖ为顶点集，Ａ为各顶点相互连接组成的边集，已知各顶点问的连接距离，要求确定一条长度最短的回路，即遍历所有顶点一次且只有一次的最短回路．
为了更好地说明问题，首先引入如下记号：ｍ：蚁群中地蚂蚁数量；
反（ｆ）：ｆ时刻位于城市ｉ的蚂蚁的个数，ｍ＝∑包（ｆ）；
扛１
吒：两城市ｆ和Ｊ之间的距离；
吃ｊ：边（ｆ，Ｊ）的能见度，反映城市ｉ转移到城市
Ｊ的启发程度，一般可初始化为彤ｄ；
互，：边（ｆ，Ｊ）上的信息素轨迹强度；
△互，：蚂蚁忌在边（ｆ，Ｊ）上留下的单位长度轨迹信息素量；
硭：蚂蚁五：的转移概率，－『是尚未访问的城市．
每只蚂蚁都是具有如下特征的简单实体：
１）在从城市ｉ到城市歹的运动过程中或是在完成一次循环后，蚂蚁在边（ｆ，，）上释放一种物质，成为信息素轨迹；
２）蚂蚁按概率选择下一个将要访问地城市，这个概率是城市间的距离和连接两城市的路径上存有的轨迹量的函数；
３）为了满足问题的约束条件，在完成一次循环以前，不允许蚂蚁选择已经选择过的城市．
初始时刻，各条路径上的信息素量相等，设互，＝Ｃ（Ｃ为常数）．蚂蚁七（忌＝１，２，３，…，ｍ）在运动过程中根据各条路径上的信息素量决定转移方向．蚁群系统使用随机比例转移规则进行状态的转移．转移规则给出了位于城市ｆ的蚂蚁尼选择移动到城
万
方数据市歹的概率．在ｆ时刻，蚂蚁尼在城市ｉ选择城市歹
的转移概率群为群（ｆ）＝
＜
ｆ管（ｆ）劈（ｆ）／∑《（ｆ）磋（ｆ），．，∈ａ１１０ｗｅｄ
，＊甜ｆｏｗ耐
【
ｏ．ｏｍｅｒｓ式中：ａ１１０ｗｅｄ＝｛Ｏ，１，…，，ｚ一１）称为禁忌表，表示蚂蚁尼下一步允许选择的城市．在蚁群系统中其状
态的转移规则采用伪随机比例规则，按如下所示：
』ｍ：ａｘｔ—揣，Ｊ∈ａ，ｂｗｅｄ，ｇ≤ｇ。
“ａｌｌｏ”ｅｄ
ｉｆ
【ｓ．
ｏｍｅｒｓａｃｃｏｒｄｉｎｇｔｏ（１）
式中：ｑ是一个在【０，ｌ】区间均匀分布的随机数，吼是一个参数（Ｏ≤吼≤１），ｓ为根据式（１）给出的概率分布所选出的一个随机变量．参数吼的大小决定了利用先验知识与探索新路径之间的相对重要性：每当一只位于城市，．的蚂蚁选择下一个将要到达的城市ｓ时，它选取一个随机数Ｏ≤口≤１．如果ｇ≤吼，根据先验知识选择最好的边，否则按式（１）概率选择
一条边．
经过咒个时刻，蚂蚁完成一次搜索周期，在路径上的信息素量的改变可根据下面式子进行局部更新：％＠＋１）＝
ｊ，（１一∽‘乃（ｆ）＋△乃（ｆ，ｆ＋１），（ｆ，Ｊ∈ｋｓｔｔｒａｖｅｌ）
０，
ｏｍｅｒｓ
△乃（ｆ，ｆ＋１）＝Ｑ／ｋｓｔｌｅｎ．
（ｉ，歹∈ｋｓｔ删）
（３）
式中：ｆｂ。。。一。表示这只蚂蚁所经过的最好路径，
哈尔滨工程大学学报第２７卷
乇删。表示这条路径的长度．ｆ表示当前的代数，口
表示挥发系数，Ｑ为一信息量增加常数．
当ｍ只蚂蚁都经过～次搜索周期后，在路径上的信息素量的改变根据下面式子进行全局更新：勺Ｏ＋１）＝
，（１一ｐ）‘乃（｝）＋△乃（ｆ，ｆ＋１），（ｉ，Ｊ∈ｇ—删）
（４）～
Ｏ．
ｏｔｌｌｅｒｓ
△弓（六ｆ＋１）＝Ｑ／ｇ一．（ｆ，歹∈ｇｂｅｓ。删）
式中：ｇ№。。。。表示所有蚂蚁所经过最好路径，ｇｋ。如。表示这条路径的长度．ｆ表示当前的代数，ｐ表示挥发系数，Ｑ为一信息量增加常数
２改进的蚁群算法
蚁群算法有很多优点：如鲁棒性好、智能搜索、全局优化、稳健性强、分布式计算、易与其它方法结合等．但是它也有过早陷入局部最优的缺点．为了解决这个问题，本小节吸收了微粒群算法的精华思想，提出了一种能够避免过早收敛的改进算法．
本小节主要对蚁群算法中的式（２）中的参数％的设置进行了改进，还对信息素的局部更新规则和
全局更新规则增加了参数ｃ１，Ｃ，Ｗ的控制．改进后
的算法的吼不是一个恒定的值，而是一个随着求解代数的增加逐渐减少的变量．其变化式子如下：
ｑ０＝Ａ＋Ｏ×口）／瓦。．
（５）
式中：｝为当前求解的代数，ＡＢ为固定参数，一般取Ａ＝０．２，Ｂ＝０．７．此时‰的取值范围是：【Ａ’Ａ＋Ｂ］．通过这样的设置有利于消除参数ｇ。对算法的影响・一般在开始阶段ｇｏ越小，则有利于算法展开对新路径的探索，避免过早陷入局部最优．而在
万
方数据结束阶段ｑｏ越大，则有利于算法的全局收敛．因此，一般来说吼的变化范围越大，则算法的搜索范围越
大．
本小节还对算法中的信息素的局部更新规则
和全局更新规则增加了参数Ｃｌ，ｃ２，ｗ的控制．改
进后的信息素更新规则如下：
％Ｏ＋１）２
Ｐ卅△∥＋１ｘａ小患咄嘲删’㈤
△乃（ｆ，ｆ＋１）＝Ｃ１・△毛（ｆ，ｆ＋１）＋ｃ！・△弓（ｆ，ｆ＋１），△毛ｏ，ｆ＋１）＝Ｑ／ｇｂｅｓⅡ。，
（ｆ，Ｊ∈ｇ鲰。。１）
△吒（ｆ，Ｈ１）＝Ｑ／ｋｄｅｎ，（ｆ，歹∈ｋ。一。）
式中：ｋ。岫。。，ｇｋ。。哪。。表示蚂蚁局部最优路径和所有蚂蚁所经过最好路径，ｚｂｃ。Ⅱｅｎ，ｇｂｅ。。ｌｅｎ表示这
条局部最优路径和全局最优路径的长度．ｆ表示当
前代数，Ｑ为一信息量增加常数．Ｗ，ｃ】，Ｃ２为新增
控制参数，控制信息素的挥发和局部最优，全局最优路径对信息素增加的贡献．Ｗ为一随着代数增加
而逐渐递减的挥发变量．它表示随着代数的增加，信息素的保留越来越小，挥发逐渐变大．Ｇ，Ｃ为【０，２】之间随机变动的随机数，控制信息素增加，
能够使各路段的信息素分布更均匀，不会出现最优
路径的信息素远远大于其它路径的情况．这样可以有效避免陷入局部最优．Ｗ的变化表达式如下：
ｗ＝Ａ—Ｏ×Ｂ），瓦。．
（７）
式中：ｆ为当前求解的代数，Ａ，曰为固定参数，一般取Ａ＝０．９，曰＝Ｏ．５．此时Ｗ的取值范围是：
【Ａ一曰，Ａ］．
３
仿真实验
本实验所使用的最优化测试问题是：将处于不
同位置的忍个设备分配给，２个城市，使得分配的代价最小，即要使设备到它所分配的城市的距离之和最短．其数学描述如下：
增刊
张听，等：一种改进的蚁群算法
・５２１・
，＝ＩＩｌｉｎ（∑嘞）Ｊ＝１，２，３…，，１．
（８）
ｆ＿ｌ
表１城市的位置数据
Ｔ妯ｌｅ
１
Ｌ眦ａｔｉｏｎｄａｔａｏｆｔｈｅ
ｃｉ６ｅｓ
万
方数据表２设备的位置数据
７ｒａｂｋ２
Ｌｏｃａ６０ｎｄａｔａｏｆｔｈｅｅｑｕｉｐｍｅｎｔｓ位置
维１
维２
维３
维４
维５
维６
五６．１３２８２１１９．５３３８２２１５．５１６５６６．３．７４１０２８１２．４９４７“
３８２５１２９五９．９５８６７５８．２９６２３７１１．３６５９１１２７１０７９５７．４３８５５６５．１０９８３８ｊ§１０．０１５９５５．５４０４９２．５．３３８２１５
７．１８３３５４１０．４４２２５３
ｌＯ．７８３７３ｌ』；１９．９８２６１２．７３３６９１１０．７７“８１
．６．６１４９５３．２“１２５
２．１９６０４１蔗４．８４０１３６１８．５９０５８９１５．５５２８１７－９．８５５７２４１３．６０６９０２
２．９２８２９７五１６．０８０６２１．６．７７７３５１—６．７０５５７５１９．３７２１４５
１７．３６４印５
８．０５５５３５石０．７３４４３ｌ１３．６７１４２８１３．５１４１０１．２．６２３７”
１４．３２６１０７７’３６４６０５石１４．０２２３３１８．７４２１１６＿４．７９９５３６２．６５７８７
．８．０６３５１６．６８４５５蔗１．４１５２１１８．７０２２４８．７００７９２．２８“９２
．７．６６６９３３
１４．９８３６８７ｍｏ－１．５０９４６ｌ７．２００７５４＿４．１４６３０６１６．４４５２９８—０．５３７９５４．９．３８２２９５五，８．８０９５４１一Ｏ，８９６１０７１３．１３４１９９３．０８７７９８３．４６８４２６
８，０１２７６丑２
１８．７２９０６５６，４３７３２３５．６３７６４２９．８７８９２４２＿３００“２
，０．２４２８７７屁
４．５９４３５９．３．４０１７２６－２．２２８６６７１７．４９８７３１．６．０３０５９５．１８９８７８９五・８．１２３６８６１．１６１４５９－２．３５９１６８－６．９８８３２７０．１４２８２６３．９２５９０４Ｚ５２．９２１０４７
１１．５５５１３７１９．９２１６９９１７．０９７８０３０７４０９５６９．２１６９９４丑６
２．４８８９“
１４．１４１２３１．２．３８５９９３Ｏ７０６８８１９．３３３７２６．５０３２９９届
一９．４３１５９６１６．２１２５７２１７．７４６６８３
－５６２０２４２０．６６９１８—７．４１５３５６五８
—５．１７９４３９
Ｏ．４４２９７８
１０．钾６３２９
１．０９１１３３１１．４９２０６１．７．５３６４３２托
ｌＯ．５７１３０４—０．６６２６５５１５９６０２７２．５９６２４４—８．１９４０１
１
．２．７５１３９６石ｏ－９７６３６４８４．７０３８３５７．４５２３３１７．４４０７３１．９．０５３８６８４．１３６１５６石ｌ３．７１２０２８１６．０７６９９６一１．２１００３４９．３３００９５１０．５２７０７９０．５６３３２９石ｚ－９．１５０２９４７．０６０１０３２．８０６４９６８．５５５７８９６．９９７０２７７．３４２１３蔗ａ
１５－８９４２９４
—０，０６２３５—９５５０４９７１８．８３４１９ｌ１０．９６０６３２６０２６２４５五
一５．９０１５“
４．５９７９８４５．０２６４６３３．２１１７７４．８．７２６８９２．８１９５４６屁７．７５４６５８６．２７４９２２
一Ｏ．８４７５３１
一Ｏ．４８０６７９１．７８９３１３８．５５４３３９屁１８．４８６１８９１１．６２５４６２一１．１５７１０９１０．５６９１２９１．７３３４８８１８．７８９９６６局１４．０３９００５－Ｏ．９２０７５７８．２７３７６２０．５６８４０４
３．１７６２４９—７．３３７０５５’
屁２．３５４８１８１４．８２３４６ｌ１７．７８８００８１０．２３７８０２０．４９５１７９９．０２５５９３局１３．３８９４．８．９５４５４２－９．０５２４１８１５．０８８８１３３．２５５２７４．５．０３００８８‰
１０．２５０８５２１．８３３５３９６．８００５５ｌ３．８８６０２９５．８１０９１９．７．１４５６５４点，一３．３５８９５９９３６９２５１０．０８４８２６１１．５３９１８７１７．６１９８０７９．８８９０７４石ｚ５．１３４４８９１５．６７６７９３—５．５９４１４２１．３１３７１．３．６７３６０３０．７６９９５６ｊ；３
－７．６３２８５７
６．２０７４９７１４．８３１４３６
４．９ｌ１１８７
１５．９２４０１９．Ｏ．７２７９０５晟１７．９３３０∞
９．３５６９２
１６．０７６９９６－９．４３５２２ｉ
５．００２５３８．０．０６３０７５民
１．９９５９４
１８，２１７２１２－９．７０３４７３
２．３１０５９２１０．２５０１２７８．１２６５８６屁５．２５５５“５．５６“１７１．６７４７６３
Ｏ．２６７５２７．５．５５３５４２
１８．１６５７３６
局８．３１７９８７—７．２３９９０４３舶９１５ｌ
６．５４６７９９—２．３２７９９２．５．６７３８９３凰１８．“３５３６３．６９１００３
—３．９０１２５４
８．２０９９６２１１．９１９８１４１２．４２７３１８局Ｏ．７“２３１１．１９９１５９－４．７２８４８５１６．６４２５６．７９１１２６一ｌ，６７１１３８‰
７．５４８０３２１８．３７９６１３－３．５９３１２７
＿４．０３９００５
．Ｏ２３４１７７１０．１９７９２６五－１８．２９０４３７１４．４２９７８３１９．７１１４４８—３．２１０３２４８．３３１０３７６．３８７２９８五ｚ
ｌＯ．７１５５８１．９２９２３９Ｏ．４９５９０１４１９．９９７ｌ
３．６６７８０３
１６．８４３３２６
％１．９８７９６５
—１．１７８１３４—７．９１０５３４１８．９５０１９２．Ｏ．８５加５６
．４－３“５３３
氨
一８．“３４１３
—８．７７４０１６
６．３９５９９８
１１．７６４６６３—７．０３１８２８Ｉ９４５９１５五ｓ
８．５６８８３９１１．２１６５５９－２．０３８７１５１６．０２１８９５
０．０４５６７５
．０．３０２３２７凰
９．０９０１１８１．２６８０３５６．５９１０２４１６．８２８１０１．７．６３１４０７８．０２４３６丑，
１３．４９０１７６６．０２９４３５１２．４６７１９４－６．０６１７７１．２０７８５９一１．９７２０１５‰
９．９３８３７５ｌＯ．０６８１５１．７．０６９１０３６．１４７３２Ｉ１１．１６３６３４４３１３０５７凰１．５６３８３７．２．９４６４２２４２５２８８２３．９２１５５４．８．９７７７４２Ｏ．４２１２２８届
３５２２８０２
０．８１１２８ｌ
１．６０５８８７
２．４５５５９３
—５．９０５８９４
１０．１１６７２６
本实验所采用的数据是５０个６维数据．表１表示５０个城市的位置．表２表示５０个设备的位置．
・５２２・
哈尔滨工程大学学报第２７卷
实验参数设置为蚂蚁的数目为５０个，ｃｌ＝２，ｃ２＝２，Ｑ＝１００，口＝１，夕＝２，蜴＝１００，％＝０．２～０．９，Ｗｒ＿０．９～０．５实验结果如表３．
实验参数设置为蚂蚁的数目为５０个，Ｃ１＝２，ｃ：＝２，Ｑ＝１００，口＝１，∥＝２，Ｑ０＝１００，ｑｏ＝０．２～Ｏ．９，诳＝０．９～Ｏ．５，实验结果如表３．
表３实验结果
１’ａｂｌｅ３
ＥｘｐｅｒｉｍｅｎｔｒｅｓＩｌｌｔｓ
比较值原始的蚁群算法
改进的蚁群算法
１００组解的平均值８６９．６７１７３４８８２０．０３３８０４６１００组解的最优值８４４．３６５８８０
７９６．５２６９７６
问题的最优值
７８１．７７２８０６
从实验结果来看，改进后的蚁群算法无论是最优值的方面还是在平均值方面都比原始蚁群算法要好．改进后的蚁群算法能够扩大最优解的搜索范围，有效地避免算法过早陷入局部最优的情况的出现．４
结束语
针对蚁群算法容易过早陷入局部最优的缺点提
出了一种新的改进算法．实验证明了这种改进的有效性和正确性．
没有对蚁群算法的各参数的设置进行研究，只是根据以往的经验来确定这些参数的值．因此如何实现这些参数的合理的搭配，将成为下一步具有重要意义的研究方向．另外，对算法所作的改进进行深入的数学理论研究和证明，并尝试寻找更优的改进方案，也将成为下一步值得研究的内容．
万
方数据参考文献：
【１１
ＤＯＲＩＧ０
Ｍ，Ⅳ【ＡＮＩＥＺＺ０ｖ’ＣＯＬＯＲＮＩ
Ａ．Ｔｈｅ
ａｎｔ
ｓｙｓｔｅｍ：ｏｐｔｉＩＩｌｉｚａｔｉｏｎｂｙａ
ｃ０１０ｎｙｏｆｃｏｏｐｅｆａｔｉｎｇ
ａｇｅｎｔｓ【Ｊ】．
ⅢＥＥ
ＴｒａＩｌｓａｃｔｉｏｎｓｏｎ
Ｓｙｓｔｅｍｓ，ＭａＩｌａｎｄ
ＣＶｂｅｍｅｔｉｃｓ，
Ｐａｒｔ．Ｂ。１９９６，２６（１）：ｌ—１３．
陀１
ＤＯＲＩＧｏ
Ｍ，ＣＡＲ０
Ｇ
Ｄ，ＧＡＭＢＡＲＤＥＬＬＡＬＭ．Ａｎｔ
ａｌｇｏｒｉｍｍｓ
ｆｏｒｄｉｓｃｒｅｔｅ
ｏｐｔｉｒＩｌｉｚａｔｉｏｎ【Ｊ】．Ａｒｔｉｆｉｃｉａｌ
Ｌｉｆｅ，
１９９９，５（３）：１３７．１７２
【３］
ＬＥＧＩⅡＺＡＭＯＮ
Ｌ
Ｍ，ＭＩＣＨＡＬＥＷＩＣＺ
Ｚ．Ａｎｅｗｖｅｒｓｉｏｎｏｆ
ａｎｔ
ｓｙｓｔｅｍｆＤｒｓｕｂｓｅｔｐｍｂｌｅｍｓ［Ｊ】．
Ｐｒｏｃｅｅｄｉｎｇｏｆｔｈｅ
１９９９Ｃｏｎｇｒｅｓｓｏｎ
ＥＶｏｌｕｔｉｏｎａｒｙＣｏｍｐｕｔａｔｉｏｎ，１９９９，２：
１４５９．１４６４．
『４１ＧＡＭＢＡＲＤＥＬＬＡ
Ｌ
Ｍ，ＴＡＩＬＬＡＲＤＥＤ，ＤＯＲＩＧｏ
Ｍ．
Ａｎｔｃｏｌｏｎｉｅｓ
ｆｏｒⅡｌｅｑｕａｄｒａｔｉｃａｓｓｉｇｎｍｅｎｔｐｒｏｂｌｅｍ【Ｊ】．
Ｊｏｕｍａｌｏｆ出ｅｏｐｅｒａｔｉｏｎａｌＲｅｓｅａｒｃｈＳｏｃｉｅｔｙ＇１９９９，５０（２）：
１６７．１７６．
ｆ５１
ＭＡＮ狂ＺＺＯＶ
ＤｏＲＩＧ０
Ｍ，ＣＯＬＯＲＮＩ
Ａ．Ａ１２０ｄｅｓｋ：ａｎ
ｅｘｐｅｒｉⅡｌｅｎｔａｌｃｏｍｐａｒｉｓｏｎｏｆｅｉｇｈｔｅｖ０１ｕｔｉｏｎａｒｙｈｅｕｒｉｓｔｉｃｓ
ａｐｐｈｅｄ
ｔｏ
ｍｅｑｕａｄｒａｔｉｃａｓｓｉｇｎｍｅｎｔＪｏ啪ａ１ｐｒｏｂｌｅｍ【Ｊ】．Ｅｕｒｏｐｅａｎ
ｏｆ０ｐｅｒａｔｉｏｎａｌ
Ｒｅｓｅａｒｃｈ，１９９５，８ｌ（１）：１８８—２０４．
［６】李士勇．蚁群算法及其应用［Ｍ】．哈尔滨：哈尔滨工业
大学出版社，２００４．［７】
ＳＴＵＴＺＬＥＴ，ＨＯＯＳＨ．Ｍａｘ－ｒＩｌｉｎ
ａｎｔ
ｓｙｓｔｅｍ【Ｊ】．Ｆｕｔｕｒｅ
ＧｅｎｅｒａｔｉｏｎＣｏｍｐｕｔｅｒＳｙｓｔｅｍｓ，２０００，１６（８）：８８９．９１４．
『８１
ＤＯＲＩＧ０
Ｍ，ＧＡＭＢＡＲＤＥＵ。ＡＬＭ．Ａｎｔ
ｃｏｌｏｎｙ
ｓｖｓｔｅｍ：
ａ
ｃｏ叩ｅｒａｔｉｖｅ
ｌｅ锄ｉｎｇ
ａｐｐｒｏａｃｈｔｏｔｈｅｔｒａＶｅｌｉｎｇｓａｌｅｓｍ锄
ｐｒｏｂｌｅｍ『Ｊ１．ＩＥＥＥ
Ｔｒａｎｓａｃｔｉｏｎｓ
ｏｎ
Ｅｖｏｌｕｔｉｏｎａｒｖ
Ｃｏｍｐｕｔａｔｉｏｎ，１９９７，１（１）：５３—６６．
『９１
ＤＯＲＩＧｏ
Ｍ，ＧＡＭＢＡＲＤＥＬＬＡＬ
Ｍ，ＭｍＤＥＮＤｏＩ己Ｆ
Ｍ，ＳＴＵＴＺＬＥＴ．Ｇｕｅｓｔｅｄｉｔｏｒｉａｌ：ｓｐｅｃｉａｌｓｅｃｔｉｏｎ
ｏｎ
ａｎｔｃｏｌ伽ｖ
ｏｐｔｉｆｌｌｉｚａｔ主ｏｎⅢ．
ＩＥＥＥ
Ｔｒａｎｓａｃ￡ｉｏｎｓ
ｏｎ
ＥｖｏｌｕｔｉｏｎａｒｙＣｏｍｐｕｔａｔｉｏｎ，２００２，６（４）：３１７—３１９．
一种改进的蚁群算法
作者：作者单位：
张昕， 彭宏， 郑启伦， ZHANG Xin， PENG Hong， ZHENG Qi-lun
张昕,ZHANG Xin(华南理工大学,计算机科学与工程学院,广东,广州,510640;华南农业大学,理学院,广东,广州,510642)， 彭宏,郑启伦,PENG Hong,ZHENG Qi-lun(华南理工大学,计算机科学与工程学院,广东,广州,510640)哈尔滨工程大学学报
JOURNAL OF HARBIN ENGINEERING UNIVERSITY2006,27(z1)5次
刊名：英文刊名：年，卷(期)：被引用次数：
参考文献(9条)
1. DORIGO M;MANIEZZO V;COLORNI A The ant system:optimization by a colony of cooperating agents1996(01)
2. DORIGO M;CARO G D;GAMBARDELLA L M Ant algorithms for discrete optimization 1999(03)3. LEGUIZAMON L M;MICHALEWICZ Z A new version of ant system for subset problems[外文会议] 19994. GAMBARDELLA L M;TAILLARD E D;DORIGO M Ant colonies for the quadratic assignment problem[外文期刊]1999(02)
5. MANIEZZO V;DORIGO M;COLORNI A Algodesk:an experimental comparison of eight evolutionary heuristicsapplied to the quadratic assignment problem[外文期刊] 1995(01)6. 李士勇 蚁群算法及其应用 2000
7. STUTZLE T;HOOS H Max-min ant system[外文期刊] 2000(08)
8. DORIGO M;GAMBARDELLA L M Ant colony system:a cooperative learning approach to the travelingsalesman problem[外文期刊] 1997(01)
9. DORIGO M;GAMBARDELLA L M;MIDDENDORF M;STUTZLE T Guest editorial:special section on ant colonyoptimization 2002(04)
本文读者也读过(1条)
1. 张军英. 敖磊. 贾江涛. 高琳. ZHANG Jun-ying. AO Lei. JIA Jiang-tao. GAO Lin 求解TSP问题的改进蚁群算法[期刊论文]-西安电子科技大学学报（自然科学版）2005,32(5)
引证文献(6条)
1. 张侠 基于最大最小蚁群算法的TSP问题求解[期刊论文]-计算机光盘软件与应用 2010(15)2. 张侠 基于最大最小蚁群算法的TSP问题求解[期刊论文]-计算机光盘软件与应用 2010(15)3. 杜波. 邵春福 基于蚂蚁算法的用户平衡分配方法研究[期刊论文]-物流技术 2009(12)4. 梅红. 李俊卿 蚁群优化算法研究综述[期刊论文]-机电一体化 2010(11)
5. 雷筱珍. 赖万钦 一种基于信息素的FCM蚁群聚类算法[期刊论文]-安阳工学院学报 2009(2)
6. 范展. 梁国龙. 林旺生. 刘凯 求解TSP问题的自适应邻域搜索法及其扩展构[期刊论文]-计算机工程与应用2008(12)
本文链接：http://d.g.wanfangdata.com.cn/Periodical_hebgcdxxb2006z1110.aspx