39. Genetic Algorithms for the Travelling Salesman Problem A Review of Representations and Operators

1. Fundamentos de la Selección por Torneo

La selección por torneo es un método donde se eligen $t$ individuos al azar de una población y el mejor de ellos es seleccionado para la siguiente generación. El parámetro $t$ se denomina tamaño del torneo y es crucial para determinar la presión de selección.

• Caso Base ($t=1$): Si el tamaño del torneo es 1, la selección es puramente aleatoria y la distribución de aptitud de la población resultante es idéntica a la inicial ($s^*(f_i) = s(f_i)$).

• Influencia del Tamaño: A medida que $t$ aumenta, la probabilidad de seleccionar individuos con alta aptitud crece significativamente, desplazando la distribución hacia la derecha (mejores valores).

2. Modelado de Distribuciones de Aptitud

El texto analiza la selección tanto en entornos discretos como continuos:

Distribución Discreta

Se utiliza como ejemplo el problema del "robot seguidor de paredes", caracterizado por una distribución donde la mayoría de los individuos tienen una aptitud baja (valor 1) y muy pocos son exitosos (valor 17).

• La probabilidad de que un individuo de rango $j$ sea seleccionado (en una tarea de maximización) se define como:

  $p_j = N^{-t}(j^t - (j - 1)^t) \quad 1 \le j \le N$

• Esta fórmula asume que todos los individuos tienen valores de aptitud distintos.

Distribución Continua

Para simplificar el análisis matemático, se define $\bar{s}(f)$ como la distribución continua y $\bar{S}(f)$ como la distribución acumulada:

$\bar{S}(f) = \int_{f_0}^f \bar{s}(x) \, dx$

• Teorema de la Distribución Esperada: Tras la selección con un torneo de tamaño $t$, la nueva distribución $\bar{s}^*(f)$ es:

  $\bar{s}^*(f) = t \bar{s}(f) \left( \frac{\bar{S}(f)}{N} \right)^{t-1}$

3. Propiedades Avanzadas

Concatenación de Fases (Teorema 4.1)

Una de las propiedades más notables es que aplicar varias fases de selección consecutivas (sin recombinación) es matemáticamente equivalente a una sola fase con un torneo más grande.

• Si se aplica primero un torneo de tamaño $t_1$ y luego uno de tamaño $t_2$, el resultado es igual a aplicar un único torneo de tamaño $t_1 \cdot t_2$:

  $\bar{\Omega}_T(\bar{\Omega}_T(\bar{s}, t_1), t_2) = \bar{\Omega}_T(\bar{s}, t_1 t_2)$

Distribuciones Gaussianas

Se observa que cuando la distribución inicial es de tipo Gaussiana ($G(\mu, \sigma)$), la selección por torneo tiende a mantener una forma aproximadamente Gaussiana, pero desplazando la media hacia valores superiores de aptitud y reduciendo la varianza a medida que el tamaño del torneo aumenta.

Proporción de Mejores Individuos

Citando a Goldberg y Deb, el texto menciona que la proporción de los individuos más aptos ($P_\tau$) tras $\tau$ generaciones de selección pura (sin cruce) sigue una progresión exponencial basada en el tamaño del torneo:

$P_\tau = 1 - (1 - P_0)^{t^\tau}$

---

relatedInteligencia Artificial