陰陽對優(yōu)化算法在旅行商問題中的推廣與應(yīng)用

樊志領(lǐng)，郭東威，陳 娜，劉 偉

(周口師范學(xué)院 數(shù)學(xué)與統(tǒng)計學(xué)院，河南 周口 466001)

陰陽對優(yōu)化算法(Yin-Yang-pair optimization, YYPO)是由Varun Punnathana等人于 2016 年提出的一種用于求解連續(xù)型單目標(biāo)優(yōu)化問題的元啟發(fā)式優(yōu)化算法[1]。YYPO算法的靈感來自于宇宙中廣泛存在的對偶關(guān)系，如男和女、光明與黑暗、正負(fù)電荷、波粒二象性、二進(jìn)制中的0和1等。這種對偶關(guān)系在中國古典著作《易經(jīng)》中被稱為陰和陽，陰和陽兩種狀態(tài)在保持著對偶關(guān)系的同時，還會在一定條件和程度下相互依存與轉(zhuǎn)化。YYPO算法受到這種對偶關(guān)系的啟發(fā)，尋求搜索空間中的全局探索和局部開發(fā)之間的平衡狀態(tài)，實現(xiàn)對復(fù)雜優(yōu)化問題的解空間的高效搜索。

旅行售貨員問題(Travelling Salesman Problem, TSP)是圖論中一個經(jīng)典的組合優(yōu)化問題，也是一個典型的NP-完全問題(NP-complete problem, NPC)，其目標(biāo)是在一個賦權(quán)圖中找一條遍歷所有節(jié)點并回到出發(fā)點的最短路線[2-3]。按照權(quán)重和旅行線路的多少，TSP問題可分為對稱TSP問題、非對稱TSP問題、多TSP問題三類，目前這三類問題均有不同的求解方法[4]。在一個節(jié)點數(shù)為n的賦權(quán)完全圖中，TSP問題可行解的數(shù)量是(n-1)!，當(dāng)網(wǎng)絡(luò)中節(jié)點數(shù)量較多時，求TSP問題的精確解通常是困難的。因此，如遺傳算法(Genetic Algorithm, GA)、分布估計算法(Estimation of Distribution Algorithm, EDA)、陰陽算法(Yin-Yang Algorithm , YYA)等優(yōu)化算法常被用來求TSP問題的近似最優(yōu)解。

GA算法是由美國的Holland于20世紀(jì)70年代提出的一種優(yōu)化算法，該算法模擬了生物進(jìn)化論中的自然進(jìn)化過程，通過選擇、交叉、變異三個算子和迭代的方式求解優(yōu)化問題[5-6]。目前，GA算法被廣泛應(yīng)用于TSP問題、路徑規(guī)劃問題、生產(chǎn)調(diào)度問題等組合優(yōu)化問題。張群等[7]通過改進(jìn)的模糊邏輯控制器實現(xiàn)交叉概率和變異概率的動態(tài)調(diào)整，提高了GA算法求解混合車輛路徑問題的收斂速度。郭東威等[8]提出了易位組合交叉算子、單車路徑重排策略及需求對換策略，提高GA算法的尋優(yōu)性能，有效求解了400個客戶點的PDPTW國際算例集。

EDA算法的概念最早在1996年被提出，該算法通過統(tǒng)計學(xué)習(xí)的手段建立解空間內(nèi)個體的概率分布模型，然后利用概率模型產(chǎn)生新的種群，通過迭代實現(xiàn)種群的優(yōu)化[9-10]。Peter A N和Bosman等[11]研究了將EDA算法從離散型問題推廣到連續(xù)型問題，同時保持算法性能的方法。Dirk Sudholt等[12]從EDA算法中的更新強(qiáng)度入手，通過對算法步長的研究，提出了在全局優(yōu)化中設(shè)置更新強(qiáng)度的新準(zhǔn)則。

