基于蚁群算法的0-1背包问题的实现

基于蚁群算法的0-1背包问题的实现内容摘要：

,它是在原有进化算法理 论框 架的基础上引入一个新算子 — 免疫算子 (i~une叩 erator),从而形成一种新的 算法。 求解背包问题的免疫算法主要采用克隆选择和贪心修正机理【川。 与相应的 遗传算法相比 ,该算法有效克服了早熟问题、改善了陷入局部极小值的缺陷 ,而 且寻优效果明显。 遗传算法、免疫算法等算法都是从进化理论发展而来的 ,但是大自然给我们 的启示并不仅仅在进化方面 ,许多社会性动物 (如蚂蚁、蜜蜂等 )的自组织行为也 引起了人们的广泛关注和研究。 蚁群算法的提出正是这些研究的成果。 蚁群算法 是一种十分有效的算法 ,它在背包问题上也有重要的 应用。 本文的工作就是在蚁 群算法的基础上进行的。 遗传算法、免疫算法和蚁群算法等算法虽然可能在求解某些问题时有计算时 间长 ,且容易陷入局部最优解的缺点 ,但是它们也有通用性强、容易与其它算法 相结合的优点。 在使用这些算法求解背包问题时 ,缩短求解时间和提高解的质量 就成为算法设计的一个关键。 本文根据背包问题的特征 ,尝试引入局部搜索策略 解决这个问题。 群算法求解 0一 l背包问题 仁自 _崔参砚 l弓旨 二月勺 `拼 .JIF二 I 1背包问题简介 0一 1背包问题的描述 在算法研究过程中 ,有很多有实际背景的重要问题 ,它们是否有有效的算法 , 是计算机科学家们非常感兴趣的问题。 1971年库克 ()发表了 `,The eomplexity。 fTheoremProvingProeedures”〔 `l和 1972年卡普 ()发表的。 `Redueibility腼 ongeombinatorialProb一 ems” I,l两篇著名的论文奠定了砂完备理 论的基础。 即是 `NondeterministiePol” omial”的缩写 ,意为“非确定型的多项式”。 在 NP 问题中 ,有一个子类 ,即完全 (NPComPlcte,简记为脚 C)问题 ,指的是 那些 NP 问题中最难的问题 :所有其它的 NP 问题都可以归约到这些 NP 完全问 题。 o一 1背包问题 (O一 1knapsackproblem,KP,以下简称背包问题 )是一个典型 NPC 问题 [2]。 对一个 m维。 一 1背包问题可描述为 :己知有几个价值为 vj仃 =l,2,„ ,。 )的 物品 ,m个容积大小为 c,(i=l,2,„ ,m)的容器 ,且卿个物品占用第 i个容器的容积 大小为乌。 现在问题是 :选择哪些物品装入这 m个容器使得装入总价值最大。 其 严格数学描述为 : maxf(x,x:,„ ,x,:)= n s `艺 b。 x,三 e`(`一 `,2/=l 艺 vi xj j=l ,„ ,m)() xz 任 {o,1}(j=1,2,„ ,n) 这里 xj 表示是否选择第 j个物品装入背包 ,如果 xj 一 o,表示没有选择该物品 装入 ,反之 xj 一 1,则表示选择该物品装入。 函数 f(x,xZ,„ ,戈 ,)表示装入背包的 物品总价值。 当 m姿 2时 ,又称为多维背包问题。 背包问题本质上是一个整数规 划问题。 群算法求解 O一 l背包问题 本文尝试以蚁群算法为基础研究背包问题 ,实现一种能够快速求解背包问题 的算法。 主要对下列几个问题进行探讨 :。 蚁群算法在许多方面已经有了很好应用 ,但是 在背包问题上应用效果还不是很理想。 蚁群算法所求解的问题模型可用图来描 述 ,本文研究了如何将背包问题转化成蚁群算法能够有效求解的图问题 ,并推广 文献 {24」的图表示法 ,将其应用在多维背包问题上。 蚁群算法的优势在于鲁棒性好、具有 分布式 ,缺点是搜索时间长 ,容易陷于局部最优解。 交换是一种局部搜索策略 , 可以扬长避短 ,极大提高蚁群算法的效率 ,所以需要研究基于交换策略的蚁群算 法。 但是背包问题具有其特色 ,交换的 策略不同于其它问题 ,因此本文中提出了 一系列的交换方式来实现背包问题的交换。 采用图形、数据等手段实现了本文 算法同其它算法在时间、最优解、搜索代数等方面的比较。 这使得实验结果更加 形象、直观。 本文的特色主要有 :采用蚁群算法求解背包问题 ,并将求解一维背包问题的 算法模型推广成可以求解多维背包问题的算法模型 ,具有应用创新。 实现基于交 换策略的蚁群算法求解背包问题 ,可以解决蚁群算法在求解背包问题时容易陷入 局部最优解的问题 ,具有创新意义。 第一章蚁群算法 第二章蚁群算法 蚂蚁又称“玄驹”、 `嗽七好”或“状元子” ,是一种既渺小而又平常的社会性昆虫。 在分类上蚂蚁属于节肢动物门、昆虫纲、膜翅目、蚁科 ,它在昆虫界种类最多、 生存量最大 ,而且己经在地球上生存了一亿多年。 随着环境的变迁 ,身体庞大的 恐龙早已经灭绝了 ,但是身体细小的蚂蚁在弱肉强食、物竟天择的自然界依靠集 体的力量和顽强的生命力一直生存繁衍到了今天。 尽管蚂蚁个体比较简单 ,但整个群体却表现为高度机构化的社会组织 ,在许 多情况下能完成远远超过蚂蚁个体能力的复杂任务。 这种能力 来源于蚂蚁群体中 的个体协作行为。 蚂蚁的觅食行为就很好地体现了这种行为 l`2]。 在自然界中 ,蚂蚁的食物源总是随机散布于蚁巢周围。 在现实生活中 ,我们 总可以观察到大量蚂蚁在巢穴和食物源之间形成几乎直线的路径 ,而不是曲线或 者圆等其他形状 ,如图。 图 蚂蚁群体不仅能完成复杂的任务 ,而且还能适应环境的变化 ,如在蚁群运动 路线上突然出现障碍物时 ,一开始蚂蚁分布是均匀的 ,不管路径长短 ,蚂蚁总是 先按同等概率选择各路径 ,如图。 算法求解 0一 l背包问题 食物源 种扣 ~吧勃” 图 但是经过一段时间后 ,大部分蚂蚁会选择比较短的路径。 这是因为蚂蚁之间 通过一种叫信息素 (Pheromone)的化学物质进行了信息的交流。 蚂蚁在运动过程 中 ,能够在其经过的路径上留下信息素 ,而且能感知这种物质的存在及强度 ,并 以此指导自己运动的方向 ,蚂蚁倾向于信息素浓度高的方向移动。 相等时间内较 短路径上的信息素遗留得比较多 ,则选择较短路径的蚂蚁也随之增多 ,如图 所示。 啥气 黑肠 .蒸麟月 *阅咖 图 ,选择该路径的蚂蚁增多 不难看出由大 量蚂蚁集体行为表现出了一种信息正反馈现象 ,即某一条路径 上走过的蚂蚁越多 ,则后者选择该路径的概率越大。 蚂蚁个体之间就是通过这种 信息交流机制搜索食物 ,并最终沿着最短路径行进 ,如图。 蚁穴 `粉瀚毒弩 图 第一章蚁群算法 蚂蚁选路过程中较短路径上遗留的信息素浓度会在很短时间内大于较长路 径的原理我们不妨用下图 (图 )说明【 39。 3】 :假设 A、 D两点是蚁群的巢穴和食物 源 ,从其间有两条路径 A一 B一 E一 C一 D和 A一 B一 F一 C一 D,其中 B一 F和 F一 C间距离 为 lm, B一 E和 E一 C间的距离为 ,如图 (a)所示。 最初 (即 t=O时刻 ),当 30只蚂蚁走到分路口 B或者 C点时 ,要决定往哪个 方向走。 因为初始时没有什么线索可供它们选择 ,所以它们就以相同的概率选择 路径 ,结果有巧只蚂蚁走左边路径 C一 F和 B一 F。 另外巧只蚂蚁走右边的路径 C一 E和 B一 E,如图 (b)所示 ,这些蚂蚁在行进过程中分别留下信息素。 若假设 蚂蚁都具有相同的速度 (1耐 s)和信息素释放能力 ,则经过 ls 后从 B点出发的 30 只蚂蚁有巧只到达了 F,有巧只经过 E到达了 C点 ,同样从 C点出发的 30只 蚂蚁有巧只蚂蚁到达了 F,有巧只经过 E到达了 C点。 很显然 ,在相等时间间 隔内路径 B一 F一 C上共有巧只蚂蚁经过并遗留信息素 ,B一 E一 C上却有 30只蚂蚁经 过并遗留了信息素 ,其信息素强度是 B一 F一 C路径上的 2倍。 因此当 30只蚂蚁分 别回到 B、 C点重新选择路径时就会以 2倍于 B一 F一 C的概率选择路径 B一 E一 C,从 而 B一 F一 C上的蚂蚁数目变成 10只 ,是 B一 E一 C上蚂蚁数目的一半 ,如图 (c)所 示 ,距离较短的路径上信息素很快得到强化 ,其优势很快被蚁群所发现。 君„华卜 05丫尸 d谷 (a)E 图 中蚂蚁觅食模拟 1989年 ,GosSS等通过著名的“双桥”实验对蚁群的觅食行为进行研究 ,并 给出了蚁群觅食行为的数学模型。 首先 ,假设在非对称桥上的信息素与过去一段 第一章蚁群算法 算机中只有一个个离散点 ,因此 ,用任意两个节点表示蚂蚁的巢穴 (初始节点 )和 食物源 (目标节点 ),人工蚂蚁从初始节点出发根据一定概率条件 (信息素大小 )选 择下一个节点 ,直到找到目标节点 ,这就是问题的一个可行解。 对信息素挥发的抽象。 因为信息素挥发在现实世界中也是一个连续事件 ,而 且蚂蚁在经过路径上也是连续不断地留下信息素。 通常做法是 :当蚂蚁完成从某 个节点到下一个节点的移动后 ,即经过一个时间单位之后 ,进行一次信息素挥发 , 这种离散时间点挥发方式与蚂蚁觅食机理是完全相符的。 引入启发因子。 蚁群算法的整个过程体现了自组织性 ,但是这种自组织系统 存在一个缺陷 ,就是系统的演化需要很长时间。 因此在决定蚂蚁行走方向的状态 转移概率时 ,引入一个随机搜索过程 ,即引入启发因子 ,根据所求问题空间的具 体特征 ,给蚁群算法一个初始引导 ,这个过程极大地加快了算法的时间有效性。 通过上述描述的一些抽象过程 ,可以建立一个蚁群算法的基本模型。 其问题 空间是用图来描述的 ,解的获取是构造性的 ,而且在解的构造过程中人工蚂蚁没 有接受任何全局的指导信息 ,因而求解过程是自组织的。 在定义了一些规则之后 , 蚁群算法就可以求解那些可用图描述的问题。 蚁群算法的数学模型可以描述如下【 `4]Il8][l9]: 设 C一 {cl,cZ,„ ,c。 }为。 个节点的集合 ,L一 {气 }c,c,。 C}是 C中节点两两连 接的路径权值集合 ,几 (t)为 t时刻路径 (i,力上的信息素浓度 ,r=笼几 (t)}ci,cj任 C} 是 t时刻路径 (i,力上残留信息素浓度的集合 ,在初始时刻各条路径上的信 息素浓 度相等 ,并设几 (0)=const,蚁群算法就是通过有向图 G=(C,L,r)实现的。 n 设互 (t)(i二 `,2,一” )是 t时刻节点 `的蚂蚁数 ,则 m。 一艺今 (t)为全部蚂蚁数。 i=, 每只人工蚂蚁有以下特性 : (l)蚂蚁根据一定概率函数选择下一节点 ,其中概率函数是节点之间权值及 边上信息素浓度的函数。 (2)每只人工蚂蚁只能走合法路线 ,除非一次遍历结束 ,不允许转到己经访 群算 .法求解 0一 l背包问题 时间内通过该桥的蚂蚁成正比。 其次 ,再假设某一时刻蚂蚁按照桥上的残留信息 素的多少来选择其中某座桥 ,经过 该桥的蚂蚁数目越多 ,则该桥上的残留信息素 就越多。 该例中 ,假设短桥为 A,长桥为 B,从 ,:和尽。 :分别表示经过桥 A和经过 桥 B的蚂蚁数目 (态 +凡 ,=m),则当所有 m只蚂蚁都经过两座桥后 ,第 m+l只 蚂蚁选择 A桥的概率为 :凡 (m)(A,。 +k)“ (A,+k)力 +(B,+k)丙 (次 ,(尽” 选择 B桥的概率为 :凡 (m)=1一凡 (m) 式中 ,参数 h和 k用以匹配真实实验数据。 第 m+1只蚂蚁按概率选择不同的桥。 根据上面的模型 ,对蚁群觅食过程进行计算机动态模拟 ,最终的结果是蚂蚁 会集中在离食物源最近的路径上。 根据蚂蚁觅食的群体行为 ,意大利学者 DorigoM等【 `“ ]于 1991年在法国巴黎 召开的第一界欧洲人工生命会议 (EuropeanConfereneeonArtifieialLife,EeAL) 上最早提出了蚁群算法的基本模型。 1992年 ,DorigoM又在其博士学位论文中 进一步阐述了蚁群算法的核心思想【 39。 5】。 .,蚁群算法模型的建立 蚁群算法的模型主要从下面几个方面对自然界中真实蚂蚁觅食行为进行了 抽象 [39。 “ ][39。 7]: 对蚂蚁个体的抽象。 由于蚁群算法只是对蚂蚁觅食行为的一种 模拟 ,没有必 要对蚂蚁个体进行完全再现 ,摒弃与算法无关的因素 ,这样抽象出来的人工蚂蚁 可以看作一个简单的智能体 ,能够构造所求问题的解 ,也能通过一种信息手段相 互影不 !l句。 对问题空间描述的抽象。 自然界中的真实蚂蚁存在于一个连续的三维空间 中 ,但计算机只能处理一些离散的点。 在实现过程中 ,一般都将蚁群算法求解的 问题转换成数学上的图 (graPh)来描述 ,在实际工程中许多问题都可以用图来描 述 ,这也是蚁群算法应用广泛的一个原因。 对寻找路径的抽象。 蚂蚁的觅食路径在现实中是一个面上连续路径 ,但是计 群算 .法求解 O一 l背包问题 问的节点。 该过程由蚂蚁的禁忌表来控制 ,禁忌表 tabu*(k二 1,2,„ ,m。 )用来记录 蚂蚁 k当前走过节点的集合 ,如果蚂蚁 k经过节点 i,就将节点动口入到自己的禁忌 表中 ,表示下次不能再选择节点 i,这样集合会随着移动过程作动态调整。 (3)完成一次遍历后 ,蚂蚁在其访问过的每一条边上留下相应的信息素。 蚁群算法可以表述如下 :在算法初始时刻 ,将 mc只蚂蚁随机放到 n个节点 , 同时更新禁忌表 ,此时各条路径上的信息素相等 ,且为一常数。 接下来 ,蚂蚁 k(k=l,2,二 ,m。 )在运动过程中 ,根据各条路径上的 信息素浓度决定其转移方向。 在搜索过程中 ,蚂蚁根据各条路径上的信息素及路径。