38. A Mathematical Analysis of Tournament Selection

Los Algoritmos Genéticos (AG) son algoritmos de búsqueda probabilísticos caracterizados por el hecho de que un número $N$ de soluciones potenciales (llamadas individuos $J_{i}\in J$, donde $J$ representa el espacio de todos los individuos posibles) del problema de optimización muestrean simultáneamente el espacio de búsqueda. Esta población $P=\{J_{1},J_{2},...,J_{N}\}\in J^{N}$ se modifica según el proceso evolutivo natural: después de la inicialización, la selección y la recombinación se ejecutan en un bucle hasta alcanzar algún criterio de terminación. Cada ejecución del bucle se denomina generación y $P(\tau)$ denota la población en la generación $\tau$.

El operador de selección tiene como objetivo mejorar la calidad media de la población otorgando a los individuos de mayor calidad una mayor probabilidad de ser copiados en la siguiente generación. De este modo, la selección enfoca la búsqueda en regiones prometedoras del espacio de búsqueda. La calidad de un individuo se mide mediante una función de aptitud $f:J\mapsto R$. La recombinación cambia el material genético en la población mediante el cruce o la mutación para explotar nuevos puntos en el espacio de búsqueda. El equilibrio entre la explotación y la exploración puede ajustarse mediante la presión de selección del operador de selección o mediante el operador de recombinación, por ejemplo, mediante la probabilidad de cruce. Dado que este equilibrio es crítico para el comportamiento del AG, es de gran interés conocer las propiedades de los operadores de selección y recombinación para comprender su influencia en la velocidad de convergencia.

Un análisis basado únicamente en el comportamiento del mejor individuo o en la aptitud media de la población solo describe un pequeño aspecto de un método de selección. En este artículo, un esquema de selección se describe por su interacción con la distribución de los valores de aptitud. Esta descripción se introduce en la siguiente sección. En la Sección 3 se realiza un análisis de la selección por torneo y en la Sección 4 se derivan sus propiedades. La Sección 5 compara la selección por torneo con otros métodos.

2 DESCRIPCIÓN DE LOS ESQUEMAS DE SELECCIÓN

En general, el comportamiento de un esquema de selección depende únicamente de los valores de aptitud (fitness) de los individuos de la población. En este artículo describimos un esquema de selección utilizando la distribución de aptitud antes y después de la selección. De este modo, se asume que la selección y la recombinación se realizan secuencialmente: primero, una fase de selección crea una población intermedia y luego se realiza la recombinación con una cierta probabilidad sobre los individuos de esta población intermedia para obtener la población de la siguiente generación. Este tipo de descripción difiere de los paradigmas comunes donde la selección se hace para obtener los individuos para la recombinación ([Goldberg, 1989; Koza, 1992]). Pero es matemáticamente equivalente y permite analizar el método de selección por separado.

Definición 2.1 (Distribución de aptitud) La función $s : R \mapsto Z_0^+$ asigna a cada valor de aptitud $f \in R$ el número de individuos en una población $P \in J^N$ que poseen este valor de aptitud. $s$ se denomina distribución de aptitud de una población $P$.

Definición 2.2 (Distribución de aptitud acumulada) Sea $n$ el número de valores de aptitud únicos y $f_1 < ... < f_{n-1} < f_n$ ($n \le N$) el ordenamiento de los valores de aptitud, donde $f_1$ denota la peor aptitud presente en la población y $f_n$ denota la mejor aptitud.

$S(f_i)$ denota el número de individuos con valor de aptitud $f_i$ o peor y se denomina distribución de aptitud acumulada, es decir:

$S(f_i) = \begin{cases} 0 & : i < 1 \\ \sum_{j=1}^{j=i} s(f_j) & : 0 \le i \le n \\ N & : i > n \end{cases} \quad (1)$

Con estas definiciones, un método de selección puede describirse como una función que transforma una distribución de aptitud en otra distribución de aptitud.

Definición 2.3 (Método de selección) Un método de selección $\Omega$ es una función que transforma una distribución de aptitud $s$ en una nueva distribución de aptitud $s'$:

