基于Prüfer數(shù)的離散粒子群優(yōu)化算法在TSP問題中的應(yīng)用

嚴坤妹

(福建商學(xué)院基礎(chǔ)部，福建 福州 350012)

基于Prüfer數(shù)的離散粒子群優(yōu)化算法在TSP問題中的應(yīng)用

嚴坤妹

(福建商學(xué)院基礎(chǔ)部，福建 福州 350012)

通過引入Prüfer數(shù)編碼、歸一化運算、粒子的位置矩陣進行模糊化等操作，將連續(xù)型粒子群優(yōu)化算法改造為離散化PSO. 并通過構(gòu)造旅行商問題的度約束最小生成樹，利用DCMST的模糊離散粒子群算法求出最優(yōu)解. 采用TSP的測試實例進行仿真實驗，證明算法的有效性與實用性.

旅行商問題;Prüfer數(shù)編碼; 粒子群優(yōu)化算法; 度約束最小生成樹

0 引言

旅行商問題(travellingsalesmanproblem,TSP)是組合最優(yōu)化的基本問題之一.TSP在生活實際中有十分重要的應(yīng)用背景，但TSP問題是NP-hard的. 已有很多算法求解TSP問題，如現(xiàn)代啟發(fā)式算法有TSP禁忌搜索算法、TSP模擬退火算法與TSP遺傳算法. 這三種算法的特點是可以跳出局部最優(yōu)，通過增加搜索的靈活性尋找更好的解. 蟻群算法屬于群集智能算法，已成功應(yīng)用到在解決旅行商問題等組合優(yōu)化問題中，但也有易于出現(xiàn)局部最優(yōu)、搜索時間長等缺點. 粒子群優(yōu)化算法(particleswarmoptimization,PSO)也是群集智能算法，一經(jīng)提出，就被廣泛用于對連續(xù)函數(shù)的優(yōu)化，很多學(xué)者對算法進行改進，使得粒子群優(yōu)化算法能運用到離散領(lǐng)域中. 其中, 文[1]對粒子群優(yōu)化算法及其在旅行商問題中的應(yīng)用進行研究； 文[2]對慣性權(quán)值進行研究，提出了相應(yīng)的粒子群優(yōu)化算法, 并用于求解旅行商問題； 文[3]也提出了一種改進的粒子群優(yōu)化算法用于求解旅行商問題, 該算法引入模糊矩陣.

為了解決度約束最小生成樹(degree-constrainedminimumspanningtree,DCMST)問題，文[4]提出了離散粒子群優(yōu)化算法，該算法中采用Prüfer數(shù)編碼，把一棵生成樹用Prüfer數(shù)表示，初始種群引入模糊矩陣產(chǎn)生. 本研究對旅行商問題和離散粒子群算法進行深入研究，提出一種基于Prüfer數(shù)的離散粒子群優(yōu)化算法用于求解TSP的策略，即通過構(gòu)造TSP的度約束最小生成樹(DCMST)，利用DCMST的模糊離散粒子群算法求出最優(yōu)解. 并用TSP進行仿真實驗，證明算法的有效性與實用性.

1 旅行商問題及s-t路旅行商問題的數(shù)學(xué)模型

1.1 旅行商問題的描述

旅行商問題是尋找n個城市的最短(閉)環(huán)游，使得在回到起點之前每個城市均被訪問且只訪問一次.TSP的圖論描述為: 設(shè)G=(V,E,W)是由n個城市構(gòu)成的賦權(quán)完全圖，其中每個城市用點vi表示，稱為頂點，V是頂點集，記為V=(v1,v2, …,vn)； 兩個城市間若有道路連接，則相應(yīng)的兩頂點之間有邊，用eij表示，E是邊的集合，記為E={eij,eij=(vi,vj),i,j=1, 2, …,n}；W={wij,wij=w(eij),i,j=1, 2, …,n}是城市與城市之間距離的集合，其中wij=w(eij)是城市vi與vj之間的距離(權(quán))，城市之間的距離也可用權(quán)矩陣W=(wij)n×n表示. 要求確定一條遍歷所有頂點一次且僅一次的最短回路, 即長度最短的哈密爾頓回路. 在TSP中，城市數(shù)目n和城市間的距離(權(quán))矩陣W=(wij)n×n是兩個重要的參數(shù)[5].

