旅行商問題(TSP)是經典的NP難問題,節點可變的TSP問題被稱為動態旅行商問題(DTSP)。通過研究化學反應算法(CRA),并對CRA算法并行化實現,能夠解決DTSP問題。實驗結果表明,CRA算法能夠有效地處理快速變化的DTSP問題,且性能不亞于其它元啟發式算法。

　　關鍵詞:動態TSP問題；遷移算子；CRA并行實現

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

　　1DTSP-動態旅行商問題

　　TSP問題的描述雖然簡單,但卻是典型的NP難問題。暴力求解TSP問題的時間復雜度是O(n!),其中n是城市(節點)的數量。已知的精確算法可以將時間復雜度降為O(n22n)[2],但對于更大的n而言,仍然需要更優的啟發式算法。

　　1.1DTSP的相關工作

　　Psaraftis提出了DTSP問題,在文獻[3]中他論證了DTSP的一般屬性和一些有用的性能指標,但未提出任何能夠解決DTSP問題的具體方案。節點的變化會改變原有的距離,使得原有的搜索序列基本無效。因此,許多嘗試解決DTSP問題的方法都使用了全局或者局部搜索重置策略[4]。全局重置策略只要檢測到更改,就會激活全局重置,將所有搜索序列重置為默認值。局部重置策略僅更改節點群的動態變化區域的搜索序列,使得節點群至少有一部分之前收集的路線是可以利用的。節點發生變化的時間和地點是DTSP問題的已知條件,必不可少。上述方法有一個主要的缺點是引入動態的方式。距離數組的更改僅由單個節點的刪除、引入或一系列此類操作組成,并且以規律的間隔激活。因此,節點群可以保持其之前大部分的解決方案不變,因為節點間距離變化的影響是有限的。實際上,很多場景下節點的變化是比較大的。因此,引入分子結構來替代不斷變化的動態節點,通過CRA算法來測量最短路線,并對CRA算法在DTSP問題上的性能進行測試和評估。

　　1.2分子結構

　　在CRA中,用分子結構來模擬每一個解,分子結構的勢能就是一條路線,勢能的最小值就是問題的最優函數解。每次節點變化都會形成新的分子勢能,也就是新的路線,該路線的距離求值操作由以下三個參數控制:(1)總改變(ALL):所有變化節點間距離的總和,是一個>0的實數;(2)改變率(ROC):變化節點的限制參數,是一個范圍為[0,1]的實數;(3)改變頻率(FOC):每次變化之間的間隔,以毫秒為單位。根據節點隨機變化前的分子結構,和變化后的分子結構,容易得到距離公式1和距離公式2。Dnew=Dold+(1-Dold)*rand()*ROC(1)Dnew=Dold-Dold*rand()*ROC(2)函數rand()生成范圍為[0,1]的隨機數。節點變化后的距離與之前距離基本始終處在同一范圍內,只要所有距離修改的總和不超過ALL,更新節點的過程就會繼續。

　　2CRAForTSP

　　化學反應算法的靈感來自于現實世界中分子與分子之間產生的化學反應,而將CRA用于TSP是元啟發式算法的選擇之一。

　　2.1TSPCRA的基本版本

　　GA、CRA和其他相關的啟發式算法的操作很簡單:由實數構成的二維數組表示一個圖,其中的距離代表兩個城市/節點之間的距離,于是可以得到一個初始的分子結構。啟發式算法的工作都采用迭代方式。經典GA算法是模擬自然界生物進化的演變而總結出來的算法,其主要過程由初始群體的逐代進化,即上一代進化成下一代,代代相傳,最后得到最優一代的過程。GA的每代進化操作主要有三個,選擇、交叉和變異:選擇操作主要是選擇當前區域里的較優解,即局部優化,慢慢向最優解靠近;交叉主要是產生最優解;變異主要是跳出局部最優,覆蓋其它區域的解。CRA算法的迭代操作主要由4個反應組成:撞墻、分解、交換和合成。撞墻反應與GA算法中的變異操作類似,但是撞墻反應在CRA中的作用不一樣,目的是繼承原分子的優秀勢能并向局部最優逼近;交換反應與GA算法中的交叉操作類似,目的是產生最優解;分解和合成的目的都是逃離局部最優,擴大解的覆蓋面。CRA算法中有2個步驟進行了全局覆蓋,因此CRA算法相對于GA算法應該具備更高的全局搜索能力,取得全局最優解的概率較GA算法高。提高CRA算法性能的關鍵因素在于提高四個基本反應的效率,優化發生化學反應的方法[5]。選擇CRA四個反應的算子參數并非易事。例如,在文獻[6]中可以找到它們對CRA操作的影響分析。對于當前的研究,足以知道最大的改進可能會在早期迭代中發生。節點選擇需要許多浮點計算,因此非常耗時。對于動態TSP,可用于交付解決方案的時間是至關重要的因素。因此,引入了并行的化學反應優化算法。

