遗传算法解背包问题

1、遗传算法解背包问题1、程序开发环境 开发环境：Visual C+6.0 (把Fortran程序改为VC) 操作系统：Windows 2003 Professional 2、程序性能对比 运行时间与加速比（如表1所示） 进程数p（个） 1 2 4 运行时间t（秒） 129s 78s 38s 加速比s 1.65 3.38 表1、运行时间与加速比 3、程序运行结果： 实例数据： 假设物体的重量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， 如何选择哪些物品装入该背包可使得在背包的容量约束限制之内所装物品的总价值最大? 传统的算法（动态规划、递归回溯法和贪心算法所得结果： 总价值为3077 , 总重量为999。 2001年张铃，张钹教授在计算机学报上发表的佳点集遗传算法所得结果 总价值为3103, 总重量为1000。 我们算法所得结果： 总价值为3103, 总重量为1000。 我们所求得最优解的个体分配情况为： 11010 10111 10110 11011 01111 11101 00001 01001 10000 01000 算法 最大迭代次数 总价值为 总重量为 传统的算

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; / 重要常量参数 #define popsize 200 /种群的规模 #define pc 0.618 /杂交概率 #define pm 0.03 /变异概率 #define lchrom 50 /染色体长度 #define maxgen 1000 /最大进化代数 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; /计算适应度时使用的 惩罚函数系数 double alpha; /一个种群中最大和最小适应度的个体 int minpop,maxpop; /* 读入背包信息,并且计算惩罚函数系数 */ 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); /根据计算的个体重量,判断此个体是否该留在群体中 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); /输出种群的代数 /输出种群中最大适应度个体的染色体信息 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; /如果生成随机数大于相应的概率则返回真，否则试验不成功 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);/统计新生种群的信息 report(newpop,gen); while(gen<maxgen) gen=gen+1; i