楊文光，嚴(yán) 哲，隋麗麗

(華北科技學(xué)院基礎(chǔ)部，北京東燕郊 101601)

0 引言

旅行商問(wèn)題(TSP)是一個(gè)多局部最優(yōu)的復(fù)雜NP難問(wèn)題，即對(duì)于n個(gè)城市，要尋找到走遍每個(gè)城市的最短閉合路徑，并且每個(gè)城市只能經(jīng)過(guò)一次，隨著城市數(shù)n的增大，問(wèn)題的計(jì)算復(fù)雜度和時(shí)空復(fù)雜度呈指數(shù)倍增長(zhǎng)。采用傳統(tǒng)的動(dòng)態(tài)規(guī)劃技術(shù)，我們可以在O(n22n)［1］時(shí)間內(nèi)解決問(wèn)題，但是算法的效率太低計(jì)算時(shí)間難以承受。隨著計(jì)算智能算法的大量出現(xiàn)，借助巧妙的智能算法和計(jì)算機(jī)的快速迭代計(jì)算，TSP問(wèn)題的求解變得相對(duì)容易，現(xiàn)如今求解TSP問(wèn)題的方法很多，主要包括遺傳算法、蜂群算法、貪心法、模擬退火法、粒子群法、蟻群算法等［2－5］。

在伴有多局部極值的求解問(wèn)題上，全局收斂的模擬退火法［2－3］(Simulated Annealing，SA)無(wú)疑是這類問(wèn)題的有效選擇。模擬退火算法最早由Metropolis等提出，其出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過(guò)程與一般的組合優(yōu)化問(wèn)題之間的相似性，逐漸發(fā)展成一種迭代自適應(yīng)啟發(fā)式概率性搜索算法，使其具有更好的收斂性。粒子群算法(Particle Swarm Optimization，PSO)［4］是由 Eberhart和Kennedy于1995年提出的一種群體智能進(jìn)化算法，該算法通過(guò)比較新粒子的適應(yīng)度值、個(gè)體極值與群體極值的適應(yīng)度值來(lái)更新個(gè)體極值和群體極值，PSO算法的概念簡(jiǎn)單，易于實(shí)現(xiàn)，調(diào)整參數(shù)少，正在受到越來(lái)越廣泛的關(guān)注和應(yīng)用。

本文擬利用粒子群算法的全局尋優(yōu)能力，并結(jié)合模擬退火算法加以改進(jìn)，建立具有自適應(yīng)性的采用蘊(yùn)含交叉和變異的混合粒子群算法［5］。在具體尋優(yōu)過(guò)程中，本文設(shè)計(jì)的混合粒子群算法依靠自適應(yīng)尋優(yōu)策略既可以跳出局部極值，又能兼顧到局部精細(xì)搜索。最后進(jìn)行旅行商問(wèn)題(TSP)優(yōu)化求解實(shí)驗(yàn)，驗(yàn)證了算法的有效性。

1 模擬退火

模擬退火法通過(guò)溫升溫降來(lái)控制算法的搜索過(guò)程。其算法實(shí)現(xiàn)的循環(huán)過(guò)程基本為:產(chǎn)生新解→計(jì)算適應(yīng)度值→是否滿足條件，按一定速率進(jìn)行降溫到既定值，最終尋找到近似最優(yōu)值。其主要參數(shù)和迭代準(zhǔn)則為:

1)主要控制參數(shù)有降溫速率q，初始溫度T0，結(jié)束溫度Tend。

2)Metropolis準(zhǔn)則:設(shè)f(X)為模擬退火的評(píng)價(jià)函數(shù)，f(Xi)為第i次迭代后的評(píng)價(jià)函數(shù)，令df=f(Xi)－f(Xi)，則對(duì) X 接受概率為［4］:

按概率P來(lái)選擇新個(gè)體。

該算法有如下特點(diǎn):(1)以一定概率結(jié)束惡化解;(2)引進(jìn)算法控制參數(shù);(3)使用適應(yīng)度值進(jìn)行搜索;(4)搜索區(qū)域復(fù)雜。

2 混合粒子群算法

在混合粒子群算法中，粒子總數(shù)為N，每個(gè)粒子的空間位置為X，利用個(gè)體極值、全局極值和本身信息，指導(dǎo)下一步粒子狀態(tài)。標(biāo)準(zhǔn)粒子群算法的更新公式為［5］:

