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

CompanyLogoCompanyLogoCompanyLogoCompanyLogo改进型遗传蚁群混合算法求解

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]之间。0102A1：采用遗传算法寻优的个体集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