ACO Flashcards
(9 cards)
What is Ant Colony Optimization (ACO)?
definition/what its used for
A swarm intelligence algorithm inspired by the foraging behavior of real ants.
Used to find good paths/solutions in combinatorial optimization problems (e.g., Traveling Salesman Problem, routing).
Artificial ants build solutions by traversing a construction graph.
A population-based metaheuristic where ants (agents) collectively find solutions.
How do ants in ACO find good solutions?
Ants deposit pheromone (τ) on paths (solution components) they traverse.
They probabilistically prefer paths with:
Higher pheromone concentration.
Better heuristic information (η) (e.g., shorter distance).
Pheromone Evaporation (ρ): Reduces pheromone over time, weakening less-used paths and allowing exploration.
CO: How is the probability P_ij of an ant choosing path (i,j) calculated?
τ_ij: Pheromone on path (i,j).
η_ij: Heuristic value for path (i,j) (e.g., 1/distance).
α: Pheromone influence parameter.
β: Heuristic influence parameter.
Denominator: Sum of (τ^α * η^β) for ALL valid next paths k from node i.
ACO: What is the role of parameters α and β?
α (Alpha): Controls the influence of pheromone.
High α: Ants strongly follow pheromone trails (more exploitation).
Low α: Pheromone has less influence.
β (Beta): Controls the influence of heuristic information.
High β: Ants strongly prefer heuristically good choices (e.g., short local distances).
Low β: Heuristic has less influence.
These parameters balance exploration vs. exploitation
ACO: How does pheromone evaporation work?
All existing pheromone trails are reduced in each iteration BEFORE new deposition.
Formula: τ_new = (1-ρ) * τ_old
ρ (rho) is the evaporation rate (0 < ρ < 1).
Purpose: Prevents premature convergence, allows old/bad paths to be forgotten, encourages exploration.
ACO: How does pheromone deposition work?
After constructing solutions, ants deposit new pheromone (Δτ) on the paths they used.
Amount deposited is usually proportional to the quality of the ant’s solution (better solution = more pheromone).
E.g., for TSP, Δτ_ij^k = 1/L_k if ant k used edge (i,j) in its tour of length L_k.
Total new pheromone: τ_ij(t+1) = (evaporated τ_ij) + Σ (Δτ_ij^k from all ants that used the edge)
ACO: What are the main factors influencing an ant choosing a path?
The presence and intensity of pheromones on the path.
The heuristic value of the path (e.g., inverse of its length/cost).
ACO: What kind of problems can be solved using ACO?
Combinatorial optimization problems.
Classic example: Traveling Salesman Problem (TSP).
Other examples: Vehicle routing, network routing, scheduling, assignment problems. (Problem variables usually discrete).
