tsp問(wèn)題的遺傳算法求解

1、TSP問(wèn)題的遺傳算法求解摘要摘要：遺傳算法是模擬生物進(jìn)化過(guò)程的一種新的全局優(yōu)化搜索算法，本文簡(jiǎn)單介紹了遺傳算法，并應(yīng)用標(biāo)準(zhǔn)遺傳算法對(duì)旅行包問(wèn)題進(jìn)行求解。關(guān)鍵詞關(guān)鍵詞：遺傳算法、旅行包問(wèn)題一、一、旅行包問(wèn)題描述：旅行包問(wèn)題描述：旅行商問(wèn)題，即TSP問(wèn)題（TravelingSalemanProblem）是數(shù)學(xué)領(lǐng)域的一個(gè)著名問(wèn)題，也稱作貨郎擔(dān)問(wèn)題，簡(jiǎn)單描述為：一個(gè)旅行商需要拜訪n個(gè)城市（1，2，…，n），他必須選擇所走的路徑，每個(gè)城市只能拜訪

2、一次，最后回到原來(lái)出發(fā)的城市，使得所走的路徑最短。其最早的描述是1759年歐拉研究的騎士周游問(wèn)題，對(duì)于國(guó)際象棋棋盤(pán)中的64個(gè)方格，走訪64個(gè)方格一次且最終返回起始點(diǎn)。用圖論解釋為有一個(gè)圖G=（VE），其中V是頂點(diǎn)集，E是邊集，設(shè)D=（dij）是有頂點(diǎn)i和頂點(diǎn)j之間的距離所組成的距離矩陣，旅行商問(wèn)題就是求出一條通過(guò)所有頂點(diǎn)且每個(gè)頂點(diǎn)只能通過(guò)一次的具有最短距離的回路。若對(duì)于城市V=v1，v2，v3，...，vn的一個(gè)訪問(wèn)順序?yàn)門(mén)=(t1，t

3、2，t3，…，ti，…，tn)，其中ti∈V(i=1，2，3，…，n)，且記tn1=t1，則旅行商問(wèn)題的數(shù)學(xué)模型為：minL=Σd(t(i)t(i1))（i=1，…，n）旅行商問(wèn)題是一個(gè)典型組合優(yōu)化的問(wèn)題，是一個(gè)NP難問(wèn)題，其可能的路徑數(shù)為（n1）！，隨著城市數(shù)目的增加，路徑數(shù)急劇增加，對(duì)與小規(guī)模的旅行商問(wèn)題，可以采取窮舉法得到最優(yōu)路徑，但對(duì)于大型旅行商問(wèn)題，則很難采用窮舉法進(jìn)行計(jì)算。在生活中TSP有著廣泛的應(yīng)用，在交通方面，如何規(guī)劃合

4、理高效的道路交通，以減少擁堵；在物流方面，更好的規(guī)劃物流，減少運(yùn)營(yíng)成本；在互聯(lián)網(wǎng)中，如何設(shè)置節(jié)點(diǎn)，更好的讓信息流動(dòng)。許多實(shí)際工程問(wèn)題屬于大規(guī)模TSP，Kte于1988年提出的VLSI芯片加工問(wèn)題可以對(duì)應(yīng)于1.2e6的城市TSP，Bl于1989年提出Xray衍射問(wèn)題對(duì)應(yīng)于14000城市TSP，Litke于1984年提出電路板設(shè)計(jì)中鉆孔問(wèn)題對(duì)應(yīng)于17000城市TSP，以及2、確定適配值函數(shù)。3、遺傳算子的設(shè)計(jì)。4、算法參數(shù)（種群數(shù)目、交叉與

5、變異概率和進(jìn)化代數(shù)等）的選取。5、確定函數(shù)終止條件。三、三、對(duì)TSPTSP問(wèn)題的遺傳算法實(shí)現(xiàn)問(wèn)題的遺傳算法實(shí)現(xiàn)設(shè)計(jì)思路：1、初始化城市距離采用一個(gè)city_xy函數(shù)獲取n個(gè)城市的TSP問(wèn)題的坐標(biāo)，保存在city矩陣中，并且用city_dis矩陣表示任意兩個(gè)城市之間的距離，矩陣中的元素city_dis（i，j)代表第i個(gè)城市與第j個(gè)城市間的距離。2、初始化種群通過(guò)rperm函數(shù)，生成一個(gè)一維隨機(jī)向量（是整數(shù)1，2，3，4，5的任意排列），

6、然后將其賦給二維數(shù)組group的第一列，作為一個(gè)個(gè)體。如此循環(huán)N次，生成了第一代種群，種群的每個(gè)個(gè)體代表一條路徑。3、計(jì)算適應(yīng)度采用的適應(yīng)度函數(shù)為個(gè)體巡回路徑的總長(zhǎng)度的函數(shù)。具體為adapt(1i)=(nmaxdisdis)(1)在式（1）中，adapt(1i)表示第i個(gè)個(gè)體的適應(yīng)度函數(shù)，maxdis為城市間的最大距離，dis為個(gè)體巡回路徑的總長(zhǎng)度，這樣定義的適應(yīng)度，當(dāng)路經(jīng)越短時(shí)適應(yīng)度值越大。在適應(yīng)度值的基礎(chǔ)上，給出的計(jì)算個(gè)體期望復(fù)制數(shù)

7、的表達(dá)式為adaptnum(1i)=(Nadapt(1i)sumadapt)(2)其中，sumadapt為種群適應(yīng)度之和。4、復(fù)制采用優(yōu)秀個(gè)體的大比例保護(hù)基礎(chǔ)上的隨機(jī)數(shù)復(fù)制法。具體做法為在生成下一代個(gè)體時(shí)，先將最大適應(yīng)度對(duì)應(yīng)的路徑個(gè)體以較大的比例復(fù)制到下一代，然后再用隨機(jī)數(shù)復(fù)制法生成下一代的其他個(gè)體。其中，有一個(gè)問(wèn)題必須考慮，即若某一次生成的隨機(jī)數(shù)過(guò)大，結(jié)果能復(fù)制一個(gè)或極少個(gè)樣本。為了避免這一情況，采用了限制措施，即壓低了隨機(jī)數(shù)的上限。