秦媛媛

（江蘇財經(jīng)職業(yè)技術(shù)學(xué)院，江蘇 淮安 223003）

一、引言

人們在日常生活當中經(jīng)常會遇到關(guān)于組合優(yōu)化方面的問題，該類問題主要任務(wù)是要在組合問題所有的可行解集合里面找到最優(yōu)的解，一般可以表示成：令集合Ω={s1，s2，…，sn}，該集合Ω是為一切狀態(tài)組合而成的問題解的集合，C(si)是狀態(tài)si是所照應(yīng)的目標函數(shù)的解，要求尋找最優(yōu)解s，使得對于所有的si∈Ω，有C(s)=minC(si)。常見的組合優(yōu)化問題包括：旅行商問題（TravelingSalesman Problem-TSP）、生產(chǎn)調(diào)度問題（Production Scheduling Problem，如Flow-Shop，Job-Shop）、0-1 背包問題（KnapsackProblem）、裝箱問題（Bin Packing Problem）、圖著色問題（Graph ColoringProblem）、聚類問題（ClusteringProblem）和最大團問題等。該類問題的表達很簡單，同時表現(xiàn)出鮮明的工程行業(yè)相關(guān)特性，然而想獲得最優(yōu)解相對較難，根本的原因在于使用傳統(tǒng)的解決這類問題的算法需要很長的運算時間和很大的存儲容量，對計算機性能的要求很高，這就是常見的一個詞“組合爆炸”的由來。組合優(yōu)化問題的復(fù)雜性和應(yīng)用廣泛引起研究人員的對其理論和算法的研究熱情，各種啟發(fā)式算法紛紛展現(xiàn)。本文從應(yīng)用十分廣泛的旅行商問題出發(fā)，研究應(yīng)用一種啟發(fā)式算法來解決此類問題。

二、研究現(xiàn)狀

旅行商問題為比較典型的組合優(yōu)化的應(yīng)用案例，它通常被這樣描述為：旅行推銷員經(jīng)常會面臨這樣一種問題，就是在給出既定的許多城市（坐標點已定）和這些城市之間的相對距離條件后，從中求解出推銷員走過每個城市一次然后還能回到起點城市的最短的回路，還可以找到推銷員行走過路程的最短路徑。旅行商問題還能衍生用至像車輛調(diào)度優(yōu)化問題、運輸路線規(guī)劃、物流和計算機應(yīng)用網(wǎng)絡(luò)等領(lǐng)域里，應(yīng)用方向相當廣泛。

追根溯源，18世紀中葉歐拉提出的騎士環(huán)游問題，被認為是最早開始發(fā)現(xiàn)的旅行商問題。當時研究的對象是國際象棋，眾所周知，國際象棋是64個方格，歐拉研究的是棋子走完這64個格子，每個格子僅僅走一次，然后還能回到起點。1954年Danzig等人創(chuàng)造性地解決了美利堅合眾國49城市之間的巡回路線規(guī)劃難題，用的是線性規(guī)劃算法。它還有著很多變種形式，比如歐幾里得旅行商（ETSP）、對稱旅行商（STSP）和非對稱旅行商（ATSP）等。詳細地說明，歐幾里得旅行商問題說明是所有城市間相對距離都是歐氏距離，在現(xiàn)實的二、三維物理空間里，歐氏距離為兩個端點間的實際間距。對稱問題意思為從城市A到城市B之間的距離等于從城市B到城市A的距離。非對稱問題則說明從城市A到城市B的距離不一定等于從城市B到城市A的距離，通常情況下都為不等于。此外，據(jù)實而言，某些旅行商問題還可能會增加一些約束性條件，像附有時間窗的旅行商問題（城市增加了服務(wù)時間區(qū)間屬性，旅行商到達每個城市時刻不能過早或者過晚）、附有瓶頸的旅行商（這個并不要求遍歷路線總距離最短,而是要求在遍歷路線中每次從一個城市到另一個城市時的單次距離盡可能是最短的）、中國郵遞員問題（一個郵遞員從郵局出發(fā)，走遍負責(zé)區(qū)域范圍里所有街道至少一次，再回到出發(fā)點郵局，怎么選出一條最短路徑）、以及多旅行商問題（顧名思義，由多個旅行商遍歷所有城市的問題）等。

