蚁群算法优化 基于局部信息素更新.doc

2012 年 8 月
第 29 卷第 8 期
湖北第二师范学院学报
Journal of Hubei University of Education
Aug. 2012
Vol. 29 No. 8
蚁群算法优化———基于局部信息素更新
余
慧
( 湖北第二师范学院计算机学院,武汉 430205)
摘要: 由于常规蚁群算法容易陷入局部最优,出现停滞现象等问题,本文采用了城市选择策略,局部信息素更新策略,
最优解预测策略和局部优化策略对蚁群算法进行优化改进,提出了基于局部信息素更新的思想。并通过一些 TSP 问题对改进的蚁群算法进行验证。实验结果表明改进后的蚁群算法在求解一些 TSP 问题上可以得到比目前所了解的最优解更满意的解。
关键词: 蚁群算法; 局部信息素更新策略; 最优解预测策略; 局部优化策略
中图分类号: O657. 3
文献标识码: A
文章编号: 1674-344X( 2012) 08-0009-04
基金项目: 湖北省教育厅 2011 年度科学技术研究计划指导性项目( B20113003)
作者简介: 余慧( 1976 - ) ,女,湖北武汉人,讲师,硕士,研究方向为计算机应用。
蚁群优化算法( Ant Colony Optimization) 是通过模
拟自然界蚂蚁寻食行为的一种进化算法,是 20 世纪
90 年代,意大利的 M Dorlgo 等学者从生物进化的机理中受到启发提出来的[1 ~ 2]。研究结果表明: 蚁群算法具有分布式计算、易于与其他方法相结合、鲁棒性强等优点[2]。在求解 TSP[3]( Traveling Salesman Problem) , QAP ( Quadratic Assignment Problem ) ,JSP ( Jobshop Scheduling Problem) 等组合优化问题中,取得了极大的成功,但同时也存在一些缺点,其中最大的问题就是在求解过程中容易出现停滞现象,陷入局部最优。十多年以来,大批的学者和科研工作者对蚁群算法进行了充分的研究,提出了大量对标准蚁群算法改进的算法, 如最大最小蚂蚁系统[4],免疫算法与蚁群算法相结合[5 ~ 6],遗传算法与蚁群算法相结合[7 ~ 9]等。本文将在简要的介绍蚁群算法和 TSP 问题的基础上,详细地论述在蚁群算法中引入城市选择策略、局部信息素更新策略、最优解预测策略和局部优化策略,并选用一些 TSP 问题做实验。
1 蚁群算法
路径。蚁群算法就是模拟蚂蚁群体觅食机理,构造一
定数量的人工蚂蚁,每个人工蚂蚁以路径上的信息素强度大小为参考,选择前进路径,当所有蚂蚁均完成 1 次搜索后,再对信息素强度进行 1 次全局更新。通过反复迭代,最终大多数蚂蚁将沿着相同的路线( 最优路线) 完成搜索。
蚁群算法解决 TSP 问题模型。我们采用 n 个城
1. 2
市( 1,2,Λ,i,Λ,n 为城市编号) 的 TSP 问题来解释基
本蚁群算法。n 城市 TSP 问题就是无重复经过 n 座城市时走过的路程最短的问题。
首先引入 TSP 问题中的常用符号:
m 为蚁群中蚂蚁的数量,Dij 为城市 i 和 j 之间距
离,τ为边( i,j) 上残留信息素数量,η为边( i,j) 上的
ij
ij
启发因子