基于Prüfer数的离散粒子群优化算法在TSP问题中的应用

严坤妹

(福建商学院基础部，福建 福州 350012)

基于Prüfer数的离散粒子群优化算法在TSP问题中的应用

严坤妹

(福建商学院基础部，福建 福州 350012)

通过引入Prüfer数编码、归一化运算、粒子的位置矩阵进行模糊化等操作，将连续型粒子群优化算法改造为离散化PSO. 并通过构造旅行商问题的度约束最小生成树，利用DCMST的模糊离散粒子群算法求出最优解. 采用TSP的测试实例进行仿真实验，证明算法的有效性与实用性.

旅行商问题;Prüfer数编码; 粒子群优化算法; 度约束最小生成树

0 引言

旅行商问题(travellingsalesmanproblem,TSP)是组合最优化的基本问题之一.TSP在生活实际中有十分重要的应用背景，但TSP问题是NP-hard的. 已有很多算法求解TSP问题，如现代启发式算法有TSP禁忌搜索算法、TSP模拟退火算法与TSP遗传算法. 这三种算法的特点是可以跳出局部最优，通过增加搜索的灵活性寻找更好的解. 蚁群算法属于群集智能算法，已成功应用到在解决旅行商问题等组合优化问题中，但也有易于出现局部最优、搜索时间长等缺点. 粒子群优化算法(particleswarmoptimization,PSO)也是群集智能算法，一经提出，就被广泛用于对连续函数的优化，很多学者对算法进行改进，使得粒子群优化算法能运用到离散领域中. 其中, 文[1]对粒子群优化算法及其在旅行商问题中的应用进行研究； 文[2]对惯性权值进行研究，提出了相应的粒子群优化算法, 并用于求解旅行商问题； 文[3]也提出了一种改进的粒子群优化算法用于求解旅行商问题, 该算法引入模糊矩阵.

为了解决度约束最小生成树(degree-constrainedminimumspanningtree,DCMST)问题，文[4]提出了离散粒子群优化算法，该算法中采用Prüfer数编码，把一棵生成树用Prüfer数表示，初始种群引入模糊矩阵产生. 本研究对旅行商问题和离散粒子群算法进行深入研究，提出一种基于Prüfer数的离散粒子群优化算法用于求解TSP的策略，即通过构造TSP的度约束最小生成树(DCMST)，利用DCMST的模糊离散粒子群算法求出最优解. 并用TSP进行仿真实验，证明算法的有效性与实用性.

1 旅行商问题及s-t路旅行商问题的数学模型

1.1 旅行商问题的描述

旅行商问题是寻找n个城市的最短(闭)环游，使得在回到起点之前每个城市均被访问且只访问一次.TSP的图论描述为: 设G=(V,E,W)是由n个城市构成的赋权完全图，其中每个城市用点vi表示，称为顶点，V是顶点集，记为V=(v1,v2, …,vn)； 两个城市间若有道路连接，则相应的两顶点之间有边，用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之间的距离(权)，城市之间的距离也可用权矩阵W=(wij)n×n表示. 要求确定一条遍历所有顶点一次且仅一次的最短回路, 即长度最短的哈密尔顿回路. 在TSP中，城市数目n和城市间的距离(权)矩阵W=(wij)n×n是两个重要的参数[5].

1.2 s-t路旅行商问题的数学模型

TSP还有更一般的形式，即所谓s-t路旅行商问题： 给定一系列的点以及它们两两之间的距离，同时给定一个起点s和终点t，需要寻找一条从s出发到t的最短路线 ，并且这条路线 恰好经过每个顶点一次. 如果包含顶点s,t的回路是长度最短的哈密而顿回路，即遍历所有顶点一次且仅一次的最短回路，则删除边(s,t)后得到的从s出发到t的路一定是s-t路，即恰好经过每个顶点一次的最短路. 假设连接顶点s，t的边是所有边中最短的，且s-t路是从s出发到t，并且恰好经过每个顶点一次的最短路，则把边(s,t)加到s-t路中得到的回路也一定是最短的哈密而顿回路. 而实际上s-t路是一棵最小生成树，其中顶点s,t的度数都为ds=dt=1，其余顶点的度数di=2(i≠s,i≠t). 因此，对给定的赋权图G=(V，E，W)，设图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路旅行商问题的数学模型[6]如下式所示：

2 求解s-t路旅行商问题(即DCMST问题)的离散粒子群算法的流程

文献[4]中，粒子编码采用Prüfer数，在求解s-t路旅行商问题的离散粒子群算法中，也是采用Prüfer数编码机制，Prüfer数的编码及解码过程详见文献[7].

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

这里给出简要的算法流程如图1所示[8]. 求解s-t路旅行商问题的算法中，有关粒子的适应度函数构造、如何初始化粒子种群、粒子位置和速度的更新公式与求解DCMST问题的算法一样，详见文献[4].s-t路是一棵特殊的度约束最小生成树，其中顶点s,t的度数都为ds=dt=1，其余顶点的度数di=2(i≠s,i≠t). 在用最大数法对位置矩阵进行解模糊后得到的Prüfer数中会出现有的粒子不满足度约束，因此需要对粒子进行顶点度数的检验. 由于顶点的度与顶点在Prüfer数中出现的次数有关： 若顶点在Prüfer数中有出现，则出现的次数再加上1就是该顶点的度； 若顶点没有在Prüfer数中出现，则该顶点的度为1. 为此检验条件定为: 顶点在Prüfer数中出现的次数为1. 改进方法: 如果某一个顶点的度超过2，违反了度约束，那么将该顶点随机替换为没有在Prüfer数中出现的顶点. 如果粒子是可行的，则对Prüfer数进行解码，可得到一棵满足度约束的生成树.

