遗传算法求解背包问题

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

3、 ,并记为v (0) = ( v1 (0) , , vchN (0) ) .1. 3 计算各个染色体的适值1. 4 置k = 0步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 检验该染色体的可

4、行性,若可行则作为变异的结果;如不可行,重复3. 2 直至该染色体可行. 3. 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)

5、 , v2 ( k + 1) , , vM ( k + 1) .步4 终止检验如果达到最大进化代数maxgen 则终止演化,否则置k : = k + 1 ,转步2.4、程序流程图程序流程图5、程序代码1）主程序代码：KnapsacksProblem.cpp文件#include "GAonKP.h"#include <iostream>using namespace std;void main()FILE* fp;CGAonKP gakp;int scale; /种群规模double MaxWeight; /背包允许最大财宝质量double pc; /杂交概率do

6、uble pm; /变异概率int maxgen; /最大进化代数char filename256;cout<<"遗传算法解决背包问题程序使用说明："<<endl;cout<<"1、该背包问题采用遗传算法"<<endl;cout<<"2、-1编码的方法，其中代表选中所对应的物品，代表不选中该物品"<<endl;cout<<"3、背包允许最带重量，种群规模（解空间大小），"cout<<"杂交概率，变异概率，最大进

7、化代数需自己给"cout<<"定，程序会提示输入"<<endl;cout<<"4、程序提供一个输入示例"<<endl;cout<<"5、输入文件可加单行或多行注释"<<endl;cout<<"例如：#添加单行注释内容#"<<endl;cout<<"例如：#添加多行注释内容"<<endl;cout<<" 添加多行注释内容#"<<

8、;endl;cout<<"6、输入文件头位置需指定物品个数为int型数据。物品重量，和物品价值为double型"<<endl;cout<<"7、程序运行结果会输出到output.txt文件中"<<endl;cout<<endl;cout<<endl;cout<<"如果你想使用示例文件进行演示请输入Y"<<endl;cout<<"如果你想使用示例文件进行演示请输入N"<<endl;cin>&g