因為條件較少，所以旅行商問題在邏輯上是比較簡單的，但其計算復(fù)雜度很高，屬于非確定性多項式時間可解的判定問題。當城市數(shù)量不斷增加，旅行商問題的計算難度會發(fā)生指數(shù)級的變化，需要強大的計算能力的輔助設(shè)備，并且計算機時間很長。常規(guī)運算方法在解決這一類問題時已經(jīng)不太現(xiàn)實，因此啟發(fā)式算法應(yīng)運而生。啟發(fā)式算法在數(shù)學(xué)上是這樣定義的：它是一種通過直觀認知和現(xiàn)實經(jīng)驗形成的算法，在相對較少的運算時間和空間花費里求得組合優(yōu)化難題的所有實例的可行的解，但是這些可行解和最優(yōu)解之間的偏離程度通常情況下無法得到提前獲取。啟發(fā)式算法最初是從仿生學(xué)中提出的概念，科學(xué)家通過仿生學(xué)中的生物行為特征和生物族群運行規(guī)律等創(chuàng)新性研究出一些算法來解決較為復(fù)雜的組合優(yōu)化問題。目前，為求解旅行商問題用到的啟發(fā)算法通常有：模擬退火算法、局部搜索算法、禁忌搜索、遺傳算法、蟻群算法、粒子群算法和蜂群算法等，還有對這些算法進行綜合研究得到的新型啟發(fā)式算法。本文研究一種改進型模擬退火法解決旅行商相關(guān)問題。

三、模擬退火算法

模擬退火算法（Simulated AnnealingAlgorithm,簡寫SA）源自固體退火現(xiàn)象，模仿固體在熔化狀態(tài)下慢慢降溫冷下來，一直持續(xù)直到最后穩(wěn)定狀態(tài)。模擬退火算法是1953年由Metropolis第一次發(fā)現(xiàn)并研究的。它是基于蒙特卡洛方法思想的一種解決優(yōu)化組合問題算法。物理現(xiàn)象中退火原理是對于一個非晶體形態(tài)的物體，首先要對其加熱到一定程度，在這個持續(xù)加熱的過程中，物體內(nèi)部的粒子的狀態(tài)將跟著加熱溫度的變高而成為無序狀態(tài)，并且離子的內(nèi)能會變大，在物體到達最高溫后，開始降溫，緩慢進行，也就是我們提到的退火，這時物體內(nèi)部粒子會在降溫過程中慢慢變得有序，逐漸平衡，在達到最后的特定溫度時候，物體變成結(jié)晶狀態(tài)，此時物體內(nèi)部粒子都排列有序。SA算法中有代表性的是Metropolis規(guī)則，這個規(guī)則Metropolis等人提出的。通常在SA中的高溫度過程中把溫度劃分為若干溫度段，每段的新解選取標準不一樣，選用Metropolis規(guī)則來比較隨機選擇組合優(yōu)化問題的最優(yōu)解，然后在持續(xù)降溫中重復(fù)選擇抽樣，一直持續(xù)至得到近似的最優(yōu)解值。

SA算法和一般的隨機搜索方法重點區(qū)別于搜索方法不同，SA既吸收隨機的理念，又借鑒物理現(xiàn)象退火過程規(guī)律，既可以在迭代運算時接受更優(yōu)解，還能在某些時候接受比目前差一些的解，增加了遍歷的靈活度。在初始階段SA算法接收劣解的概率偏低，收斂較快。在溫度繼續(xù)降低過程中接收劣解的概率逐漸變大，可以預(yù)防局部最優(yōu)陷阱。復(fù)雜度很高的問題經(jīng)常有許多局部最優(yōu)，不能只遵循選取優(yōu)解的方法，否則將會陷入局部最優(yōu)的境地，難以求出最優(yōu)解。

為了描述Metropolis規(guī)則采樣過程，如圖1所示，這里我們假設(shè)問題的初始狀態(tài)為A，狀態(tài)變化會跟著迭代，當?shù)揭欢ǔ潭群?，獲得局部最優(yōu)解B，此時B點對應(yīng)的能量低于A點，說明問題正在接近最優(yōu)解。下一步狀態(tài)跳過B點后，出現(xiàn)系統(tǒng)的能量變化上升，此時需要算法通過一個概率跳出坑，該概率與目前問題的狀態(tài)和能量值關(guān)聯(lián)較大。從B點跳出到達局部最優(yōu)C后，還會繼續(xù)通過概率繼續(xù)跳坑，直至到達全局最優(yōu)解D時，才會進入穩(wěn)定狀態(tài)。

