遺傳算法解決TSP問題

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)遺傳算法解決TSP問題TSP問題所謂TSP問題（旅行商問題）即最短路徑問題就是在給定的起始點S到終止點T的通路集合中，尋求距離最小的通路，這樣的通路成為S點到T點的最短路徑。在尋找最短路徑問題上，有時不僅要知道兩個指定頂點間的最短路徑，還需要知道某個頂點到其他任意頂點間的最短路徑。用遺傳算法解決這類問題，沒有太多的約束條件和有關解的限制，因而可以很快地求出任意兩點間的最短路徑以及一批次短路徑。遺傳算法2.1 遺傳算法介紹遺傳算法是一種模擬生命進化機制的搜索和優(yōu)化方法，是

2、把自然遺傳學和計算機科學結合起來的優(yōu)化方程，有很強的解決問題的能力和廣泛的適應性。其假設常描述為二進制位串，位串的含義依賴于具體應用。搜索合適的假設從若干初始假設的群體集合開始。當前種群成員通過模仿生物進化的方式來產(chǎn)生下一代群體，如隨機變異和交叉。每一步，根據(jù)給定的適應度評估當前群體的假設，而后使用概率方法選出適應度最高的假設作為產(chǎn)生下一代的種子。下面介紹幾個遺傳算法的基本概念：（1）染色體（Chromosome）：在使用遺傳算法時，需要把問題的解編成一個適合的碼子。這種具有固定結構的符號串既是染色體，符號串的每一位代表一個基因。符號串的總位數(shù)成為染色體的長度，一個染色體就代表問題的一個解，每

3、個染色體也被稱為一個個體。（2）群體（Population）：每代所產(chǎn)生的染色體總數(shù)成為群體，一個群體包含了該問題在這一代的一些解的集合。（3）適應度（Fitness）：對群體中每個染色體進行編碼后，每個個體對應一個具體問題的解，而每個解對應于一個函數(shù)值。該函數(shù)值即適應函數(shù)，就是衡量染色體對環(huán)境適應度的指標，也是反映實際問題的目標函數(shù)在前一代群體的基礎上產(chǎn)生新一代群體的工作成為遺傳操作，基本的遺傳操作有：（1）選擇（Select）：按一定的概率從上代群體中選擇M對個體作為雙親，直接拷貝到下一代，染色體不發(fā)生變化。（2）交叉（Crossover）：對于選中進行繁殖的兩個染色體X，Y，以X，Y為雙

4、親作交叉操作，從而產(chǎn)生兩個后代X1，Y1.（3）變異（Mutation）：對于選中的群體中的個體（染色體），隨機選取某一位進行取反運算，即將該染色體碼翻轉。用遺傳算法求解的過程是根據(jù)待解決問題的參數(shù)集進行編碼，隨機產(chǎn)生一個種群，計算適應函數(shù)和選擇率，進行選擇、交叉、變異操作。如果滿足收斂條件，此種群為最好個體，否則，對產(chǎn)生的新一代群體重新進行選擇、交叉、變異操作，循環(huán)往復直到滿足條件。2.2 遺傳算法原型：GA(Fitness,Fitness_threshold,p,r,m)Fitness:適應度評分函數(shù),為給定假設賦予一個評估分數(shù)Fitness_threshold:指定終止判據(jù)的閾值p:群體

5、中包含的假設數(shù)量r:每一步中通過交叉取代群體成員的比例m:變異率初始化群體:P隨機產(chǎn)生的p個假設評估:對于P中的每一個h,計算Fitness(h)當maxFitness(h)Fitness_threshold,做產(chǎn)生新的一代Ps:1.選擇:用概率方法選擇P的(1-r)p個成員加入Ps.從P中選擇假設hi的概率用下面公式計算: QUOTE 2.交叉:根據(jù)上面給出的 QUOTE ,從P中按概率選擇r(p/2)對假設.對于每對假設,應用交叉算子產(chǎn)生兩個后代.把所有的后代加入Ps3.變異:使用均勻的概率從Ps中選擇m%的成員.對于選出的每個成員,在它表示中隨機選擇一個為取反4.更新:PPs5.評估:對

6、于P中的每個h計算Fitness(h)從P中返回適應度最高的假設TSP問題的遺傳算法設計與實現(xiàn)3.1 TSP問題的圖論描述求最短路徑問題，用圖論術語描述如下：在圖G(V,A)中，V表示頂點集合，V=(v1,v2,vn)對G中的某一邊(,)，相應的有一個數(shù)d(,)，如果G中不存在邊(,)，則令d(,)無窮大，如果把d(,)認為是邊(,)的長度，則通路的長度定義為組成路的各條邊的長度總和。頂點,之間是否有邊相連，由鄰接矩陣來決定。鄰接矩陣A：對一個具有v個頂點，e條邊的圖G的鄰接矩陣A=是一個vv階方陣，其中=1，表示和鄰接，=0表示vi和vj不相鄰接（或i=j）。3.2 染色體編碼對于一個給定的

