求解動(dòng)態(tài)TSP問題的化學(xué)反應(yīng)算法研究

歐陽陳華 李向秀 夏曉

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

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

根據(jù)節(jié)點(diǎn)隨機(jī)變化前的分子結(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]的隨機(jī)數(shù)。節(jié)點(diǎn)變化后的距離與之前距離基本始終處在同一范圍內(nèi)，只要所有距離修改的總和不超過ALL，更新節(jié)點(diǎn)的過程就會(huì)繼續(xù)。

2 CRA For TSP

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

2.1 TSP CRA的基本版本

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

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

2.2 并行的CRA算法

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

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

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

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

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

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

3 實(shí)驗(yàn)

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

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

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

4 結(jié)論

近來，化學(xué)反應(yīng)優(yōu)化算法備受關(guān)注。本文用它來解決動(dòng)態(tài)旅行商問題。實(shí)驗(yàn)結(jié)果有力地表明，化學(xué)反應(yīng)算法能夠有效地處理快速變化的城市節(jié)點(diǎn)群。它的性能不亞于標(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)化算法的序列比對(duì)研究[D].湖南大學(xué)，2014.