基于混合粒子群算法TSP搜索算法.ppt

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