人工智能課程設(shè)計匯報課件

基于遺傳算法的TSP問題產(chǎn)生式系統(tǒng)的應(yīng)用by計算機科學(xué)與技術(shù)1401

張凱歌

人工智能課程設(shè)計匯報基于遺傳算法的TSP問題TSP問題，即旅行商問題。假設(shè)有一個旅行商人要拜訪n個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最后要回到原來出發(fā)的城市。路徑的選擇目標(biāo)是要求得的路徑路程為所有路徑之中的最小值。人工智能課程設(shè)計匯報遺傳算法求解TSP的基本步驟（1）種群初始化。個體編碼方法有：二進(jìn)制編碼和實數(shù)編碼。每一條染色體就是一種編碼，在解決TSP問題過程中個體編碼方法為實數(shù)編碼。對于TSP問題，實數(shù)編碼為1-n的實數(shù)的隨機排列。初始化的參數(shù)有城市個數(shù)，種群規(guī)模、進(jìn)化次數(shù)、交叉概率、變異概率人工智能課程設(shè)計匯報遺傳算法求解TSP的基本步驟（2）適應(yīng)度函數(shù)。在TSP問題中，任意兩個城市之間的距離D(i,j)已知，每個染色體（即n個城市的隨機排列）可計算出總距離。因此可將一個隨機全排列的總距離的倒數(shù)作為適應(yīng)度函數(shù)，即距離越短，適應(yīng)度函數(shù)越好，滿足TSP要求。人工智能課程設(shè)計匯報遺傳算法求解TSP的基本步驟（3）選擇操作。采用累計適應(yīng)度最高的選擇策略，即適應(yīng)度越好的個體被選擇的概率越大，同時在選擇中保存適應(yīng)度最高的個體。人工智能課程設(shè)計匯報遺傳算法求解TSP的基本步驟（4）交叉操作。相對于個體，隨機選擇兩個個體，隨機生成一個交叉位點。交換對應(yīng)位置兩側(cè)的基因片段，同時確保每個個體依然是1-n的隨機排列。人工智能課程設(shè)計匯報遺傳算法求解TSP的基本步驟（5）變異操作。隨機選取個體，隨機選取個體的兩個基因，進(jìn)行交換以實現(xiàn)變異操作。人工智能課程設(shè)計匯報流程圖人工智能課程設(shè)計匯報核心代碼#definenum_C10//城市個數(shù)#defineN10//群體規(guī)模#definepc0.9//交叉概率#definepm0.1//變異概率#definegenmax500//最大遺傳代數(shù)structgene//染色體結(jié)構(gòu){intpath[num_C];//路徑

doublecost;//個體代價值

doublefitness;//個體適應(yīng)度

doubleprobability;//適應(yīng)度

doubleaccumulation;//幸存概率};人工智能課程設(shè)計匯報核心代碼voidSelect(structgenegroup[N])//選擇{inti,j;intt=1;doublek;Cprobability(group);Caccumulation(group);for(i=0;i<N-1;i++){k=Randominteger(0,1);for(j=0;j<N-1;j++){if(k<group[j].accumulation){Copy_gene(&group[j],&group[t]);t++;break;}}}}voidCross(structgene*p,structgene*q)//交叉{inti,j,cross_point;intson1[num_C],son2[num_C];cross_point=Randominteger1(1,num_C-1);//隨機生成交叉位點

for(i=0;i<num_C;i++){son1[i]=-1;son2[i]=-1;}//子代1前半部分直接從父代p復(fù)制

for(i=0;i<cross_point;i++)son1[i]=p->path[i];//子代后半部分來自父代qfor(i=cross_point;i<num_C;i++){for(j=0;j<num_C;j++){if(Search_son(son1,q->path[j])==1){son1[i]=q->path[j];break;}人工智能課程設(shè)計匯報核心代碼voidVaration(structgenegroup[N])//變異{inti,j,k,temp,c;structgene*p;doubleflag;for(c=1;c<N;c++){flag=Randominteger(0,1);if(flag<pm){i=Randominteger1(1,N-1);//確定發(fā)生變異的個體

j=Randominteger1(0,num_C-1);//確定發(fā)生變異的位

k=Randominteger1(0,num_C-1);//確定發(fā)生變異的位

p=&group[i];//變異

