matlab、lingo程序代码3-背包问题(遗传算法)复习过程

遗传算法解决01背包问题2015 ～2016 学年第二学期学生姓名专业学号2016年 6 月目录一：问题描述 (3)二：遗传算法原理及特点 (3)三：背包问题的遗传算法求解 (3)1.文字描述 (3)2.遗传算法中的抽象概念在背包问题的具体化 (3)3.算法求解的基本步骤 (4)四：算法实现 (4)1.数据结构 (4)2.部分代码 (5)五：结论 (8)六：参考文献 (8)一、问题描述0-1背包问题属于组合优化问题的一个例子，求解0-1背包问题的过程可以被视作在很多可行解当中求解一个最优解。

01背包问题的一般描述如下：给定n个物品和一个背包，物品i的重量为Wi，其价值为Vi，背包的容量为C。

问应如何选择合适的物品装入背包，使得背包中装入的物品的总价值最大。

注意的一点是，背包内的物品的重量之和不能大于背包的容量C。

在选择装入背包的物品时，对每种物品i只有两种选择：即装入背包或者不装入背包，不能讲物品i装入背包多次，也不能只装入部分的物品，称此类问题为0/1背包问题。

二、遗传算法原理及特点遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。

遗传算法有着鲜明的优点：(1)遗传算法的操作对象是一组可行解,而非单个可行解;搜索轨道有多条,而非单条,因而具有良好的并行性.(2)遗传算法只需利用目标的取值信息,而无需递度等高价值信息,因而适用于任何规模,高度非线形的不连续多峰函数的优化以及无解析表达式的目标函数的优化,具有很强的通用性.(3)遗传算法择优机制是一种“软”选择,加上良好的并行性,使它具有良好的全局优化性和稳健性.(4)遗传算法操作的可行解集是经过编码化的(通常采用二进制编码),目标函数解释为编码化个体(可行解)的适应值,因而具有良好的可操作性与简单性.三、背包问题的遗传算法求解1、文字描述0-1背包问题传统的解决方法有动态规划法、分支界限法、回溯法等等。

遗传算法的M A T L A B程序实例遗传算法的程序实例如求下列函数的最大值f(x)=10*sin(5x)+7*cos(4x) x∈[0,10]一、初始化(编码)initpop.m函数的功能是实现群体的初始化，popsize表示群体的大小，chromlength表示染色体的长度(二值数的长度)，长度大小取决于变量的二进制编码的长度(在本例中取10位)。

代码:%Name: initpop.m%初始化function pop=initpop(popsize,chromlength)pop=round(rand(popsize,chromlength));% rand随机产生每个单元为 {0,1} 行数为popsize，列数为chromlength的矩阵，% roud对矩阵的每个单元进行圆整。

这样产生的初始种群。

二、计算目标函数值1、将二进制数转化为十进制数(1)代码:%Name: decodebinary.m%产生 [2^n 2^(n-1) ... 1] 的行向量，然后求和，将二进制转化为十进制function pop2=decodebinary(pop)[px,py]=size(pop); %求pop行和例数for i=1:pypop1(:,i)=2.^(py-1).*pop(:,i);py=py-1;endpop2=sum(pop1,2); %求pop1的每行之和2、将二进制编码转化为十进制数(2)decodechrom.m函数的功能是将染色体(或二进制编码)转换为十进制，参数spoint表示待解码的二进制串的起始位置。

(对于多个变量而言，如有两个变量，采用20为表示，每个变量10为，则第一个变量从1开始，另一个变量从11开始。

本例为1)，参数1ength表示所截取的长度（本例为10）。

代码:%Name: decodechrom.m%将二进制编码转换成十进制function pop2=decodechrom(pop,spoint,length)pop1=pop(:,spoint:spoint+length-1);pop2=decodebinary(pop1);3、计算目标函数值calobjvalue.m函数的功能是实现目标函数的计算，其公式采用本文示例仿真，可根据不同优化问题予以修改。

Matlab遗传算法及实例Matlab遗传算法工具箱函数及实例讲解转：最近硏究了一下遗传算法，因为要用遗传算法来求解多元非线性模型。

还好用遗传算法的工具箱予以实现了，期间也遇到了许多问题。

借此与大家分享一下。

首先，我们要熟悉遗传算法的基本原理与运算流程。

基本原理：遗传算法是一种典型的启发式算法，属于非数值算法范畴。

它是模拟达尔文的自然选择学说和自然界的生物进化过程的一种计算模型。

它是采用简单的编码技术来表示各种复杂的结构，并通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。

遗传算法的操作对象是一群二进制串（称为染色体、个体），即种群，每一个染色体都对应问题的一个解。

从初始种群出发，采用基于适应度函数的选择策略在当前种群中选择个体，使用杂交和变异来产生下一代种群。

如此模仿生命的进化进行不断演化，直到满足期望的终止条件。

运算流程：Step 1 :对遗传算法的运行参数进行赋值。

参数包括种群规模、变量个数、交叉概率、变异概率以及遗传运算的终止进化代数。

Step 2 :建立区域描述器。

根据轨道交通与常规公交运营协调模型的求解变量的约束条件，设置变量的取值范围。

Step 3 :在Step 2的变量取值范围内，随机产生初始群体，代入适应度函数计算其适应度值。