3 应用求解DCMST问题的模糊离散PSO解决TSP的策略

根据Prüfer数编码的特点，应用求解DCMST问题的离散粒子群算法解决TSP，所采取的策略是： 1)先把TSP转化成s-t路旅行商问题(即DCMST问题)，应用DCMST的模糊离散粒子群优化算法求解s-t路旅行商问题，得到最优解； 2)再把边est对应的最小距离加入所求得的s-t路中，就得到TSP的最优解.

具体做法：

第一步，对给定的实际TSP问题，把它转化为赋权图G=(V,E,W)，假设有n个顶点(城市)，分别用1至n的自然数表示顶点. 从图G中找出(权)距离最小的两个顶点(城市)，不妨记s和t，并把s和t两顶点的度限制设为1，其余顶点的度限制设为2，这样，就把TSP问题转化成s-t路旅行商问题了.

第二步，利用算法求出s-t路旅行商问题的最优解，即用算法求得以s，t为叶子顶点的最小生成树(线性树).

第三步，在求得的以s，t为叶子顶点的度约束最小生成树(线性树)中，加入边(s,t)得到的闭回路就是TSP的最优解.

4 仿真实验分析

4.1 实验参数设置

为了说明基于Prüfer数的离散粒子群优化算法用于求解TSP问题的有效性, 本研究与单亲遗传算法的实验结果进行比较. 求解s-t路旅行商问题的算法参数设置如下： 学习因子C1和C2均为2，权重系数W=1，粒子群规模分别取M=20，30，40，50，60，迭代次数CS设为40，50, 60. 实例与文献[9]中的一致, 已知给出了9个城市之间的距离构成的权矩阵数据.

实例假设图G的权矩阵W如下所示，顶点数n=9，求TSP最优解.

对于这个TSP问题，先用算法求解s-t路旅行商问题. 观察权矩阵的数据，可知顶点1和顶点4之间的距离最短为w14=4，所以置顶点1和4的度限制为1. 其余顶点的度数为2，即度约束限制为: b=[1, 2, 2, 1, 2, 2, 2, 2, 2]，实验结果见表1.

表1 实例的数值实验

4.2 实验结果比较

分析表1的具体数据，可看出当迭代次数CS为40，种群规模为40时，就得到了度约束限制为b=[1, 2, 2, 1, 2, 2, 2, 2, 2]的s-t路旅行商问题(最小生成树)的最优解为107，线性树对应的Prüfer数为[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)构成. 再将顶点1与顶点4的边(1，4)加到树中，就得到TSP的最优回路长为111. 与文献[9]提出的用单亲遗传算法对该实例求解得到的结果一样. 说明应用DCMST的模糊离散粒子群优化算法可以解决TSP问题.

表2 本研究算法与相关算法的实验对比情况

但文献[9]的算法当种群大小为100, 最大迭代次数等于100时, 才得到最短回路长是111. 而利用本研究算法当种群大小为40，最大迭代次数为40时，就能得到最优解111，而且收敛效果非常理想. 本研究算法与文献[9-10]的算法的实验结果比较见表2. 表2给出本研究算法跟文献[9-10]的算法在种群大小、最大迭代次数、TSP回路长度的对比. 在文献[10]的算法中未给出最大迭代次数，所以表中文献[10]的最大迭代次数为空，同时文献[10]会多次出现TSP回路长度为113，所以这里取平均值112.5. 从表 中可以看出本研究算法相对文献[9]在种群大小和最大迭代次数方面均比较小，能以更少的迭代次数和种群规模获得同样的TSP回路最优解. 而相对文献[10]，本研究能以更小的种群规模，获得相对更优的TSP回路长度. 综上，本研究算法相对文献[9-10]均有一定程度的优化，在求解TSP问题中更为有效.

5 结论

旅行商问题(TSP)是经典的组合最优化问题，至今未有十分有效的最优算法. 本研究分析了s-t路旅行商问题与DCMST问题的关系，提出了应用离散粒子群算法解决TSP的策略，通过把TSP转化为s-t路旅行商问题，再利用求解度约束最小生成树(DCMST)的模糊离散粒子群优化算法解决TSP问题. 并用TSP实例进行仿真实验，结果证明了算法的有效性.

[1] 陈震亦. 粒子群优化算法研究及其在TSP问题中的应用[D]. 福州: 福州大学, 2004.

[2] 郭文忠, 陈国龙. 求解TSP问题的模糊自适应粒子群算法[J]. 计算机科学, 2006，33(6)： 161-162; 185.

[3] 庞巍，王康平，周春光，等. 模糊离散粒子群优化算法求解旅行商问题[J]. 小型微型计算机系统，2005，26(8)： 1 331-1 334.

[4] 严坤妹，王镌, 林娟，等. 求解DCMST问题的模糊离散粒子群优化算法[J]. 莆田学院学报，2011，18(5): 59-63.

[5] 塔哈. 运筹学导论[M]. 9版. 刘德刚, 朱建明, 韩继业, 译. 北京: 中国人民大学出版社，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] 纪震，廖惠连，吴青华. 粒子群算法及应用[M]. 北京： 科学出版社, 2009.

[9] 宋海洲． 求解度约束最小生成树的单亲遗传算法[J]． 系统工程理论与实践，2005，25(4)： 61-66.

[10] 雷建平，沈成武，闻骥骏. 货郎担问题与单亲遗传算法[J]. 武汉理工大学学报，2003，25(6)： 80-83.

(责任编辑： 林晓)

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-)，副教授，主要从事应用数学教学、计算智能及其应用方面研究，ykm6607@163.com

国家自然科学基金资助项目(11501114)

TP301.6

A