1、人工智能第二次實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)題冃：應(yīng)用遺傳算法的設(shè)計(jì)與實(shí)現(xiàn)實(shí)驗(yàn)?zāi)康模和ㄟ^(guò)人工智能課程的學(xué)習(xí)，熟悉遺傳算法的簡(jiǎn)單實(shí)驗(yàn)內(nèi)容用遺傳算法求解 f x = x 2 的最大值， x ?0,31 ， x 取整數(shù)?？梢钥闯鲈摵瘮?shù)比擬簡(jiǎn)單， 只要是為了表達(dá)遺傳算法的思 想，在問(wèn)題選 擇上，選了一個(gè)比擬容易實(shí)現(xiàn)的，把主要精力 放在遺傳算法的實(shí)現(xiàn)，以及核 心思想體會(huì)上。四 . 實(shí)驗(yàn)過(guò)程：1. 實(shí)現(xiàn)過(guò)程 1 編碼使用二進(jìn)制編碼，隨機(jī)產(chǎn)生一個(gè)初始種群。 L 表示編碼長(zhǎng)度， 通常由對(duì)問(wèn)題的求解精度決定，編碼長(zhǎng)度 L 越長(zhǎng)，可期望的最 優(yōu) 解的精度也就越高，過(guò)大的 L 會(huì)增大運(yùn)算量。針對(duì)該問(wèn)題進(jìn) 行 了簡(jiǎn)化，因?yàn)轭}設(shè)中 x?

2、 0,31 ，所以將二進(jìn)制長(zhǎng)度定為 5 就夠 用了；2生成初始群體 種群規(guī)模表示每一代種群中所含個(gè)體數(shù)目。 隨機(jī)產(chǎn)生 N 個(gè) 初 始串結(jié)構(gòu)數(shù)據(jù)，每個(gè)串結(jié)構(gòu)數(shù)據(jù)成為一個(gè)個(gè)體， N 個(gè)個(gè)體組 成一個(gè)初始 群體，N表示種群規(guī)模的大小。 當(dāng)N取值較小時(shí)， 可提高遺傳算法的運(yùn)算速 度，但卻降低種群的多樣性，容易 引起遺傳算法早熟，出現(xiàn)假收斂；而 N當(dāng) 取值較大時(shí)，又會(huì) 使得遺傳算法效率降低。一般建議的取值范圍是 20 100 。3適應(yīng)度檢測(cè)根據(jù)實(shí)際標(biāo)準(zhǔn)計(jì)算個(gè)體的適應(yīng)度， 評(píng)判個(gè)體的優(yōu)劣， 即該個(gè) 體 所代表的可行解的優(yōu)劣。本例中適應(yīng)度即為所求的目標(biāo)函數(shù)；4選擇從當(dāng)前群體中選擇優(yōu)良 適應(yīng)度高的 個(gè)體，使它

3、們有時(shí)機(jī) 被 選中進(jìn)入下一次迭代過(guò)程， 舍棄適應(yīng)度低的個(gè)體。 本例中采用 輪 盤賭的選擇方法， 即個(gè)體被選擇的幾率與其適應(yīng)度值大小成正比；5交叉遺傳操作，根據(jù)設(shè)置的交叉概率對(duì)交配池中個(gè)體進(jìn)行基因交 叉操作， 形成新一代的種群， 新一代中間個(gè)體的信息來(lái)自父輩 個(gè) 體，表達(dá)了信息交換的原那么。 交叉概率控制著交叉操作的頻率， 由于交叉操作是遺傳算法中產(chǎn)生新個(gè)體的主要方法， 所以交叉概 率通常應(yīng)取較大值； 但假設(shè)過(guò)大的話， 又可能破壞群體的優(yōu)良模 式。 一般取 0.4 到 0.99 。6變異900 時(shí)，結(jié)束。從而觀看遺傳的效率問(wèn)題隨機(jī)選擇中間群體中的某個(gè)個(gè)體，以變異概率大小改變個(gè)體 某位基因的值。

4、變異為產(chǎn)生新個(gè)體提供了時(shí)機(jī)。 變異概率也是 影 響新個(gè)體產(chǎn)生的一個(gè)因素，變異概率小，產(chǎn)生新個(gè)體少；變異 概 率太大，又會(huì)使遺傳算法變成隨機(jī)搜索。一般取變異概率為 0.0001 0.1 。當(dāng)?shù)玫降慕獯笥诘?結(jié)束條件五. 代碼及結(jié)果：/* 遺傳算法設(shè)計(jì)最大 */ 值 #include <stdio.h> #include <string.h> #include <stdlib.h> #include <time.h>#define C 0 /#define CFLAG 4/#define JIAOCHA_RATE 0.5#define BIANYI_

5、RATE 0.09 #define ITER_NUM 1000 #define POP_NUM 20 / #define GENE_NUM 5/#defi ne FEXP(x) (x)*(x) /y=xT typedef unsigned int UINT;/ 染色體 typedef structchar geneBitGENE_NUM; /UINT fitValue; /Chromosome;/ 將二進(jìn)制的基因位轉(zhuǎn)化為十進(jìn)制測(cè)試測(cè)試標(biāo)記/ 交叉概率一般取 0.4 到 0.99/變異概率為 /迭代次數(shù)染色體個(gè)數(shù) 基因位數(shù)基因位適應(yīng)值UINT toDec(Chromosome pop)UINT

6、i;UINT radix = 1;UINT result = 0; for(i=0; i<GENE_NUM; i+) result += (pop.geneBiti-'0')*radix; radix *= 2; return result;UINT calcFitValue(UINT x) return FEXP(x);void test(Chromosome *pop) int i;int j;for(i=0; i<POP_NUM; i+)printf("%d: ", i+1); for(j=0; j<GENE_NUM; j+) pri

7、ntf("%c", popi.geneBitj);printf(" %4d", toDec(popi);printf(" fixValue=%dn", calcFitValue(toDec(popi); / 變異得到新個(gè)體 : 隨機(jī)改變基因 void mutation(Chromosome *pop) UINT randRow, randCol; UINT randValue; randValue=rand()%100; if(randValue >= (int)(BIANYI_RATE*100) #if (C=1) &

8、& (CFLAG=4)printf("n 種群個(gè)體沒(méi)有基因變異 n"); #endif return ;randCol = rand()%GENE_NUM; /隨機(jī)產(chǎn)生將要變異的基因位randRow = rand()%POP_NUM; /隨機(jī)產(chǎn)生將要變異的染色體位#if (C=1) && (CFLAG=4)printf("n 變異前 n");test(pop);printf("n 變異的位置為 : 染色體號(hào) =%d 基因位號(hào) =%dn", randRow+1, randCol); #endifpoprandRo

9、w.geneBitrandCol = (poprandRow.geneBitrandCol='0') '1':'0' /1變?yōu)?0, 0 變?yōu)?poprandRow.fitValue = calcFitValue( toDec(poprandRow) );#if (C=1) && (CFLAG=4)printf("n 變異后 n");test(pop);#endif/ 創(chuàng)立初始群體void createPop(Chromosome *pop)UINT i,j;UINT randValue;UINT value;

10、srand(unsigned)time(NULL);for(i=0; i<POP_NUM; i+)for(j=0; j<GENE_NUM; j+)randValue = rand()%2;popi.geneBitj = randValue+'0' /將隨機(jī)數(shù) 0 或 1 賦給基因value= toDec(popi);popi.fitValue = calcFitValue(value);#if (C=1) && (CFLAG=1)printf("n 隨機(jī)分配的種群如下 :n");test(pop);#endif/ 更新種群void

11、 updatePop(Chromosome *newPop, Chromosome *oldPop)UINT i;for(i=0; i<POP_NUM; i+)oldPopi=newPopi;/ 選擇優(yōu)良個(gè)體 : 根據(jù)適應(yīng)度選擇最優(yōu)解，即最優(yōu)個(gè)體void select(Chromosome *pop)UINT i,j;UINT sumFitValue; /總適應(yīng)值UINT aFitValue; /平均適應(yīng)值float choicePOP_NUM; /選擇 Chromosome tempPop; / 交換變量#if (C=1) && (CFLAG=2) /測(cè)試printf(

12、"n 沒(méi)有選擇前的種群如下 :n"); test(pop);#endif/ 根據(jù)個(gè)體適應(yīng)度冒泡降序排序for(i=POP_NUM; i>0; i-)for(j=0; j<(i-1); j+) if(popj+1.fitValue > popj.fitValue)tempPop = popj+1;popj+1 = popj;popj = tempPop;/ 計(jì)算總適應(yīng)值 sumFitValue = 0; for(i=0; i<POP_NUM; i+) sumFitValue += popi.fitValue;aFitValue = (UINT)(flo

13、at)sumFitValue/POP_NUM)+0.5); /計(jì)算平均適應(yīng)值/ 計(jì)算出每個(gè)群體選擇時(shí)機(jī)，群體的概率=群體適應(yīng)值 / 總適應(yīng)值，平均概率 = 平均適應(yīng)值 / 總適應(yīng)值，群體選擇時(shí)機(jī) = ( 群體的概率 / 平均概率 )for(i=0; i<POP_NUM; i+)choicei = (float)popi.fitValue/sumFitValue)/(float)aFitValue/sumFitValue);choicei = (float)(int)(choicei*100+0.5)/100.0);/保存到小數(shù)點(diǎn)后 2位/ 根據(jù)選擇概率來(lái)繁殖優(yōu)良個(gè)體， 并淘汰較差個(gè) 如果

