鄰域貪婪的Harris鷹優化求解立方體表面MTSP問題*

徐瀏凱 蘇守寶，3 何 超

（1.南京郵電大學計算機學院 南京 210023）（2.金陵科技學院數據科學與智慧軟件江蘇省重點實驗室 南京 211169）（3.江蘇科技大學計算機學院 鎮江 212003）

1 引言

旅行商問題（Traveling Salesman Problem，TSP）作為一個經典的路徑規劃問題，在工程領域和計算機科學領域中得到了廣泛的應用和研究。TSP問題定義為：假設有一個旅行商人要訪問n個城市，每個城市只能訪問一次，且最后要回到原來出發的城市。此問題的主要目的是使成本、時間和路徑等參數最小化。近年來，隨著對TSP的深入研究，三維空間中的TSP問題得到了廣泛的研究與關注。例如：航空公司飛行路線規劃［1］、卡車路徑規劃［2］、計算機網絡通信路徑規劃［3］等。因此，針對現實中的規劃問題提出有效的TSP解決方法顯得愈發重要。針對此需求，國內外相關研究人員提出了許多解決方案，這些方案大致可分為精確方法和啟發式方法兩類。精確方法主要包括迭代改進、分支定界和分支切割等方法TSP［4～5］，而啟發式技術主要是基于模擬退火，禁忌搜索等［6～8］方法來解決。為了獲得更好優化效果，研究者們提出了一些混合進化算法［9～10］。此外，文獻［11］還使用硬件方面的GPU并行計算技術來提升群智能算法在該類問題上的求解速度。

文獻［12～14］提出了一種3D幾何形狀（如球體和長方體）上的TSP問題。與經典TSP不同，此類TSP問題中所有坐標點都位于一個球體或長方體上，并且點之間的路徑需要在球體或長方體表面上進行計算。目前針對此類問題，研究人員們使用了粒子群算法（Particle Swarm Optimization，PSO）等群智能算法［12～14］進行了有效的研究。而本文的主要研究是采用一種較新的群智能算法Harris鷹群優化算法對立方體上的多旅行商問題進行求解。

Harris鷹群優化算法［15］（Harris Hawks Optimization，HHO）是受到了Harris地區的獵鷹圍捕獵物（兔子）和獵物相應的逃跑行為的啟發而產生的一種新的群智能算法。該算法具有參數較少，易于實現等優點，已被應用于多種尋優問題求解。

多旅行商問題（Multiple Traveling Salesman Problem，MTSP）是經典旅行商問題的一種推廣。該問題在實際應用中往往考慮的影響因素較為復雜，且只考慮旅行商路徑總長度最小化可能會造成路徑的不均衡。針對以上問題，本文在前人研究基礎上將改進的Harris鷹群優化算法。在本研究中，首先會給出立方體表面上兩點的距離計算公式，然后針對立方體表面的MTSP的不同特點，將k-mean聚類，鄰域搜索算子和貪婪策略等改進方法與HHO結合提出了一種鄰域貪婪的Harris鷹優化算法（Neighborhood Greedy Harris Hawks Optimization，NGHHO），并在TSP benchmark測試集和隨機點集上分別進行了多次測試以驗證NGHHO的算法性能，最后與其他幾種群智能算法在最優路徑搜索性能上進行了比較。

2 問題與方法

2.1 立方體表面的MTSP問題

立方體是一種常見的幾何形狀，生活中諸多的物品如書籍、櫥柜、家具和建筑物等很多都是立方體。它們都具有六個面、十二個邊和八個角，如圖1所示。

圖1 立方體

立方體MTSP問題可以定義為：m位在能夠在立方體表面移動的旅行商要向該立方體表面的n個城市販賣自己的商品，如何選擇一條最優的路徑，使得m位旅行商從立方體上的m個城市出發，經過所有城市有且僅有一次，且其所有走過的路均在該立方體表面上，所有旅行商所旅行的總路程要求最短。在現實生活中，解決該類問題可用于室外爬墻機器人，大廈外的無人機路徑規劃、建筑物外壁的自動清潔機器人的路徑規劃等方面。舉例來說，當摩天大樓發生火災且無法觸及樓層和房間時，為了運送救援物資爬墻機器人便會在建筑物表面上方移動，此時爬墻機器人就需要一條較好的路徑規劃，以更快地趕到需要救援的地點。

