基于混合粒子群算法求解TSP问题

2016-09-07何建军谢日华何汶俊成都理工大学信息科学与技术学院610059

电子测试 2016年16期

侯颖，何建军，米阁，谢日华，何汶俊（成都理工大学信息科学与技术学院，610059）

基于混合粒子群算法求解TSP问题

侯颖，何建军，米阁，谢日华，何汶俊
（成都理工大学信息科学与技术学院，610059）

遗传算法是研究TSP问题中最为广泛的一种算法，它具有全局搜索的能力。而粒子群算法收敛速度较快，但容易造成局部最优的情况。本文基于遗传算法的交叉变异设计了混合粒子群算法，通过对TSP问题求解分析，证实该方法提高了标准粒子群的搜索能力，获得了较高的收敛速度和近似最优解。

旅行商问题；遗传算法；粒子群算法；混合粒子群算法

1　基本算法原理简介

1.1遗传算法概述

遗传算法的构成要素：染色体编码方法：TSP问题中主要采用符号编码；个体适应度评价：遗传算法中使用适应度函数评估个体的适应性；遗传算子：选择算子—比例选择算子、交叉运算—部分映射杂交、变异运算—变异算子或均匀变异算子；基本遗传算法的运行参数：NIND：群体大小、MAXGEN：遗传运算的终止进化迭代数、：交叉概率、：变异概率。

1.2粒子群算法概述

在实际生物中，群居种群共同进行觅食、御敌，这种行为就是我们所说的群体智能。学者们通过对自然界中鸟群活动的模拟，建立了粒子群优化算法。