改進凸包插值算法結合大概率優化的演化算法

崔東，于湛麟

（渤海大學遼寧錦州121000）

改進凸包插值算法結合大概率優化的演化算法

崔東，于湛麟

（渤海大學遼寧錦州121000）

近似算法在解決超大規模旅行商問題時無法獲得高精度優化解（或者次優解），智能算法雖然可以獲得精度高于近似算法的解，很難在合理時間內獲得。采用改良的凸包近似算法構成初始解并結合大概率優化策略的遺傳算法來解決超大規模旅行商問題，通過對rl11849（962313），brd14051（489721），和pla33810（70757880）等實例實驗都在理想的時間內獲得優化解。證明這種混合算法在解決超大規模TSP問題時具有優勢。

智能算法；近似算法；超大旅行商問題；混合算法

TSP問題（即旅行商問題）是典型的組合優化問題[1]。問題描述為：一名商人要到幾個城市推銷貨物，從任意城市出發經過各城市一次且僅一次，然后回到出發點。由于該問題的描述簡單[2]，而其實際規模在路徑，網絡，分配，調度和集成電路設計等優化問題中又有著廣泛的應用[3]。其中精確算法在求解過程中，時間復雜度約等于O(n22n)。因為本文針對解決的是超大規模TSP問題，所以此類方法不做考慮。退而求其次，一些學者在近幾年分別根據數學優化和人工智能（Artificial Intelligence）理論提出了兩種TSP求解方法，即：近似算法[4]和智能算法[5]。

近似算法在求解TSP方面，以凸包算法為代表[6]，時間復雜度一般小于或者等于O（n4）。并且在小規模TSP實例中，該算法一般都具有良好的性價比。但是，在求解超大規模TSP方面，這些近似算法的精度有明顯的下降趨勢。并且，這些近似算法一般只能給出一個近似解。在智能算法求解TSP方面，有進化算法[7-9]和混合算法[10]。這些智能算法一般都具有全局搜索、并行處理和強魯棒性等優點[11]。并且，在中等規模TSP實例測試中，這些智能算法的精度一般要高于上面提到的近似算法。但是，隨著實例規模的增加，特別是對超大規模TSP來說，在算法后期尋優速度以及收斂速度都有明顯的下降[12-13]，從而影響了TSP尋優的質量。這可能是由于在算法后期，隨著優化解密度的急劇下降，隱含的尋優策略開始逐漸失效，從而產生大量的無價值的迭代運算影響算法的效率。

文中通過采用改進的凸包算法結合大概率優化策略的遺傳算法，首先通過使用改進的凸包算法產生的一個不壞的初始解，解決智能算法對初始解較敏感的問題，可以為后面的迭代節省的大量的時間，然后采用基于大概率思想的遺傳算法，對這個初始解進行深度優化，以期在理想的時間內找到一個較好的解。

1 改進的凸包算法

1.1 基本原理

點集H的凸包是指存在一個最小的凸多邊形，其中點集H的點或是在這個凸多邊形上或是在這個凸多邊形的內部[14]。在解決TSP問題時由于問題需要將內部點插入到凸包上形成回路初始解的方法有很多，由于演化算法對初始解比較敏感的特性，如果能對初始解的精度提高一些，可以為后面的演化算法節省大量的時間，本文針對提高算法精度的問題找到了更好的解決方法。

首先找到該點集的第一層凸包，使用凸包算法找到這些點后，將第一層凸包點順序保存并從點集中將第一層凸包點刪除。然后繼續使用快速凸包尋找第二層凸包點集，算法結束后將第二層凸包點順序保存并從點集中將第二層凸包點刪除。如此操作直到點的個數小于4算法停止。由于旅行商問題的特性需要將這些層凸包形成回路，將最外層凸包的下一層凸包的點按照最小增量的方法依次插入到最外層凸包當中，直到所有點形成回路算法結束。

1.2 算法框架

算法1：構成回路的算法

輸入：點集H

輸出：各層凸包T0，T1…Ti-1，Ti

While（H＜4）//i=0。點集H為當前城市點的集合，當點集H中的點個數小于4時算法停止

{Ti=Convex（H）；//Tubao（）是求取當前點集H的凸包Ti的算法

H=H-Ti；//將已經找到的該層凸包Ti按順序保存并從點集H中刪除

i++；}