圖1 Metropolis規(guī)則采樣示意圖

SA算法的流程描述為以下步驟：

（1）對各個參數(shù)和初始解進行初步設(shè)定，確定初溫t0和終溫tend，并且隨機生成一個初始解，用S表示，并以經(jīng)驗設(shè)定循環(huán)數(shù)R；

（2）當溫度大于終止溫度時

根據(jù)Metropolis規(guī)則產(chǎn)生新優(yōu)化解S’，把S’用概率p代替初始解S

（3）執(zhí)行結(jié)束，輸出最后結(jié)果。

SA算法的流程圖如圖2所示。

圖2 模擬退火算法流程圖

通常而言，SA算法需要滿足初始溫高、降溫慢和終溫低這三個條件，一般可以得到全局最優(yōu)解，但是這些條件需要進過反復(fù)試驗。此外，SA算法的執(zhí)行效果和初始解S設(shè)置沒什么相關(guān)性。

四、改進的SA算法

改進的SA算法使用隨機的選擇概率P，用來選擇比目前次一點的解，可以以一定的概率走出局部最優(yōu)解陷阱，實現(xiàn)全局最優(yōu)解。

設(shè)之前某個狀態(tài)為x(n)，算法通過某個指標（如梯度上升下降的能量），狀態(tài)變化為x(n+1),相應(yīng)的，算法的能量由E(n)變?yōu)镋(n+1)，定義由x(n)變?yōu)?x(n+1)的選擇概率P為

上述公式說明，當能量變小，能量轉(zhuǎn)移會被接受（此時概率為1），當能量變大時，意味著此時偏離全局最優(yōu)解，算法在此時不會拋棄該值，而是對其進行概率操作：在取值區(qū)間[0,1]中產(chǎn)生一個均勻分布的隨機數(shù)，當隨機數(shù)小于P時，說明這種轉(zhuǎn)移是被算法接受，否則拒絕轉(zhuǎn)移，進入下一步循環(huán)流程。選擇概率P的取值是動態(tài)變化的，它是大小是由能量的變化量與溫度大小決定的。

改進的SA算法流程：

（1）設(shè)定S是初始解，假設(shè)S_i=S，并設(shè)定初溫為T，令 i=0。

（2）設(shè) T=T_i，用參數(shù) T和 S_i引入 Metorpolis抽樣算法中計算，返回狀態(tài)Si作為本算法的當前解，S_i=Si。

（3）降溫流程，令 T=T_(i+1)，其中 T_(i+1)＜T_i，i=i+1。

（4）檢查是否滿足終止條件，當滿足時下一步轉(zhuǎn)到步驟(5)，否則下一步轉(zhuǎn)到步驟(2)。

（5）認定當前解S_i為最優(yōu)解，輸出最終結(jié)果，算法停止執(zhí)行。

選擇合適的初溫對本算法影響較大，初溫越高，搜索性則越強，得到最優(yōu)解的概率就越大，而其計算時間會變得很長。本算法選取初始溫度經(jīng)過反復(fù)試驗獲得。

本算法中循環(huán)鏈的鏈長表示為任何一個溫度段，或者為遍歷次數(shù)，這里我們稱循環(huán)數(shù)。循環(huán)數(shù)多，意味著遍歷時間會增長，計算時間會很長，但算法得到最優(yōu)解的概率則越大。所以，循環(huán)次數(shù)的設(shè)置我們綜合現(xiàn)實情況來進行合理設(shè)定。

本算法采用的降溫辦法為快速退火辦法，使用的降溫方程式是：T(t)=T0/1+αt，α為常數(shù)，取值小于1。快速退火辦法可以使得在高溫狀態(tài)時溫降變快，低溫時溫降變緩，這種特性吻合熱力學(xué)中的粒子運動理論。粒子在處于高溫狀態(tài)時候，內(nèi)部能量大，內(nèi)外溫度差別大，因此，熱傳遞速很快，溫降也快；而粒子處于低溫狀態(tài)時，熱量傳遞速度變緩慢，溫降也變慢。該方式可以使算法執(zhí)行深度搜索。

五、實驗

