DAACO: adaptive dynamic quantity of ant ACO algorithm to solve the traveling salesman problem

Huijun Liu, Ao Lee, Wenshi Lee, Ping GuoComplex 2023 · DOI

This paper, published in Complex & Intelligent Systems, presents DAACO, a refined Ant Colony Optimization (ACO) algorithm designed to tackle the Traveling Salesman Problem (TSP) more efficiently than previous metaheuristics.

TL;DR

DAACO improves the classic Ant Colony Optimization algorithm by dynamically scaling the number of "ants" based on the geometric complexity of the problem and using a two-stage neighbor selection strategy. The result is a significant leap in speed—taking as little as 8% of the time of competing algorithms—while consistently finding optimal or near-optimal solutions on standard benchmarks.

What Problem Does This Paper Address?

The Traveling Salesman Problem (TSP) is the quintessential NP-hard combinatorial optimization challenge: find the shortest possible route that visits a set of cities exactly once and returns to the start.

While Ant Colony Optimization (ACO) is a popular nature-inspired heuristic for TSP, it suffers from two main drawbacks:

  1. Slow Convergence: It often takes a long time to find a good solution.
  2. Local Optima: Ants tend to follow each other down "good enough" paths (premature convergence), getting stuck in sub-optimal loops and failing to find the true shortest path.

Standard ACO also typically uses a fixed number of ants regardless of whether there are 50 cities or 5,000, leading to either insufficient exploration or wasted computational power.

Methods

The authors introduce two primary strategies to transform standard ACO into DAACO:

1. Dynamic Ant Quantity (DA) & Smart Initialization

Instead of a hardcoded population, DAACO analyzes the geometry of the city locations:

  • Convex Hull & K-means: The algorithm calculates the "area" of the city distribution using a convex hull and then uses K-means clustering to group cities.
  • Adaptive Population: The number of ants is dynamically determined by the number of clusters and the density of cities within them.
  • Diverse Starting Points: Ants are initialized across these different clusters. This ensures that the "scouts" begin their search from diverse geographic regions, preventing the colony from immediately converging on a single local optimum.

2. Hybrid Local Selection (Choose the Best - CB)

DAACO uses a "Choose the Best" strategy that switches logic based on how much of the route is completed:

  • CBN (Choose Best Neighbor): For the first 70% of the route, ants use a standard pheromone-heavy selection to build the core of the path.
  • CBNP (Choose Best Neighbor Pair): For the final 30%, the algorithm switches to a "look-ahead" strategy. It evaluates pairs of upcoming nodes rather than just the next single city. This helps resolve the "last mile" problem in TSP where greedy choices early on often force long, inefficient legs at the end of the trip.

Finally, the algorithm integrates a 3-opt local search, a standard refinement technique that swaps three edges at a time to further polish the final path.

Datasets

The researchers evaluated DAACO using TSPLIB, the industry-standard library for TSP instances. They tested across a wide range of scales, including:

  • Small-scale: 1 to 500 cities (e.g., eil51, kroA100).
  • Medium-scale: 501 to 1,000 cities (e.g., rat575, dsj1000).
  • Large-scale: Over 1,000 cities (e.g., pcb1173, fl1577, d1655).

Key Insights and Ideas

  • Geometry as a Proxy for Complexity: By using the convex hull and clustering, the algorithm treats the TSP as a spatial problem rather than just a graph problem. This allows it to allocate computational resources (ants) where they are most needed.
  • The 70% Pivot: The most interesting finding is the effectiveness of switching selection strategies mid-route. Greedy selection is computationally cheap and effective for the "bulk" of the trip, but the "neighbor pair" look-ahead is critical for finishing the route without creating "cross-over" errors.
  • Initialization is Half the Battle: Forcing ants to start in different K-means clusters acts as a natural "diversity injection," which is often more effective than complex pheromone evaporation schemes used in other ACO variants.

Key Results

DAACO was compared against several state-of-the-art variants (DFACO, DEACO, DCS, and MGACACO):

  • Accuracy: DAACO found the optimal solution in 25 out of 26 tested instances. In 10 of those instances, it outperformed all other compared algorithms.
  • Speedup: The efficiency gains were massive. DAACO required only 8.17% of the execution time of DFACO and 8.44% of the time of DEACO to reach its solutions.
  • Stability: The algorithm showed a significantly lower standard deviation across multiple runs, indicating it is less sensitive to random initialization than its predecessors.

Limitations and Future Work

  • Symmetric Focus: The current study focuses exclusively on Symmetric TSP (where the distance from A to B is the same as B to A). Many real-world routing problems (like those involving one-way streets or wind resistance) are asymmetric.
  • Future Directions: The authors suggest that the dynamic ant quantity and clustering approach could be adapted for Asymmetric TSP and other combinatorial problems like the Vehicle Routing Problem (VRP). They also aim to further optimize the selection formulas to handle even larger datasets (10,000+ cities).

Summary updated

Abstract

Abstract The traveling salesman problem (TSP) is an NP-hard problem. Thus far, a large number of researchers have proposed different ant colony optimization (ACO) algorithms to solve the TSP. These algorithms inevitably encounter problems such as long convergence time and the tendency to easily fall into local optima. On the basis of the ACO algorithm, this study proposes a dynamic adaptive ACO algorithm (DAACO). DAACO realizes the diversity of initialization of the ACO algorithm by dynamically determining the number of ants to be prevented from falling into local optimization. DAACO also adopts a hybrid local selection strategy to increase the quality of ant optimization and reduce the optimization time. Among the 20 instances of the TSPLIB dataset, the DAACO algorithm obtains 19 optimal values, and the solutions of 10 instances are better than those of other algorithms. The experimental results on the TSPLIB dataset show that the DAACO algorithm has obvious advantages in terms of convergence time, solution quality, and average value relative to existing state-of-the-art ACO algorithms.
BibTeX
@inproceedings{liu2023daaco,
  author = {Huijun Liu and Ao Lee and Wenshi Lee and Ping Guo},
  title = {{DAACO: adaptive dynamic quantity of ant ACO algorithm to solve the traveling salesman problem}},
  booktitle = {Complex},
  year = {2023},
  doi = {10.1007/s40747-022-00949-6},
}
Figure