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