基于蚁群算法求解0／1背包问题.pdfVIP

维普资讯 大 庆 石 油 学 院 学 报 第29卷 第3期 2005年 6月 JOURNAIOFDAQING PETROIEUM INSTITUTE Vo1．29 No．3 Jun． 2005 基于蚁群算法求解 0／1背包问题 刘华蓥 ，林玉娥 ，刘金月 (大庆石油学院 计算机与信息技术学院，黑龙江 大庆 163318) 摘 要：阐述了蚁群算法的基本原理 ，根据求解TSP问题的蚁群系统模型及转移概率公式 ，修改了蚁群算法模型，给 出了适用于o／1背包问题的模型．通过实验测试改进的算法 ，结果表明，改进算法的收敛速度得到提高． 关 键 词 ：蚁群算法 ；信息素；背包问题；禁忌表 ；标识表 中图分类号：TP301．6 文献标识码：A 文章编号 ：1000—1891(2005)03—0059一O4 O／1背包问题是典型的组合优化问题 ，直接的枚举有哪些信誉好的足球投注网站可能遍历问题的所有 2个解，因此其计算复 杂度为 o(2)．背包问题在生产管理中有重要的应用，如资源分配、投资决策、装载等均可建模为背包问 题．蚁群算法是由意大利学者DorigoM 和Maniez—ZOV提出的一种新型的模拟进化算法 ，称之为蚁群系 统Ⅲ．蚁群算法已成功地应用于求解旅行商、二次指派、排序等问题．笔者对蚁群算法模型做适当的修改， 使之成为适于0／1背包问题的模型，仿真实验证实了该算法的有效性． 1 蚁群算法的基本原理 蚁群算法是模仿真实的蚁群行为而提 出的一种模拟进化算法．蚂蚁之间是通过一种称为信息素 (Pheromone)的物质传递信息的，蚂蚁在运动过程中能够在经过的路径上留下该种物质，而且能够感知这 种物质的存在及其强度，并以此指导 自己的运动方向．因此 ，由大量蚂蚁组成的集体行为便表现出一种信 息正反馈现象：某一条路径上走过的蚂蚁越多，该路径上留下的信息素就越多，则后来者选择该路径的概 率就越大．蚂蚁个体之间就是通过这种信息素的交流，有哪些信誉好的足球投注网站到一条从蚁巢到食物源的最短路径[2]． 2 蚁群系统模型 ’ 蚁群算法已成功地解决了TSP问题，以求解平面上 个城市的TSP问题为例说明蚁群系统模 型． TSP问题就是寻找通过 个城市各一次且最后 回到出发点的最短封闭路径．TSP 问题的目标函数为 minD 1一∑d(i，i+1)+ (，1)， (1) 式中：(i，J)(i，J一1，2，…，)表示城市 i和城市 之间的距离． 求解 TSP问题的蚁群系统模型为：设 m为蚂蚁数量， 为城市数量，t时刻 i城市与 城市间的路径 ij上的信息素密度为r (f)，其初值为很小的正数C．在 t时刻每只蚂蚁将根据转移概率公式移动到下一 个城市，时间将变为f+1，经过 次这样的移动 ，时间变为f+ ．当每只蚂蚁都完成一次循环，所有蚂蚁走 过的封闭路径中最短的一条路径将被记录下来．其转移概率公式为 是)一l』舞 一一a…bu㈨’’ (2) 一 I o ， ∈tabu(是)， 式 中： (f)为路径长度的倒数 ，表示由城市 i转移到城市 的期望程度； (f)仉 (f)为该路径单位长度的 收稿 日期：2004—1O一29；审稿人：吴雅娟；编辑 ：陆雅玲 作者简介 ：刘华蓥(1969一)，女 ，硕士 ，副教授，主要从事人工智能及应用方面的研究 维普资讯 大 庆 石 油 学 院 学 报 第29卷 2005年 信息素 ；a，卢分别表示第k只蚂蚁在运动过程中积