人工智能實(shí)驗(yàn)報(bào)告文件.doc

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

2、 0,31,所以將二進(jìn)制長度定為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ì) 般建議的取值范圍是20lOOo (3) 適應(yīng)度檢測 根據(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è)體，使它們有機(jī)會(huì) 被選中進(jìn)入下一次迭代過程，

3、舍棄適應(yīng)度低的個(gè)體。本例中采用 輪盤賭的選擇方法，即個(gè)體被選擇的幾率與其適應(yīng)度值大小成正 精品. 比； (5) 交叉 遺傳操作，根據(jù)設(shè)置的交叉概率對(duì)交配池中個(gè)體進(jìn)行基因交 叉操作，形成新一代的種群，新一代中間個(gè)體的信息來自父輩個(gè) 體，體現(xiàn)了信息交換的原則。交叉概率控制著交叉操作的頻率， 由于交叉操作是遺傳算法中產(chǎn)生新個(gè)體的主要方法，所以交叉概 率通常應(yīng)取較大值；但若過大的話，又可能破壞群體的優(yōu)良模式。 一般取0.4到0. 99 o (6) 變異 隨機(jī)選擇中間群體中的某個(gè)個(gè)體，以變異概率大小改變個(gè)體 某位基因的值。變異為產(chǎn)生新個(gè)體提供了機(jī)會(huì)。變異概率也是影 響新個(gè)體產(chǎn)生的一個(gè)因素，變異概率小，產(chǎn)

4、生新個(gè)體少；變異概 率太大，又會(huì)使遺傳算法變成隨機(jī)搜索。一般取變異概率為 0. 00010. 1o (7) 結(jié)束條件 當(dāng)?shù)玫降慕獯笥诘扔?00時(shí)，結(jié)束。從而觀看遺傳的效率問題。 /*遺傳算法設(shè)計(jì)最大值*/ #include #include # i ncIude # i ncIude #define C0 五. 代碼及結(jié)果: #define CFLAG 4 /測試標(biāo)記 #define JIAOCHA_RATE 0.5 /交叉概率一般取04到0. 99 #define BIANYLRATE0. 09變異概率為 0. 0001-0 1 #define ITER.NUM 1000 迭代次數(shù) #def

5、ine POP.NUM 20 /染色體個(gè)數(shù) #define GENE_NUM 5 基因位數(shù) #define FEXP(x) (x)*(x) /y=xV typedef uns i gned int UINT; 測試 染色體 typedef struct char geneBitGENE_NUM; /基因位 UINT fitValue;/適應(yīng)值 Chromosome; 將二進(jìn)制的基因位轉(zhuǎn)化為十進(jìn)制 UINT toDec(Chromosome pop) UINT i; UINT radix = 1; UINT result = 0; for(i=0; iGENE_NUM; i+) result +

6、= (pop. geneBiti-0)*radix; radix *= 2; return result; UINT calcFitValue(UINT x) return FEXP(x); voidChromosome *pop) int i; int j； for(i=0; iPOP_NUM； i+) printf (M%d:i+1); for (j=0; j= (int)ANYI.RATEOO) #if (C=1) #endif return ; 精品. randCol = rand()%GENE_NUM; /隨機(jī)產(chǎn)生將要變異的基因位 randRow = rand ()%P0P_NUM；

7、/隨機(jī)產(chǎn)生將要變異的染色體位 #if (C=1) test(pop); printf (Rn變異的位置為：染色體號(hào)*I基因位號(hào)=%dnn, randRow+1t randCol); #endif poprandRow geneBitrandCoI = (poprandRow geneBitrandCoI =0)? rzO1; /1 變?yōu)?0, 0 變?yōu)?1 poprandRow. f i tVaIue = caIcF i tVaIue ( toDec (poprandRow); #if (C=1) test (pop); #endif /創(chuàng)建初始群體 void createPop(Chromo