Step 4 :执行比例选择算子进行选择操作。

Step 5 :按交叉概率对交叉算子执行交叉操作。

Step 6 :按变异概率执行离散变异操作。

Step 7 :计算Step 6得到局部最优解中每个个体的适应值，并执行最优个体保存策略。

Step 8 :判断是否满足遗传运算的终止进化代数，不满足则返回Step 4，满足则输出运算结果其次，运用遗传算法工具箱。

运用基于Matlab的遗传算法工具箱非常方便，遗传算法工具箱里包括了我们需要的各种函数库。

目前，基于Matlab的遗传算法工具箱也很多，比较流行的有英国设菲尔德大学幵发的遗传算法工具箱GATBXGAOT以及Math Works公司推出的GADS实际上，GAD鉞是大家所看到的Matlab中自带的工具箱。

【背包问题】基于matlab粒⼦群算法求解背包问题【含Matlab源码1343期】⼀、获取代码⽅式获取代码⽅式1：完整代码已上传我的资源：⼆、背包问题简介1【背包问题】背包问题(Knapsack problem)是⼀种组合优化的NP完全问题。

问题描述为：给定⼀组物品，每种物品都有⾃⼰的重量weight和价格value，在限定的总重量内，我们如何选择，才能使得物品的总价格最⾼。

2【0-1背包问题】ai：第i个物品的体积；ci：第i个物品的价值；b：背包的重量限制；背包问题就是在总的体积有限的条件下,追求总价值最⼤的有效资源分配问题。

有界的整数背包问题可转化成等价的0-1背包问题，定义变量三、粒⼦群算法简介1 引⾔⾃然界中的鸟群和鱼群的群体⾏为⼀直是科学家的研究兴趣所在。

⽣物学家Craig Reynolds在1987年提出了⼀个⾮常有影响的鸟群聚集模型，在他的仿真中，每⼀个个体都遵循：避免与邻域个体相撞：匹配邻域个体的速度；飞向鸟群中⼼，且整个群体飞向⽬标。

仿真中仅利⽤上⾯三条简单的规则，就可以⾮常接近地模拟出鸟群飞⾏的现象。

1990年， ⽣物学家Frank Heppner也提出了鸟类模型， 它的不同之处在于：鸟类被吸引飞到栖息地。

在仿真中，⼀开始每⼀只鸟都没有特定的飞⾏⽬标，只是使⽤简单的规则确定⾃⼰的飞⾏⽅向和飞⾏速度，当有⼀只鸟飞到栖息地时，它周围的鸟也会跟着飞向栖息地，最终整个鸟群都会落在栖息地。

1995年， 美国社会⼼理学家James Kennedy和电⽓⼯程师RussellEberhart共同提出了粒⼦群算法(ParticleS warm Optimization，PSO) ， 该算法的提出是受对鸟类群体⾏为进⾏建模与仿真的研究结果的启发。

他们的模型和仿真算法主要对Frank Heppner的模型进⾏了修正，以使粒⼦飞向解空间并在最优解处降落。

粒⼦群算法⼀经提出，由于其算法简单，容易实现，⽴刻引起了进化计算领域学者们的⼴泛关注， 形成⼀个研究热点。

利用M A T L A B实现遗传算法和M A T L A B神经网络工具箱的使用实验一利用MATLAB实现遗传算法一、实验目的1、熟悉MATLAB语言编程环境2、掌握MATLAB语言命令3、学会利用MATLAB编程实现遗传算法二、实验原理MATLAB是美国Math Works公司出品的商业数学软件，用于算法开发、数据可视化、数据分析以及数值计算的高级技术计算语言和交互式环境，MATLAB可以进行矩阵运算、绘制函数和数据、实现算法、创建用户界面、连接其他编程语言的程序等，主要应用于工程计算、控制设计等领域。

通过学习遗传算法原理，使用MATLAB编写程序，实现其求解策略。