其中，xk為第k步粒子的狀態(tài)，vk為粒子更新的速度，pbestk為第k步粒子本身所找到的最好解的位置，gbestk為第k步整個(gè)種群目前找到的最好解的位置。作為混合粒子群算法，可將更新公式理解為:covk為粒子變異，c1(pbestk－xk)為個(gè)體現(xiàn)在狀態(tài)與個(gè)體極值交叉操作，c2(gbestk－xk)為個(gè)體現(xiàn)在狀態(tài)與全局極值交叉操作。

在TSP問(wèn)題中，交叉算子為:首先選擇兩個(gè)交叉位置，個(gè)體現(xiàn)值分別與個(gè)體極值和全局極值交叉。比如，交叉的位置為2和7，操作如下:

個(gè)體現(xiàn)值與全局極值交叉一樣。對(duì)于新的個(gè)體，采用保留優(yōu)秀個(gè)體策略。

變異操作:隨機(jī)選取個(gè)體變異位置p1和p2，然后交換兩位置，設(shè)p1=3，p2=5，交換如下:

同樣，也采用保留優(yōu)秀個(gè)體策略。

3 自適應(yīng)尋優(yōu)策略

為了使算法跳出局部極值，使算法更加穩(wěn)定，在本算法連續(xù)△k次降溫，一直保持 gbestk－1－gbestk＜a(gbestk為第k次降溫的全局最優(yōu)適應(yīng)度值，a為某一設(shè)定正數(shù))，將此作為陷入局部極值的判定依據(jù)［6］。當(dāng)△k≥K(K為設(shè)定的某正整數(shù))時(shí)，采用自適應(yīng)尋優(yōu)，獲得新個(gè)體;否則，繼續(xù)按原來(lái)算法進(jìn)行降溫。

自適應(yīng)搜索階段:

新點(diǎn)X在取值空間A中最佳點(diǎn)pbest鄰域按正態(tài)分布隨機(jī)擾動(dòng)產(chǎn)生［6］:

XU和XL分別為X的上下限;為了保證X1∈［XL，XU］，引入以下方法進(jìn)行修正:

其中，mod(*)為取余運(yùn)算;X=roundn(X1，0);將X中重復(fù)的元素保留一個(gè)，再將缺失的元素補(bǔ)充進(jìn)去，最終得到X。其中“o”為Hadamard乘積，b為搜索半徑調(diào)節(jié)半徑，I為自適應(yīng)因子，y為單位向量。

Tk為當(dāng)前第 k次迭代的溫度，mk為(0，5)的均勻隨機(jī)分布。當(dāng)Tk≥1時(shí)，搜索在一個(gè)較大的半徑內(nèi)進(jìn)行，保證算法的全局搜索能力;當(dāng)Tk＜1，相對(duì)搜索半徑很小，使其在局部進(jìn)行更精細(xì)的搜索，以提高精度。

I決定該算法以一定概率進(jìn)行自適應(yīng)尋優(yōu)，αi取(0，1)均勻隨機(jī)數(shù)，β自適應(yīng)概率。

Gaussian是標(biāo)準(zhǔn)正態(tài)分布隨機(jī)向量，‖＊‖為范數(shù)。

4 融入自適應(yīng)模擬退火與混合粒子群的算法

利用模擬退火法的全局收斂特性，克服混合粒子群算法易于陷入局部最優(yōu)值的缺陷，尤其在高維多峰值的情況下，模擬退火與粒子群的混合算法易造成算法不穩(wěn)定，因此引入自適應(yīng)尋優(yōu)策略，在每降溫一次的情況下，進(jìn)行一次局部收斂性判斷。

模擬退火算法是50年代初發(fā)展起來(lái)的一種隨機(jī)性組合優(yōu)化方法。它模擬高溫金屬降溫的熱力學(xué)過(guò)程，并廣泛應(yīng)用于組合優(yōu)化問(wèn)題。模擬退火在進(jìn)行優(yōu)化時(shí)先確定初始溫度，隨機(jī)選擇一個(gè)初始狀態(tài)并考察該狀態(tài)的目標(biāo)函數(shù)值;對(duì)當(dāng)前狀態(tài)附加一小擾動(dòng)，并計(jì)算新狀態(tài)的目標(biāo)函數(shù)值;以概率1接受較好點(diǎn)，以某種概率Pr接受較差點(diǎn)作為當(dāng)前點(diǎn)，直到系統(tǒng)冷卻。模擬退火方法在初始溫度足夠高、溫度下降足夠慢的條件下，能以概率1收斂到全局最優(yōu)值，由于它以某種概率接受較差點(diǎn)，從而具有跳出局部最優(yōu)解的能力。其算法流程如下:

