一種基于模擬退火的遺傳算法在受約束旅行商問題中的應用

孔令夷

（西安郵電大學管理工程學院，陜西 西安 710061）

0 引言

遺傳算法（Genetic Algorithm，GA）借鑒生物進化過程，模擬自然界對生物種群的優(yōu)選而獲取適應度更高的個體，并將其作為最滿意解［1］.GA的基本思想是：初始化種群（initialization）、適應度函數(shù)構(gòu)建（Fitness Function）、基于適應度的優(yōu)選與繁衍（Heredity）、選擇若干子代后的最高適應度個體作為最滿意解.GA的組成要素有：種群規(guī)模、染色體編碼方案、交叉算子、變異算子、選擇方法、終止條件.鑒于該算法的處理對象并不是問題的決策變量，而是對相關(guān)變量轉(zhuǎn)換成的編碼，即染色體或位串，因此它對目標問題基本上沒有太多限制，對函數(shù)類型的限制也很少，這就使得該算法的智能性明顯高于規(guī)范的運籌學或其他傳統(tǒng)的優(yōu)化手段，尤其是在解決復雜環(huán)境下、規(guī)模較大、非結(jié)構(gòu)性、高維度問題時，更是表現(xiàn)出強有效性，基本上可以求出最滿意解.旅行商問題（Traveling Salesman Problem，TSP）在圖論領域是一個經(jīng)典性問題，呈現(xiàn)出不確定性及多維性，具有高度的計算復雜性［2－3］，是學術(shù)界、工業(yè)界與相關(guān)服務企業(yè)長期以來需要應對的難點及重點問題.以“旅行商問題”或“TSP”作為篇名，在中國知網(wǎng)搜索，近10年來刊載于國內(nèi)期刊的該類研究論文就高達295篇，因此，怎樣更好地將當今最成功且適用性最強的智能算法——GA用于解決TSP，早已是人工智能、信息技術(shù)、工程應用、交通運輸、電子計算機、經(jīng)濟數(shù)學、算法理論、統(tǒng)籌法優(yōu)選法、管理科學等各類前沿領域的大量研究者們關(guān)注的焦點［4－8］.

1 受約束TSP的提出

實際的TSP還可能存在其他額外的限定條件，例如旅行商途經(jīng)的某兩個地點中間有天然屏障，如河流、山脈、沼澤、沙漠等，無法直達，迫使旅行商要繞道而行.這類情況下，這兩個途經(jīng)地點就是不聯(lián)通的，此類TSP就是受約束TSP，也正是本文擬研究的對象.

2 基于模擬退火的遺傳算法

針對TSP的一般性運籌方法具有諸多局限：決策變量少，過于理想化的假定使得該問題脫離實際情況，而且較為苛刻地要求函數(shù)具有某些優(yōu)良的數(shù)學特性，如若不然，就可能算出大量的不可行解，無法獲取真正的最優(yōu)解，或者也只能求出局部最優(yōu)解.顯而易見，一般性運籌優(yōu)化方法缺乏對復雜性TSP的解決能力，主要表現(xiàn)為問題描述不客觀、建模不理想及尋優(yōu)性較弱，更不用說受約束情形下了［9］.然而，GA的優(yōu)點此時卻恰恰可以被彰顯無遺.首先，該算法的處理對象并不是問題的決策變量，而是對相關(guān)變量轉(zhuǎn)換成的編碼，即染色體或位串，因此它對TSP基本上不做太多限定.其次，GA對所求函數(shù)類型的限制也很少，無論線性或非線性、離散或連續(xù)、可微或不可微，這就使得該算法的智能性明顯高于規(guī)范的運籌學或其他傳統(tǒng)的優(yōu)化手段，基本上可以求出最滿意解，這又再次顯示出GA在應用研究中的廣泛性.第三，運籌優(yōu)化法通常從初始點著手，不斷迭代和調(diào)整，路徑單調(diào)且出錯率高，而GA突破常規(guī)，從面上群體擇優(yōu)，從上一代（父代）的很多染色體（個體）開始評估選擇，擇優(yōu)后再經(jīng)過交叉變異等基因遺傳方式形成下一代（子代），這樣就確保優(yōu)良基因傳承以及種群穩(wěn)定性，篩掉的都是適應度較差的染色體，實現(xiàn)“優(yōu)勝劣汰，適者生存”，經(jīng)過足夠多次的迭代，獲取整體最滿意解就會是順理成章、水到渠成的.第四，GA對個體的選擇過程，只遵循適值評判的簡易準則，客觀性極強，不受其他因素干擾，逼真地再現(xiàn)生物體在大自然中延續(xù)生存繁衍的自適應能力及品質(zhì).最后，GA采用適中的交叉率作為重要的遺傳算子，既最大限度地擴充解空間，允許子代個體性態(tài)的持續(xù)改進，又能限制搜索工作量而加速計算、縮減染色體收斂時間；同樣的，采用合適的變異率不但可以吸收外部的有用基因，而且保留了雙親傳遞的優(yōu)質(zhì)特性，因此，最終得出的最滿意解必定有很高的可置信性，而不像傳統(tǒng)方法必須給出確定性解，從而也說明GA具有足夠的柔性和可改進性.以上優(yōu)點決定了GA非常適用于解決復雜環(huán)境下、規(guī)模較大、非結(jié)構(gòu)性、高維度、不連續(xù)、不可微分問題［10］，現(xiàn)實世界中很多問題都有這些屬性，比如受約束的旅行商問題.

