《一种基于精英策略的改进蚁群算法及应用》由会员分享，可在线阅读，更多相关《一种基于精英策略的改进蚁群算法及应用（5页珍藏版）》请在金锄头文库上搜索。
1、一种基于精英策略的改进蚁群算法及应用张家善 1,2, 王志宏 1, 陈应显 11(辽宁工程技术大学 工商管理学院, 葫芦岛 125000)2(湛江师范学院 商学院, 湛江 524048)摘 要: 针对基本蚁群算法存在求解速度慢,容易出现“早熟”, 导致搜索停滞的缺点, 将遗传算法中排序的概念 扩展到精英机制当中, 以一种新的加权方法进行信息素更新, 建立了改进蚁群算法模型. 对 30 城市物流配送问 题仿真结果表明: 改进算法的求解速度和求解精确度都明显优于基本蚁群算法. 关键词: 蚁群算法; 搜索停滞; 精英策略; 排序; 物流配送Improved Ant Colony Algorithm
2、Based on Elitist Strategy and ApplicationZHANG Jia-Shan1,2, WANG Zhi-Hong1, CHEN Ying-Xian11(College of Business Administration, Liaoning Technical University, Huludao 125000, China)2(School of Business, Zhanjiang Normal University, Zhanjiang 524048, China)Abstract: The basic ant colony algorithm co
3、nverges slowly, is prone to plunge into partial optimum and results in searchstagnation. In this paper, the optimized compositor is introduced into elitist strategy. According to ant compositor, new weighted coefficient is designed for pheromone updating. The simulation results of 30-city logistic d
4、istribution show that improved algorithm is more efficient and accurate than the basic ant colony algorithm.Key words: ant colony algorithm(ACA); search stagnation; elitist strategy; compositor; logistic distribution1引言 蚁群算法(Ant Colony Algorithm, ACA)1又称作蚂蚁 算法, 是由意大利的 Marco Dorigo 于 1992 年在他的博士 论文中首
5、先提出, 其基本思想是模仿蚂蚁依赖信息素进 行通信而显示出的社会行为, 在Agent 总体的基础上, 由 一个贪心算法指导下的自催化过程引导每个 Agent 的行 动. 该算法模拟了蚂蚁觅食时的行为, 按照启发式思想, 通过信息素的诱导作用, 逐步收敛到问题的最优解. 其 主要特点就是: 通过正反馈、分布式协作来寻找最优路 径. 目前, 蚁群算法已经广泛应用于旅行商问题、 二次分 配问题、作业车间调度问题、物流配送问题, 成为解决 组合优化问题最有效的算法之一. 基本蚁群算法复杂度较高, 一般需要较长的搜索 时 间 , 而 且 容 易 出 现 搜 索 停 滞 现 象 (Stagnation B
6、ehaviour), 即搜索进行到一定程度后, 所有个体所发现的解完全一致, 不能对解空间进一步进行搜索, 不 利于发现更好的解. 围绕该问题, 学者们发表了不少 文献, 如文献3在路径选择时提出了一种不再考虑距 离因素, 仅考虑信息素强度的方法; 文献4通过在局 部搜索中采用聚类进行二次搜索,取得了较好求解效 果; 文献5引入精英策略, 即在每次循环之后给予最 优解以额外的信息素量, 以使到目前为止所找出的最 优解在下一循环中对蚂蚁更有吸引力. 文献6基于蚂 蚁分类, 提出了一种改进精英策略算法. 实验表明, 上述算法在一定程度上拓展了解的搜索空间, 提高了 解的质量. 但是依然存在问题,
7、或者搜索速度慢, 或 者虽然搜索快但却容易陷入局部最优. 本文基于精英 策略并将遗传算法中排序的概念扩展到精英机制当 中, 对蚁群算法进行改进, 以在较短时间内获得问题 的满意最优解. 基金项目:国家自然科学基金(50904032) 收稿时间:2012-02-16;收到修改稿时间:2012-03-14基本蚁群算法1,2,8 假设有 m 只蚂蚁放入到 n 个随机选择的需求节点 中, 每一只蚂蚁将根据线路上的信息浓度选择下一个 它还没有访问的节点; 同时在完成一步(从一个节点到 达另外一个节点)或者一个循环(完成对所有 n 个节点 的访问)后, 更新所有路径上的残留信息浓度. m 是蚁3算法改进
8、1)状态转移概率公式的改进 本文引入一个新的常 量: q0(0,1), 蚂蚁 k 在每次选择路径之前, 先随机产生 q0(0,1), 蚂蚁 k 将根据下式选择路径 j:2arg max (t ) (t ),q q ; ijij0j jallowed .k;(5)群中蚂蚁的数量, dij 是城市 i 到城市 j 之间的距离, ij 式(1),q q0 ;是边(i, j)的能见度, ij=1/dij, 反映由城市 i 转移到城 市 j 的启发程度, ij 是边(i, j)上的信息素轨迹强度,式中, 当 qq0 时, 该式表示基本 ACA 中的探索性搜索; 当 q q0 时, 该式表示确定性搜索,
9、即从已得的结 果中, 找出概率最大的路径作为选择确定性搜索利用了已得的经验知识来指导路径选择, 弥补了探索性 搜索在收敛速度上受限制的缺陷.2)信息素更新的改进 精英策略(elitist Strategy)的基本思想是: 在每次 循环结束后即对所有已经发现的最优解给予额外的信 息素增强, 其目的是为了使到目前为止所找出的最优 解在下一次循环中对蚂蚁更具有吸引力5. 信息素根 据下式进行更新:k ij 是蚂蚁 k 在边(i, j)上留下的单位长度轨迹信息素 k量, pij 是蚂蚁 k 从城市 i 转移到城市 j 的状态转移概率,kj 是尚未访问的城市, 则状态转移概率 pij ij t ij t
10、 , j allowed(1)pk t t k ijsallowedk isis0, otherwise式中, allowedk=0,1, ,n-1表示蚂蚁 k 下一步允许选择的城市. 和为两个参数, 分别反映了蚂蚁在运 动过程中积累的信息和启发信息在蚂蚁选择路径中的 相 对 重 要 性 7. 为 每 只 蚂 蚁 设 计 一 个 禁 忌 表 tabuk(k=1,2, ,m), 记录在 t 时刻蚂蚁 k 已走过城市, 不 (t 1) (t ) *(6)i j i j i ji j 其中, 允许该蚂蚁在本次循环中重复经过. 禁忌表被清空.本次循环结束后 Q如 果 边 (i,j)是 所L* i j
11、找 出 最 优 解 的 一 部 分当所有蚂蚁完成一次循环后, 根据各蚂蚁遍历的 0否则 好坏(适应度值), 计算信息素增量, 更新相关路径上的 信息素, 更新规则如下:* i j 表示精英蚂蚁引起的路径(i ,j)上的信息索 量的增加, 是精英蚂蚁的个数, L* 为所找出的最优解的路径长度. 文献5认为所有经过边(i,j)蚂蚁对该边信息素更 i j (t 1) (1 ) i j (t ) i j (t, t 1)m(2)ij k t, t 1 (t, t 1) (3)新的贡献是相同的, 计算采用(4)式. 实验表明,ijij 使用精英策略可以使蚂蚁系统经过较少的进化代数就 能找出更优的解. 但
12、是使用精英策略后, 解元素之间 的差异减小了, 导致选择概率的差异也随之减小, 使 得搜索过程集中在到目前为止所找出的最优解附近, 从而阻止了对更优解的进一步搜索. 为了维持选择压力, 本文将蚂蚁按路径长度排序, 认为蚂蚁对信息素更新的贡献与该蚂蚁所找到路径的 质量有关, 路径越优(短), 对信息素更新的贡献越大; 路径越长, 对信息素更新的贡献越小. ij 的确定按 如下规则进行:k 1式中 为信息素轨迹的衰减系数, k (t, t+1)表示 ij 第 k 只蚂蚁在(t, t+1)时刻留在(i, j)路段上的信息量, ij (t, t+1)表示本次循环中路段(i, j)的信息素增量.Q,(i
13、, j) lk否则为常数, 其值由实验确定.k L, 0,(4)kij其中, Q 表示初始信息素量,Lk 表示第 k 只蚂蚁在本次循环中所走路线的费用值(可以表示为长度). ij (t ) max ,则设置 ij (t )= max ; 若 ij (t) min ,则当所有蚂蚁都完成一次遍历后, 蚂蚁按路径长度排序( L1 L2 . Lm ), 蚂蚁对激素轨迹量 更新的贡献根据该蚂蚁的排名位次(记为 )进行加权, 只考虑前 m /3 只蚂蚁.在排列中, 前 m /3 只蚂蚁中的一只所经过的边 获得一定量的信息素, 其量正比于该蚂蚁的排名位次, Lav L其权系数为 . 信息素增加按下式进行:设
14、置 (t)=. 这样可以有效地避免某条路径上的ijmin 信息量远大于其余路径, 使得所有的蚂蚁都集中到同 一条路径上, 从而阻止了对解空间的进一步探索. 改进后算法流程如图 1 所示.L L* av m/3 i j (7)i j 1 Lav L Q如果第只最好L L* L av i j 蚂蚁经过路径(i,j) 0否则其中, 为蚂蚁排列的顺序号; i j 表示由第 只 Lav最好蚂蚁引起的路径(i, j)上的信息素量的增加;为本次循环平均路径长度, L 是第 只最优蚂蚁的路径长度. 此外, 到目前为止找出最优路径蚂蚁所经过的边 也将获得额外的激素量(相当于带精英策略蚁群算法 中精英蚂蚁的激素更
15、新).3)信息素设置上下界 本文在信息素更新过程中引 入 MMAS 的思想, 对 信息素实施上下界限制. 设信息素最小值和最大值分图 1 改进后算法流程4应用仿真 选取 VRP 测试库中的 Eil30 问题做仿真: 已知车 辆额定载重量为 4500kg, 客户数为 29,编号 1 对应的位 置为配送中心,各配送点坐标及需求量如表 1 所示. 别 min和 max , 从而使得对所有信息素 ij (t) , 有 min ij (t ) max . 在进行信息素更新时,若发现有 表 1 各配送点坐标及需求量数据表编号x 坐标y 坐标需求量/kg编号x 坐标y 坐标需求量/kg123456789101112131416221821820121422421010412611912912612
