人工智能作業(yè)實(shí)驗(yàn)五

1、實(shí)驗(yàn)五 計(jì)算智能(2)軟工研-142014312170106基于背包問(wèn)題的模型（*），設(shè)計(jì)了針對(duì)于背包問(wèn)題的編碼方法：將待求解的各量實(shí)驗(yàn)?zāi)康睦斫膺z傳算法的求解 ，掌握遺傳算法的原理，通過(guò)運(yùn)用 編程（或相關(guān)編程語(yǔ)言）實(shí)現(xiàn)遺傳算法，并求解實(shí)際問(wèn)題，對(duì)求解結(jié)果進(jìn)行分析。通過(guò)分析結(jié)果了解遺傳算法在求解實(shí)際問(wèn)題的特點(diǎn)和優(yōu)勢(shì)。實(shí)驗(yàn)內(nèi)容編寫一個(gè)遺傳算法及其實(shí)際應(yīng)用的程序，能運(yùn)用遺傳算法求解實(shí)際問(wèn)題。實(shí)驗(yàn)要求（1）簡(jiǎn)述實(shí)驗(yàn)原理及方法，并請(qǐng)給出程序設(shè)計(jì)流程圖。2.1 按照下列公式計(jì)算種群中適：4.1 根據(jù)事先定義好的交叉概率GenMaxgen?新種群的最大適舊種群的置演化代數(shù)gen=gen+1圖 12、主函數(shù)

2、main 的流程圖是舊種群的最大適應(yīng)度到新種群中最小調(diào)用sistics ( )統(tǒng)計(jì)種群的適調(diào)用report( )，輸出結(jié)果信息是調(diào)用generation()生成新種群調(diào)用sistics ( )統(tǒng)計(jì)種群的適調(diào)用initpop( )生成初始種群置演化代數(shù)gen=0調(diào)用 read_infor，讀入背包信息/ knapsack.cpp : Defines the entry pofor the console application./#include stdafx.h#include #include #include #include #include #include / 重要常量參數(shù)#defi

3、ne popsize 200#define pc 0.618#define pm 0.03#define lchrom 50#define maxgen 1000/種群的規(guī)模/雜交概率/變異概率/長(zhǎng)度/最大進(jìn)化代數(shù)struct populationunsignedchromlchrom;/double weight;double fitness;/背包重量/適unsigned;parent1,parent2,cross;/雙親、交叉點(diǎn)/種群、父代種群struct population oldpoppopsize,newpoppopsize;/背包問(wèn)題中物體重量、收益、背包容量weightlch

4、rom,profitlchrom,contain;/種群的總適、最小、最大、平均適double sumfitness,minfitness,maxfitness,avgfitness;/計(jì)算適double alpha;時(shí)使用的 懲罰函數(shù)系數(shù)/一個(gè)種群中最大和最小適minpop,maxpop;的（2）源程序：/* 讀入背包信息,并且計(jì)算懲罰函數(shù)系數(shù) */ void read_infor()FILE *fp; j;/獲取背包問(wèn)題信息文件if (fp=fopen(knapsack.txt,r)=NULL)/文件失敗AfxMessageBox(The file is not found,MB_OK,N

5、ULL);return;/讀入物體收益信息 for (j=0;jlchrom;j+)fscanf(fp,%d,&profitj);/讀入物體重量信息 for (j=0;jlchrom;j+)fscanf(fp,%d,&weightj);/讀入背包容量fscanf(fp,%d,&contain); fclose(fp);/根據(jù)計(jì)算的重量,判斷此是否該留在群體中double cal_weight(unsignedj;*chr)double pop_weight;/背包重量pop_weight=0;for (j=0;jlchrom;j+)pop_weight=pop_weight+(*chr)*we

6、ightj; chr+;return pop_weight;/* 種群中適計(jì)算*/double cal_fit(unsigned*chr)j;double pop_profit;/適pop_profit=0;/pop_weight=0;for (j=0;jlchrom;j+)pop_profit=pop_profit+(*chr)*profitj; pop_weight=pop_weight+(*chr)*weightj; chr+;/return pop_profit;/* 群體適*/的最大最小值以及其他信息void sistics(struct population *pop)i;doub

7、le tmp_fit;sumfitness=pop0.fitness; minfitness=pop0.fitness; minpop=0; maxfitness=pop0.fitness;maxpop=0;for (i=1;imaxfitness)&()(tmp_fit*10)%10=0)maxfitness=popi.fitness; maxpop=i;/選擇種群中最小適 if (tmp_fitminfitness)minfitness=popi.fitness; minpop=i;的/計(jì)算平均適avgfitnesmfitness/(float)popsize;/prpr prf(nthe

8、 max pop = %d;,maxpop);f(nthe min pop = %d;,minpop); f(nthe sumfitness = %fn,sumfitness);/種群信息void report(struct population *pop,j; pop_weight=0;gen)prf(teration is %d.n,gen); /輸出種群的代數(shù)/輸出種群中最大適的信息prf(The populations chrom is:n); for (j=0;jlchrom;j+)if (j%5=0)prf( );prf(%1d,popmaxpop.chromj);/輸出群體中最大

