遗传蚁群混合求解背包问题

《遗传蚁群混合求解背包问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、改进型遗传蚁群混合算法求解所在院系学科专业研究生姓名指导老师0/1背包问题计算机技术与工程学院农业信息化高静201341431.研究背景22.背包问题数学模型23.混合方法概述24.算法步骤35.算法策略46.仿真实验结果分析57.结论6参考文献71•研究背景背包问题(KnapsackProblems)是运筹学中的一个典型的优化难题，对背包问题的研究具有极艾重要的理论和现实意义。实际生活中，资源分配、投资决策、装载问题、网络资源分配等问题都可归纳为背包问题。目前，已经出现许多种求解背包问题的优化算

2、法。英中遗传算法是一•种基于自然选择和群体遗传机理的搜索算法，模拟了自然选择和自然遗传过程屮的繁殖、杂交和突变现彖。它属于随机搜索算法，具有较强的全局搜索能力，但遗传算法中的个体对于每次的选择不存在反馈信息，因此遗传算法的收敛速度较慢，而且优化精度不高。蚁群算法在求解0/1背包问题时，主要通过物品上的信息素进行选择，一个物品上的信息素越高，被选择的概率就越大。蚁群算法采用正反馈机制，能够快速地收敛到问题的局部最优解，但存在全局搜索能力较低、搜索时间较长等缺点。由于两种算法齐有利弊，近年来，许多学者

3、致力于两种算法的混合研究。本文提出了一•种基于两者新的混合方式的算法，来求解0/1背包问题。2.背包问题数学模型通常，0/1背包问题被描述为：有一个背包和n件物品，其中背包所能承受的最大重量为C,物品j的重量为Wj,价值为Pj,求解0/1背包问题的目标是从n件物品中选择部分物品装入背包，在满足所选物品的总重量不超过C的情况下，使得装入背包的物品的总价值最人。nMaxv=Max/(xpx2,---9x„)=工几xy(1

4、被选中。3.混合方法概述现实屮，白然界的蚂蚁分工是十分明确的，大约有1/4蚂蚁是专门寻找新食物源的，受其启发，我们提出了一种新混合方式：挑选部分优秀人工蚂蚁采用遗传算法寻优，并利用此结果对蚂蚁系统进行信息素的全局更新，指引蚁样向最优方向寻优；剩余蚂蚁采用蚁群算法寻优，并利用此结果对蚁群系统进行信息素的局部更新，指引下一个蚂蚁的寻优方向。这样，一方面利用遗传算法屮的交叉、变异操作产生新个体，扩大种群的多样性，增强算法的全局搜索能力，另一方而利用蚁群算法提高寻优精度。为了描述白然界屮蚂蚁群根据环境的改

5、变而做出调整的特性，该算法屮采用两种不同寻优方式的蚂蚁数口随迭代次数自适应改变。算法的具体过程为：在每次迭代过程中，蚂蚁数固定为R1,挑选k只优秀的蚂蚁采用遗传算法寻优，寻优结束进行全局信息素更新，其余蚂蚁采用蚁群算法寻优，寻优结束进行局部信息素更新。一代寻优结束后，m只蚂蚁寻得的解和上一代的前k个解共同参与排序，排序后的前k个解作为下一次迭代中遗传算法的初始种群。为保证蚂蚁的寻优能力和寻优效率，k值随进化代数口适应变化，并且对k值采用上下限策略，k的取值在区间[1/4,3/4]之间。2.算法步骤

6、步骤1参数初始化步骤2随机生成矩阵Al(k,CodeL),并对其按适应值大小进行降序排列步骤3对迭代次数循环(g二計1)步骤4判断k是否小于m/4,若是，则k=m/4,否则k=3Xm/4-2X(g—1)步骤5对k个蚂蚁使用遗传算法寻优(1)复制矩阵Al(B=A1)(2)根据交叉概率几对Al进行交叉操作(3)根据变异概率Pm对A1进行变异操作(4)对所求得的不可行解进行修复操作(5)进行全局信息素更新步骤6对(m—k)个蚂蚁使用蚁群算法寻优(1)初始化Allowed=[l:CodeL],Tabu=[

7、],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、骤8保留此代屮的最优值步骤9判断是否满足结束条件(g>G),若满足则输出最优结果，否则转步骤3算法2屮只需修改步骤4步骤4判断k是否大于3Xm/4,若是则k二3Xm/4,否则k=m/4+2X(g—1)。其中Al：采用遗传算法寻优的个体集，A2：采用蚁群算法寻优所得的解集，Allowed：蚂蚁i卜一次允许选择的物品序号集，Tabu：蚂蚁i已经选择的物品序号集，Ovgt：卜•一次选择时Allowed中不满足约束条件的物品序号集，G：最人迭代次数，M：蚂蚁总个数，K：进行遗传算法寻优的蚂