改进粒子群算法求解TSP问题

第五届“挑战杯”广西大学生课外学术科技作品申报书序号：编码：第五届“挑战杯”广西大学生课外学术科技作品竞赛作品申报书作品名称：基于k-means的改进粒子群算法求解TSP问题学校全称： 河池学院申报者姓名（集体名称： 陈国类别：自然科学类学术论文□哲学社会科学类社会调查报告和学术论文AB说 明申报者应认真阅读此说明各项内容后按要求详细填写。A1A2（自然科学类学术论文、分别B1、B2B3C技作品竞赛组委会填写。学术论文、社会调查报告及所附的有关材料必须是中文（若是外文，请附中文版，请以四号楷体打印在4纸上，附于0（5×。6．参赛作品（数量参照通知）各一式叁份分别按组委会规定的时间报至组委会秘书处。7送。其他参赛事宜请向本校竞赛组织协调机构咨询。4联系人：廖梅宣联系电话：（办公）（手机）传 真：邮政编码：530022A1．申报者情况（个人项目）说明：1．必须由申报者本人按要求填写，申报者情况栏内必须填写个人作品的第一作者（60%以上的工作者2．本表中的学籍管理部门签章视为对申报者情况的确认。姓 名 陈国鸿 性别 男 出生年月 1986年7月学校全称 河池学院

专业 计算机科学与技术现学历申作品全称报 毕业论

本科 年级 大四学制4年 入学时间 2007年9月基于k-means的改进粒子群算法求解TSP问题者 题目情 通讯地况常住地

改进粒子群算法求解TSP问题42计信系42

邮政编码单位电话邮政编码

5463000778—546300通讯地址计信系

住宅电话

0778—合姓名作者情况资格意见认定 院系负人或导师意见

性别 年龄 学历 所在单位是否为2011年7月1人教育、非在职的各类高等院校学生（含专科生、本科生和研究生。是□否若是，其学号为：2007107201 （签章）2011年4月23日本作品是否为课外学术科技或社会实践活动成果□是 否 负责人签名：2011年4月25日B1．申报作品情况（自然科学类学术论文）说明：1．必须由申报者本人填写。本部分中科研管理部门签章视为对申报者所填内容的确认。作品分类请按作品学术方向或所涉及的主要学科领域填写。硕士研究生、博士研究生作品不在此列。作品全称 改进粒子群算法求解TSP问题（B）A．机械与控制（包括机械、仪器仪表、自动化控制、工程、交通、建筑等）B．信息技术（包括计算机、电信、通讯、电子等）C．数理（包括数学、物理、地球与空间科学等）作品分类作品撰写的目

D．生命科学（康、卫生、食品等）E．能源化工（包括能源、材料、石油、化学、化工、生态、环保等）旅行商问题(TSP)又名货郎担问题，是一个典型的NP难题。其数学描述非常简单，但却无法找到一个确定的算法在多项式时间内求解TSP问题，另一方面很多研究领域出现的复杂优化问题可以被抽象概括为TSP问题加以求解，因此找到能够有效解决TSP问题的方法,在理论上和实际应用中都的和基本思路很有价值。本文对基本PSO算法中粒子的位置、速度以及操作进行了重新定义，TSP引入了适合于求解TSP问题的基于k-means的改进措施，对粒子群进行聚类分析，实现了粒子之间的信息交换，扩大了粒子的搜索空间，克服了PSO算法易陷入局部最优的缺陷。两个种群同时寻优，种群内部独立进行PSO进化，种群个体最优之间以一定概率进行交叉。两个种群同时寻优可以减小算法陷入局部最优的概率，种群间个体最优的交叉能够增强两种群间以及粒子间的信息共享，及时传递最优值信息，提高粒子向更好解进化的速度。最后本文对30点TSP问题进行仿真测试，试验表明改进后的粒子群算法能有效地求解TSP问题。（算法在多维连续优化问题的应用中取得了较好（TSPTSPPSO步都取局部最优。这样产生的初始种群全局最优值已经比较接近问题的解，先进性及独特之处 优的缺陷，提出了适合旅行商问题的基于k-means的改进措施。采用k-meansPSO共享，及时传递最优值信息，提高粒子向更好解进化的速度。作品的实际应用价值和现实意义

