Métodos de optimización: Algoritmos genéticos.
 
 
  • Usted está aquí:
  • Home
  • Optimización
  • Métodos de optimización: Algoritmos genéticos.

Métodos de optimización: Algoritmos genéticos.

 
TradingSys (AndG) - 16 Feb 2012
2 comentarios
 

tradingsysLa inmensa mayoría de los sistemas tienen parámetros. Los que no los tienen, es porque incorporan variables ocultas elegidas ad hoc para operar un determinado activo  o se han utilizado técnicas evolutivas para generar y elegir un conjunto óptimo de reglas.  En cualquier caso, tanto al diseñar como al evaluar una estrategia, nunca nos veremos libres del problema de la optimización. Ya que, en definitiva, optimizar no es más que elegir, entre todas las alternativas posibles, aquellas que se acomodan mejor a un problema específico.

 

1.- INTRODUCCIÓN


En la actualidad las principales plataformas de trading cuentan  con un auténtico arsenal de herramientas para evaluar y optimizar sistemas y, en algún caso, portfolios enteros.  Soportan numerosas modalidades de operativa, permitiendo la gestión simultánea de varias cuentas, líneas de datos y brokers en entornos de creciente complejidad en los que trabajar con gráficos de minutos,  incluso de ticks, suele ser habitual. Todo esto conduce a que el volumen de información necesario (diversidad de activos, tamaño de los históricos) para construir y evaluar sistemas adquiera un tamaño tan desmesurado que los métodos de optimización tradicionales, basados en algoritmos búsqueda exhaustiva o en programación matemática (lineal, cuadrática, mixta, gradientes), acaben dejando paso a métodos heurísticos y evolutivos  entre los que destacan los algoritmos genéticos.

Los algoritmos genéticos son un recurso común en ámbitos tan dispares como la Ingeniería, la Medicina, la Astrofísica, las Telecomunicaciones o la Economía.  Y, en general, en todas aquellas actividades en las que el data mining y la resolución de problemas complejos de tipo no lineal tengan alguna importancia. Un ejemplo temprano de este método de optimización lo encontramos en la búsqueda de conexiones óptimas en grandes redes (Comunication Networks, Walke, I.B, 1996):

 

tradingsys

 

En general podemos definir los algoritmos evolutivos como métodos robustos de optimización diseñados para resolver problemas complejos con elevado número de elementos, restricciones y variables y en los que, por lo general, coexisten una o varias soluciones optimas que no pueden aproximarse por los métodos tradicionales propios de la programación lineal (como el famoso algoritmo Simplex. Dantzing, 1940) que utilizan aplicaciones tan populares como el Solver de Excel.

El tipo de problemas característico de estos algoritmos es aquel en el que partiendo de una población de "n" individuos (estrellas conocidas de la galaxia, historiales clínicos, incidencia de accidentes de tráfico, hábitos de consumo, históricos de cotizaciones, etc.) se busca un conjunto de parámetros que minimicen o maximicen una función de adaptación (fitness) u objetivo diana.  Como en los algoritmos clásicos, el proceso se realiza en sucesivos pasos o iteraciones en las que se van combinando y seleccionando aquellos juegos de parámetros qué más se aproximen al criterio establecido. Siendo la principal diferencia el método meta-heurístico de búsqueda y selección de los mejores parámetros. En definitiva, estamos ante métodos no determinísticos que permiten llegar a soluciones distintas recorriendo innumerables caminos y bifurcaciones en cada optimización.

Por otra parte los algoritmos genéticos consiguen eludir mejor el problema del curve fitting ya que, a diferencia de otros métodos de optimización en los que iterando de manera lineal se avanza hacia una solución  única (siempre la misma) determinada  por el criterio diana elegido, en los algoritmos evolutivos se mantiene una población de posibles candidatos potenciales que cubre una amplia "región de valor" (o zona robusta). Esta diversidad de soluciones alternativas y viables, unida a la presencia de mecanismos para evitar caer en lo que se denomina  "local optimun", es un factor determinante para minimizar el riesgo de sobreoptimización.

Una conocida técnica para evaluar el riesgo del  curve fitting es la de los mapas de optimización 3D. Las zonas elevadas o mesetas representan regiones óptimas en el espacio de búsqueda mientas que las concavidades o depresiones serían las combinaciones paramétricas menos eficientes.

 

tradingsys


 