YYA算法是由Tam S C等人結(jié)合中國古典著作《易經(jīng)》中的陰和陽的概念，于2011年提出的一種專門用來求解TSP問題的算法，該算法利用《易經(jīng)》中卦象之間的復(fù)卦、綜卦和交互卦等三種轉(zhuǎn)化方式，設(shè)計了變異、翻轉(zhuǎn)和交互三個算子求解TSP問題[13]。值得說明的是，YYA算法與YYPO算法僅僅在名稱方面有相似之處，在算法流程及操作過程中并沒有類似之處[1]。

目前，YYPO算法主要被應(yīng)用于求解連續(xù)型變量的優(yōu)化問題，而TSP問題是一個離散型優(yōu)化問題。本文針對YYPO算法和TSP問題的特點，將YYPO算法推廣到TSP問題這一典型的離散型優(yōu)化問題的求解中，設(shè)計出了一種離散型陰陽對優(yōu)化算法(Discrete Yin-Yang-pair optimization, DYYPO)，并將該算法的求解結(jié)果與GA算法、EDA算法、YYA算法的求解結(jié)果相比較。結(jié)果表明，DYYPO算法在求解TSP問題時，比GA算法、EDA算法、YYA算法更有效。

1 YYPO算法

YYPO算法對所有的變量都作歸一化處理，將其映射到從0到1的實數(shù)區(qū)間內(nèi)，在迭代過程中通過分裂和存檔兩個階段，利用P1點(開發(fā)點)和P2點(探索點)的擇優(yōu)交換實現(xiàn)種群的尋優(yōu)過程。在YYPO算法中，P1的主要任務(wù)是開發(fā)，即開發(fā)可能出現(xiàn)最優(yōu)解的潛在區(qū)域，獲得更好的解；P2的主要任務(wù)是搜索，即擴(kuò)大算法的搜索范圍，尋找可能出現(xiàn)最優(yōu)解的潛在區(qū)域。開發(fā)點P1和搜索點P2分別是以δ1和δ2為半徑的超球體的中心，在算法的迭代過程中，以超球體的中心和半徑隨機(jī)生成新的附加點，且P1和P2會以一定的條件互換，以實現(xiàn)開發(fā)和探索之間的平衡。YYPO算法的迭代過程分為分裂和存檔兩個階段，超球體的半徑δ1和δ2受縮放因子α的控制分別具有增加和減小的趨勢，確保了算法的收斂性。

1.1 參數(shù)初始化

1.2 分裂階段

在分裂階段，將P1和P2的相同副本保存為S，S的更新方式有單路分裂和D路分裂兩種方式，這兩種方式在迭代過程中會以同樣的概率被隨機(jī)選擇。單路分裂更新公式為

式中的上標(biāo)為變量序號；下標(biāo)為點序號；r為0到1之間的隨機(jī)數(shù)；δ為搜索半徑。

D路分裂更新公式為

1.3 存檔階段

在存檔階段，首先比較P1和P2的適應(yīng)值，若P2的適應(yīng)值優(yōu)于P1，則將P1和P2，δ1和δ2的值互換。然后根據(jù)存檔次數(shù)I的取值范圍[Imin,Imax]隨機(jī)生成I的值，根據(jù)分裂階段得到的結(jié)果進(jìn)行存檔，若存儲的最佳點P0比P1和P2的適應(yīng)值更好，則將P0與P1和P2交換。存檔結(jié)束后，根據(jù)如下公式更新搜索半徑δ1和δ2

式中δ1和δ2分別為P1和P2的搜索半徑，α為縮放因子。

由上式可知，隨著迭代的進(jìn)行，δ1和δ2會分別呈下降和增長趨勢，其中δ1的下降會保證算法的收斂。由于δ2隨著迭代的進(jìn)行呈增長趨勢，因此須將δ2的最大值進(jìn)行限定，通常取最大值為0.75。YYPO算法的詳細(xì)過程可參考文獻(xiàn)[1]。

2 TSP問題