7、圖模型，將圖中各頂點序號自然排序，然后按此順序?qū)⒚總€待選頂點作為染色體的一個基因，當基因值為1時，表示相應的頂點被選入該條路徑中，否則反之。此染色體中的基因排列順序即為各頂點在次條通路中出現(xiàn)的先后順序，染色體的長度應等于該圖中的頂點個數(shù)。在本程序的TSP問題中一共有20個城市，也就是在圖模型中有20個頂點，因此一個染色體的長度為20。3.3 適應函數(shù)f(i)對具有n個頂點的圖，已知各頂點之間(,)的邊長度d(,)，把到間的一條通路的路徑長度定義為適應函數(shù)： 對該最優(yōu)化問題，就是要尋找解，使f()值最小。3.4 選擇操作選擇作為交叉的雙親，是根據(jù)前代染色體的適應函數(shù)值所確定的，質(zhì)量好的個體，即從

8、起點到終點路徑長度短的個體被選中的概率較大。3.5 交叉與變異操作將被選中的兩個染色體進行交叉操作的過程是先產(chǎn)生一個隨機數(shù)，確定交叉點，位于染色體的第幾位基因上.然后在此位置進行部分基因交換。變異操作是將染色體中某位基因逆變，即由1變?yōu)?，或反之。變異的意義為在某條路徑上去掉或增加某頂點.但這樣做的結果并不一定能使路徑的長度減少。也就是說有可能使各代中產(chǎn)生的比較好的方案在遺傳過程中丟失，遲緩了獲得最優(yōu)解的速度。為了使算法盡可能快地獲得更好的解，改善遺傳算法的收斂性。在變異操作時，增加了個體求優(yōu)的自學習過程，即在某位基因變異后.計算新產(chǎn)生的染色體的適應函數(shù)值，若適應函數(shù)值更小，即獲得的路徑更短，

9、則保留;否則，保持原來的解不變。如果有連續(xù)N/3次沒有得到更好的解，則該過程結束。其中N表示從起點到終點的頂點數(shù)。3.6 TSP問題的遺傳算法的具體步驟解最短路徑的遺傳算法如下：Generatep(n);表示程序開始時要首先產(chǎn)生一個群體，群體個數(shù)為nEvaluatep(h);表示計算每個個體適應度，h是種群中的一個個體Repeat roof Generations times;重復下面的操作，直到滿足條件為止Select p(h) from p(n-1);表示從前一代群體中選擇一對雙親，用于交叉、變異 操作，P(n)代表第n代群體Crossover and mutation p(n);進行交叉

10、和變異操作Learningp(n);自學習過程Evaluatep(h);計算新生成的種群中每個個體的適應度End;實驗測試與結果分析交叉率不可選擇過小，否則，延緩獲得最優(yōu)解的過程，本程序選擇=0.85。變異率的選擇對規(guī)模大的優(yōu)化問題影響很大，本程序選=0.1。 群體中的個體數(shù)的選取是算法中一個很重要的參數(shù)，群體中的個體數(shù)目越大，算法就越能找到更好的解，個體數(shù)目過小，有可能找不到最優(yōu)解。本程序種群大小為300。因為有20個城市，每個城市作為染色體中的一個基因，因此在本程序中染色體的長度為20。本程序的循環(huán)終止的條件是迭代次數(shù)不大于100，因此，最大迭代次數(shù)為100。本程序中總共運行10次，得到每

11、次最好的路徑、回路總開銷和適應度。程序的運行結果如下：參考文獻1 遺傳書算法理論、應用與軟件實現(xiàn),王小平、曹立明,西安交通大學出版社,20022 機器學習,Tom M.Mitchell 機械工業(yè)出版社,2009源代碼清單：#include #include #include #include #include #include #include using namespace std;float pcross = 0.85; /交叉率float pmutation = 0.1; /變異率int popsize = 300; /種群大小const int lchrom = 20; /染色體長度i

12、nt gen; /當前世代int maxgen = 100; /最大世代數(shù)int run; /當前運行次數(shù)int maxruns =10; /總運行次數(shù)float max_var = 9 ; /路徑最大連接開銷!/基因定義(一個城市)struct Genestring name;map linkCost; /該城市到其它城市的路程開銷;/染色體定義(到各城市順序的一種組合)struct Chromvector chrom_gene; /染色體（到各城市去的順序）float varible; /路程總開銷float fitness; /個體適應度 ;/種群定義struct Popvector p