TSPTSP物理、数学、运筹学、人工智能等诸多领域的研究者，对其近似解的研究一作为一类组合优化问题的代表，TSPVLSIXPSOTSPPSOTSP（的效果，但在旅行商（TSP）等组合优化问题中的应用则相对较TSPPSO学术论文文摘GA）的思想，每一步都取局部最优。这样产生的初始种群全局最优值已经比较接近问题的解，因此可以节省搜索时间，提高算法收敛速度。针对粒子群k-meansk-means种群内部独立进行PSO进化，种群个体最优之间以一定概率进行交叉，减小算法陷入局部最优的概率，种群间个体最优的交叉能够增强两种群间以及粒子间的信息共享，及时传递最优值信息，提高粒子向更好解进化的速度。实验证明，改进后的粒子群算法能有效地求解TSP问题。1..一种基于收缩因子的改进粒子群算法[J].地、何种机构举软件导刊.2009，9(9)：59-60行的会议上或报刊上发表登载及所获奖励

《一种基于收缩因子的改进粒子群算法》获第四届“挑战杯”广西大学生课外学术科技作品竞赛二等奖。审稿。鉴定结果请提供对于理所申报作品具有参考价值的现有技术及技术文献的检索目录申报材料清单（申报论文一称及数量）

申报论文《改进粒子群算法求解TSP问题》一篇。科研管理部门签章

（签章）年 月 日当前国内外同类课题研究水平概述说明：1．申报者可根据作品类别和情况填写。2．填写此栏有助于评审。最初的PSO是用来解决连续空间问题的,为了适合求解TSP问题,人们对算法进行了各种改进。主要可以分为以下几个方面:PSO的运算符号和规则：PSO用于求解TSP阵技术,并重新定义其更新公式。ClercTSP。李盘荣QPSO等,为了克服PSOPSO算法。通过引入模糊技术,给出了一种惯性权重的模糊自适应调整模型及其相应的粒子群优化算法。王文峰等,在重新定义了PSO的速度和位置公式的基础上,针对易早熟,收敛慢的缺陷,建立局部极小区域的扰动机制,PSECHDPSO。混合粒子群算法。高尚等结合遗传算法、蚁群算法和模拟退火算法的思想,提出用混合粒子群算法来求解CTSP。谭皓等,提出一种结合PSO和蚁群算法特点的混合算法。陈曦把免疫系统的免疫信息处理机制引入到粒子群优化算法中,设计了免疫粒子群优化算法。PSO。王翠茹为了更有利于粒子发现问题的全局最优解,在算法中引入了更符合自然界生物学习规律的速度变异机制和粒子自探索机制。莫愿斌提出了粒子群复形(CPSO)算法。对TSP解序列提出5种运算,得到能求解TSP的PSO算法。推荐者情况及对作品的说明说明：1．由推荐者本人填写。2．推荐者须具有高级专业技术职称，并与申报作品相同（教研组集体3．推荐者填写此部分，即视为同意推荐。推荐者所在单位签章仅被视为对推荐者身份的确认。推荐者

姓 名

黄星寿性别男 年龄47职称 副教授河池学院计算机与信息科学系广西宜州市龙江路42号情况 通讯地

河池学院计信系

邮政编码住宅电话

546300推荐者所在单位签章 （签章）年 月 日申报者所呈交的作品是在指导教师的指导下独立进行

研究所取得的研究成果。该作品针对粒子群算法易陷入局部最优的缺陷引入了请对作品的意义、适合于求解TSP问题的基于k-means的改进措施，对粒子技术水平、适用范群进行聚类分析，实现了粒子之间的信息交换，扩大了粒围及推广前景做出的搜索空间，克服了PSO算法易陷入局部最优的缺陷。实您的评价 验结果表明改进后的粒子群算法能有效地求解TSP问题。其它说明姓 名推荐 工作单者

周永权 性别男年龄49职称 教授河池学院计算机与信息科学系（兼职教授）广西宜州市龙江路42号河池邮政情 通讯地况

学院计信系 编码住宅电话

546300推荐者所在单位签章 （签章）年 月 日该作品是在指导教师易云飞的指导下独立进行研究所取得请对申报者申报的研究成果，作品中的实验数据是真实的。情况的真实性做出阐述该作品地提出了一种改进的粒子群算法，并将该算法用于TSP请对作品的意 科学研,又特别适合工程应用；可广泛应用于函数寻优、神义、技术水平、经网络训练、模式分类、模糊系统控制以及其它的应用领域。适用范围及推广仿真实验表明改进后的算法是可行、有效的。前景做出评价其它说明学校组织协调机

（签章）构确认并签章 年 月 日校主管领导或校主管部门确认并签章

我单位经自查，承诺该作品符合挑战杯申报作品的要求，接受竞赛组委会抽查。（签章）年 月 日各省（区、市）评审委员会初评意见 （签章）年 月 日各省（区、市）组织协调委员会审定意见