Los picos escarpados son "óptimos locales" o soluciones de caso único cuyo valor predictivo es muy escaso ya que resulta extremadamente improbable que las configuraciones de datos que las provocan se puedan repetir en el futuro.

 

tradingsys

 

 

2.- TIPOLOGÍA Y CARACTERÍSTICAS DE LOS ALGORITMOS GENÉTICOS.


En función del tipo de problema a evaluar existen dos tipos de algoritmos:

 

1.- Algoritmo genético simple. Se aplica a problemas de optimización en los que partimos de una población finita y bien definida, la función objetivo converge hacia una solución óptima y los parámetros a evaluar son de tipo continuo.  Es el tipo de algoritmo más empleado y fácil de programar. La práctica totalidad de las plataformas de trading implementan algoritmos de este tipo ya que estructuralmente se acomodan muy bien a nuestro problema específico: Cómo encontrar una combinación robusta de parámetros para un determinado activo o cesta de activos. En nuestro caso los elementos a considerar son:

- Un conjunto finito de datos procedentes de cotizaciones históricas.

- Un conjunto finito y acotado de parámetros: cada parámetro tiene unos valores máximo, mínimo y salto bien definidos.

- Una función objetivo escalable y lineal: Maximizar el beneficio, el net profit, el ratio de Sharpe, el SQN, minimizar el drawdown, etc.

El tipo de solución al que se llega con este algoritmo consiste en encontrar un "óptimo global" o combinación paramétrica de máximo rendimiento que satisfaga el criterio diana elegido.

 

2.- Algoritmos genéticos paralelos. Normalmente se utiliza en ámbitos en los que se precisa localizar múltiples soluciones derivadas de la aplicación concurrente de varias funciones objetivo. El resultado es que la optimización no converge hacia un máximo global, sino hacia varias soluciones igualmente válidas. Estos algoritmos funcionan evaluando y manteniendo subespecies (o "nichos de población") que evolucionan con criterios diferentes y compiten entre sí. La programación de estos algoritmos es más compleja, ya que ahora los elementos que se requieren son:

- Un conjunto, acotado o no, de parámetros o variables de decisión.

- Un conjunto de funciones objetivo que se aplican en paralelo.

- Un conjunto de restricciones que son funciones de las variables de decisión.

Las restricciones, que pueden aplicarse a algunas o todas las funciones objetivo, determinan los caminos o bifurcaciones factibles que puede seguir el proceso de optimización. De este modo, cada camino converge hacia una solución alternativa. Por ejemplo, en el ámbito de la optimización de sistemas de trading podríamos considerar las siguientes restricciones: No considerar válidas soluciones  con menos de x operaciones, o las que generen una pérdida máxima de determinado valor, o aquellas que contengan meses con resultado negativo.

Tanto si hablamos de algoritmos simples o multiobjetivo, sus elementos  básicos son:  Universo, Individuos, genes, cromosomas, población, generación, método de selección, recombinación y mutación.

 

Veamos todo esto con un ejemplo práctico del trading sistemático:

Hemos construido un sistema intradiario para futuros sobre índices basado en bandas de Bollinger, con un filtro de volatilidad, horarios de inicio y fin de sesión y un MMStop porcentual. Queremos encontrar combinaciones paramétricas robustas aplicables a tres mercados europeos y tres americanos.


a) Universo: contexto de aplicación y espacio de búsqueda.
Históricos de cotizaciones de los 6 activos (Ej. FDAX, CAC40, FESX, TF, EMD y ES) en compresión de minuto y con una extensión de al menos 5 años. Como podrán imaginar el tamaño es descomunal al estar formado por cientos de miles o millones de puntos de datos, lo que ya de entrada, y a pocos parámetros que tengamos, invalida una optimización exhaustiva.

b) Individuo. Combinación única de valores paramétricos. (Ej. BollingerSMA = 26, Stdev =2, VolatFil = 1,4 HoraInicio = 9:00, HoraFin = 18:30, MMStop = 1,5%) La función fitness mide la bondad relativa de cada miembro de la población con respecto al criterio diana elegido.

c) Genes. Valores paramétricos individuales de cada miembro de la población. (Ej.  VolatFil = 1,4)

d) Cromosomas. Grupos de genes vinculados entre sí. En este caso tendríamos dos  directamente relacionados: Los valores del indicador de Bollinger (media y desviación) y el rango horario (HoraInicio y HoraFin).

