遗传蚁群算法解决背包问题

改进型遗传蚁群混合算法求解0/1背包问题报告人：宋玲地点：计算机院软工实训室时间：2013年11月15日研究背景背包问题（KnapsackProblems）是运筹学中的一个典型的优化难题，对背包问题的研究具有极其重要的理论和现实意义。实际生活中，资源分配、投资决策、装载问题、网络资源分配等问题都可归纳为背包问题。目前，已经出现许多种求解背包问题的优化算法。其中遗传算法是一种基于自然选择和群体遗传机理的搜索算法，模拟了自然选择和自然遗传过程中的繁殖、杂交和突变现象。它属于随机搜索算法，具有较强的全局搜索能力，但遗传算法中的个体对于每次的选择不存在反馈信息，因此遗传算法的收敛速度较慢，而且优化精度不高。蚁群算法在求解0/1背包问题时，主要通过物品上的信息素进行选择，一个物品上的信息素越高，被选择的概率就越大。蚁群算法采用正反馈机制，能够快速地收敛到问题的局部最优解，但存在全局搜索能力较低、搜索时间较长等缺点。由于两种算法各有利弊，近年来，许多学者致力于两种算法的混合研究。本文提出了一种基于两者新的混合方式的算法，来求解0/1背包问题。主要内容背包问题数学模型1算法步骤3算法的混合方式概述2仿真结果分析5结论6算法策略4背包问题数学模型通常，0/1背包问题被描述为：有一个背包和n件物品，其中背包所能承受的最大重量为C，物品j的重量为Wj，价值为Pj，求解0/1背包问题的目标是从n件物品中选择部分物品装入背包，在满足所选物品的总重量不超过C的情况下，使得装入背包的物品的总价值最大。其中，xj=1表示物品j被选中，xj=0表示物品j没有被选中。改进的遗传蚁群混合算法的混合方式现实中，自然界的蚂蚁分工是十分明确的，大约有1/4蚂蚁是专门寻找新食物源的，受其启发，我们提出了一种新混合方式：挑选部分优秀人工蚂蚁采用遗传算法寻优，并利用此结果对蚂蚁系统进行信息素的全局更新，指引蚁群向最优方向寻优；剩余蚂蚁采用蚁群算法寻优，并利用此结果对蚁群系统进行信息素的局部更新，指引下一个蚂蚁的寻优方向。这样，一方面利用遗传算法中的交叉、变异操作产生新个体，扩大种群的多样性，增强算法的全局搜索能力，另一方面利用蚁群算法提高寻优精度。为了描述自然界中蚂蚁群根据环境的改变而做出调整的特性，该算法中采用两种不同寻优方式的蚂蚁数目随迭代次数自适应改变。算法的具体过程为：在每次迭代过程中，蚂蚁数固定为m，挑选k只优秀的蚂蚁采用遗传算法寻优，寻优结束进行全局信息素更新，其余蚂蚁采用蚁群算法寻优，寻优结束进行局部信息素更新。一代寻优结束后，m只蚂蚁寻得的解和上一代的前k个解共同参与排序，排序后的前k个解作为下一次迭代中遗传算法的初始种群。为保证蚂蚁的寻优能力和寻优效率，k值随进化代数自适应变化，并且对k值采用上下限策略，k的取值在区间[1/4，3/4]之间。A1：采用遗传算法寻优的个体集A2：采用蚁群算法寻优所得的解集Allowed：蚂蚁i下一次允许选择的物品序号集Tabu：蚂蚁i已经选择的物品序号集Over：下一次选择时Allowed中不满足约束条件的物品序号集G：最大迭代次数M：蚂蚁总个数K：进行遗传算法寻优的蚂蚁个数CodeL：物品数目算法步骤—各个参数含义算法步骤采用上述中遗传蚁群的混合方式，设计了两种算法（算法1中k值从3×m/4逐渐减小到m/4，算法2中k值从m/4逐渐增加到3×m/4）。算法流程（算法1）：步骤1参数初始化步骤2随机生成矩阵A1（k，CodeL），并对其按适应值大小进行降序排列◆步骤3对迭代次数循环（g=g+1）步骤4判断k是否小于m/4，若是，则k=m/4，否则k=3×m/4－2×（g－1）步骤5对k个蚂蚁使用遗传算法寻优（1）复制矩阵A1（B=A1）（2）根据交叉概率Pc对A1进行交叉操作（3）根据变异概率Pm对A1进行变异操作（4）对所求得的不可行解进行修复操作（5）进行全局信息素更新算法2中只需修改步骤4步骤4判断k是否大于3×m/4，若是则k=3×m/4，否则k=m/4+2×（g－1）。算法步骤步骤6对（m－k）个蚂蚁使用蚁群算法寻优（1）初始化Allowed=[1：CodeL]，Tabu=[]，Over=[]A2=zeros（（m－k），CodeL）（2）判断Allowed是否为空，若为空时转步骤6（-6），若不为空则转步骤6（-3）（3）求Allowed中所有物品被选择的概率（4）蚂蚁i按物品被选择的概率以轮盘赌的方法Allowed中选择一个物品j（5）更新Allowed、Tabu和Over（6）进行局部信息素更新（7）判断（m－k）个蚂蚁是否全部搜索完毕，若全部搜索完毕，则转步骤7，否则转步骤6（-1）步骤7对矩阵B、A1和A2按适应值大小进行降序排列，选取前k条个体组成A1步骤8保留此代中的最优值步骤9判断是否满足结束条件（gG），若满足则输出最优结果，否则转步骤3算法策略（1）交叉操作（步骤5（2））中，交叉的第一个个体由交叉概率Pc决定，交叉的第二个个体为与第一个个体海明距离（两个码字的对应比特取值不同的比特数称为这两个码字的海明距离）最大的个体，交叉起始位置为两个个体第一个不相同的基因位X，交叉的基因位个数在1和（n－X）（n为物品个数，即染色体的长度）之间随即产生。这样可以最大限度地产生新个体，增加种群的多样性。（2）变异操作（步骤5（3））中，变异的基因位个数随机产生，每个基因位变异的概率由当代种群中每个基因位上1和0的比例之差的绝对值决定，差值越大变异概率越小，相反差值越小变异概率越大。把每个基因位变异的概率按照从大到小的循序排列，根据随机产生的基因位个数选取要变异的前几个基因位进行变异操作。此种变异操作方式尽可能地确保算法寻得的最优解为全局最优解。（3）修复操作（步骤5（4））。本文采用目前最常用的启发式修复策略，当某个解违反了约束条件则对其进行修复，修复时按物品的价值重量之比递增排列，然后按此顺序依次删除背包中的物品直到满足约束条件为止。算法策略（4）Allowed中物品j被选择的概率（步骤6（3））为：其中，tj为物品j上的信息素浓度，初始信息浓度tj相等，本文设tj=1/sum(P)（P为物品的价值集），qj为物品j的价值重量比。（5）选择操作（步骤7）采用排序法，所有蚂蚁和上代中的前k个个体共同参与排序。遗传算法和蚁群算法均采用0、1编码和统一的信息素更新公式：其中，tj(g)为第g代物品j上的信息素浓度，ρ为信息素挥发系数，Δtj为物品j上的信息素变化量，Δt为蚂蚁i在物品j上留下的信息素量，Q为定值，本文取Q=1/m*sum(P)Li为当代中蚂蚁i所选择的物品的价值重量比之和。ij仿真实验结果分析为验证本文算法的有效性，本文对文献[4]中的3个0/1背包问题算例进行了测试。其中蚂蚁数m=200，Pc=0.8，Pm=0.15，信息素权值a=1，期望权值b=1，信息挥发系数ρ=0.7。每种算法均运行20次，测试结果如表（算法1和算法2是本文的两种算法，算法3采用文献[2]的混合方式，算法4采用文献[3]的混合方式，算法5的结果来自参考文献[4]）。另注：表1~表3中---表示没有达到最优解，***表示文献中没有此结果。表1中，算法1、2所求得最优解明显好于其他算法，对于算例2，算法2稍好于算法1。仿真实验结果分析表2中，对于算法的收敛速度，算法2稍好于算法1，算法4次之，算法3最慢。表3中，对于程序的运行速度，算法2最快，其次是算法1和3，算法4最慢。结论仿真实验的结果表明：在求解0/1背包问题上，本次报告提出的两种算法不论是在最优解方面还是求解速度方面都有很大的提高，并且算法2在程序运行速度方面也得以较大改善，从而表明了本算法的有效性。通过对遗传算法和蚁群算法优缺点的分析，以及对两种算法混合方式的研究，提出了一种新的混合方式，采用这种混合方式，设计了两种算法。为了使算法的寻优性能更好，寻优速度更快，在对两种算法进行混合的基础上，进一步改进了传统遗传算法中的交叉和变异操作算子，并且对蚁群算法的赋值等方面也进行了一些改善。通过对实例的仿真，证明本文提出的算法在求解背包问题时，算法的寻优性能、寻优速度和程序运行速度都得到很大的改善。参考文献[1]王娜，向凤红，毛剑琳.改进型遗传蚁群混合算法求解0/1背包问题[J].计算机工程与应用，（2013）09-0054-03[2]康岚兰，曹文梁.混合遗传蚁群算法的改进及在TSP问题中的应用研究[J].科技广场，2010（7）：10-12.[3]汤旻安，任恩恩，赵春艳.遗传蚁群算法的公交车辆调度路线优化[J].微计算机信息，2009（31）：48-49.[4]李康顺，贾玉珍，张文生.一种基于模式替代的遗传算法解0/1背包问题[J].计算机应用研究，2009，26（2）：470-471.Thankyou!结束