然而，現(xiàn)有GA的求解效率很大程度上受到參量選取及各種遺傳算子的影響，普遍呈現(xiàn)早熟現(xiàn)象，迭代冗余問題也會頻發(fā).針對于此，研究者們對GA做了很多改造工作，起到了一定的預防和矯正作用［11－14］.而且，算法運行過程中引入確定性策略能確保種群優(yōu)良基因的穩(wěn)定性；同時，基于模擬退火思想引入不確定性策略，能實現(xiàn)種群子體的多元化保留，有效提高算法的全局尋優(yōu)性［15－16］.C.Bierwirth等人通過大量算例研究，認為優(yōu)先保留交叉（Precedence Preservation Crossover，PPX）方法的交叉比例適中，有助于繼承上一代的優(yōu)質(zhì)特性，從而較好地抑制現(xiàn)有GA的早熟問題發(fā)生［17］.T.Murata等人進行大量數(shù)值實驗研究，開發(fā)設計了平移變異（Shift Change Mutation，SCM）操作，大幅度提升進化質(zhì)量，同時能縮短CPU在求解過程中的運行時間［18］.

2.1 染色體編碼的方案選擇

文中擬設計適合TSP的專屬編碼，即根據(jù)旅行商途徑的全部地點的順序，來得到識別所有個體身份信息（ID）的唯一位串，這種編碼方案較為常見，具有合理性和窮舉性.如此設計可以使得搜尋最優(yōu)解在極為有限的解空間（即該問題所涉及的全部地點的各種排列的集合）內(nèi)展開，必將大大提升算法運行速度及有效性.例如S＝（2，1，3，4，6，5，7），則意味著旅行商的行進路線是從起點2開始，分別途經(jīng)地點1－3－4－6－5－7，最后返回地點2.

2.2 種群初始化

遺傳算法的效能不僅受制于各類算子，也對染色體初值較為敏感［1］.性能較劣的父代群體會對緊接著的迭代過程及進化質(zhì)量產(chǎn)生不可低估的負面影響.如果隨意產(chǎn)生第一代群體，就無法確保其質(zhì)量的優(yōu)良性，也未必符合最初問題中所要求的某些地點之間的不聯(lián)通條件，以此為基礎不斷迭代后求得的“最滿意解”的可行性就會大打折扣，致使算法效率較差.因此，將現(xiàn)有GA優(yōu)化為：在現(xiàn)有隨機方法的基礎上，混合貪心轉(zhuǎn)換法以得到最初的第一代種群，從而提高其優(yōu)良性［19－20］.貪心轉(zhuǎn)換法就是每次都追求實現(xiàn)局部的優(yōu)化，而未必考慮全局的系統(tǒng)優(yōu)化.

2.3 適值函數(shù)構(gòu)建

解決TSP是要求出最短的總路程，所以，適值應該與旅行商的穿越總路程成反比，令α是常量，則可得出適值

即S的適值在種群中將是很小的，甚至是最小的，按照GA的選擇操作中“適者生存”的思想，這種適應度值很小的不可行染色體S必然會篩除，從而較早且較為容易地舍掉不可行解.

2.4 基于模擬退火的交叉變異操作

本算法選擇PPX［17，22］及SCM［18］.PPX操作過程基于2個已有染色體串和1個相同長度的｛1，2｝隨機數(shù)字串.若數(shù)字串的第i個碼是1，就取第1個染色體最左側(cè)的地點編號，放入新染色體的第i位；反之就從第2個染色體中取得，刪掉現(xiàn)有2個染色體中已選地點，繼續(xù)讀取數(shù)字串其余碼，直至完畢.研究發(fā)現(xiàn)，PPX相比映射交叉、次序交叉或循環(huán)交叉，子串能更多地保留雙親的好特性.

