五、结果分析MMATLAB程序 采用混合粒子群算法规划TSPATLAB 路径。各城市初始位置如图 程序
所示。
图 1.城市的初始位置
五、结果分析
图 2.适应度值
五、结果分析
图 3.规划出来的最优路径
THANK YOU .
2和4，变异操作如下所示：
三、解题思路以及步骤
对得到的新个体依然采用保留优秀个体策略，只有当新粒
子适应度值好于旧粒子时才更新粒子。
根据混合粒子群算法原理，在MATLAB中编程实现基于混
合粒子群TSP搜索算法。 1适应度函数，适应度函数计算个体适应值，个体适应值 为路径总长度。 2.粒子初始化，粒子初始化步骤初始化粒子，计算粒子适
公式为：
三、操作
个体通过和个体极值和群体极值交叉来更新，交叉方法采
用整数交叉法。首先选择两个交叉位置，然后把个体和个
体极值或个体和群体极值进行交叉。以上述10个城市为例，
假定随机选取的交叉位置为3和5，个体和极值的编码分别
为操作方法如下：
三、解题思路以及步骤
基于混合粒子群算法的TSP搜索算法
机械工程
夏永强 2016年5月
理论基础 问题描述 解题思路以及步骤 MATLAB程序设计 结果分析
目 录
一、理论基础
标准粒子群算法是通过追随个体极值和群体极值来完成极值寻 优的，虽然操作简单，且能够快速收敛，但是随着迭代次数的不断 增加，在种群收敛集中的同时，各粒子也越来越相似，可能在局部 解周边无法跳出。混合粒子群算法摒弃传统粒子群算法通过跟踪极 通过粒子同个体极值和群体极值的交叉以及粒子自身变异的方式来 搜索最优解。
四、MATLAB程序MMATLAB 程序 ATLAB程序
应度值，并根据适应度值确定个体最优粒子和群体最优粒
子。 从而得到更好的个体。
3.交叉操作，交叉操作把同个体极值和群体极值进行交叉，
四、MATLAB程序MMATLAB 4.变异操作，变异操作对自身进行变异，从而得到更好的 程序 ATLAB程序 个体。
值来更新粒子位置的方法，而是引入了遗传算法的交叉和变异操作，
二、问题描述
旅行商问题（Traveling Salesman Problem，TSP）又译为旅行推 销员问题、货郎担问题，简称为TSP问题，是最基本的路线问题， 该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之
后，最后再回到原点的最小路径成本。最早的旅行商问题的数学规
划是由Dantzig（1959）等人提出。旅行商问题是车辆路线问题 （VRP）的特例，已证明旅行商问题是NP难题。
三、解题思路以及步骤
1.算法流程
基于混合粒子群TSP算法流程图如图所示：
混合粒子群算法流程图
其中，种群初始化模块初始化粒子群种群；适应度值计算模块计算 粒子群个体的适应度值；更新粒子模块根据粒子适应度值更新个体 最优粒子和群体最优粒子；个体最优交叉把个体和个体最优粒子进 行交叉得到最新粒子；群体最优交叉把个体和群体最优粒子进行交 叉得到新粒子；粒子变异是指粒子自身变异得到最新粒子。
产生的新个体若存在重复位置则进行调整，调整方法为用
个体中未包括的城市代替重复包括的城市，如下所示：
对得到的新个体采用保留优秀个体策略，只有当新粒子
适应度值好于旧粒子时才更新粒子。
（4）变异操作
变异采用个体内部两位互换方法，首先随机选取变异位置
pos1和pos2，然后把两个变异位置互换，假设变异位置为
三、解题思路以及步骤
2.算法实现
（1）个体编码
粒子个体编码采用整数编码的方式，每个粒子表示历 经的所有城市顺序，比如当历经的城市数为 10，个体编 码为[94213761085]，表示从城市遍历从9出发，经过 4,2,1,3…最终回到城市9，从而完成TSP遍历。
（2）适应度值
粒子适应度值表示路径长度，第i个粒子的适应度值计算