13、op_chrom; /種群里的染色體組 float sumfitness; /種群中個體適應度累計 ;Pop oldpop; /當前代種群Pop newpop; /新一代種群vector genes(lchrom); /保存全部基因/產(chǎn)生一個隨機整數(shù)(在low和high之間)inline int randomInt(int low,int high)if(low=high)return low;return low+rand()%(high-low+1);/計算一條染色體的個體適應度inline void chromCost(Chrom& chr)float sum=0;for(int i=0

14、;ilinkCostchr.chrom_genei+1;sum += (chr.chrom_gene.front()-linkCostchr.chrom_gene.back();chr.varible=sum;chr.fitness=max_var*(lchrom) - chr.varible;/計算一個種群的個體適應度之和inline void popCost(Pop &pop)float sum=0;for(int i=0;ipop.pop_chrom.size();i+)sum+=pop.pop_chromi.fitness;pop.sumfitness = sum;void outCh

15、rom(Chrom& chr);/隨機初始化一條染色體inline void initChrom(Chrom& chr)vector tmp(lchrom);for(int i=0;i1)choose=randomInt(0,tmp.size()-1);chr.chrom_gene.push_back(&genestmpchoose);tmp.erase(tmp.begin()+choose);chr.chrom_gene.push_back(&genestmp0);chromCost(chr);/隨機初始化種群inline void initpop(Pop& pop)pop.pop_chro

16、m.reserve(popsize);Chrom tmp;tmp.chrom_gene.reserve(lchrom);for(int i=0;i pick) | i=pop.pop_chrom.size()-1)return i-1; /?為什么返回29就會出錯？elsereturn randomInt(0,pop.pop_chrom.size()-2);/精英策略，返回最優(yōu)秀的一條染色體inline int chooseBest(const Pop& pop)int choose = 0;float best = 0;for(int i = 0;i best)best = pop.pop_

17、chromi.fitness;choose = i;return choose;/染色體交叉操作,由兩個父代產(chǎn)生兩個子代(順序交叉OX)inline void crossover(Chrom& parent1,Chrom& parent2,Chrom& child1,Chrom& child2)child1.chrom_gene.resize(lchrom);child2.chrom_gene.resize(lchrom);vector:iterator v_iter,p1_beg,p2_beg,c1_beg,c2_beg,p1_end,p2_end,c1_end,c2_endp1_beg =

18、 parent1.chrom_gene.begin(); p2_beg = parent2.chrom_gene.begin();c1_beg = child1.chrom_gene.begin(); c2_beg = child2.chrom_gene.begin();p1_end = parent1.chrom_gene.end(); p2_end = parent2.chrom_gene.end();c1_end = child1.chrom_gene.end(); c2_end = child2.chrom_gene.end();vector v1(parent2.chrom_gene

19、), v2(parent1.chrom_gene); /用于交叉的臨時表/隨機選擇兩個交叉點 int pick1 = randomInt(1,lchrom-3);int pick2 = randomInt(pick1+1,lchrom-2);int dist = lchrom-1-pick2; /第二交叉點到尾部的距離/子代保持兩交叉點間的基因不變copy(p1_beg+pick1, p1_beg+pick2+1, c1_beg+pick1); copy(p2_beg+pick1, p2_beg+pick2+1, c2_beg+pick1);/循環(huán)移動表中元素rotate(v1.begin()

20、, v1.begin()+pick2+1,v1.end(); rotate(v2.begin(), v2.begin()+pick2+1,v2.end();/從表中除去父代已有的元素for(v_iter = p1_beg+pick1; v_iter!=p1_beg+pick2+1; +v_iter)remove(v1.begin(),v1.end(),*v_iter);for(v_iter = p2_beg+pick1; v_iter!=p2_beg+pick2+1; +v_iter)remove(v2.begin(),v2.end(),*v_iter);/把表中元素復制到子代中copy(v1

21、.begin(), v1.begin()+dist, c1_beg+pick2+1);copy(v1.begin()+dist, v1.begin()+dist+pick1, c1_beg);copy(v2.begin(), v2.begin()+dist, c2_beg+pick2+1);copy(v2.begin()+dist, v2.begin()+dist+pick1, c2_beg);/染色體變異操作,隨機交換兩個基因inline void mutation(Chrom& chr)vector:iterator beg = chr.chrom_gene.begin();int pic

22、k1,pick2;pick1 = randomInt(0,lchrom-1);dopick2 =randomInt(0,lchrom-1);while(pick1=pick2);iter_swap(beg+pick1, beg+pick2);/世代進化(由當前種群產(chǎn)生新種群)void generation(Pop& oldpop,Pop& newpop)newpop.pop_chrom.resize(popsize);int mate1,mate2,j;float pick;float tmp;Chrom gene1,gene2,tmp1,tmp2;gene1.chrom_gene.resiz

23、e(lchrom);gene2.chrom_gene.resize(lchrom);tmp1.chrom_gene.resize(lchrom);tmp2.chrom_gene.resize(lchrom);/將最佳染色體放入下一代mate1 = chooseBest(oldpop);newpop.pop_chrom0 = oldpop.pop_chrommate1; j = 1;/產(chǎn)生兩條新染色體doint count = 0;mate1 = selectChrom(oldpop);mate2 = selectChrom(oldpop);pick = float(randomInt(0,10

24、00)/1000;gene1= oldpop.pop_chrommate1;gene2= oldpop.pop_chrommate1;if(pick gene1.fitness)gene1 = tmp1;flag1 = true;if(tmp2.fitness gene2.fitness)gene2 = tmp2;flag2 = true;if(flag1=true & flag2=true) | count 50)newpop.pop_chromj = gene1; newpop.pop_chromj+1 = gene2;break;count+;elsenewpop.pop_chromj.

25、chrom_gene = oldpop.pop_chrommate1.chrom_gene;newpop.pop_chromj+1.chrom_gene = oldpop.pop_chrommate2.chrom_gene;chromCost(newpop.pop_chromj);chromCost(newpop.pop_chromj+1);pick = float(randomInt(0,1000)/1000;if(pick newpop.pop_chromj.fitness & count 50);pick = float(randomInt(0,1000)/1000;if(pick ne

26、wpop.pop_chromj+1.fitness & count 50);/chromCost(newpop.pop_chromj); /計算適應度/chromCost(newpop.pop_chromj+1);j += 2;while(j popsize-1);popCost(newpop); /計算新種群的適應度之和/輸出一條染色體信息inline void outChrom(Chrom& chr)coutendl路徑:;for(int i=0;ilchrom;i+)coutname;coutendl回路總開銷:chr.varibleendl;cout適應度:chr.fitnessend

27、l;int main()cout*用遺傳算法解決TSP(旅行商)問題*endl;stringnameslchrom=A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T;/基因（城市）名稱/用矩陣保存各城市間的路程開銷float distlchromlchrom =0, 1, 4, 6, 8, 1, 3, 7, 2, 9, 7, 3, 4, 5, 8, 9, 2, 8, 2, 8,1, 0, 7, 5, 3, 8, 3, 4, 2, 4, 4, 6, 2, 8, 2, 9, 4, 5, 2, 1,4, 7, 0, 3, 8, 3, 7, 9, 1, 2, 5, 8,

28、1, 8, 9, 4, 7, 4, 8, 4,6, 5, 3, 0, 3, 1, 5, 2, 9, 1, 3, 5, 7, 3, 4, 7, 3, 4, 5, 2,8, 3, 8, 3, 0, 2, 3, 1, 4, 6, 3, 8, 4, 5, 2, 8, 1, 7, 4, 7,1, 8, 3, 1, 2, 0, 3, 3, 9, 5, 4, 5, 2, 7, 3, 6, 2, 3, 7, 1,3, 3, 7, 5, 3, 3, 0, 7, 5, 9, 3, 4, 5, 9, 3, 7, 3, 2, 8, 1,7, 4, 9, 2, 1, 3, 7, 0, 1, 3, 4, 5, 2, 7,

29、 6, 3, 3, 8, 3, 5,2, 2, 1, 9, 4, 9, 5, 1, 0, 1, 3, 4, 7, 3, 7, 5, 9, 2, 1, 7,9, 4, 2, 1, 6, 5, 9, 3, 1, 0, 3, 7, 3, 7, 4, 9, 3, 5, 2, 5,7, 4, 5, 3, 3, 4, 3, 4, 3, 3, 0, 5, 7, 8, 4, 3, 1, 5, 9, 3,3, 6, 8, 5, 8, 5, 4, 5, 4, 7, 5, 0, 8, 3, 1, 5, 8, 5, 8, 3,4, 2, 1, 7, 4, 2, 5, 2, 7, 3, 7, 8, 0, 5, 7, 4

30、, 8, 3, 5, 3,5, 8, 8, 3, 5, 7, 9, 7, 3, 7, 8, 3, 5, 0, 8, 3, 1, 8, 4, 5,8, 2, 9, 4, 2, 3, 3, 6, 7, 4, 4, 1, 7, 8, 0, 4, 2, 1, 8, 4,9, 9, 4, 7, 8, 6, 7, 3, 5, 9, 3, 5, 4, 3, 4, 0, 4, 1, 8, 4,2, 4, 7, 3, 1, 2, 3, 3, 9, 3, 1, 8, 8, 1, 2, 4, 0, 4, 3, 7,8, 5, 4, 4, 7, 3, 2, 8, 2, 5, 5, 5, 3, 8, 1, 1, 4, 0, 2, 6,2, 2, 8, 5, 4, 7, 8, 3, 1, 2, 9, 8, 5, 4, 8, 8, 3, 2, 0, 4,8, 1, 4, 2, 7, 1, 1, 5, 7, 5, 3, 3,