A Multi-MetaHeuristic Combined ACS-TSP System | SpringerLink
Skip to main content
Springer Nature Link
Log in

A Multi-MetaHeuristic Combined ACS-TSP System

  • Conference paper
Artificial Intelligence and Computational Intelligence (AICI 2011)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 7003))

  • 2215 Accesses

Abstract

This paper presents a Multi-MetaHeuristic combined Ant Colony System (ACS)-Travelling Salesman Problem(TSP) algorithm for solving the TSP. We introduce genetic algorithm in ACS-TSP to search solutions space for dealing with the early stagnation problem of the traveling salesman problem. Moreover, we present a new strategy of Minimum Spanning Tree (MST) coupled with Nearest Neighbor(NN) to construct a initial tour for improving TSP thus obtaining good solutions quickly. According to our simulation results, the new algorithm can provide a significantly improvement for obtaining a global optimum solution or a near global optimum solution in large TSPs.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Colori, A., Dorigo, M., Maniezzo, V.: Distributed optimization by ant colonies. In: Varela, F., Bourgine, P. (eds.) First Eur. Conference Artificial life, pp. 134–142 (1991)

    Google Scholar 

  2. Blum, C.: Ant colony optimization: Introduction and recent trends. Physics of Life Reviews 2, 353–373 (2005)

    Article  Google Scholar 

  3. Hseuh-Fu, R., Shan, N.-P.: A new Hybrid heuristic approach for solving large traveling salesman problem. Information Sciences 166, 67–81 (2004)

    Article  MathSciNet  Google Scholar 

  4. Bland, J.A.: Space-planning by ant colony optimization. International Journal of Computer Applications in Technology 12(6), 320–328 (1999)

    Article  Google Scholar 

  5. Dorigo, M., Maniezzo, V., Colorni, A.: Ant System: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics—Part B: Cybernetics 26(1), 29–41 (1996)

    Article  Google Scholar 

  6. Dorigo, M., Gambardella, L.M.: Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation 1(1), 53–66 (1997)

    Article  Google Scholar 

  7. Dorigo, M., Caro, G.D., Gambardella, L.M.: Ant algorithms for discrete optimization. Artificial Life 5(2), 137–172 (1999)

    Article  Google Scholar 

  8. Parpinelli, R.S., Lopes, H.S., Freitas, A.A.: Data mining with an ant colony optimization algorithm. IEEE Transactions on Evolutionary Computation 6(4), 321–332 (2002)

    Article  MATH  Google Scholar 

  9. Maniezzo, V., Colorni, A.: The ant system applied to the quadratic assignment problem. IEEE Transactions on Knowledge and Data Engineering 11(5), 769–778 (1999)

    Article  Google Scholar 

  10. Bonabeau, E., Dorigo, M., Theraulaz, G.: Swarm Intelligence: From Natural to Artificial Systems. Oxford University Press, New York (1999)

    MATH  Google Scholar 

  11. Holland, J.H.: Adaptation in Natural and Artificial Systems. The University of Michigan Press, Ann Arbor (1975)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dept. of Computer Science, Taiyuan University of Technology, Taiyuan, China

    Liang Meng & Lijuan Wang

Authors
  1. Liang Meng
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Lijuan Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. School of Business Information Technology, RMIT University, City Campus, 124 La Trobe Street, 3000, Melbourne, VIC, Australia

    Hepu Deng

  2. School of Electronics and Information, Tongji University, 201804, Shanghai, China

    Duoqian Miao

  3. School of Computer and Information Engineering, Shanghai University of Electric Power, 200090, Shanghai, China

    Jingsheng Lei

  4. Department of Business Administration, Caritas Institute of Higher Education, 18 Chui Ling Road, Tseung Kwan O, Hong Kong, China

    Fu Lee Wang

Rights and permissions

Reprints and permissions

Copyright information

© 2011 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Meng, L., Wang, L. (2011). A Multi-MetaHeuristic Combined ACS-TSP System. In: Deng, H., Miao, D., Lei, J., Wang, F.L. (eds) Artificial Intelligence and Computational Intelligence. AICI 2011. Lecture Notes in Computer Science(), vol 7003. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-23887-1_3

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-23887-1_3

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-23886-4

  • Online ISBN: 978-3-642-23887-1

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics