MTSP 的改進(jìn)模擬退火算法及其求解

畢少辰，石保東，劉小龍，張 蕾

（青島理工大學(xué)a.理學(xué)院；b.管理學(xué)院，山東 青島 266520）

0 引言

旅行商問題（Traveling Salesman Problem，TSP）是近代組合優(yōu)化領(lǐng)域的一個(gè)典型難題。旅行商問題可以簡(jiǎn)單描述為：一個(gè)旅行商遍歷城市節(jié)點(diǎn)集后返回原點(diǎn)的最優(yōu)線路規(guī)劃問題。旅行商問題有重要的實(shí)際意義和工程背景，在印制電路板轉(zhuǎn)孔、衛(wèi)星位置調(diào)整、電光纜布置、晶體結(jié)構(gòu)分析等多領(lǐng)域得到應(yīng)用。

受限于枚舉的計(jì)算限制，近代研究學(xué)者提出了一系列針對(duì)TSP 問題的算法方案?？傮w上可以分為基于已有成熟啟發(fā)式算法的改良算法和借助仿生學(xué)提出的新的啟發(fā)式算法。其中模擬退火算法是求解TSP 較為成熟的算法，具有最值結(jié)果質(zhì)量高、初值魯棒性強(qiáng)、通用易實(shí)現(xiàn)等諸多優(yōu)點(diǎn)。

模擬退火算法是現(xiàn)代優(yōu)化算法，模擬退火算法的出現(xiàn)得益于材料統(tǒng)計(jì)力學(xué)的研究成果。在很多學(xué)者的研究中發(fā)現(xiàn)，粒子在高溫狀態(tài)下具有較高的能量，在緩慢降溫的過程中，粒子能量逐漸減少，粒子的狀態(tài)趨于穩(wěn)定。模擬退火算法是基于物理學(xué)中固體物質(zhì)的退火過程與一般優(yōu)化問題的相似性，通過逐步迭代使中間解逐步向最優(yōu)解收斂?；谀M退火算法在求解旅行商問題上的優(yōu)勢(shì)，研究并優(yōu)化一般模擬退火算法以求解多旅行商問題有很大的應(yīng)用價(jià)值。

優(yōu)化問題可以轉(zhuǎn)化為目標(biāo)函數(shù)的極值問題，對(duì)于多目標(biāo)的優(yōu)化問題，多目標(biāo)優(yōu)化時(shí)存在各優(yōu)化目標(biāo)之間的制約關(guān)系，在模擬退火改進(jìn)過程中，優(yōu)化一項(xiàng)目標(biāo)會(huì)使另一項(xiàng)目標(biāo)偏離。需要對(duì)優(yōu)化的各個(gè)目標(biāo)設(shè)置權(quán)重，協(xié)調(diào)各目標(biāo)的影響程度。在實(shí)際問題中，考慮各種資源平衡的情況下，模擬退火算法使用起來往往得不到預(yù)期的最優(yōu)規(guī)劃。

多旅行商問題（MTSP）是經(jīng)典旅行商問題的推廣。在現(xiàn)實(shí)應(yīng)用的過程中，多旅行商問題的影響因素往往更加復(fù)雜，單純考慮運(yùn)行路徑的總長度會(huì)導(dǎo)致路徑之間極不均衡。結(jié)合模擬退火算法在求解旅行商問題上的優(yōu)勢(shì)，本文通過改進(jìn)模擬退火算法，在算法中引入綜合目標(biāo)函數(shù)，對(duì)總運(yùn)行路徑和其他影響因素進(jìn)行綜合評(píng)價(jià)。改進(jìn)模擬退火算法，可以綜合衡量多個(gè)因素對(duì)最終結(jié)果的影響程度。

1 模擬退火算法簡(jiǎn)介與改進(jìn)

1.1 綜合目標(biāo)函數(shù)改進(jìn)模擬退火算法

為解決路徑長度與子路徑均衡程度相沖突的問題，文章引入綜合目標(biāo)函數(shù)：

公式（1）（2）中，Z 為綜合目標(biāo)函數(shù)，用于綜合衡量路徑優(yōu)劣程度，S 為路徑總長度，J 為子路徑的均衡度。a、b 分別為總路徑與均衡度的權(quán)重系數(shù)。

總路徑長度S 為：

L為第i 段子路徑的長度。

期望反映變量的平均取值的大小，偏差與方差均是衡量源數(shù)據(jù)與期望的離散程度的度量值。應(yīng)用統(tǒng)計(jì)學(xué)中標(biāo)準(zhǔn)方差的表示形式，均衡度可通過式（4）進(jìn)行衡量：

為了統(tǒng)一量綱和簡(jiǎn)化計(jì)算，將均衡度J 定義為：

1.2 改進(jìn)模擬退火算法流程

（1）給定初始溫度T、降溫系數(shù)α、終止溫度T并通過固定關(guān)鍵節(jié)點(diǎn)插值法與蒙特卡洛算法給定較優(yōu)初始解。

（2）根據(jù)關(guān)鍵節(jié)點(diǎn)劃分子路徑，計(jì)算各子路徑長度L與各子路徑均衡程度J。

（4）進(jìn)行2 變換、3 變換（交換解序列中任意2 或3個(gè)節(jié)點(diǎn)的位置），得到新解。

（6）在同一溫度下進(jìn)行多次內(nèi)循環(huán)，求得該溫度下的較優(yōu)解。

（7）按降溫系數(shù)T-α·T 退火，當(dāng)T=T時(shí)停止迭代。

