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

1、第五届“挑战杯”广西大学生课外学术 科技作品申报书序号：编码：第五届挑战杯”广西大学生课外学术科技作品竞赛作品名称：基于 k-means 的改进粒子群算法求解 TSP问题学校全称：河池学院陈国鸿申报者姓名（集体名称）类别：回自然科学类学术论文哲学社会科学类社会调查报告和学术论文科技发明制作A类科技发明制作B类说明1申报者应认真阅读此说明各项内容后按要求详细填写。2申报者在填写申报作品情况时只需根据个人项目或集体 项目填写 A1 或 A2 表，根据作品类别（自然科学类学术论文、 哲学社会科学类社会调查报告和学术论文、 科技发明制作） 分别 填写 B1、B2 或 B3 表。所有申报者可根据情况填写

2、 C 表。3表内项目填写时一律用钢笔或打印， 字迹要端正、 清楚， 此申报书可复制。4序号、编码由第五届“挑战杯”广西大学生课外学术科 技作品竞赛组委会填写。5学术论文、社会调查报告及所附的有关材料必须是中文 （若是外文，请附中文版） ，请以四号楷体打印在 A4 纸上，附于 申报书后，字数在8000字左右（文章版面尺寸 14.5 X22cm ）。6参赛作品（数量参照通知）各一式叁份分别按组委会规 定的时间报至组委会秘书处。7 作品申报书须按要求由各校竞赛组织协调机构统一寄送。8 其他参赛事宜请向本校竞赛组织协调机构咨询。9 寄送地址：南宁市古城路 4 号共青团广西区委学校部。联 系 人：廖梅宣

3、联系电话：（办公）（手机）传 真：邮政编码：530022A1 申报者情况（个人项目）说明：1 .必须由申报者本人按要求填写，申报者情况栏内必须填写 个人作品的第一作者（承担申报作品 60%以上的工作者） 2 .本表中的学籍管理部门签章视为对申报者情况的确认。姓名陈国鸿性别男出生年月1986年7月申 报 者 情 况学校全称河池学院专业计算机科学与技术现学历本科 年级大四学制4年入学时间2007年9月作品全称基于k-means的改进粒子群算法求解TSP冋题毕业论文 题目改进粒子群算法求解TSP问题通讯地址广西宜州市龙江路42号河池学院计信系邮政编码546300单位电话0778 常住地 通讯地址广西

4、宜州市龙江路42号河池学院计信系邮政编码546300住宅电话0778 合 作 者 情 况姓名性别年龄学历所在单位资 格 认 疋学校学籍 管理部门 意见是否为2011年7月1日前正式注册在校的全日制非成 人教育、非在职的各类高等院校学生（含专科生、本科生和 研究生）。是否若是，其学号为：2007107201（签章）2011年4月23日院系负责 人或导师 意见本作品是否为课外学术科技或社会实践活动成果 魂 否负责人签名：2011年4月25日B1 申报作品情况（自然科学类学术论文）说明：1.必须由申报者本人填写。2 .本部分中科研管理部门签章视为对申报者所填内容的确认。3 .作品分类请按作品学术方向

5、或所涉及的主要学科领域填写。4 .硕士研究生、博士研究生作品不在此列。作品全称改进粒子群算法求解TSP问题作品分类（B） A .机械与控制（包括机械、仪器仪表、自动化控 制、工程、交通、建筑等）B. 信息技术（包括计算机、电信、通讯、电子等）C. 数理（包括数学、物理、地球与空间科学等）D .生命科学（包括生物、农学、药学、医学、健 康、卫生、食品等）E.能源化工（包括能源、材料、石油、化学、化 工、生态、环保等）作品撰写的目 的和基本思路旅行商问题（TSP）又名货郎担问题，是一个典型的 NP难题。其数学描 述非常简单，但却无法找到一个确定的算法在多项式时间内求解TSP问题,另一方面很多研究领

