摘要
本文研究了求解旅行商问题的粒子群算法。针对标准粒子群算法在求解旅行商问题过程中容易出现早熟和停滞现象的缺点,提出了一种改进的粒子群算法。首先,在初始种群的选取过程中,利用改进的贪婪策略直接获得具有较高性能的初始种群以提高算法的搜索效率。其次,通过引入次优吸引子,使粒子在搜索过程中可以更加充分地利用群体的信息来提高自身的性能,有效抑制收敛过程中的停滞现象,提高算法的搜索能力。最后为了验证所提出的方法的有效性和可行性,对TSPLIB标准库中的多个实例进行了测试,并给出了数值结果。
This paper deals with the traveling salesman problem with the particle swarm optimization algorithm.To overcome the disadvantages of premature convergence and stagnation phenomenon of the standard particle swarm optimization algorithm,this paper proposes an improved particle swarm optimization algorithm for the traveling salesman problem.Firstly,in the selection of an initial population,a modified greedy strategy is exploited to directly obtain a population of high-performance initial solutions so as to improve the search efficiency of the algorithm.Secondly,through introducing sub-optimal attractor,the particles in the search process can make full use of the population information to enhance their own performance,so as to effectively inhibit stagnation in the convergence process,and improve the search ability of the algorithm.Finally,in order to verify the effectiveness and feasibility of the proposed method,the instances in the standard library TSPLIB have been tested and the numerical results are given.
出处
《运筹与管理》
CSCD
北大核心
2010年第5期20-26,共7页
Operations Research and Management Science
基金
国家自然科学基金资助项目(10571018
70871015)
国家高技术研究发展计划(863计划)资助项目(2008AA04Z107)
关键词
运筹学
粒子群优化
旅行商问题
贪婪策略
operations research
particle swarm optimization
traveling salesman problem
greedy strategy