三、实验内容通过MATLAB编程，利用遗传算法求解：)x=求[-2,2]f-(xf.x，max∈.005)sin(),x((xexp)200三、实验要求1、程序设计2、调试3、实验结果4、撰写实验报告实验二 MATLAB神经网络工具箱的使用一、实验目的1、掌握MATLAB语言命令2、提高MATLAB程序设计能力3、学会使用MATLAB神经网络工具箱二、实验原理MATLAB语言是Math Works公司推出的一套高性能计算机编程语言，集数学计算、图形显示、语言设计于一体，其强大的扩展功能为用户提供了广阔的应用空间。

它附带有30多个工具箱，神经网络工具箱就是其中之一。

利用该工具箱可以方便的构建神经网络的结构模型、设计、训练等，实现神经网络算法。

三、实验内容通过MATLAB编程，利用神经网络工具箱预测公路运量：公路运量主要包括公路客运量和公路货运量两个方面。

据研究，某地区的公路运量主要与该地区的人数、机动车数量和公路面积有关，上表给出了该地区20年的公路运量相关数据。

根据有关部门数据，该地区2010和2011年的人数分别为73.39和75.55万人，机动车数量分别为3.9635和4.0975万辆，公路面积分别为0.9880和1.0268万平方千米。

matlab背包问题遗传算法代码背包问题是运筹学中的经典问题，通过遗传算法求解时基本流程如下：（1）初始化种群：随机产生多个种群。

（2）计算种群适应度：计算每个个体的结果，得到每个个体的适应度函数。

（3）选择操作：对种群中的每个个体进行适应度函数的排序，按照排序结果，从最优个体开始，每次选取适应度函数值较高的个体，最后得到要留下来繁殖的个体。

（4）交叉操作：将两个个体进行配对，利用一定的概率将两个个体的一个部分交换，进行杂交，产生新的一代种群。

（5）变异操作：对种群中的某个个体，以一定的概率采取变异的操作，即在原有的个体基础上，随机改变其中的某个片段，使得新生成的个体具有更广的适应性。

（6）重复步骤2-5，直至满足一定的目标为止。

MATLAB中可以利用optiToolbox实现上述流程，相应的代码如下：//创建优化问题problem = OptiProblem(10, 20);//初始化种群：产生大小为N*M的种群N = 10;M = 20;pop = optipop(N, M);//计算适应性函数pop = calcFitness(pop);//计算解空间[pop, stats] = optiAdapt(problem, pop);//进行选择操作pop = optiSelect(pop, stats.fitness);//进行交叉操作pop = optiCross(pop);//进行变异操作pop = optiMutates(pop);//迭代群组，直到收敛为止for i = 1 : 100pop = calcFitness(pop);[pop,stats] = optiAdapt(problem,pop);pop = optiSelect(pop,stats.fitness);pop = optiCross(pop);pop = optiMutates(pop);end有关编程可以参考MATLAB中optiToolbox自带的例程及demo。

背包问题：clearclcpopsize=500;%种群大小n=50;CW=1000;%背包大小可容纳的总重量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 50 30 45 30 60 50 20 65 20 25 30 10 ...20 25 15 10 10 10 4 4 2 1];%各个物品的重量，50个个体v=[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];%各个物品的价值，50个个体t=100;%迭代次数pc=0.9;%交叉率pm=0.05;%变异率pop=initpop(popsize,n); %产生初始种群for i=1:500[objvalue]=calobjvalue(pop,n,popsize,v,w,CW); %计算目标函数[fitvalue]=calfitvalue(objvalue);%计算群体中每个个体的适应度[newpop]=selection(pop,fitvalue);%进行选择计算[newpop1]=crossover(newpop,pc);%进行交叉计算[newpop2]=mutation(newpop1,pm);%进行变异计算[newobjvalue]=newcalobjvalue(newpop2,n,popsize,v,w,CW); %计算最新代目标函数值，经过选择交叉变异后的下一代[newfitvalue]=newcalfitvalue(newobjvalue);%计算最新代的个体适应度[bestweight,bestvalue]=best(newpop2,newfitvalue,w); %计算最优个体重量，价值，和位置y(i)=max(bestvalue);%记录最大价值g(i)=max(bestweight);%记录最大重量n(i)=i;%记录位置pop=newpop2;%迭代重复endi=1:500;plot(y(i),'-b*')xlabel('迭代次数')ylabel('最大价值');title('最优点变化趋势');legend('最优点');grid on[z index]=max(y);po=n(index)%最优代数位置W=g(index)%最优重量V=z%最优价值%误差率计算%文献中的结果：算法最大迭代次数总价值为总重量为%传统的算法4003077999%佳点集算法7031031000%遗传算法7531031000%本程序中的计算与文献结果的比较p1=(3077-V)/3077%与传统算法相比的误差率p2=(3103-V)/3103%与佳点集算法相比的误差率p3=(3103-V)/3103%与贪心算法遗传算法相比的误差率function [bestweight,bestvalue]=best(newpop2,newfitvalue,w) %寻找最优个体，包括其重量和价值。

背包问题遗传算法matlab
背包问题是一种NP难问题，它在计算机科学，特别是优化问题中广泛应用。

它的基本形式是：有一个固定大小的背包，一些物品和它们的价值。

需要找到一种装载方式，使得装进背包的物品的总价值最大。

遗传算法是一种模拟自然进化过程的优化算法。

在解决背包问题时，遗传算法的应用可以大大提高求解效率。

在MATLAB中实现背包问题的遗传算法需要遵循以下步骤：
1.初始化种群。

随机生成符合题目限制的二进制编码，用于表示每个物品是否被选择。

种群大小可以根据实际情况设置。

2.计算适应度。

通过计算每个个体所装物品的总价值和总重量，计算适应度值。

3.选择。

采用轮盘赌算法进行选择，适应度越好的个体被选中的概率越大。

4.交叉。

对于被选中的个体，采用二进制交叉算子进行交叉，产生新一代个体。

5.变异。

对新一代个体进行变异操作，以保证种群的多样性。

6.重复以上步骤，直到满足终止条件。

通过上述步骤，我们可以得到背包问题的近似最优解。

不过，在实际应用过程中，需要针对问题的特点进行具体调整，遗传算法也需要根据问题的性质进行优化，如选择合适的交叉算子、变异算子等。

在MATLAB中实现遗传算法的过程并不复杂，但对于初学者来说，可能需要掌握一些相关知识和技能。

因此，在实践中，可以结合相关资源和实例进行练习和掌握。

