遺傳算法求解背包問題

1、遺傳算法求解背包問題程序?qū)崿F(xiàn)一、背包問題描述背包問題是著名的NP 完備類困難問題,對這個(gè)問題的求解前人已經(jīng)研究出了不少的經(jīng)典的方法,對該問題確實(shí)能得到很好的結(jié)果。近年來蓬勃發(fā)展起來的遺傳算法已被廣泛地應(yīng)用于優(yōu)化領(lǐng)域,其全局最優(yōu)性、可并行性、高效性在函數(shù)優(yōu)化中得到了廣泛地應(yīng)用遺傳算法克服了傳統(tǒng)優(yōu)化方法的缺點(diǎn),借助了大自然的演化過程,是多線索而非單線索的全局優(yōu)化方法,采用的是種群和隨機(jī)搜索機(jī)制. 本程序?qū)⑦z傳算法應(yīng)用于背包問題。二、實(shí)驗(yàn)程序1、編程語言：C+2、開發(fā)環(huán)境：Microsoft Visual Studio 20053、程序整體流程：步1 初始化過程1. 1 確定種群規(guī)模scale、雜交

2、概率pc 、變異概率pm 、染色體長度chN 及最大進(jìn)化代數(shù)maxgen。1. 2 取x1(0) = u (0 ,1) , x2(0) = u (0 ,1) , , xchN(0) = u (0 ,1) ,其中函數(shù)u (0 ,1) 表示隨機(jī)地產(chǎn)生數(shù)0 或1 ,則x (0) = ( x1 (0) , x2 (0) , xN (0) ) .若不滿足約束條件,則拒絕接受. 由(1. 2) 重新產(chǎn)生一個(gè)新的染色體; 如果產(chǎn)生的染色體可行,則接受它作為種群的一名成員,經(jīng)過有限次抽樣后, 得到scale個(gè)可行的染色體xj (0) , j =1 ,2 , , M ,設(shè)xj (0) 的染色體編碼為vj (0)

3、 ,并記為v (0) = ( v1 (0) , , vchN (0) ) .1. 3 計(jì)算各個(gè)染色體的適值1. 4 置k = 0步2 選擇操作2. 1 采用轉(zhuǎn)輪法選擇下一代。.步3 雜交變異操作3. 1 事先定義雜交操作的概率pc ,為確定雜交操作的父代,從j = 1 到M 重復(fù)以下過程:從0 ,1 中產(chǎn)生隨機(jī)數(shù)r ,若r < pc ,則選擇cj( k) 作為一個(gè)父代.3. 2 產(chǎn)生兩個(gè)1 , N 上的隨機(jī)整數(shù)i 、j ,變異的結(jié)果為染色體vj( k) 的第i 位基因的值變?yōu)槠涞趈 位基因的值,同樣將染色體的vj( k) 第j 位基因的值變?yōu)槠涞趇 位基因的值.3. 3 檢驗(yàn)該染色體的可

4、行性,若可行則作為變異的結(jié)果;如不可行,重復(fù)3. 2 直至該染色體可行. 3. 4 事先定義變異概率pm ,對經(jīng)過雜交操作的中間個(gè)體進(jìn)行變異操作: ,如果r < pm ,則選擇vi( k) 作為變異的父代.3. 5 產(chǎn)生一個(gè)1 , N 上的隨機(jī)整數(shù)i ,及隨機(jī)地產(chǎn)生數(shù)0 或1 , 記為b , 變異的結(jié)果為染色體vi( k) 的第i 位基因的值變?yōu)閎.3. 6 檢驗(yàn)該染色體的可行性,若可行則作為變異的結(jié)果:如不可行,重復(fù)3. 5 直至該染色體可行. 3. 7 計(jì)算新個(gè)體的適應(yīng)值,并把它們同時(shí)放回,和步2 選擇操作中剩余的個(gè)體一起構(gòu)成新一代種群v ( k + 1) = v1 ( k + 1)

5、 , v2 ( k + 1) , , vM ( k + 1) .步4 終止檢驗(yàn)如果達(dá)到最大進(jìn)化代數(shù)maxgen 則終止演化,否則置k : = k + 1 ,轉(zhuǎn)步2.4、程序流程圖程序流程圖5、程序代碼1）主程序代碼：KnapsacksProblem.cpp文件#include "GAonKP.h"#include <iostream>using namespace std;void main()FILE* fp;CGAonKP gakp;int scale; /種群規(guī)模double MaxWeight; /背包允許最大財(cái)寶質(zhì)量double pc; /雜交概率do

