遗传算法求解01背包问题
一、问题描述
01背包问题属于组合优化问题的一个例子，求解01背包问题的过程可以被视作在很多可行解当中求解一个最优解。01背包问题的一般描述如下：
给定n个物品和一个背包，物品i的重量为W i，其价值为V i，背包的容量为C。选择合适的物品装入背包，使得背包中装入的物品的总价值最大。注意的一点是，背包内的物品的重量之和不能大于背包的容量C。在选择装入背包的物品时，对每种物品i只有两种选择：装入背包或者不装入背包，即只能将物品i装入背包一次。称此类问题为0/1背包问题。
01背包问题是NP问题，传统的解决方法有动态规划法、分支界限法、回溯法等等。传统的方法不能有效地解决01背包问题。遗传算法（Genetic Algorithms）则是一种适合于在大量的可行解中搜索最优（或次优）解的有效算法。
二、遗传算法
1、遗传算法的基本思想
遗传算法的搜索从一个被称作种群的候选解集开始，新的种群由旧的种群中产生以期得到更好的种群。从旧种群中按照解的适应度来选择解以产生新的解；适应度越大，解被选择生成后代的机率也越大。这个从已有种群中选择双亲并产生后代的迭代过程持续到遗传算法的停止条件满足为止。
2、遗传算法的基本元素。
遗传算法由以下几个原素组成：由染色体组成的种群，根据适应度进行选择以及交叉产生后代。
三、用遗传算法求解01背包问题
1、01背包问题中染色体的表示。
用向量X来表示染色体，
X = ｛x1，x2，……，x n｝。，x i∈｛0,1｝，
x i=1表示物品i装入了背包，x i =0表示物品i未装入背包。
每个染色体对应其当前装入背包的物品的总价值和总重量。背包中物品的中价值代表了该物品的适应度。
程序中定义了这样的一个结构来表示染色体：
typedef struct{
int Weight; //染色体代表的物品的总重量
int Fitness; //染色体代表的物品的价值（适应度）
int Gene[NUMG]; //用元素取值于定义域｛0,1｝的数组表示染色体。
}GENE;
2、遗传算法求解01背包问题时用到的参数。
POPSIZE：种群大小，即已知的可行解的个数。
NUMG：染色体中基因的个数，即物品的总数。
CAPACITY：背包的容量。
MAXB：二进制表示的染色体换算之后的最大十进制整数。用于随机产生一个整数，进而转换作染色体。
SIM：染色体之间的相似度阈值。当染色体之间的相似度达到阈值时，算法即停止运行。
PC=1.0 ：交叉概率为100％。
PM=0.2 ：变异概率为20％，变异可以保证种群的多样性，从而防止算法收敛于某个局部解。
3、选择操作。
选择操作采用了赌轮选择（Roulette-wheel selection）的方法。函数selectIndex()中包含了选择染色体的具体过程。其流程图如图1所示。
图1 赌轮选择流程图
程序中用一个Begin来代表当前赌轮上的指针的位置，End则用来使赌轮循环转动。
用summaryBE表示当前赌轮上的指针转过的染色体的总价值。
用summaryF表示当前全部染色体的价值总和。
用randProb作为染色体选择的阈值。randProb为介于[0,1]之间的随机数。
选择使summaryBE/summaryF 大于阈值randProb的染色体作为要选择的染色体。
4、交叉操作
程序中采用了单点交叉的策略。如下程序代码所示：
for(int j=0; j nextGenome[i].Gene[j] = parentGenome[Father].Gene[j]; nextGenome[i+POPSIZE/2].Gene[j] = parentGenome[Mother].Gene[j]; } for(;j nextGenome[i].Gene[j] = parentGenome[Father].Gene[j]; nextGenome[i+POPSIZE/2].Gene[j] = parentGenome[Mother].Gene[j]; } partPos为随机产生的整数，代表交叉的位置。第一个for循环将partPos位置之前的基因遗传给一个后代，而第二个循环则将partPos位置之后的基因进行了交换。 calculateCapacity函数用于计算交叉操作后的染色体的容量。 calculateFitness函数用于计算交叉操作后的染色体的适应度。 checkCapacity函数则用于检查交叉后的染色体的合理性，容量超出背包的染色体是不合理的。这里没有使后代死亡，而是随机地调整了染色体中的基因。使得基因能够适应环境（背包的容量）而继续生存。 5、精英策略 精英策略为了不使最优解在交叉的过程中，不会丢失最优解而采取的策略。其思想是保存上一代中 的适应性强的染色体。相应地取代下一代中适应性弱的染色体。 程序中精英策略由keepBestParents函数和sortFiness函数来实现。需要说明的是sortFitness仅仅对种群的索引进行了排序。然后用父代中20%的适应度较大的优秀染色体替换子代中20%的适应性弱的染色体。 6、变异操作 染色体的变异可以保持种群的多样性，防止最优解的丢失以及算法收敛到局部最优解。 变异操作由mutation函数实现。 首先产生一个介于0和1之间的随机数prob，若prob小于MP则进行变异操作：随机产生一个位置partPos，然后变异前染色体的partPos位置的基因为1，则变异为0，否则变异为1；相应地要进行适应度和染色体容量的变化。 7、代际更新 代际之间的更新，即用新生成的种群代替取代旧的种群。这个操作在updateGeneration函数中实现，同时这个操作使用了前面提及的精英策略。实际上，父代种群中优秀的染色体已被保留，updateGeneration中只是用新种群中的优秀染色体来代替父代中的染色体。 由于对父代和子代的染色体都进行了排序，因此程序中将子代的80％视作优秀，将父代中的前20％视作优秀。 8、算法的终止 程序中采用了一个HASH表来对子代种群的适应度进行HASH操作。HASH表中的头结点纪录了头结点所指向的单链表的信息。如下代码中的注释： typedef struct Head{ int maxFitness; //单链表中的最大的Fitness int Count; //HASH到该结点的染色体的数目 int Diff; //单链表中有多少不同的Fitness HASHNODE *Next; }HEAD; 用这样的一个HASH表结构可以只需遍历HASH表中的头结点，即可知当前的种群的适应度最大的染色体是否集中。 具体地，如checkFitness函数中的下面几行代码： index = maxFitness(hashTable); double CPount = hashTable[index].Count/(double)POPSIZE; double pDiff = hashTable[index].Diff/(double)POPSIZE; if(CPount>=0.9 && pDiff<=0.1){ sameFlag = false; } 如果当前maxFitness最大的头结点满足if语句中的判断条件，则sameFlag置为真，即算法停止迭代的条件得到了满足。 TraverseHashTable函数则用于遍历HASH表。 算法终止的另一个条件是迭代的次数。程序中设定了算法的最大迭代次数为1000。 四、实验结果。 试验中用到的物品的重量和价值分别存储于以下两个数组之中。 int Weight[NUMG]={6,9,8,8,6, 1, 10,5,7, 1}; int Value[NUMG]={2,20,5,4,19,14,18,8,11,6}; 父代种群存储于parentGenome[NUMG]中，子代种群存储于nextGenome[NUMG]中。程序的初始状态和结束状态如下面的表格所示： 停止时的种群 即可知当前 X =｛0,1,0,0,1,1,0,1,1,1｝ 对应的最优值是78，即当前能够装入背包的最大价值。 《算法分析与设计》实验报告 2015-2016年第2学期 实验班级： 学生姓名： 学号： 指导老师： 信息工程学院 实验项目名称：回溯算法解决0-1背包问题 实验日期：2016年5 月18 日 一、实验类型：□√验证性□设计性 二、实验目的 掌握0—1背包问题的回溯算法 三、实验内容及要求 给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 四、实验步骤 #include int cw;//当前重量 int cp;//当前价值 int bestp;//当前最优值 int *bestx;//当前最优解 int *x;//当前解 }; int Knap::Bound(int i) { //计算上界 int cleft=c-cw;//剩余容量 int b=cp; //以物品单位重量价值递减序装入物品while(i<=n&&w[i]<=cleft) { cleft-=w[i]; b+=p[i]; i++; } //装满背包 if(i<=n) b+=p[i]/w[i]*cleft; return b; } void Knap::Backtrack(int i) { if(i>n) { if(bestp 基于遗传算法的一种新的约束处理方法 苏勇彦1，王攀1，范衠2 （1武汉理工大学 自动化学院， 湖北 武汉 430070） （2丹麦理工大学 机械系 哥本哈根） 摘 要：本文针对目前的约束处理方法中存在的问题，提出一种新的约束处理方法。该方法通过可行解和不可行解混合交叉的方法对问题的解空间进行搜索，对可行种群和不可行种群分别进行选择操作。避免了惩罚策略中选取惩罚因子的困难，使得约束处理问题简单化。实例测试结果表明，该约束处理方法的有效性。 关键词：遗传算法、约束处理、可行解、不可行解、两种群混合交叉 1引言 科学研究和工程应用中许多问题都可以转化为求解一个带约束条件的函数优化问题[1]。遗传算法（Genetic Algorithm ）与许多基于梯度的算法比较,具有不需要目标函数和约束条件可微,且能收敛到全局最优解的优点 [2]，因此，它成为一种约束优化问题求解的有力工具。目前，基于GA 的约束处理方法有拒绝策略，修复策略，改进遗传算子策略以及惩罚函数策略等。但是这些方法都存在一些问题[3]：修复策略对问题本身的依赖性，对于每个问题必须设计专门的修复程序。改进遗传算子策略则需要设计针对问题的表达方式以及专门的遗传算子来维持解的可行性。惩罚策略解的质量严重依赖于惩罚因子的选取，当惩罚因子不适当时，算法可能收敛于不可行解。 本文针对目前的约束处理方法中存在的问题，提出一种新的约束处理方法。该方法通过可行解和不可行解混合交叉的方法对问题的解空间进行搜索，对可行种群和不可行种群分别进行选择操作。避免了惩罚策略中选取惩罚因子的困难，使得约束处理问题简单化。实例测试结果表明，该约束处理方法的有效性。 2约束处理方法描述 2.1单目标有约束优化问题一般形式 )(max x f ..t s ;0)(≤x g i 1,,2,1m i L L =;0)(=x h i )(,,1211m m m m i +=+=L X x ∈ 这里都是定义在m m m m h h h g g g f ,,,;,,;2121111L L ++n E 上的实值函数。X 是n E 上的 子集，x 是维实向量，其分量为。上述问题要求在变量满足约 束的同时极大化函数。函数通常为目标函数。约束n n x x x ,,,21L n x x x ,,,21L f f ;0)(≤x g i 称为不等式约束；约束称为等式约束。集合;0)(=x h i X 通常为变量的上下界限定的区域。向量且满足所有约束，则称之为问题的可行解。所有可行解构成可行域。否则,为问题的不可行解,所有不可行解构成不可行域。问题的目标是找到一个可行解X x ∈x 使得)()(x f x f ≤对于所有可行解x 成立。那么，x 为最优解[4]。 2.2算法描述 目前，最常采用的约束处理方法为惩罚函数法。但优化搜索的效率对惩罚因子的选择有 实现遗传算法的0-1背包问题 求解及其改进 姓名： 学号： 班级： 提交日期：2012年6月27日 实现遗传算法的0-1背包问题求解 摘要：研究了遗传算法解决0-1背包问题中的几个问题： 1）对于过程中不满足重量限制条件的个体的处理,通过代换上代最优解保持种群的进化性 2）对于交换率和变异率的理解和处理方法,采用逐个体和逐位判断的处理方法 3）对于早熟性问题,引入相似度衡量值并通过重新生成个体替换最差个体方式保持种群多样性。4）一种最优解只向更好进化方法的尝试。 通过实际计算比较表明,本文改进遗传算法在背包问题求解中具有很好的收敛性、稳定性和计算效率。通过实例计算，表明本文改进遗传算法优于简单遗传算法和普通改进的遗传算法。 关键词：遗传算法；背包问题；优化 1.基本实现原理： 一、问题描述 0-1背包问题属于组合优化问题的一个例子，求解0-1背包问题的过程可以被视作在很多可行解当中求解一个最优解。01背包问题的一般描述如下： 给定n个物品和一个背包，物品i的重量为Wi，其价值为Vi，背包的容量为C。选择合适的物品装入背包，使得背包中装入的物品的总价值最大。注意的一点是，背包内的物品的重量之和不能大于背包的容量C。在选择装入背包的物品时，对每种物品i只有两种选择：装入背包或者不装入背包，即只能将物品i装入背包一次。称此类问题为0/1背包问题。 其数学模型为： 0-1背包问题传统的解决方法有动态规划法、分支界限法、回溯法等等。传统的方法不能有效地解决0-1背包问题。遗传算法（Genetic Algorithms）则是一种适合于在大量的可行解中搜索最优（或次优）解的有效算法。 二、遗传算法特点介绍: 遗传算法(Genetic Algorithm, GA)是1962年Holland教授首次提出了GA算法的思想是近年来随着信息数据量激增，发展起来的一种崭新的全局优化算法，它借用了生物遗传学的观点，通过自然选择、遗传、变异等作用机制，实现各个个体的适应性的提高。 基本遗传算法求解步骤： Step 1 参数设置：在论域空间U上定义一个适应度函数f(x)，给定种群规模N，交叉率P c 和变异率P m，代数T； Step 2 初始种群：随机产生U中的N个染色体s1, s2, …, s N，组成初始种群S={s1, s2, …, s N}，置代数计数器t=1； Step 3计算适应度：S中每个染色体的适应度f() ； Step 4 判断：若终止条件满足，则取S中适应度最大的染色体作为所求结果，算法结束。Step 5 选择-复制：按选择概率P(x i)所决定的选中机会，每次从S中随机选定1个染色体并将其复制，共做N次，然后将复制所得的N个染色体组成群体S1； Step 6 交叉：按交叉率P c所决定的参加交叉的染色体数c，从S1中随机确定c个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体S2； Step 7 变异：按变异率P m所决定的变异次数m，从S2中随机确定m个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体S3； Step 8 更新：将群体S3作为新一代种群，即用S3代替S，t=t+1，转步3； 动态规划是用空间换时间的一种方法的抽象。其关键是发现子问题和记录其结果。然后利用这些结果减轻运算量。 比如01背包问题。 因为背包最大容量M未知。所以，我们的程序要从1到M一个一个的试。比如，开始任选N件物品的一个。看对应M的背包，能不能放进去，如果能放进去，并且还有多的空间，则，多出来的空间里能放N-1物品中的最大价值。怎么能保证总选择是最大价值呢？看下表。 测试数据： 10,3 3,4 4,5 5,6 c[i][j]数组保存了1,2,3号物品依次选择后的最大价值. 这个最大价值是怎么得来的呢?从背包容量为0开始,1号物品先试,0,1,2,的容量都不能放.所以置0,背包容量为3则里面放4.这样,这一排背包容量为 4,5,6,....10的时候，最佳方案都是放4.假如1号物品放入背包.则再看2号物品.当背包容量为3的时候，最佳方案还是上一排的最价方案c为4.而背包容量为5的时候，则最佳方案为自己的重量5.背包容量为7的时候，很显然是5加上一个值了。加谁??很显然是7-4=3的时候.上一排c3的最佳方案是4.所以。 总的最佳方案是5+4为9.这样.一排一排推下去。最右下放的数据就是最大的价值了。(注意第3排的背包容量为7的时候,最佳方案不是本身的6.而是上一排的9.说明这时候3号物品没有被选.选的是1,2号物品.所以得9.) 从以上最大价值的构造过程中可以看出。 f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}这就是书本上写的动态规划方程.这回清楚了吗? 下面是实际程序: #include 0-1背包动态规划解决问题 一、问题描述： 有n个物品，它们有各自的重量和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？ 二、总体思路： 根据动态规划解题步骤（问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填表、寻找解组成）找出01背包问题的最优解以及解组成，然后编写代码实现。 原理： 动态规划与分治法类似，都是把大问题拆分成小问题，通过寻找大问题与小问题的递推关系，解决一个个小问题，最终达到解决原问题的效果。但不同的是，分治法在子问题和子子问题等上被重复计算了很多次，而动态规划则具有记忆性，通过填写表把所有已经解决的子问题答案纪录下来，在新问题里需要用到的子问题可以直接提取，避免了重复计算，从而节约了时间，所以在问题满足最优性原理之后，用动态规划解决问题的核心就在于填表，表填写完毕，最优解也就找到。 过程： a) 把背包问题抽象化（X1，X2，…，Xn，其中 Xi 取0或1，表示第i个物品选或不选），V i表示第i个物品的价值，W i表示第i个物品的体积（重量）； b) 建立模型，即求max(V1X1+V2X2+…+VnXn)； c) 约束条件，W1X1+W2X2+…+WnXn 遗传算法求解背包问题 信管专业李鹏 201101002044 一、遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。 二、背包问题描述 背包问题是一个典型的组合优化问题，在计算理论中属于NP完全问题，主要应用于管理中的资源分配，资金预算，投资决策、装载问题的建模。传统“0/1”背包问题可以描述为：把具有一定体积和价值的n件不同种类物品放到一个有限容量的背包里，使得背包中物品的价值总量最大。 三、数学模型 背包问题可以描述如下：假设有n个物体，其重量用表示，价值用表示，背包的最大容量为b。这里和b都大于0。问题是要求背包所装的物体的总价值最大。背包问题的数学模型描述如下： (1) (2) (3) 约束条件(3)中表示物体i被选入背包，反之，表示物体i没有被选入背包。约束条件(2)表示背包的容量约束。 四、使用遗传算法解决“0-1背包问题”的思路：0-1背包的解可以编码为一串0-1字符串（0：不取，1：取）；首先，随机产生M个0-1字符串，然后评价这些0-1字符串作为0-1背包问题的解的优劣；然后，随机选择一些字符串通过交叉、突变等操作产生下一代的M个字符串，而且较优的解被选中的概率要比较高。这样经过G代的进化后就可能会产生出0-1背包问题的一个“近似最优解”。 五、程序整体流程 （1）读取存取包的限种、商品的重要和价值的TXT文件； （2）初始化种群； （3）计算群体上每个个体的适应度值(Fitness) ； （4）评估适应度,对当前群体P(t)中每个个体Pi计算其适应度F(Pi)，适应度表示了该个体的性能好坏； （5）依照Pc选择个体进行交叉操作； （6）仿照Pm对繁殖个体进行变异操作 （7）没有满足某种停止条件，则转第3步，否则进入8 ； （8）输出种群中适应度值最优的个体。 六、代码 function Main() %定义全局变量 global VariableNum POPSIZE MaxGens PXOVER PMutation VariableNum=3 %变量个数 POPSIZE=50 %种群大小 MaxGens=1000 %种群代数 PXOVER=0.8 %交叉概率 PMutation=0.2 %变异概率 %读取数据文件 算法实验报告 ---背包问题 实验目的 1．掌握动态规划算法的基本思想，包括最优子结构性质和基于表格的最优 值计算方法。 2．熟练掌握分阶段的和递推的最优子结构分析方法。 3．学会利用动态规划算法解决实际问题。 问题描述： 给定n种物品和一个背包。物品i的重量是wi，体积是bi，其价值为vi， 背包的容量为c，容积为d。问应如何选择装入背包中的物品，使得装入背包中 物品的总价值最大? 在选择装入背包的物品时，对每种物品只有两个选择：装入 或不装入，且不能重复装入。输入数据的第一行分别为：背包的容量c，背包的 容积d，物品的个数n。接下来的n行表示n个物品的重量、体积和价值。输出 为最大的总价值。 问题分析: 标准0-1背包问题，MaxV表示前i个物品装入容量为j的背包中时所能产生的最大价值，结构体objec表示每一个可装入物品，其中w表示物品的重量，v表示物品的价值。如果某物品超过了背包的容量，则该物品一定不能放入背包，问题就变成了剩余i-1个物品装入容量为j的背包中所能产生的最大价值；如果该物品能装入背包，问题就变成i-1个物品装入容量为j-objec[i].w的背包所能产生的最大价值加上物品i的价值objec[i].v. 复杂性分析 时间复杂度，最好情况下为0，最坏情况下为：（abc） 源程序 #include 算法分析与设计实验报告第五次附加实验 附录： 完整代码（回溯法） //0-1背包问题回溯法求解 #include Typew c; //背包容量 int n; //物品数 Typew *w; //物品重量数组| Typep *p; //物品价值数组 Typew cw; //当前重量 Typep cp; //当前价值 Typep bestp; //当前最后价值 }; template 实验三01背包问题不同算法设计、分析与对比一．问题描述 给定n种物品和一背包。物品i的重量是w i ，其价值为v i ，背包的容量为c。 问题：应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。 说明：在选择装入背包的物品时，对每种物品i只有两个选择，装入背包或不装入背包，也不能将物品装入背包多次。 二．实验内容与要求 实验内容： 1.分析该问题适合采用哪些算法求解（包括近似解）。 ^ 动态规划、贪心、回溯和分支限界算法。 2.分别给出不同算法求解该问题的思想与算法设计，并进行算法复杂性分析。 动态规划： 递推方程： m(i,j) = max{m(i-1,j),m(i-1,j-wi)+vi} j >= wi; m(i-1,j) j < wi; 时间复杂度为O(n). 贪心法： ^ 算法思想：贪心原则为单位价值最大且重量最小，不超过背包最大承重量为约束条件。也就是说，存在单位重量价值相等的两个包，则选取重量较小的那个背包。但是，贪心法当在只有在解决物品可以分割的背包问题时是正确的。贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。 用贪心法设计算法的特点是一步一步地进行，根据某个优化测度（可能是目标函数，也可能不是目标函数），每一步上都要保证能获得局部最优解。每一步只考虑一个数据，它的选取应满足局部优化条件。若下一个数据与部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中， 直到把所有数据枚举完，或者不能再添加为止。 回溯法： 回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(bounding function)来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。这种具有限界函数的深度优先生成法称为回溯法。 对于有n种可选物品的0/1背包问题，其解空间由长度为n的0-1向量组成,可用子集数表示。在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入左子树。当右子树中有可能包含最优解时就进入右子树搜索。 时间复杂度为：O(2n) 空间复杂度为：O(n) ： 分支限界算法： 首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。在优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。 算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。 3.设计并实现所设计的算法。 4.对比不同算法求解该问题的优劣。 这动态规划算法和贪心算法是用来分别解决不同类型的背包问题的，当一件背包物品可以分割的时候，使用贪心算法，按物品的单位体积的价值排序，从大到小取即可。当一件背包物品不可分割的时候，（因为不可分割，所以就算按物品的单位体积的价值大的先取也不一定是最优解）此时使用贪心是不对的，应使用动态规划。 5.需要提交不同算法的实现代码和总结报告。 动态规划方法： public class Knapsack { 背包问题---遗传算法解决 function Population1=GA_copy(Population,p,w0,w) %复制算子 %Population为种群 n=length(Population(:,1)); fvalue=zeros(1,n); for i=1:n fvalue(i)=GA_beibao_fitnessvalue(Population(i,:),p,w0,w); end fval=fvalue/sum(fvalue); F(1)=0; for j=1:n F(j+1)=0; for k=1:j F(j+1)=F(j+1)+fval(k); end end for i=1:n test=rand; for j=1:n if((test>=F(j))&&(test POP(j,z)=Population(i,z); end POP(j,l+1)=i; p(j)=randint(1,1,[1 l-1]); j=j+1; end end k0=j-1; k=floor(k0/2); if k>=1 for m=1:k for t=p(2*m-1)+1:l s=POP(2*m-1,t); POP(2*m-1,t)=POP(2*m,t); POP(2*m,t)=s; end end for m=1:k0 for i=1:l Population1(POP(m,l+1),i)=POP(m,i); end end end function fitnessvalue=GA_fitnessvalue(x,p,w0,w) %使用惩罚法计算适应度值 %x为染色体 %p为背包问题中每个被选物体的价值 %w0为背包问题中背包总容积 %w为背包问题中每个被选物品的容积 l=length(x); for i=1:l a(i)=p(i).*x(i); end f=sum(a); b=min(w0,abs(sum(w)-w0)); for i=1:l wx(i)=w(i).*x(i); end if abs(sum(wx)-w0)>b*0.99 p=0.99; 动态规划法、回溯法解0-1背包问题 2012级计科庞佳奇 一、问题描述与分析 1.动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会 有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。 不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。 多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化问题的方法为动态规划方法。任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。1.最优化原理（最优子结构性质）最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。2.无后效性将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。3.子问题的重叠性动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。 01背包是在M件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W2……Wn，与之相对应的价值为P1,P2……Pn。求出获得最大价值的方案。 2.回溯法（探索与回溯法）是一种选优搜索法，按选优条件向前搜索，以达到目 标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。 在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。 0-1背包问题 计科1班朱润华 2012040732 方法1：回溯法 一、回溯法描述： 用回溯法解问题时，应明确定义问题的解空间。问题的解空间至少包含问题的一个（最优）解。对于0-1背包问题，解空间由长度为n的0-1向量组成。该解空间包含对变量的所有0-1赋值。例如n=3时，解空间为：｛（0，0，0），（0，1，0），（0，0，1），（1，0，0），（0，1，1），（1，0，1），（1，1，0），（1，1，1）｝然后可将解空间组织成树或图的形式，0-1背包则可用完全二叉树表示其解空间给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 形式化描述：给定c >0, wi >0, vi >0 , 1≤i≤n.要求找一n元向量(x1,x2,…,xn,), xi∈{0,1}, ? ∑ wi xi≤c,且∑ vi xi达最大.即一个特殊的整数规划问题。 二、回溯法步骤思想描述： 0-1背包问题是子集选取问题。0-1 背包问题的解空间可以用子集树表示。在搜索解空间树时，只要其左儿子节点是一个可行节点，搜索就进入左子树。当右子树中有可能含有最优解时，才进入右子树搜索。否则，将右子树剪去。设r是当前剩余物品价值总和，cp是当前价值；bestp是当前最优价值。当cp+r<=bestp时，可剪去右子树。计算右子树上界的更好的方法是将剩余物品依次按其单位价值排序，然后依次装入物品，直至装不下时，再装入物品一部分而装满背包。 例如：对于0-1背包问题的一个实例，n=4,c=7,p=[9,10,7,4],w=[3,5,2,1]。这4个物品的单位重量价值分别为[3,2,3,5,4]。以物品单位重量价值的递减序装入物品。先装入物品4，然后装入物品3和1.装入这3个物品后，剩余的背包容量为1，只能装0.2的物品2。由此得一个解为[1,0.2,1,1]，其相应价值为22。尽管这不是一个可行解，但可以证明其价值是最优值的上界。因此，对于这个实例，最优值不超过22。 在实现时，由Bound计算当前节点处的上界。类Knap的数据成员记录解空间树中的节点信息，以减少参数传递调用所需要的栈空间。在解空间树的当前扩展节点处，仅要进入右子树时才计算上界Bound,以判断是否可将右子树剪去。进入左子树时不需要计算上界，因为上界预期父节点的上界相同。 三、回溯法实现代码： #include "stdafx.h" #include #include 遗传算法求解0-1背包问题 一、问题描述 给定n种物品和容量为C的背包。物品i的重量是wi，其价值为vi。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 二、知识表示 1、状态表示 （1）个体或染色体：问题的一个解，表示为n个比特的字符串，比特值为0表示不选该物品，比特值为1表示选择该物品。 （2）基因：染色体的每一个比特。 （3）种群：解的集合。 （4）适应度：衡量个体优劣的函数值。 2、控制参数 （1）种群规模：解的个数。 （2）最大遗传的代数 （3）交叉率：参加交叉运算的染色体个数占全体染色体的比例，取值范围一般为0.4～0.99。（4）变异率：发生变异的基因位数所占全体染色体的基因总位数的比例，取值范围一般为0.0001～0.1。 3、算法描述 （1）在搜索空间U上定义一个适应度函数f(x)，给定种群规模N，交叉率Pc和变异率Pm，代数T； （2）随机产生U中的N个个体s1, s2, …, sN，组成初始种群S={s1, s2, …, sN}，置代数计数器t=1； （3）计算S中每个个体的适应度f() ； （4）若终止条件满足，则取S中适应度最大的个体作为所求结果，算法结束。 （5）按选择概率P(xi)所决定的选中机会，每次从S中随机选定1个个体并将其染色体复制，共做N次，然后将复制所得的N个染色体组成群体S1； （6）按交叉率Pc所决定的参加交叉的染色体数c，从S1中随机确定c个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体S2； （7）按变异率P m所决定的变异次数m，从S2中随机确定m个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体S3； （8）将群体S3作为新一代种群，即用S3代替S，t = t+1，转步3。 三、算法实现 1、主要的数据结构 染色体：用一维数组表示，数组中下标为i的元素表示第（i+1）个物品的选中状态，元素值为1，表示物品被选中，元素值为0表示物品不被选中。 种群：用二维数组表示，每一行表示一个染色体。 具有最大价值的染色体：由于每一个染色体经过选择、交叉、变异后都可能发生变化，所以对于产生的新的总群，需要记录每个物品的选中状态。同时保存该状态下物品的最大价值，如果新的总群能够产生更优的值，则替换具有最大价值的染色体。 实验5 分支界限法解0-1背包问题一、实验要求 1．要求用分支界限法求解0-1背包问题； 2．要求交互输入背包容量，物品重量数组，物品价值数组； 3．要求显示结果。 二、实验仪器和软件平台 仪器：带usb接口微机 软件平台：WIN-XP + VC++ 三、源程序 #include "" #include float ub; //结点的上界值 }; //类Knap中的数据记录解空间树中的结点信息，以减少参数传递及递归调用所需的栈空间class Knap { private: struct node *front, //队列队首 *bestp,*first; //解结点、根结点 int *p,*w,n,c,*M;//背包价值、重量、物品数、背包容量、记录大小顺序关系 long lbestp;//背包容量最优解 public: void Sort(); Knap(int *pp,int *ww,int cc,int nn); ~Knap(); float Bound(int i,int cw,int cp);//计算上界限 node *nnoder(node *pa,int ba,float uub);//生成一个结点 ba=1生成左节点 ba=0生成右节点 void addnode(node *nod);//向队列中添加活结点 void deletenode(node *nod);//将结点从队列中删除 struct node *nextnode(); //取下一个节点 void display(); //输出结果 void solvebag(); //背包问题求解 }; //按物品单位重量的价值排序 void Knap::Sort() { 1、实验目的 （1）掌握回溯法设计策略。 （2）通过0-1背包问学习回溯法法设计技巧2.实验内容 源程序： #include } if(cw+w[i]<=c) //搜索左子树 { cw+=w[i]; cp+=p[i]; Backtrack(i+1); cp-=p[i]; cw-=w[i]; } if(bound(i+1)>bestp)//搜索右子树 Backtrack(i+1); } double Knapsack (double pp[],double ww[],double d) { int i; double TP=0,TW=0; cw=0.0;cp=0.0;bestp=0.0;//计算所有物品的重量及价值 for(i=1;i<=n;i++) { TP=TP+pp[i]; TW=TW+ww[i]; } if(TW<=d)//所有物品装入背包 bestp=TP; else { Backtrack(1); } return bestp; }; int main() { 初始遗传算法及一个简单的例子 遗传算法(Genetic Algorithms, GA)是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。它模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。 下面我以一个实例来详细表述遗传算法的过程 例：求下述二元函数的最大值： 2 =] y x x∈ ,0[ 31 1、编码： 用遗传算法求解问题时，不是对所求解问题的实际决策变量直接进行操作，而是对表示可行解的个体编码的操作，不断搜索出适应度较高的个体，并在群体中增加其数量，最终寻找到问题的最优解或近似最优解。因此，必须建立问题的可行解的实际表示和遗传算法的染色体位串结构之间的联系。在遗传算法中，把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法称之为编码。反之，个体从搜索空间的基因型变换到解空间的表现型的方法称之为解码方法。 编码是应用遗传算法是需要解决的首要问题，也是一个关键步骤。迄今为止人们已经设计出了许多种不同的编码方法。基本遗传算法使用的是二进制符号0和1所组成的二进制符号集｛0，1｝，也就是说，把问题空间的参数表示为基于字符集｛0，1｝构成的染色体位串。每个个体的染色体中所包含的数字的个数L 称为染色体的长度或称为符号串的长度。一般染色体的长度L为一固定的数，如本例的编码为 s1 = 1 0 0 1 0 (17) s2 = 1 1 1 1 0 (30) s3 = 1 0 1 0 1 (21) s4 = 0 0 1 0 0 (4) 表示四个个体，该个体的染色体长度L=5。 2、个体适应度函数 在遗传算法中，根据个体适应度的大小来确定该个体在选择操作中被选定的概率。个体的适应度越大，该个体被遗传到下一代的概率也越大；反之，个体的适应度越小，该个体被遗传到下一代的概率也越小。基本遗传算法使用比例选择操作方法来确定群体中各个个体是否有可能遗传到下一代群体中。为了正确计算不同情况下各个个体的选择概率，要求所有个体的适应度必须为正数或为零，不能是负数。这样，根据不同种类的问题，必须预先确定好由目标函数值到个体适应度之间的转换规则，特别是要预先确定好目标函数值为负数时的处理方法。回溯算法解决0-1背包问题(DOC)
基于遗传算法的一种新的约束处理方法
用遗传算法解决0-1背包问题概述
01背包问题动态规划详解
动态规划与回溯法解决0-1背包问题
遗传算法求解背包问题
算法设计背包问题
回溯法实验(0-1背包问题)
01背包问题不同算法设计、分析与对比报告
matlab、lingo程序代码3-背包问题(遗传算法)复习过程
算法分析与程序设计动态规划及回溯法解背包问题
回溯法和分支限界法解决0-1背包题
用回溯法解决0-1背包问题
遗传算法求解0-1背包问题(JAVA)
分支界限法解0-1背包问题实验报告
回溯算法之0-1背包问题
遗传算法求解y=x2 - 副本
相关主题
文本预览