TSP問題是指一名售貨員從初始節(jié)點出發(fā)，經(jīng)過其他所有節(jié)點，以最短的路徑返回出發(fā)點的問題，該問題是一個非常著名的離散型的組合優(yōu)化問題。TSP問題研究歷史十分悠久，最早的研究開始于1759年，著名數(shù)學(xué)家Euler提出的在國際象棋棋盤上的騎士環(huán)游問題，Menger于1930年提出了TSP問題的一般數(shù)學(xué)模型，1954年Danzig等人利用割平面法解決了一個49個城市的巡回問題。TSP問題的數(shù)學(xué)模型為

對于節(jié)點數(shù)較少的TSP問題，可以通過線性規(guī)劃方法或者窮舉法求得問題的最優(yōu)解。但由于TSP問題是一個NPC問題，當(dāng)節(jié)點數(shù)超過100時，可行解的個數(shù)將超過10 150，此時利用窮舉法求解該問題是不可能的。近年來，受螞蟻、蜜蜂、鳥類、魚群等生物種群活動影響的優(yōu)化算法已經(jīng)非常常見，這類算法雖然不能保證求得問題的理論最優(yōu)解，但可以在理想的時間內(nèi)得到近似最優(yōu)解，利用這類算法求解TSP問題的近似解也已經(jīng)成為了一個重要的研究方向。

3 利用DYYPO算法求解TSP問題

3.1 YYPO算法在TSP問題中的推廣

一般情況下，利用優(yōu)化算法求解n個節(jié)點的TSP問題時，可行解可以認(rèn)為是由正整數(shù)1,2,…,n構(gòu)成的一個隨機(jī)排列的字符串。同時，由YYPO算法的分裂公式和存檔階段中開發(fā)半徑、探索半徑的更新公式可知，該算法主要用于求解連續(xù)型變量的問題，若將YYPO算法直接用于TSP問題的求解，可能會導(dǎo)致迭代過程中出現(xiàn)大量的非可行解。因此，現(xiàn)階段對YYPO算法的研究無法直接用于TSP問題的求解。

本文結(jié)合YYA算法中的交互算子，利用YYPO算法的思想，將YYPO算法中的分裂過程、存檔過程、求解過程中保持開發(fā)與探索之間的平衡關(guān)系和利用縮放因子控制開發(fā)半徑和探索半徑的方法應(yīng)用到了TSP問題的求解中，設(shè)計出了一種求解TSP問題的DYYPO算法。

3.1.1 參數(shù)初始化

3.1.2 分裂階段

(1)

圖1 DYYPO算法的分裂階段示意圖

3.1.3交互階段

交互階段的主要任務(wù)是根據(jù)開發(fā)半徑δ1或者探索半徑δ2的值，生成一個二進(jìn)制向量Bj，具體公式為

(2)

式中的r為0到1之間的隨機(jī)數(shù)。然后利用Bj分別以0.5的概率對一個可行解執(zhí)行下列兩種交互操作的一種：

(1)將可行解中與Bj中字符0對應(yīng)位置的節(jié)點放到新的可行解的前面，而將可行解中與Bj中字符1對應(yīng)位置的節(jié)點放到新的可行解的后面；

(2)將可行解中與Bj中字符1對應(yīng)位置的節(jié)點放到新的可行解的前面，而將可行解中與Bj中字符0對應(yīng)位置的節(jié)點放到新的可行解的后面。

與分裂階段相同，利用上述交互操作可以根據(jù)開發(fā)半徑δ1或者探索半徑δ2分別生成p個開發(fā)點和p個探索點。交互階段的操作如圖2所示。

圖2 DYYPO算法的交互階段示意圖

3.1.4 存檔階段

在存檔階段，首先利用縮放因子α更新開發(fā)半徑δ1和探索半徑δ2的值，其公式為

(3)

