遺傳算法實驗報告

..信息與管理科學(xué)學(xué)院計算機科學(xué)系實驗報告課程名稱：人工智能實驗名稱：遺傳算法問題XX：鵬海賈美麗妍漢昭學(xué)號：15100030631510003024班級：計科實驗室：軟件技術(shù)實驗室指導(dǎo)教師：慧日期：2016.11.09&&遺傳算法問題實驗?zāi)康?．熟悉和掌握遺傳算法的原理、實質(zhì)；2．學(xué)會使用遺傳算法解決問題；3．學(xué)會編寫遺傳算法程序?qū)ふ液瘮?shù)最值；實驗原理遺傳算法是仿真生物遺傳學(xué)和自然選擇機理，通過人工方式所構(gòu)造的一類搜索算法，從某種程度上說遺傳算法是對生物進(jìn)化構(gòu)成進(jìn)展的數(shù)學(xué)方式仿真。在遺傳算法中染色體對應(yīng)的是一系列符號序列，在標(biāo)準(zhǔn)的遺傳算法(即根本遺傳算法)中，通常用0,1組成的位串表示，串上各個位置對應(yīng)基因座，各位置上的取值對應(yīng)等位基因。遺傳算法對染色體進(jìn)展處理，染色體稱為基因個體。一定數(shù)量的基因個體組成基因種群。種群中個體的數(shù)目為種群的規(guī)模，各個體對環(huán)境的適應(yīng)程度稱為適應(yīng)度。實驗容用遺傳算法求根號2，也就是求方程f(x)=x*x-2=0的正整數(shù)解，x=1時f(1)<0，x=2時f(2)>0，由介值定理，那么1到2中間存在一個根，根據(jù)代數(shù)根本定理和根的對稱性知這就是我們要找的根，由目標(biāo)函數(shù)得到適應(yīng)度函數(shù)，我們選擇個體都在[1,2]之間，那適應(yīng)度函數(shù)我可以取j(x)=40/(2+|x*x-2|)-10，由x的取值圍知j的圍是(0,10)

