Intelligent Systems II · TEE · formulas

TEE-only formulas: ACO and GA for TSP

TEE formula sheet · Units 1 and 4

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

Ant colony optimisation

Transition probabilityP_{ij}=\dfrac{\tau_{ij}^\alpha\eta_{ij}^\beta}{\sum_{l\in\text{allowed}}\tau_{il}^\alpha\eta_{il}^\beta},\;\eta_{ij}=1/d_{ij}LaTeX: 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 rulecumulative 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_kLaTeX: \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=1LaTeX: \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)LaTeX: L=\sum_{i=1}^{n-1}d(c_i,c_{i+1})+d(c_n,c_1)
F_{TSP}=1/LLaTeX: 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.