e) Generación: Conjunto de individuos en cada etapa del proceso iterativo. El número de generaciones está vinculado al problema de la parada. Existen diversas de soluciones: La más simple es fijar manualmente el número al inicio de la optimización, siendo en este caso la solución optima el mejor valor de la función de adaptación (fitness) encontrado en los individuos de la última generación. Otra alternativa más elaborada consiste en establecer dos parámetros: el número mínimo de generaciones y otro número para detener el proceso cuando transcurren x generaciones sin encontrar individuos que contengan una solución mejor.

f)  Población: Número máximo de individuos en cada generación. Algunos dispositivos realizan una estimación automática del número idóneo de individuos en función de las variables del problema a evaluar, en otros casos debemos fijar manualmente este número.

g)  Método de selección.  El algoritmo genético comienza estimando una población inicial de n elementos generados aleatoriamente.  El desempeño de cada individuo es ponderado y rescaldado en relación a la población mediante la función fitness.  El siguiente paso es generar una nueva población que incorpore a los mejores individuos de la generación anterior junto a un porcentaje de individuos nuevos (esto generalmente es otro parámetro).  El cometido de un método de selección es orientar la búsqueda hacia aquellas soluciones que maximicen el criterio diana.  Se han desarrollado numerosas estrategias de selección : Proporcional, por rankings, muestreo estocástico, etc.

h) Recombinación (crossover). Es el mecanismo de recombinación genética. Representa el porcentaje de individuos que pasarán a la generación siguiente combinando el material genético de sus padres.  El resto, hasta completar el número requerido por el tamaño de la población, se elegirá aleatoriamente. 

 

tradingsys


 

I) Mutación. Mecanismo aleatorio para aumentar la diversidad de la población. Consiste en invertir ocasionalmente  un bit en la cadena binaria que representa el genoma de cada individuo. En los algoritmos genéticos simples tiene escasa importancia y se solapa con los procesos para generar y completar poblaciones, también aleatorios.

 

3.- CASO PRACTICO DE OPTIMIZACIÓN GENÉTICA CON NINJATRADER.

 

Independientemente del sistema a utilizar nuestro primer paso será construir y especificar:

 

a)   El modelo de optimización:

 

- Histórico: Base de datos de mercados, Time frame, tamaño.

- Parámetros: Valores máximo, mínimo y de salto.

- Pesos y restricciones: Plantilla de mercado, gastos de operativa, cierre a fin de día.

- Simulación de órdenes: algoritmo de llenado para órdenes limitadas y en stop, entradas por lado.

- Propiedades de cada orden: Gestión del tamaño de la posición, time in force.

 

tradingsys


 

La imagen superior corresponde a la configuración del modelo para un sistema intradiario aplicado el FBGL con 2 contratos. Al construir el modelo es muy importante ajustar adecuadamente los valores máximo, mínimo y de salto del cada parámetro.  Si la horquilla paramétrica es muy amplia en relación a los puntos de datos obtendremos mayor dispersión de resultados. Y, en el lado opuesto, cuando es muy estrecha, estaremos estrangulando la capacidad del algoritmo para conseguir mayor diversidad y potencial adaptativo.


b) Los parámetros del  optimizador genético.


NT7 no destaca precisamente por tener  un optimizador genético sofisticado y repleto de opciones. Por ejemplo, echamos en falta la posibilidad establecer restricciones condicionales sencillas que guíen al algoritmo en la búsqueda de soluciones óptimas. Aun así, funciona relativamente deprisa y permite obtener combinaciones paramétricas, en función de un repertorio bastante amplio de criterios diana. 

 

tradingsys


Los parámetros clave del optimizador son el número de generaciones (sorprende que no presente una estimación automática como hacen otras plataformas) y el tamaño de la población en cada generación. Cuanto mayor sea el valor de ambos parámetros más tiempo consumirá la optimización, pero obtendremos por lo general soluciones mejores.  También tiene importancia el ratio crossover que, como ya hemos visto, representa el porcentaje de individuos que pasan a la siguiente generación combinando el material genético de sus padres. Otros parámetros como los porcentajes de mutaciones (Mutation Rate) y de reposición de individuos (Reset Size) o el porcentaje de los mejores individuos que no se alteran (Stability Size) tienen importancia menor (salvo que los llevemos a extremos absurdos) y conviene dejar los valores por defecto.

En la imagen inferior mostramos el resultado de la optimización del sistema. En este caso el ratio diana elegido fue el SQN (System Quality Number).

 

