基于汉明距离的改进粒子群算法求解旅行商问题

发布时间：2018-11-23 06:52

【摘要】：针对传统粒子群算法不适合求解离散型问题,提出一种基于汉明距离的改进粒子群算法。该算法保留了粒子群算法的基本思想和流程,并基于汉明距离为粒子定义了一种新型的速度表示。同时,为了使算法寻优能力更高、避免迭代过程陷入局部最优无法跳出,设计了2-opt和3-opt算子,结合随机贪婪规则,使求解质量更高、收敛更快。在算法后期,为了提高粒子在整体解空间中的全局搜索能力,采用一部分粒子重新生成的方式去重新探索解空间。为了验证算法的有效性,采用了众多旅行商问题(TSP)标准算例进行测试。实验结果表明,对于小规模TSP,该算法可以找到历史最优解;对于大规模TSP,如城市数在100以上的问题,也可以找到满意解,与已知最优解之间偏差度较小,通常在5%以内。
[Abstract]:An improved particle swarm optimization algorithm based on hamming distance is proposed to solve discrete problems. The algorithm preserves the basic idea and flow of particle swarm optimization algorithm and defines a new speed representation for particles based on hamming distance. At the same time, in order to improve the optimization ability of the algorithm and avoid the iterative process falling into the local optimal can not jump out, the 2-opt and 3-opt operators are designed, combined with the random greedy rules, the solution quality is higher and the convergence is faster. In the later stage of the algorithm, in order to improve the global search ability of particles in the global solution space, a part of the particle is regenerated to re-explore the solution space. In order to verify the validity of the algorithm, many (TSP) standard examples of traveling salesman problems are used to test. The experimental results show that the historical optimal solution can be found for the small scale TSP, algorithm and the satisfactory solution can be found for the large scale TSP, problem such as the number of cities above 100. The deviation between the proposed algorithm and the known optimal solution is less than 5%.
【作者单位】：北京科技大学工程技术研究院;北京科技大学钢铁共性技术协同创新中心;
【基金】：国家自然科学基金资助项目(51274043)~~
【分类号】：TP18

【相似文献】