輸入：各層凸包T0，T1…Ti-1，Ti

輸出：哈密爾頓回路T0

while（j＞i）//j=1；

{將Tj層凸包的所有點按照最小增量的方法插入到T0層凸包當中，將兩層凸包形成一條新的回路；j++；}

算法2：Convex（）//改進的凸包的快速算法

步驟1：Initial（H）//初始點選擇函數。

首先找到一個或多個y值最小的點。如果有多個這樣的點，再比較其x值，將這些點中x值最小的點作為該層凸包的初始點。

步驟 2：Center（H，O[2]）//點集的中心點求取函數。

設點集H共有n個點，a為n個點x值的總和，b為n個點y值的總和。O[0]=a/n，O[1]=b/n。

設點O的x值為O[0]，y值為O[1]，點O為該點集的中心點。

步驟 3：Authentication（）//尋找初始點下一個該層凸包點的函數。

點p為初始點，點O為中心點，設點q為待驗證該層凸包的下一個點，設點集K為除初始點和待驗證點以外所有點的集合。

while（j＜n-1）

{while（i＜n-2）//n當前點集的總個數，i=0

{A=Intersection（p，q，Ki，O）//A點為初始點和待驗證點與中心點和Ki點的交點

if（distance{O，A}+diatance{A，Ki}==distance{O，Ki}）{break；}//若存在 Ki點在 p 點和 q 點連線的外部，則該q點不是這層凸包的下一個點。

else{i++；}}//若該q點通過點Mi的測試則繼續測試點Mi+1，直到測試所有n-2個點停止。

if（i!=n-3）{q=q-＞next；}//若該q點沒有通過點集K中所有點的驗證則尋找下一個待驗證點q。

else{break；}}//若該q點通過所有K點集中所有點的驗證，則該q點為該層凸包的下一個點。將q點作為該層凸包的下一個初始點p重復執行步驟3，直到找到的q點為第一個初始點算法結束。

2 大概率思想的演化算法

2.1 基本思想

在解決旅行商問題時，精度與時間往往是評價算法優劣的重要標準。而在利用演化算法解決超大旅行商問題時，對局部優化的時間和精度往往不好掌握，結果會導致大量的冗余結算占用大量的時間最終導致無法在規定時間內獲得較好的解。本文針對這個問題采用大概率思想的演化算法，首先通過對已經給出優化解的小型TSP實例進行統計以期選擇最佳的優化局部半徑，對其優化可以最大概率的得到較好的優化解，其次優先對局部范圍內找到優化解的周圍尋找更好的結果，直到優化解不在滿足設定的閾值停止算法并找新的局部范圍進行優化。這樣即提高了局部的優化效果，又能對下次可以獲得較好優化效果的標準點做出選擇，可以使每次的優化都是大概率事件。

證明:設實例V={v1,v2…vn}，平均距離。如果存在A?V，B?C，A?B=V，并且，那么稱r為近鄰系數。

假設存在一個函數f(r)，并且誤差，即：函數f(r)→。那么，稱f(r)為近鄰系數r的概率密度函數，為近鄰系數r的概率分布函數。

文中通過對上述TSP實例庫1002個點以內部分已經給出優化解的實例進行統計，具體統計方式為:

首先計算出已經給出優化解的實例n中點a1與其下一個a2的路徑長度，然后計算點a1與其余n-2個點的路徑長度，將a1到a2的路徑與這些路徑進行排序，對該實例中所有點都統計后設ai到aj路徑與ai到其余n-2個點排序最大為k。通過統計發現，隨著實例點的增加k值也會有相對的增加，其中pr1002實例的k值達到24，也就是說只有隨著實例點的增加擴大優化局域半徑才能夠確保其可能搜索到該實例中最好的優化結果。

通過這種統計方式來對局部進行優化的優勢是明顯的：可以保證標準點的最可能獲得優化解下一個點在這個局域內，這樣優化的時候也就可能獲得該局部內最好的解，從整體來看，若一個區域得到優化對其周邊區域進行優化同樣也是大概率事件。然而這個優化大概率事件隨著深度的增加所產生的問題也是明顯的:隨著其運算次數的增加，其精度難以保障而出現下溢。針對上述問題本文給出的解決方法是：根據不同的實例設定相應的閾值，當優化速度達到閾值的時候停止，尋找新的范圍進行優化。

