Ant colony algorithms for the travelling salesman problem and the quadratic assignment problem

Ant colony algorithms for the travelling salesman problem and the quadratic assignment problem

For access to this article, please select a purchase option:

Buy chapter PDF
(plus tax if applicable)
Buy Knowledge Pack
10 chapters for £75.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Your details
Why are you recommending this title?
Select reason:
Swarm Intelligence - Volume 1: Principles, current algorithms and methods — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

The ant colony optimization (ACO) is a metaheuristic, which has been successfully used to solve computationally difficult optimization problems, especially combinatorial optimization problems which belong to the class of non-deterministic polynomial (NP)-hard problems. This chapter explains ACO algorithms, their most important variants, and hybridization with local optimization methods. Practical considerations for successful ACO implementation and parameter setting are given. The working of the algorithm is explained in detail by using simple examples. The chapter ends with overview of research trends in ACO.

Chapter Contents:

  • Abstract
  • 15.1 Introduction
  • 15.2 Ant colony optimization metaheuristic
  • 15.2.1 Constructing the solutions
  • 15.2.2 Updating pheromone trails
  • 15.2.3 Optional daemon actions
  • 15.3 Important variants of ant colony optimization algorithms
  • 15.3.1 Probabilistic rules for choosing solution components
  • 15.3.2 Ant system
  • 15.3.3 Elitist ant system
  • 15.3.4 Ant colony system
  • 15.3.5 Rank-based ant system
  • 15.3.6 Approximate nondeterministic tree search
  • 15.3.7 MAX–MIN ant system
  • 15.3.8 Best–worst ant system
  • 15.3.9 Population-based ant colony optimization
  • 15.3.10 Three bound ant system
  • 15.3.11 Other variants of ACO and ant-inspired algorithms
  • 15.4 Practical examples of ant colony optimization
  • 15.4.1 Travelling salesman problem
  • 15.4.2 Quadratic assignment problem
  • 15.4.3 A variant of MMAS algorithm for TSP
  • 15.4.4 A sketch of MMAS for QAP
  • 15.4.5 A detailed example of solution construction
  • 15.5 Suggestions for successful applications
  • 15.5.1 Local optimization
  • 15.5.2 Parameter settings
  • 15.6 Research trends in ant colony optimization
  • References

Inspec keywords: combinatorial mathematics; computational complexity; search problems; travelling salesman problems; optimisation

Other keywords: local optimization methods; ant colony optimization; ACO algorithms; quadratic assignment problem; travelling salesman problem; parameter setting; nondeterministic polynomial-hard problems; combinatorial optimization problems

Subjects: Optimisation techniques; Combinatorial mathematics; Optimisation techniques; Combinatorial mathematics

Preview this chapter:
Zoom in

Ant colony algorithms for the travelling salesman problem and the quadratic assignment problem, Page 1 of 2

| /docserver/preview/fulltext/books/ce/pbce119f/PBCE119F_ch15-1.gif /docserver/preview/fulltext/books/ce/pbce119f/PBCE119F_ch15-2.gif

Related content

This is a required field
Please enter a valid email address