遗传算法的0-1背包问题c语言99250

1、基于遗传算法的0-1背包问题的求解摘要：一、前言组合优化问题的求解方法研究已经成为了当前众多科学关注的焦点，这不仅在于其内在的复杂性有着重要的理论价值，同时也在于它们能在现实生活中广泛的应用。比如资源分配、投资决策、装载设计、公交车调度等一系列的问题都可以归结到组合优化问题中来。但是，往往由于问题的计算量远远超出了计算机在有效时间内的计算能力，使问题的求解变为异常的困难。尤其对于NP完全问题，如何求解其最优解或是近似最优解便成为科学的焦点之一。遗传算法已经成为组合优化问题的近似最优解的一把钥匙。它是一种模拟生物进化过程的计算模型，作为一种新的全局优化搜索算法，它以其简单、鲁棒性强、适应并行处理

2、以及应用范围广等特点，奠定了作为21世纪关键智能计算的地位。背包问题是一个典型的组合优化问题，在计算理论中属于NP-完全问题，其计算复杂度为O（2n）,传统上采用动态规划来求解。设wi是经营活动i所需要的资源消耗，M是所能提供的资源总量，pi是人们经营活动i得到的利润或收益，则背包问题就是在资源有限的条件下，追求总的最大收益的资源有效分配问题。二、问题描述背包问题（KnapsackProblem用一般提法是：已知n个物品的重量（weight:）及其价值（或收益profit）分别为Wi0和Pi0,背包的容量（contain）假设设为G0,如何选择哪些物品装入背包可以使得在背包的容量约束限制之内所

3、装物品的价值最大？该问题的模型可以表示为下述0/1整数规划模型：cixii1目标函数：maxf（x1,x2,xn）n7Wi为piS.ti1Xi0,1（i1,2,n）式中Xi为0-1决策变量，Xi1时表示将物品i装入背包中，Xi0时则表示不将其装入背包中。三、求解背包问题的一般方法解决背包问题一般是采取动态规划、递归回溯法和贪心方法。动态规划可以把困难得多阶段决策变换为一系列相互联系比较容易的单阶段问题。对于背包问题可以对子过程用枚举法求解，而且约束条件越多，决策的搜索范围越小，求解也越容易。它的主要缺点是用数值方法求解时会随着状态变量的个数呈指数级的增长，往往对于求解背包问题的实际问题是不现实

4、的。使用递归回溯法解决背包问题的优点在于它算法思想简单，而且它能完全遍历搜索空间，肯定能找到问题的最优解；但是由于此问题解的总组合数有2n个，因此，随着物件数n的增大，其解的空间将以2n级增长，当n大到一定程度上，用此算法解决背包问题将是不现实的。使用贪心方法求解时计算的复杂度降低了很多，但是往往难以得到最优解，有时所得解与最优解相差甚远。因此，我们可以探索使用遗传算法解决物件数较大的背包问题。四、遗传算法简介遗传算法(GeneticAlgorithms,GA)是在1975年首次由美国密西根大学的DoJoHolland教授和他的同事们借鉴生物界达尔文的自然选择法则和孟德尔的遗传进化机制基础之上

5、提出的。经过近30年的研究、应用，遗传算法已被广泛地应用于函数优化、机器人系统、神经网络学习过程、模式识别、图象处理、工业优化控制等领域。遗传算法是将问题的每一个可能性解看作是群体中的一个个体(染色体),并将每一个染色体编码成用的形式，再根据预定的目标函数对每个个体进行评价，给出一个适应值。算法将根据适应度值进行它的寻优过程，遗传算法的寻优过程是通过选择、杂交和变异三个遗传算子来具体实现的。它的搜索能力由选择算子和杂交算子决定，变异算子则保证了算法能够搜索到问题空间的尽可能多的点，从而使其具有搜索全局最优的能力。遗传算法的高效性和强壮性可由Holland提出的模式定理(SchemaTherem

6、)和隐式并行性得以解释。在遗传算法中，定义长度较短、低阶且适应值超过平均适应值的模式在群体中数目的期望值按指数递增，这个结论称为遗传算法的基本定理。遗传算法是通过定义长度短、确定位数少、适应度值高的模式的反复抽样、组合来寻找最佳点，称这些使遗传算法有效工作的模式为积木块，是遗传算法构造答案的基本材料。但归根到底，要使遗传算法有效工作必须按照遗传算法的模式定理（或积木块假设）根据具体问题设计合理的编码方案。在运行遗传算法程序时，需要对一些参数作事先选择，它们包括种群的大小、染色体长、交叉率、变异率、最大进化代数等，这些参数对GA的性能都有很重要的影响。在试验中参数一般选取如下：种群大小N=201