2.2 算法框架

輸入：初始種群T

輸出：優化后的種群T0（若沒有得到優化保留初始種群T）

while（i＜n）//i=0；n為迭代次數

{T1=Code（T，a，n）；//T 為初始解，以a點為中心，對距離其最近的n個點進行編碼

//1萬點的實例到2萬點的實例k值取30，3萬點的實例到4萬點的實例k值取40，4萬點以上的實例k值取50

T2=optimization（T1）；

if（f（T1）＜f（T2））//f（）為適應度函數

{T0=Decode（T2）；

While（j＜m）{T3=Code（T，am，n）//am 是指以a點為中心距離最近的第m個點

T4=Optimization（T3）；if（f（T3）-f（T4）＞M）{T0=Decode（T4）；}//M為閾值；若T3局部解得到優化則對T4進行解碼將結果對種群T0覆蓋

else{break；}//若優化值小于閾值停止該層優化

j++；}}else{若T1沒有得到優化重新選擇標準點進行優化}i++；}

2.3 編碼/解碼函數

文中采用的是局部優化策略，求解TSP問題的編碼/解碼方法有很多，本文采用的路徑表示法。

編碼（Code（））

輸入：T初始種群；標準點a；距離a最近的k個點

輸出：優化后種群T1

以a點為標準點，從初始種群T中選出距離其最近的k個點，按照T中的順序排列生成其子代T1，并對其余的沒有參與編碼的路徑進行保存。

解碼（Decode（））

輸入：參與優化后的子代T1，編碼中保留的有向路徑

輸出:參與優化后的種群T0

將編碼操作中保留的有向路徑按照最小增量方式插入到子代T1中形成新的種群T0

2.4 適應度函數

適應度函數用來評價新生個體的優劣程度，文中采用的適應度函數為路徑行徑長度的倒數來表示個體的優劣程度。根據適應度的大小來對子代個體選擇是否保留，保證使更符合標準的子代個體有更多的存活機會。

2.5 優化函數

超大旅行商問題與小規模旅行商問題相比城市點較多，分布較密集，導致其在優化的初期較容易而且優化速度較快，只需要調整較少的邊數就可以獲得更優解，本文在算法初期和中期優化的方法是:通過調整4個城市點的排列方式來獲得更優解，隨著算法運行時間的增加需要對局部解進行增加優化的次數。調整方法如下:

優化函數（Optimization（））

輸入：初始種群T，局部解T1

輸出：若局部解得到優化則輸出優化解T0，否則保留初始種群T

T1=Code（T，a，k） //T1為T的局部解

While（N＜4）{cityN=Random（T1）；N++}//從局部解T1中隨機選擇4個城市點位 b0，b1，b2，b3

對這4個城市點排列組合共有23種排列方式（除初始狀態以外）最少需要調整兩個城市點的位置，最多需要3個城市點位置。若調整兩個城市點位或者3個城市點位后T1得到優化，則保留當前調整后的結果，否則將其還原成調整前的狀態。

T2=exchange（city1，city2）//交換兩個城市點的位

if（f（T1）＜f（T2））{T0=Decode（T2）；}//若T1得到優化，對T2局部解進行解碼得優化種群T0

else{exchange（city1，city2）}//若 T1 沒有得到優化，將兩個城市點還原

3 實 驗

為檢驗文中的算法性能，通過3次實驗求解標準問題庫TSPLIB中一萬點以上的部分實例（實驗環境：CPU為因特爾3.10GHz，內存為4.00GB，操作系統為win7，編程語言為c語言，編程工具為Microsoft Visual C++。）實驗結果如下方表圖所示。從實驗結果來看，其中pla33810（70757880.60），brd14051（489721.70）和實例 rl11849（962313.90）所獲得的 3次實驗結果均好于文獻[2]的實驗結果。

表1 TSPLIB中超大規模實例的實驗結果

圖1 rl11849的實驗1優化路徑（962313.9）

圖2 brd14051的實驗1優化路徑（489721.7）

圖3 pla33810的實驗1優化路徑（70757880.6）

