9 Ant Colony Optimization Details and Socratic Method Introduction

Initialize parameters, heuristic functions, and pheromone levels.
Ants construct solutions by traversing the graph.
Optionally apply local search (skipped here).
Update pheromone levels based on the solutions found.
Repeat the process for a number of generations or iterations.
A more detailed view: For each iteration, for each ant, for each step, follow a stochastic transition rule.
Two main points: stochastic state transition rule and updating the pheromone.

This implementation uses three matrices: distance matrix, heuristic matrix, and pheromone matrix.
This is just one approach; other data structures can be used.

The instructor asks students to write down the distance matrix for the five-city graph.
Example first row: 0, 10, 12, 11, 14 (where 0 represents the distance from a city to itself).

The heuristic function guides the ant's next move.
For TSP, the heuristic is one over the distance to neighboring nodes ( $1/distance$ ).
This prioritizes shorter nodes to minimize the tour length.
To compute the heuristic matrix, take the distance matrix and compute one over each non-zero entry.
The heuristic matrix represents the preference for moving from one node to another.

Typically, the pheromone matrix is initialized with random numbers between zero and one.
For simplicity, in this example, the pheromone matrix is initialized with all ones.
All matrices refer to the construction graph, with each entry representing a weight on an edge.

Assume three ants for this iteration.
For each ant:
- Initialize allowed nodes (initially all nodes).
- Remove the current node from the allowed nodes.
- Compute transition probabilities to other allowed nodes.
- Select a node based on these probabilities and move.
The instructor asks how to keep track of nodes not allowed for each ant.
A list of visited cities for each ant is a possible solution.

To prevent an ant from visiting a node (e.g., node 1), set the corresponding column (column 1) in the heuristic matrix to zero.
This makes the heuristic strongly disfavor that node.

Remind the formula: $P{ij}^k(t) = \frac{{\tau{ij}(t)^{\alpha} * \eta{ij}^{\beta}}}{{\sum{l \in allowed} \tau{il}(t)^{\alpha} * \eta{il}^{\beta}}}$
Where:
- $P_{ij}^k(t)$ is the probability of ant k at time t moving from node i to node j.
- $\tau_{ij}(t)$ is the pheromone level on edge (i, j) at time t.
- $\eta_{ij}$ is the heuristic value for edge (i, j).
- $\alpha$ and $\beta$ are parameters.
The formula balances pheromone and heuristic information.

The instructor asks how to use the transition probability formula with the matrices.
Compute probabilities from the pheromone and heuristic matrices.
Given: Ant k = 1 (ANT1), current node i = 1, time t = 1, $\alpha = 1$ , $\beta = 2$ .

Compute the numerators for ant one moving from node one to each of the other nodes.
Example:
- Probability of ant one moving from node one to one: pheromone(1,1)^1 * heuristic(1,1)^2 = 1^1 * 0^2 = 0.
The zero comes from the heuristic matrix where the column has been zeroed out to prevent revisits.

The denominator is the sum of all numerators for the allowed moves.
Normalize the numerators by dividing each by the denominator to get the probabilities.

Use roulette wheel selection (or rule at will selection) to make probabilistic decisions.
Compute cumulative probabilities.
Generate a random number between 0 and 1.
Select the city corresponding to the cumulative probability that is just above the random number.

Given cumulative probabilities: 0, 0.207, 0.453, 0.838, 1.0.
If the random number is 0.6841, select city four (cumulative probability 0.838).
The instructor emphasizes selecting the closest higher probability.

After moving to city four, remove city four from the allowable cities by setting zeros in column four of the heuristic matrix.
Recompute the probabilities using the updated heuristic matrix.

Example tour lengths:
- Ant 1: 1 -> 4 -> 3 -> 5 -> 2 -> 1
- Ant 2: [Tour]
- Ant 3: [Tour]
Measure the fitness (total tour length) for each ant.
- Example: Fitness for ant one is 52, for ant two is 60, for ant three is 60.

Remind the formula: $\tau{ij}(t+1) = (1 - \rho) * \tau{ij}(t) + \sum{k=1}^{m} \Delta \tau{ij}^k$
Where:
- $\tau_{ij}(t+1)$ is the pheromone level on edge (i, j) at time t+1.
- $\rho$ is the evaporation rate.
- $\Delta \tau_{ij}^k$ is the amount of pheromone ant k deposits on edge (i, j).
- $\Delta \tau{ij}^k = \frac{Q}{Lk}$ if ant k used edge (i, j) in its tour, otherwise 0.
- $Q$ is a constant (e.g., 1).
- $L_k$ is the length of the tour of ant k.

For each edge traversed by an ant, add $\Delta \tau{ij}^k = \frac{Q}{Lk}$ to the corresponding entry in the pheromone matrix.
If an edge was not traversed, add zero.
Example: Ant one went from city one (0 in Python) to city four (3), so add one over its tour length (1/52) to pheromone[0][3].
This updates pheromone levels based on tour quality.