# TEE-only formulas: ACO and GA for TSP

Subject: Intelligent Systems II

Exam: TEE

Reader: https://deep-learning-study-room.vercel.app/is2/#tee/formulas/tee-formulas/aco-tsp

Canonical: https://deep-learning-study-room.vercel.app/read/is2/tee/formulas/tee-formulas--aco-tsp/

Probability, Bayes, GMM/EM, Markov chains and Bellman equations (Units 2–3 are in the M2 sheet)

## Ant colony optimisation

|  |  |
| --- | --- |
| Transition probability | 

$$
P_{ij}=\dfrac{\tau_{ij}^\alpha\eta_{ij}^\beta}{\sum_{l\in\text{allowed}}\tau_{il}^\alpha\eta_{il}^\beta},\;\eta_{ij}=1/d_{ij}
$$

 |
| Choice rule | cumulative probabilities in **city order**; first city with cumulative ≥ r |
| Pheromone update | 

$$
\tau_{ij}\leftarrow(1-\rho)\tau_{ij}+\sum_{k:\,ij\in tour_k} Q/L_k
$$

 on every edge ant k used (return edge included); symmetric only for an undirected symmetric TSP |
| Values assumed in the worked PYQs | 

$$
\alpha=\beta=1,\;\rho=0.5,\;Q=1,\;\tau_0=1
$$

 |

α weights pheromone influence; β weights inverse-distance influence; ρ is the evaporation rate; Q is the deposit constant; L is the complete tour length. These must be supplied or explicitly assumed. Do not treat the example values as universal defaults.



$$
L=\sum_{i=1}^{n-1}d(c_i,c_{i+1})+d(c_n,c_1)
$$





$$
F_{TSP}=1/L
$$



The return edge is part of the tour. Permutation crossover/mutation must keep each city exactly once. For positive lengths, shorter length gives larger reciprocal fitness.