圖1 算法流程

5 實(shí)驗(yàn)仿真

實(shí)驗(yàn)數(shù)據(jù)取51個(gè)城市，即n=51，初始溫度T0=500，結(jié)束溫度Tend=0.1，降溫速率q=0.95;粒子個(gè)數(shù)individual=80，粒子群進(jìn)化最大代數(shù)nMax=50。本實(shí)驗(yàn)運(yùn)用MATLAB進(jìn)行。將混合粒子群算法［10］和本文算法各隨機(jī)運(yùn)行15次，進(jìn)行算法比較。圖3為本文算法求解的最優(yōu)路徑，圖4為本文算法迭代尋優(yōu)過(guò)程。

圖2 城市分布

圖3 最優(yōu)路徑

圖4 尋優(yōu)過(guò)程

在城市規(guī)模達(dá)到51個(gè)的情況下，本文算法僅僅運(yùn)行了100 s，降溫次數(shù)在60次左右即達(dá)到穩(wěn)定狀態(tài)，表現(xiàn)出了強(qiáng)大的搜索能力。為了說(shuō)明本文算法的有效性，表1給出了混合粒子群算法與本文算法的對(duì)比情況。從表1可以看到，本文設(shè)計(jì)的算法在最優(yōu)路徑長(zhǎng)度和平均路徑長(zhǎng)度都要優(yōu)于混合粒子群算法。

表1 算法結(jié)果比較

6 結(jié)論

本文針對(duì)混合粒子群算法在求解TSP問(wèn)題中存在的缺陷，將模擬退火法引入到混合粒子群中，達(dá)到了改善優(yōu)化求解和避免陷入局部最優(yōu)的目的。首先將自適應(yīng)尋優(yōu)策略應(yīng)用于模擬退火的每次降溫，便于跳出局部最優(yōu)。而在進(jìn)行完粒子群既定迭代次數(shù)后，自適應(yīng)尋優(yōu)策略將會(huì)判斷所得最優(yōu)極值是否為局部極值，最后在一定概率下進(jìn)行自適應(yīng)尋優(yōu)。這樣既避免算法陷入局部極值，也可讓算法較精確地進(jìn)行局部搜索。通過(guò)仿真實(shí)驗(yàn)驗(yàn)證，表明該算法具有良好的全局收斂性能，對(duì)于TSP問(wèn)題的實(shí)際優(yōu)化求解具有很好的借鑒意義。

［1］ HELD M，KARP R M.A Dynamic Programming Approach to Sequencing Problems［J］.Journal of the Society for Industrial and Applied Mathematics，1962，10(1):196 －210.

［2］ 馮劍，岳琪.模擬退火算法求解TSP問(wèn)題［J］.森林工程，2008，24(01):94 －96.

［3］ 楊艷霞.一種基于模擬退火操作的混合差分進(jìn)化算法［J］.智能系統(tǒng)學(xué)報(bào)，2014，9(1):1－6.

［4］ 張建航，李國(guó).模擬退火算法及其在求解TSP中的應(yīng)用［J］. 現(xiàn)代電子技術(shù)，2006(22):157－158.

［5］ 高尚，韓斌，等.求解旅行商問(wèn)題的混合粒子群優(yōu)化算法［J］. 控制與決策，2004，19(11):1286 －1289

［6］ 孫士平，吳建軍.直接搜索模擬退火法的自適應(yīng)改進(jìn)［J］.計(jì)算機(jī)工程與應(yīng)用，2014，

［7］ 馮玉榮，朱均燕.模擬退火法算法收斂性研究［J］.福建電腦，2006(12):46－47.

［8］ 高海昌，馮博琴，朱利.智能優(yōu)化算法求解TSP問(wèn)題［J］.控制與決策，2006，21(3):241－247，252.

［9］ 王凌.智能算法及其應(yīng)用［M］.北京:清華大學(xué)出版社.2001.

［10］ 史峰，王輝，等.MATLAB智能算法30案列分析［M］.北京:北京航天航空大學(xué)出版社，2011.