蚁群算法思想论文：蚁群算法的0-1背包问题求解研究

1、蚁群算法思想论文：蚁群算法的0-1背包问题求解研究摘要：提出解决背包问题的蚁群算法思想及求解0-1背包问题问题描述，给出了改进常规的蚁群算法的方法。关键词：背包问题，蚁群算法，问题设计，算法改进1问题描述0/1背包问题是指有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品且对每一物品，要么选，要么不选，满足被选物品的总重量不超过背包指定的限制重量且达到被选物品的价值总和最大的问题。如果所有物品的重量之和小于背包的容量，贝恫题极其简单，所得利益也就是所有物品的价值之和。2蚁群算法的思想蚁群算法是模仿真实的蚁群行为而提出的一种模拟进化算法.蚂蚁之间是通过一种称为信息素(Pheromon

2、e)的物质传递信息的，蚂蚁在运动过程中能够在经过的路径上留下该种物质，而且能够感知这种物质的存在及其强度，并以此指导自己的运动方向.因此，由大量蚂蚁组成的集体行为便表现出一种信息正反馈现象：某一条路径上走过的蚂蚁越多，该路径上留下的信息素就越多，则后来者选择该路径的概率就越大.蚂蚁个体之间就是通过这种信息素的交流，搜索到一条从蚁巢到食物源的最短路径.3利用蚁群算法求解0-1背包问题设计设有n个城市，d,(i,J=l,2,，n)表示城市i和J间的距离，t.j(t)表示在t时刻城市i和j之间的信息量，以此来模拟实际蚂蚁的分泌物。设共有m只蚂蚁，用P.ijk表示在t时刻蚂蚁k由城市i转移到城市J的概

3、率，则Pk.ijk(t)由城市i转移到城市J的概率，贝SQ.ij(t)Ii.ij(t)ErallowedkQ.ir(t)卩.ir(t)jallowdk0otherwise其中，allowedk表示蚂蚁k下一步允许走过的城市的集合，表示路径上的信息量对蚂蚁选择路径所起的作用大小，n为由城市i转移到城市j的期望程度，例如，可以取nij=1/d.ij。B表示nij的作用。当a=0时，算法就是传统的贪心算法；而当p=O时,就成了纯粹的正反馈的启发式算法。经过n个时刻，蚂蚁走完所有的城市，完成一次循环。每只蚂蚁所走过的路径就是一个解。此时，要根据式(3)对各路径上的信息量作更新：tij(t+1)=(1-

4、p)?tij+Atij(2)其中p(0,I),表示信息量r.ij随时间的推移而衰减的程度。信息增量AT可表示为Axij=Dmk=1k.ij其中Ajk表示蚂蚁k在本次循环中在城市i和之间留下的信息量，它的计算公式根据计算模型而定，例如在最常用的antcirclesystem模型中.蚂蚁k在本次循环中经过城市i和j之间AtQ/L.k蚂蚁k在本次循环中经过城市i和j之间Totherwise其中Q为常数，为蚂蚁k在本次循环中所走路径的长度。经过若干次循环以后，可以根据适当的停止条件来结束计算。4算法描述蚁群算法的主要步骤如下：步骤1:初始化。步骤2:生成M只蚂蚁，并将其置于节点1。步骤3：for每只蚂蚁do按照式（1）计算并选择下一条有向线段；如果没有有向线段满足背包问题的约束条件，则该蚂蚁就死掉：如果蚂蚁没有死亡.则将选择有向线段的序号加入蚂蚁的禁忌表中；.步骤4:计算本次迭代的最好解.如果其优于当前的最好解。则用其