本文的實驗環(huán)境：硬件環(huán)境為CPU：Intel(R)Core(TM)i3-7100@3.90GHz；內(nèi)存：8GB；操作系統(tǒng)為 Windows10。軟件編譯環(huán)境為Python3.8。TSP問題描述為：給出既定的30座城市的坐標和每座城市之間的距離參數(shù)，求出遍歷每座城市一次并能回到出發(fā)起點城市的最短回路和最短距離。

（一）實驗步驟

（1）數(shù)據(jù)初始化：計算距離矩陣；隨機得到初始解（起點為0城市）；編寫距離計算函數(shù)。

（2）在每個溫度下，進行R次迭代。每次迭代時，需要求出新的路徑，之后后再計算出該路徑的總長度。

（3）當求出新的路徑總長小于目前路徑總長時，會同時更新目前路徑和目前路徑總長為新的路徑的；當該新路徑總長比目前最優(yōu)路徑總長還小時，會更新最優(yōu)路徑和其長度為該新路徑。

（4）當求出新的路徑總長大于或等于目路徑總長時，會通過相應(yīng)的目標函數(shù)計算出接受概率，把算法產(chǎn)生的隨機數(shù)和計算得到的接受概率進行對比，再決定是否接收新路徑（即劣解）。

（5）算法執(zhí)行檢查到當前溫度小于終止溫度的條件后，算法停止執(zhí)行，輸出最終結(jié)果，并回執(zhí)最終路線圖。

（6）調(diào)參來優(yōu)化模型。

（二）實驗結(jié)果

1.初始溫度為150，結(jié)束溫度為1e-7，循環(huán)次數(shù)為100，溫度衰減系數(shù)為0.98的旅行商最佳路線圖如圖3所示。

圖3 循環(huán)次數(shù)為100的旅行商最佳路線圖

最佳路線：[27,25,24,29,22,21,20,19,18,17,16,15,11,10,12,6,5,4,3,1,7,9,8,2,0,14,13,23,28,26]

最佳距離：441.55

運算時間:1.89秒

2.初始溫度為150，結(jié)束溫度為1e-7，循環(huán)次數(shù)為200，溫度衰減系數(shù)為0.98的旅行商最佳路線圖如圖4所示。

圖4 循環(huán)次數(shù)為200的旅行商最佳路線圖

最佳路線：[22,29,24,25,27,26,28,23,13,14,0,2,8,9,7,1,3,4,5,6,12,10,11,15,16,17,18,19,20,21]

最佳距離：433.72

運算時間:3.87秒

3.初始溫度為150，結(jié)束溫度為1e-7，循環(huán)次數(shù)為500，溫度衰減系數(shù)為0.98的旅行商最佳路線圖如圖5所示。

圖5 循環(huán)次數(shù)為500的旅行商最佳路線圖

最佳路線：[18,17,16,15,11,10,12,6,5,4,3,1,7,9,8,2,0,14,13,23,28,26,27,25,24,29,22,21,20,

最佳距離：426.30

運算時間:10.48秒

（三）實驗結(jié)果分析

實驗結(jié)果表明：算法迭代運行次數(shù)越多時，算法執(zhí)行的搜索次數(shù)更大，執(zhí)行程序運行會變慢，但此時得到的最佳距離值最優(yōu)。本算法在前期增加了新解的接受概率，可以增加算法的搜索區(qū)間，避免陷入局部最優(yōu)解；在算法的后期，減少接受新解的概率，以免丟失目前最優(yōu)解。當目標函數(shù)的差值越大時，新解的接受概率也會變得越大。當?shù)螖?shù)不斷增加，溫度下降逐漸減小，系統(tǒng)逐漸趨于穩(wěn)定狀態(tài)后，新解的接受概率會越小。

六、結(jié)語

組合優(yōu)化領(lǐng)域目前熱點問題之一便是關(guān)于旅行商問題，對旅行商問題進行相關(guān)研究有著非常重要的理論和實用意義。啟發(fā)式算法是解決組合優(yōu)化問題的良策，本文介紹了一種改進的啟發(fā)式算法及其在解決組合優(yōu)化問題中的應(yīng)用，分析該算法的詳細流程，并通過仿真實驗驗證該算法的性能，并對其優(yōu)勢和不足進行了分析。改進的模擬退火算法雖然具有空間開銷相對較小、時間消耗不大等優(yōu)點，但也存在一定的缺陷，比如其初始溫度、降溫速度等參數(shù)難以控制，不能保證一次就收斂到最優(yōu)值，通常需要多次嘗試才可求得最優(yōu)解。