$s' = \Omega(s, par\_list) \quad (2)$

$par\_list$ es una lista opcional de parámetros del método de selección.

Definición 2.4 (Distribución de aptitud esperada) _\Omega^_ denota la distribución de aptitud esperada después de aplicar el método de selección $\Omega$ a la distribución de aptitud $s$, es decir:*

$\Omega^*(s, par\_list) := E(\Omega(s, par\_list)) \quad (3)$

$s^* = \Omega^*(s, par\_list)$ se utiliza como abreviatura.

Con esta notación, no solo se puede describir el comportamiento del mejor individuo de la población o el valor de aptitud promedio, sino todos los aspectos de un esquema de selección. Nuestro objetivo es predecir $s^*(f)$ a partir de la distribución de aptitud dada $s(f)$. En la siguiente sección queremos derivar esta predicción para la selección por torneo.

3 SELECCIÓN POR TORNEO

La selección por torneo funciona de la siguiente manera: se elige un número $t$ de individuos al azar de la población y se copia al mejor individuo de este grupo en la población intermedia, y se repite $N$ veces. A menudo los torneos se realizan solo entre dos individuos (torneo binario), pero es posible una generalización a un tamaño de grupo arbitrario $t$ llamado tamaño del torneo.

Para los siguientes cálculos, asumimos que la selección por torneo se realiza con reemplazo.

Teorema 3.1 _La distribución de aptitud esperada \Omega_T^_(s, t) después de realizar la selección por torneo con tamaño de torneo $t$ sobre la distribución $s$ es*

$s^*(f_i) = \Omega_T^*(s, t)(f_i) = N \left( \left( \frac{S(f_i)}{N} \right)^t - \left( \frac{S(f_{i-1})}{N} \right)^t \right) \quad (4)$

Prueba: Primero calculamos el número esperado de individuos con aptitud $f_i$ o peor, es decir, $S^*(f_i)$. Un individuo con aptitud $f_i$ o peor solo puede ganar el torneo si todos los demás individuos en el torneo tienen una aptitud de $f_i$ o peor. Esto significa que tenemos que calcular la probabilidad de que los $t$ individuos tengan una aptitud de $f_i$ o peor. Como la probabilidad de elegir un individuo con aptitud $f_i$ o peor está dada por $\frac{S(f_i)}{N}$, obtenemos:

$S^*(f_i) = N \left( \frac{S(f_i)}{N} \right)^t \quad (5)$

Usando esta ecuación y la relación $s^*(f_i) = S^*(f_i) - S^*(f_{i-1})$ (ver Definición 2.2) obtenemos (4).

(4) muestra la fuerte influencia del tamaño del torneo $t$ en el comportamiento del esquema de selección. Obviamente, para $t = 1$ obtenemos (en promedio) la distribución inicial sin cambios como:

$s^*(f_i) = \Omega_T(s, 1)(f_i) = N \left( \frac{S(f_i)}{N} - \frac{S(f_{i-1})}{N} \right) = S(f_i) - S(f_{i-1}) = s(f_i)$

Como ejemplo de una distribución de aptitud (fitness) discreta, utilizamos la distribución de aptitud inicial del problema del "robot seguidor de paredes" de Koza [Koza, 1992]. Esta distribución es típica de los problemas resueltos mediante programación genética: existen muchos individuos malos (valor de aptitud 1) y solo unos pocos buenos (valor de aptitud 17). La Figura 1 muestra la distribución de aptitud inicial y las distribuciones resultantes para diferentes tamaños de torneo. En la Figura 2 se verifica la alta concordancia entre los resultados teóricos derivados y una simulación. Aquí se muestran las distribuciones de acuerdo a (4) y el promedio de 20 simulaciones.

• •                                ![Pasted image 20260214200711.png](/in-my-mind-os/img/Pasted%20image%2020260214200711.png)
    

• Eje Y ($s(f)$): Frecuencia de individuos.