6、域出现的复杂优化问题可以被抽象概括为TSP问题加以求解，因此找到能够有效解决 TSP问题的方法，在理论上和实际应用中都 很有价值。本文对基本PSO算法中粒子的位置、速度以及操作进行了重新定义， 使粒子群算法适合于求解TSP问题，并采用贪心算法的思想每一步都取局部 最优。这样产生的初始种群全局最优值已经比较接近问题的解，因此可以节 省搜索时间，提高算法收敛速度。针对粒子群算法易陷入局部最优的缺陷，引入了适合于求解TSP冋题的基于k-means的改进措施，对粒子群进行聚 类分析，实现了粒子之间的信息交换，扩大了粒子的搜索空间，克服了PSO算法易陷入局部最优的缺陷。两个种群同时寻优，种群内部独立进行

7、PSO进化，种群个体最优之间以一定概率进行交叉。两个种群同时寻优可以减小 算法陷入局部最优的概率，种群间个体最优的交叉能够增强两种群间以及粒 子间的信息共享，及时传递最优值信息，提高粒子向更好解进化的速度。最后本文对30点TSP问题进行仿真测试，试验表明改进后的粒子群算 法能有效地求解TSP问题。作品的科学性、 先进性及独特 之处粒子群优化（简称PSO）算法在多维连续优化问题的应用中取得了较好 的效果，但在旅行商（简称TSP问题）等组合优化问题中的应用则相对较少。 为使粒子群算法适合于求解 TSP问题本文对基本PSO算法中粒子的位置、 速度以及操作进行了重新定义。初始种群的产生借鉴贪心算法的思

8、想，每一 步都取局部最优。这样产生的初始种群全局最优值已经比较接近问题的解， 因此可以节省搜索时间，提高算法收敛速度。针对粒子群算法易陷入局部最 优的缺陷， 提出了适合旅行商冋题的基于 k-means的改进措施。米用 k-means对粒子群进行聚类分析，实现了粒子之间的信息交换，扩大了粒子 的搜索空间，避免了算法陷入局部最优。两个种群同时寻优，种群内部独立 进行PSO进化，种群个体最优之间以一定概率进行交叉，减小算法陷入局 部最优的概率，种群间个体最优的交叉能够增强两种群间以及粒子间的信息 共享，及时传递最优值信息，提高粒子向更好解进化的速度。作品的实际应 用价值和现实 意义TSP问题是一种典

9、型的组合优化问题，是一种用来验证算法有效性的典 型算例。由于TSP最优解的求解代价是指数级的，因此该问题吸引了生物、 物理、数学、运筹学、人工智能等诸多领域的研究者，对其近似解的研究一 直是算法设计的一个重要课题，TSP问题的有效解决对推动整个组合优化领 域的发展有重大的影响。作为一类组合优化问题的代表，TSP问题在实际工程中有许多应用，如 计算机联网、物流等行业中的车辆调度优化、电力系统配电网络重构、城市 管道铺设优化、交通导航、电气布线、电子地图、VLSI单元布局、X射线结晶学问题等。PSO算法在连续空间优化问题上已经取得了很好的效果，但是将其应用 在TSP等离散优化冋题中还是一种尝试。因

10、此用改进的PSO算法有效的求解TSP问题，在整个组合优化领域和实际工程中都有着重要影响和实际意 义。学术论文文摘粒子群优化（简称PSO）算法在多维连续优化问题的应用中取得了较好 的效果，但在旅行商（简称TSP问题）等组合优化问题中的应用则相对较 少。为使粒子群算法适合于求解 TSP问题本文对基本PSO算法中粒子的位 置、速度以及操作进行了重新定义。初始种群的产生借鉴贪心算法（简称 GA）的思想，每一步都取局部最优。这样产生的初始种群全局最优值已经比 较接近问题的解，因此可以节省搜索时间，提高算法收敛速度。针对粒子群 算法易陷入局部最优的缺陷，提出了适合旅行商问题的基于 k-means的改 进措

11、施。采用k-means对粒子群进行聚类分析，实现了粒子之间的信息交 换，扩大了粒子的搜索空间，避免了算法陷入局部最优。两个种群同时寻优，种群内部独立进行PSO进化，种群个体最优之间以一定概率进行交叉，减 小算法陷入局部最优的概率，种群间个体最优的交叉能够增强两种群间以及 粒子间的信息共享，及时传递最优值信息，提高粒子向更好解进化的速度。 实验证明，改进后的粒子群算法能有效地求解 TSP问题。作品在何时、何 地、何种机构举 行的会议上或 报刊上发表登 载及所获奖励1已发表相似论文：易云飞，陈国鸿 一种基于收缩因子的改进粒子群算法J. 软件导刊.2009, 9(9): 59-602-一种基于收缩因

