摘要
为提高粒子群算法求解TSP(Travelling Salesman Problem)问题的性能,在算法搜索初期,将混合蛙跳算法和粒子群算法相融合,针对初始粒子群随意性大、粒子分布不均的问题,利用混合蛙跳算法的分组策略将种群分组,采用改进的蛙跳更新公式优化次优个体,并抽取各层次个体得到新种群,从而提高最优个体的获得速度;在算法后期,引入3重交叉策略和基于疏密性的引导变异操作,解决粒子多样性降低、易陷入局部最优的问题。利用改进算法求解TSP问题,并与其他算法进行对比。结果表明,改进算法是有效的且性能优于其他算法。
In order to improve the performance of particle swarm optimization algorithm for solving travelling salesman problem, the shuffled frog leaping algorithm is merged with particle swarm optimization algorithm in the initial period. Because the initial particles are arbitrary and the distribution is uneven, the particle swarm is carried out by using the grouping strategy of the shuffled frog leaping algorithm. The suboptimal individuals are optimized by the improved frog leaping update formula, and new particle swarm is obtained by extracting individuals at each level, so as to improve the speed of obtaining the optimal individual. In the later period of the algorithm, the triple crossover strategy and guided mutation operation based on density are introduced to solve the problem that the particle diversity reduces gradually and the algorithm is easy to fall into local optimum. The results show that the improved algorithm is effective and superior to other algorithms.
出处
《吉林大学学报（信息科学版）》
CAS
2017年第5期498-506,共9页
Journal of Jilin University（Information Science Edition）
基金
国家自然科学基金资助项目(61374127)
关键词
混合蛙跳算法
粒子群算法
TSP问题
交叉变异
shuffled frog leaping algorithm （ SFLA ）
particle swarm optimization （ PSO ） algorithm
travelling salesman problem （TSP）
crossover and mutation