• Eje X ($f$): Valores de aptitud.

• Descripción: Comparación entre la Distribución Teórica derivada (—) y la Simulación (- - -) para un Tamaño de Torneo $t = 10$. Se observa un ajuste casi perfecto entre ambas líneas.

---

• •                                ![Pasted image 20260214200735.png](/in-my-mind-os/img/Pasted%20image%2020260214200735.png)
    

• Eje Y ($s(f)$): Frecuencia de individuos.

• Eje X ($f$): Valores de aptitud.

• Descripción: Distribución de aptitud antes (—) y después de la Selección por Torneo con tamaño $t = 2$ (- -) y $t = 10$ (-- --). El tamaño de la población es $N = 1000$.

---

En [Bäck, 1994], la probabilidad de que el individuo con rango $i$ sea seleccionado mediante selección por torneo se da como $p_i = N^{-t}((N - i + 1)^t - (N - i)^t)$, bajo el supuesto de que los individuos están ordenados según su valor de aptitud $f(J_1) \le f(J_2) \le \dots \le f(J_N)$. Nótese que Bäck utiliza una función de aptitud "invertida" donde el mejor individuo tiene el índice más bajo. Para comparar con nuestros resultados, transformamos la tarea en una de maximización usando $j = N - i + 1$:

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

Esta fórmula es un caso especial de (4) con todos los individuos teniendo un valor de aptitud diferente. Entonces $s(f_i) = 1$ para todo $i \in [1, N]$ y $S(f_i) = i$, y $p_i = \frac{s^*(f_i)}{N}$ produce la misma ecuación dada por Bäck. Nótese que esta fórmula no es válida si algunos individuos tienen el mismo valor de aptitud.

---

3.1 DESCRIPCIÓN USANDO DISTRIBUCIÓN CONTINUA

Ahora describiremos la distribución $s(f)$ como una distribución continua $\bar{s}(f)$, lo que permitirá derivar las siguientes propiedades de manera más sencilla. Para ello, asumimos valores de aptitud distribuidos continuamente. El rango de la función $\bar{s}(f)$ es $f_0 < f \le f_n$, utilizando la misma notación que en el caso discreto.

Denotamos todas las funciones en el caso continuo con una barra, por ejemplo, escribimos $\bar{s}(f)$ en lugar de $s(f)$. Las sumas similares se reemplazan por integrales, por lo tanto:

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

denota la distribución de aptitud acumulada continua.

Teorema 3.2 Sea $\bar{s}$ la distribución de aptitud continua de la población. Entonces la distribución de aptitud esperada $\bar{\Omega}_T(\bar{s}, t)$ después de realizar la selección por torneo con tamaño $t$ es:

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

Prueba: De forma análoga a la prueba del caso discreto, la probabilidad de que un individuo con aptitud $f$ o peor gane el torneo viene dada por:

$\bar{S}^*(f) = N \left( \frac{\bar{S}(f)}{N} \right)^t \quad (9)$

Como $\bar{s}^*(f) = \frac{d\bar{S}^*(f)}{df}$, obtenemos (8).

La Figura 3 muestra las distribuciones resultantes después del torneo si la distribución inicial es una distribución Gaussiana $G(\mu, \sigma)$ con $G(\mu, \sigma)(x) = \frac{1}{\sqrt{2\pi}\sigma} e^{-\frac{(x-\mu)^2}{2\sigma^2}}$.

distribución $\bar{s}_G(f) = N G(\mu, \sigma)(f)$ con $\sigma = 30, \mu = 100, N = 1000$ y $f_0 = -\infty, f_n = +\infty$. Las distribuciones resultantes después del torneo con tamaños de torneo 2, 5 y 10 se muestran en la región de interés $f \in [0, 200]$.

• Eje Y ($s(f)$): Frecuencia de individuos.

• Eje X ($f$): Valores de aptitud (fitness).

• Descripción: La distribución de aptitud Gaussiana conduce aproximadamente de nuevo a distribuciones Gaussianas tras el torneo. De izquierda a derecha: Distribución inicial; Distribución tras Selección por Torneo con tamaño $t = 2, t = 5, t = 10$.

