蚁群算法及其应用研究(8)

第１章绪论

＾Ｂ

图１－２蚁群寻找食物的过程

Ｆｉｇｕｒｅｌ－２Ｐｒｏｃｅｓｓｏｆａｎｔｓｆｏｒａｇｉｎｇｆｏｒｆｏｏｄ

径的蚂蚁也随之增多，表现为一种信息正反馈的现象，即某一路径上走过的蚂蚁越多，后来的蚂蚁选择该路径的概率就越大Ｈ１。蚂蚁个体之间正是通过这种信息交流机制来搜索食物源，并最终沿着最短路径行进。

基于以上的蚂蚁觅食行为，意大利学者ＤｏｒｉｇｏＭ等在１９９１年第一次提出了蚁群算法嵋’６１。１９９６年ＤｏｒｉｇｏＭ等又发表了另一篇奠基性的文章“Ａｎｔ

ｏｐｔｉｍｉｚａｔｉｏｎｂｙａＳｙｓｔｅｍ：ｃｏｌｏｎｙｏｆｃｏｏｐｅｒａｔｉｏｎａｇｅｎｔｓ”ｍ，该文系统地阐述了蚁群算法的基本原理和数学模型，还将其与遗传算法、模拟退火算法、爬山法等进行实验仿真比较，并把蚁群算法从解决对称旅行商问题（ＴｒａｖｅｌｉｎｇＳａｌｅｓｍａｎＰｒｏｂｌｅｍ）扩展到解决非对称旅行商问题、指派问题及车间作业调度问题，同时也对蚁群算法中初始参数对算法性能的影响做了初步探讨。在此之后，蚁群算法迅速引起了世界许多国家研究者的广泛关注，其应用领域不断拓宽，针对原算法的改进的成果也大量涌现。

１．１．３蚁群算法的发展

ＤｏｒｉｇｏＭ等提出了第一个蚁群优化算法，即蚂蚁系统（ＡｎｔＳｙｓｔｅｍ，简称ＡＳ）并成功应用于求解ＴＳＰ问题，其实验结果表明ＡＳ算法具有较强的鲁棒性和发现较好解的能力，但其存在的缺陷也很明显，如收敛速度慢、易陷入停滞等。随后许多学者对如何改进基本的蚁群算法进行了研究，如基于蚂蚁等级的蚁群算法嘲。随后，ＤｏｒｉｇｏＭ等又提出了Ａｎｔ－Ｏ算法叫，该算法用伪随机比例状态转移规则（Ｐｓｕｅｄｏｒａｎｄｏｍｐｒｏｐｏｒｔｉｏｎａｌｓｔａｔｅｔｒａｎｓｉｔｉｏｎｒｕｌｅ）替换ＡＳ算法中

ｒｕｌｅ），使得该算法在的随机比例选择规则（Ｓｔｏｃｈａｓｔｉｃｐｒｏｐｏｒｔｉｏｎａｌｃｈｏｉｃｅ

构造解的过程中能更好地保持探索（ｅｘｐｌｏｒａｔｉｏｎ）和利用（ｅｘｐｌｏｉｔａｔｉｏｎ）之间的平衡，另外算法还引入了全局信息素更新中的精英策略。在Ａｎｔ—Ｑ算法的基