9、適prf(nThe populations max fitness is %d.,()popmaxpop.fitness); prf(nThe knapsack weight is %d.nn,()popmaxpop.weight);/*生成初始種群 */void initpop()i,j,ispop; double tmpWeight;/變量用于判斷是否為滿足條件的ispop=false;/生成 popsize 個(gè)種群for(i=0;ipopsize;i+)while (!ispop)for(j=0;jlchrom;j+)oldpopi.chromj=rand()%2;/隨機(jī)生成 oldpo

10、pi.parent1=0;/雙親oldpopi.parent2=0;的oldpopi.cross=0;/交叉點(diǎn)/選擇重量小于背包容量的,即滿足條件tmpWeight=cal_weight(oldpopi.chrom); if (tmpWeight=contain)oldpopi.fitness=cal_fit(oldpopi.chrom); oldpopi.weight=tmpWeight; oldpopi.parent1=0;oldpopi.parent2=0; oldpopi.cross=0; ispop=true;/此可以加入到種群中ispop=false;/*遺傳操作*/概率選擇試驗(yàn)

11、execise(double probability)double pp;/如果生成隨機(jī)數(shù)大于相應(yīng)的概率則返回真，否則試驗(yàn)不成功 pp=(double)(rand()%20001/20000.0);if (pp=probability) return 1; return 0;/ 選擇進(jìn)行交叉操作的selection(pop)double wheel_parent;,rand_Numbartsum;/賭輪法選擇rand_Number=(rand()%2001)/2000.0;wheel_=rand_Number*sumfitness;/賭輪大小partsum=0; parent=0; dopar

12、tsum=partsum+oldpopparent.fitness;parent=parent+1; while (partsumwheel_return parent-1;& parentpopsize);/*交叉操作 */crossover(unsigned*parent1,unsigned*parent2,i)j,cross_;if (execise(pc)/生成交叉位置 0,1,.(lchrom-2)cross_=rand()%(lchrom-1);else cross_=lchrom-1;for (j=0;j=cross_;j+)/保留；/包括在概率選擇不成功時(shí)，父體完全保留newp

13、opi.chromj=parent1j;for(j=cross_+1;j=(lchrom-1);j+)/從交叉點(diǎn)開始交叉newpopi.chromj=parent2j;/交叉位置newpopi.cross=cross_return 1;/*變異操作 */muion(unsignedalleles)if (execise(pm)if (alleles)alleles=0; else alleles=1;/返回變異值，或者返回原值 return alleles;/* 群體更新 */ void generation()unsignedi,j,mate1,mate2;double tmpWeight;

14、ispop;/i=0;是否是符合條件的while (ipopsize)ispop=false; while (!ispop)/選擇mate1=selection(i); mate2=selection(i+1);/交叉crossover(oldpopmate1.chrom,oldpopmate2.chrom,i);/變異for (j=0;jlchrom;j+)newpopi.chromj=muion(newpopi.chromj);/選擇重量小于背包容量的,即滿足條件tmpWeight=cal_weight(newpopi.chrom); if (tmpWeight=contain)newpo

15、pi.fitness=cal_fit(newpopi.chrom);newpopi.weight=tmpWeight; newpopi.parent1=mate1; newpopi.parent2=mate2;ispop=true;/此 i=i+1;可以加入到種群中void main(argc, char* argv)gen,oldmaxpop,k;double oldmax;read_infor();/讀入背包信息 gen=0;srand( (unsigned)time( NULL ) );/置隨機(jī) initpop();memcpy(&newpop,&oldpop,popsize*sizeo

16、f(struct population); sistics(newpop);/統(tǒng)計(jì)新生種群的信息 report(newpop,gen);while(genmaxgen)gen=gen+1;if (gen%100=0)srand( (unsigned)time( NULL ) );/置隨機(jī)oldmax=maxfitness;oldmaxpop=maxpop; generation();sistics(newpop); /統(tǒng)計(jì)種群信息/如果種群中的最大適小于老一代種群/的最大適，則保存老一代種群的最大適/否則的最大適if (maxfitnessoldmax)for(k=0;koldmax)repo

17、rt(newpop,gen);/保存種群的信息到老一代種群信息空間memcpy(&oldpop,&newpop,popsize*sizeof(struct population);prf(It is over.);getch();實(shí)例數(shù)據(jù)：假設(shè)物體的重量 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， 1Profit= 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，Contain=1000，20，15，10， 8，5，3，1如何選擇哪些物品裝入該背包可使得在