基于离散差分进化算法的多维01背包问题求解

背包问题报告小组成员：张灿、吴雪涛、高坤、占强、习慧平小组分工情况小组成员查找资料制作ppt 编写程序讲解ppt 制作报告张灿ⅴⅴⅴⅴⅴ吴雪涛ⅴ高坤ⅴⅴ占强ⅴ习慧平ⅴ背包问题一、背包问题的历史由来它是在1978年由Merkel和Hellman提出的。

它的主要思路是假定某人拥有大量物品，重量各不同。

此人通过秘密地选择一部分物品并将它们放到背包中来加密消息。

背包中的物品中重量是公开的，所有可能的物品也是公开的，但背包中的物品是保密的。

附加一定的限制条件，给出重量，而要列出可能的物品，在计算上是不可实现的。

背包问题是熟知的不可计算问题，背包体制以其加密，解密速度快而其人注目。

在解决大量的复杂组合优化问题时，它常常作为一个子问题出现，从实际的观点看，许多问题可以用背包问题来描述，如装箱问题，货仓装载，预算控制，存储分配，项目选择决策等，都是典型的应用例子。

随着网络技术的不断发展，背包公钥密码在电子商务中的公钥设计中也起着重要的作用。

然而当问题的规模较大时，得到最优解是极其困难的。

但是，大多数一次背包体制均被破译了，因此现在很少有人使用它。

二、背包问题的描述背包问题(Knapsack problem)是一种组合优化的NP完全问题。

问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。

问题的名称来源于如何选择最合适的物品放置于给定背包中。

相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。

也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V？三、背包问题的定义我们有n种物品，物品j的重量为w j，价格为p j。

我们假定所有物品的重量和价格都是非负的。

背包所能承受的最大重量为W。

如果限定每种物品只能选择0个或1个，则问题称为0-1背包问题。

可以用公式表示为：maximizesubject to如果限定物品j最多只能选择b j个，则问题称为有界背包问题。

基于分解的多目标进化算法摘要：在传统的多目标优化问题上常常使用分解策略。

但是，这项策略还没有被广泛的应用到多目标进化优化中。

本文提出了一种基于分解的多目标进化算法。

该算法将一个多目标优化问题分解为一组？？？单目标优化问题并对它们同时优化。

通过利用与每一个子问题相邻的子问题的优化信息来优化它本身，这是的该算法比MOGLS和非支配排序遗传算法NSGA-Ⅱ相比有更低的计算复杂度。

实验结果证明：在0-1背包问题和连续的多目标优化问题上，利用一些简单的分解方法本算法就可以比MOGLS和NSGA-Ⅱ表现的更加出色或者表现相近。

实验也表明目标正态化的MOEA/D算法可以解决规模范围相异的多目标问题，同时使用一个先进分解方法的MOEA/D可以产生一组分别非常均匀的解对于有3个目标问题的测试样例。

最后，MOEA/D在较小种群数量是的性能，还有可扩展性和敏感性都在本篇论文中通过实验经行了相应的研究。

