c语言贪婪遗传算法算法背包问题 求高手帮我用C语言写一个运用贪心和遗传算法求解背包

匿名用户

1级

-07-13 回答

1、程序开发环境

开发环境：VisualC++6.0(把Fortran程序改为VC)

操作系统：WindowsProfessional

2、程序性能对比

运行时间与加速比(如表1所示)

进程数p(个)124

运行时间t(秒)129s78s38s

加速比s1.653.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，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，8，5，3，1}

Contain=1000，

如何选择哪些物品装入该背包可使得在背包的容量约束限制之内所装物品的总价值最大?

传统的算法(动态规划、递归回溯法和贪心算法所得结果：

总价值为3077,总重量为999。

2001年张铃，张钹教授在计算机学报上发表的《佳点集遗传算法》所得结果

总价值为3103,总重量为1000。

我们算法所得结果：总价值为3103,总重量为1000。

我们所求得最优解的个体分配情况为：

110101011110110110110111111101000010100110000

01000

算法最大迭代次数总价值为总重量为

传统的算法4003077999

佳点集算法7031031000

遗传算法7531031000

//knapsack.cpp:Definestheentrypointfortheconsoleapplication.

//

#include"stdafx.h"

#include

#include

#include

#include

#include

#include

//重要常量参数

#definepopsize200//种群的规模

#definepc0.618//杂交概率

#definepm0.03//变异概率

#definelchrom50//染色体长度

#definemaxgen1000//最大进化代数

structpopulation

{

unsignedintchrom[lchrom];//染色体

doubleweight;//背包重量

doublefitness;//适应度

unsignedintparent1,parent2,cross;//双亲、交叉点

};

//新生代种群、父代种群

structpopulationoldpop[popsize],newpop[popsize];

//背包问题中物体重量、收益、背包容量

intweight[lchrom],profit[lchrom],contain;

//种群的总适应度、最小、最大、平均适应度

doublesumfitness,minfitness,maxfitness,avgfitness;

//计算适应度时使用的惩罚函数系数

doublealpha;

//一个种群中最大和最小适应度的个体

intminpop,maxpop;

/*读入背包信息,并且计算惩罚函数系数*/

voidread_infor()

{

FILE*fp;

intj;

//获取背包问题信息文件

if((fp=fopen("knapsack.txt","r"))==NULL)

{

//读取文件失败

AfxMessageBox("Thefileisnotfound",MB_OK,NULL);

return;

}

//读入物体收益信息

for(j=0;j

{

fscanf(fp,"%d",&profit[j]);

}

//读入物体重量信息

for(j=0;j

{

fscanf(fp,"%d",&weight[j]);

}

//读入背包容量

fscanf(fp,"%d",&contain);

fclose(fp);

}

//根据计算的个体重量,判断此个体是否该留在群体中

doublecal_weight(unsignedint*chr)

{

intj;

doublepop_weight;//背包重量

pop_weight=0;

for(j=0;j

{

pop_weight=pop_weight+(*chr)*weight[j];

chr++;

}

returnpop_weight;

}

/*种群中个体适应度计算*/

doublecal_fit(unsignedint*chr)

{

intj;

doublepop_profit;//适应度

pop_profit=0;

//pop_weight=0;

for(j=0;j

{

pop_profit=pop_profit+(*chr)*profit[j];

//pop_weight=pop_weight+(*chr)*weight[j];

chr++;

}

returnpop_profit;

}

/*群体适应度的最大最小值以及其他信息*/

voidstatistics(structpopulation*pop)

{

inti;

doubletmp_fit;

sumfitness=pop[0].fitness;

minfitness=pop[0].fitness;

minpop=0;

maxfitness=pop[0].fitness;

maxpop=0;

for(i=1;i

{

//计算种群的总适应度

sumfitness=sumfitness+pop[i].fitness;

tmp_fit=pop[i].fitness;

//选择种群中最大适应度的个体

if((tmp_fit>maxfitness)&&((int)(tmp_fit*10)%10==0))

{

maxfitness=pop[i].fitness;

maxpop=i;

}

//选择种群中最小适应度的个体

if(tmp_fit

{

minfitness=pop[i].fitness;

minpop=i;

}

//计算平均适应度

avgfitness=sumfitness/(float)popsize;

}

//printf("\nthemaxpop=%d;",maxpop);

//printf("\ntheminpop=%d;",minpop);

//printf("\nthesumfitness=%f\n",sumfitness);

}

//报告种群信息

voidreport(structpopulation*pop,intgen)

{

intj;

intpop_weight=0;

printf("thegenerationis%d.\n",gen);//输出种群的代数

//输出种群中最大适应度个体的染色体信息

printf("Thepopulation'schromis:\n");

for(j=0;j

{

if(j%5==0)

{printf("");}

printf("%1d",pop[maxpop].chrom[j]);

}

//输出群体中最大适应度

printf("\nThepopulation'smaxfitnessis%d.",(int)pop[maxpop].fitness);

printf("\nTheknapsackweightis%d.\n\n",(int)pop[maxpop].weight);

}

/*生成初始种群*/

voidinitpop()

{

inti,j,ispop;

doubletmpWeight;

//变量用于判断是否为满足条件的个体

ispop=false;

//生成popsize个种群个体

for(i=0;i

{

while(!ispop)

{

for(j=0;j

{

oldpop[i].chrom[j]=rand()%2;//随机生成个体的染色体

oldpop[i].parent1=0;//双亲

oldpop[i].parent2=0;

oldpop[i].cross=0;//交叉点

}

//选择重量小于背包容量的个体,即满足条件

tmpWeight=cal_weight(oldpop[i].chrom);

if(tmpWeight<=contain)

{

oldpop[i].fitness=cal_fit(oldpop[i].chrom);

oldpop[i].weight=tmpWeight;

oldpop[i].parent1=0;

oldpop[i].parent2=0;

oldpop[i].cross=0;

ispop=true;

}

}

//此个体可以加入到种群中

ispop=false;

}

}

/*遗传操作*/

//概率选择试验

intexecise(doubleprobability)

{

doublepp;

//如果生成随机数大于相应的概率则返回真，否则试验不成功

pp=(double)(rand()%20001/20000.0);

if(pp<=probability)return1;

return0;

}

//选择进行交叉操作的个体

intselection(intpop)

{

doublewheel_pos,rand_Number,partsum;

intparent;

//赌轮法选择

rand_Number=(rand()%2001)/2000.0;

wheel_pos=rand_Number*sumfitness;//赌轮大小

partsum=0;

parent=0;

do{

partsum=partsum+oldpop[parent].fitness;

parent=parent+1;

}while(partsum

returnparent-1;

}

/*交叉操作*/

intcrossover(unsignedint*parent1,unsignedint*parent2,inti)

{

intj,cross_pos;

if(execise(pc))

{

//生成交叉位置0,1,...(lchrom-2)

cross_pos=rand()%(lchrom-1);

}

elsecross_pos=lchrom-1;

for(j=0;j<=cross_pos;j++)

{//保留复制；

//包括在概率选择不成功时，父体完全保留

newpop[i].chrom[j]=parent1[j];

}

for(j=cross_pos+1;j<=(lchrom-1);j++)

{

//从交叉点开始交叉

newpop[i].chrom[j]=parent2[j];

}

//记录交叉位置

newpop[i].cross=cross_pos;

return1;

}

/*变异操作*/

intmutation(unsignedintalleles)

{

if(execise(pm))

{

if(alleles)

alleles=0;

elsealleles=1;

}

//返回变异值，或者返回原值

returnalleles;

}

/*群体更新*/

voidgeneration()

{

unsignedinti,j,mate1,mate2;

doubletmpWeight;

intispop;//记录是否是符合条件的个体

i=0;

while(i

{

ispop=false;

while(!ispop)

{

//选择

mate1=selection(i);

mate2=selection(i+1);

//交叉

crossover(oldpop[mate1].chrom,oldpop[mate2].chrom,i);

//变异

for(j=0;j

{

newpop[i].chrom[j]=mutation(newpop[i].chrom[j]);

}

//选择重量小于背包容量的个体,即满足条件

tmpWeight=cal_weight(newpop[i].chrom);

if(tmpWeight<=contain)

{

newpop[i].fitness=cal_fit(newpop[i].chrom);

newpop[i].weight=tmpWeight;

newpop[i].parent1=mate1;

newpop[i].parent2=mate2;

ispop=true;

}

}

//此个体可以加入到种群中

i=i+1;

}

}

voidmain(intargc,char*argv[])

{

intgen,oldmaxpop,k;

doubleoldmax;

read_infor();//读入背包信息

gen=0;

srand((unsigned)time(NULL));//置随机种子

initpop();

memcpy(&newpop,&oldpop,popsize*sizeof(structpopulation));

statistics(newpop);//统计新生种群的信息

report(newpop,gen);

while(gen

{

gen=gen+1;

if(gen%100==0)

{

srand((unsigned)time(NULL));//置随机种子

}

oldmax=maxfitness;

oldmaxpop=maxpop;

generation();

statistics(newpop);//统计新生代种群信息

//如果新生代种群中个体的最大适应度小于老一代种群

//个体的最大适应度，则保存老一代种群个体的最大适应度

//否则报告新生代的最大适应度

if(maxfitness

{

for(k=0;k

newpop[minpop].chrom[k]=oldpop[oldmaxpop].chrom[k];

newpop[minpop].fitness=oldpop[oldmaxpop].fitness;

newpop[minpop].parent1=oldpop[oldmaxpop].parent1;

newpop[minpop].parent2=oldpop[oldmaxpop].parent2;

newpop[minpop].cross=oldpop[oldmaxpop].cross;

statistics(newpop);

}

elseif(maxfitness>oldmax)

{

report(newpop,gen);

}

//保存新生代种群的信息到老一代种群信息空间

memcpy(&oldpop,&newpop,popsize*sizeof(structpopulation));

}

printf("Itisover.");

getch();

}

追问：

这个没有贪心算法的，能不能求一个两个相结合的啊？？？

追答：

背包还能用贪心解吗？

除了这个我只知道搜索和动态规划

c语言贪婪遗传算法算法背包问题 求高手帮我用C语言写一个运用贪心和遗传算法求解背包问题的程序。。。。谢谢！！！！！！十分紧急！！！...

如果觉得《c语言贪婪遗传算法算法背包问题 求高手帮我用C语言写一个运用贪心和遗传算法求解背包》对你有帮助，请点赞、收藏，并留下你的观点哦！