在分裂階段和交互階段，利用當(dāng)前種群一共生成了2p個開發(fā)點和2p個探索點，可計算出開發(fā)點的最優(yōu)值p1和探索點的最優(yōu)值p2，將其中的最優(yōu)值存儲到新的種群中。然后比較p1和p2的大小。如果p2

DYYPO算法描述:STEP1 初始化,生成規(guī)模為p的初始種群和α,δ1,δ2等參數(shù);STEP2 分裂階段,根據(jù)公式(1)計算翻轉(zhuǎn)字符串的長度,隨機(jī)生成翻轉(zhuǎn)字符串的起點,執(zhí)行翻轉(zhuǎn)操作,生成p個開發(fā)點和p個探索點;STEP3 交互階段,根據(jù)公式(2)生成二進(jìn)制向量Bj,執(zhí)行交互操作,生成p個開發(fā)點和p個探索點;STEP4 存檔階段,根據(jù)公式(3)生成新的δ1和δ2,計算開發(fā)點最優(yōu)值p1和探索點最優(yōu)值p2,比較二者大小,判斷是否將p1與p2、δ1與δ2的值交換,并將最優(yōu)值存儲到新種群中;STEP5 選取種群中適應(yīng)值最好的p個點,作為下次迭代的初始種群;STEP6 判斷是否達(dá)到最大迭代次數(shù)?若是,則轉(zhuǎn)STEP7;若否,轉(zhuǎn)STEP2;STEP7 將種群中的最優(yōu)值作為求解結(jié)果輸出,迭代結(jié)束。

在DYYPO算法的迭代過程中，初始種群的規(guī)模為p，分裂階段和交互階段分別產(chǎn)生了2p個新個體，加上最優(yōu)值會被存儲到新種群中，迭代產(chǎn)生的新種群規(guī)模為5p+1。在算法執(zhí)行過程中，開發(fā)半徑呈遞減趨勢，且每次迭代的最優(yōu)解始終保留在新的種群中，因此DYYPO算法具有收斂性。

3.2 DYYPO算法求解TSP問題的具體過程

在本文中，選取的TSP問題算例均來自于國際標(biāo)準(zhǔn)測試庫TSPLIB。首先選取TSPLIB中一個節(jié)點數(shù)為29個的算例Bays29，該算例的理論最優(yōu)解的值為2020，利用DYYPO算法求解該問的具體情況如表1所示(運(yùn)行環(huán)境：Intel core 2 Duo CPU 2.93Hz；2G RAM；MATLAB 2016b，下文同)。

從表1中的結(jié)果可知，在種群規(guī)模為200，迭代次數(shù)為600時，DYYPO算法運(yùn)行100次就能夠求得該問題的理論最優(yōu)解，且求解結(jié)果的平均值與理論最優(yōu)解較為接近，誤差平均值為1.93%。在迭代過程中，開發(fā)半徑δ1、探索半徑δ2的變化情況和種群最優(yōu)值的變化情況分別如圖3和圖4所示。

表1 DYYPO算法求解算例Bays29的結(jié)果

圖3 開發(fā)半徑與探索半徑的變化情況

圖4 種群最優(yōu)值的變化情況

由圖3可知，迭代次數(shù)在400次之前時，開發(fā)半徑δ1和探索半徑δ2的互換較為頻繁，這意味著在該階段探索點比開發(fā)點獲得了更優(yōu)的值，探索點的搜索在該階段占主導(dǎo)地位。隨后，開發(fā)半徑δ1和探索半徑δ2的互換逐漸減少，并分別收斂于0和1，且種群的最優(yōu)值也呈現(xiàn)出收斂趨勢，在經(jīng)過大約500次迭代后逐步趨于穩(wěn)定。同時，將圖3和圖4對比可知，無論開發(fā)半徑δ1和探索半徑δ2是否進(jìn)行互換，均有可能出現(xiàn)適應(yīng)值下降的現(xiàn)象，表明了開發(fā)點和探索點都能在一定程度上提高可行解的質(zhì)量。

