Ant colony optimization (ACO) is a population-based, stochastic search technique inspired by ants finding routes to food. Artificial ants construct candidate solutions, while shared pheromone values make promising choices more likely for later ants. It is useful for route-finding and can be adapted to scheduling and assignment problems. A strong trail guides the search; it does not guarantee the global optimum. section 10.2 section 10.3 section 2.2
Two paths to food
Imagine a nest connected to food by two paths. Give both paths equal initial pheromone: the first ants have no trail-based reason to prefer either one. After ants travel, update each trail through evaporation and new deposits. Repeated use can strengthen a promising path, while evaporation prevents old choices from remaining permanently attractive. With no evaporation, ants may repeatedly follow the same trail and become trapped in a local optimum. section 10.1 section 10.2
To turn that intuition into a graph search, repeat these steps:
- Initialize pheromone on edges and place several ants at the source. section 10.3.1
- Let each ant build a feasible path. At each node, choose among available next nodes probabilistically using pheromone and a desirability heuristic, typically inverse distance. Parameters α and β control their respective influence. section 10.3.1
- Evaluate the completed paths, evaporate pheromone, and deposit new pheromone. Repeat while retaining the best solution found. Excessive pheromone influence can drive rapid convergence to a suboptimal path. section 10.3.1 section 10.3.5
ACO is a family rather than one fixed procedure. Simple ACO builds paths on a graph; ant system adds a tabu-list memory. Ant colony system changes the transition rule with an elitist strategy. Max–min ant system uses the iteration-best path for updates and bounds pheromone values to reduce premature stagnation. Pheromone may be deposited during construction, after a solution is complete, or both. section 10.3.1 section 10.6
An open traveling-salesperson route
For 20 US cities, start every candidate route in New York City, visit each other city once, and do not return home. Compute pairwise haversine distances, then let each ant choose its next unvisited city from normalized pheromone-and-inverse-distance weights. A Python implementation evaluates route lengths, updates pheromone after each iteration, and keeps its best route; one reported run used 30 ants, 100 iterations, α = 1, β = 0.9, and an evaporation rate of 0.5. A separate ACOpy implementation applies a solver and colony to a weighted NetworkX graph. section 10.3.5
def run_ACO(distances, ants, iterations, alpha, beta, evaporation_rate, Q):
pheromones = np.ones((city_count, city_count)) #1
best_path = None
best_distance = float('inf')
for _ in tqdm(range(iterations), desc="Running ACO", unit="iteration"):
paths =ant_tour(pheromones, distances) #2
distances_paths = np.array([cost_function(path) for path in paths]) #3
min_idx = distances_paths.argmin()
min_distance = distances_paths[min_idx]
if min_distance < best_distance: #4
best_distance = min_distance
best_path = paths[min_idx]
pheromones = update_pheromones(paths, pheromones) #5
return best_path, best_distance #6
Inspect the iteration loop to see where ants construct routes, route costs are compared, the best-so-far route is saved, and pheromone is updated. section 10.3.5
