歐陽陳華 李向秀 夏曉

摘要：旅行商問題（TSP）是經(jīng)典的NP難問題，節(jié)點可變的TSP問題被稱為動態(tài)旅行商問題（DTSP）。通過研究化學(xué)反應(yīng)算法（CRA），并對CRA算法并行化實現(xiàn)，能夠解決DTSP問題。實驗結(jié)果表明，CRA算法能夠有效地處理快速變化的DTSP問題，且性能不亞于其它元啟發(fā)式算法。

關(guān)鍵詞：動態(tài)TSP問題;遷移算子;CRA并行實現(xiàn)

中圖分類號：TP301 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9416（2019）11-0115-02

0 引言

經(jīng)典TSP問題的描述十分簡單：給定一個城市列表以及每兩個城市之間的距離，任務(wù)是找到一條最短路線，該路線要不重復(fù)地訪問每個城市節(jié)點一次。TSP問題是人工智能的經(jīng)典問題之一，CRA算法是用來解決TSP問題的啟發(fā)式算法之一[1]。經(jīng)典TSP問題在現(xiàn)實生活中的應(yīng)用其實非常有限，因為在很大部分的TSP問題應(yīng)用場景中，節(jié)點之間的距離是變化的。這種節(jié)點間距離會變化的TSP問題被稱為動態(tài)TSP問題。動態(tài)TSP問題的解決遠(yuǎn)比靜態(tài)TSP問題更復(fù)雜，CRA算法具備求解動態(tài)TSP問題的可行性。

1 DTSP-動態(tài)旅行商問題

TSP問題的描述雖然簡單，但卻是典型的NP難問題。暴力求解TSP問題的時間復(fù)雜度是O（n?。渲衝是城市（節(jié)點）的數(shù)量。已知的精確算法可以將時間復(fù)雜度降為O（n22n）[2]，但對于更大的n而言，仍然需要更優(yōu)的啟發(fā)式算法。

1.1 DTSP的相關(guān)工作

Psaraftis提出了DTSP問題，在文獻(xiàn)[3]中他論證了DTSP的一般屬性和一些有用的性能指標(biāo)，但未提出任何能夠解決DTSP問題的具體方案。節(jié)點的變化會改變原有的距離，使得原有的搜索序列基本無效。因此，許多嘗試解決DTSP問題的方法都使用了全局或者局部搜索重置策略[4]。全局重置策略只要檢測到更改，就會激活全局重置，將所有搜索序列重置為默認(rèn)值。局部重置策略僅更改節(jié)點群的動態(tài)變化區(qū)域的搜索序列，使得節(jié)點群至少有一部分之前收集的路線是可以利用的。節(jié)點發(fā)生變化的時間和地點是DTSP問題的已知條件，必不可少。

上述方法有一個主要的缺點是引入動態(tài)的方式。距離數(shù)組的更改僅由單個節(jié)點的刪除、引入或一系列此類操作組成，并且以規(guī)律的間隔激活。因此，節(jié)點群可以保持其之前大部分的解決方案不變，因為節(jié)點間距離變化的影響是有限的。實際上，很多場景下節(jié)點的變化是比較大的。

因此，引入分子結(jié)構(gòu)來替代不斷變化的動態(tài)節(jié)點，通過CRA算法來測量最短路線，并對CRA算法在DTSP問題上的性能進(jìn)行測試和評估。

1.2 分子結(jié)構(gòu)

在CRA中，用分子結(jié)構(gòu)來模擬每一個解，分子結(jié)構(gòu)的勢能就是一條路線，勢能的最小值就是問題的最優(yōu)函數(shù)解。

每次節(jié)點變化都會形成新的分子勢能，也就是新的路線，該路線的距離求值操作由以下三個參數(shù)控制：

（1）總改變（ALL）：所有變化節(jié)點間距離的總和，是一個> 0的實數(shù);（2）改變率（ROC）：變化節(jié)點的限制參數(shù)，是一個范圍為[0，1]的實數(shù);（3）改變頻率（FOC）：每次變化之間的間隔，以毫秒為單位。

根據(jù)節(jié)點隨機變化前的分子結(jié)構(gòu)，和變化后的分子結(jié)構(gòu)，容易得到距離公式1和距離公式2。