3.3 DYYPO算法與其他算法的對比研究

為了進(jìn)一步測試DYYPO算法在求解TSP問題時的性能，選取了GA算法、EDA算法、YYA算法求解TSPLIB中的多個問題，并將求解結(jié)果與DYYPO算法的求解結(jié)果進(jìn)行對比。本文選取TSPLIB中的10個節(jié)點數(shù)較少的算例對上述算法進(jìn)行測試,為保證不同算法之間的可對比性，迭代過程中的種群規(guī)模p的值均取200，生成的新種群規(guī)模均為1001，循環(huán)次數(shù)均取1000次，所用到的算法主要流程如圖5所示。

圖5 本文用到的算法流程及種群規(guī)模示意圖

利用上述算法求解所選取的節(jié)點數(shù)在29至225之間的10個TSP問題算例，每個算例中的節(jié)點個數(shù)均體現(xiàn)在算例名稱中，每種算法均重復(fù)運(yùn)行100次，求解結(jié)果見表2。

表2 利用不同算法求解TSP問題的結(jié)果

從求解的平均值及其誤差方面來看，在所有選取的測試算例中，DYYPO算法求解結(jié)果的平均值均優(yōu)于其他算法，這說明DYYPO算法在求解TSP問題時通常能獲得相對較優(yōu)的解。在最優(yōu)值這一指標(biāo)上，DYYPO算法在Bays29算例中求得了理論最優(yōu)解；在Berlin52，Eil76和Ch130這三個算例中，DYYPO算法的結(jié)果要明顯優(yōu)于GA算法和YYA算法，但要稍劣于EDA算法；在其余6個算例中，DYYPO算法的求解結(jié)果均是最優(yōu)的。

在平均用時這一指標(biāo)上，DYYPO算法的用時比EDA算法和YYA算法要長，比GA算法要短。不同算法的用時隨著節(jié)點數(shù)量的變化情況如圖6所示，由圖6可知，隨著節(jié)點數(shù)量的增加，DYYPO算法用時的增長速度要明顯低于其他算法，這一項數(shù)據(jù)表明DYYPO算法在用時方面較為穩(wěn)定。將Bays29和Tsp225兩個問題的用時情況進(jìn)行對比，在節(jié)點數(shù)量增加了6.76倍的情況下，DYYPO算法的用時僅增長了1.14倍。相比之下，YYA算法的用時增長了1.78倍，比DYYPO算法略高，EDA算法和GA算法的用時均增加了8倍以上。因此，可以預(yù)測DYYPO算法在處理更大規(guī)模的TSP問題時會具有一定的時間優(yōu)勢。

圖6 不同算法的用時隨著節(jié)點數(shù)量的變化情況

4 結(jié)語

本文將求解連續(xù)型優(yōu)化問題的YYPO算法推廣到了TSP問題這一經(jīng)典的離散型優(yōu)化問題的求解中，利用YYPO算法中分裂操作和存檔操作的思想，并結(jié)合YYA算法中的交互算子，設(shè)計了一種包含分裂、交互、存檔等三個基本階段的新的優(yōu)化算法——DYYPO算法，并選取TSPLIB中的10個算例對算法性能進(jìn)行測試。測試結(jié)果表明，與其他三種算法相比，DYYPO算法在求解的平均值、最優(yōu)值和用時方面，均具有一定的優(yōu)勢。

需要說明的是，TSPLIB中算例的節(jié)點數(shù)量在十幾個到上萬個不等，本文選取的雖然是規(guī)模較小的算例，但DYYPO算法的求解時間已經(jīng)很長。以Tsp225問題為例，算法的平均時間是24.86秒，若運(yùn)行100次，總時間將超過40分鐘。因此，如何利用DYYPO算法在較短的時間內(nèi)求解更大規(guī)模的TSP問題，以及如何進(jìn)一步提高求解的效率，是一個重要的后續(xù)研究方向。