tradingsys

 

El tiempo consumido fue de unos cuantos minutos, frente a las decenas de horas que posiblemente hubiésemos invertido con una optimización exhaustiva.

En las siguientes imágenes podemos ver la distribución de la población con la misma función objetivo después de 3,  9 y 18 generaciones.

 

tradingsys

 

La velocidad de convergencia hacia soluciones óptimas que satisfagan el criterio diana es bastante alta.  En 9 generaciones el algoritmo se aproxima un 92%  a la mejor solución.  Tenemos que esperar otras 9 generaciones más (hasta la 18) para incrementar la mejora hasta el 98%. En la generación 21 ya no obtenemos soluciones  mejores (al menos hasta la 26 en que decido terminar la prueba). Por lo que se puede decir que nuestro modelo ha alcanzado un máximo local. El máximo global estaría representado por los valores próximos a la línea R. de los gráficos.

Seguidamente vamos a evaluar el efecto del  mecanismo de Recombinación (crossover) en poblaciones con un número fijo de individuos (100) y de generaciones (9).

 

tradingsys

 

Los tres escenarios elegidos para el ratio crossover son:

 

- Recombinación = 10% .- En esta situación solamente un 10% de los individuos pasarán a la generación siguiente combinando sus valores por cruzamiento, mientras que los valores del 90% restante serán elegidos aleatoriamente. Como podemos observar los resultados son bastante mediocres ya que el componente aleatorio toma prácticamente el control del proceso de optimización genética.

- Recombinación = 50% .- En este caso cada generación está formada a partes iguales por miembros seleccionados por cruzamiento y aleatoriamente. En este caso obtenemos resultados mucho mejores que en la situación anterior y se alcanzan los óptimos locales más altos.

- Recombinación = 90%.- Solamente un 10% de los miembros son de procedencia aleatoria. Aunque se obtienen óptimos locales algo más bajos que en la situación anterior, los datos aparecen más agrupados y la línea de regresión tiene un valor más alto. Es decir, obtenemos un óptimo global mejor.

 

4.- CONCLUSIONES.


De este pequeño estudio podemos sacar las siguientes conclusiones:


1.- Los algoritmos genéticos constituyen una de las mejores alternativas para la optimización de sistemas de trading; en particular cuando el número de combinaciones paramétricas a evaluar y/o el tamaño de los datos históricos son muy grandes.

2.- Para obtener buenos resultados es necesario planificar cuidadosamente el modelo de optimización (valores de las horquillas paramétricas, criterio diana, datos históricos, restricciones, etc.) y configurar los parámetros idóneos del optimizador genético.

4.- Los parámetros que en mayor medida afectan al proceso de optimización son el número de generaciones y el tamaño de la población. En principio, cuanto más altos mejor;  si bien hay que tener en cuenta que a medida que aumentamos su número el tiempo consumido por el algoritmo de dispara.

5.- Siempre debemos contar con un criterio de parada. El más empleado consiste en detener   el proceso de optimización cuando ya no se consiguen mejores soluciones en varias  generaciones consecutivas (Ej. 5-9). En algunas aplicaciones el algoritmo se detiene de forma automática, en otras debemos aplicar el criterio manualmente.

6.- La tasa de recombinación también es un parámetro que puede contribuir a aumentar la calidad de las soluciones obtenidas. Encontramos las tasas de cruzamiento más favorables con valores del 70% al 90%.

7.- Otros parámetros, como las mutaciones o el porcentaje invariable de individuos por generación, resultarán menos determinantes (salvo valores extremos) en este tipo de optimizaciones .

 

 

Andrés A. García.

TradingSys.org, 2012.

 

 

 

Comentarios

 

flyscalper - Me viene al pelo

Excelente artículo Andrés, como siempre. 
 
Me viene muy bien además, porque acabo de adquirir el software Adaptrade Builder, y tu artículo me ayuda a conocer un poco más en profundidad cómo funciona este software que utiliza algoritmos genéticos esta vez no para optimizar un sistema, sino para buscar nuevos sistemas. 
 
Un saludo, 
 
Pablo

eab - Genial !!!

Excelente Andrés... excelente !

Añadir comentario

 
Modificado por TradingSys (AndG) - 16 Feb 2012
 
 

* Campos obligatorios

 
 

 
 

Secciones

 
 
 

Entradas recientes

 
 

Enlaces