12、子的改进粒子群算法获第四届挑战杯”广西大学生课 外学术科技作品竞赛二等奖。3.本次申报的论文已投往全国中文核心期刊 计算机工程与应用，目前正在 审稿。鉴定结果请提供对于理 解、审查、评价 所申报作品具 有参考价值的 现有技术及技 术文献的检索 目录申报材料清单 （申报论文一 篇，相关资料名 称及数量）申报论文改进粒子群算法求解 TSP问题一篇。科研管理 部门签章（签章）年 月日C当前国内外同类课题研究水平概述说明：1 .申报者可根据作品类别和情况填写。2 .填写此栏有助于评审。最初的PSO是用来解决连续空间问题的，为了适合求解TSP问题，人们对算法进行了各 种改进。主要可以分为以下几个方面：1

13、. 重新定义PSO的运算符号和规则：黄岚等引入交换子和交换序的概念,构造一种特殊的PSO用于求解TSP。庞巍采用模糊矩 阵技术,并重新定义其更新公式。Clerc重新定义了运算符号和规则,并用于求解TSP。李盘荣 针对收敛速度不够快的缺陷，提出利用量子粒子群优化算法 QPSO。钟一文等，在重新定义运算 速度、规则和运动方程的基础上，为防止算法的早熟停滞现象，提出用扰动速度来增加粒子群的 多样性，为提高算法的求精能力，设计了一种高效的近邻搜索算子来提高粒子的适应值。郭文忠等，为了克服PSO在求解离散问题所具有的计算时间长和容易陷入停滞状态等问题，基于“簇”思想，对粒子间距离进行重新定义并给出了相应

14、的动态邻域PSO算法。通过引入模糊技术，给出了一种惯性权重的模糊自适应调整模型及其相应的粒子群优化算法。王文峰等，在重新定义了 PSO的速度和位置公式的基础上，针对易早熟，收敛慢的缺陷，建立局部极小区域的扰动机 制,结合局部搜索算法PSEC,提出了一种混合离散粒子群算法 HDPSO。2. 混合粒子群算法。高尚等结合遗传算法、蚁群算法和模拟退火算法的思想 ，提出用混合粒子群算法来求解 CTSP。谭皓等,提出一种结合PSO和蚁群算法特点的混合算法。陈曦把免疫系统的免疫信息 处理机制引入到粒子群优化算法中，设计了免疫粒子群优化算法。3. 其他改进的PSO o王翠茹为了更有利于粒子发现问题的全局最优解

15、，在算法中引入了更符合自然界生物学 习规律的速度变异机制和粒子自探索机制。莫愿斌提出了粒子群复形(CPSO)算法。对TSP解序列提出5种运算,得到能求解TSP的PSO算法。D.推荐者情况及对作品的说明说明：1.由推荐者本人填写。2 .推荐者须具有高级专业技术职称，并与申报作品相同或相关领域的专家学者或专业技术人员 （教研组集体）推荐亦可。3 .推荐者填写此部分，即视为同意推荐。4 .推荐者所在单位签章仅被视为对推荐者身份的确认。推荐者 情况姓名黄星寿性别男年龄47职称副教授工作单位河池学院计算机与信息科学系通讯地址广西宜州市龙江路42号 河池学院计信系邮政编码546300单位电话住宅电话推荐者

16、所在 单位签章（签章）年 月日请对申报者申报情况真实性做出阐述申报者所呈交的作品是在指导教师的指导下独立进行 研究所取得的研究成果。请对作品的意义、 技术水平、适用范 围及推广前景做出 您的评价该作品针对粒子群算法易陷入局部最优的缺陷，引入了适合于求解TSP问题的基于k-means的改进措施，对粒子 群进行聚类分析，实现了粒子之间的信息交换，扩大了粒子 的搜索空间，克服了 PSO算法易陷入局部最优的缺陷。实 验结果表明改进后的粒子群算法能有效地求解TSP问题。其它说明推 荐 者 情 况姓名周永权性别男年龄49职称教授工作单位河池学院计算机与信息科学系（兼职教授）通讯地址广西宜州市龙江路42号河

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