9、t;filename;if (filename0='Y')if(!(fp=fopen("example.txt","r")cout<<"请确认example.txt是否背删除了！"<<endl;cout<<"演示文件中example.txt的输入参数："<<endl;cout<<"背包允许最带重量："<<endl;cout<<"种群规模："<<endl;cout&l

10、t;<"杂交概率：.5"<<endl;cout<<"变异概率：.1"<<endl;cout<<"最大进化代数："<<endl;gakp.GetSolute(100,0.5,0.2,30,50,fp);fclose(fp);else if (filename0='N')while (1)cout<<"请输入要读取的文件名（注意扩展名也要输入）："<<endl;cin>>filename;if(!(fp

11、=fopen(filename,"r")/最后要修改一下cout<<"请确认该文件名所对应的输入文件是否存在！"<<endl;else break;cout<<"请输入背包允许最带重量："<<endl;cin>>MaxWeight;cout<<"请输入种群规模："<<endl;cin>>scale;cout<<"请输入杂交概率："<<endl;cin>>pc;cou

12、t<<"请输入变异概率："<<endl;cin>>pm;cout<<"请输入最大进化代数："<<endl;cin>>maxgen;gakp.GetSolute(MaxWeight,pc,pm,scale,maxgen,fp);fclose(fp);elsecout<<"请确认你输入正确性！"<<endl;exit(0);cout<<"请输入任意内容结束程序运行"<<endl;cin>>

13、filename;2）保存数据矩阵类SaveMatrixArray代码Matrix.h文件#ifndef MATRIX_H_H#define MATRIX_H_H#define MATRIX_DATE_TYPE intclass CGAonKP;class SaveMatrixArraylong n,m;MATRIX_DATE_TYPE* pMatrix;void ReleaseMemory();public:SaveMatrixArray();SaveMatrixArray(long N,long M);SaveMatrixArray();MATRIX_DATE_TYPE* GetPMatr

14、ix();void ObtainMemory(long N,long M);long GetRow();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;i<n;i+)pMatrixi=ne

15、w MATRIX_DATE_TYPEm;SaveMatrixArray:SaveMatrixArray()ReleaseMemory();void SaveMatrixArray:ReleaseMemory()if (n!=0)for (int i=0;i<n;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

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

17、nclude <stdio.h>#ifndef GAONKP_H_H#define GAONKP_H_Hclass CGAonKPpublic:double (*Element)2; /财宝存储double* adaptive_value;/适应值double* Wheel; /轮盘数组int scale; /种群规模double MaxWeight; /背包允许最大财宝质量double pc; /杂交概率double pm; /变异概率int chN; /染色体长度int maxgen; /最大进化代数SaveMatrixArray x_m2;/遗传运算中的解矩阵int inde

18、x;int nindex;double EndWeight;double 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）

19、上均匀分布的n个浮点型随机数*/double RandomDist(int a, int 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 <time.h>#include <math.h>#include <iostream>#include <stdio.h>using

20、 namespace std;CGAonKP:CGAonKP()index=0;nindex=1;EndValue=0;EndWeight=0;CGAonKP:CGAonKP()delete Element;Element=0;delete adaptive_value;delete Wheel;delete Endx;Endx=0;Wheel=0;adaptive_value=0;long CGAonKP:ReadInt(FILE* in)char dum, dummy128;for(;)fscanf(in,"%s", dummy);if(dummy0='#

21、9; && strlen(dummy)>1 && dummystrlen(dummy)-1='#') /单行#-#else if(dummy0='#') dofscanf(in,"%c", &dum);/多行连接#-/-# while(dum!='#');else return atoi(dummy); /读到数据将其转化为型数存储 double CGAonKP:ReadDouble(FILE* in)char dum, dummy128;for(;)fscanf(in,"

22、;%s", dummy);if(dummy0='#' && strlen(dummy)>1 && dummystrlen(dummy)-1='#') else if(dummy0='#') dofscanf(in,"%c", &dum); while(dum!='#');else return atof(dummy); /atof是什么函数/转化为什么型的数是double还是float型数据break; double CGAonKP:GetSum(int

23、*che)double sum=0;for (int i=0;i<chN;i+)if (chei)sum+=Elementi0;return sum;double CGAonKP:GetAdaptiveValue(int *che)double sum=0;for (int i=0;i<chN;i+)if (chei)sum+=Elementi1;return sum;void CGAonKP:GetAdaVector()for (int i=0;i<scale;i+)adaptive_valuei=GetAdaptiveValue(x_mindex.pMatrixi);if

24、 (adaptive_valuei>EndValue)EndValue=adaptive_valuei;for (int j=0;j<chN;j+)Endxj=x_mindex.pMatrixij;EndWeight=GetSum(x_mindex.pMatrixi);void CGAonKP:GetWheel()double sum=0;int i;for (i=0;i<scale;i+)sum+=adaptive_valuei;for (i=0;i<scale;i+)Wheeli=adaptive_valuei/sum;for (i=1;i<scale;i+)

25、Wheeli+=Wheeli-1;void CGAonKP:SelectV()double temp;int i,j;int* h_v=new intscale;for (i=0;i<scale;i+)temp=RandomDist(0,1);if (temp<=Wheel0)h_vi=0;elsefor (j=1;j<scale;j+)if (temp<=Wheelj&&temp>Wheelj-1)h_vi=j;break;for (i=0;i<scale;i+)for (j=0;j<chN;j+)x_mnindex.pMatrixi

26、j=x_mindex.pMatrixh_vij;delete h_v;void CGAonKP:HybriVariat()int tempi,tempj;int temp;int i,j;for (i=0;i<scale;i+)if (RandomDist(0,1)<pc)dotempi=rand()%chN;tempj=rand()%chN;temp=x_mnindex.pMatrixitempi;x_mnindex.pMatrixitempi=x_mnindex.pMatrixitempj;x_mnindex.pMatrixitempj=temp;while (!JudgeSa

27、tis(x_mnindex.pMatrixi);if (RandomDist(0,1)<pm)dotempi=rand()%chN;temp=rand()%2;x_mnindex.pMatrixitempi=temp;while (!JudgeSatis(x_mnindex.pMatrixi);bool CGAonKP:JudgeSatis(int* che)if (MaxWeight<GetSum(che)return false;return true;void CGAonKP:Initial(FILE* fp)int i,j;chN=ReadInt(fp);Wheel=new

28、 doublescale;Element=new doublechN2;Endx=new intchN;for (i=0;i<chN;i+)Elementi0=ReadDouble(fp);Elementi1=ReadDouble(fp);for (i=0;i<chN;i+)if (MaxWeight>=Elementi0) break;if (i=chN)cout<<"对不起任何备选物品中质量都大于您输入的背包允许质量！"<<endl;exit(0);adaptive_value=new doublescale;x_mindex.

29、ObtainMemory(scale,chN);x_mnindex.ObtainMemory(scale,chN);for (i=0;i<scale;i+)dofor (j=0;j<chN;j+)x_mindex.pMatrixij=rand()%2;while (!JudgeSatis(x_mindex.pMatrixi);double CGAonKP:RandomDist(int a, int b)if(a=b)cout<<"illegal 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 种群规模 */* max_gen 最大进化代数 */*/void CGAonKP:GetSolute(double max_weig