遺傳算法解背包問題

1、遺傳算法解背包問題1、程序開發(fā)環(huán)境 開發(fā)環(huán)境：Visual C+6.0 (把Fortran程序改為VC) 操作系統(tǒng)：Windows 2003 Professional 2、程序性能對比 運行時間與加速比（如表1所示） 進程數(shù)p（個） 1 2 4 運行時間t（秒） 129s 78s 38s 加速比s 1.65 3.38 表1、運行時間與加速比 3、程序運行結(jié)果： 實例數(shù)據(jù)： 假設物體的重量Weight、物體的收益Profit和背包的容量Contain 分別為： Weight= 80，82，85，70，72， 70，66，50，55，25 ， 50，55，40，48，50， 32，22，60，30

2、，32 ， 40，38，35，32，25， 28，30，22，50，30 ， 45，30，60，50，20 ， 65，20，25，30，10 ， 20，25，15，10，10 ， 10，4， 4， 2， 1 Profit= 220，208，198，192，180， 180，165，162，160，158， 155，130，125，122，120 ， 118，115，110，105，101， 100，100，98， 96， 95， 90， 88， 82， 80， 77 ， 75， 73， 72， 70， 69， 66， 65， 63， 60， 58， 56， 50， 30， 20， 15， 10

3、， 8， 5， 3， 1 Contain=1000， 如何選擇哪些物品裝入該背包可使得在背包的容量約束限制之內(nèi)所裝物品的總價值最大? 傳統(tǒng)的算法（動態(tài)規(guī)劃、遞歸回溯法和貪心算法所得結(jié)果： 總價值為3077 , 總重量為999。 2001年張鈴，張鈸教授在計算機學報上發(fā)表的佳點集遺傳算法所得結(jié)果 總價值為3103, 總重量為1000。 我們算法所得結(jié)果： 總價值為3103, 總重量為1000。 我們所求得最優(yōu)解的個體分配情況為： 11010 10111 10110 11011 01111 11101 00001 01001 10000 01000 算法 最大迭代次數(shù) 總價值為 總重量為 傳統(tǒng)的算

4、法 400 3077 999 佳點集算法 70 3103 1000 遺傳算法 75 3103 1000 / knapsack.cpp : Defines the entry point for the console application. / #include "stdafx.h" #include <AfxWin.h> #include <stdlib.h> #include <math.h> #include <time.h> #include <conio.h> #include <stdio.h&

5、gt; / 重要常量參數(shù) #define popsize 200 /種群的規(guī)模 #define pc 0.618 /雜交概率 #define pm 0.03 /變異概率 #define lchrom 50 /染色體長度 #define maxgen 1000 /最大進化代數(shù) struct population unsigned int chromlchrom; /染色體 double weight; /背包重量 double fitness; /適應度 unsigned int parent1,parent2,cross; /雙親、交叉點 ; /新生代種群、父代種群 struct popula

6、tion oldpoppopsize,newpoppopsize; /背包問題中物體重量、收益、背包容量 int weightlchrom,profitlchrom,contain; /種群的總適應度、最小、最大、平均適應度 double sumfitness,minfitness,maxfitness,avgfitness; /計算適應度時使用的 懲罰函數(shù)系數(shù) double alpha; /一個種群中最大和最小適應度的個體 int minpop,maxpop; /* 讀入背包信息,并且計算懲罰函數(shù)系數(shù) */ void read_infor() FILE *fp; int j; /獲取背包問題

7、信息文件 if (fp=fopen("knapsack.txt","r")=NULL) /讀取文件失敗 AfxMessageBox("The file is not found",MB_OK,NULL); return; /讀入物體收益信息 for (j=0;j<lchrom;j+) fscanf(fp,"%d",&profitj); /讀入物體重量信息 for (j=0;j<lchrom;j+) fscanf(fp,"%d",&weightj); /讀入背包容量 f

8、scanf(fp,"%d",&contain); fclose(fp); /根據(jù)計算的個體重量,判斷此個體是否該留在群體中 double cal_weight(unsigned int *chr) int j; double pop_weight;/背包重量 pop_weight=0; for (j=0;j<lchrom;j+) pop_weight=pop_weight+(*chr)*weightj; chr+; return pop_weight; /* 種群中個體適應度計算*/ double cal_fit(unsigned int *chr) int