x和y穿插就用取平均(x+y)/2，穿插概率取0.9，變異概率為0，步驟分析選擇目標(biāo)函數(shù)，確定變量定義域及編碼精度，形成編碼方案隨機產(chǎn)生一個規(guī)模為〔即該種群中含有個體〕的種群2個體評價：計算群體P(t)中各個個體適應(yīng)度選擇運算:將選擇算子作用于群體。選擇的目的是把優(yōu)化的個體直接遺傳到下一代或通過配對穿插產(chǎn)生新的個體再遺傳到下一代。選擇操作是建立在群體中個體的適應(yīng)度評估根底上的?！策x擇運算用輪盤賭算法〕對被選擇進(jìn)入匹配池中的個體進(jìn)展穿插操作，形成新種群以小概率在種群中選擇個體進(jìn)展變異操作形成新種群計算每個個體的適值根據(jù)適值概率選擇新個體形成新種群檢查完畢條件，假設(shè)滿足那么算法完畢，當(dāng)前種群中適值最高的個體即所求解；否那么轉(zhuǎn)3選擇操作：首先要知道適應(yīng)度函數(shù)，所謂的適應(yīng)度函數(shù)就是評價函數(shù)，通常是問題的目的函數(shù)〔或它的倒數(shù)〕，它描述了個體的優(yōu)劣程度同時也決定了選擇操作的概率，設(shè)fi表示第i個個體的適應(yīng)度值，那選擇第i個個體的概率就是fi/∑fj，簡單來說，這個概率的大小就決定了該個體是被淘汰還是被保存。通常的具體做法是用類似賭盤的方法，每個個體占它的適應(yīng)度那么寬的轉(zhuǎn)盤大小，每次擲色子，落到哪一格就選哪一格對應(yīng)的個體。穿插操作：穿插操作就是讓2個以上的染色體進(jìn)展穿插產(chǎn)生后代的過程，具體的穿插操作要看具體的問題。不過我覺得有一個原那么，就是要有對稱性，穿插得到的后代中的基因要來源于父代的所有個體中，也就是說n個個體進(jìn)展穿插是和它們的排列沒關(guān)系，這樣子代才有時機得到更優(yōu)秀的基因。穿插操作是遺傳算法中最重要的操作。最簡單的根本方式是交換父代中染色體片段。變異操作：生物可以突變，有時候突變是好的，有時候卻是壞的，但正是因為有了突變才讓有限的種群中基因庫可以非常豐富，也保證了種群的適應(yīng)能力。變異操作通常是翻轉(zhuǎn)個體中某段染色體，編碼后的染色體在計算機中都是01串，也就可以隨機的翻轉(zhuǎn)某個〔或多個〕bit上的值。穿插和變異不是一定要發(fā)生在選擇了的個體上，而是按一定控制概率發(fā)生的，穿插概率比擬高通常是0.6~0.95，而變異概率比擬低通常是0.001~0.01。五、實驗程序#include<stdio.h>#include<time.h>#include<stdlib.h>typedefstruct_indi//個體{doublecode;//染色體doubledegree;//適應(yīng)度}Indi;Indigroup[40];//種群規(guī)模為40//------------------------------------------------------//適應(yīng)度算法voidJudge(Indi&x)//適應(yīng)度算法{doubletmp=x.code*x.code-2.0;if(tmp>=0)x.degree=40.0/(2.0+tmp)-10.0;elsex.degree=40.0/(2.0-tmp)-10.0;}//------------------------------------------------------inthappened(doublep)//是否發(fā)生一個概率在p=0~1的事件{returnrand()<(int)(p*RAND_MAX);}//------------------------------------------------------//穿插操作voidCross(Indi&x,Indi&y)//穿插操作，產(chǎn)生一個子代取代父代中最次的一個{Indiz;z.code=(x.code+y.code)/2.0;//穿插只進(jìn)展了取平均值Judge(z);if(x.degree<y.degree){if(z.degree<=x.degree)return;//如果新個體不如雙親，淘汰之x=z;//否那么，替代父代中最次的一個}else{if(z.degree<=y.degree)return;y=z;}}//------------------------------------------------------voidmain(){srand(time(NULL));//設(shè)置隨機數(shù)種子inti,j,best,x,y,c;doublesum,strick;for(i=0;i<40;++i)//隨機得到初始種群{group[i].code=1.0+(double)rand()/RAND_MAX;Judge(group[i]);}for(i=1;i<=10;++i)//固定進(jìn)化10代{for(sum=0.0,best=0,j=0;j<40;++j){sum+=group[j].degree;//求總的適應(yīng)度sumif(group[j].degree>group[best].degree)best=j;//求當(dāng)前最優(yōu)個體}printf("第%2d代中最優(yōu)個體為%10f(適應(yīng)度%10f)平均適應(yīng)度為%10f\n",i,group[best].code,group[best].degree,sum/40.0);for(c=40;c;--c)//輪盤賭法選擇個體{strick=(double)rand()/RAND_MAX*sum;//賭盤中的色子，選擇個體x,yfor(x=0;x<40&&strick>=group[x].degree;++x)strick-=group[x].degree;strick=(double)rand()/RAND_MAX*sum;for(y=0;y<40&&strick>=group[y].degree;++y)strick-=group[y].degree;if(happened(0.9))//穿插率為0.9Cross(group[x],group[y]);//穿插}}}實驗結(jié)果：六、實驗心得本次人工智能實驗是以小組任務(wù)來完成，小組中的幾個成員分工明確，各有所長，就我們組所選擇的人工智能遺傳算法而言，從拿到題目不知所措到問題一一解決，例如程序運行錯誤，流程圖難以畫出等。重要的是在遺傳算法實驗過程