18、校主管部门确认并我单位经自查，承诺该作品符合挑战杯申报作品的要签章求，接受竞赛组委会抽查。（签章）年月日各省（区、市） 评审委员会初评 意见年（签章） 月日各省（区、市）组织协调委员会 审定意见团委科协教育厅学联（签章）（签章）（签章）（签章）年月日E.组织委员会秘书处资格和形式审查意见组委会秘书处资格审查意见审查人（签名） 年 月日组委会秘书处形式审查意见审查人（签名）年 月日组委会秘书处审查结果合格不合格负责人（签名）年 月日F1.评审委员会预审意见粘贴处F2 评审委员会终审意见粘贴处（正文打印页 ）基于k-means的改进粒子群算法求解TSP问题陈国鸿（ 河池学院 计算机与信息科学系 ,

19、 广西 宜州 546300）摘 要粒子群优化（简称PSO）算法在多维连续优化问题的应用中取得了较好的效果，但在旅行商（简称TSP问题）等组合优化问题中的应用则相对较少。为使粒子群算法适合于求 解TSP问题本文对基本PSO算法中粒子的位置、速度以及操作进行了重新定义。初始种群的 产生借鉴贪心算法的思想， 每一步都取局部最优。 这样产生的初始种群全局最优值已经比较 接近问题的解， 因此可以节省搜索时间， 提高算法收敛速度。 针对粒子群算法易陷入局部最 优的缺陷，提出了适合旅行商问题的基于 k-mea ns的改进措施。采用k-mea ns对粒子群进行 聚类分析， 实现了粒子之间的信息交换， 扩大了粒