　　2.2并行的CRA算法

　　將CRA算法改寫成適用于多處理機的算法是非常直截了當的。大概有兩種方法可以值得使用:(1)讓每個處理器獨立地運行于分子集合的一個隔離子代上,通過遷移與其它處理器周期地共享它的那些最優分子。每個處理器首先獨立地生成它自己的初始分子集合。然后每個處理器對第k代分子集合進行適應性的評估,根據評估結果從它的第k代分子集合中選擇優秀個體以用來生成第k+1代分子集合,在它的第k+1代分子集合上完成撞墻、分解、交換和合成計算。在經歷上述k代后(k>=1),這些處理器就與其它的處理器通過遷移算子(migrationoperator)共享它們的最優分子。當將遷移結合進來后,分子集合的變化就不再僅僅是由于繼承其父代的基因造成的,偶爾也會有隨機突變所造成的,以及引入新的品種所造成的。在CRA算法中,遷移算子要負責的任務是在分子集合間實現個體的交換。在并行環境中,從每個分子集合中選擇最優的分子進行遷移,并將已接收的分子融合到集合中以替代最差的分子將導致更快的收斂。所以通過從一個分子集合中拷貝一些較優的分子到另一分子集合以代替最差的分子將會達到更快的收斂。但是,以這種方式進行選擇和融合最終將對分子集合施加太多的選擇壓力,從而可能阻礙最優解的生成。此外,如果選擇壓力過大的話,可能使結果的引進趨向局部優化而非全局優化。(2)第二種方法讓每個處理器在一個公共的分子集合上完成算法中的每一步的一部分——撞墻、分解、交換和合成。因此,至少需要一個4核CPU或者能提供4個同時進程的處理器才能實現該算法的并行化。

　　3實驗

　　在實驗過程中,使用了兩個城市節點群,一個節點群的節點在距離上發生了較大變化(CityBC),另一個節點群的節點發生了較小的變化(CitySC)。但是它們有一個共同點:具有相同的初始節點數50個,總改變(ALL)等于20,改變頻率(FOC)等于2s。唯一的區別是它們的改變率ROC。CitySC等于0.15,CityBC等于0.35。取距離變化修改的平均數,CitySC是380,CityBC是850。這意味著CityBC幾乎改變了總距離的一半以上,節點變化比較頻繁。CitySC的距離變化量較少,因為變化的節點較少。表1顯示了節點動態變化大的節點群(CityBC)和節點動態變化小的節點群(CitySC)的CRA算法的性能對比。CityBC的節點變化數從2到15,改變率10%到30%;CitySC的節點變化數從1到8,改變率1%到8%。迭代次數50或者100。從時間和結果來看,迭代50次的算法運行時間明顯小于迭代100次的,但是差距不大。節點變化大的節點群,算法運行速度慢于節點變化小的節點群。

　　4結論

　　近來,化學反應優化算法備受關注。本文用它來解決動態旅行商問題。實驗結果有力地表明,化學反應算法能夠有效地處理快速變化的城市節點群。它的性能不亞于標準GA。還有很多方面需要進一步研究,例如:迭代次數、可變性與CRA算法的密切相關性;最優解的精度即結果的誤差等。這些主題的研究工作目前正在進行中。

　　作者：歐陽陳華 李向秀 夏曉 單位：衡陽師范學院計算機科學與技術學院