10.2 TSP y el Ant System

La primera versión de ACO se utilizó para resolver el agente viajero.

Al construir soluciones, una hormiga $k$ decide irse de la ciudad $i$ a la ciudad $j$ con la siguiente probabilidad:

$$p_{ij}^{k}(t) = \frac{[\tau_{ij}(t)]^{\alpha} \cdot [\eta_{i... ...a} \cdot [\eta_{ij}]^{\beta} } \mbox{ si } j \in {\cal N}_i^k$$

donde $\eta_{ij} = 1/d_{ij}$ es información disponible, $\alpha$ y $\beta$ son parámetros que se tienen que definir, y ${\cal N}_i^k$ es la vecindad factible de la hormiga $k$ (el conjunto de ciudades que $k$ no ha visitado).

Si $\alpha=0$ se visita la ciudad más cercana. Si $\beta = 0$ se basa solo en las trazas de feromona y tiende a converger rápidamente a un punto de no mejora subóptimo.

Cuando todas las hormigas completan un circuito, se actualizan las feromonas.Primero se reducen todos los caminos por un factor constante (evaporación) y después cada hormiga deposita la siguiente cantidad de feromona en los nodos de su circuito:

$$\forall (i,j) \mbox{ } \tau_{ij}(t+1) = (1 - \rho) \cdot \tau_{ij}(t) + \sum_{k=1}^{m} \Delta \tau_{ij}^{k}(t)$$

donde $0 \leq \rho \leq 1$ es la razón de evaporación de feromona y $m$ es el número de hormigas.

$\Delta \tau_{ij}^{k}(t)$ es la cantidad que deposita cada hormiga en cada nodo, definida por:

$$\Delta \tau_{ij}^{k}(t) = \left\{ \begin{array}{ll} 1/L^k(t)... ...la hormiga } k \\ 0 \mbox{ de otra forma} \end{array}\right .$$

donde $L^k(t)$ es la longitud del circuito de la hormiga $k$.