人工智能之遗传算法求解0/1背包问题实验报告Pb03000982 王皓棉一、问题描述：背包问题是著名的ＮＰ完备类困难问题, 在网络资源分配中有着广泛的应用，已经有很多人运用了各种不同的传统优化算法来解决这一问题，这些方法在求解较大规模的背包问题时,都存在着计算量大,迭代时间长的弱点。

而将遗传算法应用到背包问题的求解，则克服了传统优化方法的缺点,遗传算法是借助了大自然的演化过程,是多线索而非单线索的全局优化方法,采用的是种群和随机搜索机制。

遗传算法（GA）是一类借鉴生物界自然选择和自然遗传机制的随机化的搜索算法，由美国J.Holland教授提出，其主要特点是群体搜索策略、群体中个体之间的信息交换和搜索不依赖于梯度信息。

因此它尤其适用于处理传统搜索方法难于解决的复杂和非线性问题，可广泛应用于组合优化，机器学习，自适应控制，规划设计和人工生命领域。

GA是一种群体型操作，该操作以群体中的所有个体为对象。

选择，交叉和变异是遗传算法的三个主要算子，他们构成了遗传算法的主要操作，使遗传算法具有了其它传统方法所没有的特性。

遗传算法中包含了如下五个基本要素：1 .参数编码,2.初始群体的设置,3.适应度函数的设计, 4.遗传操作设计,5.控制参数设定,这个五个要素构成可遗传算法的核心内容。

遗传算法的搜索能力是由选择算子和交叉算子决定,变异算子则保证了算法能够搜索到问题空间的每一个点,从而使其具有搜索全局最优的能力.而遗传算法的高效性和强壮性可由Holland提出的模式定理和隐式并行性得以解释。

二、实验目的：通过本实验，可以深入理解遗传算法，以及遗传算法对解决NP问题的作用。

三、算法设计：1、确定种群规模M、惩罚系数 、杂交概率c p、变异概率m P、染色体长度n及最大max.进化代数genx=1表2、采用二进制n维解矢量X作为解空间参数的遗传编码，串T的长度等于n，ix=0表示不装入背包。

例如X={0，1，0，1，0，0，1}表示第2，4，7示该物件装入背包，i这三个物件被选入包中。

遗传算法的过程：初始化：将计划装入背包的每个物品看成一个二进制串的一位，为1表示放入该物品，为0表示不放入该物品。

初始种群的产生：初始化前对放入背包物品数的一个预测（背包容积/物品最大体积），接下来只要在种群每条染色体中保证有（背包容积/物品最大体积）个为1的位初始化就完成了。

选择：选择进行杂交的父代染色体，被选中的父代染色体总是若干个染色体中最优（适应度最高）的，来保证向优化的方向发展。

详细的选择方法：随机产生2个数：Chrom_Cross_From, Chrom_Cross_To,当然得采用一定的手段来保证前者比后者小。

从Chrom_Cross_From到Chrom_Cross_To这Chrom_Cross_To-Chrom_Cross_From+1条染色体中选择最优（适应度最大）的染色体作为父代之一。

需要进行两次选择得到杂交的两条父代染色体。

这样做可以保证算法不会过早收敛。

函数实现：Individual Select(int ChromSize,Individual Pop[]){int Num_Selected,i,j,Chrom_Selected_From,Chrom_Selected_To,temp;Individual *Chrom_Selected;do{Chrom_Selected_From=rand()%PopSize;Chrom_Selected_To=rand()%PopSize;if(Chrom_Selected_From>Chrom_Selected_To){temp=Chrom_Selected_From;Chrom_Selected_From=Chrom_Selected_To;Chrom_Selected_To=temp;}Num_Selected=Chrom_Selected_To-Chrom_Selected_From+1;}while(Num_Selected<=0);Chrom_Selected=new Individual[Num_Selected];for(i=0;i<Num_Selected;i++)Chrom_Selected[i].chrom=new int[ChromSize];for(i=0,j=Chrom_Selected_From;i<Num_Selected,j<Chrom_Selected_To+1;i++,j++){Chrom_Selected[i]=Pop[j];}Order_Best_First(ChromSize,Num_Selected,Chrom_Selected);Chrom_Selected[0].fitness=Fitness(Chrom_Selected[0].chrom,ChromSize);return Chrom_Selected[0];}杂交：将两次选择得到的父代染色体进行杂交得到一条新的染色体，作为较新种群（并非新的种群）的一条染色体，杂交直到较新种群的染色体数等于原种群的染色体数。

背包问题的三种解法实验报告实验要求：分别用动态规划法、回溯法、分支限界法解决0/1 背包问题，了解三种算法的算法步骤并上机实现。

实验步骤：1. 建立一个背包问题的解法类Bag.h。

bag_m为动态规划法，bag_b为回溯法，bag_t为分支限界法。

2. 建立一个排序类Sort1.h。

程序的需要对背包的价值比排序。

3. 由分支限界建立一个动态的最大堆及堆的各种操作和运算类SqList.h。

