遺傳算法解決商旅問題

1、精選優(yōu)質(zhì)文檔-傾情為你奉上人工智能導(dǎo)論實(shí)驗(yàn)報(bào)告之二遺傳算法解決商旅問題 專業(yè)班級(jí)：計(jì)0901姓 名：薛彬?qū)W 號(hào)：6電子信箱：手機(jī)號(hào)碼：提交日期：2012年6月04日指導(dǎo)老師：程國(guó)建實(shí)驗(yàn)成績(jī)：一.問題描述：TSP是一個(gè)具有廣泛應(yīng)用背景和重要理論價(jià)值的組合優(yōu)化難題，TSP問題可以簡(jiǎn)單的描述為：已知N個(gè)城市之間的相互距離現(xiàn)有一個(gè)旅行商必須遍歷這N個(gè)城市，并且每個(gè)城市只能訪一次，最后必須返回出發(fā)城市。如何安排他對(duì)這些城市的訪問次序，可使旅行路線的總長(zhǎng)度最短？二.需求分析：TSP已經(jīng)被證明是一個(gè)NPHard問題，即找不到一種算法能在多項(xiàng)式時(shí)間內(nèi)求得問題的最優(yōu)解。利用遺傳算法，在一定時(shí)間內(nèi)求得近似最優(yōu)解的

2、可能性比較大。實(shí)驗(yàn)?zāi)繕?biāo)是：1）設(shè)計(jì)用遺傳算法解決TSP問題的程序；2）求出該TSP問題的（近似）最短路程；3）求得相應(yīng)的城市遍歷序列；4）檢查算法收斂性，求解決該問題的（近似）最優(yōu)遺傳參數(shù)。三.算法分析：1 算法描述與基本流程(1) 編碼 遺傳算法先將解空間的解數(shù)據(jù)表示成遺傳空間的基因型串結(jié)構(gòu)數(shù)據(jù)，他們的不同組合就構(gòu)成了不同的點(diǎn)。 (2) 生成初始種群 采用隨機(jī)的方法產(chǎn)生若干個(gè)初始串結(jié)構(gòu)數(shù)據(jù)，每個(gè)串結(jié)構(gòu)數(shù)據(jù)代表一個(gè)個(gè)體，全體初始串結(jié)構(gòu)數(shù)據(jù)構(gòu)了初始種群。種群的大小一般是20100，這樣既可以提高遺傳算法的穩(wěn)定型，又能夠保證種群的多樣性，容易獲得全局最優(yōu)解。 (3) 適應(yīng)度評(píng)估 對(duì)于不同的優(yōu)化問題

3、，采用不同的適應(yīng)度函數(shù)來評(píng)價(jià)個(gè)體的優(yōu)劣性。通常有一些常用的帶欺騙性的函數(shù)用于測(cè)試。 (4) 選擇 按照適者生存的目的，從當(dāng)前的種群中選擇出適應(yīng)度強(qiáng)的優(yōu)良個(gè)體，使它們有機(jī)會(huì)作為父代產(chǎn)生下一代，適應(yīng)度強(qiáng)的個(gè)體被選擇的概率大。 (5) 交叉 交叉算子根據(jù)交叉率將種群中兩個(gè)個(gè)體隨機(jī)的交換某些基因，從而產(chǎn)生新一代個(gè)體。新個(gè)體組合了父輩個(gè)體的特性。交叉率根據(jù)具體問題確定，一般取0.250.75，這樣既可以得到高適應(yīng)度的結(jié)構(gòu)，又可以保證搜索效率。 (6) 變異 變異算子根據(jù)交叉率隨機(jī)地在當(dāng)前種群中選擇一個(gè)個(gè)體，對(duì)其以一定的概率隨機(jī)地改變串結(jié)構(gòu)數(shù)據(jù)中的某個(gè)串的數(shù)值，從而產(chǎn)生新一代個(gè)體。變異率不宜取得過高，一般

4、取0.0050.20。初始群體生成選擇交叉變異群體適應(yīng)度計(jì)算結(jié)束輸出結(jié)果YN計(jì)算適應(yīng)度并輸出2 編碼策略與初始群體設(shè)定TSP的一般編碼策略主要有二進(jìn)制表示、次序表示、路徑表示、矩陣表示和邊表示等。而路徑編碼是最直觀的方式，以城市序號(hào)作為遺傳基因。在本實(shí)驗(yàn)中，我們用一個(gè)N維向量來表示一個(gè)個(gè)體，N是城市總數(shù)，元素表示城市遍歷順序，以最后一個(gè)到達(dá)的城市為結(jié)束。則群體用一個(gè)N * POP的矩陣表示，POP為群體中的人口（個(gè)體數(shù)）。初始群體在空間中自動(dòng)生成。3 適應(yīng)度函數(shù)及結(jié)束條件適應(yīng)度函數(shù)采用題目的目標(biāo)函數(shù)路徑的總路程（包括回到出發(fā)點(diǎn)）。適應(yīng)度越低，個(gè)體越優(yōu)秀。由于暫時(shí)無法先驗(yàn)估計(jì)收斂性和目標(biāo)結(jié)果，所