20、子的搜索空间， 避免了算法陷入局部最 优。两个种群同时寻优，种群内部独立进行PSOS化，种群个体最优之间以一定概率进行交叉， 减小算法陷入局部最优的概率， 种群间个体最优的交叉能够增强两种群 间以及粒子间的信息共享， 及时传递最优值信息， 提高粒子向更好解进化的速度。 实验证明， 改进后的粒子群算法能有效地求解 TSP问题。关键词旅行商问题；粒子群算法； K-means;贪心算法0 引言旅行商问题 (Traveling Salesman Problem，简称TSP）又名货郎担问题,是一个典型的 NP 完全问题。原型描述：给定求一条访问各个城市且仅访问一次的最短路线。N 个城市和两两城市之见的距

21、离, 虽然其数学描述非常简单, 但却TSP 问题,另一方面很多研究领 域出现的复杂优化问题可以被抽象概括为 TSP 问题加以求解,因此找到能够有无法找到一个确定的算法在多项式时间内求解效解决 TSP 问题的方法 ,在理论上和实际应用中都很有价值。粒子群算法（Particle SwarmOptimization，简称PSO算法最早是在1995 年由美国社会心理学家 James Kennedy和电气工程师 Russell Eberhart 共同提出的一种全局优化算法， 该算法的基本思想来源于对鸟群简化社会模型的研究及 行为模拟， 其中的每个个体充分利用群体的与自身的智能， 不断地调整学习， 最 终

22、得到满意解。该算法在多维连续优化问题的运用中取得了较好的效果，但在 TSP 等组合优化问题中的应用则相对较少。本文对基本PSO算法中粒子的位置、速度以及操作进行了重新定义，使粒子 群算法适合于求解TSP问题，并采用贪心算法的思想每一步都取局部最优。这样 产生的初始种群全局最优值已经比较接近问题的解， 因此可以节省搜索时间， 提 高算法收敛速度。针对粒子群算法易陷入局部最优的缺陷，引入了适合于求解 TSP问题的基于k-means的改进措施，对粒子群进行聚类分析，实现了粒子之间的信息交换，扩大了粒子的搜索空间，克服了 PSO算法易陷入局部最优的缺 陷。两个种群同时寻优，种群内部独立进行PSO进化，

23、种群个体最优之间以一定 概率进行交叉。 两个种群同时寻优可以减小算法陷入局部最优的概率， 种群间个 体最优的交叉能够增强两种群间以及粒子间的信息共享，及时传递最优值信息， 提高粒子向更好解进化的速度。最后本文对30点TSP问题进行仿真测试，试验表明改进后的粒子群算法能 有效地求解TSP问题。1 TSP 问题TSP是运筹学、图轮和组合优化中的 NP难问题。问题的具体如下：给定 N 个城市及两两城市之间的距离， 求一条经过各城市一次且仅一次的最短路线。 其 图论描述为：给定图G=(V，A),其中V为顶点集，A为各顶点相互连接组成的 弧集，已知各顶点间连接距离，要求确定一条长度最短的 Hamilto

24、n 回路，即遍 历所有顶点一次且仅一次的最短回路。设dij 为城市 i 与 j 之间的距离，即弧( i,j) 的长度。引入决策变量：1 若旅行商访问城市 i 后访问城市 jXij =0 否则 (1.1)nMin ZXij dij则TSP的目标函数为i,j 1(1.2)TSP 问题描述非常简单， 但最优化求解很困难， 若用穷举法搜索， 则要考虑所有可能情况， 并两两对比， 找出最优 , 其算法复杂性呈指数增长 , 即所谓的“组 合爆炸”。所以，寻求和研究 TSP的有效启发式算法，是问题的关键。2基本PSO算法PSO算法主要模拟鸟群飞行的觅食行为，通过鸟群的集体协作达到寻优目 的。在PSO算法中，

25、每个粒子利用自身的历史最优位置和整个粒子群的全局最优 解提供的信息，在解空间内不断飞行，实现寻找最优解的目的。2.1基本PSO算法的数学描述如下：设搜索空间为N维，总粒子数为Num 第i个粒子的位置向量 人=(冷必2必3,，沧)，第)个粒子的速度向量是Vi =(Vii，Vi2，Vi3，-, Vin)，第i个 粒子在“飞行”中的历史最优位置是 P=( Pi1, Pi2, Pi3,，Pn)，Pg表示目前为止在 整个粒子群中发现的全局最优粒子；粒子按如下方式飞行：Vj(t+1) = w VjXt) + ci rartdl ( ) P><(t)-Xj + c2 rand2 ( ) P矗(t

26、)-対(t) (2.1)Xj(t +1) = Xj(t) + Vj(t +1)(2.2)其中，下标“j”表示第j维，t为飞行的次数；w为惯性权重，使粒子保持 运动惯性，控制前一速度对当前速度的影响，较大的w适于对解空间进行大规模 探查，较小的w适合于进行小范围开挖；c1，c2为加速常数，通常在02间 取值，c1调节粒子飞向自身最好位置方向的步长，c2调节粒子向全局最好位置 飞行步长；rand1()和rand2 ()是0,1 之间相互独立的随机数。粒子的位置 向量中各维变化范围为Xmin , Xmax，速度变化范围为Vmin, Vmax，迭代中若位 置和速度超过边界范围则取边界值。PSO算法通过

27、粒子在解空间内不断地变化速 度向量来改变位置，最终找到最优解。2.2 基本粒子群算法的流程如下:Stepl :依照初始化过程，对粒子群的随机位置和速度进行初始设定；Step2 :计算每个粒子的适应值；Step3:对于每个粒子，将其适应值与所经历过的最好位置P的适应值进行比较，若较好，则将其作为当前的最好位置；Step4 :对每个粒子，将其适应值与全局所经历的最好位置Pg的适应值进行比较，若较好，则将其作为当前的全局位置；Step5 :根据方程(2.1)、(2.2)对粒子的速度和位置进行迭代进化；Step6 :循环步骤2-5，直到结束条件为足够好的适应值或达到一个预设最 大迭代次数，算法终止。3

