9.8.3 XCS: sistema clasificador genético

Es un sistema clasificador reciente que difiere con los anteriores en lo siguiente:

• La aptitud de un clasificador se basa en la precisión de la predicción de pago más que en la predicción misma.
• El algoritmo genético actúa sobre los conjuntos de acciones en lugar de la población en su conjunto.
• XCS no tiene lista de mensajes y es sólo aplicable a ambientes Markovianos.

Al igual que otros clasificadores, el ambiente da una entrada sensorial del tipo $\sigma(t) \in \{0,1\}^L$. El sistema responde con una acción $\alpha(t) \in \{a_1, \ldots, a_n\}$. Cada acción recibe una recompensa escalar $\rho(t)$ asociada.

Los problemas pueden ser de un solo paso (las situaciones sucesivas no están relacionadoas entre si) o de varios pasos (sí están relacionadas).

XCS tiene una población de clasificadores cada uno siendo una regla del tipo condición-acción con la siguiente información:

• Condición $C \in \{0,1,\char93 \}^L$.
• Acción $A \in \{a_1, \ldots, a_n\}$.
• Predicción $p$ que es la recompensa esperada si se usa este clasificador.

También se puede guardar, el error en la predicción ($\epsilon$), la aptitud ($F$) del clasificador, la experiencia ($exp$), que es el número de veces que ha estado en el conjunto de acciones, la última vez que se usó, el tamaño promedio de los conjuntos de acciones a los que ha pertenecido ($as$), el número de clasificadores que este clasificador representa ($n$).

Se consideran cuatro conjuntos en XCS:

• La población de clasificadores $[P]$.
• El conjunto de clasificadores $[M]$ que aparea la situación actual $\sigma(t)$.
• El conjunto de acciones $[A]$ con los clasificadores que proponen una acción.
• El conjunto de acciones anterior $[A]_{-1}$.

La población inicial puede estar vacía o llenarse con $N$ clasificadores generados aleatoriamente. La diferencia entre los dos enfoques es poca, por lo que en general se empieza con un conjunto vacío.

Cuando se recibe una señal de entrada se seleccionan todos los clasificadores que aparean la situación ($[M]$). Se ve para cada posible acción cual es su predicción de pago. Se selecciona una acción $a_i$ tomando en cuenta esta predicción y se seleccionan todos los clasificadores que proponen dicha acción $[A]$.

La acción ganadora se ejecuta y el conjunto de acciones previo $[A]_{-1}$ (en caso de problemas de multiples pasos) se modifica usando un esquema parecido a Q-learning. El algoritmo viene descrito en la tabla 9.2.

Tabla 9.2: Algoritmo de XCS.

Al momento de generar el conjunto de clasificadores que aparea la situación (MATCH SET), si el número de acciones presentes en $[M] < \theta$ (un cierto umbral que se tiene que definir), entonces se crea un nuevo clasificador que aparea las condiciones del ambiente ($\sigma(t)$) y que contiene don't cares (#) con cierta probabilidad ($P_{\char93 }$). La acción del clasificador se selecciona aleatoriamente entre las que no están presentes en $[M]$.

Para generar el PREDICTION ARRAY ($[PA]$), se suma la multiplicación de la predicción de cada acción que aparece en $[M]$ por su aptitud, y el total se divide entre el total de las aptitudes de las $[M]$ que tienen esa acción. Osea que todas las predicciones y aptitud de las acciones iguales que aparecen en $[M]$ se consideran para regresar la predicción de cada acción.

Tomando en cuenta $[PA]$, la selección de la acción ($acc$) puede hacerse con $\epsilon-$greedy (aunque puede hacerse de otras formas).

El ACTION SET son todos los clasificadores en $[M]$ cuya acción es $acc$.

El pago de cada clasificador es una combinación de recompensa inmediata y del estimado de la máxima recompensa en el siguiente estado.

La actualización de los parámetros de los clasificadores se hace en el siguiente orden: experiencia ($exp$), estimación de predicción ($p$), predicción de error ($\epsilon$), tamaño promedio del conjunto de acciones al que pertenece el clasificador ($as$), la aptitud ($F$). Esta actualización se hace como se ilustra en la tabla 9.3.

Tabla 9.3: Actualización de parámetros en XCS.

El algoritmo genético para generar nuevos individuos, se corre si se rebasa también un cierto umbral, que determina cuándo se uso la última vez el algoritmo genético. En tal caso, se seleccionan dos clasificadores tomados de $[A]$ usando ruleta, basados en su aptitud. Si se cruzan, su predicción, error y aptitud se toman como el promedio de sus padres.

Cruza sólo se aplica sobre las condiciones de los clasificadores, mientras que mutación se aplica sobre todo el clasificador. Si se muta una condición del clasificador, ésta debe de ser ó # ó un valor que aparea la información del ambiente.

Si se verifica por subsumsión, los hijos subsumidos por sus padres no se añaden y se aumenta la numerosidad al padre ($cl.n++$).

También se eliminan individuos seleccionados por ruleta y revisando que la numerosidad de los clasificadores sea mayor que $N$ ($cl.n > N$).

Si el clasificador seleccionado tiene una numerosidad mayor que 1, ésta se decrementa en 1, si es 1, se elimina el clasificador.

El criterio para eliminar clasificadores se hace si el clasificador tiene suficiente experiencia ( $cl.exp > \theta_{elim}$) y si su aptitud es menor que el promedio de aptitud de los clasificadores.

Debido a su conección con aprendizaje por refuerzo y análisis más teórico, XCS tiende a producir mejores y más compactos clasificadores.