2.2 立方體表面的任意兩點最短距離

立方體表面的任意兩點的距離計算與普通的平面上的計算存在一定的區別。距離計算需要考慮三種情況，即兩點處于同一平面上，兩點處于對立面上，兩點處于相鄰面上。三種情況的距離計算公式如下：

假如兩點處于相同面上，此時，距離計算等價于平面情況的計算。點i到點j的距離方程為

假如兩點處于對立面上，此時需要考慮四種情況，點i可能從周圍的四個面中的任意一個面經過到達點j，所以計算時需要將四種方式得到的距離都計算出來，最后將四個距離進行比較，其中的最小值是兩點間的最短距離。以下面-前面-上面這種情況如圖2（a）所示，其公式如下：

假如兩點在相鄰面上，此時需要考慮三種情況，點i到點j可能的路徑如圖2（b）所示。假設點i在前面，點j在上面，那么就存在前面-上面、前面-左面-上面、前面-右面-上面三種路徑。此時，也需要將三種情況的距離求出，然后取三個距離的最小值作為兩點間真正的最短距離。

圖2 最短距離

1）前面-上面情況的計算公式

2）前面-左面-上面情況的計算公式

3）前面-右面-上面情況的計算公式

2.3 HHO算法

HHO算法受到鷹捕食行為以及兔子（即獵物）的逃跑行為的啟發，構建了鷹基于不同策略捕獵兔子的數學模型，使鷹群在棲息和捕獵過程中逐漸接近獵物，即最優解。該算法具有易于實現，參數較少等優點。算法中的種群迭代部分由三部分組成：探索階段，從探索到開發的過渡階段，開發階段。

1）探索階段

該階段中，HHO算法模擬了鷹的棲息行為。從搜索角度來看，該階段主要進行全局探索，由兩種不同的策略組成，即基于鷹群中某一只鷹的位置進行棲息的策略和基于在搜索范圍內隨機位置的進行棲息的策略。兩種策略的具體數學形式為

式中，Xi(t+1)和Xi(t)分別為第t+1代和t代種群中的第i個體的位置，Xrabbit是第t代為止所獲得的全局最優位置，即目前的全局最優解，Xrand是第t代種群中隨機選取獲得的個體位置，Xm是當前種群所有個體的平均位置，q和randi（i=1，2，3，4）均是服從在（0，1）區間上的均勻分布的隨機數，lb和ub分別是搜索空間的下界和上界。

2）從探索到開發的過渡階段

HHO算法中，每代種群中的每一個個體都會依據獵物的逃逸能量E選擇進入探索階段或者開發階段。逃逸能量E的公式如下所示：

式中，E0表示獵物初始的逃逸能量，是服從在（-1，1）區間上的均勻分布的隨機數，t是當前迭代次數，T是最大迭代次數。

3）開發階段

該階段中，HHO算法模擬了鷹群的圍捕行為，建模成四種不同的搜索策略，分別為軟圍攻，硬圍攻，具有漸進式俯沖的軟圍攻以及具有漸進式俯沖的硬圍攻。代種群中的每一個個體都會依據獵物的逃逸能量E以及服從在區間（0，1）上的均勻分布的隨機數r的取值選擇執行相應的捕食策略更新種群。上述搜索策略具體的數學表達形式為

（1）軟圍攻策略：當r≥0.5，||E≥0.5時，因為獵物的逃逸能量較高，具有足夠的體力進行逃跑，所以鷹群選擇包圍獵物。該策略的數學公式如下：

式中，Jump是獵物的隨機跳躍強度，表達式為Jump=2×(1-rand5)，rand5是服從在區間（0，1）上的均勻分布的隨機數。

（2）硬圍攻策略：當r≥0.5，||E＜0.5時，因為獵物的逃逸能量較低，所以鷹群使用較為強硬的包圍策略。該策略的數學公式如下：

（3）具有漸進式俯沖的軟圍攻策略：當r＜0.5，||E≥0.5時，雖然獵物仍然有體力逃跑，但鷹群采取軟圍攻與嘗試性的俯沖捕殺相結合的方式進行捕獵。該策略的數學公式如下：