9、j; double pop_profit;/適應度 pop_profit=0; / pop_weight=0; for (j=0;j<lchrom;j+) pop_profit=pop_profit+(*chr)*profitj; / pop_weight=pop_weight+(*chr)*weightj; chr+; return pop_profit; /* 群體適應度的最大最小值以及其他信息 */ void statistics(struct population *pop) int i; double tmp_fit; sumfitness=pop0.fitness; minf

10、itness=pop0.fitness; minpop=0; maxfitness=pop0.fitness; maxpop=0; for (i=1;i<popsize;i+) /計算種群的總適應度 sumfitness=sumfitness+popi.fitness; tmp_fit=popi.fitness; /選擇種群中最大適應度的個體 if (tmp_fit>maxfitness)&&(int)(tmp_fit*10)%10=0) maxfitness=popi.fitness; maxpop=i; /選擇種群中最小適應度的個體 if (tmp_fit<

11、;minfitness) minfitness=popi.fitness; minpop=i; /計算平均適應度 avgfitness=sumfitness/(float)popsize; / printf("nthe max pop = %d;",maxpop); / printf("nthe min pop = %d;",minpop); / printf("nthe sumfitness = %fn",sumfitness); /報告種群信息 void report(struct population *pop,int gen)

12、 int j; int pop_weight=0; printf("the generation is %d.n",gen); /輸出種群的代數(shù) /輸出種群中最大適應度個體的染色體信息 printf("The population's chrom is: n"); for (j=0;j<lchrom;j+) if (j%5=0) printf(" "); printf("%1d",popmaxpop.chromj); /輸出群體中最大適應度 printf("nThe population&#

13、39;s max fitness is %d.",(int)popmaxpop.fitness); printf("nThe knapsack weight is %d.nn",(int)popmaxpop.weight); /* 生成初始種群 */ void initpop() int i,j,ispop; double tmpWeight; /變量用于判斷是否為滿足條件的個體 ispop=false; /生成popsize個種群個體 for(i=0;i<popsize;i+) while (!ispop) for(j=0;j<lchrom;j+)

14、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.weight=tmpWeight; oldpopi.parent1=0; oldpopi.parent2=0; oldpopi.cr

15、oss=0; ispop=true; /此個體可以加入到種群中 ispop=false; /* 遺傳操作 */ /概率選擇試驗 int execise(double probability) double pp; /如果生成隨機數(shù)大于相應的概率則返回真，否則試驗不成功 pp=(double)(rand()%20001/20000.0); if (pp<=probability) return 1; return 0; / 選擇進行交叉操作的個體 int selection(int pop) double wheel_pos,rand_Number,partsum; int parent;

16、 /賭輪法選擇 rand_Number=(rand()%2001)/2000.0; wheel_pos=rand_Number*sumfitness; /賭輪大小 partsum=0; parent=0; do partsum=partsum+oldpopparent.fitness; parent=parent+1; while (partsum<wheel_pos && parent<popsize); return parent-1; /* 交叉操作 */ int crossover(unsigned int *parent1,unsigned int *pa

17、rent2,int i) int j,cross_pos; if (execise(pc) /生成交叉位置0,1,.(lchrom-2) cross_pos=rand()%(lchrom-1); else cross_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=

18、cross_pos; return 1; /* 變異操作 */ int mutation(unsigned int alleles) if (execise(pm) if (alleles) alleles=0; else alleles=1; /返回變異值，或者返回原值 return alleles; /* 群體更新 */ void generation() unsigned int i,j,mate1,mate2; double tmpWeight; int ispop;/記錄是否是符合條件的個體 i=0; while (i<popsize) ispop=false; while (

19、!ispop) /選擇 mate1=selection(i); mate2=selection(i+1); /交叉 crossover(oldpopmate1.chrom,oldpopmate2.chrom,i); /變異 for (j=0;j<lchrom;j+) newpopi.chromj=mutation(newpopi.chromj); /選擇重量小于背包容量的個體,即滿足條件 tmpWeight=cal_weight(newpopi.chrom); if (tmpWeight<=contain) newpopi.fitness=cal_fit(newpopi.chrom

20、); newpopi.weight=tmpWeight; newpopi.parent1=mate1; newpopi.parent2=mate2; ispop=true; /此個體可以加入到種群中 i=i+1; void main(int argc, char* argv) int gen,oldmaxpop,k; double oldmax; read_infor();/讀入背包信息 gen=0; srand( (unsigned)time( NULL ) );/置隨機種子 initpop(); memcpy(&newpop,&oldpop,popsize*sizeof(struct population); statistics(newpop);/統(tǒng)計新生種群的信息 report(newpop,gen); while(gen<maxgen) gen=gen+1; i