7、00,交叉概率pc=0.40.9,变异概率pm=0.0010.1,最大进化代数maxgen=100500.遗传算法是具有“生成+检测”的迭代过程的搜索算法。它的基本处理流程如图1所示。图1、遗传算法的基本流程遗传算法的基本流程描述如下:(1)编码：将解空间的解数据进行二进制编码，表达为遗传空间的基因型用(即染色体)结构数据，如将数据9编码为“1001”；(2)初始化种群：定义整数pop_size作为染色体的个数，并且随机产生pop_size个染色体作为初始种群；(3)评估种群中个体适应度：评价函数对种群中的每个染色体(chromosome求得其个体适应度fi(fitness)；(4)选择：选择

8、把当前群体中适应度较高的个体按某种规则或者模型遗传到下一代种群中，这里所用的规则是：染色体在种群中被选择的可能性与其个体的适应度的大小成正比；(5)交叉：定义参数Pc作为交叉操作的概率，由(4)选择得到的两个个体以概率pc交换各自的部分染色体，得到新的两个个体；(6)变异：定义参数Pm作为变异操作的概率，由(5)得到每个个体中的每个基因值都以概率Pm进行变异；(7)演化：经过选择、交叉和变异操作，得到一个新的种群，对上述步骤经过给定的循环次数(maxgen)的种群演化，遗传算法终止。五、背包问题的遗传算法求解描述基于背包问题的模型(*),我们设计了针对于背包问题的染色体编码方法：将待求解的各量

9、X表示成长为n的二进制字符串xj,j=1,2,，n。xj0表示物体j不放入背包内，xj1表示物体j放入背包内。例如：111001100000111代表一个解，它表示将第1、2、3、6、7-n-2,n-1,n号物体放入背包中，其它的物体则不放入。根据遗传算法的基本流程，我们确定了求解背包问题的遗传算法：步骤1、初始化过程1.1 确定种群规模popsizes杂交概率Pc、变异概率Pm、染色体长度lchrom及最大进化代数maxgen；1.2 读入背包问题的相关信息，如每个物体的重量weightj、每个物体的收益profitj和背包的容量contain,其中j0,1,(Ichrom1)；1.3 取x

10、ju(0,1)j0,1,(Ichrom1),其中u(0,1)表示0-1整数的均匀分布函数，即随机地生成数0或1,生成的xj用即可看为一个染色体个体。若不满足模型(*)的约束条件，则拒绝接受，由1.2重新生成一个新的染色体个体chrom；如果产生的染色体可行，则接受它作为种群的一名成员，经过有限次的1.2抽样后，得到popsize个可行的染色体chrom,形成新的种群。1.4置种群的代数gen=0；步骤2、计算种群中个体适应度以及统计种群适应度情况2.1按照下列公式计算种群中个体适应度：lchrom1weightweightj*chromj(1);j0lchrom1profitj*chromji

11、fweightcontainfitnesslchro：1(2)profitj*chromjalpha*(weightcontain)ifweightcontainj0公式(2)的下半部分即为适应度的惩罚函数，其中参数alpha1.0。2.2按公式(3)计算种群的总体适应度，popsize1sumfitnessfitnessi(3)i0并且按照排序的方法统计出种群中的最大、最小适应度的染色体个体，分别标记为maxpop、minpop；步骤3、选择操作3.1 生成一个随机数randNumber,要求0randNuber1;3.2 按照赌轮法选择个体，赌轮法的算法描述如下：intselection(

12、)(i=0;个体的编号sum=0；/部分个体适应度的累加和/根据随机数和群体的总适应度确定赌轮的位置wheel-pos=rand_Number*sufitness;whilesum<wheel-pos&&i<=popsizei=i+1;sum=sum+fitnessi;/fitness为第i个个体的适应度returni-1;/选择了个体i-13.3重复两次操作3.1、3.2,生成两个个体作为交叉操作的父代；步骤四、交叉操作4.1 根据事先定义女？的交叉概率pc,为了确定是否进行交叉操作，则生成0,1的随机数pp,若pppc,则进行4.2交叉操作，否则将两个父代保留为

13、下一代的两个个体；4.2 随机生成0,lchrom1的整数作为交叉点，对两个父代个体交叉生成新的两个个体；4.3 重复pop_size/2次4.1、4.2便可生成pop_size个个体组成新的种群；步骤五、变异操作5.1 根据事先定义女?的变异概率pm,为了确定新种群上的每个个体上的每个基因是否进行变异操作，则生成0,1的随机数pp,若pppm,则进行5.2变异操作，否则基因不变异；5.2 基因变异操作为原基因若为1,则新基因则变异为0,若原基因为0,则新基因变异为0;步骤6、演化6.1 按步骤2的方法计算新种群的个体适应度和总体适应度情况，尤其是找出新种群中最大适应度的个体和最小适应度的个体

14、；6.2 若旧种群的最大个体适应度新种群的最大个体适应度，把旧种群的最大适应度的个体代替新种群中的最小适应度的个体，否则进行6.3;6.3 种群的代数gen=genm+1,若genMaxgen,则结束种群的演化，否则转到步骤2六、遗传算法求解的实现/种群的规模/杂交概率/变异概率/染色体长度1、遗传算法的主要参数#definepopsize80#definepc0.7#definepm0.1#defineIchrom50#definemaxgen5000/最大进化代数doublealpha;/计算适应度时使用的惩罚函数系数2、数据结构(1)背包信息:/背包问题中物体重量、收益、背包容量intw

15、eightlchrom,profitlchrom,contain;(2)种群个体结构体structpopulationunsignedintchromlchrom;染色体doublefitness;适应度unsignedintparent1,parent2,cross;/双亲、交叉点;(3)父代种群和新生代种群/父代种群、新生代种群structpopulationoldpoppopsize,newpoppopsize;/pop_size为种群大/、(4)适应度信息/种群的总适应度、最小、最大适应度doublesumfitness,minfitness,maxfitness;/一个种群中最大和最

16、小适应度的个体编号intminpop,maxpop;3、主要函数说明(1)、intread_infor()收益、背包容量）功能：从文件knapsack.txt中读出背包信息（物体重量、参数：无；返回值：返回读取文件信息是否正确;流程图：见图2。图2、read_infor()流程图(2)doublecal_fit(unsignedint*chr)功能：种群中个体适应度计算;参数：unsignedint*chr是染色体个体的指针，根据指针所指向的染色体计算个体的适应度；返回值：染色体个体适应度的大小;流程图：见图3。图3、函数cal_fit的流程图(3)、voidstatistics(struct

17、population*pop)功能：群体适应度的最大最小值以及其他信息；参数：structpopulation*pop是种群指针，根据指针所指向的种群信息统计群体适应度的信息；返回值：无；流程图：见图4。(4)、voidreport(structpopulation*pop,intgen)功能：报告种群的适应度信息，尤其是最大个体适应度、最大适应度个体的染色体信息；参数：structpopulation*pop是种群指针，根据指针所指向的种群报告群体适应度的信息，gen是表示此种群所在的演化代数返回值：无；流程图：见图5图4、函数statistics的流程图图5、函数report的流程图(5)

18、、voidinitpop()功能：生成初始种群;参数：无；返回值：无；流程图：见图6。图6、函数initpop流程图(6)、intexecise(doubleprobability)功能：概率选择试验，以概率probability做随机试验，判断是否进行交叉或变异操作；参数：doubleprobability为交叉概率或变异概率返回值：试验是否成功，0代表不试验成功，将不做交叉或者变异操作，1代表试验成功，即进行交叉或者变异操作；流程图：见图7图7、函数execise的流程图(7)、intselection(intpop)功能：在父代种群中选择个体，规则为适应度越大的个体被选择的概率越大;参数

19、：intpop为父代种群；返回值：父体中被选择的个体i;流程图：见图8。图8、函数selection的流程图(8)、intcrossover(unsignedint*parent1,unsignedint*parent2,inti)功能：两个父代个体在染色体的第i个位置进行交叉，生成两个新个体；i为新种群的个体编号;参数：unsignedint*parent1,unsignedint*parent2分别为两个父代染色体指针，指针指向父代个体的染色体，返回值：交叉是否成功;流程图：见图9。图9、函数crossover的流程图(9)、intmutation(unsignedintalleles)功

20、能：根据变异概率进行变异操作；参数：unsignedintalleles是染色体上的基因型，在这里就是0或1的取值;返回值：变异后的基因型；流程图：见图10。(10)、voidgeneration()功能：综合选择、交叉、变异等操作，生成新的种群;参数：无；返回值：无；流程图：见图11。图11、函数generation的流程图(11)、voidmain()功能：遗传算法的主函数；参数：无；返回值：无；流程图：见图11。调用read_infor,读入背面言息70,66,50,55,25,32,22,60,30,32,28,30,22,50,30,65,20,25,30,10,10,4,4,2,1

21、180,165,162,160,158,118,115,110,105,101,90,88,82,80,77,66,65,63,60,58,10,8,5,3,1七、成果说明1、程序开发环境开发环境：VisualC+6.0（把Fortran程序改为VC）操作系统：Windows2003Professional2、程序性能对比运行时间与加速比（如表1所示）进程数p（个）124运行时间t（秒）129s78s38s加速比s1.653.38表1、运行时间与加速比3、程序运行结果:实例数据：假设物体的重量Weight、物体的收益Profit和背包的容量Contain分别为:Weight=80,82,85,

22、70,72,50,55,40,48,50,40,38,35,32,25,45,30,60,50,20,20,25,15,10,10,Profit=220,208,198,192,180,155,130,125,122,120,100,100,98,96,95,75,73,72,70,69,56,50,30,20,15,Contain=1000,如何选择哪些物品装入该背包可使得在背包的容量约束限制之内所装物品的总价值最大？传统的算法（动态规划、递归回溯法和贪心算法所得结果：总价值为3077，总重量为999。2001年张铃，张钱教授在计算机学报上发表的佳点集遗传算法所得结果总价值为3103,总重量

23、为1000。我们算法所得结果：总价值为3103,总重量为1000c我们所求得最优解的个体分配情况为：11010101111011011011011111110100001010011000001000算法最大迭代次数总价值为总重量为传统的算法4003077999佳点集算法7031031000遗传算法7531031000八、收获、体会和课题展望在本课题中，我们研究了如何用遗传算法求解组合优化问题中的背包问题。我们可以看出在求解背包问题上显示了超出想象、良好的搜索能力，它具有收敛快、搜索速度快的特点，在试验中取得了比动态规划、递归回溯法和贪心法等更好的求解效果。然而在一般情况下，使用基本遗传算法解

24、决背包问题时，得到问题的近似解也不能满足逼近最优解的要求。如何改进基本遗传算法使它所求得的解逼近最优解，成为我们当前亟待解决的问题，也是我们将来的课题中所要研究的重要问题。/knapsack.cpp:Definestheentrypointfortheconsoleapplication./#include"stda仅.h”#include<AfXWin.h>#include<stdlib.h>#include<math.h>#include<time.h>#include<conio.h>#include<stdio

25、.h>/重要常量参数# definepopsize200/种群的规模# definepc0.618杂交概率# definepm0.03变异概率# definelchrom50染色体长度# definemaxgen1000/最大进化代数structpopulation(unsignedintchromlchrom;染色体doubleweight;背包重量doublefitness;/适应度unsignedintparent1,parent2,cross;/双亲、交叉点;新生代种群、父代种群structpopulationoldpoppopsize,newpoppopsize;背包问题中物体

26、重量、收益、背包容量intweightlchrom,profitlchrom,contain;/种群的总适应度、最小、最大、平均适应度doublesumfitness,minfitness,maxfitness,avgfitness;计算适应度时使用的惩罚函数系数doublealpha;/一个种群中最大和最小适应度的个体intminpop,maxpop;/*读入背包信息，并且计算惩罚函数系数*/voidread_infor()(FILE*fp;intj;/获取背包问题信息文件if(fp=fopen("knapsack.txt","r")尸NULL)(/读

27、取文件失败AfxMessageBox("Thefileisnotfound",MB_OK,NULL);return;读入物体收益信息for(j=0;j<lchrom;j+)(fscanf(fp,"%d",&profitj);读入物体重量信息for(j=0;j<lchrom;j+)fscanf(fp,"%d",&weightj);)读入背包容量fscanf(fp,"%d",&contain);fclose(fp);)根据计算的个体重量，判断此个体是否该留在群体中doublecal_

28、weight(unsignedint*chr)(intj;doublepop_weight;/背包重量pop_weight=0;for(j=0;j<lchrom;j+)(pop_weight=pop_weight+(*chr)*weightj;chr+;)returnpop_weight;)/*种群中个体适应度计算*/doublecal_fit(unsignedint*chr)(intj;doublepop_profit;/适应度pop_profit=0;/pop_weight=0;for(j=0;j<lchrom;j+)(pop_profit=pop_profit+(*chr)*

29、profitj;/pop_weight=pop_weight+(*chr)*weightj;chr+;)returnpop_profit;/*群体适应度的最大最小值以及其他信息*/voidstatistics(structpopulation*pop)(inti;doubletmp_fit;sumfitness=pop0.fitness;minfitness=pop0.fitness;minpop=0;maxfitness=pop0.fitness;maxpop=0;for(i=1;i<popsize;i+)(/计算种群的总适应度sumfitness=sumfitness+popi.fi

30、tness;tmp_fit=popi.fitness;选择种群中最大适应度的个体if(tmp_fit>maxfitness)&&(int)(tmp_fit*10)%10=0)(maxfitness=popi.fitness;maxpop=i;选择种群中最小适应度的个体if(tmp_fit<minfitness)(minfitness=popi.fitness;minpop=i;计算平均适应度avgfitness=sumfitness/(float)popsize;/printf("nthemaxpop=%d;",maxpop);/printf(&

31、quot;ntheminpop=%d;",minpop);/printf("nthesumfitness=%fn",sumfitness);报告种群信息voidreport(structpopulation*pop,intgen)(intj;intpop_weight=0;printf("thegenerationis%d.n",gen);/输出种群的代数输出种群中最大适应度个体的染色体信息printf("Thepopulation'schromis:n");for(j=0;j<lchrom;j+)if(j%5

32、=0)printf("");printf("%1d",popmaxpop.chromj);输出群体中最大适应度printf("nThepopulation'smaxfitnessis%d.",(int)popmaxpop.fitness);printf("nTheknapsackweightis%d.nn",(int)popmaxpop.weight);/*生成初始种群*/voidinitpop()inti,j,ispop;doubletmpWeight;/变量用于判断是否为满足条件的个体ispop=fal

33、se;/生成popsize个种群个体for(i=0;i<popsize;i+)while(!ispop)for(j=0;j<lchrom;j+)oldpopi.chromj=rand()%2;随机生成个体的染色体oldpopi.parent1=0;/双亲oldpopi.parent2=0;oldpopi.cross=0;交叉点选择重量小于背包容量的个体，即满足条件tmpWeight=cal_weight(oldpopi.chrom);if(tmpWeight<=contain)oldpopi.fitness=cal_fit(oldpopi.chrom);oldpopi.wei

34、ght=tmpWeight;oldpopi.parent1=0;oldpopi.parent2=0;oldpopi.cross=0;ispop=true;)此个体可以加入到种群中ispop=false;)/*遗传操作*/概率选择试验intexecise(doubleprobability)(doublepp;如果生成随机数大于相应的概率则返回真，否则试验不成功pp=(double)(rand()%20001/20000.0);if(pp<=probability)return1;return0;)/选择进行交叉操作的个体intselection(intpop)(doublewheel_p

35、os,rand_Number,partsum;intparent;赌轮法选择rand_Number=(rand()%2001)/2000.0;wheel_pos=rand_Number*sumfitness;赌轮大小partsum=0;parent=0;dopartsum=partsum+oldpopparent.fitness;parent=parent+1;while(partsum<wheel_pos&&parent<popsize);returnparent-1;/*交叉操作*/intcrossover(unsignedint*parent1,unsigne

36、dint*parent2,inti)intj,cross_pos;if(execise(pc)(生成交叉位置0,1,.(lchrom-2)cross_pos=rand()%(lchrom-1);elsecross_pos=lchrom-1;for(j=0;j<=cross_pos;j+)(保留复制；/包括在概率选择不成功时，父体完全保留newpopi.chromj=parent1j;for(j=cross_pos+1;j<=(lchrom-1);j+)(/从交叉点开始交叉newpopi.chromj=parent2j;记录交叉位置newpopi.cross=cross_pos;re

37、turn1;/*变异操作*/intmutation(unsignedintalleles)(if(execise(pm)(if(alleles)alleles=0;elsealleles=1;返回变异值，或者返回原值returnalleles;/*群体更新*/voidgeneration()(unsignedinti,j,mate1,mate2;doubletmpWeight;intispop;/记录是否是符合条件的个体i=0;while(i<popsize)(ispop=false;while(!ispop)(/选择mate1=selection(i);mate2=selection(i+1);/交叉crosso