代码实现：1. 主函数：// 背包问题的解法#include <iostream> #include "Bag.h"// 背包问题处理方法类using namespace std;int main() int i,n,M;coutvv"请输入物品个数：";cin>>n;double *m=new double[n+1];double *p=new double[n+1];coutvv"输入每个物品的重量：";for(i=1;i<=n;i++)cin>>m[i];coutvv"输入每个物品的价值:for(i=1;i<=n;i++)cin>>p[i];coutvv"请输入背包的重量：";cin>>M;Bag bag;//创建一个背包问题的解法类对象coutvv"选择背包问题的解法，输入1,动态规划法，输入2,回溯法，输入3,分支限界法。

"vv'\n'vv"请输入1或者2,或者输入3："<<"";cin>>i;if(i==1)bag.bag_m(m, p,n,M);//调用动态规划法if(i==2)bag.bag_b(m, p,n,M);// 调用回溯法if(i==3)bag.bag_t(m, p,n ,M);//调用分支限界法return 0;2. 排序方法类：（Filename：Sort1.h）// 合并排序类（合并排序）#include <iostream>using namespace std;struct objdouble m;double p;double v;};typedef struct obj OBJ; // 定义物体的数据结构class Sort1public:void merge_sort(OBJ a[],int n)// 以物体的价值比排序int i,s,t=1;while(t<n)s=t;t=2*s;i=0;while(i+t<n)merge(a,i,i+s-1,i+t-1,t);i=i+t;if(i+s<n)merge(a,i,i+s-1,n-1,n-i);void merge(OBJ a[],int p,int q,int r,int n)OBJ *bp=new OBJ[n];int i,j,k;i=p;j=q+1;k=0;while(i<=q&&j<=r)if(a[i].v<=a[j].v)bp[k++]=a[i++];elsebp[k++]=a[j++];if(i==q+1)for(;j<=r;j++)bp[k++]=a[j];elsefor(;i<=q;i++)bp[k++]=a[i];k=0;for(i=p;i<=r;i++)a[i]=bp[k++];delete bp;};3. 背包问题解法类：（Filename：Bag.h）// 背包问题方法类（包含三种方法）//bag_m 动态规划法//bag_b 回溯法//bag_t 分支限界法#include <iostream>using namespace std;#include "Sort1.h"#include "SqList.h"class Bagpublic:void bag_m(double *m,double *p,int n,int M)// 动态规划法int i,j;int *x=new int[n+1];OBJ *objs=new OBJ[n+1];objs[0].p=0;objs[0].v=0;for(i=1;i<=n;i++)objs[i].m=m[i];objs[i].p=p[i];objs[i].v=objs[i].m/objs[i].p;double **optp;optp=new double *[n+1]; for(i=0;i<n+1;i++)optp[i]=new double[M+1]; x[i]=0;for(i=0;i<=n;i++)optp[i][0]=0;for(i=0;i<=M;i++)optp[0][i]=0;for(i=1;i<=n;i++)for(j=1;j<=M;j++)optp[i][j]=optp[i-1][j];elseoptp[i][j]=optp[i-1][j];if(optp[i][j]<(optp[i-1][int(j-objs[i].m)]+objs[i].p)) optp[i][j]=(optp[i-1][int(j-objs[i].m)]+objs[i].p);i=n;j=M;while(i&&j)if(optp[i][j]>optp[i-1][j])x[i]=1;j-=objs[i].m;elsex[i]=0;cout<<" 输出结果，装入为1，不装入为0:"<<'\n'; for(i=1;i<=n;i++)cout<<x[i]<<" ";}cout<<'\n';coutvv"背包物体的总价值最大为："VVO ptp[n ][M]VV'\n：delete x,objs;for(i=0;i<=n;i++)delete [] optp[i];delete optp;void bag_b(double *m,double *p,int n,int M)// 回溯法int i,j,k;int *x=new int[n+1];int *y=new int[n+2];double m_cur,m_est,p_cur,p_est,p_total;m_cur=0;p_cur=0;p_total=0;OBJ *objs=new OBJ[n+1];objs[0].m=0;objs[0].p=0;objs[0].v=0;for(i=1;i<=n;i++)objs[i].m=m[i];objs[i].p=p[i];objs[i].v=objs[i].m/objs[i].p;y[i]=0;x[i]=0;y[n+1]=0;Sort1 sort;sort.merge_sort(objs,n+1);// 排序k=1;while(k>=1)p_est=p_cur;m_est=m_cur;for(i=k;i<=n;i++)m_est=m_est+objs[i].m;if(m_est<M)p_est=p_est+objs[i].p;elsep_est=p_est+((M-m_est+objs[i].m)/objs[i].m)*objs[i].p;break; if(p_est>p_total)for(i=k;i<=n;i++)if(m_cur+objs[i].m<=M) m_cur+=objs[i].m;p_cur+=objs[i].p;y[i]=1;else {y[i]=0; break;}if(i>=n)if(p_cur>p_total)p_total=p_cur;k=n+1; for(j=1;j<=n;j++)x[j]=y[j];else k=i+1;elsewhile(i>=1&&y[i]==0)if(i<1) break;elsem_cur-=objs[i].m;p_cur-=objs[i].p;y[i]=0;k=i+1;for(i=1;i<=n;i++)cout<<x[i];cout<<'\n';cout<<"total="<<p_total;delete x,y,objs;void bag_t(double *m,double *p,int n,int M)// 分支限界法int i;double t;OBJ *ob=new OBJ[n];for(i=0;i<n;i++)ob[i].m=m[i+1];ob[i].p=p[i+1];ob[i].v=ob[i].m/ob[i].p;Sort1 sort;sort.merge_sort(ob,n);Knapnode kn a,k nax,k nay;//定义左节点和右节点kna.b=0;kna.k=0;kna.p=0;kna.w=0;for(i=0;i<5;i++)kna.s1[i]=0;for(i=kna.k,t=kna.w;i<n;i++)if(t+ob[i].m<=M)t+=ob[i].m;kna.b+=ob[i].p;elsekna.b+=(M-t)*ob[i].p/ob[i].m;break;sqlist q;SqList sq;sq.InitList_Sq(q);sq.insert(q,kna);while(q.length!=0)kna=sq.delete_max(q);if(kna.k==5)}}cout<<"the value is:"<<kna.p<<'\n'; for(i=0;i<5;i++)cout<<kna.s1[i]<<" ";cout<<'\n';break;knay=kna;knay.k++;knay.b=knay.p;for(i=knay.k,t=knay.w;i<n;i++)if(t+ob[i].m<=M)t+=ob[i].m;knay.b+=ob[i].p;elseknay.b+=(M-t)*ob[i].p/ob[i].m;break;sq.insert(q,knay);knax=kna;if(knax.w+ob[knax.k].m>M)continue;knax.s1[knax.k]=1;knax.w+=ob[knax.k].m;knax.p+=ob[knax.k].p;knax.k++;sq.insert(q,knax);};4.动态堆方法类（分支限界方法中用到，Filename：SqList.h）// 动态最大堆#include <iostream>#include "math.h"#include <iomanip>using namespace std;#define ListInitSize 20#define ListIncrement 10const n=5;typedef structint s1[n];int k;float b;float w;float p;}Knapnode;typedef struct sqListKnapnode *elem;int length;int listsize;}sqlist;class SqList/动态堆类public:void InitList_Sq(sqlist &L)//n 为单位元素的大小，初始化堆L.elem=(Knapnode *)malloc(ListInitSize* sizeof(Knapnode));if(L.elem==NULL) exit(OVERFLOW);L.length=0;L.listsize=ListInitSize;void ListI nsert_Sq(sqlist & L,K napn ode elem)/向堆中插入节点Knapnode * newbase;if(L.length>=L.listsize)newbase=(Knapnode*)realloc(L.elem,(L.listsize+ListIncrement)sizeof(Knapnod e))if(newbase==NULL) exit(OVERFLOW);L.elem=newbase;L.listsize+=ListIncrement;L.elem[++L.length]=elem;void sift_up(sqlist &L,int i)// 上移操作while(i>=2)*if(L.elem[i].b>L.elem[i/2].b)swap(L.elem[i/2],L.elem[i]);i/=2;else break;void sift_down(sqlist &L,int i)// 下移操作int done=0;i=2*i;while(done==0&&i<=L.length)if(i+1<=L.length&&L.elem[i+1].b>L.elem[i].b) i++;if(L.elem[i/2].b<L.elem[i].b)swap(L.elem[i/2],L.elem[i]);else done=1;void swap(Knapnode &a,Knapnode &b)Knapnode t;t=a;a=b;b=t;void in sert(sqlist & L,Kna pn ode x)//插入节点后，并排序ListInsert_Sq(L,x);sift_up(L,L.length);Kna pn ode delete_max(sqlist & L)//删除堆中预测价值的最大者Knapnode p;p=L.elem[1];swap(L.elem[1],L.elem[L.length]);L.length--;sift_down(L,1);return p;void print(sqlist &L)// 打印堆的数据int i;};for(i=1;i<=L.length;i++)cout<<L.elem[i].b;运行方法和结果（用这三种算法分别给出实验结果）：1. 动态规划法：2. 回溯法：3. 分支限界法。