5、以以一個(gè)參數(shù)，最大遺傳代數(shù)MAXGEN作為程序結(jié)束控制。4 遺傳算子設(shè)計(jì)遺傳算子的設(shè)計(jì)方法主要有兩大類：自然算法和貪心算法。自然算法是以大自然的進(jìn)化規(guī)律為依據(jù)，大體采用“優(yōu)勝劣汰”的機(jī)制來進(jìn)行遺傳；貪心算法則是以迅速收斂為目標(biāo)，對(duì)個(gè)體進(jìn)行更嚴(yán)格的選擇和遺傳處理。本實(shí)驗(yàn)中，為了更好地研究遺傳算法的內(nèi)部原理和收斂性質(zhì)，我們偏向采用自然算法設(shè)計(jì)算子。以下是各算子的設(shè)計(jì)：選擇算子在遺傳個(gè)體的選擇上，我們先人工保留最優(yōu)種子，再采用輪盤賭法選擇保留一部分個(gè)體，用輪盤賭法的理由是在“擇優(yōu)錄取”的原則上增加選擇的隨機(jī)性。在輪盤賭過程中，如果按適應(yīng)度來劃分，將導(dǎo)致適應(yīng)度高的劣質(zhì)個(gè)體被選擇的概率更大，于是我們?cè)O(shè)計(jì)

6、了一個(gè)變換，用最壞適應(yīng)度減去該個(gè)體的適應(yīng)度，再進(jìn)行輪盤賭選擇。另外，為了保持群體的“生命力”，我們?cè)谶x擇的同時(shí)又引入隨機(jī)的新個(gè)體，與保留的個(gè)體進(jìn)行“雜交”，產(chǎn)生下一代。交叉算子我們采用的是Davis等提出順序交叉、雙親雙子遺傳的算法。隨機(jī)選擇兩個(gè)交叉點(diǎn)A、B（0ABN），兩個(gè)父序列中交叉點(diǎn)之間的部分交叉復(fù)制給兩個(gè)子代，其余部分則按順序不重復(fù)填充到對(duì)應(yīng)子代序列中。遺傳中進(jìn)行交叉操作的概率為參數(shù)PXOVER。變異算子個(gè)體發(fā)生變異的概率為參數(shù)PMUTATION。當(dāng)一個(gè)個(gè)體發(fā)生變異時(shí)，隨機(jī)選擇序列中一個(gè)基因與其相鄰基因交換。其他部分?jǐn)?shù)據(jù)輸入為直接讀取城市距離矩陣文本，本例中為ctsp.txt；數(shù)據(jù)輸出

7、格式為：每代的最佳適應(yīng)度，平均適應(yīng)度和標(biāo)準(zhǔn)差，最終結(jié)果序列和相關(guān)參數(shù)。文件名galog.txt。四.程序源代碼及運(yùn)行結(jié)果#include #include #include struct node/建立結(jié)點(diǎn)結(jié)構(gòu)體int label;int former;int access100;int weight100;int c_p;node* f100;int flag100;int scount;int source;/int length=0;int parent=-10;int answer100101;int an_p=0;void convert(int a100,char b100)/轉(zhuǎn)變

8、算法for(int i=0;i100;i+)ai=bi-48;bi=0;void init()node* temp;int count=0;char t_a100;char t_w100;for(int i=0;i100;i+)flagi=-5;for(int j=0;j100;j+) answerij=-5;answeri100=9999;doprintf(please input a new node:n);/建立一個(gè)新的節(jié)點(diǎn)printf(label: %dn,count);/節(jié)點(diǎn)數(shù)目printf(access:n);/進(jìn)入節(jié)點(diǎn)的許可scanf(%s,t_a);printf(weight:

9、n);/輸入路徑長(zhǎng)度scanf(%s,t_w);if(strcmp(t_a,end)/輸入結(jié)束語(yǔ)temp=(node *)malloc(sizeof(node);(*temp).label=count;(*temp).former=-5;(*temp).c_p=0;convert(*temp).access,t_a);convert(*temp).weight,t_w);fcount=temp;flagcount=0;count+;while(strcmp(t_a,end);/輸入結(jié)束語(yǔ)結(jié)束則輸入元結(jié)點(diǎn)scount=count;printf(please input the source no

10、de:n);scanf(%d,&source);int check(int f100)/檢查函數(shù)for(int i=0;iscount;i+)if(fi=0)return i;return -1;int search(node* node)/搜索函數(shù)for(int i=(* node).c_p;i0;i-)answeran_pi=tp;temp=tp;tp=(*ftp).former;sum+=(*ftp).weighttemp;answeran_p0=source;answeran_p100=sum+(*fn).weightsource;an_p+;int fetch(int n)/定義路線

11、int t=0;int l=0;int x=0;/*if(n!=0)l=(*fparent).weightn;elsel=0;*/if(n=0&flagn!=1)flagn=1;(*fn).former=parent;/length+=l;if(n!=source)search(fparent);if(check(flag)=-1)/ all the nodes has been visitedif(verify(n)/ current node has access to the sourcerecord(n);flagn=0;/roll back(*fn).former=-5;/lengt

12、h-=l;fetch(*fparent).c_p-1);else/ keep expanding dot=search(fn);while(flagt!=0&t!=-5);if(flagt=0&t!=-5)/ find a node to expandparent=n;fetch(t);else if(t=-5)flagn=0;/roll back(*fn).former=-5;/length-=l;(*fn).c_p=0;fetch(*fparent).c_p-1);else if(flagn=1)search(fparent);fetch(*fparent).c_p-1);else if(

13、n=scount)if(*fparent).former=-10)printf(the work is done!n);return 0;elseflagparent=0;/length-=(*f(*fparent).former).weightparent;x=(*fparent).former;(*fparent).former=-5;(*fparent).c_p=0;parent=x;fetch(*fparent).c_p-1);void plot()/繪制路線int i=0;int pointer=0;int temp=9999;while(answeri0!=-5)/*printf(the path is:);for(int j=0;j,answerij);printf(%dlength: %dn,source,answeri