Odili Julius Beneoluchi, Noraziah A, Zarina M
Department of Mathematical Sciences, Anchor University Lagos, Lagos, Nigeria.
Faculty of Computing, Universiti Malaysia Pahang, Pekan 26600, Malaysia.
Comput Intell Neurosci. 2021 Apr 17;2021:6625438. doi: 10.1155/2021/6625438. eCollection 2021.
This paper presents a comparative performance analysis of some metaheuristics such as the African Buffalo Optimization algorithm (ABO), Improved Extremal Optimization (IEO), Model-Induced Max-Min Ant Colony Optimization (MIMM-ACO), Max-Min Ant System (MMAS), Cooperative Genetic Ant System (CGAS), and the heuristic, Randomized Insertion Algorithm (RAI) to solve the asymmetric Travelling Salesman Problem (ATSP). Quite unlike the symmetric Travelling Salesman Problem, there is a paucity of research studies on the asymmetric counterpart. This is quite disturbing because most real-life applications are actually asymmetric in nature. These six algorithms were chosen for their performance comparison because they have posted some of the best results in literature and they employ different search schemes in attempting solutions to the ATSP. The comparative algorithms in this study employ different techniques in their search for solutions to ATSP: the African Buffalo Optimization employs the modified Karp-Steele mechanism, Model-Induced Max-Min Ant Colony Optimization (MIMM-ACO) employs the path construction with patching technique, Cooperative Genetic Ant System uses natural selection and ordering; Randomized Insertion Algorithm uses the random insertion approach, and the Improved Extremal Optimization uses the grid search strategy. After a number of experiments on the popular but difficult 15 out of the 19 ATSP instances in TSPLIB, the results show that the African Buffalo Optimization algorithm slightly outperformed the other algorithms in obtaining the optimal results and at a much faster speed.
本文对一些元启发式算法进行了性能比较分析，这些算法包括非洲水牛优化算法（ABO）、改进的极值优化算法（IEO）、模型诱导最大最小蚁群优化算法（MIMM - ACO）、最大最小蚁群系统（MMAS）、合作遗传蚁群系统（CGAS）以及启发式随机插入算法（RAI），用于解决非对称旅行商问题（ATSP）。与对称旅行商问题截然不同的是，针对非对称的旅行商问题的研究非常匮乏。这十分令人困扰，因为大多数实际应用本质上都是非对称的。选择这六种算法进行性能比较，是因为它们在文献中取得了一些最佳结果，并且在尝试解决ATSP问题时采用了不同的搜索方案。本研究中的比较算法在搜索ATSP解决方案时采用了不同的技术：非洲水牛优化算法采用了改进的卡普 - 斯蒂尔机制，模型诱导最大最小蚁群优化算法（MIMM - ACO）采用了带修补技术的路径构建方法，合作遗传蚁群系统使用自然选择和排序；随机插入算法采用随机插入方法，改进的极值优化算法使用网格搜索策略。在对TSPLIB中19个ATSP实例里广为人知但难度较大的15个实例进行了多次实验后，结果表明非洲水牛优化算法在获得最优结果方面略优于其他算法，且速度要快得多。