14、 choicei=0 淘汰繁殖一次最優(yōu)的 體 for(i=0; i<POP_NUM; i+) if(int)(choicei+0.55) = 0) /群體 popPOP_NUM-1 = pop0;#if (C=1) && (CFLAG=2)printf("n 經(jīng)過(guò)選擇以后的種群 :n");test(pop);#endif/ 交叉 : 基因交換void cross(Chromosome *pop) char tmpStrGENE_NUM=""UINT i;UINT randPos;UINT randValue; randValue=r

15、and()%100; if(randValue >= (int)(JIAOCHA_RATE*100) #if (C=1) && (CFLAG=3) printf("n種群沒(méi)有進(jìn)行交叉 .n");#endifreturn ; #if (C=1) && (CFLAG=3)printf("n交叉前 , 種群如下 :n");test(pop);printf("n交叉的位置依次為 :");#endif/ 染色體兩兩交叉for(i=0; i<POP_NUM; i+=2) randPos = (rand(

16、)%(GENE_NUM-1)+1); / 產(chǎn)生隨機(jī)交叉點(diǎn)，范圍是 1 到 GENE_NUM-1 strncpy(tmpStr, popi.geneBit+randPos, GENE_NUM-randPos); strncpy(popi.geneBit+randPos, popi+1.geneBit+randPos,GENE_NUM-randPos); strncpy(popi+1.geneBit+randPos, tmpStr, GENE_NUM-randPos); #if (C=1) && (CFLAG=3) printf(" %d", randPos);

17、#endif/ 對(duì)個(gè)體計(jì)算適應(yīng)度f(wàn)or(i=0; i<POP_NUM; i+) popi.fitValue = calcFitValue(toDec(popi) );#if (C=1) && (CFLAG=3)printf("n 交叉后 , 種群如下 :n"); test(pop);#endif/ 輸出結(jié)果 void result(Chromosome *pop)UINT i;UINT x = 0;UINT maxValue = 0; / 函數(shù)的最大值for(i=0; i<POP_NUM; i+)if(popi.fitValue > max

18、Value) maxValue = popi.fitValue;x = toDec(popi);printf("n 當(dāng) x=%d 時(shí), 函數(shù)得到最大值為 ： dnn", x, maxValue); int main(int argc, char *argv) int count;Chromosome curPopPOP_NUM; /Chromosome nextPopPOP_NUM; / 迭代次數(shù) 初始種群或 者當(dāng)前總?cè)?變異后種 群createPop(curPop);for(count=1; count<(ITER_NUM+1); count+) updatePop(curPop, nextPop); / select(nextPop); / c