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

第五届“挑战杯”广西大学生课外学术科技作品申报书序号： 编码： 第五届“挑战杯”广西大学生课外学术科技作品竞赛作品申报书作品名称：基于k-means的改进粒子群算法求解TSP问题 学校全称： 河池学院 申报者姓名（集体名称）： 陈国鸿 类别：自然科学类学术论文 哲学社会科学类社会调查报告和学术论文 科技发明制作A类 科技发明制作B类说 明1申报者应认真阅读此说明各项内容后按要求详细填写。2申报者在填写申报作品情况时只需根据个人项目或集体项目填写A1或A2表，根据作品类别（自然科学类学术论文、哲学社会科学类社会调查报告和学术论文、科技发明制作）分别填写B1、B2或B3表。所有申报者可根据情况填写C表。3表内项目填写时一律用钢笔或打印，字迹要端正、清楚，此申报书可复制。4序号、编码由第五届“挑战杯”广西大学生课外学术科技作品竞赛组委会填写。5学术论文、社会调查报告及所附的有关材料必须是中文（若是外文，请附中文版），请以四号楷体打印在A4纸上，附于申报书后，字数在8000字左右（文章版面尺寸14.522cm）。6参赛作品（数量参照通知）各一式叁份分别按组委会规定的时间报至组委会秘书处。7作品申报书须按要求由各校竞赛组织协调机构统一寄送。8其他参赛事宜请向本校竞赛组织协调机构咨询。9寄送地址：南宁市古城路4号共青团广西区委学校部。联 系 人： 廖梅宣联系电话：办公手机）传 真：政编码： 530022A1申报者情况（个人项目）说明：1必须由申报者本人按要求填写，申报者情况栏内必须填写 个人作品的第一作者（承担申报作品60%以上的工作者）。 2本表中的学籍管理部门签章视为对申报者情况的确认。姓 名 陈国鸿性别 男出生年月 1986年7月申报者情况学校全称 河池学院专 业 计算机科学与技术现学历 本科年级 大四学制 4 年入学时间 2007年9月作品全称基于k-means的改进粒子群算法求解TSP问题毕业论文题目改进粒子群算法求解TSP问题通讯地址广西宜州市龙江路42号河池学院计信系邮政编码 546300单位电话07783144832常住地通讯地址广西宜州市龙江路42号河池学院计信系邮政编码 546300住宅电话07783144832合作者情况姓 名性别年龄学历所在单位资 格 认定学校学籍管理部门意见是否为2011年7月1日前正式注册在校的全日制非成人教育、非在职的各类高等院校学生（含专科生、本科生和研究生）。是 否若是，其学号为： 2007107201 （签章） 2011年4月23日院系负责人或导师意见本作品是否为课外学术科技或社会实践活动成果是 否 负责人签名： 2011年4月25日B1申报作品情况（自然科学类学术论文）说明：1必须由申报者本人填写。2本部分中科研管理部门签章视为对申报者所填内容的确认。3作品分类请按作品学术方向或所涉及的主要学科领域填写。4硕士研究生、博士研究生作品不在此列。作品全称 改进粒子群算法求解TSP问题作品分类（B） A机械与控制（包括机械、仪器仪表、自动化控 制、工程、交通、建筑等） B信息技术（包括计算机、电信、通讯、电子等） C数理（包括数学、物理、地球与空间科学等） D生命科学（包括生物、农学、药学、医学、健 康、卫生、食品等） E能源化工（包括能源、材料、石油、化学、化 工、生态、环保等）作品撰写的目的和基本思路 旅行商问题 (TSP)又名货郎担问题，是一个典型的NP难题。其数学描述非常简单，但却无法找到一个确定的算法在多项式时间内求解TSP 问题，另一方面很多研究领域出现的复杂优化问题可以被抽象概括为TSP 问题加以求解，因此找到能够有效解决TSP 问题的方法,在理论上和实际应用中都很有价值。 本文对基本PSO算法中粒子的位置、速度以及操作进行了重新定义，使粒子群算法适合于求解TSP问题，并采用贪心算法的思想每一步都取局部最优。这样产生的初始种群全局最优值已经比较接近问题的解，因此可以节省搜索时间，提高算法收敛速度。针对粒子群算法易陷入局部最优的缺陷，引入了适合于求解TSP问题的基于k-means的改进措施，对粒子群进行聚类分析，实现了粒子之间的信息交换，扩大了粒子的搜索空间，克服了PSO算法易陷入局部最优的缺陷。两个种群同时寻优，种群内部独立进行PSO进化，种群个体最优之间以一定概率进行交叉。两个种群同时寻优可以减小算法陷入局部最优的概率，种群间个体最优的交叉能够增强两种群间以及粒子间的信息共享，及时传递最优值信息，提高粒子向更好解进化的速度。最后本文对30点TSP问题进行仿真测试，试验表明改进后的粒子群算法能有效地求解TSP问题。作品的科学性、先进性及独特之处 粒子群优化（简称PSO）算法在多维连续优化问题的应用中取得了较好的效果，但在旅行商（简称TSP问题）等组合优化问题中的应用则相对较少。为使粒子群算法适合于求解TSP问题本文对基本PSO算法中粒子的位置、速度以及操作进行了重新定义。初始种群的产生借鉴贪心算法的思想，每一步都取局部最优。这样产生的初始种群全局最优值已经比较接近问题的解，因此可以节省搜索时间，提高算法收敛速度。针对粒子群算法易陷入局部最优的缺陷， 提出了适合旅行商问题的基于k-means的改进措施。采用k-means对粒子群进行聚类分析，实现了粒子之间的信息交换，扩大了粒子的搜索空间，避免了算法陷入局部最优。两个种群同时寻优，种群内部独立进行PSO进化，种群个体最优之间以一定概率进行交叉，减小算法陷入局部最优的概率，种群间个体最优的交叉能够增强两种群间以及粒子间的信息共享，及时传递最优值信息，提高粒子向更好解进化的速度。作品的实际应用价值和现实意义TSP问题是一种典型的组合优化问题，是一种用来验证算法有效性的典型算例。由于TSP最优解的求解代价是指数级的，因此该问题吸引了生物、物理、数学、运筹学、人工智能等诸多领域的研究者，对其近似解的研究一直是算法设计的一个重要课题，TSP问题的有效解决对推动整个组合优化领域的发展有重大的影响。作为一类组合优化问题的代表，TSP问题在实际工程中有许多应用，如计算机联网、物流等行业中的车辆调度优化、电力系统配电网络重构、城市管道铺设优化、交通导航、电气布线、电子地图、VLSI单元布局、X射线结晶学问题等。PSO算法在连续空间优化问题上已经取得了很好的效果，但是将其应用在TSP等离散优化问题中还是一种尝试。因此用改进的PSO算法有效的求解TSP问题，在整个组合优化领域和实际工程中都有着重要影响和实际意义。学术论文文摘粒子群优化（简称PSO）算法在多维连续优化问题的应用中取得了较好的效果， 但在旅行商（简称TSP问题）等组合优化问题中的应用则相对较少。为使粒子群算法适合于求解TSP问题本文对基本PSO算法中粒子的位置、速度以及操作进行了重新定义。初始种群的产生借鉴贪心算法（简称GA）的思想，每一步都取局部最优。这样产生的初始种群全局最优值已经比较接近问题的解，因此可以节省搜索时间，提高算法收敛速度。针对粒子群算法易陷入局部最优的缺陷， 提出了适合旅行商问题的基于k-means的改进措施。采用k-means对粒子群进行聚类分析，实现了粒子之间的信息交换，扩大了粒子的搜索空间，避免了算法陷入局部最优。两个种群同时寻优，种群内部独立进行PSO进化，种群个体最优之间以一定概率进行交叉，减小算法陷入局部最优的概率，种群间个体最优的交叉能够增强两种群间以及粒子间的信息共享，及时传递最优值信息，提高粒子向更好解进化的速度。实验证明，改进后的粒子群算法能有效地求解TSP问题。作品在何时、何地、何种机构举行的会议上或报刊上发表登载及所获奖励1.已发表相似论文：易云飞，陈国鸿. 一种基于收缩因子的改进粒子群算法J.软件导刊.2009，9(9)：59-602.一种基于收缩因子的改进粒子群算法获第四届“挑战杯”广西大学生课外学术科技作品竞赛二等奖。3.本次申报的论文已投往全国中文核心期刊计算机工程与应用，目前正在审稿。鉴定结果请提供对于理解、审查、评价所申报作品具有参考价值的现有技术及技术文献的检索目录申报材料清单（申报论文一篇，相关资料名称及数量）申报论文改进粒子群算法求解TSP问题一篇。科研管理部门签章 （签章） 年 月 日C当前国内外同类课题研究水平概述说明：1申报者可根据作品类别和情况填写。 2填写此栏有助于评审。 最初的PSO 是用来解决连续空间问题的, 为了适合求解TSP 问题, 人们对算法进行了各种改进。主要可以分为以下几个方面:1.重新定义PSO 的运算符号和规则：黄岚等引入交换子和交换序的概念, 构造一种特殊的PSO 用于求解TSP。庞巍采用模糊矩阵技术, 并重新定义其更新公式。Clerc重新定义了运算符号和规则, 并用于求解TSP。李盘荣针对收敛速度不够快的缺陷, 提出利用量子粒子群优化算法QPSO。钟一文等, 在重新定义运算速度、规则和运动方程的基础上,为防止算法的早熟停滞现象, 提出用扰动速度来增加粒子群的多样性, 为提高算法的求精能力, 设计了一种高效的近邻搜索算子来提高粒子的适应值。郭文忠等, 为了克服PSO 在求解离散问题所具有的计算时间长和容易陷入停滞状态等问题, 基于“簇”思想, 对粒子间距离进行重新定义并给出了相应的动态邻域PSO 算法。通过引入模糊技术, 给出了一种惯性权重的模糊自适应调整模型及其相应的粒子群优化算法。王文峰等, 在重新定义了PSO 的速度和位置公式的基础上,针对易早熟, 收敛慢的缺陷, 建立局部极小区域的扰动机制, 结合局部搜索算法PSEC, 提出了一种混合离散粒子群算法HDPSO。2.混合粒子群算法。高尚等结合遗传算法、蚁群算法和模拟退火算法的思想, 提出用混合粒子群算法来求解CTSP。谭皓等, 提出一种结合PSO 和蚁群算法特点的混合算法。陈曦把免疫系统的免疫信息处理机制引入到粒子群优化算法中, 设计了免疫粒子群优化算法。3.其他改进的PSO。 王翠茹为了更有利于粒子发现问题的全局最优解, 在算法中引入了更符合自然界生物学习规律的速度变异机制和粒子自探索机制。莫愿斌提出了粒子群复形(CPSO)算法。对TSP 解序列提出5 种运算, 得到能求解TSP 的PSO 算法。D推荐者情况及对作品的说明说明：1由推荐者本人填写。2推荐者须具有高级专业技术职称，并与申报作品相同或相关领域的专家学者或专业技术人员（教研组集体）推荐亦可。 3推荐者填写此部分，即视为同意推荐。 4推荐者所在单位签章仅被视为对推荐者身份的确认。推荐者情况姓 名黄星寿性别男年龄47职称副教授工作单位河池学院计算机与信息科学系通讯地址广西宜州市龙江路42号河池学院计信系邮政编码546300单位电宅电荐者所在单位签章（签章） 年 月 日请对申报者申报情况真实性做出阐述申报者所呈交的作品是在指导教师的指导下独立进行研究所取得的研究成果。请对作品的意义、技术水平、适用范围及推广前景做出您的评价该作品针对粒子群算法易陷入局部最优的缺陷，引入了适合于求解TSP问题的基于k-means的改进措施，对粒子群进行聚类分析，实现了粒子之间的信息交换，扩大了粒子的搜索空间，克服了PSO算法易陷入局部最优的缺陷。实验结果表明改进后的粒子群算法能有效地求解TSP问题。其它说明推荐者情况姓 名周永权性别男年龄49职称教授工作单位河池学院计算机与信息科学系（兼职教授）通讯地址广西宜州市龙江路42号河池学院计信系邮政编码546300单位电宅电荐者所在单位签章（签章） 年 月 日请对申报者申报情况的真实性做出阐述该作品是在指导教师易云飞的指导下独立进行研究所取得的研究成果，作品中的实验数据是真实的。请对作品的意义、技术水平、适用范围及推广前景做出评价该作品地提出了一种改进的粒子群算法，并将该算法用于求解TSP问题。所提出的改进算法提高了算法的有效性；既适合科学研究,又特别适合工程应用；可广泛应用于函数寻优、神经网络训练、模式分类、模糊系统控制以及其它的应用领域。仿真实验表明改进后的算法是可行、有效的。其它说明学校组织协调机构确认并签章（签章） 年 月 日校主管领导或校主管部门确认并签章我单位经自查，承诺该作品符合挑战杯申报作品的要求，接受竞赛组委会抽查。（签章）年 月 日各省（区、市）评审委员会初评意见（签章）年 月 日各省（区、市）组织协调委员会审定意见 团 委 科 协 教 育 厅 学 联（签章） （签章） （签章） （签章）年 月 日E组织委员会秘书处资格和形式审查意见组委会秘书处资格审查意见 审查人（签名） 年 月 日组委会秘书处形式审查意见 审查人（签名） 年 月 日组委会秘书处审查结果合格 不合格 负责人（签名） 年 月 日F1评审委员会预审意见粘贴处F2评审委员会终审意见粘贴处 (正文打印页)基于k-means的改进粒子群算法求解TSP问题陈国鸿(河池学院 计算机与信息科学系,广西 宜州546300)摘 要 粒子群优化（简称PSO）算法在多维连续优化问题的应用中取得了较好的效果， 但在旅行商（简称TSP问题）等组合优化问题中的应用则相对较少。为使粒子群算法适合于求解TSP问题本文对基本PSO算法中粒子的位置、速度以及操作进行了重新定义。初始种群的产生借鉴贪心算法的思想，每一步都取局部最优。这样产生的初始种群全局最优值已经比较接近问题的解，因此可以节省搜索时间，提高算法收敛速度。针对粒子群算法易陷入局部最优的缺陷， 提出了适合旅行商问题的基于k-means的改进措施。采用k-means对粒子群进行聚类分析， 实现了粒子之间的信息交换， 扩大了粒子的搜索空间，避免了算法陷入局部最优。两个种群同时寻优，种群内部独立进行PSO进化，种群个体最优之间以一定概率进行交叉，减小算法陷入局部最优的概率，种群间个体最优的交叉能够增强两种群间以及粒子间的信息共享，及时传递最优值信息，提高粒子向更好解进化的速度。实验证明，改进后的粒子群算法能有效地求解TSP问题。关键词旅行商问题；粒子群算法；K-means；贪心算法0 引言旅行商问题 (Traveling Salesman Problem，简称TSP)又名货郎担问题，是一个典型的NP 完全问题。原型描述：给定N个城市和两两城市之见的距离，求一条访问各个城市且仅访问一次的最短路线。虽然其数学描述非常简单，但却无法找到一个确定的算法在多项式时间内求解TSP 问题，另一方面很多研究领域出现的复杂优化问题可以被抽象概括为TSP 问题加以求解，因此找到能够有效解决TSP 问题的方法,在理论上和实际应用中都很有价值。粒子群算法（Particle Swarm Optimization，简称PSO）算法最早是在1995年由美国社会心理学家James Kennedy和电气工程师Russell Eberhart 共同提出的一种全局优化算法，该算法的基本思想来源于对鸟群简化社会模型的研究及行为模拟，其中的每个个体充分利用群体的与自身的智能，不断地调整学习，最终得到满意解。该算法在多维连续优化问题的运用中取得了较好的效果，但在TSP 等组合优化问题中的应用则相对较少。本文对基本PSO算法中粒子的位置、速度以及操作进行了重新定义，使粒子群算法适合于求解TSP问题，并采用贪心算法的思想每一步都取局部最优。这样产生的初始种群全局最优值已经比较接近问题的解，因此可以节省搜索时间，提高算法收敛速度。针对粒子群算法易陷入局部最优的缺陷，引入了适合于求解TSP问题的基于k-means的改进措施，对粒子群进行聚类分析， 实现了粒子之间的信息交换， 扩大了粒子的搜索空间，克服了PSO算法易陷入局部最优的缺陷。两个种群同时寻优，种群内部独立进行PSO进化，种群个体最优之间以一定概率进行交叉。两个种群同时寻优可以减小算法陷入局部最优的概率，种群间个体最优的交叉能够增强两种群间以及粒子间的信息共享，及时传递最优值信息，提高粒子向更好解进化的速度。最后本文对30点TSP问题进行仿真测试，试验表明改进后的粒子群算法能有效地求解TSP问题。1 TSP问题 TSP是运筹学、图轮和组合优化中的NP难问题。问题的具体如下：给定N个城市及两两城市之间的距离，求一条经过各城市一次且仅一次的最短路线。其图论描述为：给定图G=（V，A），其中V为顶点集，A为各顶点相互连接组成的弧集，已知各顶点间连接距离，要求确定一条长度最短的Hamilton回路，即遍历所有顶点一次且仅一次的最短回路。设为城市i 与j 之间的距离，即弧( i,j)的长度。引入决策变量：Xij = (1.1)则TSP的目标函数为 (1.2) TSP 问题描述非常简单，但最优化求解很困难，若用穷举法搜索，则要考虑所有可能情况，并两两对比，找出最优,其算法复杂性呈指数增长, 即所谓的“组合爆炸”。所以，寻求和研究TSP 的有效启发式算法,是问题的关键。2 基本PSO算法PSO算法主要模拟鸟群飞行的觅食行为，通过鸟群的集体协作达到寻优目的。在PSO算法中，每个粒子利用自身的历史最优位置和整个粒子群的全局最优解提供的信息，在解空间内不断飞行， 实现寻找最优解的目的。2.1 基本PSO算法的数学描述如下：设搜索空间为N维，总粒子数为Num，第i个粒子的位置向量=()，第i个粒子的速度向量是=()， 第i个粒子在“飞行”中的历史最优位置是=()，表示目前为止在整个粒子群中发现的全局最优粒子；粒子按如下方式飞行：(t+1) = w (t) + c1 rand1 ( ) (t)-(t) + c2 rand2 ( ) (t)-(t) (2.1) (t +1) = (t) + (t +1) (2.2)其中，下标“j”表示第j维，t为飞行的次数；w为惯性权重，使粒子保持运动惯性，控制前一速度对当前速度的影响，较大的w适于对解空间进行大规模探查，较小的 w 适合于进行小范围开挖；c1，c2 为加速常数，通常在间取值，c1调节粒子飞向自身最好位置方向的步长，c2调节粒子向全局最好位置飞行步长；rand1( )和 rand2 ( )是0,1 之间相互独立的随机数。粒子的位置向量中各维变化范围为,，速度变化范围为,，迭代中若位置和速度超过边界范围则取边界值。PSO算法通过粒子在解空间内不断地变化速度向量来改变位置，最终找到最优解。图1 粒子移动原理图 图1.粒子移动原理图 2.2 基本粒子群算法的流程如下：Step1：依照初始化过程，对粒子群的随机位置和速度进行初始设定；Step2：计算每个粒子的适应值；Step3：对于每个粒子，将其适应值与所经历过的最好位置的适应值进行比较，若较好，则将其作为当前的最好位置；Step4：对每个粒子，将其适应值与全局所经历的最好位置的适应值进行比较，若较好，则将其作为当前的全局位置；Step5：根据方程(2.1)、(2.2)对粒子的速度和位置进行迭代进化；Step6：循环步骤2-5，直到结束条件为足够好的适应值或达到一个预设最大迭代次数，算法终止。3 改进的粒子群算法求解TSP问题 3.1 定义更新 TSP问题为离散问题，用PSO求解TSP问题需要对基本PSO算法中粒子的位置、速度以及操作进行重新定义： (1)状态空间 TSP问题的结果是要求出具有最短路径的哈密尔顿圈，所以状态空间即为所有位置的集合。 (2)粒子的位置粒子的位置可以定义为一个具有所有节点的哈密尔顿圈，设所有与之间的弧存在，粒子的位置可表示为序列，其中，E为状态空间。(3)粒子的速度 速度定义为粒子位置的变换集，表示一组置换序列的有序列表。可以表示为： （3.1）其中，| v |表示该速度所含交换的数目，式(3.1)表示先交换粒子中、的位置，然后交换、的位置，依此类推。(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，由于X(1)=Y(3)=2,)=2，所以第一个交换为=（1，3），X1=X+=2,41,5,3,2+(1,3)=1,4,2,5,3,1；X1(2)=Y(4)=4，因此第二个交换为=(2,4)，作用到粒子的位置X1后得X2=X1+=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),(2,4),V2=(2,3),(5,4),相加后得V=V1+V2=(1,3),(2,4),(2,3),(5,4)。 (7)实数与粒子速度的乘法操作实数c为(0，1)的任意实数，设速度v为k个置换序列，则乘法操作为对速度置换序列进行截取，使得新的速度的置换序列长度为|ck| (ck取整)。例如：速度V=(2,3),(1,3),(4,5),(5,2),k=4,若c=0.78,则ck=3.12，|ck| =3，相乘后速度为cV=(2,3),(1,3),(4,5)。3.2 公式更新粒子的速度、位置及其各种操作重新定义后，离散粒子群算法的速度更新公式表示如下： （3.2） (3.3)其中，cl、c2与基本PSO算法中定义相同，仍为加速常数，在02之间取值，r1、r2为(0,1)上均匀分布的两个相互独立的随机数；为两交换序的合并算子，表示速度与速度的加法操作；表示粒子位置与位置的减法操作；表示粒子位置与速度的加法操作。3.3 基于k-means的改进措施 具有良好多样性的粒子群能增加粒子在迭代中获得的有效信息量，这不仅能扩大粒子在解空间内的搜索范围，而且在算法陷入局部最优时，有助于粒子逃离局部最优区域，避免PSO 算法陷入局部最优的境地。在 PSO 算法中，粒子利用自身信息、个体极值信息和全局极值信息，指导自我的搜索方向：个体极值和全局极值信息使粒子能够迅速地集中于全局极值所在的区域；个体信息使粒子能够根据自身的信息避免陷入局部最优化。这一机制下，PSO 算法具有较高的搜索效率和较快的收敛速度，但是粒子在搜索中会过分依赖粒子群提供的极值信息(无论是个体极值信息，还是全局极值信息)，从而导致粒子群更易趋于同质化，减少了粒子能够获得的有效信息量，降低了粒子逃离局部最优的可能性。本文使用聚类算法对粒子的历史最优位置进行聚类分析，利用聚类后形成的类中心 ，替代式(3.2)中个体的历史最优位置，避免粒子在搜索中因为过多极值信息的影响而快速同质化。通过这一改进措施，粒子首先利用其他粒子提供的信息，确定粒子群中所有粒子在解空间内的相对位置，实现粒子之间的信息交换；其次，根据该粒子所在类的中心点提供的信息，更新粒子的速度向量，从而加强算法对该类所在区域的局部搜索能力；最后，从整个粒子群的角度看，由于各粒子的搜索范围都集中于聚类所形成的局部区域内，可以维持粒子之间的个体差异，粒子群能保持较好的多样性。3.3.1 k-Means算法 k-Means聚类算法属于聚类分析方法中一种基本的且应用最广的划分方法，是一种在无类标号数据中发现簇和簇中心的方法。 该算法的基本思想是：给定n个数据对象和要生成的簇的数目k，随机选取k个对象作为初始的k个聚类中心，然后计算剩余各个样本到每一个聚类中心的距离，把该样本归到离它最近的那个聚类中心所在的类，对调整后的新类使用平均值的方法计算新的聚类中心，如果相邻两次的聚类中心没有任何变化，说明样本调整结束且聚类平均误差准则函数已经收敛。本算法在每次迭代中都要考察每个样本的分类是否正确，若不正确，就要调整，在全部样本调整完后，再修改聚类中心，进入下一次迭代。如果在一次迭代算法中，所有的样本被正确分类，则不会有调整，聚类中心也不会有任何变化。在算法迭代的过程中聚类平均误差准则函数的值在不断减小，最终收敛至一个固定的值。因此，k-Means算法可以描述如下：输入：聚类个数k，n个数据对象。输出：满足方差最小标准的k个聚类。处理流程： （1）从 n个数据对象任意选择k个对象作为初始聚类中心；（2）根据每个聚类对象的中心对象，计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分；（3）重新计算每个有变化聚类的中心对象。（4）循环(2)到(3)直到每个聚类不再发生变化为止； k-Means 算法接受输入量 k ，然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高，而不同聚类中的对象相似度较小。即k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。其中聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。 K-Means 算法的工作过程说明如下：首先从n个数据对象任意选择 k 个对象作为初始聚类中心；然后对于所剩下的其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；再计算每个新聚类的聚类中心（该聚类中所有对象的均值）；不断重复以上过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数。3.3.2 基于k-Means的改进粒子群算法PSO算法在迭代中使用了两个不同的粒子群：各粒子的历史最优位置组成的粒子群1；各粒子在迭代中动态变化的粒子群2。粒子群2在搜索的过程中是对整个解空间进行的随机搜索，在每次迭代中其变化的速度较快，而且其变化后的粒子并不一定代表较好的结果，故其提供的信息对其他粒子而言并不具有很好的指导意义；相反，粒子群1在迭代过程中相对稳定，而且具有的信息往往能够代表粒子在解空间各局部区域的优质信息，为其他粒子提供了较好的指导信息。因此，我们选择对粒子群1进行聚类分析。综上，基于k-means的改进PSO算法的速度和位置向量更新方式为： （3.4） （3.5）其中，表示对粒子历代最优解聚类后粒子所属类的代表对象，其他参数的含义与基本PSO算法的含义相同。3.4 贪心算法产生初始种群 由于旅行商问题为一个循环回路，所以起始城市可以为任意的一个城市。本文采用贪心算法的思想，随机选择一个城市作为出发城市，并始终选择距离当前城市最近的城市作为下一个遍历城市，直到所有城市均被遍历后直接连接到出发城市即可。 至此，可以利用这个贪心算法得到近似最优循环序列，产生一定规模的初始种群。这样产生的初始种群全局最优值已经比较接近问题的解，因此可以节省搜索时间，提高算法收敛速度。3.5两个种群同时寻优生物界中少数优良个体进行交叉，有利于产生优良的后代，并保证了父代优良品性的繁衍，符合生物界优胜劣汰的进化机制，因此，交叉产生的个体最优有利于种群的进化。本文根据这一生物界的繁衍规律，提出两个种群同时寻优的机制，即种群内部独立进行PSO进化，种群个体最优之间以一定概率进行交叉。两个种群同时寻优可以减小算法陷入局部最优的概率，种群间个体最优的交叉能够增强两种群间以及粒子间的信息共享，及时传递最优值信息，提高粒子向更好解进化的速度。 3.6改进的PSO算法求解TSP流程如下：Step1：用贪婪算法产生两个初始种群A群和B群，随机产生两个基本交换序作为两个种群的初始速度，每个粒子位置向量的每一维随机取0,1 之间的实数，设定粒子群算法的参数w，c1，c2；Step2：计算粒子适应度，确定个体极值pbest和全局极值gbest；Step3：使用k-Means对粒子的历史最优解进行聚类分析，确定每个粒子所在的类以及类的中心点。Step4：以一定概率将A群粒子的个体最优与B群粒子的个体最优进行交叉，产生新的个体最优；Step5：为每个粒子按照式(3.4)和式(3.5)确定新的速度向量和下一代的位置向量，并产生两个新的全局最优。Step6：对新形成的粒子群按照Step2的方法确定各粒子代表的可行解的路径长度，更新粒子个体的历史最优位置和粒子群的全局最优解。Step7：如未满足终止条件(一个种群两次进化适应度之差小于最小误差)，则返回step3。改进算法的流程图如图2所示：图2 改进粒子群算法流程图 4 实验结果及分析 为了检验算法的有效性，本文选用Oliver30作为实验例子，并与基本PSO算法，遗传算法进行比较。目前已知Oliver30问题的最好解为423.7406，巡回路径为：图3 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-12-13-4-5-6。采用Microsoft Visual Studio 2005为编程工具，实验环境为Intel(R) Core(TM) i3,2.13GHz CPU,2GB内存，Windows Vista系统。为便于比较，将该改进PSO算法与基本PSO算法、遗传算法分别连续进行30次实验，对其结果进行比较分析。几种算法中，种群的粒子数均为100。粒子群算法中惯性权重W从14线性递减到0.5，加速常数C1=C2=1.2,K-means聚类数为5，最大迭代次数1000。遗传算法交叉概率Pc=0.2，变异概率Pm=0.5。实验结果如表1所示，得到的最优结果巡回路径如图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算法求解TSP问题有更高效的性能。5 结束语本文在分析基本粒子群