Dnew=Dold+（1-Dold）*rand（）*ROC? ? ? ? ? ? ? ? ? ? ? （1）

Dnew=Dold-Dold*rand（）*ROC? ? ? ? ? ? ? ? ? ? ? ? ?（2）

函數(shù)rand（）生成范圍為[0，1]的隨機數(shù)。節(jié)點變化后的距離與之前距離基本始終處在同一范圍內(nèi)，只要所有距離修改的總和不超過ALL，更新節(jié)點的過程就會繼續(xù)。

2 CRA For TSP

化學(xué)反應(yīng)算法的靈感來自于現(xiàn)實世界中分子與分子之間產(chǎn)生的化學(xué)反應(yīng)，而將CRA用于TSP是元啟發(fā)式算法的選擇之一。

2.1 TSP CRA的基本版本

GA、CRA和其他相關(guān)的啟發(fā)式算法的操作很簡單：由實數(shù)構(gòu)成的二維數(shù)組表示一個圖，其中的距離代表兩個城市/節(jié)點之間的距離，于是可以得到一個初始的分子結(jié)構(gòu)。啟發(fā)式算法的工作都采用迭代方式。經(jīng)典GA算法是模擬自然界生物進(jìn)化的演變而總結(jié)出來的算法，其主要過程由初始群體的逐代進(jìn)化，即上一代進(jìn)化成下一代，代代相傳，最后得到最優(yōu)一代的過程。GA的每代進(jìn)化操作主要有三個，選擇、交叉和變異：選擇操作主要是選擇當(dāng)前區(qū)域里的較優(yōu)解，即局部優(yōu)化，慢慢向最優(yōu)解靠近;交叉主要是產(chǎn)生最優(yōu)解;變異主要是跳出局部最優(yōu)，覆蓋其它區(qū)域的解。CRA算法的迭代操作主要由4個反應(yīng)組成：撞墻、分解、交換和合成。撞墻反應(yīng)與GA算法中的變異操作類似，但是撞墻反應(yīng)在CRA中的作用不一樣，目的是繼承原分子的優(yōu)秀勢能并向局部最優(yōu)逼近;交換反應(yīng)與GA算法中的交叉操作類似，目的是產(chǎn)生最優(yōu)解;分解和合成的目的都是逃離局部最優(yōu)，擴大解的覆蓋面。CRA算法中有2個步驟進(jìn)行了全局覆蓋，因此CRA算法相對于GA算法應(yīng)該具備更高的全局搜索能力，取得全局最優(yōu)解的概率較GA算法高。提高CRA算法性能的關(guān)鍵因素在于提高四個基本反應(yīng)的效率，優(yōu)化發(fā)生化學(xué)反應(yīng)的方法[5]。

選擇CRA四個反應(yīng)的算子參數(shù)并非易事。例如，在文獻(xiàn)[6]中可以找到它們對CRA操作的影響分析。對于當(dāng)前的研究，足以知道最大的改進(jìn)可能會在早期迭代中發(fā)生。節(jié)點選擇需要許多浮點計算，因此非常耗時。對于動態(tài)TSP，可用于交付解決方案的時間是至關(guān)重要的因素。因此，引入了并行的化學(xué)反應(yīng)優(yōu)化算法。

2.2 并行的CRA算法

將CRA算法改寫成適用于多處理機的算法是非常直截了當(dāng)?shù)?。大概有兩種方法可以值得使用：

（1）讓每個處理器獨立地運行于分子集合的一個隔離子代上，通過遷移與其它處理器周期地共享它的那些最優(yōu)分子。

每個處理器首先獨立地生成它自己的初始分子集合。然后每個處理器對第k代分子集合進(jìn)行適應(yīng)性的評估，根據(jù)評估結(jié)果從它的第k代分子集合中選擇優(yōu)秀個體以用來生成第k+1代分子集合，在它的第k+1代分子集合上完成撞墻、分解、交換和合成計算。在經(jīng)歷上述k代后（k>=1），這些處理器就與其它的處理器通過遷移算子（migration operator）共享它們的最優(yōu)分子。