I.介绍多目标优化问题可以用下面式子表示：Maximize F(x)=((f1(x)…...f m(x))Tsubject to x∈Ω其中Ω是决策空间，F：Ω→R m，包含了m个实值目标方法，R m被称为目标区间。

对于可以得到的目标集合成为{F(x)|x∈Ω}。

如果x∈R m，并且所有的目标函数都是连续的，那么Ω则可以用Ω={x∈R n|h j(x)≤0,j=1……m}其中hj是连续的函数，我们可以称(1)为一个连续的多目标优化问题。

如果目标函数互斥，那么同时对所有目标函数求最优解往往是无意义的。

有意义的是获得一个能维持他们之间平衡的解。

这些在目标之间获得最佳平衡的以租借被定义Pareto最优。

令u, v∈Rm，如果u i≥v i对于任意的i，并且至少存在一个u j≥v j(i,j∈{1…..m})，那么u支配v。

如果在决策空间中，没有一个点F(y)能够支配F(x)点，那么x就是Pareto最优，F(x)则被称为Pareto最优向量。

一种求解0-1背包问题的启发式遗传算法王秋芬;梁道雷【摘要】分析求解背包问题的多种方法,研究背包问题的贪婪策略及最优值的特点,将贪婪策略融入到遗传算法的种群初始化、交叉算子、变异算子中,将分治策略引入到选择算子中,提出一种启发式遗传算法.实验结果表明:算法无论在求解速度上还是在求解质量上都有明显改进.%In this paper we analyse various methods for solving the knapsack problem, and study the greedy strategy of knapsack problem and the characteristics of its optimal value. By integrating the greedy strategy into population initialisation, crossover operator and mutation operator of the genetic algorithm, and introducing the divide-and-conquer strategy to selection operator, we propose a heuristic genetic algorithm. Experimental results show that for both the quality of solution and the time consumed in problem solving, this algorithm all makes obvious improvement.【期刊名称】《计算机应用与软件》【年(卷),期】2013(030)002【总页数】6页(P33-37,57)【关键词】背包问题;遗传算法;贪婪策略;分治策略【作者】王秋芬;梁道雷【作者单位】华东师范大学计算机科学技术系上海200062;浙江理工大学理学院浙江杭州310018【正文语种】中文【中图分类】TP3010 引言0－1背包问题的一般描述为:给定n个物品的重量wi(wi＞0)和价值pi(pi＞0)(i=1，2，…，n)，又给定一个背包，容量限制为C(C＞0)，问如何装入物品，使得在不超过背包容量限制的前提下，装入的物品总价值最大，单个物品不允许分割。

现代经济信息求解０－１背包问题算法研究田秀芹 百色学院数学与统计学院摘要：本文主要概述了求解0-1背包问题的两大类算法：精确算法和近似算法，并分析了这些算法的优缺点，并提出了求解该问题的算法发展趋势。

关键词：0-1背包问题；精确算法；近似算法中图分类号：TP312 文献识别码：A 文章编号：1001-828X(2017)010-0386-03The Study of the 0-1 Knapsack Problem AlgorithmAbstract: This paper mainly summarizes the solving 0-1 knapsack problem algorithm of two categories: accurate and approximate algorithms, and analyzes the advantages and disadvantages of these algorithms, and put forward the development trend of algorithms to solve the problem.Keywords: 0-1 knapsack problem, precise algorithm, approximate algorithmDantzig[1]在20世纪50年代首次提出了背包问题(Knapsack problem，简称KP)，在文献[2]中，阐述了该问题是一个NP-难问题，在背包问题中，我们很难设计出多项式时间算法，除非P=NP。

0-1背包问题就是，给定一个容量为的背包和件具有价值的物品，在不超过背包容量的前提下，选择若干物品放入背包，使得装入背包的物品总价值最大。

同时给出一种放置物品的方案。

背包问题就有普遍的应用背景，在日常的许多实践中如：材料切割、资源有效分配问题、资金估算的问题、运输过程的货仓装载等起着很大的作用，许多的组合优化问题都可以简化为背包问题，背包问题的各种解法也可用来解决组合优化问题，因此对0-1背包问题的解法进行深入的研究具有重大的意义。

《工业控制计算机》2021年第34卷第5期83基于离散二进制粒子群-模拟退火算法求解0-1背包问题Solv i ng0-1Kn apsack Problem Based on Part i c le B in a ry Swarm-S i mulatedAnneali ng Algor ithm汤飞何永义（上海大学机电工程与自动化学院，上海300444）摘要：0-1背包问题是最典型的组合优化问题之一遥目前,有很多算法来解决这个问题，主要分为两类：一个是传统的算法，虽然它在低维和小规模的背包问题中有一个良好的寻优性能，但对于高维大规模的背包问题解决能力显然不占优势；另一个是仿生智能算法，它虽然能够很好地解决高维大规模的背包问题，但使用单一算法总是存在一定的局限性。

在搜索解的过程中缺乏全局搜索能力，易陷入局部最优解。

针对这一问题，提出了BPSO-SA算法，利用BPSO算法的全局搜索的优点，再引入了SA算法的退火过程中思想，使算法避免陷入局部最优解。

通过大量的实验测试，验证了该文提出的算法的可行性，并且具有更好的寻优能力。

关键词：粒子群;模拟退火；0-1背包问题Abstract:The0-1knapsack problems one of the most typ i c al comb i n ator i a l opt i m i z at i o n problems.At present,there are many algor i t hms to solve th i s problem,ma i n ly d i v i dednto two categor i es：one is the trad it i o nal algor i thm,although it has s good opt i m i z at i o n performance in low-d i m ens i o nal and small-scale knapsack problems,but for h i g h-d i m ens i o nal large-scale knapsack problems,the solut i o n ab il ity is obv i o usly not the dom inant one;the others the b ion i c intell i g ent algor i t hm.Although it can solve the h igh-d imens i o nal and large-scale knapsack problem well,the use of a s i n gle algor i t hm always has certa i n l i m i t at i o ns.In the process of search i n g the solut i o n,i t lacks the global search ab il ity,and it is easy to fallnto the local opt imal solut ion.A i m i n g at th i s problem,th i s paper proposes the BPSO-SA algor i thm,wh i c h uses the advantages of the BPSO algo­rithm's global search,and then introduces the SA algor i thm's anneal i n g process idea,so that the algor i t hm avo i d s fall ing into the local opt i m al solut i o n.Through a large number of exper i m ental tests,the feas i b il i t y of the algor i t hm proposed in th i s paper is ver i f i ed,and it has better opt i m i z at i o n ab il ity.Keywords:part i c le swarm,s i m ulated annealing,0/1knapsai0-1背包问题(0-1Knapsack Problem,0-1KP)是运筹学中经典的组合优化问题［1］，其最终的目的是找到满足背包约束的最有价值的物品加载方案咱y」。

求解0-1背包问题的改进混合遗传算法刘寒冰;张亚娟【摘要】针对一种混合遗传算法所采用的贪心变换法的不足，给出了一种改进的贪心修正法；并基于稳态复制的策略，对遗传算法的选择操作进行改进，给出了随机选择操作。

在此基础上，提出了一种改进的混合遗传算法，并将新算法用于解决大规模的0-1背包问题，通过实例将新算法与 HGA 算法进行实验对比分析，并研究了变异概率对新算法性能的影响。

实验结果表明新算法收敛速度快，寻优能力强。

%An improved greedy correction method is advanced for overcome the flaw of greedy transform method adopted by hybrid genetic algorithm (HGA). And based on steady state reproduction strategy, the choice method of random selection is advanced. These new methods are combined with genetic algorithm to propose a high-efficient hybrid genetic algorithm (IHGA), and new algorithm was used to solve large-scale 0-1 knapsack problem. By many simulation experiments, IHGA algorithm is compared with HGA algorithm, and how the mutation probability affect the performance of the new algorithm has been studied. The experimental results show that the new algorithm has higher convergent speed and better optimization capability.【期刊名称】《计算机系统应用》【年(卷),期】2015(000)006【总页数】5页(P197-201)【关键词】混合遗传算法;0-1背包问题;贪心变换;随机选择;贪心修正【作者】刘寒冰;张亚娟【作者单位】黄河科技学院信息工程学院，郑州 450063;黄河科技学院信息工程学院，郑州 450063【正文语种】中文0-1背包问题属于组合优化理论中最重要的问题之一, 是计算科学中的一个经典NP问题, 也是算法界最典型的一个实例. 求解该问题的算法很多, 主要分为精确算法和近似算法两大类. 精确算法主要有分支限界法、回溯法和动态规划算法等[1]. 精确算法求解0-1背包问题时, 是先找出问题的所有候选解, 然后按一定的方式在候选解中找出满足约束条件的最优解. 这类精确算法能找到问题的最优解, 具有较高的精确度, 但随着待选择物品数量和背包容量的增长, 算法的时间复杂度对于输入是指数级的, 计算效率较低. 因此, 对该问题进行研究的一些学者提出了一些近似算法来解决该问题, 如贪心算法[1]、遗传算法[2-5]、微粒群算法[6]、蚁群算法[7]等, 这些算法虽然不能保证求出问题的最优解, 但能在可接受的时间内求出最优解的近似解.遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率的近似算法. 该算法通过对生物遗传和进化过程中选择、交叉、变异机理的模仿, 来完成对问题最优解的自适应搜索过程[2]. 该算法具有全局优化性、通用性、并行性、稳健性和简单性等特点. 近年来, 将遗传算法用于解决0-1背包问题已取得良好进展, 但处理后期收敛速度、局部的寻优能力方面仍无法达到理想的效果. 贪心算法是一种用来解决较复杂的最优化问题的近似算法. 该算法解决问题时是从问题的某一个初始解出发逐步逼近给定的目标, 以尽可能快的速度求得更好的解.因此, 该算法具有设计简单、复杂度低、运行速度快等特点. 但该算法并不从整体最优解考虑, 它所做出的选择只是在某种意义上的局部最优选择, 因此, 用贪心算法解决0-1背包问题, 求解的效率较高, 但不能保证得到最优解.文献[8]中将贪心算法与遗传算法相结合形成混合遗传算法(Hybrid Genetic Algorithm, HGA). 在HGA中应用贪心算法, 是为了把经过交叉、变异后得到的不满足约束条件的染色体变成满足约束条件的染色体, 这样能提高种群的多样性和求解效率, 但后期的收敛速度和寻优能力并没有明显改进.为此, 本文在HGA算法的基础上, 提出了一种求解0-1背包问题的改进混合遗传算法, 该算法采用新的贪心修正法对染色体进行修正, 同时对选择操作进行改进, 并通过实例进行仿真实验, 实验表明该算法具有较高的收敛速度和寻优能力.1.1 0-1背包问题给定n种物品和一个背包. 物品i的重量是wi, 其价值为vi, 背包的容量为C. 问应如何选择装入背包的物品, 使得装入背包中物品的总价值最大？在选择物品装入背包时, 对每物品只有两种选择, 不装和全装. 此问题的数学描述是:其中, xi代表第i种物品的选择情况, xi=1代表第i种物品装入背包, xi=0代表第i种物品不装入背包. 公式(1)是价值和表达式, 公式(2)是约束条件.1.2 染色体的修正在解决0-1背包问题的遗传算法中, 将随机产生的初始种群中的染色体和经过交叉、变异操作后得到的新染色体分为三类: 不满足约束条件的染色体、满足约束条件但背包资源利用不足的染色体、满足约束条件并且背包资源充分利用的染色体. 文献[8]中提出的混合遗传算法(HGA)中应用贪心算法, 是为了把经过交叉、变异操作后得到的不满足约束条件的染色体通过贪心变换操作修正为满足约束条件的染色体. 贪心变换的基本思想: 对于不满足约束条件的染色体, 将该染色体中所表示的已选中的物品按单位重量价值比vi/wi从大到小的次序进行排序, 然后根据排列次序将物品装入背包, 直到背包无法装入为止, 将剩余的未装入背包的物品状态由“装”改变为“不装”. 分析HGA算法中贪心变换操作发现存在不足: 在贪心变换方法中只能对不满足约束条件染色体进行修正使其转化为满足约束条件的染色体, 但修正后的染色体不一定是充分利用背包资源的染色体, 因而就会影响算法的收敛速度和寻优能力. 因此, 本文中对不满足约束条件的染色体和满足约束条件但背包资源利用不足的染色体设计了贪心修正法进行修正, 使其转化为背包资源充分利用的染色体, 进而提高算法的收敛速度和寻优能力.1.3 子代的选择对文献[9]中提到的稳态繁殖的选择策略进行研究. 稳态繁殖的选择策略的基本思想是: 在每个繁殖代, 将通过交叉、变异和贪心变换操作后得到的子代染色体, 按比例t(0<t<1)选择最优的部分染色体替换父代中较弱的染色体. 这种选择方式能保留最优染色体也能保持种群的多样性, 但是也存在不足, 主要是替换比例t的选择问题, t 的值越大, 算法收敛的速度就越快, 就会引起染色体早熟. 针对这一不足, 本文采用随机选择策略, 每代中替换率的选择是根据父代和子代中染色体的适应度而随机确定的, 每次选择时替换率都是变化的, 只在子代染色体的适应度值高于父代染色体的情况下, 子代染色体才可以替换掉父代染色体, 否则父代染色体仍保留在下一代群体中, 故它既能有效地维持种群多样性, 又能避免因替代率太高而引起染色体早熟现象.1.4 迭代终止条件由于该算法采用的是随机选择法, 新生种群中的染色体是按适应度的降序进行排列的, 所以当新生种群中第一个染色体的适应度与最后一个染色体的适应度相等时, 表示种群中所有染色体的适应度都相等. 繁殖过程就可以结束. 因此, 新算法迭代终止条件是: 新生种群中第一个染色体的适应度与最后一个染色体的适应度相等.本文提出了一种改进的混合遗传算法IHGA (Improved Hybrid Genetic Algorithm). 该算法首先对初始种群中的染色体和通过交叉、变异操作后得到的不满足约束条件的染色体和满足约束条件但背包资源利用不足的染色体采用贪心修正法进行修正, 使其转化为为背包资源充分利用的染色体, 然后对父代染色体和子代染色体进行随机选择产生下一代种群. 算法的流程图如图1所示.IHGA算法解决0-1背包问题的主要步骤如下:输入: n种物品的价值V=(v1,v2,…,vn), 重量W=(w1,w2,…,wn), 背包的容量C, 交叉概率PC, 变异概率PM, 种群规模M.输出: 根据0-1背包问题的数学表达式, 则输出的最优解是一个n元0-1向量(x1,x2,…,xn).1) 种群初始化采用二进制编码. 随机生成M个长度为n的“0”, “1”编码的串结构数据. 每个串结构数据代表一个染色体, M个染色体构成了一个群体, 称为初始种群, 从初始种群进行迭代.2)染色体修正对初始种群中的染色体进行修正, 修正主要分为两步:第1步: 修正不满足约束条件的染色体. 对于该部分染色体, 用HGA算法中的贪心变换法进行修正, 使其转换为满足约束条件的染色体, 如果转换后的染色体是背包资源充分利用的染色体, 则修正结束, 否则转为第2步.第2步: 修正满足约束条件但背包资源利用不足的染色体. 对于该部分染色体, 用贪心修正法修正.设X=(x1,x2,…,xn)是一个背包资源利用不足的染色体, 该染色体代表的选择是有r 个物品未装入背包, 背包剩余容量为C0, 通过贪心修正法将其修正为充分利用背包资源的染色体Y=(y1,y2,…,yn).贪心修正法的基本思想: 对染色体X中未装入背包中的物品按单位重量价值比的降序进行排序, 然后按排序的次序将相应的物品装入背包, 直到无法再装入为止.实现的步骤如下:排序. 对X中未装入背包中的物品按单位重量价值比v/w从大到小对物品的序号排序, 形成长度为r的序列{b1,b2,…,br}(即b1为单位重量价值比最大物品的序号, br 为单位重量价值比最小物品的序号).优化.①令k=1, W0=0, Y=X;②如果W0+ wbk≤C0, 则置ybk=1, W0=W0+wbk;③k=k+1, 如果k≤ r转②, 否则, 结束优化.3) 计算个体适应度染色体对环境的适应程度叫做适应度. 为了体现染色体的适应能力, 引入了对问题中的每一个染色体都能进行度量的函数, 叫适应度函数. 本算法中适应度函数为: 4)交叉用赌轮法随机取两个染色体, 依照概率PC选择个体进行交叉操作, 采用单点交叉, 将被选择出的两个个体S1和S2作为父母个体, 随机产生一个在1到n之间的数c, 将S1和S2的低c位交换, 产生新个体P1和P2.5)变异依照PM对繁殖个体进行变异操作, 采用基位变异, 将个体的基因链的各位按概率PM进行异向转化, “0”变异为“1”, “1”变异为“0”.6)选择本文中采用随机选择法. 在每一个繁殖代, 将通过交叉、变异和贪心变换操作后得到的子代染色体加入到父代染色体中形成一个新的群体, 对新群体中的个体按适应度的降序进行排序, 按排好序的次序从中选择前M个染色体作为新生种群. 这种选择策略中替换率t不是常量, 而是根据父代和子代中染色体的适应度随机变化的变量, 因而能解决稳态繁殖的选择策略中存在的不足. 另外, 新生代的产生是从子、父两代染色体群体中选择较优的, 能保证新生种群中染色体的最优性和多样性, 因而能提高算法收敛速度.用数组oldpop存储当前要进行繁殖操作的种群, 数组oldpop中的个体是有序的, 排序标准是根据个体的适应度进行降序排列, 用数组newpop存储由oldpop通过交叉、变异和贪心变换操作后产生的子代染色体.随机选择操作实现步骤如下:① 对数组newpop中的个体按适应度的降序进行排序;② 将数组oldpop中的个体与数组newpop中的个体按适应度从大到小进行合并排序, 将排好序的个体保存到数组tmp中;③ 取数组tmp中的前M个个体, 形成下一代种群.为了测试IHGA算法的性能, 并研究变异概率的取值对IHGA性能的影响. 本文对IHGA算法和HGA算法进行仿真实验. 实验中用到实例为0-1背包问题的经典实例, 实例选自文献[3], 两个实例的实验次数均为50次. 实验参数: n代表物品个数, C代表背包容量, J代表50次实验中得到的最满意值(背包中所装物品价值和的最大值), JC代表满意值在50次实验中出现的次数, JZ代表繁殖代数的均值.实例1如下:n=50, C=1000V={220,208,198,192,180,180,165,162,160,158,155,130,125,122,120,118,115, 110,105,101,100,100,98,96,95,90,88,82,80,77,75,73,72,70,69,66,65,63,60,58, 56,50,30,20,15,10,8,5,3,1}W={80,82,85,70,72,70,66,50,55,25,50,55,40,48,50,32,22,60,30,32,40,38,35,32 ,25,28,30,22,25,30,45,30,60,50,20,65,20,25,30, 10,20,25,15,10,10,10,4,4,2,1}实例2如下:n=100, C=6178V={597,596,593,586,581,568,567,560,549,548,547,529,529,527,520,491,482, 478,475,475,466,462,459,458,454,451,449,443,442,421,410,409,395,394,390, 377,375,366,361,347,334,322,315,313,311,309,296,295,294,289,285,279,277, 276,272,248,246,245,238,237,232,231,230,225,192,184,183,176,174,171,169, 165,165,154,153,150,149,147,143,140,138,134,132,127,124,123,114,111,104, 89,74,63,62,58,55,48,27,22,12,6}W={54,183,106,82,30,58,71,166,117,190,90,191,205,128,110,89,63,6,140,86, 30,91,156,31,70,199,142,98,178,16,140,31,24,197,101,73,169,73,92,159,71,1 02,144,151,27,131,209,164,177,177,129,146,17,53,164,146,43,170,180,171,1 30,183,5,113,207,57,13,163,20,63,12,24,9,42,6,109,170,108,46,69,43,175,81, 5,34,146,148,114,160,174,156,82,47,126,102,83,58,34,21,14}3.1 IHGA算法与HGA算法的性能比较实验中用到的交叉概率PC和变异概率PM分别为0.5和0.01. 实验结果如表1所示.从表1的实验数据可以看出, 在实例1中算法HGA和IHGA都能得到问题的最优值, 在实例2中, IHGA算法能求出问题的最优值, 而HGA算法仅能求出最优值的近似值, 这说明IHGA算法的寻优能力较强; 在50次实验中, IHGA算法出现的最优值次数明显高于HGA算法, 这说明IHGA算法的求解效率较高; 实例1中HGA 算法设置的繁殖代数为300, 而IHGA算法繁殖代数的均值仅为31.8, 实例2 HGA 算法设置的繁殖代数为500, 而IHGA算法的平均繁殖代数仅为63.5, 这说明采用贪心修正法和随机选择策略能提高IHGA算法的收敛速度和寻优效率. 从实例1和2的平均繁殖代数可以看出问题规模越大IHGA算法的寻优能力越强.3.2 不同变异概率下IHGA算法的计算性能为研究变异概率PM对IHGA算法的影响, 在交叉概率不变的情况下, 变异概率PM取5个不同值(0.005,0.01,0.02,0.05,0.10), 每种取值对实例1分别进行50次仿真实验, 多次实验得到的最满意值都为最优值3119, 满意值出现次数JC随变异概率变化曲线如图2所示, 繁殖代数均值JZ随变异概率变化曲线如图3所示, 图2、3中纵坐标为变异概率.从图2可以看出变异概率越大, 满意值出现的次数也越多, 但当变异概率增加到0.05时, 满意值出现的次数达到最好值50次. 从图3可以看出, 变异概率越大, 种群的平均繁殖代数越多, 当变异概率在0.005到0.02范围内变化时平均繁殖代数变化曲线增长缓慢, 变异概率在0.05到0.1范围内变化时平均繁殖代数变化曲线增长较快. 这是因为变异概率增大能够增加染色体的多样性, 提高算法的寻优能力, 但算法的收敛速度反而降低. 因此, 变异概率对算法的影响较大, 取值在0.01和0.05之间较好.本文提出了一种解决0-1背包问题的混合遗传算法IHGA, 该算法通过用贪心修正法对非优染色体进行修正和优化, 提高种群中染色体的质量, 进而提高算法的寻优能力; 对经过交叉、变异和修正操作后得到的子代染色体和父代染色体进行随机选择操作得到新生种群, 该操作既能保留父代中的最优染色体也能保持新生种群的多样性, 进而提高算法收敛速度. 用实例对算法进行仿真实验, 实验结果表明IHGA算法具有高效性和稳定性, 能够胜任大规模0-1背包问题的求解.1 王晓东.计算机算法设计与分析.第3版.北京:电子工业出版社,2008.2 周明,孙树栋.遗传算法原理及应用.北京:国防工业出版社,1999.3 吕晓峰,张勇亮,马羚.一种求解0-1背包问题的改进遗传算法.计算机工程与应用,2011,47(34):44–46.4 王秋芬,梁道雷.一种求解0-1背包问题的启发式遗传算法.计算机应用与软件,2013,30(2):33–37.5 Singh, RP. Solving 0-1Knapsack problem using Genetic Algorithms. Proc. of the 3rd IEEE International Conference on Communication Software and Networks. Xi’an, China. 2011. 591–595.6 Rana S, Jasola S, Kumar R. A review on particle swarm optimization algorithms and their applications to data clustering. Artificial Intelligence Review, 2011, 35: 211–222.7 何小锋,马良.求解0-1背包问题的量子蚁群算法.计算机工程与应用,2011,47(16):29–31.8 徐宗本.计算智能—模拟进化计算.北京:高等教育出版社,2005.9 董鹏.求解0/1背包问题的快速收敛的混合遗传算法.计算机工程与应用,2008,44(30):47–49.。

