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

張凱歌

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

doublecost;//個(gè)體代價(jià)值

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

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

doubleaccumulation;//幸存概率};人工智能課程設(shè)計(jì)匯報(bào)核心代碼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);//隨機(jī)生成交叉位點(diǎn)

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];//子代后半部分來(lá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è)計(jì)匯報(bào)核心代碼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ā)生變異的個(gè)體

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);//重新計(jì)算變異后路徑的代價(jià)

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