1.2 s-t路旅行商問題的數(shù)學(xué)模型

TSP還有更一般的形式，即所謂s-t路旅行商問題： 給定一系列的點以及它們兩兩之間的距離，同時給定一個起點s和終點t，需要尋找一條從s出發(fā)到t的最短路線 ，并且這條路線 恰好經(jīng)過每個頂點一次. 如果包含頂點s,t的回路是長度最短的哈密而頓回路，即遍歷所有頂點一次且僅一次的最短回路，則刪除邊(s,t)后得到的從s出發(fā)到t的路一定是s-t路，即恰好經(jīng)過每個頂點一次的最短路. 假設(shè)連接頂點s，t的邊是所有邊中最短的，且s-t路是從s出發(fā)到t，并且恰好經(jīng)過每個頂點一次的最短路，則把邊(s,t)加到s-t路中得到的回路也一定是最短的哈密而頓回路. 而實際上s-t路是一棵最小生成樹，其中頂點s,t的度數(shù)都為ds=dt=1，其余頂點的度數(shù)di=2(i≠s,i≠t). 因此，對給定的賦權(quán)圖G=(V，E，W)，設(shè)圖G的一棵生成樹表示為x=(x12x13x14…xij…xn-1, n)，其中xij∈{0, 1}，如果頂點i,j之間有邊相連且被選中，則xij=1，否則xij=0(i=1, 2, …,n-1;j=i+1, …,n).X為所有x=(x12x13x14…xij…xn-1, n)的集合，S是頂點集V的子集，則s-t路旅行商問題的數(shù)學(xué)模型[6]如下式所示：

2 求解s-t路旅行商問題(即DCMST問題)的離散粒子群算法的流程

文獻[4]中，粒子編碼采用Prüfer數(shù)，在求解s-t路旅行商問題的離散粒子群算法中，也是采用Prüfer數(shù)編碼機制，Prüfer數(shù)的編碼及解碼過程詳見文獻[7].

圖1 算法流程圖Fig.1 Algorithm flow chart

這里給出簡要的算法流程如圖1所示[8]. 求解s-t路旅行商問題的算法中，有關(guān)粒子的適應(yīng)度函數(shù)構(gòu)造、如何初始化粒子種群、粒子位置和速度的更新公式與求解DCMST問題的算法一樣，詳見文獻[4].s-t路是一棵特殊的度約束最小生成樹，其中頂點s,t的度數(shù)都為ds=dt=1，其余頂點的度數(shù)di=2(i≠s,i≠t). 在用最大數(shù)法對位置矩陣進行解模糊后得到的Prüfer數(shù)中會出現(xiàn)有的粒子不滿足度約束，因此需要對粒子進行頂點度數(shù)的檢驗. 由于頂點的度與頂點在Prüfer數(shù)中出現(xiàn)的次數(shù)有關(guān)： 若頂點在Prüfer數(shù)中有出現(xiàn)，則出現(xiàn)的次數(shù)再加上1就是該頂點的度； 若頂點沒有在Prüfer數(shù)中出現(xiàn)，則該頂點的度為1. 為此檢驗條件定為: 頂點在Prüfer數(shù)中出現(xiàn)的次數(shù)為1. 改進方法: 如果某一個頂點的度超過2，違反了度約束，那么將該頂點隨機替換為沒有在Prüfer數(shù)中出現(xiàn)的頂點. 如果粒子是可行的，則對Prüfer數(shù)進行解碼，可得到一棵滿足度約束的生成樹.

3 應(yīng)用求解DCMST問題的模糊離散PSO解決TSP的策略

根據(jù)Prüfer數(shù)編碼的特點，應(yīng)用求解DCMST問題的離散粒子群算法解決TSP，所采取的策略是： 1)先把TSP轉(zhuǎn)化成s-t路旅行商問題(即DCMST問題)，應(yīng)用DCMST的模糊離散粒子群優(yōu)化算法求解s-t路旅行商問題，得到最優(yōu)解； 2)再把邊est對應(yīng)的最小距離加入所求得的s-t路中，就得到TSP的最優(yōu)解.