6、uble pm; /變異概率int maxgen; /最大進(jìn)化代數(shù)char filename256;cout<<"遺傳算法解決背包問題程序使用說明："<<endl;cout<<"1、該背包問題采用遺傳算法"<<endl;cout<<"2、-1編碼的方法，其中代表選中所對應(yīng)的物品，代表不選中該物品"<<endl;cout<<"3、背包允許最帶重量，種群規(guī)模（解空間大?。?，"cout<<"雜交概率，變異概率，最大進(jìn)

7、化代數(shù)需自己給"cout<<"定，程序會(huì)提示輸入"<<endl;cout<<"4、程序提供一個(gè)輸入示例"<<endl;cout<<"5、輸入文件可加單行或多行注釋"<<endl;cout<<"例如：#添加單行注釋內(nèi)容#"<<endl;cout<<"例如：#添加多行注釋內(nèi)容"<<endl;cout<<" 添加多行注釋內(nèi)容#"<<

8、;endl;cout<<"6、輸入文件頭位置需指定物品個(gè)數(shù)為int型數(shù)據(jù)。物品重量，和物品價(jià)值為double型"<<endl;cout<<"7、程序運(yùn)行結(jié)果會(huì)輸出到output.txt文件中"<<endl;cout<<endl;cout<<endl;cout<<"如果你想使用示例文件進(jìn)行演示請輸入Y"<<endl;cout<<"如果你想使用示例文件進(jìn)行演示請輸入N"<<endl;cin>&g

9、t;filename;if (filename0='Y')if(!(fp=fopen("example.txt","r")cout<<"請確認(rèn)example.txt是否背刪除了！"<<endl;cout<<"演示文件中example.txt的輸入?yún)?shù)："<<endl;cout<<"背包允許最帶重量："<<endl;cout<<"種群規(guī)模："<<endl;cout&l

10、t;<"雜交概率：.5"<<endl;cout<<"變異概率：.1"<<endl;cout<<"最大進(jìn)化代數(shù)："<<endl;gakp.GetSolute(100,0.5,0.2,30,50,fp);fclose(fp);else if (filename0='N')while (1)cout<<"請輸入要讀取的文件名（注意擴(kuò)展名也要輸入）："<<endl;cin>>filename;if(!(fp

11、=fopen(filename,"r")/最后要修改一下cout<<"請確認(rèn)該文件名所對應(yīng)的輸入文件是否存在！"<<endl;else break;cout<<"請輸入背包允許最帶重量："<<endl;cin>>MaxWeight;cout<<"請輸入種群規(guī)模："<<endl;cin>>scale;cout<<"請輸入雜交概率："<<endl;cin>>pc;cou

12、t<<"請輸入變異概率："<<endl;cin>>pm;cout<<"請輸入最大進(jìn)化代數(shù)："<<endl;cin>>maxgen;gakp.GetSolute(MaxWeight,pc,pm,scale,maxgen,fp);fclose(fp);elsecout<<"請確認(rèn)你輸入正確性！"<<endl;exit(0);cout<<"請輸入任意內(nèi)容結(jié)束程序運(yùn)行"<<endl;cin>>

13、filename;2）保存數(shù)據(jù)矩陣類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;/*/* 注意該函數(shù)調(diào)用后將清除以前內(nèi)容，重新分配內(nèi)存空間，如果沒有分配則按指定分配*/*/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; /財(cái)寶存儲double* adaptive_value;/適應(yīng)值double* Wheel; /輪盤數(shù)組int scale; /種群規(guī)模double MaxWeight; /背包允許最大財(cái)寶質(zhì)量double pc; /雜交概率double pm; /變異概率int chN; /染色體長度int maxgen; /最大進(jìn)化代數(shù)SaveMatrixArray x_m2;/遺傳運(yùn)算中的解矩陣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:/*產(chǎn)生（a，b）

19、上均勻分布的n個(gè)浮點(diǎn)型隨機(jī)數(shù)*/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); /讀到數(shù)據(jù)將其轉(zhuǎn)化為型數(shù)存儲 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是什么函數(shù)/轉(zhuǎn)化為什么型的數(shù)是double還是float型數(shù)據(jù)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<<"對不起任何備選物品中質(zhì)量都大于您輸入的背包允許質(zhì)量！"<<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);/*/* 函數(shù)名：GetSolute(double max_weight,double PC,double PM,int chn,int max_gen)*/* 參數(shù)：max_weight 背包允許最大財(cái)寶質(zhì)量 */* PC 雜交概率 */* PM 變異概率 */* SCALE 種群規(guī)模 */* max_gen 最大進(jìn)化代數(shù) */*/void CGAonKP:GetSolute(double max_weig