當(dāng)將遷移結(jié)合進(jìn)來后，分子集合的變化就不再僅僅是由于繼承其父代的基因造成的，偶爾也會有隨機突變所造成的，以及引入新的品種所造成的。在CRA算法中，遷移算子要負(fù)責(zé)的任務(wù)是在分子集合間實現(xiàn)個體的交換。

在并行環(huán)境中，從每個分子集合中選擇最優(yōu)的分子進(jìn)行遷移，并將已接收的分子融合到集合中以替代最差的分子將導(dǎo)致更快的收斂。所以通過從一個分子集合中拷貝一些較優(yōu)的分子到另一分子集合以代替最差的分子將會達(dá)到更快的收斂。但是，以這種方式進(jìn)行選擇和融合最終將對分子集合施加太多的選擇壓力，從而可能阻礙最優(yōu)解的生成。此外，如果選擇壓力過大的話，可能使結(jié)果的引進(jìn)趨向局部優(yōu)化而非全局優(yōu)化。

（2）第二種方法讓每個處理器在一個公共的分子集合上完成算法中的每一步的一部分——撞墻、分解、交換和合成。因此，至少需要一個4核CPU或者能提供4個同時進(jìn)程的處理器才能實現(xiàn)該算法的并行化。

3 實驗

在實驗過程中，使用了兩個城市節(jié)點群，一個節(jié)點群的節(jié)點在距離上發(fā)生了較大變化（CityBC），另一個節(jié)點群的節(jié)點發(fā)生了較小的變化（CitySC）。但是它們有一個共同點：具有相同的初始節(jié)點數(shù)50個，總改變（ALL）等于20，改變頻率（FOC）等于2s。

唯一的區(qū)別是它們的改變率ROC。CitySC等于0.15，CityBC等于0.35。取距離變化修改的平均數(shù)，CitySC是380，CityBC是850。這意味著CityBC幾乎改變了總距離的一半以上，節(jié)點變化比較頻繁。CitySC的距離變化量較少，因為變化的節(jié)點較少。

表1顯示了節(jié)點動態(tài)變化大的節(jié)點群（CityBC）和節(jié)點動態(tài)變化小的節(jié)點群（CitySC）的CRA算法的性能對比。CityBC的節(jié)點變化數(shù)從2到15，改變率10%到30%;CitySC的節(jié)點變化數(shù)從1到8，改變率1%到8%。迭代次數(shù)50或者100。從時間和結(jié)果來看，迭代50次的算法運行時間明顯小于迭代100次的，但是差距不大。節(jié)點變化大的節(jié)點群，算法運行速度慢于節(jié)點變化小的節(jié)點群。

4 結(jié)論

近來，化學(xué)反應(yīng)優(yōu)化算法備受關(guān)注。本文用它來解決動態(tài)旅行商問題。實驗結(jié)果有力地表明，化學(xué)反應(yīng)算法能夠有效地處理快速變化的城市節(jié)點群。它的性能不亞于標(biāo)準(zhǔn)GA。

還有很多方面需要進(jìn)一步研究，例如：迭代次數(shù)、可變性與CRA算法的密切相關(guān)性;最優(yōu)解的精度即結(jié)果的誤差等。這些主題的研究工作目前正在進(jìn)行中。

參考文獻(xiàn)

[1] Albert Y.S.Lam，Victor O.K.Li.Chemical-Reaction-Inspired Metaheuristic for Optimization，Evolutionary-Computation[J].IEEE-Transactions-on Evolutionary Computation，2010，6（3）：381-399.

[2] Michael Held，Richard M.Karp.A dynamic programming approach to sequencing problems[J].Journal of the Society for Industrial and Applied Mathematics，1962，10（1）：196-210.

[3] Psarafits，H.N. Dynamic vehicle routing： status and prospects[J].Annals of Operations Research，1995，61（1）：143-164.

[4] Guntsch，M.，Middendorf，M.Pheromone modifcation strategies for ant algorithms applied to dynamic TSP[J].Applications of Evolutionary Computation，2001，2037（6）：213-222.

[5] 歐陽陳華.求解TSP問題的化學(xué)反應(yīng)優(yōu)化算法研究[D].湖南大學(xué)，2014.

[6] 黃丹青.基于混合化學(xué)反應(yīng)優(yōu)化算法的序列比對研究[D].湖南大學(xué)，2014.