具體做法：

第一步，對給定的實際TSP問題，把它轉(zhuǎn)化為賦權(quán)圖G=(V,E,W)，假設(shè)有n個頂點(城市)，分別用1至n的自然數(shù)表示頂點. 從圖G中找出(權(quán))距離最小的兩個頂點(城市)，不妨記s和t，并把s和t兩頂點的度限制設(shè)為1，其余頂點的度限制設(shè)為2，這樣，就把TSP問題轉(zhuǎn)化成s-t路旅行商問題了.

第二步，利用算法求出s-t路旅行商問題的最優(yōu)解，即用算法求得以s，t為葉子頂點的最小生成樹(線性樹).

第三步，在求得的以s，t為葉子頂點的度約束最小生成樹(線性樹)中，加入邊(s,t)得到的閉回路就是TSP的最優(yōu)解.

4 仿真實驗分析

4.1 實驗參數(shù)設(shè)置

為了說明基于Prüfer數(shù)的離散粒子群優(yōu)化算法用于求解TSP問題的有效性, 本研究與單親遺傳算法的實驗結(jié)果進行比較. 求解s-t路旅行商問題的算法參數(shù)設(shè)置如下： 學(xué)習(xí)因子C1和C2均為2，權(quán)重系數(shù)W=1，粒子群規(guī)模分別取M=20，30，40，50，60，迭代次數(shù)CS設(shè)為40，50, 60. 實例與文獻[9]中的一致, 已知給出了9個城市之間的距離構(gòu)成的權(quán)矩陣數(shù)據(jù).

實例假設(shè)圖G的權(quán)矩陣W如下所示，頂點數(shù)n=9，求TSP最優(yōu)解.

對于這個TSP問題，先用算法求解s-t路旅行商問題. 觀察權(quán)矩陣的數(shù)據(jù)，可知頂點1和頂點4之間的距離最短為w14=4，所以置頂點1和4的度限制為1. 其余頂點的度數(shù)為2，即度約束限制為: b=[1, 2, 2, 1, 2, 2, 2, 2, 2]，實驗結(jié)果見表1.

表1 實例的數(shù)值實驗

4.2 實驗結(jié)果比較

分析表1的具體數(shù)據(jù)，可看出當(dāng)?shù)螖?shù)CS為40，種群規(guī)模為40時，就得到了度約束限制為b=[1, 2, 2, 1, 2, 2, 2, 2, 2]的s-t路旅行商問題(最小生成樹)的最優(yōu)解為107，線性樹對應(yīng)的Prüfer數(shù)為[9 , 7 , 5 , 6 , 3 , 8 , 2]，s-t路由邊(9-1，7-4，5-7，6-5，3-6，8-3，2-8，2-9)構(gòu)成. 再將頂點1與頂點4的邊(1，4)加到樹中，就得到TSP的最優(yōu)回路長為111. 與文獻[9]提出的用單親遺傳算法對該實例求解得到的結(jié)果一樣. 說明應(yīng)用DCMST的模糊離散粒子群優(yōu)化算法可以解決TSP問題.

表2 本研究算法與相關(guān)算法的實驗對比情況

但文獻[9]的算法當(dāng)種群大小為100, 最大迭代次數(shù)等于100時, 才得到最短回路長是111. 而利用本研究算法當(dāng)種群大小為40，最大迭代次數(shù)為40時，就能得到最優(yōu)解111，而且收斂效果非常理想. 本研究算法與文獻[9-10]的算法的實驗結(jié)果比較見表2. 表2給出本研究算法跟文獻[9-10]的算法在種群大小、最大迭代次數(shù)、TSP回路長度的對比. 在文獻[10]的算法中未給出最大迭代次數(shù)，所以表中文獻[10]的最大迭代次數(shù)為空，同時文獻[10]會多次出現(xiàn)TSP回路長度為113，所以這里取平均值112.5. 從表 中可以看出本研究算法相對文獻[9]在種群大小和最大迭代次數(shù)方面均比較小，能以更少的迭代次數(shù)和種群規(guī)模獲得同樣的TSP回路最優(yōu)解. 而相對文獻[10]，本研究能以更小的種群規(guī)模，獲得相對更優(yōu)的TSP回路長度. 綜上，本研究算法相對文獻[9-10]均有一定程度的優(yōu)化，在求解TSP問題中更為有效.

