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

1、 人工智能第二次實(shí)驗(yàn)報(bào)告 一實(shí)驗(yàn)題目： 遺傳算法的設(shè)計(jì)與實(shí)現(xiàn) 二.實(shí)驗(yàn)?zāi)康模?熟悉遺傳算法的簡(jiǎn)單 通過(guò)人工智能課程的學(xué)習(xí)， 應(yīng)用。 .實(shí)驗(yàn)內(nèi)容 用遺傳算法求解f (x) = x 2的最大值，x 0,31 , x取整數(shù)。 可以看出該函數(shù)比較簡(jiǎn)單，只要是為了體現(xiàn)遺傳算法的思 想，在問(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è)中

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

4、體產(chǎn)生的一個(gè)因素，變異概率小，產(chǎn)生新個(gè)體少；變異概 率太大，又會(huì)使遺傳算法變成隨機(jī)搜索。一般取變異概率為 0.0001 0.1 o (7) 結(jié)束條件 當(dāng)?shù)玫降慕獯笥诘扔?900時(shí)，結(jié)束。從而觀看遺傳的效率問(wèn)題。 五.代碼及結(jié)果: /*遺傳算法設(shè)計(jì)最大值 #i nclude #in elude #i nclude #in clude */ #defi ne C 0/ #defi ne CFLAG 4 #define JIAOCHA RATE 0.5 / / #defi ne BIANYI_RATE0.09 #defi ne ITER_NUM1000 #defi ne POP_NUM20/ #de

5、fi ne GENE_NUM5/ #defi ne FEXP(x) (x)*(x) /y=xT typedef un sig ned int UINT; /染色體 typedef struct / / 測(cè)試 測(cè)試標(biāo)記 交叉概率一般取 0.4到0.99 變異概率為 0.0001-0.1 迭代次數(shù) 染色體個(gè)數(shù) 基因位數(shù) char gen eBitGENE_NUM; / 基因位 UINT fitValue; /適應(yīng)值 Chromosome; /將二進(jìn)制的基因位轉(zhuǎn)化為十進(jìn)制 UINT toDec(Chromosome pop) UINT i; UINT radix = 1; UINT result =

6、 0; for(i=0; iGENE_NUM; i+) result += (pop.ge neBi ti-O)*radix; radix *= 2; return result; UINT calcFitValue(UINT x) return FEXP(x); void test(Chromosome *pop) int i; int j; for(i=0; iPOP_NUM; i+) prin tf(%d: , i+1); for(j=0; j= (in t)(BIANYI_RATE*100) #if (C=1) #en dif return ; ran dCol = ran d()%G

7、ENE_NUM; /隨機(jī)產(chǎn)生將要變異的基因位 ran dRow = ran d()%POP_NUM;/隨機(jī)產(chǎn)生將要變異的染色體位 #if (C=1) test(pop); printf(n變異的位置為：染色體號(hào)=%d基因位號(hào)=%dn, randRow+1, randCol); #en dif popra ndRow.ge neBitra ndCol=(popra ndRow.ge neBitra ndCol=0) 1:0; 1變?yōu)?0, 0 變?yōu)?1 popra ndRow.fitValue = calcFitValue( toDec(popra ndRow); #if (C=1) test(

8、pop); #en dif /創(chuàng)建初始群體 void createPop(Chromosome *pop) UINT i,j; UINT ran dValue; UINT value; sran d( un sig ned)time(NULL); for(i=0; iPOP_NUM; i+) for(j=0; jGENE_NUM; j+) ran dValue = ran d()%2; popi.geneBitj = randValue+O; /將隨機(jī)數(shù) 0 或 1 賦給基因 value= toDec(popi); popi.fitValue = calcFitValue(value); #i

9、f (C=1) test(pop); #en dif /更新種群 void updatePop(Chromosome *n ewPop, Chromosome *oldPop) UINT i; for(i=0; i0; i-) for(j=0; j popj.fitValue) tempPop = popj+1; popj+1 = popj; popj = tempPop; /計(jì)算總適應(yīng)值 sumFitValue = 0; for(i=0; iPOP_NUM; i+) sumFitValue += popi.fitValue; aFitValue = (UINT)(float)sumFitVa

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

11、_RATE*1OO) #if (C=1) #en dif return ; #if (C=1) test(pop); prin tf(n交叉的位置依次為：”)； #en dif /染色體兩兩交叉 for(i=0; iPOP_NUM; i+=2) ran dPos = (ran d()%(GENE_NUM-1)+1); /產(chǎn)生隨機(jī)交叉點(diǎn)，范圍是 1 到 GENE_NUM-1 strncpy(tmpStr, popi.geneBit+randPos, GENE_NUM-randPos); strn cpy(popi.ge neBit+ra ndPos,popi+1.ge neBit+ra ndPo

12、s, GENE_NUM-ra ndPos); strncpy(popi+1.ge neBit+ra ndPos, tmpStr, GENE_NUM-ra ndPos); #if (C=1) #en dif /對(duì)個(gè)體計(jì)算適應(yīng)度 for(i=0; iPOP_NUM; i+) popi.fitValue = calcFitValue(toDec(popi); #if (C=1) test(pop); #en dif /輸出結(jié)果 void result(Chromosome *pop) UINT i; UINT x = 0; UINT maxValue = 0; /函數(shù)的最大值 for(i=0; i

13、maxValue) maxValue = popi.fitValue; x = toDec(popi); printf(n當(dāng) x=%d時(shí)，函數(shù)得到最大值為：dnn, x, maxValue); int main (i nt argc, char *argv) 迭代次數(shù) 初始種群或者當(dāng)前總?cè)?變異后種群 int count;/ Chromosome curPopPOP_NUM; / Chromosome n extPopPOP_NUM; / createPop(curPop); for(count=1; count(ITER_NUM+1); count+) updatePop(curPop, nextPop); /更新種群 select( nextPop);/選擇 cross (n extPop);/交叉 mutati on(n extPop);/變異 updatePop( nextPo