遺傳算法解決商旅問題

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

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

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

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

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

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

7、格式為：每代的最佳適應度，平均適應度和標準差，最終結(jié)果序列和相關(guān)參數(shù)。文件名galog.txt。四.程序源代碼及運行結(jié)果#include #include #include struct node/建立結(jié)點結(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);/建立一個新的節(jié)點printf(label: %dn,count);/節(jié)點數(shù)目printf(access:n);/進入節(jié)點的許可scanf(%s,t_a);printf(weight:

9、n);/輸入路徑長度scanf(%s,t_w);if(strcmp(t_a,end)/輸入結(jié)束語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é)束語結(jié)束則輸入元結(jié)點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