基于PSO的TSP问题的研究,指导老师：叶茂发 答 辩 人：胡 涛 专 业：计算机科学与技术,基于PSO的TSP问题的研究,引 言,研究背景： 蚁群算法被应用到解决TSP问题，通过信息素的不断更新最终收敛于最优解，但由于初级阶段的信息素缺乏，面对庞大数据时收敛速度过慢，其他诸如遗传算法、免疫算法都存在一定的局限性。 本文方法： 利用改进后的粒子群算法来求解TSP问题,实验通过引进交换子和交换序使得PSO算法可以解决离散的TSP问题，展现其实现容易、精度高、收敛快的特点。,TSP问题,定义： 有n个城市，一个旅行商从某个 城市出发，遍历所有城市后回到出发点，求一条经历所有城市且仅一次的最短遍历路径。,重要特点：离散型问题,粒子群算法,标准PSO算法： 粒子群算法（简称PSO）是源于对鸟群觅食过程中的迁徙和群居的模拟，在粒子群算法中，个体被看着是在D维搜索空间中没有重量和体积的粒子，并以一定的速度飞行。,改进的粒子群算法,对于TSP问题，标准粒子群算法只能解决连续性的问题，求解离散性问题必须将标准粒子群算法改进，引入交换子和交换序以后就可以用粒子群算法处理TSP问题了。,定义一：设n个节点的TSP解序列 ，表示该问题的行走路径，定义交换子 为交换解中的 。 例如：,定义二：一个或多个交换子的有序序列为一个交换序，记为 ，其中是 交换序子，它们满足结合性。,改进后粒子群算法步骤：,1）初始化位置和交换序； 2）检查循环条件，若不满足转5）； 3）计算交换序； 4）根据适应度更新、和每一个粒子的状态,转步骤2）； 5）显示结果。,TSP实验仿真,实验结果:,总 结,本文通过引入交换子和交换序，使粒子群算法不仅可以解决TSP问题，还可以用来解决很多的离散性问题。 优点：实现容易、精度高、收敛快 缺点：易陷入局部最优 改进：引入k-means算法或者贪心算法对初始解优化,