交叉操作后，對于新的子體接納決策可引入確定性策略［15－16］，確保優(yōu)良基因的保留及種群穩(wěn)定性得以較好的延續(xù).設S，T是兩個父代個體，S1與T1是對S與T 執(zhí)行交叉操作后的子代個體，即［S1，T1］＝crossover［S，T］，那么執(zhí)行下述條件語句：

可見，確定性策略就是通過對新老個體的適值比較而保留適值更高的一組個體.

接著，執(zhí)行SCM，即任選插入點及碼位，實施平移，以產(chǎn)生新串.設S＝（1，5，4，3，2，6，7），插入第6位碼，即地點6，插入點為第3位，就有S1＝（1，5，6，4，3，2，7）.類似于PPX，SCM 相比對換或目標導向變異，其遺傳效能更高，可將上一代的優(yōu)良特性丟失控制在最低限度.

為了實現(xiàn)種群多元化，在變異操作中引入不確定性策略，即對變異后的子體實施模擬退火算法，做出子體是否接納的決策［15－16］.設S是父代個體，S1是對S執(zhí)行變異操作后的子體，即［S1］＝mutation［S］；初始溫度T足夠大且逐漸降低，從而不斷被更新，最終趨近于0；a略小于1，令其取值范圍是［0.90，0.99］.先算出Δt＝f（S1）－f（S），若Δt＞0則接納新子體S1作為新解；否則，也同樣能以概率exp（Δt／T）接納S1作為新解.若滿足終止條件則輸出當前解，終止條件設定為連續(xù)若干個子體都不能被接納.具體而言，就是執(zhí)行下述條件語句：

結(jié)合上述的確定性策略和基于模擬退火的不確定性策略，本研究的交叉變異操作就能實現(xiàn)對現(xiàn)有GA更好的優(yōu)化效果，表現(xiàn)為追求種群穩(wěn)定性與多樣性的兼容、抑制種群早熟、確保向全局最優(yōu)解收斂.而且，上述的算法設計適用性較強，基本上不存在局限和缺陷，可以順利推廣到TSP以外的各類NPC問題.

2.5 選擇策略

根據(jù)進化論思想，選擇就是保留適應能力強的個體，舍棄較差生存能力者，使得種群漸漸朝著適應于生存環(huán)境的方向發(fā)展演化.依據(jù)上文所設計的適值高低對應的概率分布進行選擇，就能體現(xiàn)自然選擇的客觀規(guī)律.本算法仍采納多見的輪賭法（roulette wheel selection），有利于全局性、可持續(xù)優(yōu)化［23］.

3 算法檢驗與分析

使用Matlab 2012b對現(xiàn)有GA［1，21］與本文的模擬退火遺傳算法編程，引用文獻［16］的TSP算例.取值Pc＝0.2，Pm＝0.5，MaxItr＝1000，運行結(jié)果見表1、圖1—2.可見，兩種算法的快速尋優(yōu)能力都較強，運行時間不超過2min.但是，對解進行比較，可知本文的算法更優(yōu)，起到對現(xiàn)有GA優(yōu)化的效果.現(xiàn)有GA處于劣勢，根由在于：在初始種群生成方面產(chǎn)生了大量不可行解，交叉變異過程中遺傳進化質(zhì)量不高，也缺乏種群多樣性.

而且，極差的比較也會給出一些啟示：基于模擬退火的新遺傳算法的個體離散性弱，收斂性強.其原因在于：其一，新算法的初始染色體質(zhì)量較優(yōu)，貪心法屏蔽了很多不可行個體；其二，在交叉變異操作之后實施的模擬退火算法，兼顧了種群優(yōu)良基因保留以及種群子體多樣性存在，基于模擬退火的子體接納決策從子體適值入手，這對于提升子代整體遺傳質(zhì)量大有裨益，不但能有限地抑制染色體早熟，而且加速了向全局最優(yōu)解的收斂.

表1 算法運行結(jié)果

圖1 基于模擬退火的新型遺傳算法的最滿意解

圖2 現(xiàn)有GA的最滿意解

4 結(jié)束語

本研究集成模擬退火算法及遺傳算法，應用于解決受約束TSP，更逼真地模擬了現(xiàn)實中各種復雜因素，研究價值較高.首先，利用隨機選取與貪心法相結(jié)合的方式來生產(chǎn)初始種群，確保了初始種群滿足不聯(lián)通約束，克服了現(xiàn)有GA的主要缺陷；接著，選擇并實施了效能更高的PPX及SCM，以確保優(yōu)良基因；再者，分別接繼交叉以及變異操作之后的確定性策略以及基于模擬退火算法的不確定性策略，兩種策略能夠確保新一代子體接納的最優(yōu)決策，實現(xiàn)了優(yōu)良基因穩(wěn)定性與種群多樣性的兼容，抑制種群早熟，而且確保向全局最優(yōu)解收斂；最后，給出了基于不聯(lián)通約束而經(jīng)特殊處理的適值函數(shù)，還采納了經(jīng)典有效的選擇方法.本算法設計適用性較強，基本上不存在明顯局限和缺陷，可以順利推廣到TSP以外的各類NPC問題，當然具體情況還有待今后相關(guān)研究的不斷證實.

