ALGORITMOS GENÉTICOS

En casuísticas donde el número de posibilidades es inmenso y probarlas todas lleva un tiempo y capacidad de cómputo del que no se dispone, los algoritmos genéticos permiten encontrar una buena solución en un tiempo razonable.

Aunque las máquinas son cada vez más potentes y pueden procesar gran cantidad de operaciones por segundo, hay tareas que sobrepasan sus límites. Muchos de los problemas que se plantean en entornos de trading tienen un número de combinaciones exponencial que hace que su cálculo consuma más tiempo del que se dispone para su resolución. Hablamos de horas, días… incluso meses o años.

Un ejemplo simple puede mostrar la problemática de intentar abordar problemas exponenciales, incluso con los equipos más potentes o usando entornos de programación distribuida. Los sistemas automáticos tienen un número variable de parámetros que pueden tomar, cada uno, un conjunto de valores que se seleccionen previamente. Buscar el mejor conjunto de parámetros de un sistema puede ser un problema con un coste computacional enorme, dependiendo del número de parámetros y del número de valores que se permita que tenga cada parámetro.

Como se puede apreciar en la tabla 1, optimizar un sistema con pocos parámetros y permitiendo un conjunto pequeño de valores para cada parámetro es factible pero cuando crecen ambos valores se vuelve inabordable. Si evaluar un sistema requiere de 10 segundos, el último caso de la tabla necesitaría casi 10.000 años para evaluar todas las combinaciones posibles.

Cuando el conjunto de combinaciones es enorme, es decir, el espacio de búsqueda es muy amplio, obtener una buena solución en un tiempo aceptable es preferible a obtener la mejor solución en un tiempo inaceptable. Y esto es trabajo para los algoritmos genéticos.

Las bases

Los algoritmos genéticos se basan en propiedades de la genética y es importante entender algunas claves para poder desarrollar un algoritmo genético eficiente. Un cromosoma está compuesto por un conjunto de genes. El cromosoma representa a un individuo y el gen una propiedad del mismo como el color de ojos o la estatura.

De la genética sabemos que de dos padres altos hay una alta probabilidad de que el hijo sea también alto pues los genes del hijo reciben información de los genes de los padres. También sabemos que pueden producirse mutaciones que alteran el orden general existente en la transmisión de genes entre padres e hijos. La mutación modifica genes y hace que ciertas propiedades del hijo sean totalmente distintas a las de sus padres, para bien o para mal.

La selección natural hace el resto: los padres fuertes suelen tener hijos fuertes que se mantendrán en la siguiente generación. Los débiles tienen menos probabilidades de sobrevivir aunque si se cruzan con una pareja fuerte o tienen mutaciones beneficiosas puede aumentar la probabilidad de que sus hijos sobrevivan en la siguiente generación.

Es muy importante que las claves anteriores se cumplan cuando se diseña un algoritmo genético. Si, por ejemplo, dos padres fuertes no tienen más probabilidad de generar hijos fuertes que dos padres débiles, implementar un algoritmo genético seria, a efectos prácticos, una búsqueda aleatoria.

Teoría de algoritmos genéticos

El funcionamiento de un algoritmo genético es como sigue:

• Se parte de una población inicial de individuos/cromosomas, normalmente aleatoria.

• Se clasifican los individuos según el criterio a optimizar.

• Se seleccionan los individuos que van a combinarse. Los mejores individuos tienen mayor probabilidad de cruzarse pues interesan sus propiedades más que las de un individuo peor.

• Se combinan los individuos seleccionados. Generalmente, de cada dos padres se obtienen dos hijos.

• Se mutan aleatoriamente varios genes de algunos individuos.

• Se eliminan individuos originales (algunos o todos) y se reemplazan por los nuevos.

• Se repite el ciclo hasta que se cumpla la condición de parada.

Cuando se combinan dos individuos, los hijos suelen ser parecidos a los padres, es decir, pertenecen a la misma zona de búsqueda. Podemos explorar estas zonas de forma intensa, dando más probabilidad de reproducirse a los mejores y limitando las mutaciones. De esta forma se llega a la mejor solución rápidamente pero es la mejor solución de esa zona, no de todas las combinaciones existentes. Si, por el contrario, permitimos algo más de margen de reproducción a los débiles y aumentamos la probabilidad de que se produzcan mutaciones, exploramos más zonas (buscamos en más sitios) pero tardamos más en localizar los mejores resultados de cada zona.