式中，F是最小化問題的適應度函數值，S是一個大小為1×D，其中元素為服從在區間（0，1）上的均勻分布的隨機數的向量，D為該最小化問題的維度，LF是大小為1×D，其中元素為服從levy分布的隨機數的向量。levy分布的一維計算公式如下：

式中，μ和ν都是服從在區間（0，1）上的均勻分布的隨機數，β一般取值為1.5。

4）具有漸進式俯沖的硬圍攻策略：當r＜0.5，||E＜0.5時，獵物沒有足夠的體力逃跑，所以鷹群采取硬圍攻與嘗試性的俯沖捕殺相結合的方式進行捕獵。該策略的數學公式如下：

3 改進HHO算法

針對離散問題的求解需求，本文提出了一種新穎的改進HHO算法（Neighborhood Greedy Harris Hawks Optimization，NGHHO）。該算法主要是采用了隨機實數編碼方式、k-mean聚類方法、鄰域搜索算子以及貪婪策略等方法以適應對于MTSP這類離散型問題的求解。

3.1 隨機編碼方式

隨機編碼是一種將離散空間中的一個組合轉換成連續空間中的一組解的方法。該編碼將一個實數分為兩個部分，即整數部分和小數部分。整數部分的意義是旅行商的序號，小數部分表示了路徑順序。

小數部分的表示細節如下：對于MTSP問題來說，首先每個城市對應于一個實數，就產生了一個實數向量；然后根據該向量的小數部分進行升序排序，可以得到一個路徑順序，如圖3所示，城市1到5分別對應著0.8到0.4，將其升序排列，就得到了每個城市所在的位置，即5-3-4-1-2，轉化為路徑就是4-5-2-3-1。

圖3 隨機編碼

因為TSP問題中的路徑信息是離散的一串數組，原始的HHO算法是一種在連續空間上求解的優化算法，所以本文采用該方法將TSP問題中的路徑信息轉化為一組實數解，再帶入到HHO算法中進行求解。

3.2 k-mean聚類

在MTSP中，k-mean算法可以用于將城市群分配給K個旅行商，其主要思想是首先在城市坐標點集合中選取K個點，即聚類中心，然后計算每個點到所有聚類中心的歐式距離，將每個點分配給歐氏距離最近的那個聚類中心，得到一個個簇，最后通過不斷迭代更新簇得到聚類結果。該方法產生的初始解質量較高。

3.3 鄰域搜索算子

為了避免算法的過早收斂，本文采用了三種基礎的鄰域搜索算子［16］來提升算法鵝性能。這三種基礎的鄰域搜索算子分別是隨機交換算子、隨機插入算子和隨機反轉算子。

1）隨機交換算子：在一次旅行中隨機選擇兩座城市，然后交換兩個選定城市的訪問順序。使用該算子的優點之一是使得每個城市之間有更多彼此相鄰的可能性，對路徑產生一定的干擾和變化。如圖4（a）所示，隨機交換算子使得城市2與城市5的位置被交換了。

2）隨機插入算子：該算子隨機選擇兩個城市，然后它將第i個城市提到第j個城市的后面進行訪問。該算子相較于隨機交換算子對路徑的改變更小。如圖4（b）所示，隨機交換算子使得城市2插入到了城市3的位置。

3）隨機反轉算子：該算子隨機選擇一連串城市。然后它將第i個城市到第j個城市的順序顛倒過來（即在路徑組合中隨機選擇兩個點，然后反轉位于兩個選定點之間的城市的順序）。如圖4（c）所示，隨機交換算子使得城市1和城市5之間所有城市的位置發生了翻轉。

本文中在鷹群在開發階段和每次迭代的解集更新階段后加入了鄰域搜索算子。在開發階段，為了增強HHO算法的局部搜索能力，所以結合鷹群圍捕思想使用隨機交換算子和隨機翻轉算子重新定義了軟圍攻和硬圍攻策略。具體方法如下：按照原始HHO中，根據當前最優解的位置更新鷹的位置的圍攻思想，將對當前迭代的最優解使用隨機交換算子和隨機翻轉算子進行當前解的更新，定義為新的軟圍攻和硬圍攻，其可以記為如式（18）和（19）。同時，傳統的HHO容易陷入局部最優，為了增加種群的多樣性，在每次迭代解集更新階段后，所有使用上述三種鄰域搜索算子對解進行一次變異。該變異具體方法如下：每只鷹按照等概率的可能會選擇三種算子或者保持不變共四種策略進行一次變異移動。上述方法可以記為式（20）。