---

4. PROPIEDADES DE LA SELECCIÓN POR TORNEO

4.1 CONCATENACIÓN DE FASES DE SELECCIÓN POR TORNEO

Una propiedad interesante de la selección por torneo es la concatenación de varias fases de selección. Supongamos una población arbitraria con la distribución de aptitud $\bar{s}$. Aplicamos primero una selección por torneo con tamaño $t_1$ a esta población y luego, sobre la población resultante, otra selección por torneo con tamaño $t_2$ (sin recombinación entre ellas). La distribución de aptitud obtenida es la misma que si se aplicara una sola selección por torneo con tamaño $t_1 t_2$ a la distribución inicial $\bar{s}$.

Teorema 4.1 Sea $\bar{s}$ una distribución de aptitud y $t_1, t_2 \ge 1$ dos tamaños de torneo. Entonces se cumple la siguiente ecuación:

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

Prueba:

$\bar{\Omega}_T(\bar{\Omega}_T(\bar{s}, t_1), t_2)(f) = t_2 \bar{\Omega}_T(\bar{s}, t_1)(f) \left( \frac{1}{N} \int_{f_1}^f \bar{\Omega}_T(\bar{s}, t_1)(x) \, dx \right)^{t_2-1} = \text{}$

$t_2 t_1 \bar{s}(f) \left( \frac{1}{N} \int_{f_1}^f \bar{s}(x) \, dx \right)^{t_1-1} \cdot \left( \frac{1}{N} \int_{f_1}^f t_1 \bar{s}(x) \left( \frac{1}{N} \int_{f_1}^x \bar{s}(y) \, dy \right)^{t_1-1} dx \right)^{t_2-1} \text{}$

Como

$\int_{f_1}^f t_1 \bar{s}(x) \left( \frac{1}{N} \int_{f_1}^x \bar{s}(y) \, dy \right)^{t_1-1} dx = N \left( \frac{1}{N} \int_{f_1}^f \bar{s}(x) \, dx \right)^{t_1} \text{}$

podemos escribir

$\bar{\Omega}_T(\bar{\Omega}_T(\bar{s}, t_1), f), t_2, f) = t_2 t_1 \bar{s}(f) \left( \frac{1}{N} \int_{f_1}^f \bar{s}(x) \, dx \right)^{t_1-1} \cdot \left( \left( \frac{1}{N} \int_{f_1}^f \bar{s}(x) \, dx \right)^{t_1} \right)^{t_2-1} = \text{}$

$t_2 t_1 \bar{s}(f) \left( \frac{1}{N} \int_{f_1}^f \bar{s}(x) \, dx \right)^{t_1 t_2-1} = \bar{\Omega}_T(\bar{s}, t_1 t_2)(f) \text{}$

En [Goldberg y Deb, 1991] la proporción $P_\tau$ de los mejores individuos después de $\tau$ selecciones con tamaño de torneo $t$ (sin recombinación) se da por:

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

Esto puede obtenerse como un caso especial del Teorema 4.1.

Corolario 4.1 Sea $\bar{s}(f)$ una distribución de aptitud representable como:

$\bar{s}(f) = \beta g(f) \left( \frac{\int_{f_1}^f g(x) \, dx}{N} \right)^{\beta-1} \quad (12) \text{}$

con $\beta \ge 1$ y $\int_{f_1}^{f_n} g(x) \, dx = N$. Entonces la distribución esperada tras el torneo con tamaño $t$ es:

$\bar{s}^*(f) = \beta t g(f) \left( \frac{\int_{f_1}^f g(x) \, dx}{N} \right)^{\beta t-1} \quad (13) \text{}$

Prueba: Si asumimos que $\bar{s}(f)$ es el resultado de aplicar la selección por torneo con tamaño $\beta$ sobre la distribución $g(f)$, (13) se obtiene directamente usando el Teorema 4.1. $\square$

relatedInteligencia Artificial