遺傳算法解決TSP問題

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

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

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

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

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

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

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

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

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

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

11、次最好的路徑、回路總開銷和適應(yīng)度。程序的運(yùn)行結(jié)果如下：參考文獻(xiàn)1 遺傳書算法理論、應(yīng)用與軟件實(shí)現(xiàn),王小平、曹立明,西安交通大學(xué)出版社,20022 機(jī)器學(xué)習(xí),Tom M.Mitchell 機(jī)械工業(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; /染色體長(zhǎng)度i

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

13、op_chrom; /種群里的染色體組 float sumfitness; /種群中個(gè)體適應(yīng)度累計(jì) ;Pop oldpop; /當(dāng)前代種群Pop newpop; /新一代種群vector genes(lchrom); /保存全部基因/產(chǎn)生一個(gè)隨機(jī)整數(shù)(在low和high之間)inline int randomInt(int low,int high)if(low=high)return low;return low+rand()%(high-low+1);/計(jì)算一條染色體的個(gè)體適應(yīng)度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;/計(jì)算一個(gè)種群的個(gè)體適應(yīng)度之和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);/隨機(jī)初始化一條染色體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);/隨機(jī)初始化種群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就會(huì)出錯(cuò)？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;/染色體交叉操作,由兩個(gè)父代產(chǎn)生兩個(gè)子代(順序交叉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); /用于交叉的臨時(shí)表/隨機(jī)選擇兩個(gè)交叉點(diǎn) int pick1 = randomInt(1,lchrom-3);int pick2 = randomInt(pick1+1,lchrom-2);int dist = lchrom-1-pick2; /第二交叉點(diǎn)到尾部的距離/子代保持兩交叉點(diǎn)間的基因不變copy(p1_beg+pick1, p1_beg+pick2+1, c1_beg+pick1); copy(p2_beg+pick1, p2_beg+pick2+1, c2_beg+pick1);/循環(huán)移動(dòng)表中元素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);/把表中元素復(fù)制到子代中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);/染色體變異操作,隨機(jī)交換兩個(gè)基因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);/世代進(jìn)化(由當(dāng)前種群產(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); /計(jì)算適應(yīng)度/chromCost(newpop.pop_chromj+1);j += 2;while(j popsize-1);popCost(newpop); /計(jì)算新種群的適應(yīng)度之和/輸出一條染色體信息inline void outChrom(Chrom& chr)coutendl路徑:;for(int i=0;ilchrom;i+)coutname;coutendl回路總開銷:chr.varibleendl;cout適應(yīng)度: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,