“遗传算法”解决“背包问题”遗传算法基本思想：1) ⼀个种群有多个个体，每个个体有染⾊体和对应的基因为了繁殖进⾏：2) 选择：在残酷的世界中，适者⽣存，优胜略汰。

3) 重组：染⾊体交叉，基因重组4) 突变：染⾊体上的基因⼩概率的突变（⼀般给⼩数点后两位）背包问题：背包只能容得下⼀定重量b的物品，物品有m种，每种物品有⾃⼰的重量w(i)和价值v(i)（0<i<=m），从这些物品中选择装⼊背包，是背包不超过重量b，但价值⼜要最⼤。

运⽤动态规划，分⽀限界都可以达到效果，但不佳。

我⽤遗传算法解决：⼀般⼈有多条染⾊体，但对于背包问题，⼀个解我们将看成⼀个个体，所以，⼀个个体只有⼀个染⾊体，⼀个染⾊体对应多个基因。

如：100101010100111 表⽰装⼊背包的可能解。

（具体情况具体分析）遗传所做准备：1) ⽤0表⽰“不选择装⼊”，1表⽰“装⼊”，形成⼀条基因链；100101010100111则表⽰“15种物品”装⼊或不装⼊背包的可能解。

------- 此处⽤chrom[]存放基因，代表染⾊体2) ⼀个基因对应⼀个个体。

------- 此处⽤Population类或结构体声明其含有chrom[]等信息3) 可能的解有很多，构成⼀个种群。

------- ⽤Population类定义⼀个数组代表个体构成的种群newPop[]：存放新⽣代，oldPop[]：存放上⼀代4) 适应度：适应度和⽬标函数是正相关的，所以需要物品价值和重量。

------- fitness,weight包含在Population类中最⼤适应度：maxFitness,最⼩适应度：minFitness,总适应度：sumFitness,(帮助求突变和交叉的染⾊体)平均适应度：avgFitness遗传算法的函数：基本：1) InitPop() 初始化个体，使每个个体都有基因组2) Statistics(*pop) 计算适应度（最⼤，最⼩，总的，平均的）3) Selection(*pop) 通过选择种群中符合要求的⽗母去繁殖新代，返回这对⽗母的位置4) crossover(*parent1,*parent2,pos) 传⼊要改的个体位置，随机产⽣交叉位置，⽤优良⽗母繁殖优良后代并替代传⼊个体位置5) mutation(i) i为基因组基因的位置，逐个基因看是否要变异6) generation() 对个体进⾏判断，若不符合要求，进⾏选择，重组，突变。

智能控制作业遗传算法求解背包问题智能控制遗传算法求解背包问题——16组遗传算法求解背包问题摘要：遗传算法是在分析遗传个体进化机制基础上提出的一种新型优化算法。

本论文根据0-1 背包问题的特点，提出用于求该问题的遗传算法及相关的解决方案，阐明算法的具体实现过程。

通过对其他文献中仿真实例的计算和结果比较，表明应用该算法求解背包问题取得了良好的效果。

该算法同样可以应用于其他组合优化题。

关键词：背包问题；遗传算法一．概述背包问题(knapsack problem) 是运筹学中一个典型的优化难题，有着广泛的实际应用背景，如管理中的资源分配、投资决策、预算控制等问题，并且经常作为其他问题的子问题被研究。

研究背包问题的求解算法在理论上和实践中都具有一定的意义。

从计算复杂性理论来看，背包问题是个NP 完全问题，该问题的求解方法主要有启发式算法，如贪心算法、遗传算法、粒子群算法。

以遗传算法为代表的生物进化算法建立在达尔文自然选择学说的基础上，是对生物进化过程的模拟，是人们对从自然演化过程中抽象出的概念、原则和机制的类比应用，被广泛用于解决复杂的计算问题。

其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。

遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。

它是现代有关智能计算中的关键技术。

本文在分析遗传算法的基础上，提出了将贪婪修复方法与遗传算法相结合，构成混和遗传算法，并应用于求解经典背包问题。

它是可以解决复杂问题的新方法。

本论文系统的介绍背包问题的遗传算法解决方案。

二．背包问题的数学模型背包问题的定义：我们有n 种物品，物品j 的重量为wj ，价格为pj 。

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

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

本栏目责任编辑：谢媛媛开发研究与设计技术遗传算法（ＧＡ）是借鉴生物界自然选择和群体进化机制而形成的一种全局寻优算法，其本质上是一种基于概率的随机搜索算法。

与其它的优化算法相比较，遗传算法具有以下优点：（１）通用性；（２）并行性；（３）简单性和可操作性；（４）稳定性和全局性。

１遗传算法概述在遗传算法中，首先将空间问题中的决策变量通过一定的编码表示成遗传空间的一个个体，它是一个基因型串结构数据；然后将目标函数转换成适应度值，用来评价每个个体的优劣，并将其作为遗传操作的依据。

遗传操作包括三个算子：选择、重组和变异。

选择是从当前群体中选择适应值高的个体以生成交配池的过程，交配池是当前代与下一代之间的中间群体。

选择算子的作用是用来提高群体的平均适应度值。

重组算子的作用是将原有的优良基因遗传给下一代个体，并生成包含更复杂基因的新个体，它先从交配池中的个体随机配对，然后将两两配对的个体按一定方式相互交换部分基因。

变异算子是对个体的某一个或几位按某一较小的概率进行反转其二进制字符，模拟自然界的基因突变现象。

遗传算法的基本程序实现流程如下：（１）先确定待优化的参数大致范围，然后对搜索空间进行编码；（２）随机产生包含各个个体的初始种群；（３）将种群中各个个体解码成对应的参数值，用解码后的参数求代价函数和适应度函数，运用适应度函数评估检测各个个体适应度；（４）对收敛条件进行判断，如果已经找到最佳个体，则停止，否则继续进行遗传操作；（５）进行选择操作，让适应度大的个体在种群中占有较大的比例，一些适应度较小的个体将会被淘汰；（６）随机交叉，两个个体按一定的交叉概率进行交叉操作，并产生两个新的子个体；（７）按照一定的变异概率变异，使个体的某个或某些位的性质发生改变；（８）重复步骤（３）至（７），直至参数收敛达到预定的指标。

使用遗传算法需要确定的运行参数有：编码串长度、交叉和变异概率、种群规模。

编码串长度由问题的所要求的精度来决定。

LINGO 使用教程LINGO 是用来求解线性和非线性优化问题的简易工具。

LINGO 内置了一种建立最优化模型的语言，可以简便地表达大规模问题，利用LINGO 高效的求解器可快速求解并分析结果。