En la figura 1 vemos una gráfica donde el eje X representa distintos cromosomas (por ejemplo, juegos de parámetros de un sistema) y el eje Y la bondad de los mismos (el beneficio del sistema). Si evaluamos individuos en la zona 1 y el genético está configurado para converger rápido (penalizando mucho a los individuos menos aptos), rápidamente se llegará al máximo, anotado con un 2. Pero con dicha configuración, es menos probable que se llegue a explorar otra zona donde puede haber una solución mejor, como la óptima marcada con una M.

La probabilidad de cruce y mutación son parámetros que el usuario puede configurar para determinar cómo quiere que se comporte el algoritmo, el grado de convergencia que desea.

La condición de parada puede ser que pase cierto tiempo, que se obtenga una solución aceptablemente buena, que se generen X generaciones sin que ningún individuo mejore al mejor actual, etc.

Optimización de sistemas

Un sistema automático tiene un número de parámetros que pueden tomar un conjunto de valores dado. Vamos a diseñar un algoritmo genético para encontrar un buen conjunto de parámetros.

Primer paso: Determinar cuál va a ser la función de evaluación, la que puntúa la bondad de un individuo. Puede ser el beneficio, el riesgo, el draw down o una combinación de distintas propiedades. Por ejemplo, podríamos determinar la bondad de un sistema en función del beneficio neto penalizado si el draw down es grande.

Esta función se invoca para evaluar a todos los individuos generados por lo que es recomendable que su cálculo sea lo más eficiente y rápido posible.

Segundo paso: Codificar el sistema como un cromosoma. Aunque la codificación binaria es bastante frecuente, para este problema concreto, tiene más sentido usar una codificación en coma flotante, con números reales. Así, un individuo se codifica con un array con tantos elementos como parámetros del sistema se optimicen. Por ejemplo, un individuo para un sistema donde se optimizan 4 parámetros podría ser [1.2, 14, 35, 3.5]. Los genes son el valor concreto de cada parámetro del sistema.

Tercer paso: Desarrollar el operador de cruce. La forma de mezclar individuos para generar dos hijos a partir de dos padres puede variar de unas implementaciones a otras. Lo más común es el cruce en un punto, donde varios genes de un cromosoma se intercambian con los del otro cromosoma.

Para ello se selecciona un punto de cruce y se intercambian los genes en ese punto entre los cromosomas, tal como se aprecia en la figura 2.

Cuarto paso: Desarrollar el operador de mutación. En codificaciones binarias, la mutación se limita a cambiar algunos ceros por unos y/o viceversa. En una codificación como la del presente ejemplo, la mutación debe modificar el valor de uno (o varios, dependiendo de lo intensa que sea la mutación) de los parámetros del sistema y establecer un valor aleatorio para el mismo.

Quinto paso: Generar una población inicial. El tamaño de esta población hay que elegirlo teniendo en cuenta el número total de combinaciones posibles. Generar individuos aleatorios es tan sencillo como generar los 4 valores anteriores de forma aleatoria con un generador de números aleatorio.

Sexto paso: Evaluar cada individuo con la función de evaluación para conocer su bondad. Es decir, aplicar el sistema en el histórico y calcular el valor de la función elegida.

Séptimo paso:

• Se seleccionan los individuos que van a combinarse. Los mejores individuos tienen mayor probabilidad de cruzarse pues interesan sus propiedades más que las de un individuo peor.

• Se combinan los individuos seleccionados. Generalmente, de cada dos padres se obtienen dos hijos.

• Se mutan aleatoriamente varios genes de algunos individuos.

• Se seleccionan los individuos a eliminar de la población (los menos aptos con mayor probabilidad) y se sustituyen por los generados anteriormente.

• Se repite el ciclo hasta que se cumpla la condición de parada.

En la siguiente imagen se puede apreciar mejor cómo funciona el algoritmo. Los individuos en blanco son individuos sin evaluar (no sabemos si son mejores o peores). Los distintos colores representan distintos valores de bondad del individuo. Por poner un criterio, de mejor a peor se codifica con los colores azul, verde, naranja, rojo y negro. Tras evaluar a los individuos, se seleccionan varios para cruzarse y algunos de ellos sufren también mutaciones. Se seleccionan individuos en la población inicial para ser reemplazados por los nuevos y se empieza de nuevo.