2022年遗传算法求解背包问题 2.pdf

《2022年遗传算法求解背包问题 2.pdf》由会员分享，可在线阅读，更多相关《2022年遗传算法求解背包问题 2.pdf（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 遗传算法求解背包问题程序实现一、背包问题描述背包问题是著名的NP 完备类困难问题,对这个问题的求解前人已经研究出了不少的经典的方法,对该问题确实能得到很好的结果。近年来蓬勃发展起来的遗传算法已被广泛地应用于优化领域,其全局最优性、可并行性、高效性在函数优化中得到了广泛地应用遗传算法克服了传统优化方法的缺点,借助了大自然的演化过程,是多线索而非单线索的全局优化方法,采用的是种群和随机搜索机制.本程序将遗传算法应用于背包问题。二、实验程序1、编程语言：C+2、开发环境：Microsoft Visual Studio 2005 3、程序整体流程：步1初始化过程1.1确定种群规模 scale、杂交

2、概率 pc、变异概率 pm、染色体长度chN 及最大进化代数maxgen。1.2取x1(0)=u(0,1),x2(0)=u(0,1),xchN (0)=u(0,1),其中函数 u(0,1)表示随机地产生数 0 或1,则 x(0)=(x1(0),x2(0),?,xN(0).若不满足约束条件,则拒绝接受.由(1.2)重新产生一个新的染色体;如果产生的染色体可行,则接受它作为种群的一名成员,经过有限次抽样后,得到 scale个可行的染色体xj(0),j=1,2,?,M,设xj(0)的染色体编码为vj(0),并记为 v(0)=(v1(0),?,vchN(0).1.3计算各个染色体的适值1.4 置k=0

3、 步2选择操作2.1采用转轮法选择下一代。.步3杂交变异操作3.1 事先定义杂交操作的概率pc,为确定杂交操作的父代,从j=1 到M 重复以下过程:从0,1 中产生随机数r,若 r pc ,则选择 cj (k)作为一个父代.3.2 产生两个 1,N 上的随机整数i、j,变异的结果为染色体vj (k)的第 i 位基因的值变为其第 j 位基因的值,同样将染色体的vj(k)第j 位基因的值变为其第i 位基因的值.3.3 检验该染色体的可行性,若可行则作为变异的结果;如不可行,重复 3.2 直至该染色体可名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 12 页 -2 行.3.4 事先定义

4、变异概率pm,对经过杂交操作的中间个体进行变异操作:,如果 r pm,则选择vi (k)作为变异的父代.3.5 产生一个 1,N 上的随机整数i,及随机地产生数0 或1,记为 b,变异的结果为染色体vi(k)的第 i 位基因的值变为b.3.6 检验该染色体的可行性,若可行则作为变异的结果:如不可行,重复 3.5 直至该染色体可行.3.7 计算新个体的适应值,并把它们同时放回,和步2 选择操作中剩余的个体一起构成新一代种群 v(k+1)=v1(k+1),v2(k+1),?,vM(k+1).步4 终止检验如果达到最大进化代数maxgen 则终止演化,否则置 k:=k+1,转步2.4、程序流程图名师

5、资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 12 页 -3 开始手动输入备选物体文件读取文档初始化形成初始种群转轮法选择个体杂交变异操作形成新的种群计算适值结束输出结果文件output.txt输出结果打到最大繁殖代数？YN程序流程图5、程序代码1）主程序代码：KnapsacksProblem.cpp文件#include GAonKP.h#include using namespace std;void main()FILE*fp;CGAonKP gakp;int scale;/种群规模double MaxWeight;/背包允许最大财宝质量double pc;/杂交概率doubl

6、e pm;/变异概率名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 12 页 -4 int maxgen;/最大进化代数char filename256;cout 遗传算法解决背包问题程序使用说明：endl;cout1、该背包问题采用遗传算法endl;cout2、-1编码的方法，其中代表选中所对应的物品，代表不选中该物品endl;cout3、背包允许最带重量，种群规模（解空间大小），;cout 杂交概率，变异概率，最大进化代数需自己给;cout 定，程序会提示输入endl;cout4、程序提供一个输入示例endl;cout5、输入文件可加单行或多行注释endl;cout 例如：#

7、添加单行注释内容#endl;cout 例如：#添加多行注释内容endl;cout 添加多行注释内容#endl;cout6、输入文件头位置需指定物品个数为int 型数据。物品重量，和物品价值为double 型endl;cout7、程序运行结果会输出到output.txt文件中 endl;coutendl;coutendl;cout 如果你想使用示例文件进行演示请输入Yendl;cout 如果你想使用示例文件进行演示请输入Nfilename;if(filename0=Y)if(!(fp=fopen(example.txt,r)cout 请确认 example.txt是否背删除了！endl;cout

8、 演示文件中 example.txt的输入参数：endl;cout 背包允许最带重量：endl;cout 种群规模：endl;cout 杂交概率：.5endl;cout 变异概率：.1endl;cout 最大进化代数：endl;gakp.GetSolute(100,0.5,0.2,30,50,fp);fclose(fp);else if(filename0=N)while(1)cout 请输入要读取的文件名（注意扩展名也要输入）：filename;if(!(fp=fopen(filename,r)/最后要修改一下 cout 请确认该文件名所对应的输入文件是否存在！endl;else break

9、;cout 请输入背包允许最带重量：MaxWeight;cout 请输入种群规模：scale;cout 请输入杂交概率：pc;cout 请输入变异概率：pm;名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 12 页 -5 cout 请输入最大进化代数：maxgen;gakp.GetSolute(MaxWeight,pc,pm,scale,maxgen,fp);fclose(fp);else cout 请确认你输入正确性！endl;exit(0);cout 请输入任意内容结束程序运行filename;2）保存数据矩阵类SaveMatrixArray代码Matrix.h 文件#ifn

10、def MATRIX_H_H#define MATRIX_H_H#define MATRIX_DATE_TYPE int class CGAonKP;class SaveMatrixArray long n,m;MATRIX_DATE_TYPE*pMatrix;void ReleaseMemory();public:SaveMatrixArray();SaveMatrixArray(long N,long M);SaveMatrixArray();MATRIX_DATE_TYPE*GetPMatrix();void ObtainMemory(long N,long M);long GetRow

11、();long GetCol();friend CGAonKP;#endifMatrix.cpp 文件#include Matrix.h SaveMatrixArray:SaveMatrixArray()n=0;m=0;pMatrix=0;SaveMatrixArray:SaveMatrixArray(long N,long M):n(N),m(M)pMatrix=new MATRIX_DATE_TYPE*n;for(int i=0;in;i+)pMatrixi=new MATRIX_DATE_TYPEm;SaveMatrixArray:SaveMatrixArray()ReleaseMemo

12、ry();void SaveMatrixArray:ReleaseMemory()名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 12 页 -6 if(n!=0)for(int i=0;in;i+)delete pMatrixi;pMatrixi=0;delete pMatrix;pMatrix=0;n=0;m=0;MATRIX_DATE_TYPE*SaveMatrixArray:GetPMatrix()return pMatrix;long SaveMatrixArray:GetRow()return n;long SaveMatrixArray:GetCol()return

13、m;/*/*注意该函数调用后将清除以前内容，重新分配内存空间，如果没有分配则按指定分配*/*/void SaveMatrixArray:ObtainMemory(long N,long M)ReleaseMemory();n=N;m=M;pMatrix=new MATRIX_DATE_TYPE*n;for(int i=0;in;i+)pMatrixi=new MATRIX_DATE_TYPEm;3）遗传算法解决背包问题类CGAonKP 代码GAonKP.h 文件#include Matrix.h#include#ifndef GAONKP_H_H#define GAONKP_H_H class

14、 CGAonKP public:double(*Element)2;/财宝存储double*adaptive_value;/适应值double*Wheel;/轮盘数组int scale;/种群规模double MaxWeight;/背包允许最大财宝质量double pc;/杂交概率double pm;/变异概率int chN;/染色体长度名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 12 页 -7 int maxgen;/最大进化代数SaveMatrixArray x_m2;/遗传运算中的解矩阵int index;int nindex;double EndWeight;doub

15、le EndValue;int*Endx;void Initial(FILE*fp);void GetWheel();bool JudgeSatis(int*che);double GetSum(int*che);double GetAdaptiveValue(int*che);void GetAdaVector();long ReadInt(FILE*in);double ReadDouble(FILE*in);void SelectV();void HybriVariat();public:/*产生（a，b）上均匀分布的n个浮点型随机数*/double RandomDist(int a,i

16、nt b);CGAonKP();CGAonKP();void GetSolute(double max_weight,double PC,double PM,int SCALE,int max_gen,FILE*fp);#endifGAonKP.cpp 文件#include GAonKP.h#include#include#include#include using namespace std;CGAonKP:CGAonKP()index=0;nindex=1;EndValue=0;EndWeight=0;CGAonKP:CGAonKP()delete Element;Element=0;de

17、lete adaptive_value;delete Wheel;delete Endx;Endx=0;Wheel=0;adaptive_value=0;long CGAonKP:ReadInt(FILE*in)名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 12 页 -8 char dum,dummy128;for(;)fscanf(in,%s,dummy);if(dummy0=#&strlen(dummy)1&dummystrlen(dummy)-1=#)/单行#-#else if(dummy0=#)do fscanf(in,%c,&dum);/多行连接#-/-#while(

18、dum!=#);else return atoi(dummy);/读到数据将其转化为型数存储 double CGAonKP:ReadDouble(FILE*in)char dum,dummy128;for(;)fscanf(in,%s,dummy);if(dummy0=#&strlen(dummy)1&dummystrlen(dummy)-1=#)else if(dummy0=#)do fscanf(in,%c,&dum);while(dum!=#);else return atof(dummy);/atof是什么函数/转化为什么型的数是double 还是 float型数据break;doub

19、le CGAonKP:GetSum(int*che)double sum=0;for(int i=0;ichN;i+)if(chei)sum+=Elementi0;return sum;double CGAonKP:GetAdaptiveValue(int*che)double sum=0;for(int i=0;ichN;i+)名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 12 页 -9 if(chei)sum+=Elementi1;return sum;void CGAonKP:GetAdaVector()for(int i=0;iEndValue)EndValue=ada

20、ptive_valuei;for(int j=0;jchN;j+)Endxj=x_mindex.pMatrixij;EndWeight=GetSum(x_mindex.pMatrixi);void CGAonKP:GetWheel()double sum=0;int i;for(i=0;iscale;i+)sum+=adaptive_valuei;for(i=0;iscale;i+)Wheeli=adaptive_valuei/sum;for(i=1;iscale;i+)Wheeli+=Wheeli-1;void CGAonKP:SelectV()double temp;int i,j;int

21、*h_v=new intscale;for(i=0;iscale;i+)temp=RandomDist(0,1);if(temp=Wheel0)h_vi=0;else for(j=1;jscale;j+)if(tempWheelj-1)名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 12 页 -10 h_vi=j;break;for(i=0;iscale;i+)for(j=0;jchN;j+)x_mnindex.pMatrixij=x_mindex.pMatrixh_vij;delete h_v;void CGAonKP:HybriVariat()int tempi,tempj;

22、int temp;int i,j;for(i=0;iscale;i+)if(RandomDist(0,1)pc)do tempi=rand()%chN;tempj=rand()%chN;temp=x_mnindex.pMatrixitempi;x_mnindex.pMatrixitempi=x_mnindex.pMatrixitempj;x_mnindex.pMatrixitempj=temp;while(!JudgeSatis(x_mnindex.pMatrixi);if(RandomDist(0,1)pm)do tempi=rand()%chN;temp=rand()%2;x_mninde

23、x.pMatrixitempi=temp;while(!JudgeSatis(x_mnindex.pMatrixi);bool CGAonKP:JudgeSatis(int*che)if(MaxWeightGetSum(che)return false;return true;void CGAonKP:Initial(FILE*fp)名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 12 页 -11 int i,j;chN=ReadInt(fp);Wheel=new doublescale;Element=new doublechN2;Endx=new intchN;for(i=

24、0;ichN;i+)Elementi0=ReadDouble(fp);Elementi1=ReadDouble(fp);for(i=0;i=Elementi0)break;if(i=chN)cout 对不起任何备选物品中质量都大于您输入的背包允许质量！endl;exit(0);adaptive_value=new doublescale;x_mindex.ObtainMemory(scale,chN);x_mnindex.ObtainMemory(scale,chN);for(i=0;iscale;i+)do for(j=0;jchN;j+)x_mindex.pMatrixij=rand()%

25、2;while(!JudgeSatis(x_mindex.pMatrixi);double CGAonKP:RandomDist(int a,int b)if(a=b)coutillegal Argument!endl;exit(0);return(double)rand()/RAND_MAX*(b-a)+a);/*/*函数名：GetSolute(double max_weight,double PC,double PM,int chn,int max_gen)*/*参数：max_weight 背包允许最大财宝质量 */*PC 杂交概率 */*PM 变异概率 */*SCALE 种群规模 */*

26、max_gen 最大进化代数 */*/void CGAonKP:GetSolute(double max_weight,double PC,double PM,int SCALE,int max_gen,FILE*fp)MaxWeight=max_weight;pc=PC;pm=PM;scale=SCALE;maxgen=max_gen;srand(int)time(0);Initial(fp);GetAdaVector();for(int k=0;kmax_gen;k+)名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 12 页 -12 GetWheel();SelectV()

27、;HybriVariat();if(index)index=0;nindex=1;else index=1;nindex=0;GetAdaVector();int i;coutendlendl输出运算结果：endl;cout 最后结果价值总量：EndValueendl;cout 最后结果质量：EndWeightendl;cout 最后结果所选个体：endl;for(i=0;ichN;i+)coutEndxi ;coutendl;FILE*fpout=fopen(output.txt,w);fprintf(fpout,程序运行结果输出n);fprintf(fpout,最后结果价值总量：n);fprintf(fpout,%gn,EndValue);fprintf(fpout,最后结果质量：n);fprintf(fpout,%gn,EndWeight);fprintf(fpout,最后结果所选个体：n);for(i=0;ichN;i+)fprintf(fpout,%d,Endxi);fprintf(fpout,n);fclose(fpout);名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 12 页 -