temp=p->path[j]; p->path[j]=p->path[k]; p->path[k]=temp; Calculate_cost(p);//重新計算變異后路徑的代價

}}}人工智能課程設(shè)計匯報運行結(jié)果遺傳算法屬于啟發(fā)式算法,最終只能獲得最優(yōu)解的一個近似解。每次的運行結(jié)果也是有差別的。人工智能課程設(shè)計匯報產(chǎn)生式動物識別系統(tǒng)設(shè)計并實現(xiàn)具有15條規(guī)則能自動識別7種動物的產(chǎn)生式系統(tǒng)。知識庫與控制系統(tǒng)相互獨立，系統(tǒng)完成后除了能識別已有的7種動物外，按產(chǎn)生式知識表示方法向知識庫中添加、修改新的知識后，系統(tǒng)能在不修改控制系統(tǒng)程序的情況下仍然能正確識別。人工智能課程設(shè)計匯報設(shè)計知識庫知識用If前提t(yī)hen結(jié)論的形式來表示<知識庫><事實><條件>1:有毛發(fā)2:產(chǎn)奶3:有羽毛4:會飛5:會下蛋6:吃肉7:有犬齒8:有爪9:眼盯前方10:有蹄11:反芻12:黃褐色13:有斑點14:有黑色條紋15:長脖16:長腿17:不會飛18:會游泳19:黑白二色20:善飛</條件>人工智能課程設(shè)計匯報設(shè)計知識庫<中間結(jié)論>21:哺乳類22:鳥類23:食肉類24:蹄類</中間結(jié)論><結(jié)論>25:金錢豹26:虎27:長頸鹿28:斑馬29:鴕鳥30:企鵝31:信天翁</結(jié)論></事實>人工智能課程設(shè)計匯報設(shè)計知識庫<規(guī)則>有毛->哺乳類產(chǎn)奶->哺乳類有羽毛->鳥類會飛,會下蛋->鳥類哺乳類,吃肉->食肉類有犬齒,有爪,眼盯前方->食肉類哺乳類,有蹄->蹄類哺乳類,反芻->蹄類食肉類,黃褐色,有斑點->金錢豹食肉類,黃褐色,有黑色條紋->虎蹄類,長脖,長腿,有斑點->長頸鹿蹄類,有黑色條紋->斑馬鳥類,長脖,長腿,會飛->鴕鳥鳥類,會游泳,黑白二色,會飛->企鵝鳥類,善飛->信天翁</規(guī)則>人工智能課程設(shè)計匯報規(guī)則符號化1->21//有毛->哺乳類2->21//產(chǎn)奶->哺乳類3->22//有羽毛->鳥類4,5->22//會飛,會下蛋->鳥類21,6->23//哺乳類,吃肉->食肉類7,8,9->23//有犬齒,有爪,眼盯前方->食肉類21,10->24//哺乳類,有蹄->蹄類21,11->24//哺乳類,反芻->蹄類23,12,13->25//食肉類,黃褐色,有斑點->金錢豹23,12,14->26//食肉類,黃褐色,有黑色條紋->虎24,15,16,13->27//蹄類,長脖,長腿,有斑點->長頸鹿24,14->28//蹄類,有黑色條紋->斑馬22,15,16,4->29//鳥類,長脖,長腿,會飛->鴕鳥22,18,19,4->30//鳥類,會游泳,黑白二色,會飛->企鵝22,20->31//鳥類,善飛->信天翁人工智能課程設(shè)計匯報核心代碼stringfact[fact_num]={"有毛發(fā)","產(chǎn)奶","有羽毛","會飛","會下蛋","吃肉","有犬齒","有爪","眼盯前方","有蹄","反芻","黃褐色","有斑點","有黑色條紋","長脖","長腿","不會飛","會游泳","黑白二色","善飛","哺乳類","鳥類","食肉類","蹄類","金錢豹","虎","長頸鹿","斑馬","鴕鳥","企鵝","信天翁"};人工智能課程設(shè)計匯報核心代碼intrule_prerequisite[rule_num][rule_volume]={{1,0,0,0},{2,0,0,0},{3,0,0,0},{4,5,0,0},{21,6,0,0},{7,8,9,0},{21,10,0,0},{21,11,0,0},{23,12,13,0},{23,12,14,0},{24,15,16,13},{24,14,0,0},{22,15,16,4},{22,18,19,4},{22,20,0,0}};intrule_result[rule_num]={21,21,22,22,23,23,24,24,25,26,27,28,29,30,31};人工智能課程設(shè)計匯報核心代碼