8、some *pop) UINT i,j; UINT randValue; UINT value; srand (unsigned) time(NULL); for(i=0; iPOP_NUM； i+) for(j=0; jGENE_NUM； j+) ( randValue = rand () %2; popi. geneBit j = randValue+O*; / 將隨機(jī)數(shù) 0 或 1 賦給基因 vaIue= toDec (popi); popij.fitValue = caIcFitValue(vaIue); #if (C=1) test(pop); #endif 更新種群 void up

9、datePop(Chromosome *newPop, Chromosome *oldPop) UINT i; for(i=0; i0； i) for (j=0； j popj. fitValue) tempPop = pop j+1; popj+1 = popj; popj = tempPop; /計(jì)算總適應(yīng)值 sumF i tVaIue = 0; for(i=0； iPOP_NUM； i+) sumFitValue += popij.fi tVaIue; aFitValue = (UI NT) (f I oat) sumF i tVa I ue/POPNUM) +0. 5); 計(jì)算平均適應(yīng)

10、值 /計(jì)算出每個(gè)群體選擇機(jī)會(huì)，群體的概率二群體適應(yīng)值/總適應(yīng)值，平均概率二平均適 應(yīng)值/總適應(yīng)值，群體選擇機(jī)會(huì)=(群體的概率/平均概率) for(i=0; iPOP_NUM; i+) choicei= (fI oat) popi. fitVaIue/sumFitVaIue) /(fI oat) aFitVaIue/sumFitVaIue); choicei = (float) (int) (choicei*100+0.5)/100.0);保留到小數(shù)點(diǎn)后 2 位 根據(jù)選擇概率來繁殖優(yōu)良個(gè)體，并洶汰校差個(gè)體 for(i=0； i= (int) (JIAOCHA_RATE*100) #if (C=1

11、) #endif return ; #if (C=1) test (pop); printf(n交叉的位置依次為：)； #endif /染色體兩兩交叉 for(i=0； iPOP_NUM； i+=2) randPos = (rand()%(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); strnc

12、py (pop i +1. geneBit+randPos, tmpStr, GENE_NUM-randPos); #if (0=1) #endif /對(duì)個(gè)體計(jì)算適應(yīng)度 for(i=0; iPOP_NUM; i+) popi. fitValue = calcFitVaIue(toDec(popi); #if (C=1) test (pop); #endif 輸出結(jié)果 void result(Chromosome *pop) UINT i; UINT x = 0; UINT maxValue = 0;/函數(shù)的最大值 for(i=0; i maxValue) maxVaIue = popifitV

13、alue; x = toDec (popij); pr intf (n 當(dāng) x=%d 時(shí)，函數(shù)得到最大值為:%dnn, x, maxVaIue); int main(int argc, char *argv) int count;迭代次數(shù) Chromosome curPopPOP-NUM;/初始種群或者當(dāng)前總?cè)?Chromosome nextPop POP_NUM;/變異后種群 createPop (curPop); for (count=1; count (ITER_NUM+1); count卄) updatePop (curPop, nextPop); / 更新種群 se I ect (n

14、extPop);/選擇 cross (nextPop);交叉 mutat i on (nextPop) ;/ 變異 updatePop (nextPop, curPop); 更新 printf (n 第d 次迭代:n count); test (curPop); result(curPop); roturn 0; 實(shí)驗(yàn)結(jié)果: 精品. XAUsersXwuyangXDesktopVDebugXzsrfc-fl.exe 第1000次迭代; 1 : 11111 31 fixUalue=961 2： 11111 31 fixUalue=961 3： 11111 31 fixUalue=961 4： 1

15、1111 31 fixUalue=9G1 5： 11111 31 fixUalue=961 6： 11111 31 fixUalu=961 7： 11111 31 fixUalue=961 8： 11111 31 fixUalue=961 9； 11111 31 fixUalue=961 10： 11111 31 fixllalue=961 11 11111 31 fixUalue=9G1 12 11111 31 fixUalue=9S1 13： 11111 31 fixUalue=9G1 14； 11111 31 fixUalue=961 15 10111 29 fixUalue=841 16； 01011 26 fixUalue=676 17 1