人工智能實驗報告

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

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

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

4、體產(chǎn)生的一個因素，變異概率小，產(chǎn)生新個體少；變異概 率太大，又會使遺傳算法變成隨機搜索。一般取變異概率為 0.0001 0.1 o (7) 結(jié)束條件 當?shù)玫降慕獯笥诘扔?900時，結(jié)束。從而觀看遺傳的效率問題。 五.代碼及結(jié)果: /*遺傳算法設(shè)計最大值 #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 / / 測試 測試標記 交叉概率一般取 0.4到0.99 變異概率為 0.0001-0.1 迭代次數(shù) 染色體個數(shù) 基因位數(shù) char gen eBitGENE_NUM; / 基因位 UINT fitValue; /適應值 Chromosome; /將二進制的基因位轉(zhuǎ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; /隨機產(chǎn)生將要變異的基因位 ran dRow = ran d()%POP_NUM;/隨機產(chǎn)生將要變異的染色體位 #if (C=1) test(pop); printf(n變異的位置為：染色體號=%d基因位號=%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; /將隨機數(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; /計算總適應值 sumFitValue = 0; for(i=0; iPOP_NUM; i+) sumFitValue += popi.fitValue; aFitValue = (UINT)(float)sumFitVa

10、lue/POP_NUM)+0.5); /計算平均適應值 /計算出每個群體選擇機會，群體的概率=群體適應值/總適應值，平均概率=平均適 應值/總適應值，群體選擇機會=(群體的概率/平均概率) 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ù)點后 2 位 /根據(jù)選擇概率來繁殖優(yōu)良個體，并淘汰較差個體 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)生隨機交叉點，范圍是 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 /對個體計算適應度 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當 x=%d時，函數(shù)得到最大值為：dnn, x, maxValue); int main (i nt argc, char *argv) 迭代次數(shù) 初始種群或者當前總?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