基于区域分割的差分进化算法求解0-1背包问题钟培华;吴志远;胡建根;朱丽【摘要】为了更有效地求解0-1背包问题，提出了基于区域分割的差分进化算法(PDE)。

为保证变异算子的封闭性，对传统差分进化算法(DE)的变异算子进行了修改。

引入区域分割算法以后，解空间中一些没有希望的点被移除，缩小了最优解的搜索范围，增加了找到最优解的概率。

将区域分割和贪婪算法相结合，用搜索到的最好解替换了种群中目标函数值最差的个体，保证了种群的多样性。

数值实验表明：该算法比文献中的DE算法更稳健，全局搜索能力更强，能以更大的概率找到背包问题的最优解。

【期刊名称】《江西师范大学学报（自然科学版）》【年(卷),期】2012(000)004【总页数】6页(P364-369)【关键词】背包问题;差分进化算法;分割【作者】钟培华;吴志远;胡建根;朱丽【作者单位】江西农业大学理学院, 江西南昌 330045;江西农业大学理学院, 江西南昌 330045;江西农业大学理学院, 江西南昌 330045;江西农业大学理学院, 江西南昌 330045【正文语种】中文【中图分类】TP180 引言背包问题是运筹学中的NP难问题, 有极其广泛的应用背景. 如选址问题、资金预算问题、投资决策等经济管理中的问题都可以建立背包问题的数学模型. 背包问题可以描述为: 有一个最大承重为b的背包和n种物品, 物品j的重量为wj, 价值为cj,在背包承重允许条件下应如何选择一组物品装入背包, 才能使装入背包的物品价值最大.若用xj =1表示物品j装入背包, xj=0表示物品j不装入背包, 则背包问题可用下列0-1整数规划表示:其中xj称为决策变量, 当x=(x1, x2,…,xn )∈{0,1}n且满足(1)式时, 称为背包问题的可行解, 否则, 称x为不可行解.背包问题的算法有精确算法和近似算法. 精确算法的优点是能求到问题的最优解,缺点是求解时间和内存消耗会随着问题规模的增加而急剧增加.近似算法的优点是时间和内存消耗相对稳定, 能在合理的时间内求到大规模问题的有效解, 因而在背包问题中得到广泛应用. 其中近似算法主要有差分进化算法[1-3]、粒子群算法[4]、遗传算法[5]、蜂群算法[6]等. 这些算法经过多次运算能找到问题的最优解, 但是找到最优解概率的大小因问题而异, 也和问题的规模有关. 可见算法的稳健性有待于进一步提高. 由于差分进化算法具有原理简单、控制参数少、易于实现、全局搜索能力强等优点, 它在连续空间的函数优化中得到广泛的应用[7-10]. 本文结合背包问题适合二进制编码的特点, 在差分进化算法的框架下, 对其变异算子进行了改进, 保证了变异、选择、交叉等算子的封闭性. 根据背包问题的特性引入区域分割算法,提出了基于区域分割的差分进化算法. 对经典背包问题的测试表明, 该算法找到最优解的概率更大, 运行更稳健, 所需的种群规模和迭代次数更少.1 差分进化算法及其改进差分进化算法(DE)是基于群体差异的演化算法,是在1995年由Rainer Storn和Kennth Prince提出的直接搜索算法. 它主要由变异、交叉、选择3个算子组成. 下面就以最大化问题为例, 简单介绍DE/best/1/bin模式的差分进化算法.设优化问题为其中和uj为变量xj的下界和上界. 在DE算法中, 种群的个体对应S中的一个点. 若差分进化算法第t代的第i个个体表示为2,…,N), N称为种群规模, 则DE算法的步骤如下.Step 1 初始化: 置t=0, 按(1)式产生初始种群的第i个个体其中r是[0,1]上ij服从均匀分布的随机数.Step 2变异操作: 求出当前最优解Z=(z1, z2,…,zn ), 对种群中的每一个目标个体, 按(2)式产生中间个体其中F∈[0,2], 互不相等的随机数r1, r2∈{1,2,…, N}.Step 3 交叉操作: 为增加种群多样性, 将目标个体和中间个体按(3)式杂交产生实验个体其中P是交叉概率, r是cij [0,1]上服从均匀分布的随机数, 均匀分布随机整数Rand( i)∈{1,2,…,n},Step 4 选择操作: 按(4)式选择相应的个体进入下一代,Step 5 算法收敛性判断: 若算法达到最大迭代次数, 输出当前最优解作为最优解; 否则, 转Step 2.由于背包问题的决策变量xj只取0和1, 因此,种群的个体更适合二进制编码. 但是, 注意到按(2)式产生的中间个体将不再是二进制编码. 因此, 须对变异操作进行改进. 为解决变异操作问题, 文献[2]产生中间个体方法是“少数服从多数”(见表1). 即当zj, xr1j和xr2j中有2个取值为1(或0), 则中间个体分量取1(或0), 否则取0(或1). 其数值实验表明, 该方法是有效的.本文保留“少数服从多数的思想”, 提出一种分2步的、以概率变异的变异操作. 如表1所示, 在第1步变异中取F=1计算中间个体, 其分量按(2)式计算. 显然, ∈{−1,0,1,2}. 由于第1步变异已经破坏二进制编码结构, 为了保证变异算子的封闭性, 须进行第2步变异, 以便将映射到{0,1}上去, 从而产生二进制的临时中间个体=第2步变异的操作是: 若第1步变异后则以概率0.333 3取1, 以概率为0.666 7取0. 类似地, 若第1步变异后则以概率0.666 7取1, 以概率为0.333 3取0. 若则以概率1取1. 若第1步变异后−1, 则以概率1取0.从表1可知, 本文分2步、依概率变异的操作本质上还是按“少数服从多数”的变异操作, 而且更能保持种群多样性.表1 临时中间个体分量的取值概率() zxx取值的情形jr jr j ,,“少数服从多数”原则第2步变异: 已知t112ij v+取值1 ˆti j第1步变异: 按(2)式计算t1v+ ij v+取值条件下临时中间个体分量t1q+的取值概率ij (1,0,0) 0 1P qP vv tt ijijij ()t+1===== 1() ˆ++ 11 110.333 3 (0,1,0) 0 1 (1,1,1) 1 1P qP vv ()ttijijijt+1===== 0() ˆ++ 11 010.666 7 (1,0,1) 1 0 (0,0,0) 0 0 (0,1,1) 1 0 P qP vv ()ttijijij t+1===== 1() ˆ++ 11 100.666 7 P qP vv ()ttijijij t+1===== 0() ˆ++ 11 000.333 3 (1,1,0) 1 2 () ===== (0,0,1) 0 −1 () P qP vv tt ijijij t+11() ˆ++ 11 121 P qP vv tt ijijij t+1====−= 0(ˆ++ 11 011)交叉操作相应地改为用临时中间个体按(5)式交叉产生实验个体, 其中Pc是交叉概率. 然后, 按(6)式选择个体进入下一代种群,2 区域分割算法为了增加找到最优解的概率, 本文引进区域分割算法, 将一些没有希望的点移除, 缩小最优解的搜索范围, 并用搜索到的最好可行解替换种群中适应值最差的点.设l=(l1, l2,…,l n ), u=(u1, u2,…,un)∈Zn, 其中lj, uj∈Z, 且lj≤uj (j=1,2,…,n). 称为Zn上的超长方体整数箱子. l和u分别称为箱子的下界和上界. 若∃lj＞uj , 则称为空箱子. 如果且满足l≤α≤β≤u, 则称是中的子箱子,其中l≤α≤β≤u是指lj≤αj ≤ βj≤uj(j=1, 2,…,n)成立. 特别地,和也是中的子箱子. 从中移除和中的整数点可以借助(6)式和(7)式实现, 且剩下的整数点仍然可以表示成互不相交的超长方体箱子(不超过2n个). 证明见文献[11]. 称(6)式和(7)式为区域分割算法,设l=(0,0,…,0),u=(1,1,…,1),x, y∈{0,1}n=且x是背包问题的可行解, y是背包问题的不可行解. 由于背包问题的目标函数f( x)和约束函数g( x)都是单调增加的, 不难理解,都是背包问题的可行解.都是背包问题的不可行解. 因此, 可以借助区域分割算法将子箱子和从中移除, 且不会遗失比x更好的可行解. 然后在更小的范围内搜索最优解, 就可以增加找到最优解的概率.3 基于区域分割的差分进化算法由差分进化算法的变异和交叉算子产生的实验个体可能是可行解, 也可能是不可行解. 为尽快找到最优解, 须将其中的可行解改进为充分利用背包承重的、更好的可行解, 同时将不可行解修复成可行解.3.1 对可行解的改进算法设x=(x1, x2,…,xn)是背包问题的可行解, 为了充分利用背包的承重, 尽快找到最优解. 对x进行改进的方法是: 对未装入背包的物品按价值密度(pj与wj的比值)从大到小排序. 首先, 考虑其中价值密度最大的物品, 如果该物品未装入背包; 且装入背包不会超重, 则将该物品装入背包. 否则, 该物品不装入背包. 然后, 类似考虑其中价值密度第2大的物品, 直到未装入背包的物品都不能装入背包为止. 设将x改进后得到的可行解为则x*是充分利用背包承重的可行解. 若 x*中存在分量xj满足则一定是不可行解.3.2 修复不可行解的算法设y=(y1,y2,…,yn)是不可行解, 对其进行修复的过程分2步执行, 第1步对已装入背包的物品按价值密度从小到大排序, 将背包中价值密度最小的物品取出, 如果背包中的物品仍然超重, 再将背包中价值密度最小的物品取出, 直到背包中的物品不超重为止. 这样将得到1个可行解. 第2步对第1步得到的可行解用改进可行解的算法对其进行改进.3.3 基于区域分割的差分进化算法为便于叙述, 以下假设lj =0, uj=1(j=1, 2,…,n), 即l, u={0,1}n.Step 1 初始化: 随机产生含N个二进制个体的种群, 将其中的可行个体改进, 将不可行个体修复.求出当前最优解设置最大的允许迭代次数, 设置交叉概率, 令进化代数t=0.Step 2 第1步变异: 令F=1, 按(2)式计算中间个体Step 3第2步变异: 根据以概率计算临时中间个体Step 4 按(5)式交叉产生实验个体(i=1, 2,…,N), 对其中的不可行解进行修复, 对可行解进行改进.step 5 按(4)式选择种群的个体和实验个体进入下一代新种群. 如果新种群存在个体比当前最优解更好, 则更新当前最优解, 令迭代次数t=t+1.Step 6 判断当前最优解是否已经连续迭代若干代都未得到更新, 若是, 转Step 7; 否则, 转Step 2.Step 7 判断是否达到最大迭代次数, 若是, 转Step 10; 否则, 转Step 8.Step 8 由于Xg是充分利用背包承重的可行解,随机选一个取值为0的变量(=0), 将其取值改为1, 则得到不可行解借助(8)式和(7)式从中先移除子箱子再移除丢弃其中下界不可行的箱子和空箱子后,设剩余的K个超长方体箱子表示为2,…,K).Step 9 若K=0, 转 Step 10; 否则, 第i个箱子的下界Si=(si1,si2,…,sin )是可行解. 将其改进成充分利用背包问题的可行解. 第i个箱子的上界Ti=(ti1,ti2,…,t in )可能是可行解, 也可能是不可行解.将其中的可行解改进为充分利用背包承重的可行解,并将不可行解修复. 这样即可得到2K个可行解, 用其中最好的可行解替换种群中适应值最差的个体,当该可行解比当前最优解好时, 更新当前最优解,转Step 2.Step 10 算法结束, 输出当前最优解.4 数值实验为了测试本文算法的性能, 对来源于文献的7个经典算例和1个随机产生的大规模算例进行了2组数值测试. 其中随机产生的150维背包问题KP8数据为: 问题规模n=150, 背包最大承重b=2 116, 物品价值系数C={325, 44, 47, 507, 260, 43, 208, 72, 176, 312, 219, 159, 19, 457, 18, 220, 130, 39, 202, 151, 221, 458, 95, 148, 400, 445, 292, 302, 47, 410, 325, 272, 125, 193, 10, 41, 27, 170, 331, 297, 197, 328, 360, 226, 100, 435, 408, 403, 236, 232, 146, 457, 249, 429, 369, 192, 124, 259, 21, 413, 104, 164, 125, 360, 410, 179, 255, 346, 169, 169, 420, 210, 243, 456, 156, 77, 339, 476, 494, 217, 191, 173, 197, 80, 462, 420, 393, 426, 221, 489, 301, 239, 326, 61, 232, 385, 72, 506, 485, 260, 423, 253, 427, 405, 286, 263, 367, 414, 392, 475, 252, 260, 216, 172, 406, 148, 126, 351, 184, 344, 317, 236, 175, 433, 221, 320, 79, 196, 395, 458, 443, 431, 124, 162, 376, 296, 319, 203, 147, 109, 384, 30, 185, 178, 419, 263, 105, 72, 220, 356}; 物品重量系数W={56, 51, 47, 37, 58, 28, 42, 25, 43, 44, 11, 14, 56, 14,24, 45, 55, 40, 40, 38, 21, 23, 13, 58, 23, 40, 48, 11, 54, 53, 56, 10, 59, 33, 57, 24, 32, 40, 30, 32, 41, 25, 25, 17, 22, 53, 45, 12, 14, 50, 45, 12, 17, 57, 27, 22, 29, 43, 47, 21, 51, 58, 31, 58, 22, 30, 55, 30, 10, 26, 46, 16, 39, 44, 21, 51, 58, 52, 56, 17, 20, 53, 33, 56, 21, 53, 12, 48, 14, 35, 17, 53, 36, 11, 13, 41, 41, 20, 43, 11, 18, 32, 59, 52, 11, 18, 47, 49, 59, 57, 18, 49, 34, 24, 47, 36, 25, 49, 18, 45, 36, 45, 24, 43, 14, 33, 43, 43, 17, 30, 20, 40, 48, 40, 42, 14, 30, 13, 43, 33, 37, 38, 33, 19, 55, 54, 32, 19, 45, 51}, 最优解xbest={0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0}, 最优值为25 903, 最优解的背包承重2 115. 另外, 需要指出的是: KP3的重量数据的第29个取值为50, KP6的重量数据第29个取值为25, 而它们其它数据的取值相同.第1组实验: 比较本文基于区域分割的差分进化算法(PDE)和文献[2]的二进制差分进化算法(BDE1)以及文献[3]的离散差分进化算法(GDDEA)的全局搜索能力和稳健性. 3种算法对8个实例独立运行100次, 比较它们找到最优解的次数. 8个算例的来源和3种算法的计算结果如表2所示.将所有算法用MATLAB7.01编程, 在CPU双核2.9 GHz, 内存2.00 GHz的微机(XP环境)上运行. 文献[2]的BDE1算法采用“少数服从多数”的变异规则,且参数设置同原文献(种群规模为50, 最大的允许迭代次数为200代, 交叉概率0.1). 与文献[3]相同, GDDEA算法连续进化10代重新初始化种群(种群规模为50, 最大的允许迭代次数为200代, 交叉概率0.1). 本文PDE算法种群规模为50, 最大的允许迭代次数为200代, 交叉概率0.1, 若连续10次迭代当前最优解未得到更新, 则启用区域分割算法, 区域分割算法最多使用20次.从表2可知, 对8个算例的100次独立计算中, PDE算法找到每个实例最优解的次数都多于GDDEA算法和和BDE1算法. PDE算法找到最优解次数最少的都达到98次(KP7). 而其它2种算法就没那么稳健, 其中BDE1算法找到KP5和KP8最优解的次数分别只有29次和2次, GDDEA算法找到KP7和KP8最优解的次数分别只有1次和8次, . 因此, 在种群规模相同条件下, 本文算法更稳健, 找到最优解的概率更大, 全局寻优能力更强.第2组实验: 比较本文算法和文献[1]基于混合编码的差分进化算法(MCDE)以及文献[5]基于模式替代的遗传算法(GASR)找到最好解时所需的最少迭代次数. 3种算法对KP5、KP6、KP7独立求解10次的计算结果见表3. 本文PDE算法种群规模为40,最大的允许迭代次数为150代, 其它参数设置同第一组实验. MCDE算法种群规模50, 变异概率0.5,交叉概率0.5, 最大允许的迭代次数150代. GASR算法种群规模200, 变异概率0.06, 交叉概率0.618,最大允许的迭代次数1 000代.在10次计算中, 本文算法找到KP5和KP6的最优解10次, 找到KP7的最优解9次. GASR算法和MCDE算法10次计算均未找到KP6的最优解. 本文算法找到3个实例最优解的进化代数远小于GASR算法和MCDE算法的进化代数, 其中本文算法找到KP7的最优解最少需进化36代, 平均需进化代数为78代, 其平均进化代数都小于GASR算法和MCDE算法的最少迭代次数(分别为147代和137代). 3个实例表明, 本文算法能以更少的种群、更少的迭代次数、更大的概率找到背包问题的最优解. 它比GASR算法和MCDE算法更稳健, 全局寻优能力更强, 所需种群规模和迭代次数更少.5 结论为了更有效地求解0-1背包问题, 提出了基于区域分割的差异进化算法. 该算法将传统差分进化算法的变异操作改为分2步以概率变异的操作, 保证了变异操作的封闭性. 将区域分割算法和背包问题的单调性相结合, 割去了一些没有希望的点, 缩小了最优解的搜索空间, 因此增加了找到最优解的概率. 同时用区域分割算法找到的最好可行解替换了种群中目标函数值最差的解, 增加了种群多样性,促进了种群的进化, 增强了算法的全局搜索能力.此外, 对可行解的改进和对不可行解的修复也在一定程度上加速了算法的收敛速度. 数值实验表明,本文算法在求解背包问题时, 比文献中的DE算法更稳健, 求到最优解的概率更大, 全局寻优能力更强, 所需的种群规模和迭代次数更少. 因此, 该算法更有效, 为求解其它类似问题的提供了一个有效途径.表2 3种差分进化算法求解0-1背包问题100次的结果注: 带*的数据引自文献[2]本文算例来源规模n 最优值背包承重 GDDEA BDE1 PDE最优解找到最优解次数 KP1 文献[2]问题1 10 295 269 100 100* 100 KP2 文献[2]问题2 20 1 024 871 100 100* 100 KP3 文献[2]问题3 50 3 103 1 000 100 100* 100 KP4 文献[2]问题4 50 16 102 11 231 100 100* 100 KP5 文献[1]的KP1 20 1 042 878 100 29 100 KP6 文献[1]的KP2 50 3 119 1 000 87 100 100 KP7 文献[1]的KP3 100 26 559 6 717 1 95 98 KP8 随机产生 150 25 903 2 115 8 2 100表3 3种算法找到的最好优解和所需的最少迭代次数对比注: MCDE与GASR的计算结果直接引自文献[1].实例最好结果(最少迭代次数) 最好结果(最少迭代次数) 最好结果(最少迭代次数) GASR MCDE PDE KP5 1 042/878 (12) 1 042/878 (5) 1 042/878 (1) KP6 3 103/1 000 (50) 3 105/997 (46) 3 119/1 000 (7) KP7 26 559/6 717 (147) 26 559/6 717 (137) 26 559/6 717 (36)6 参考文献【相关文献】[1] 邓长寿, 赵秉岩, 梁昌勇. 基于混合编码的差异演化算法解0-1背包问题[J]. 计算机应用研究, 2010, 27(6): 2031-2033.[2] 蔡鸿英, 郝志峰, 王志刚, 等. 解0-1背包问题的二进制差异演化算法[J]. 计算机工程与设计, 2009, 30(7): 1716-1721.[3] 苗世清, 高岳林. 求解0/1背包问题的离散差分进化算法[J].小微型计算机系统, 2009, 30(9): 1828-1830.[4] 赵新超, 杨婷婷. 求背包问题的更贪心粒子群算法[J]. 计算机工程与应用, 2009, 45(36): 32-34.[5] 李康顺, 贾玉珍, 张文生. 一种基于模式替代的遗传算法解0/1背包问题[J]. 计算机应用研究, 2009, 26(2): 470-471.[6] 樊小毛, 马良. 0-1背包问题的蜂群优化算法[J]. 数学的实践与认识, 2010, 40(6): 155-160.[7] Stom R, Price K. Differential evolution: a simple and efficient adaptive scheme for global optimization over continuous space [R]. Berkeley: University of California, 2006. [8] Ali M M, Kajee-Bagdadi Z. A local exploration-based differential evolution algorithm for constrained global optimization [J]. Applied Mathematics and Computation, 2009, 208(1): 31-48.[9] Mallipeddi R, Suganthan P N, Ensemble of constraint handling techniques [J]. IEEE Trans on Evolutionary Computation, 2010, 10(4): 311-338.[10] 刘若辰, 焦李成, 雷峰, 等. 一种新的差分进化约束优化算法[J]. 西安电子科技大学学报: 自然科学版, 2011, 38(1): 47-53.[11] Ruan Ning, Sun Xiaoling. An exact Algorithm for cost minimization in series reliability systems with multiple component choices[J]. Applied Mathematics and Computation, 2006,181(1): 732-741.。