§1 LINGO 快速入门当你在windows 下开始运行LINGO 系统时，会得到类似下面的一个窗口：外层是主框架窗口，包含了所有菜单命令和工具条，其它所有的窗口将被包含在主窗口之下。

在主窗口内的标题为LINGO Model – LINGO1的窗口是LINGO 的默认模型窗口，建立的模型都都要在该窗口内编码实现。

下面举两个例子。

例1.1 如何在LINGO 中求解如下的LP 问题：,6002100350..32min 212112121≥≤+≥≥++x x x x x x x t s x x在模型窗口中输入如下代码： min =2*x1+3*x2; x1+x2>=350; x1>=100;2*x1+x2<=600;然后点击工具条上的按钮 即可。

例1.2 使用LINGO 软件计算6个发点8个收点的最小费用运输问题。

产销单位运价如model:!6发点8收点运输问题;sets:warehouses/wh1..wh6/: capacity;vendors/v1..v8/: demand;links(warehouses,vendors): cost, volume;endsets!目标函数;min=@sum(links: cost*volume);!需求约束;@for(vendors(J):@sum(warehouses(I): volume(I,J))=demand(J));!产量约束;@for(warehouses(I):@sum(vendors(J): volume(I,J))<=capacity(I));!这里是数据;data:capacity=60 55 51 43 41 52;demand=35 37 22 32 41 32 43 38;cost=6 2 6 7 4 2 9 54 95 3 8 5 8 25 2 1 9 7 4 3 37 6 7 3 9 2 7 12 3 9 5 7 2 6 55 5 2 2 8 1 4 3;enddataend然后点击工具条上的按钮即可。

图1最小值的求解图在Matlab 中没有求最大值函数,因此需要先将目标转化为最小值问题:min (-f )=-3x 1-7x 2;s.tx 1≤7x 2≤6x 1,x 2>0x 1+2x 2≤17⎧⎩⏐⏐⏐⏐⏐⏐⎨⏐⏐⏐⏐⏐⏐,然后进行转换即可。

Matlab 中代码设计如下:>>f =[-3,-7];>>A =[1,0;0,1;1,2];>>b =[7,6,17];>>lb =[0,0];>>[x ,fval ]=linprog (f ,A ,b ,[],[],lb )Optimization terminated.可得到x =5.0000fval =-57.00006.0000可以发现x 1和x 2取值都符合要求,即maxf =fval*(-1),则maxf =57.0000。

2.2.2基于Lingo 求线性规划最优解图2最大值的求解图3结论通过以上的基于两种软件的求最优值的过程对比可以得出,不管是使用Matlab还是Lingo,两种方法一样,但求解的程序形式有着较大的差异。

Matlab中,需要用到数组(矩阵)的知识点,所以可能需要前期的学习过程作为铺垫。

同时,也可以明显知道,Matlab中的程序接口是已经写好的,即linprog的使用格式是固定的,就线性规划而言,在日常生活中,需要使用的整数性的线性规划时就会受到一定的限制,一般的情况下,整数情况可能较少,所以关于小数化整数的过程需要自己进行编译,因此,这一过程可能对初学者很不友善,受到一定的制约。

但Matlab在进行规模庞大的变量运算时具有很大的优势,在非线性(上接第33页)息融合NFE模型的研究及应用[J].电子与信息。

matlab、lingo程序代码3-背包问题（遗传算法）复习过程背包问题---遗传算法解决function Population1=GA_copy(Population,p,w0,w)%复制算子%Population为种群n=length(Population(:,1));fvalue=zeros(1,n);for i=1:nfvalue(i)=GA_beibao_fitnessvalue(Population(i,:),p,w0,w);endfval=fvalue/sum(fvalue);F(1)=0;for j=1:nF(j+1)=0;for k=1:jF(j+1)=F(j+1)+fval(k);endendfor i=1:ntest=rand;for j=1:nif((test>=F(j))&&(test<f(j+1)))< p="">Population1(i,:)=Population(j,:);endendendfunction Population1=GA_exchange(Population,pc) %遗传算法交换算子%pc为交换概率Population1=Population;POP=[];n=length(Population(:,1));%k=floor(n*pc); %用于交换的染色体数目%采用单点交换算子j=1;l=length(Population(1,:));for i=1:ntest(i)=rand;if test(i)<pc< p="">for z=1:lPOP(j,z)=Population(i,z);endPOP(j,l+1)=i;p(j)=randint(1,1,[1 l-1]);j=j+1;endendk0=j-1;k=floor(k0/2);if k>=1for m=1:kfor t=p(2*m-1)+1:ls=POP(2*m-1,t);POP(2*m-1,t)=POP(2*m,t);POP(2*m,t)=s;endendfor m=1:k0for i=1:lPopulation1(POP(m,l+1),i)=POP(m,i);endendendfunction fitnessvalue=GA_fitnessvalue(x,p,w0,w) %使用惩罚法计算适应度值%x为染色体%p为背包问题中每个被选物体的价值%w0为背包问题中背包总容积%w为背包问题中每个被选物品的容积l=length(x);for i=1:la(i)=p(i).*x(i);endf=sum(a);b=min(w0,abs(sum(w)-w0));for i=1:lwx(i)=w(i).*x(i);endif abs(sum(wx)-w0)>b*0.99p=0.99;</pc<></f(j+1)))<>。