团 委 科 协 教育厅 学 联（签章） （签章） （签章） （签章）年 月 日组织委员会秘书处资格和形式审查意见组委会秘书处资格审查意见审查人（签名）年 月 日组委会秘书处形式审查意见审查人（签名）年 月 日组委会秘书处审查结果□合格 □不合格负责人（签名）年 月 日F1．评审委员会预审意见粘贴处F2．评审委员会终审意见粘贴处(正文打印页)基于k-means的改进粒子群算法求解TSP问题陈国鸿(河池学院计算机与信息科学系,广西宜州546300)[摘要]（TSP问题）解TSPPSO算法中粒子的位置、速度以及操作进行了重新定义。初始种群的k-means的改进措施。采用k-means对粒子群进行PSO进化，种群个体最优之间以TSP问题。[关键词]旅行商问题；粒子群算法；K-means；贪心算法引言旅行商问题(TravelingSalesmanProblem，简称TSP)又名货郎担问题，NPNTSP问题，另一方面很多研究领域出现的复杂优化问题可以被抽象概括为TSP问题加以求解，因此找到能够有TSP问题的方法,在理论上和实际应用中都很有价值。（ParticleSwarmJamesKennedyRussellEberhart终得到满意解。该算法在多维连续优化问题的运用中取得了较好的效果，但在TSPPSOTSPk-meansPSOPSO提高粒子向更好解进化的速度。30TSP试验TSPTSPTSPNP图论描述为：给定图其中VHamilton历所有顶点一次且仅一次的最短回路。设(i,j)的长度。引入决策变量：

dij为城市i与j之间的距离，即弧=1若旅行商访问城市i后访问城市j=X

(1.1)ij

0 否则MinZXdTSP

i,j1

ijij (1.2)TSP合爆炸”。所以，寻求和研究TSP的有效启发式算法,是问题的关键。PSOPSO算法主要模拟鸟群飞行的觅食行为，通过鸟群的集体协作达到寻优目PSO解提供的信息，在解空间内不断飞行，实现寻找最优解的目的。PSO设搜索空间为N维，总粒子数为Numi个粒子的位置向量=(X x,x=(i i1 i

,x,...,xi3

i

v,v=(i1 i=(

,v,...,vi3

)，第i个i粒子在“飞行”中的历史最优位置是Ppi

,p,...,p

)，

表示目前为止在i i1 i2 i3 in g整个粒子群中发现的全局最优粒子；粒子按如下方式飞行：v(t+1)=w×vij

(t)+c1×rand1()Pij

(t)-xij

(t)]+c2×rand2()Pgj

(t)-xij

(t)] (2.1)x(t+1)= xij

(t)+ vij

(t+1) (2.2)jww为加速常数，通常在０～２取值，c1c2rand2[0,1maxXminXmaxVmin,Vmax

]，迭代中若位PSO度向量来改变位置，最终找到最优解。X[t+1]V[t]pbest[i]X[t] gbest图1.粒子移动原理图图1粒子移动原理图i基本粒子群算法的流程如下：Step1：依照初始化过程，对粒子群的随机位置和速度进行初始设定；Step2：计算每个粒子的适应值；Step3：Pig比较，若较好，则将其作为当前的最好位置；Step4：对每个粒子，将其适应值与全局所经历的最好位置g

的适应值进行比较，若较好，则将其作为当前的全局位置；Step5：根据方程(2.1)、(2.2)对粒子的速度和位置进行迭代进化；Step6：循环步骤2-5，直到结束条件为足够好的适应值或达到一个预设最大迭代次数，算法终止。TSP定义更新TSPPSOTSPPSO置、速度以及操作进行重新定义：状态空间TSP问题的结果是要求出具有最短路径的哈密尔顿圈，所以状态空间即为所有位置的集合。n粒子的位置n与in与i

i1之x(n

,...,n ,

E,nn ，E为状态空间。粒子的速度

1 2

N

i 1 N速度定义为粒子位置的变换集，表示一组置换序列的有序列表。可以kv{(ik

,j),(ik

,j,),N},k,v}} （3.1）i1k其中，||v||表示该速度所含交换的数目，式(3.1)表示先交换粒子中ni1kinj1的位置，然后交换n 、nj2i粒子位置与速度的加法操作3)，(2，4)},X+VX={2，4，1,5,3,2}。粒子位置与位置的减法操作X={2，4，1，5，3，2}，Y={1，5，2，4，3，1}，由于X(1)=Y(3)=2,)=2，所以第一个交换为11so1X1=X+11

={2,41,5,3,2}+(1,3)={1,4,2,5,3,1}；X1(2)=Y(4)=4，因此第二个交换为22so=(2,4)，作用到粒子的位置X1后得X2=X1+so为22

