Opposition-Based Ant Colony Optimization Algorithm for the Traveling Salesman Problem

Zhaojun Zhang, Zhaoxiong Xu, Shengyang Luan, Xuanyu Li and Yifei Sun
Additional contact information
Zhaojun Zhang: School of Electrical Engineering and Automation, Jiangsu Normal University, Xuzhou 221116, China
Zhaoxiong Xu: School of Electrical Engineering and Automation, Jiangsu Normal University, Xuzhou 221116, China
Shengyang Luan: School of Electrical Engineering and Automation, Jiangsu Normal University, Xuzhou 221116, China
Xuanyu Li: School of Electrical Engineering and Automation, Jiangsu Normal University, Xuzhou 221116, China
Yifei Sun: School of Computer Science & School of Physics and Information Technology, Shaanxi Normal University, Xi’an 710119, China

Mathematics, 2020, vol. 8, issue 10, 1-16

Abstract: Opposition-based learning (OBL) has been widely used to improve many swarm intelligent optimization (SI) algorithms for continuous problems during the past few decades. When the SI optimization algorithms apply OBL to solve discrete problems, the construction and utilization of the opposite solution is the key issue. Ant colony optimization (ACO) generally used to solve combinatorial optimization problems is a kind of classical SI optimization algorithm. Opposition-based ACO which is combined in OBL is proposed to solve the symmetric traveling salesman problem (TSP) in this paper. Two strategies for constructing opposite path by OBL based on solution characteristics of TSP are also proposed. Then, in order to use information of opposite path to improve the performance of ACO, three different strategies, direction, indirection, and random methods, mentioned for pheromone update rules are discussed individually. According to the construction of the inverse solution and the way of using it in pheromone updating, three kinds of improved ant colony algorithms are proposed. To verify the feasibility and effectiveness of strategies, two kinds of ACO algorithms are employed to solve TSP instances. The results demonstrate that the performance of opposition-based ACO is better than that of ACO without OBL.

Keywords: opposition-based learning; ant colony optimization; opposite path; traveling salesman problems (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2227-7390/8/10/1650/pdf (application/pdf)
https://www.mdpi.com/2227-7390/8/10/1650/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:8:y:2020:i:10:p:1650-:d:418579

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().