28、改进的粒子群算法求解TSP问题3.1 定义更新TSP问题为离散问题，用PSO求解TSP问题需要对基本PSO算法中粒子的位 置、速度以及操作进行重新定义：(1) 状态空间TSP问题的结果是要求出具有最短路径的哈密尔顿圈，所以状态空间即为所有位置的集合。(2) 粒子的位置粒子的位置可以定义为一个具有所有节点的哈密尔顿圈，设所有口与口 1之间的弧存在，粒子的位置可表示为序列x (ni,n2,., nN, n” 1) ，其中 n E,n1 nN 1，E为状态空间。(3) 粒子的速度速度定义为粒子位置的变换集，表示一组置换序列的有序列表。可以(3.1)表示为：v (ik,jk),(ik, jk,) 1,

29、2,N,k 1,2,v其中，| v |表示该速度所含交换的数目，式(3.1)表示先交换粒子中ni1n j1的位置，然后交换n2、nj2的位置，依此类推(4) 粒子位置与速度的加法操作 该操作表示将一组置换序列依次作用于某个粒子位置， 其结果为一个新的位 置，即一个新的节点的排列。 例如：位置为 X=l ，5，2，4，3，l ，速度为 V=(1 ，3) , (2 , 4),则其相加 X+V后结果为 X=2, 4, 1,5,3,2。(5) 粒子位置与位置的减法操作 粒子位置与位置相减后结果为一组置换序列,即速度。例如 X=2, 4, 1 ,5, 3, 2, Y=1, 5, 2, 4, 3, 1,由

30、于 X(1)=Y(3)=2,)=2 ,所以第一个交换为so1 =(1,3),X1=X+ so1 =2,41,5,3,2+(1,3)=1,4,2,5,3,1 ；X1(2)=Y(4)=4 ,因此第二个交换 为 so2 =(2,4) ,作用到粒子的位置 X1 后得 X2=X1+ so2 =1 ,4,2,5,3,1+(2,4)=1 ,5,2,4,3,1=Y ,)=Y ,所以位置 X 与位置 Y 相减后得到一组置换序列,即 X-Y=(1,3),(2,4) 。(6) 粒子速度与速度的加法操作 粒子速度与速度的加法操作为两个置换序列的合并,结果为一个新的置换 序列,即一个新的速度。例如：速度 V1=(1,3

31、),(2,4),V2=(2,3),(5,4),相加后得 V=V1+V2=(1,3),(2,4),(2,3),(5,4)。(7) 实数与粒子速度的乘法操作实数 c 为(0, 1 )的任意实数, 设速度 v 为 k 个置换序列, 则乘法操作为对速 度置换序列进行截取，使得新的速度的置换序列长度为|c 乂| (c &取整)。例如： 速度 V=(2,3),(1,3),(4,5),(5,2),k=4,若 c=0.78,贝U c&=3.12 , |c =3 ,相乘后速度为 c刃=(2,3),(1,3),(4,5)。3.2 公式更新粒子的速度、 位置及其各种操作重新定义后， 离散粒子群算法的

32、速度更新公 式表示如下：k 1kk kk k3.2)Vik 1wVikc1r1(PikXik)c2r2(PgkXik )XiXik Vi k 1(3.3)其中，cl、c2与基本PSO算法中定义相同，仍为加速常数，在02之间取值，r1、r2为(0,1) 上均匀分布的两个相互独立的随机数；为两交换序的合并算子，表示速度与速度的加法操作； 表示粒子位置与位置的减法操作； 表示粒子位置与速度的 加法操作。3.3 基于 k-means 的改进措施 具有良好多样性的粒子群能增加粒子在迭代中获得的有效信息量， 这不仅能 扩大粒子在解空间内的搜索范围， 而且在算法陷入局部最优时， 有助于粒子逃离 局部最优区域

33、，避免PSO算法陷入局部最优的境地。在 PSO算法中，粒子利用 自身信息、 个体极值信息和全局极值信息， 指导自我的搜索方向： 个体极值和全 局极值信息使粒子能够迅速地集中于全局极值所在的区域； 个体信息使粒子能够 根据自身的信息避免陷入局部最优化。 这一机制下，PSO算法具有较高的搜索效 率和较快的收敛速度，但是粒子在搜索中会过分依赖粒子群提供的极值信息(无论是个体极值信息，还是全局极值信息 ) ，从而导致粒子群更易趋于同质化，减 少了粒子能够获得的有效信息量，降低了粒子逃离局部最优的可能性。 本文使用聚类算法对粒子的历史最优位置进行聚类分析， 利用聚类后形成的类中 心 ，替代式(3.2)

