COOBBO: A Novel Opposition-Based Soft Computing Algorithm for TSP Problems

Algorithms

Qingzheng Xu¹  Lemeng Guo¹  Na Wang²  Yongjian He¹ 

[1] Department of Information Service, Xi’an Communications Institute, No. 8, Zhangba East Road, Xi’an 710106, China; E-Mails:;Department of Basic Courses, Xi’an Communications Institute, No. 8, Zhangba East Road, Xi’an 710106, China; E-Mail:

关键词: biogeography-based optimization;    opposition-based learning;    traveling salesman problems;    discrete domain;    opposite path;    population diversity;   

DOI  :  10.3390/a7040663

来源: mdpi

【 摘 要 】

In this paper, we propose a novel definition of opposite path. Its core feature is that the sequence of candidate paths and the distances between adjacent nodes in the tour are considered simultaneously. In a sense, the candidate path and its corresponding opposite path have the same (or similar at least) distance to the optimal path in the current population. Based on an accepted framework for employing opposition-based learning, Oppositional Biogeography-Based Optimization using the Current Optimum, called COOBBO algorithm, is introduced to solve traveling salesman problems. We demonstrate its performance on eight benchmark problems and compare it with other optimization algorithms. Simulation results illustrate that the excellent performance of our proposed algorithm is attributed to the distinct definition of opposite path. In addition, its great strength lies in exploitation for enhancing the solution accuracy, not exploration for improving the population diversity. Finally, by comparing different version of COOBBO, another conclusion is that each successful opposition-based soft computing algorithm needs to adjust and remain a good balance between backward adjacent node and forward adjacent node.

【 授权许可】

CC BY   
© 2014 by the authors; licensee MDPI, Basel, Switzerland.