求解旅行商问题的多尺度量子自由粒子优化算法  

Multi-scale quantum free particle optimization algorithm for solving travelling salesman problem

作　　者：杨云亭 王鹏[3] YANG Yunting;WANG Peng(Chengdu Institute of Computer Application,Chinese Academy of Sciences,Chengdu Sichuan 610041,China;University of Chinese Academy of Sciences,Beijing 100049,China;School of Computer Science and Technology,Southwest Minzu University,Chengdu Sichuan 610041,China)

机构地区：[1]中国科学院成都计算机应用研究所,成都610041 [2]中国科学院大学,北京100049 [3]西南民族大学计算机科学与技术学院,成都610225

出　　处：《计算机应用》2020年第5期1278-1283,共6页journal of Computer Applications

基　　金：国家自然科学基金资助项目(60702075)。

摘　　要：针对目前元启发式算法在求解组合优化问题中的旅行商问题(TSP)时求解缓慢的问题,受量子理论中波函数的启发提出一种多尺度自适应的量子自由粒子优化算法。首先,在可行域中随机初始化表示城市序列的粒子,作为初始的搜索中心;然后,以每个粒子为中心进行当前尺度下的均匀分布函数的采样,并交换采样位置上的城市编号产生新解;最后,根据新解相较上一次迭代中最优解的优劣进行搜索尺度的自适应调整,并在不同的尺度下进行迭代搜索直到满足算法结束条件。将该算法和混合粒子群优化(HPSO)算法、模拟退火(SA)算法、遗传算法(GA)和蚁群优化算法应用在TSP上进行性能测试,实验结果表明自由粒子模型算法适合求解组合优化问题,在TSP数据集上相比目前较优算法在求解速度上平均提升50%以上。Aiming at the problem of slowness of the current meta-heuristic algorithms when solving Travelling Salesman Problem(TSP)in combinatorial optimization problems,a multi-scale adaptive quantum free particle optimization algorithm was proposed based on the inspiration of the wave function in quantum theory.Firstly,the particles representing the city sequences were randomly initialized in the feasible region as the initial search centers.Then,the new solution was obtained by taking each particle as the center to perform the sampling with uniformly distributed function and exchanging the city numbers in the sampling positions.Finally,according to the comparison result of the new solution with the optimal solution in the previous iteration,the search scale was adaptively adjusted,and the iterative search was carried out at different scales until the end condition of the algorithm was satisfied.The algorithm was compared with Hybrid Particle Swarm Optimization(HPSO)algorithm,Simulated Annealing(SA),Genetic Algorithm(GA)and Ant Colony Optimization(ACO)algorithm on TSP.The experimental results show that the multi-scale quantum free particle optimization algorithm is suitable for solving combinatorial optimization problems,and increases the solving speed by over 50%on average compared with the current better algorithms on the TSP datasets.

关 键 词：自由粒子 动态搜索 优化算法 组合优化 旅行商问题 波函数 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]