自适应混合粒子群优化算法求解大规模旅行商问题  

SOLVING LARGE-SCALE TSP WITH ADAPTIVE HYBRID PSO

作　　者：张江维[1] 

机构地区：[1]许昌学院国际教育学院,河南许昌461000

出　　处：《计算机应用与软件》2015年第12期265-269,共5页Computer Applications and Software

基　　金：河南省基础与前沿技术研究计划项目(132300410349)

摘　　要：基于随机搜索策略的改进增强型自探索粒子群优化算法难于获得大规模旅行商问题的高质量近似解。为此,引入变异和利用进化过程信息缩减问题规模等机制,提出自适应混合粒子群优化算法。进化搜索分多批次自适应进行,每个批次包括两个阶段。第一阶段,多次搜索获得多个不同的局部最优解,并记录于周游边结构中。第二阶段,学习记录的信息,获得多个关键边序列段,每个段归约为一个整体,以此重新初始化种群,并在其基础上进行下个批次的进化搜索。上述过程反复进行,直到在某第一阶段多次进化中都收敛于同一解为止。实验结果对比分析表明该算法能够获得比同类算法更高质量的近似解。The improvement enhanced self-exploration particle swarm optimisation algorithm based on stochastic search strategy can hardly achieve the high-quality approximate solution of the large-scale traveling salesman problem（ TSP）. For this reason,the paper proposes a selfadaptive hybrid PSO algorithm（ SAHPSO） by introducing the mechanisms of mutation and using evolution process information to cut down the problem scale. The evolution search is performed adaptively in multiple processes,each process includes two stages. In first stage,it records various local optimal solutions gotten by multiple searches to a traveling edge structure. In second stage,it obtains more key edge sequence segments based on learning the recorded information,and each segment is reduced to an integer used for initialising the population once again,and then starts the next evolution searching process based on it. The above operation will be going on repeatedly until the multiple evolutions in a certain process all converge to one solution. Comparative analysis of experimental results shows that the SAHPSO can obtain the approximate solution with higher quality than similar algorithms.

关 键 词：自适应 混合算法 粒子群优化算法 大规模旅行商问题 

分 类 号：TP31[自动化与计算机技术—计算机软件与理论]