摘要
针对求解最小比率旅行商问题方法存在精度低和速度慢等问题,设计阴阳平衡优化算法进行求解。采用佳点集构造初始解集;以超球体和归档集进行解的更新;并用相对位置索引法将算法搜索空间映射为问题解空间;基于综卦变换引入局部搜索。采用典型算例进行一系列数值实验,并将算法与微粒群优化算法、引力搜索算法、生物地理学优化算法以及最有价值球员算法进行比较。实验结果表明,所提算法在计算精度和优化速度方面优势显著,能够有效求解最小比率旅行商问题。
Due to the disadvantages of low accuracy and slow speed in the algorithms for the minimum ratio traveling salesman problem,a Yin-Yang pair optimization algorithm is proposed.The good points set is used to construct initial solutions.The solutions are updated by hyperspheres and archive sets.The relative position indexing approach is adopted to map the search space of the algorithm to the solution space of the problem.A local search is introduced by the synthesis operator.Experiments with typical examples are carried out.The presented method is compared with particle swarm optimization,biogeography-based optimization and the most valuable player algorithm.The results show the algorithm has significant advantages in calculation accuracy and optimization speed.The proposed algorithm can effectively solve the minimum ratio traveling salesman problem.
作者
许秋艳
马良
刘勇
XU Qiu-yan;MA Liang;LIU Yong(School of Management,University of Shanghai for Science and Technology,Shanghai 200093,China;College of Information Engineering,Yancheng Institute of Technology,Yancheng Jiangsu 224051,China)
出处
《计算机仿真》
北大核心
2022年第8期356-362,共7页
Computer Simulation
基金
上海市“科技创新行动计划”软科学研究重点项目(18692110500)
上海市社科规划课题(2019BGL014)。
关键词
最小比率旅行商问题
阴阳平衡优化算法
佳点集
综卦变换
组合优化
Minimum ratio traveling salesman problem
Yin-Yang pair optimization algorithm
Good points set
Synthesis operator
Combinatorial optimization