2 數(shù)值算例

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）在生活中被廣泛應(yīng)用。無線傳感網(wǎng)絡(luò)，需要傳感器、數(shù)據(jù)中心和移動(dòng)充電器三部分相互協(xié)同進(jìn)行運(yùn)作。高效的路由算法能有效降低網(wǎng)絡(luò)能量消耗，延長網(wǎng)絡(luò)壽命。為保證傳感器有足夠電量來正常工作，數(shù)據(jù)中心需要按時(shí)用充電器為傳感器充電。傳感器和數(shù)據(jù)中心分布在同一個(gè)二維平面內(nèi)，數(shù)據(jù)中心與任意一個(gè)傳感器、任意傳感器之間都相互連通。數(shù)據(jù)中心和傳感器的位置可以通過水準(zhǔn)測(cè)量以坐標(biāo)的形式確定，也可基于自身定位設(shè)備確定。

傳感器電量消耗由充電器消耗和運(yùn)行路程上的損耗兩部分組成，為減少能量損失，需要規(guī)劃移動(dòng)充電器在傳感器之間的最短運(yùn)行路線。為提高充電工作的效率，網(wǎng)絡(luò)中有四臺(tái)移動(dòng)充電器為傳感器充電。求四臺(tái)充電器運(yùn)行的最佳運(yùn)行路線。

在原有路徑中設(shè)置D、D、D三個(gè)插入點(diǎn)作為充電器的出發(fā)點(diǎn)，得到距離矩陣。

單純以總路程最短為要求，求最優(yōu)解，就會(huì)導(dǎo)致4個(gè)傳感器運(yùn)行的線路極為不均衡。總路程最短情況下的不均衡運(yùn)行線路見圖1。

如圖1 所示，總路程最短不一定能使各個(gè)充電器任務(wù)均衡。在4 個(gè)充電器總運(yùn)行距離最短的情況下，求解出的不均衡的分布線路，雖然滿足充電器總能量損失最小，但總的時(shí)間周期加長，使體系的總體充電效率變低。

圖1 總路程最短變情況下的不均衡運(yùn)行線路圖

總路徑長度S 為：

由于隨機(jī)的位置交換，可能改變插入節(jié)點(diǎn)的位置。所以在新路徑中，以插入的新節(jié)點(diǎn)出現(xiàn)的前后順序劃分四段子路徑，將四段子路徑的距離依次標(biāo)記為L、L、L、L。

新得到的路徑的四段子路徑形成的距離矩陣表示為MaxL=（L，L，L，L）。

進(jìn)行多次降溫模擬，得到權(quán)重系數(shù)為1∶1 情況下，綜合目標(biāo)函數(shù)最小情況下的運(yùn)行路徑，如圖2 所示。

圖2 4 個(gè)充電器運(yùn)行路徑示意圖

4 個(gè)充電器的運(yùn)行路徑長度分別為：

3 514.04 0 693 829 77 米、3 456.1 59 670 828 92米、3 780.35 8 008 895 60 米、3 488.70 6 674 434 52 米。

此時(shí)的總路徑長度為14 239 米。

最優(yōu)解時(shí)綜合目標(biāo)函數(shù)值Z＝14.68。

總路程極短（路徑長度系數(shù)a 遠(yuǎn)大于均衡度系數(shù)b）情況下，運(yùn)行路徑的總長度為12.833 2 千米。由前文分析得出，在一條路徑下運(yùn)行距離最短，最短距離為11.483 2 千米。12.833 2 千米非常趨近于最優(yōu)解。

在總路徑均衡（路徑長度系數(shù)a 遠(yuǎn)低于均衡度系數(shù)b）的情況下，四段子路程的距離分別為3.666 5 千米、3.529 2 千米、3.727 8 千米、3.712 2 千米。這里使用統(tǒng)計(jì)學(xué)中標(biāo)準(zhǔn)方差的表現(xiàn)形式，體現(xiàn)四段子路徑對(duì)于均值的離散程度。

四段子路徑的均衡度為d（X）=0.078 211 168，趨近零值，即四段子線路的長度非常接近。

實(shí)際應(yīng)用中，可根據(jù)具體問題對(duì)“路徑總長度”和“子路徑均衡度”的不同需求，為兩者選定不同的權(quán)重系數(shù)，從而求取相應(yīng)條件下的最優(yōu)解。

3 結(jié)論

本文改進(jìn)的模擬退火算法，將多旅行商問題中的總路徑長度與子路徑均衡度同時(shí)參與迭代。綜合目標(biāo)函數(shù)Z，可以根據(jù)對(duì)“路徑”和“均衡度”的重視程度設(shè)置權(quán)重。在求解路徑長度和子路徑的均衡度問題上，很容易通過系數(shù)的變化來掌控。通過這種方法可以求解多旅行商問題中“路徑盡可能短”“路徑盡可能均衡”以及“在盡可能均衡的條件下求最短”等類似問題。

例如：如果需要使總路徑盡可能短，即可增加路徑權(quán)重，降低均衡度權(quán)重。

同時(shí)保留了模擬退火算法在求解經(jīng)典旅行商問題時(shí)其固有的全局尋優(yōu)能力。最終求解方案的子路徑均衡，每個(gè)旅行商運(yùn)行完各自路徑的時(shí)間相對(duì)接近，其綜合效率較高；改進(jìn)后的模擬退火算法在求解時(shí)間和求解精度上都有較好的表現(xiàn)。