4 結束語

演化算法發展至今已經經歷了40多年，無數的學者投身其中。隨著計算機技術的發展，演化算法又步入了新的階段。目前針對旅行商問題這一演化算法試金石的解決，只有當問題規模較小時，可以在合理的時間內獲得高精度的解，在解決超大規模旅行商問題時，還是有許多不足，無論是近似算法或者智能算法都遇到了不同的困難。雖然本文可以對一些超大旅行商實例在合理的時間內給出較好的解，但是這也是針對文獻[2]的結果相比較而言的。之所以可以獲得較好的結果是因為在初始值的產生方法和選擇標準點優化策略的方法上較前人而言較新穎，可以很大概率上尋得較好的解，提高了算法的效率。在未來針對解決超大旅行商問題的混合算法將是研究的熱點和重點。

[1]許文超.混雜運行條件下客運專線動車組運用優化研究[D].北京：北京交通大學，2013.

[2]趙連朋，金喜子，王娜，等.求解超大規模旅行商問題的縱深遺傳算法[J].計算機工程與應用，2009，45（4）：56-58.

[3]Osaba E，Carballedo R，Diaz F，et al.On the influence ofusing initialization functions on genetic algorithms solving combinatorial optimization problems:A first study on the TSP[C]//2014 IEEE Conference on Evolving and Adaptive Intelligent Systems（EAIS），2014.

[4]趙海森，楊承磊，呂琳.多邊形中的點可見性快速算法[J].計算機輔助設計與圖形學報，2013，25（3）：331-340.

[5]張貴軍，何洋軍，郭海峰，等.基于廣義凸下界估計的多模態差分進化算法[J].軟件學報，2013，24（6）：1177-1195.

[6]楊玉婷，康厚良.2D圖形引擎中的平面多邊形內外點判別[J].圖學學報，2013，34（3）：100-102，105.

[7]張宇翔，黃力宇.Hopfield網絡求解TSP兩種改進算法的仿真研究[J].電子設計工程，2009（10）：119.

[8]程畢云，魯海燕，徐向平，等.求解旅行商問題的改進局部搜索混沌離散粒子群優化算法[J].計算機應用，2016（1）：138-142.

[9]王寶生，屈寶存.蟻群算法在求解TSP問題中的改進研究[J].電子設計工程，2014（22）：14-18.

[10]姚明海，王娜，趙連朋.改進的模擬退火和遺傳算法求解TSP問題[J].計算機工程與應用，2013，48（14）：60-65.

[11]Yu Yingying，CHEN Yan，LI Taoying.A New Design of Ge-netic Algorithm for Solving TSP[C]//2011FourthInternational Joint Conference on Computational Sciences and Optimization，2011.

[12]李煜，馬良.用量子蟻群算法求解大規模TSP問題 [J].上海理工大學學報，2012，34（3）：355-358.

[13]盛虹平，馬良.求解大規模旅行商問題的改進大洪水算法[J].小型微型計算機系統，2012，33（2）：259-262.

[14]范美玲.面向場景的TD-LTE無線參數優化配置系統設計與實現[D].北京：北京郵電大學，2014.

Improved convex hull algorithm combined with probability optimization evolutionary algorithm

CUI Dong，YU Zhan?lin
（Bohai University，Jinzhou121000，China）

The approximate algorithm can not obtain the high accuracy optimization solution（or sub optimal solution）when solving the problem of super large scale traveling salesman problem.Although the intelligent algorithm can obtain the solution of the algorithm with higher accuracy than the approximate algorithm，it is difficult to obtain the.By using the improved convex hull approximation algorithm and genetic algorithm are combined to constitute the initial solution of the probability optimization strategy to solve large scale traveling salesman problem，based on the rl11849（962313），brd14051（489721），and pla33810（70757880）and other examples of experiments in the ideal time to obtain optimal solution.It is proved that the hybrid algorithm has the advantage of solving the problem of super large scale TSP.

intelligent algorithm；approximation algorithm；large traveling salesman problem；hybrid algorithm

TN609

A

1674-6236（2017）22-0026-05

2016-09-24稿件編號：201609220

崔東（1992—），男，遼寧沈陽人，碩士研究生。研究方向:規劃識別。