算法分析与设计大作业…实验题目：0-1背包问题求解方法综述组员：班级：指导老师：]%0-1背包问题求解方法综述【摘要】：0-1背包问题是一个经典的NP-hard组合优化问题，现实生活中的很多问题都可以以它为模型。

本文首先对背包问题做了阐述，然后用蛮力解法、动态规划算法、贪心算法和回溯解法对背包问题进行求解，分析了0-1背包问题的数学模型,刻划了最优解的结构特征,建立了求最优值的递归关系式。

最后对四种算法从不同角度进行了对比和总结。

【关键词】：0-1背包问题；蛮力解法；动态规划算法；贪心算法；回溯解法。

0.引言0-1背包问题是指给定n个物品,每个物品均有自己的价值vi和重量wi(i=1,2,…,n),再给定一个背包,其容量为W。

要求从n个物品中选出一部分物品装入背包,这部分物品的重量之和不超过背包的容量,且价值之和最大。

单个物品要么装入,要么不装入。

很多问题都可以抽象成该问题模型,如配载问题、物资调运[1]问题等,因此研究该问题具有较高的实际应用价值。

目前,解决0-1背包问题的方法有很多,主要有动态规划法、回溯法、分支限界法、遗传算法、粒子群算法、人工鱼群算法、蚁群算法、模拟退火算法、蜂群算法、禁忌搜索算法等。

其中动态规划、回溯法、分支限界法时间复杂性比较高,计算智能算法可能出现局部收敛,不一定能找出问题的最优解。

文中在动态规划法的基础上进行了改进,提出一种求解0-1背包问题的算法,该算法每一次执行总能得到问题的最优解,是确定性算法,算法的时间复杂性最坏可能为O(2n)。

背包问题描述0-1背包问题(KP01)是一个著名的组合优化问题。

它应用在许多实际领域,如项目选择、资源分布、投资决策等。

背包问题得名于如何选择最合适的物品放置于给定背包中。

本文主要研究背包问题中最基础的0/1背包问题的一些解决方法。

为解决背包问题，大量学者在过去的几十年中提出了很多解决方法。

解决背包问题的算法有最优算法和启发式算法[2]，最优算法包括穷举法、动态规划法、分支定界法、图论法等，启发式算法包括贪心算法、遗传算法、蚁群算法、粒子算法等一些智能算法。