［1］雷德明，嚴新平.多目標智能優(yōu)化算法及其應用［M］.北京：科學出版社，2009：1－10.

［2］YANG J H，WU C G，LEE H P，et al.Solving traveling salesman problems using generalized chromosome genetic algorithm［J］.Progress in Natural Science，2008，18（7）：887－892.

［3］吳春國.廣義染色體遺傳算法與迭代式最小二乘支持向量機回歸算法研究［D］.長春：吉林大學數(shù)學學院，2006.

［4］YU HONG，YANG DACHUN.An incremental rule acquisition algorithm based on rough set［J］.The Journal of China Universities of Posts and Telecommunications，2005，12（1）：47252.

［5］賀毅朝，寇應展，陳致明.求解多選擇背包問題的改進差分演化算法［J］.小型微型計算機系統(tǒng)，2007，（9）：1682－1685.

［6］韓偉一，王錚.負權(quán)最短路問題的新算法［J］.運籌學學報，2007，11（1）：111－120.

［7］黃永青，梁昌勇，張祥德，等.一種小種群自適應遺傳算法研究［J］.系統(tǒng)工程理論與實踐，2005，25（11）：92－97.

［8］郟宣耀，王芳.一種改進的小生境遺傳算法［J］.重慶郵電學院學報：自然科學版，2005，17（16）：721－723.

［9］BHATIA A K，BASU S K.Tackling 0／1knapsack problem with gene induction［J］.Soft Computing，2003，8（1）：1－9.

［10］ZHAO X C，Gao X S.Affinity genetic algorithm［J］.Journal of Heuristics，2007，13（2）：133－150.

［11］CHENG R，GEN M，TSUJIMURA Y.A tutorial survey of Job－shop scheduling problems using genetic algorithms Part II：hybrid genetic search strategies［J］.Computers ＆Industrial Engineering，1999，36（2）：343－364.

［12］王濤，付宜利.一種改進的遺傳算法在車間調(diào)度中的應用［J］.計算機集成制造系統(tǒng)，2002，8（5）：392－420.

［13］張超勇，饒運清，李培根，等.求解作業(yè)車間調(diào)度問題的一種改進遺傳算法［J］.計算機集成制造系統(tǒng)，2004，10（8）：966－970.

［14］張國輝，高亮，李培根.基于遺傳規(guī)劃的作業(yè)車間調(diào)度算法研究［J］.控制與決策，2008，23（8）：924－928.

［15］趙新超，韓宇，艾文寶.求解背包問題的一種改進遺傳算法［J］.計算機工程與應用，2011，47（24）：34－36.

［16］康立山，謝云，尤矢勇，等.模擬退火算法［M］.北京：科學出版社，1994：150－151.

［17］BIERWIRTH C，MATTFELD D，KOPFER H.On permutation representations for scheduling problems［C］／／Proceedings of the 4th International Conference on Parallel Problem Solving from Nature，Berlin：Springer，1996：310－318.

［18］MURATA T，ISHIBUCHI H，TANAKA H.Genetic algorithms for flowshop scheduling problem［J］.Computers ＆Industrial Engineering，1996，30（4）：1061－1071.

［19］賀毅朝，劉坤起，張翠軍，等.求解背包問題的貪心遺傳算法及其應用［J］.計算機工程與設計，2007，28（11）：2655－2657.

［20］賀毅朝，劉建芹，曲文龍，等.求解廣義背包問題的貪心 DS＿BPSO算法［J］.計算機應用與軟件，2008，25（4）：230－232.

［21］梁艷春，吳春國，時小虎，等.群智能優(yōu)化算法理論與應用［M］.北京：科學出版社，2009：34－43.

［22］晏鵬宇，楊乃定，車阿大.自動化制造單元最小完工時間調(diào)度問題的混合啟發(fā)式算法［J］.計算機集成制造系統(tǒng)，2010，16（4）：847－854.

［23］晏鵬宇，車阿大，李鵬，等.具有柔性加工時間的機器人制造單元調(diào)度問題改進遺傳算法［J］.計算機集成制造系統(tǒng)，2010，16（2）：404－410.