34、中个体的历史最优位置， 避免粒子在搜索中因为过多极值信息 的影响而快速同质化。通过这一改进措施，粒子首先利用其他粒子提供的信息， 确定粒子群中所有粒子在解空间内的相对位置， 实现粒子之间的信息交换； 其次， 根据该粒子所在类的中心点提供的信息， 更新粒子的速度向量， 从而加强算法对 该类所在区域的局部搜索能力； 最后， 从整个粒子群的角度看， 由于各粒子的搜 索范围都集中于聚类所形成的局部区域内， 可以维持粒子之间的个体差异， 粒子 群能保持较好的多样性。3.3.1 k-Means 算法k-Means 聚类算法属于聚类分析方法中一种基本的且应用最广的划分方法， 是一种在无类标号数据中发现簇和簇

35、中心的方法。该算法的基本思想是：给定n个数据对象和要生成的簇的数目k,随机选取 k 个对象作为初始的 k 个聚类中心， 然后计算剩余各个样本到每一个聚类中心的 距离，把该样本归到离它最近的那个聚类中心所在的类， 对调整后的新类使用平 均值的方法计算新的聚类中心， 如果相邻两次的聚类中心没有任何变化， 说明样 本调整结束且聚类平均误差准则函数已经收敛。 本算法在每次迭代中都要考察每 个样本的分类是否正确，若不正确，就要调整，在全部样本调整完后，再修改聚 类中心，进入下一次迭代。如果在一次迭代算法中，所有的样本被正确分类，则 不会有调整， 聚类中心也不会有任何变化。 在算法迭代的过程中聚类平均误差

36、准 则函数的值在不断减小，最终收敛至一个固定的值。因此， k-Means 算法可以描述如下： 输入：聚类个数 k， n 个数据对象。 输出：满足方差最小标准的 k 个聚类。 处理流程：（1）从 n 个数据对象任意选择 k 个对象作为初始聚类中心；（2）根据每个聚类对象的中心对象，计算每个对象与这些中心对象的距离；并 根据最小距离重新对相应对象进行划分；（3）重新计算每个有变化聚类的中心对象。（4）循环（2） 到（3）直到每个聚类不再发生变化为止；k-Means 算法接受输入量 k ，然后将 n 个数据对象划分为 k 个聚类以便 使得所获得的聚类满足： 同一聚类中的对象相似度较高， 而不同聚类中

37、的对象相 似度较小。即k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间 尽可能的分开。 其中聚类相似度是利用各聚类中对象的均值所获得一个 “中心对 象”（引力中心）来进行计算的。K-Means 算法的工作过程说明如下： 首先从 n 个数据对象任意选择 k 个 对象作为初始聚类中心； 然后对于所剩下的其它对象， 则根据它们与这些聚类 中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的） 聚类；再计算每个新聚类的聚类中心（该聚类中所有对象的均值）；不断重 复以上过程直到标准测度函数开始收敛为止。 一般都采用均方差作为标准测度函 数。3.3.2 基于 k-Means 的改

38、进粒子群算法PSO算法在迭代中使用了两个不同的粒子群： 各粒子的历史最优位置组成的 粒子群 1；各粒子在迭代中动态变化的粒子群 2。粒子群 2 在搜索的过程中是对 整个解空间进行的随机搜索， 在每次迭代中其变化的速度较快， 而且其变化后的 粒子并不一定代表较好的结果， 故其提供的信息对其他粒子而言并不具有很好的 指导意义； 相反，粒子群 1 在迭代过程中相对稳定， 而且具有的信息往往能够代 表粒子在解空间各局部区域的优质信息， 为其他粒子提供了较好的指导信息。 因此，我们选择对粒子群1进行聚类分析。综上，基于k-means的改进PSO算法的 速度和位置向量更新方式为：3.4)XiXik Vik

