8 Ant Colony Optimization and Coursework Details

Given a set of cities, find the shortest tour that visits each city exactly once and returns to the starting city.
NP-complete problem, commonly used as a testbed for various algorithms.

Construction Graph:
- Nodes represent cities.
- Edges connect all nodes (fully connected graph).
- Pheromone is placed on edges.
Ant Traversal:
- Multiple ants traverse the graph.
- Ants are attracted to edges with more pheromone.
- Ants have memory and avoid revisiting cities.
- After $n$ steps, each ant completes a tour.
Tour Quality Measurement:
- The quality (fitness) of each tour is evaluated.
Pheromone Update:
- Edges in good tours receive more pheromone.
- Edges in bad tours receive less pheromone.
- Pheromone evaporation occurs on all edges (pheromone levels decrease over time).
Repeat:
- Steps 2-4 are repeated iteratively.
- Positive feedback mechanism: Shortest paths gradually accumulate more pheromone.

Step 0: Initialize the graph with random pheromone on edges.
Three nested loops:
- Outer loop: Iterations or generations (discrete time units).
- Middle loop: For each generation, consider a certain number of ants (num_ant parameter).
- Inner loop: Each ant performs a number of steps equal to the number of cities (num_city).
Ant Placement:
- Ants are randomly placed on the nodes (cities) of the graph.
Parallel Computation:
- Ants operate independently and in parallel. No interaction
State Transition Rule:
- Each ant chooses the next city to visit based on a probabilistic rule.
Solution Evaluation:
- After all ants complete their tours, each tour represents a solution.
- The fitness of each solution is measured.
Pheromone Update:
- Pheromone levels are updated based on the quality of the solutions.
Evaporation:
- Pheromone evaporation is applied to all edges.
Termination Condition:
- The algorithm terminates after a certain number of generations or when a solution of sufficient quality is found.

Probability of an ant $k$ moving from city $i$ to city $j$ at iteration $t$ depends on:
- Whether the city $j$ has been visited (tabu list).

Static Local Heuristic ( $\eta_{ij}$ ):
- Represents the desirability of visiting city $j$ from city $i$ .
- For TSP: $\eta{ij} = .frac{1}{d{ij}}$ , where $d_{ij}$ is the distance between cities $i$ and $j$ .
- Static: Can be pre-computed and doesn't change during the algorithm's execution.
- Local: Only considers the direct neighborhood of the current node.
Learned Global Pheromone Trail ( $\tau_{ij}(t)$ ) :
- Represents the amount of virtual pheromone on edge $(i, j)$ at time $t$ .
- Learned: Changes over time based on the algorithm's progress.
- Global: Considers the complete solution and information from all ants.

The probability $p_{ij}^k(t)$ of ant $k$ moving from city $i$ to city $j$ at time $t$ is given by:

$p{ij}^k(t) = \frac{[\tau{ij}(t)]^\alpha [\eta{ij}]^\beta}{\sum{l \in \text{allowed}k} [\tau{il}(t)]^\alpha [\eta_{il}]^\beta}$

Where:

$\tau_{ij}(t)$ is the amount of pheromone on edge $(i, j)$ at time $t$ .
$\eta_{ij}$ is the heuristic desirability of moving from $i$ to $j$ .
$\alpha$ and $\beta$ are parameters that control the relative importance of pheromone and heuristic information. Always Positive.
$\text{allowed}_k$ is the set of cities that ant $k$ is allowed to visit (not in its tabu list).

If $\alpha = 0$ , ants make decisions greedily based on desirability alone.
If $\beta = 0$ , ants only consider pheromone, leading to rapid convergence and potentially suboptimal solutions.
Good values for $\alpha$ and $\beta$ are typically between zero and five, but depend on the problem.

After each ant $k$ completes its tour, it deposits pheromone on the edges it used.
The amount of pheromone deposited is proportional to the quality (fitness) of the tour.

The pheromone update rule is given by:

$\tau{ij}(t+1) = (1 - \rho) \tau{ij}(t) + \sum{k=1}^{m} \Delta \tau{ij}^k$

Where:

$\tau_{ij}(t+1)$ is the amount of pheromone on edge $(i, j)$ at time $t+1$ .
$\rho$ is the evaporation rate (between 0 and 1).
$m$ is the number of ants.
$\Delta \tau_{ij}^k$ is the amount of pheromone deposited by ant $k$ on edge $(i, j)$ , which is typically:
- $\frac{Q}{L_k}$ if ant $k$ used edge $(i, j)$ in its tour.
- 0 otherwise.
$Q$ is a constant.
$L_k$ is the length of the tour of ant $k$ .

Early ACO algorithms were competitive but not the best for static TSP problems.
ACO is adaptive and can track changes in dynamic environments. Hybridizing ACO with hill climbing led to significant improvements.
Hybrid algorithms combine the constructive heuristic of ACO with local search (hill climbing) to find nearby optimal solutions.
Extensions to ACO include:
- Max-Min Ant System: Limits the minimum and maximum amount of pheromone on edges to encourage exploration.
- Elitist Rank-Based System: Uses ranking instead of fitness-proportional selection to address issues related to fitness scaling.

Goal: Schedule jobs on a single machine to minimize lateness.
Construction Graph:
- Nodes: Tasks to be scheduled ( $a, b, c, d, e$ ).
- Edges: Connections between tasks, representing the order of scheduling.
- Start node: Needed because the first job scheduled needs to be considered.
Heuristic:
- Desirability is proportional to the inverse of the lateness of each job.

Goal: Pack items into bins to balance/minimize the difference in the level of each bin
Construction Graph:
- Each item must be assigned to a Bin.
- Nodes: start node, end node, representation of each bin, K columns for the items themselves
- Interpretation: The algorithm traverses the graph in layers, starting with "item one", followed by "item two" etc. Each layer has K nodes, one for each item. Each path of a layer goes to one of the Bins (ie. one of the rows). The item is then assigned to this bin if that path is taken by the ACO.