={1，4，2，5，3，1}+(2,4)={1，5，2，4，3，1}=Y，)=Y，所以位置X与位置Y相减后得到一组置换序列，即X-Y={(1,3),(2,4)}。粒子速度与速度的加法操作粒子速度与速度的加法操作为两个置换序列的合并，结果为一个新的置换序列，即一个新的速度。例如：速度V1={(1,3),(2,4)},V2={(2,3),(5,4)},相加后得V=V1+V2={(1,3),(2,4),(2,3),(5,4)}。实数与粒子速度的乘法操作cvk|c×k|(c×kV={(2,3),(1,3),(4,5),(5,2)},k=4c=0.78,c×k=3.12，|c×k|=3，c×V={(2,3),(1,3),(4,5)}。公式更新式表示如下：Vk1wVkcr(PkXk)cr(PkXk)i i 11 i

22 g i

（3.2）iiiXkXkVk(3.3)iii、c2PSO0～2、为(0,1)为两交换序的合并算子，表示速度与k-meansPSOPSO算法具有较高的搜索效率和较快的收敛速度，但是粒子在搜索中会过分依赖粒子群提供的极值信息(无论是个体极值信息，还是全局极值信息)，从而导致粒子群更易趋于同质化，减少了粒子能够获得的有效信息量，降低了粒子逃离局部最优的可能性。(3.2)k-Meansk-Means是一种在无类标号数据中发现簇和簇中心的方法。该算法的基本思想是：给定nk，随机选取kk则函数的值在不断减小，最终收敛至一个固定的值。因此，k-Meansk，nk处理流程：从nk根据最小距离重新对相应对象进行划分；重新计算每个有变化聚类的中心对象。循环(2)到(3)直到每个聚类不再发生变化为止；k-Meansknkk象”（引力中心）来进行计算的。K-Meansnk个聚类；③再计算每个新聚类的聚类中心（该聚类中所有对象的均值）；④k-MeansPSO1；2211k-meansPSO速度和位置向量更新方式为：VkwVkcr(cluster(Pk)Xk)c

r(Pk

Xk)i i 1

i i 22 g

（3.4）Xk1XkVk1i i i

（3.5）i其中，cluster(Pk)表示对粒子历代最优解聚类后粒子Xi所属类的代表对象，其他参数的含义与基本PSO算法的含义相同。i贪心算法产生初始种群由于旅行商问题为一个循环回路，所以起始城市可以为任意的一个城市。发城市即可。至此，可以利用这个贪心算法得到近似最优循环序列，产生一定规模的初搜索时间，提高算法收敛速度。两个种群同时寻优生物界中少数优良个体进行交叉，有利于产生优良的后代，并保证了父代PSOPSOTSPStep1：：AB[0,12改进粒子群算法流程图实数，设定粒子群算法的参数w，c1，c2；Step2：pbestgbest；Step3：k-Means2改进粒子群算法流程图i在的类以及类的中心点cluster(Pk)。iStep4：以一定概率将A群粒子的个体最优与B群粒子的个体最优进行交叉，产生新的个体最优；Step5：为每个粒子按照式(3.4)和式(3.5)确定新的速度向量和下一代的位置向量，并产生两个新的全局最优。Step6：Step2径长度，更新粒子个体的历史最优位置和粒子群的全局最优解。Step7：如未满足终止条件(一个种群两次进化适应度之差小于最小误差)，则返回step3。改进算法的流程图如图2所示：实验结果及分析Oliver30作为实验例子，并与基本Oliver30问题的最好解为径为：1-2-3-9-18-19-20-21-10-11-7-8-14-15-24-25-26-27-28-29-16-17-22-23-30-采用MicrosoftVisualStudio2005Intel(R)Core(TM)i3,2.13GHzCPU,2GB内存，WindowsVista进PSO算法与基本PSO30100粒子群算法中惯性权重W从递减到0.5，加速常数C1=C2=1.2,K-means聚类数为5，最大迭代次数1000。遗传算法交叉概率Pc=0.2，变异概率Pm=0.5。实验结果如表1所示，得到的最优结果巡回路径如图3所示，其巡回路径与目前已知最好解一致。表1Oliver30实验结果比较基本PSO457.6632435.9918基本PSO457.6632435.9918480.14520.00次数---遗传算法425.6905423.7406429.487625.37%735.40改进PSO424.7926423.7406425.693174.59%583.00

平均迭代12-13-4-5-6。12-13-4-5-6。3Oliver30130423.740630PSO423.7406，Oliver30PSO435.9918，前最优解，遗传算法虽然也能收敛到当前最优解，但