IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v8y2020i10p1650-d418579.html
   My bibliography  Save this article

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

Author

Listed:
  • Zhaojun Zhang

    (School of Electrical Engineering and Automation, Jiangsu Normal University, Xuzhou 221116, China
    These authors contributed equally to this work.)

  • Zhaoxiong Xu

    (School of Electrical Engineering and Automation, Jiangsu Normal University, Xuzhou 221116, China
    These authors contributed equally to this work.)

  • Shengyang Luan

    (School of Electrical Engineering and Automation, Jiangsu Normal University, Xuzhou 221116, China
    These authors contributed equally to this work.)

  • 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)

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.

Suggested Citation

  • Zhaojun Zhang & Zhaoxiong Xu & Shengyang Luan & Xuanyu Li & Yifei Sun, 2020. "Opposition-Based Ant Colony Optimization Algorithm for the Traveling Salesman Problem," Mathematics, MDPI, vol. 8(10), pages 1-16, September.
    • Handle: RePEc:gam:jmathe:v:8:y:2020:i:10:p:1650-:d:418579
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/8/10/1650/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/8/10/1650/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Anand Kumar & Manoj Thakur & Garima Mittal, 2018. "A new ants interaction scheme for continuous optimization problems," International Journal of System Assurance Engineering and Management, Springer;The Society for Reliability, Engineering Quality and Operations Management (SREQOM),India, and Division of Operation and Maintenance, Lulea University of Technology, Sweden, vol. 9(4), pages 784-801, August.
    2. Liao, Tianjun & Stützle, Thomas & Montes de Oca, Marco A. & Dorigo, Marco, 2014. "A unified ant colony optimization algorithm for continuous optimization," European Journal of Operational Research, Elsevier, vol. 234(3), pages 597-609.
    3. Min Huang & Ping Ding, 2013. "An Improved Ant Colony Algorithm and Its Application in Vehicle Routing Problem," Mathematical Problems in Engineering, Hindawi, vol. 2013, pages 1-9, November.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Jun Xu & Wei Hu & Wenjuan Gu & Yongguang Yu, 2023. "A Discrete JAYA Algorithm Based on Reinforcement Learning and Simulated Annealing for the Traveling Salesman Problem," Mathematics, MDPI, vol. 11(14), pages 1-23, July.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Anand Kumar & Manoj Thakur & Garima Mittal, 2018. "A new ants interaction scheme for continuous optimization problems," International Journal of System Assurance Engineering and Management, Springer;The Society for Reliability, Engineering Quality and Operations Management (SREQOM),India, and Division of Operation and Maintenance, Lulea University of Technology, Sweden, vol. 9(4), pages 784-801, August.
    2. Pagnozzi, Federico & Stützle, Thomas, 2019. "Automatic design of hybrid stochastic local search algorithms for permutation flowshop problems," European Journal of Operational Research, Elsevier, vol. 276(2), pages 409-421.
    3. Fayez Alanazi & Ibrahim Khalil Umar & Sadi Ibrahim Haruna & Mahmoud El-Kady & Abdelhalim Azam, 2023. "Development of Artificial Intelligence Based Safety Performance Measures for Urban Roundabouts," Sustainability, MDPI, vol. 15(14), pages 1-17, July.
    4. Stefano Bromuri, 2019. "Dynamic heuristic acceleration of linearly approximated SARSA( $$\lambda $$ λ ): using ant colony optimization to learn heuristics dynamically," Journal of Heuristics, Springer, vol. 25(6), pages 901-932, December.
    5. Li, Guiqiang & Jin, Yi & Akram, M.W. & Chen, Xiao & Ji, Jie, 2018. "Application of bio-inspired algorithms in maximum power point tracking for PV systems under partial shading conditions – A review," Renewable and Sustainable Energy Reviews, Elsevier, vol. 81(P1), pages 840-873.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:8:y:2020:i:10:p:1650-:d:418579. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.