粒子群论文PPTPPT.ppt

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