5 結(jié)論

旅行商問題(TSP)是經(jīng)典的組合最優(yōu)化問題，至今未有十分有效的最優(yōu)算法. 本研究分析了s-t路旅行商問題與DCMST問題的關(guān)系，提出了應(yīng)用離散粒子群算法解決TSP的策略，通過把TSP轉(zhuǎn)化為s-t路旅行商問題，再利用求解度約束最小生成樹(DCMST)的模糊離散粒子群優(yōu)化算法解決TSP問題. 并用TSP實例進行仿真實驗，結(jié)果證明了算法的有效性.

[1] 陳震亦. 粒子群優(yōu)化算法研究及其在TSP問題中的應(yīng)用[D]. 福州: 福州大學(xué), 2004.

[2] 郭文忠, 陳國龍. 求解TSP問題的模糊自適應(yīng)粒子群算法[J]. 計算機科學(xué), 2006，33(6)： 161-162; 185.

[3] 龐巍，王康平，周春光，等. 模糊離散粒子群優(yōu)化算法求解旅行商問題[J]. 小型微型計算機系統(tǒng)，2005，26(8)： 1 331-1 334.

[4] 嚴坤妹，王鐫, 林娟，等. 求解DCMST問題的模糊離散粒子群優(yōu)化算法[J]. 莆田學(xué)院學(xué)報，2011，18(5): 59-63.

[5] 塔哈. 運籌學(xué)導(dǎo)論[M]. 9版. 劉德剛, 朱建明, 韓繼業(yè), 譯. 北京: 中國人民大學(xué)出版社，2014.

[6] GUO W Z, GAO H L, CHEN G L,etal． Particle swarm optimization for the degree-constrained mst problem in wsn topology control[C]// Proceedings of the Eighth International Conference on Machine Learning and Cybernetics. Baoding: IEEE, 2009: 1 793-1 798.

[7] ZHOU G, GEN M. Genetic algorithm approach on multi-criteria minimum spanning tree problem[J]． Euro Pean Journal of Operational Researeh，1999，114(1): 141-151.

[8] 紀(jì)震，廖惠連，吳青華. 粒子群算法及應(yīng)用[M]. 北京： 科學(xué)出版社, 2009.

[9] 宋海洲． 求解度約束最小生成樹的單親遺傳算法[J]． 系統(tǒng)工程理論與實踐，2005，25(4)： 61-66.

[10] 雷建平，沈成武，聞驥駿. 貨郎擔(dān)問題與單親遺傳算法[J]. 武漢理工大學(xué)學(xué)報，2003，25(6)： 80-83.

(責(zé)任編輯： 林曉)

A discrete particle swarm optimization algorithm based on Pr ü fer number for the application of the TSP problem

YANKunmei

(TheFoundationDepartment,FujianCommercialCollege,Fuzhou,Fujian350012,China)

ThePrüfernumbercodingmechanism,thenormalizedoperation,andthefuzzificationoftheparticle'spositionmatrixaredesignedfortransformthecontinuousPSOintodiscretePSOinthispaper.Thenthefuzzydiscreteparticleswarmoptimizationalgorithmofdegree-constrainedminimumspanningtree(DCMST)isdesignedtosolvethetravellingsalesmanproblem(TSP) .ThebenchmarkforTSPissimulatedandthesimulationresultsshowtheeffectivenessofthealgorithm.

travellingsalesmanproblem;Prüfernumbercoding;particleswarmoptimization;degreesconstraintsminimumspanningtree

10.7631/issn.1000-2243.2017.01.0147

1000-2243(2017)01-0147-04

2016-01-31

嚴坤妹 (1966-)，副教授，主要從事應(yīng)用數(shù)學(xué)教學(xué)、計算智能及其應(yīng)用方面研究，ykm6607@163.com

國家自然科學(xué)基金資助項目(11501114)

TP301.6

A