最小比率旅行商问题的阴阳平衡优化算法

Yin-Yang Pair Optimization Algorithm for Minimum Ratio Traveling Salesman Problem

针对求解最小比率旅行商问题方法存在精度低和速度慢等问题,设计阴阳平衡优化算法进行求解。采用佳点集构造初始解集;以超球体和归档集进行解的更新;并用相对位置索引法将算法搜索空间映射为问题解空间;基于综卦变换引入局部搜索。采用典型算例进行一系列数值实验,并将算法与微粒群优化算法、引力搜索算法、生物地理学优化算法以及最有价值球员算法进行比较。实验结果表明,所提算法在计算精度和优化速度方面优势显著,能够有效求解最小比率旅行商问题。

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.