一、背包问题描述
背包问题是著名的NP 完备类困难问题,对这个问题的求解前人已经研究出了不少的经典的方法,对该问题确实能得到很好的结果。近年来蓬勃发展起来的遗传算法已被广泛地应用于优化领域,其全局最优性、可并行性、高效性在函数优化中得到了广泛地应用遗传算法克服了传统优化方法的缺点,借助了大自然的演化过程,是多线索而非单线索的全局优化方法,采用的是种群和随机搜索机制. 本程序将遗传算法应用于背包问题。
二、实验程序
1、编程语言：C++
2、开发环境：Microsoft Visual Studio 2005
3、程序整体流程：
步1 初始化过程
1. 1 确定种群规模scale、杂交概率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
步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 直至该染色体可行.
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) , v2 ( k + 1) , ⋯, vM ( k + 1) } .
步4 终止检验
如果达到最大进化代数maxgen 则终止演化,否则置k : = k + 1 ,转步2.
4、程序流程图
程序流程图
5、程序代码
1）主程序代码：
KnapsacksProblem.cpp文件
#include "GAonKP.h"
#include using namespace std; void main() { FILE* fp; CGAonKP gakp; int scale; //种群规模 double MaxWeight; //背包允许最大财宝质量 double pc; //杂交概率 double pm; //变异概率 int maxgen; //最大进化代数 char filename[256]; cout<<"遗传算法解决背包问题程序使用说明："< cout<<"杂交概率，变异概率，最大进化代数需自己给"; cout<<"定，程序会提示输入"< cout< if (filename[0]=='Y') { if(!(fp=fopen("example.txt { cout<<"请确认example.txt是否背删除了！"< cout<<"演示文件中example.txt的输入参数："< fclose(fp); } else if (filename[0]=='N') { while (1) { cout<<"请输入要读取的文件名（注意扩展名也要输入）："< if(!(fp=fopen(filename,"r")))//最后要修改一下 { cout<<"请确认该文件名所对应的输入文件是否存在！"< else break; } cout<<"请输入背包允许最带重量："< cout<<"请输入种群规模："< cout<<"请输入杂交概率："< cout<<"请输入变异概率："< cout<<"请输入最大进化代数："< gakp.GetSolute(MaxWeight,pc,pm,scale,maxgen,fp); fclose(fp); } else { cout<<"请确认你输入正确性！"< } cout<<"请输入任意内容结束程序运行"< } 2）保存数据矩阵类SaveMatrixArray代码 Matrix.h文件 #ifndef 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(); long GetCol(); friend CGAonKP; }; #endif Matrix.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 pMatrix[i]=new MATRIX_DATE_TYPE[m]; } } SaveMatrixArray::~SaveMatrixArray() { ReleaseMemory(); } void SaveMatrixArray::ReleaseMemory() { if (n!=0) { for (int i=0;i delete[] pMatrix[i]; pMatrix[i]=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 m; } /*****************************************************************************/ /* 注意该函数调用后将清除以前内容，重新分配内存空间，如果没有分配则按指定分配*/ /*****************************************************************************/ void SaveMatrixArray::ObtainMemory(long N,long M) { ReleaseMemory(); n=N;m=M; pMatrix=new MATRIX_DATE_TYPE*[n]; for (int i=0;i pMatrix[i]=new MATRIX_DATE_TYPE[m]; } } 3）遗传算法解决背包问题类CGAonKP代码 GAonKP.h文件 #include "Matrix.h" #include #ifndef GAONKP_H_H #define GAONKP_H_H class CGAonKP { public: double (*Element)[2]; //财宝存储 double* adaptive_value;//适应值 double* Wheel; //轮盘数组 int scale; //种群规模 double MaxWeight; //背包允许最大财宝质量 double pc; //杂交概率 double pm; //变异概率 int chN; //染色体长度 int maxgen; //最大进化代数 SaveMatrixArray x_m[2];//遗传运算中的解矩阵 int index; 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）上均匀分布的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); }; #endif GAonKP.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; delete[] adaptive_value; delete[] Wheel; delete[] Endx; Endx=0; Wheel=0; adaptive_value=0; } long CGAonKP::ReadInt(FILE* in) { char dum, dummy[128]; for(;;) { fscanf(in,"%s", dummy); if(dummy[0]=='#' && strlen(dummy)>1 && dummy[strlen(dummy)-1]=='#') {}//单行#----# else if(dummy[0]=='#') { do { fscanf(in,"%c", &dum);//多行连接#----- //-----# } while(dum!='#'); } else { return atoi(dummy); //读到数据将其转化为ｉｎｔ型数存储 } } } double CGAonKP::ReadDouble(FILE* in) { char dum, dummy[128]; for(;;) { fscanf(in,"%s", dummy); if(dummy[0]=='#' && strlen(dummy)>1 && dummy[strlen(dummy)-1]=='#') {} else if(dummy[0]=='#') { do { fscanf(in,"%c", &dum); } while(dum!='#'); } else { return atof(dummy); //atof是什么函数/转化为什么型的数是double还是float型数据 break; } } } double CGAonKP::GetSum(int *che) { double sum=0; for (int i=0;i if (che[i]) { sum+=Element[i][0]; } } return sum; } double CGAonKP::GetAdaptiveValue(int *che) { double sum=0; for (int i=0;i if (che[i]) { sum+=Element[i][1]; } } return sum; } void CGAonKP::GetAdaVector() { for (int i=0;i adaptive_value[i]=GetAdaptiveValue(x_m[index].pMatrix[i]); if (adaptive_value[i]>EndValue) { EndValue=adaptive_value[i]; for (int j=0;j Endx[j]=x_m[index].pMatrix[i][j]; EndWeight=GetSum(x_m[index].pMatrix[i]); } } } } void CGAonKP::GetWheel() { double sum=0; int i; for (i=0;i sum+=adaptive_value[i]; } for (i=0;i Wheel[i]=adaptive_value[i]/sum; } for (i=1;i Wheel[i]+=Wheel[i-1]; } } void CGAonKP::SelectV() { double temp; int i,j; int* h_v=new int[scale]; for (i=0;i temp=RandomDist(0,1); if (temp<=Wheel[0]) { h_v[i]=0; } else { for (j=1;j if (temp<=Wheel[j]&&temp>Wheel[j-1]) { h_v[i]=j; break; } } } } for (i=0;i for (j=0;j x_m[nindex].pMatrix[i][j]=x_m[index].pMatrix[h_v[i]][j]; } } delete[] h_v; } void CGAonKP::HybriVariat() { int tempi,tempj; int temp; int i,j; for (i=0;i if (RandomDist(0,1) do { tempi=rand()%chN; tempj=rand()%chN; temp=x_m[nindex].pMatrix[i][tempi]; x_m[nindex].pMatrix[i][tempi]=x_m[nindex].pMatrix[i][tempj]; x_m[nindex].pMatrix[i][tempj]=temp; }while (!JudgeSatis(x_m[nindex].pMatrix[i])); if (RandomDist(0,1) do { tempi=rand()%chN; temp=rand()%2; x_m[nindex].pMatrix[i][tempi]=temp; }while (!JudgeSatis(x_m[nindex].pMatrix[i])); } } } } bool CGAonKP::JudgeSatis(int* che) { if (MaxWeight return false; } return true; } void CGAonKP::Initial(FILE* fp) { int i,j; chN=ReadInt(fp); Wheel=new double[scale]; Element=new double[chN][2]; Endx=new int[chN]; for (i=0;i Element[i][0]=ReadDouble(fp); Element[i][1]=ReadDouble(fp); } for (i=0;i if (i==chN) { cout<<"对不起任何备选物品中质量都大于您输入的背包允许质量！"< } adaptive_value=new double[scale]; x_m[index].ObtainMemory(scale,chN); x_m[nindex].ObtainMemory(scale,chN); for (i=0;i do { for (j=0;j x_m[index].pMatrix[i][j]=rand()%2; } }while (!JudgeSatis(x_m[index].pMatrix[i])); } } double CGAonKP::RandomDist(int a, int b) { if(a==b){cout<<"illegal Argument!"< } /********************************************************************************/ /* 函数名：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_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;k GetWheel(); SelectV(); HybriVariat(); if (index) { index=0; nindex=1; } else { index=1; nindex=0; } GetAdaVector(); } int i; cout< cout< cout< FILE* fpout=fopen("output.txt fprintf(fpout,"程序运行结果输出\\n"); fprintf(fpout,"最后结果价值总量：\\n"); fprintf(fpout,"%g\\n",EndValue); fprintf(fpout,"最后结果质量：\\n"); fprintf(fpout,"%g\\n",EndWeight); fprintf(fpout,"最后结果所选个体：\\n"); for (i=0;i fprintf(fpout,"%d ",Endx[i]); } fprintf(fpout,"\\n"); fclose(fpout); }下载本文