3.4 貪婪策略

采用三種鄰域搜索算子以及HHO算法對問題進行求解的時候，由于缺乏問題本身的信息指導，其更新策略是偏向于隨機的，解的迭代更新中容易產生冗余路徑。為了使得HHO算法的搜索過程能夠更加高效，使搜索結果能夠不斷趨近最優解。本文將HHO算法和貪心選擇相結合，通過在HHO算法的俯沖階段中采用貪婪策略［17］，使得算法的能力得到改善。由于TSP問題優化目標是距離因素，所以本文采用的貪婪策略基于距離因素，在HHO俯沖階段，將原本的模擬俯沖定義為在路徑組合中隨機選擇某一個城市后插入一個距離該城市最近的城市，產生一個新解，其可以表示為如下公式。

3.5 算法描述

本文所提出的NGHHO算法的偽代碼和流程如算法1和圖5所示。

圖5 NGHHO算法流程圖

4 實驗結果與分析

實驗使用Matlab R2018b編寫了改進HHO算法。實驗中將NGHHO與一些群體智能算法進行比較，對比算法包括粒子群算法（PSO）［13］，Harris鷹群優化算法（HHO）［15］以及灰狼優化算法（GWO）［18］。所有算法的搜索個體數1.5倍的城市數量，運行次數為30次，迭代最大代數為2000代。實驗中的所有算法的參數設置如下：粒子群算法的局部學習因子為2，全局學習因子為2。本文進行了兩種實驗。

第一種實驗是采用了solomon測試集中c101問題（http：//w.cba.neu.edu/～msolomon/problems.htm）為實驗數據在長、寬、高分別為100、50、100的立方體表面上進行了實驗。考慮不同問題規模，又分為30次100迭代30個點的2旅行商MTSP問題和30次2000次迭代100個點的4旅行商的MTSP問題，第一個30個點的實驗結果如圖6（a）和圖7（a）所示，第二個100個點的實驗結果如圖6（b）和圖7（b）所示。從圖6（a）和6（b）示出NGHHO找到的最優路徑，可見在不同規模下的MTSP問題中，NGHHO基本上可以找到一個可行解，而圖7（a）和7（b）顯示了各算法的平均收斂曲線，可見與HHO，GWO和PSO相比，其找到的解更優。通過以上分析可得，NGHHO在尋優精度以及跳出局部最優的能力上都比原始HHO，PSO和GWO強。

圖6 測試集上NGHHO獲得的最短路徑

第二種實驗是在20、30、40的立方體上，隨機生成100個坐標（即這些坐標與第一種實驗不同可以分布在立方體的任意面上）進行的實驗。其同樣進行兩種規模的實驗，30個點實驗結果如圖8（a），8（b）和7（c）所示，100個點的實驗結果則顯示于圖8（c），8（d）和7（d）。從圖8同樣可以展示出在不同規模中NGHHO找到的最優路徑，NGHHO基本上具有搜索到可行解的能力，從圖7（c）和7（d）中可以看出算法隨著迭代次數的增長所求得的總路徑長度雖然下降增速有所減少但是仍然是不斷降低的，同時也顯示NGHHO與其他群智能算法相比，所求得總路程一直是較優的。通過上述分析NGHHO具有一定的優越性。

圖7 實驗結果

圖8 隨機點集上NGHHO獲得的最短路徑

5 結語

本文討論了立方體表面上的MTSP問題上兩點間的距離計算方法，并針對該問題的特征，使用k-mean聚類，鄰域搜索和貪婪策略改進了Harris鷹優化算法，并利用改進后的算法有效地求解了該問題，得到了一種較為簡單且有效的在任意立方體表面上的MTSP問題的求解方法。該方法適用于在任意大小的立方體上的路徑規劃問題，可以考慮應用于室內爬墻機器人的路徑規劃或者大廈外側清潔路徑規劃等特殊幾何表面的路徑優化問題，具有一定的使用價值。