【文章內(nèi)容簡(jiǎn)介】 效地解決 TSP 問題有著極高的實(shí)際應(yīng)用價(jià)值，也就吸引了眾多領(lǐng)域的學(xué)者對(duì)它進(jìn)行研究。盡管 TSP 仍未找到最優(yōu)解，但是求解它的算法逐漸在改進(jìn)。 1954 年 Dantzig， Fulkerson 和 Johnson 解決了 49個(gè)城市數(shù)目的 TSP 問題，經(jīng)過半個(gè)世紀(jì)的研究，目前，最大的已成功求解的旅行商問題有 24798 個(gè)城市。 TSP 問題的分類 從 TSP問題映射到圖的類型 ,可以分為兩類 : (1)城市間的距離都是對(duì)稱的 ,它對(duì)應(yīng)的是圖論中的無(wú)向圖 。 (2)兩個(gè)城市 間的距離是非對(duì)稱的 ,它所對(duì)應(yīng)的是圖論中的有向圖 . 從問題本身的限制條件的強(qiáng)弱 ,可分為三類 : (但是一般都要求城市間的費(fèi)用不為負(fù)數(shù) ),只是給出距離矩陣 ,求最小回路 。 。 TSP 問題 ,即 EuclidTSP,它給出每個(gè)點(diǎn)在歐式平面 上的坐標(biāo) ,而城市間的距離就是以他們的歐式距離來(lái)定義 . 10 現(xiàn)有的求解 TSP 問題的幾種算法 在求解 TSP的算法的過程中，人們一直在尋找切實(shí)有效的方法，按招時(shí)間出現(xiàn)的順序大致可分為：傳統(tǒng)算法和智能演化算法。 傳統(tǒng)算法有精確算法和近似優(yōu)化算法，精確算法又有線性規(guī)劃方法、動(dòng)態(tài)規(guī)劃方法、分支定界方法等，而近似算法有插入法、最近鄰算法、 ropt 算法、混合算法、概率算法等。 雖然傳統(tǒng)算法能夠找 TSP 問題的最優(yōu)解，但隨著問題規(guī)模的不斷增長(zhǎng)，算法所需要的時(shí)間非常巨大，因此只適用于求解規(guī)模較小的 TSP 問題。 20 世紀(jì) 80 年代以來(lái)，一些新穎的智能優(yōu)化算法，如模擬退火、遺傳算法、禁忌搜索、人工神經(jīng)網(wǎng)絡(luò)、蟻群算法、粒子群算法、郭濤算法、免疫算法等，通過模擬或揭示某些自然現(xiàn)象 (或過程 )而得到發(fā)展，其思想和內(nèi)容涉及數(shù)學(xué)、物理學(xué)、生物進(jìn) 化、人工智能、神經(jīng)科學(xué)和統(tǒng)計(jì)力學(xué)等方面，為解決復(fù)雜問題提供了新的思路和手段．由于這些算法構(gòu)造的直觀性和自然機(jī)理，通常稱作智能演化算法，或稱為現(xiàn)代啟發(fā)式算法。引入智能演化算法的原因在于避免陷人局部最優(yōu)解，希望得到更好的解上界。 (1)禁忌搜索算法 禁忌搜索算法是局部領(lǐng)域搜索算法的推廣，主要思想是標(biāo)記已經(jīng)得到的局部最優(yōu)解，并在進(jìn)一步的迭代中避開這些局部最優(yōu)解。此方法需較 強(qiáng)技術(shù)性，禁忌長(zhǎng)度較難取。若禁忌長(zhǎng)度過長(zhǎng)，則所需內(nèi)存較大，否則， 易陷入局部最優(yōu)解。 (2)模擬退火算法 這是一種源于五十年代、基于 Monte Carlo 迭代求解思想的隨機(jī)搜索算法，八十年代才開始應(yīng)用于組合優(yōu)化領(lǐng)域，其出發(fā)點(diǎn)是將組合優(yōu)化問題與統(tǒng)計(jì)力學(xué)的熱平衡作類比，把優(yōu)化的目標(biāo)函數(shù)視作能量函數(shù)，模仿物理學(xué)中固體物質(zhì)的退火處理，先加溫使之具有足夠高的能量，然后再逐漸降溫，其內(nèi)部能量也相應(yīng)下降，在熱平衡條件下，物體內(nèi)部處于不同狀態(tài)的概率服從 Boltzmann分布，若退火步驟恰當(dāng)，則最終會(huì)形成最低能量的基態(tài)。這種算法思想在求解優(yōu)化問題時(shí)，不但接受對(duì)目標(biāo)函數(shù) (能量函數(shù) )有改進(jìn)的狀態(tài)，還以某種概率接受使目標(biāo)函數(shù)惡化的狀態(tài)，從而可使之避免過早收斂到某個(gè) 局部極值點(diǎn)，也正是這種概率性的擾動(dòng)能夠使之跳出局部極值點(diǎn)，故而得到的解常常很好。 (3)蟻群算法 又稱 螞蟻算法，是一種用來(lái)在圖中尋找優(yōu)化路徑的機(jī)率型算法。它由 Marco Dorigo 于 1992年在他的 博士論文 中提出， 過模擬螞蟻的覓食行為， 螞蟻覓食的時(shí)候會(huì)在所走過的路徑上留下信息激素， 同時(shí)信息激素會(huì)隨時(shí)間而揮發(fā) .一條路徑走過的螞蟻越多， 留下的信息激素越多 。 反過來(lái)， 信息激素濃度高的路徑上會(huì)吸引更多的螞蟻。通過這種正向反饋， 最終將找到一條最優(yōu)路徑。為了避免螞蟻兩次走上同一條路徑 ( 非法路徑 ) ， 為每個(gè)螞蟻設(shè)置一個(gè)禁忌表以記錄它 11 已走過的路徑。該算法的優(yōu)點(diǎn)是 : 它是一種自 適應(yīng) 度 、自組織、本質(zhì)上并 行的方法， 而且是一種正向反饋的方法，可以促使整個(gè)系統(tǒng)向最優(yōu)解進(jìn)化，而且參數(shù)少、易于調(diào)整，易于移植到其他組合優(yōu)化問題。 但是，它存在收斂慢、易于陷人局部最優(yōu) 的缺點(diǎn) 。 (4)人工神經(jīng)網(wǎng)絡(luò) 人工神經(jīng)網(wǎng)絡(luò) (Artificial Neural Network， ANN)，是由大量處理單元即神經(jīng)元 (Neurons)互相連接而成的網(wǎng)絡(luò)，對(duì)人腦進(jìn)行抽象，簡(jiǎn)化和模擬的一種工程系統(tǒng) ，反映人腦的基本特性 。人工神經(jīng)網(wǎng)絡(luò) 算法成為近年來(lái)的熱點(diǎn)研究領(lǐng)域，涉及到 數(shù)學(xué) 、電氣工程、 計(jì)算機(jī)工程 、 物理學(xué) 等諸多學(xué)科，其應(yīng)用領(lǐng)域包括了建模、時(shí)間序列分析、模式識(shí)別和控制等，并且仍然在一斷擴(kuò)展。作為神經(jīng)網(wǎng)絡(luò)的基本單元 ，神經(jīng)元模型具備三個(gè)基本要素。其一是有一組突觸或連接，常用表示內(nèi)部神經(jīng)元的聯(lián)接強(qiáng)度，或者稱 為權(quán)值，取值 范圍 可在負(fù)值和正值之間 ， 其二是 可以 反映生物神經(jīng)元時(shí)空整合功能的輸入信號(hào)累加器 ， 其三是具有一個(gè)激勵(lì)函數(shù)用于限制神經(jīng)元的輸出 。 12 第 4 章 遺傳算法在 TSP 的應(yīng)用 TSP上的應(yīng)用 在遺傳算法研究中， TSP 問題已被廣泛地用于評(píng)價(jià)不同的遺傳操作及選擇機(jī)制的性能。 TSP問題因其典型性已成為各種啟發(fā)式的搜索，優(yōu)化算法的間接比較標(biāo)準(zhǔn)，而遺傳算法方法就本質(zhì)來(lái)說，主要處理復(fù)雜問題的一個(gè)魯棒性強(qiáng)的啟發(fā)式隨機(jī)搜索算法。因此遺傳算法在 TSP 問題求解方面的應(yīng)用研究，對(duì)于構(gòu)造合適的遺傳算法框架，建立有效的遺傳操作以及有效地解決 TSP 等有著多方面的重要意義。 圖 41遺傳算法運(yùn)用在 TSP 上的流圖程 13 遺傳算法的進(jìn)化過程是建立在編碼機(jī)制基礎(chǔ)上的，編碼對(duì)于算法的性能，如搜索 能力和種群多樣性等影響很大。如何將問題的解轉(zhuǎn)換為編碼表達(dá)的染色體是遺傳算法的關(guān)鍵問題。編碼機(jī)制的主要工作是把對(duì)象抽象為由特定符號(hào)按一定順序排成的串。這就如同研究生物遺傳是從染色體著手，而染色體則是由基因排成的串。遺傳算法中經(jīng)常使用二進(jìn)制串進(jìn)行編碼，其優(yōu)點(diǎn)是編碼、解碼操作簡(jiǎn)單，交叉、變異等操作也易于實(shí)現(xiàn)，且便于應(yīng)用模式定理進(jìn)行理論分析；其缺點(diǎn)主要是處理 連續(xù)函數(shù)的優(yōu)化問題時(shí)存在映射誤差：編碼長(zhǎng)度較小時(shí)達(dá)不到精度要求， 度較大時(shí)又會(huì)使算法搜索空間過大。 選擇一個(gè)群體，就是選擇一個(gè)個(gè)體的集合。這個(gè)初 始群體也就是問題假設(shè)解得集合。在遺傳算法求解 TSP 問題中通常以隨機(jī)方式產(chǎn)生串或者個(gè)體的集合。初始種群個(gè)數(shù)越多，得到最優(yōu)解的希望越大，但個(gè)數(shù)過多會(huì)導(dǎo)致每進(jìn)行一輪的機(jī)器時(shí)間變長(zhǎng)，致使算法效率低下。 在研究自然界中生物的遺傳和進(jìn)化現(xiàn)象時(shí)，生物學(xué)家常常使用適應(yīng)度這個(gè)術(shù)語(yǔ)來(lái)衡量某個(gè)物種對(duì)環(huán)境的適應(yīng)率。適應(yīng)度較高的物種將會(huì)得到更多的繁殖的機(jī)會(huì)；從而導(dǎo)致適應(yīng)度低的物種被淘汰。度量物種適應(yīng)度的函數(shù)就被稱為適應(yīng)度函數(shù)。 本文中適應(yīng)度函數(shù)取為哈密爾頓圈的長(zhǎng)度的倒數(shù)。 void CalFitness(PTSP city) { int i,j。 int start,end。 for(i=0。iPOPSIZE。i++){//求適應(yīng)值 cityDistance[i]=0。 for(j=1。j=CITY_NUM。j++){ start=citycolony[i][j1]。end=citycolony[i][j]。 cityDistance[i]=cityDistance[i]+CityDistance[start][end]。 } cityfitness[i]=N/(cityDistance[i])。 } } 遺傳算法中的選擇操作就是用來(lái)確定如何從父代群體中按某種方法選 取哪 些個(gè)體遺傳到 14 下一代群體中的一種遺傳運(yùn)算。選擇操作的目的是為了避免基因缺失，提高全局收斂性和計(jì)算效率。常用的選擇可略包括以下幾種： (1) 輪盤賭法。 (2) 錦標(biāo)賽選擇。 (3) 最優(yōu)保存策略。 (4) 期望值方法。 (5) 排序選擇方法。 比較常用的就是輪盤賭法，以及最優(yōu)策略保留法。本文采用的是 輪盤賭法 。 在輪盤賭法中，各個(gè)個(gè)體的被選擇概率和其適應(yīng)度值成比例。設(shè)群體大小為 N，個(gè)體 i 的適應(yīng)度值 Fi，則 個(gè)體 i 被選擇的概率 Psi為： Psi=Fi／ ??nj j1F (n=l， 2?．． n) 顯然，概率 Psi反映了個(gè)體 i的適應(yīng)度在整個(gè)群體的個(gè)體適應(yīng)度總和中所占的比例。根據(jù)個(gè)體適應(yīng)度值的大小，適應(yīng)度值越大的，其概率 Psi越大，被選擇到的機(jī)會(huì)也越多，從而其基因結(jié)構(gòu)被遺傳到下一代的可能性也越大，反 之亦 然。 輪盤賭的具體執(zhí)行過程如下： a)先計(jì)算出種群中所有個(gè)體的適應(yīng)度的總和。 b)其次計(jì)算出每個(gè)個(gè)體的相對(duì)適應(yīng)度的大小，作為被選中的概率。 void Select(PTSP city) { //選擇算子 double tempRand,tempflag1。 int i,j。 for(i=0。iPOPSIZE。i++)//選 POPSIZE 次 { tempRand=(rand()%100000)/*3。 tempflag1=0。 for(j=0。jPOPSIZEamp。amp。tempflag1==0。j++) { if(tempRand=cityaddFitness[j])//輪盤賭選中第 j 個(gè) { 15 tempflag1=1。 //if(i!=cityBestFitCityXuh) if(cityfitness[j]=cityfitness[i]amp。amp。i!=j) { copyColony(i,j,city)。 } } } } return。 } 基于 TSP 問題 的順序編碼，若采取簡(jiǎn)單的一點(diǎn)交叉或多點(diǎn)交叉策略，必然以極大的概率導(dǎo)致未能完全遍歷所有城市的非法路徑 1 2 3 4| 5 6 7 8 8 7 6 5 |4 3 2 1 若采取一點(diǎn)交叉，且交叉點(diǎn)隨機(jī)選為 4，則交叉后產(chǎn)生的兩個(gè)后代為 8 7 6 5 5 6 7 8 1 2 3 4 4 3 2 1 顯然，這兩個(gè)子路徑均未能遍歷所有 8 個(gè)城市，都違反了 TSP 的約束條件。針對(duì)這一問題，當(dāng)然可以采取上述構(gòu)造懲罰函數(shù)的方法，但是實(shí)驗(yàn)效果不佳。 解決這一約束問題的另一種處理方法是對(duì)交叉，變異等遺傳操作作適當(dāng)?shù)男拚?，使其自?dòng)滿 足 TSP 的約束條件，本文采用部分匹配交叉法 ： 部分匹配交叉中先依據(jù)均勻隨機(jī)分布產(chǎn)生兩個(gè)位串交叉點(diǎn)，定義這兩點(diǎn)之間的區(qū)域?yàn)橐黄ヅ鋮^(qū)域，并使用位置交換操作交換兩個(gè)父串的匹配區(qū)域，兩父串及匹配區(qū)域?yàn)? A=9 8 4 |5 6 7| 1 3 2 0 B=8 7 1 |2 3 0| 9 5 4 6 首先交換 A 和 B 的兩個(gè)匹配區(qū)域，得到 A1=9 8 4 |2 3 0| 1 3 2 0 16 B1=8 7 1 |5 6 7| 9 5 4 6 對(duì)于 A1， B1 兩個(gè)串中匹配區(qū)域以外出現(xiàn)的遍歷重復(fù)，依據(jù)匹配區(qū)域內(nèi)的位置映射關(guān)系， 逐一進(jìn)行交換，對(duì)于 A1 有 2 到 5,3 到 6,0 到 7 的位置符號(hào)映射，對(duì) A1 的匹配區(qū)以外的 2， 3， 0分別以 5,6,7 替換，則得 A2=9 8 4 |2 3 0 |1 6 5 7 B2=8 0 1| 5 6 7 |9 2 4 3 這樣，每個(gè)子串的次序部分有其父串確定。 這 是 在選中用于繁殖下一代的個(gè)體中，對(duì) 兩個(gè)不同的個(gè)體的相同位置的基因進(jìn)行交換，從而產(chǎn)生新的個(gè)體，也即對(duì)兩個(gè)父染色體的部分結(jié)構(gòu)進(jìn)行重組，以產(chǎn)生新一代子染色體。 遺傳交叉的主要目的是子代盡可能地繼承父代的優(yōu)秀基因。 void Cross(PTSP city,double pc) {//交叉概率是 pc int crossNum,i。 int cityCross[2][CITY_NUM+1]。 int tempXuh[2]。 crossNum=int(POPSIZE*pc)。 for(i=0。icrossNum/2。i++) { tempXuh[0]=rand()%(POPSIZE1)。 do { tempXuh[1]=rand()%(POPSIZE1)。 }while(tempXuh[0]==tempXuh[1])。 copyCityXuhTo(city,tempXuh,cityCross)。 crossTwo(city,tempXuh,cityCross)。 } 17