39、 13.5)Vik 1 wVikc1r1 (cluster (Pi k ) Xik) c2r2(Pgk Xik)其中，clusteMRk）表示对粒子历代最优解聚类后粒子 Xi所属类的代表对象，其 他参数的含义与基本PSO算法的含义相同。3.4 贪心算法产生初始种群由于旅行商问题为一个循环回路，所以起始城市可以为任意的一个城市。本文采用贪心算法的思想， 随机选择一个城市作为出发城市， 并始终选择距离当 前城市最近的城市作为下一个遍历城市， 直到所有城市均被遍历后直接连接到出 发城市即可。至此，可以利用这个贪心算法得到近似最优循环序列，产生一定规模的初 始种群。这样产生的初始种群全局最优值已经比较

40、接近问题的解， 因此可以节省 搜索时间，提高算法收敛速度。3.5 两个种群同时寻优生物界中少数优良个体进行交叉，有利于产生优良的后代，并保证了父代 优良品性的繁衍， 符合生物界优胜劣汰的进化机制， 因此， 交叉产生的个体最优 有利于种群的进化。 本文根据这一生物界的繁衍规律， 提出两个种群同时寻优的 机制，即种群内部独立进行 PSO进化，种群个体最优之间以一定概率进行交叉。 两个种群同时寻优可以减小算法陷入局部最优的概率， 种群间个体最优的交叉能 够增强两种群间以及粒子间的信息共享， 及时传递最优值信息， 提高粒子向更好 解进化的速度。3.6改进的PSO算法求解TSP流程如下：Step1 ：用

41、贪婪算法产生两个初始种群 A 群和 B 群，随机产生两个基本交 换序作为两个种群的初始速度， 每个粒子位置向量的每一维随机取 0,1 之间的 实数，设定粒子群算法的参数w, cl, c2;Step2:计算粒子适应度，确定个体极值pbest和全局极值gbest;Step3 :使用k-Means对粒子的历史最优解进行聚类分析，确定每个粒子所 在的类以及类的中心点山血仆。Step4:以一定概率将A群粒子的个体最优与B群粒子的个体最优进行交叉， 产生新的个体最优；Step5 :为每个粒子按照式（3.4）和式（3.5）确定新的速度向量和下一代的位 置向量，并产生两个新的全局最优。Step6 :对新形成的

42、粒子群按照Step2的方法确定各粒子代表的可行解的路 径长度，更新粒子个体的历史最优位置和粒子群的全局最优解。Step7 :如未满足终止条件（一个种群两次进化适应度之差小于最小误差），则返回step3。改进算法的流程图如图2所示:NU'fbi鎳東图2改进粒子群算法流程图4实验结果及分析为了检验算法的有效性，本文选用Oliver30作为实验例子，并与基本 PSO算法，遗传算法进行比较。目前已知Oliver30问题的最好解为423.7406，巡回路 径为：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

43、12-13-4-5-6 。图3 Oliver30 问题优化结果采用Microsoft Visual Studio 2005为编程工具，实验环境为Intel(R)Core(TM) i3,2.13GHz CPU,2G内存，Windows Vista 系统。为便于比较，将该改 进PSOT法与基本PSOT法、遗传算法分别连续进行30次实验，对其结果进行比较 分析。几种算法中，种群的粒子数均为100。粒子群算法中惯性权重 呗1. 4线性 递减到0.5，加速常数3= C2=1.2,K-means聚类数为5,最大迭代次数1000。遗传 算法交叉概率Pc=0.2，变异概率Pm=05实验结果如表1所示，得到的最

44、优结果 巡回路径如图3所示，其巡回路径与目前已知最好解一致。表1 Oliver30实验结果比较算法平均值最好解最差解收敛率平均迭代 次数基本PSO457.6632435.9918480.14520.00遗传算法425.6905423.7406429.487625.37%735.40改进PSO424.7926423.7406425.693174.59%583.00表1中，收敛率是30次实验中，算法收敛到最优值423.7406的次数与实验 次数30之比。由表中数据可知，改进的 PSO算法最优解为423.7406，与当前 Oliver30问题的最优解一致，基本 PSO算法最优解为435.9918，无法收敛到当 前最优解，遗传算法虽然也能收敛到当前最优解，但其收敛率25.37%和收敛速度远不如改进的PSO算法的收敛率74.59%和收敛速度。综上所述，用改进的PSO 算法求解T