The ant colony optimization (ACO) meta-heuristic was inspired from the foraging behaviour of real ant colonies. In particular, real ants communicate indirectly via pheromone trails and find the shortest path. Although real ants proved that they can find the shortest path when the available paths are known a prior, they may face serious challenges when some paths are made available after the colony has converged to a path. This is because the colony may continue to follow the current path rather than exploring the new paths in case a shorter path is available. For the ACO meta-heuristic, the challenges are similar when applied to dynamic optimization problems (DOPs). Once the algorithm converges, it loses its adaptation capabilities and may have poor performance in DOPs. Several strategies have been integrated with ACO to address difficult combinatorial DOPs. Their performance proved that ACO is a powerful computational technique for combinatorial DOPs once enhanced. This chapter investigates the applications of ACO for combinatorial DOPs.

Chapter Contents:

• Abstract
• 5.1 Introduction
• 5.2 Dynamic optimization problems
• 5.2.1 DOP definition
• 5.2.2 Dynamic characteristics
• 5.2.3 Generate dynamic environments
• 5.2.3.1 Travelling salesman problem
• 5.2.3.2 Vehicle routing problem
• 5.2.3.3 Job-shop scheduling problem
• 5.2.3.4 Binary-encoded functions
• 5.2.3.5 Knapsack problem
• 5.3 Ant colony optimization meta-heuristic
• 5.3.1 Construct solutions
• 5.3.2 Local search
• 5.3.3 Pheromone update
• 5.3.4 Main ACO algorithms
• 5.3.4.1 MAX–MIN ant system
• 5.3.4.2 Ant colony system
• 5.3.4.3 Population-based ant colony optimization
• 5.4 ACO for DOPs
• 5.4.1 Increasing diversity after a change
• 5.4.2 Maintain diversity during the execution
• 5.4.3 Memory schemes
• 5.4.4 Multi-colony schemes
• 5.4.5 Hybridizations
• 5.4.6 Discussion
• 5.5 ACO in real-world DOP applications
• 5.6 Conclusions
• Acknowledgement
• References

Inspec keywords: combinatorial mathematics; search problems; ant colony optimisation

Other keywords: ACO meta-heuristic; ant colony optimization meta-heuristic; dynamic combinatorial optimization problems; combinatorial DOP; foraging behaviour

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