Los sistemas de trading tienen con frecuencia una cantidad importante de parámetros que hay que ajustar o establecer para tener una versión concreta del sistema. Los traders experimentados suelen desarrollar un sexto sentido para estos ajustes basándose sobre todo en el sentido común y la gran experiencia adquirida con los años en la profesión. ¿Será posible aplicar esto en el trading sistemático? La optimización combinatoria puede darnos la solución.
El conocimiento en profundidad del problema de la optimización desde un punto de vista científico ayudará, sin duda, al trader a tener una visión más precisa del problema que hay que resolver y una perspectiva más amplia de todas las técnicas a su alcance. Además tenemos un punto a nuestro favor, el problema de la optimización se aplica a todos los campos de la ingeniería. Por tanto los éxitos obtenidos en diversas aplicaciones de la ingeniería y que encontramos en nuestra vida cotidiana se pueden proyectar sobre los sistemas de trading.
Supongamos que hacemos una analogía de un sistema de trading con una función matemática. Ésta devuelve un valor cuando le aplicamos unos argumentos determinados. En el caso del sistema de trading, los argumentos de la función serían los parámetros del sistema y el valor devuelto sería el rendimiento del sistema al aplicarle unos datos históricos.
En matemáticas, la optimización se refiere a la búsqueda valores del dominio de una función que, al aplicar dicha función nos proyecte a un valor mínimo o máximo, según la tipología del problema a resolver, dentro del conjunto imagen. Es decir los parámetros de un sistema de trading que mejor rendimiento proporcionen.
Dentro de la optimización matemática, encontramos la rama de optimización combinatoria, que se aplica a las ciencias de la computación. Relaciona la investigación de operaciones, teoría de algoritmos y teoría de la complejidad computacional. También está relacionada con otros campos, como la inteligencia artificial e ingeniería de software. Los algoritmos de optimización combinatoria resuelven instancias de problemas difíciles en general, explorando el espacio de soluciones (usualmente grande) para estas instancias. Los algoritmos de optimización combinatoria logran esto reduciendo el tamaño efectivo del espacio, y explorando el espacio de búsqueda eficientemente.
ESPACIO DE BÚSQUEDA
En optimización, se refiere al dominio de la función a ser optimizada. En el caso de la optimización combinatoria se refiere al conjunto discreto: finito o infinito numerable; de todas las posibles soluciones candidatas a un problema.
De esta definición se concluye que la solución no tiene porqué ser única y que en caso de ser varias, son susceptibles de ser comparadas entre sí, y por ende, podemos encontrar unas soluciones “mejores” que otras bajo dicho criterio de comparación; e incluso, que siendo a priori candidatas, una vez comprobadas, son descartadas como solución porque no cumplen algunas de las restricciones del problema a resolver.
Un concepto que es muy fácil puede complicarse debido a varios factores, uno de ellos es obvio: si buscamos el mínimo de la imagen de una función, es porque no se conoce y esto puede provocar que no sepamos cuando lo encontremos, si realmente lo hemos obtenido: existe la posibilidad de haber encontrado un mínimo local.
Suponiendo que la imagen de la función es una coordenada de un espacio bidimensional y el rango de valores dentro del conjunto imagen fuese muy limitado, una simple representación gráfica podría ser suficiente para verificar que se ha obtenido dicho mínimo, en incluso encontrarlo a simple vista; pero normalmente un problema a ser optimizado es de cierta magnitud para que esto no sea posible.
Una alternativa a la inspección gráfica sería probar todos los valores dentro del dominio de la función, comparando los valores proyectados y guardando la solución que nos dé el menor valor hasta encontrar el mínimo valor proyectado.
Por otro lado, hay problemas que por su tipología tienen un espacio de búsqueda lo suficientemente extenso como para que el examen completo de dicho espacio sea inviable de forma exhaustiva; se traduce en un problema np-hard de optimización combinatoria donde escoger soluciones que proyecten un mínimo de la función en un espacio bidimensional (en el mejor de los casos), donde cada coordenada del hipercubo que forma el dominio, es una posible solución.
TÉCNICAS DE RESOLUCIÓN
Las técnicas exactas (enumerativas, exhaustivas, etc.) garantizan encontrar la solución óptima de cualquier problema. Serían los métodos idóneos si no tuvieran el inconveniente de la cantidad de tiempo necesario para la resolución. El tiempo crece exponencialmente con el tamaño del problema. En determinados casos, el tiempo de resolución podría llegar a ser de varios días, meses o incluso años, lo que provoca que el problema sea inabordable con estos métodos.
Las técnicas aproximadas sacrifican la garantía de encontrar el resultado óptimo a cambio de obtener una buena solución en un tiempo razonable. Se han venido desarrollando durante los últimos 30 años y se distinguen tres tipos: métodos constructivos, métodos de búsqueda local y las técnicas metaheurísticas. Los métodos constructivos suelen ser los más rápidos. Partiendo de una solución vacía, a la que se le va añadiendo componentes, generan una solución completa. Las soluciones ofrecidas suelen ser de muy baja calidad. Su planteamiento depende en gran parte del tipo de problema. Es muy difícil encontrar métodos de esta clase que produzcan buenas soluciones, y en algunas ocasiones es casi imposible, por ejemplo, en problemas con muchas restricciones.
Los métodos de búsqueda local usan el concepto de vecindario y se inician con una solución completa recorriendo parte del espacio de búsqueda hasta encontrar un óptimo local. El vecindario de una solución es el conjunto de soluciones que se pueden construir a partir de aquella aplicando un operador de modificación denominado movimiento. Estos métodos parten de una solución inicial, examinan su vecindario y eligen el mejor vecino continuando el proceso hasta que encuentran un óptimo local. En función del operador de movimiento utilizado, el vecindario cambia y el modo de explorar el espacio de búsqueda también, pudiendo la búsqueda complicarse o simplificarse.
Las técnicas metaheurísticas son algoritmos no exactos. Se fundamentan en la combinación de diferentes métodos heurísticos a un nivel más alto para conseguir un Sistema.
Una heurística es una técnica que busca soluciones buenas (óptimas o rondando el óptimo) a un coste computacional razonable, aunque sin garantizar la factibilidad de las mismas. En algunos casos ni siquiera puede determinar la cercanía al óptimo de una solución factible.
Las metaheurísticas se definen como métodos que integran de diversas maneras, procedimientos de mejora local y estrategias de alto nivel para crear un proceso capaz de escapar de óptimos locales y realizar una búsqueda robusta en el espacio de búsqueda. En su evolución, estos métodos han incorporado diferentes estrategias para evitar la convergencia a óptimos locales, especialmente en espacios de búsqueda complejos.
– EXACTAS
Técnicas para obtener todas las soluciones del problema. Búsqueda de soluciones por fuerza bruta o algunas variantes que acotan o reducen el espacio de búsqueda.
– HEURÍSTICAS
Las técnicas heurísticas son algoritmos específicos para el problema a resolver, que encuentran soluciones de buena calidad para problemas combinatorios complejos explotando el conocimiento del dominio de aplicación. Son fáciles de implementar y encuentran buenas soluciones con esfuerzos computacionales relativamente pequeños; sin embargo, renuncian (desde el punto de vista teórico) a encontrar la solución óptima global de un problema.
En problemas de gran tamaño rara vez un algoritmo heurístico encuentra la solución óptima global.
Requieren un conocimiento exhaustivo de las propias soluciones, dependientes de las entradas y específicas del problema.
– METAHEURÍSTICAS
Los algoritmos metaheurísticos son algoritmos de propósito general, que no dependen del problema, y que ofrecen buenos resultados pero que normalmente no acaban ofreciendo “la” solución óptima sino soluciones subóptimas. Se acostumbran a utilizar para aquellos problemas en que no existe un algoritmo o heurística específicos que los resuelva, o bien cuando no es práctico implementar dichos métodos; o bien es eficiente incorporar la técnica heurística dentro del “esqueleto” creado por la técnica metaheurística.
Resumen de características:
Una técnica metaheurística es una estrategia genérica de alto nivel que usa diferentes métodos heurísticos para explorar el espacio de búsqueda de gran tamaño, con el objetivo de encontrar una solución óptima o cercana al óptimo. Debe identificar rápidamente las regiones prometedoras del espacio de búsqueda global, y no malgastar tiempo en regiones que hayan sido exploradas y/o no contengan soluciones de alta calidad.
Exactas
Son técnicas que buscan todas las soluciones posibles; encuentran soluciones de óptimo global a cambio de empeorar el rendimiento, hasta el punto de que en problemas de complejidad exponencial, el tiempo necesitado para encontrar la solución óptima o posibles soluciones, es inviable.
Búsqueda por fuerza bruta
Es una técnica de optimización trivial pero efectiva en determinados casos, ya que se asegura que todas las soluciones posibles son encontradas, pues se barre todo el espacio de búsqueda.
La restricción en la aplicación de este sistema, es normalmente, porque el espacio de búsqueda es intratable computacionalmente en un tiempo factible para el problema a resolver.
Sí el espacio de búsqueda no es elevado y la función a optimizar tiene un rendimiento adecuado para responder todas las peticiones de evaluación en un tiempo razonable, podría ser una opción utilizar la búsqueda por fuerza bruta, pero generalmente este tipo de problemas tiene una complejidad exponencial en base al número de parámetros a optimizar.
Metaheurísticas
En la vida cotidiana, continuamente se presentan y resuelven problemas de optimización combinatoria. Los pequeños problemas se resuelven utilizando la lógica y pequeñas fórmulas matemáticas. Pero si los problemas presentan complejidad o son de una elevada magnitud se ha de recurrir al uso de computadores.
Uno de los principales objetivos de cualquier Ingeniería es el uso de métodos exactos y heurísticos para optimizar funciones objetivo. La optimización de estos problemas parte de un conjunto de datos y una serie de condiciones y limitaciones que dificultan la utilización de métodos exactos. La dificultad se presenta principalmente por la alta complejidad de los cálculos y la duración de éstos, en algunas ocasiones el tiempo de resolución está limitado.
Son diversos los problemas de optimización complejos y las limitaciones en su resolución, esto ha provocado el desarrollo de estas técnicas. Una metaheurística es un conjunto de conceptos que se usan para definir métodos heurísticos que pueden ser aplicados a una amplia variedad de problemas, es decir, es vista como un marco general algorítmico que se puede aplicar a diferentes problemas de optimización con mínimos cambios para ser adaptado a un problema específico.
Los algoritmos metaheurísticos son procedimientos iterativos que guían una heurística subordinada, combinando de forma inteligente distintos conceptos para explorar y explotar adecuadamente el espacio de búsqueda. Son algoritmos aproximados de optimización y búsqueda de propósito general. Son capaces de proporcionar muy buenas soluciones (no necesariamente la óptima pero sí aproximada) en tiempo y con recursos razonables.
Hay diferentes formas de clasificar estas técnicas: basadas en la naturaleza (algoritmos bioinspirados) o no basadas en la naturaleza, basadas en memoria o sin memoria, con función objetivo estática o dinámica, etc.
ALGORITMOS EVOLUTIVOS [AE]
Este grupo de técnicas se inspiran en la capacidad de la evolución de seres o individuos para adaptarlos a los cambios de su entorno. Cada individuo representa una posible solución.
El funcionamiento básico de estos algoritmos es el siguiente: La población se genera de forma aleatoria. Cada individuo de la población tiene asignado un valor de su bondad con respecto al problema considerado, por medio de una función de aptitud, capacidad, adaptabilidad o estado, también denominada con bastante frecuencia por la palabra inglesa “fitness”.
El valor de la aptitud de un individuo es la información que el algoritmo utilizar para realizar la búsqueda. La modificación de la población se efectúa mediante la aplicación de tres operadores:
selección, recombinación y mutación.
En estos algoritmos se pueden distinguir la fase de selección, explotación de buenas soluciones, y la fase de reproducción, búsqueda de nuevas regiones. Se debe de mantener un equilibrio entre estas dos fases. La política de reemplazo permite la aceptación de nuevas soluciones que no necesariamente mejoran las existentes.
ALGORITMOS GENÉTICOS [AG]
Son una técnica metaheurística de búsqueda basada en la teoría de la evolución biológica y del de selección natural, cuyos padres son Charles Darwin y Alfred Russel Wallace, dos naturalistas que de manera independiente. Desarrollada inicialmente por Holland en 1975, cuyo objetivo consistía en que las computadoras aprendieran por su cuenta; por tanto los inicios de los algoritmos genéticos no fueron planteados para la optimización combinatoria, sino para Inteligencia Artificial.
En la actualidad los [AG] han alcanzado una gran madurez y quizás sean reconocidos como el estado del arte en las técnicas metaheurísticas y una de las más empleadas en problemas de optimización combinatoria. Incluso se usan de referencia para la validación de otras técnicas de búsqueda no exhaustiva.
El [AG] se basa en los mecanismos de selección natural de los procesos biológicos; de acuerdo con esto, los individuos más aptos de una población son los que sobreviven y adaptan a los cambios del entorno. Esta adaptación se fundamenta en las leyes postuladas por Mendel, donde el cruce de dos individuos produce otro con características de ambos progenitores, donde las características dominantes son las que se manifiestan en el individuo.
Hasta ahora hemos visto el modelo que inspiró el concepto de [AG], pero a alto nivel de abstracción, se basa en la transformación de un conjunto de objetos individuales con respecto al tiempo usando operaciones modeladas de acuerdo al principio de reproducción y supervivencia del más apto, tras haberse presentado de forma “natural” una serie de operaciones “genéticas” de entre las que destaca la recombinación. Cada uno de estos objetos matemáticos suele ser una cadena de componentes básicos, o parámetros, que se ajusta al modelo de las cadenas de cromosomas, y se les asocia con una cierta función matemática que refleja su aptitud (fitness).
En la resolución de un problema mediante un algoritmo genético se realiza la elección y codificación de las variables, se aplican métodos evolutivos: selección y reproducción con intercambio de información incluyendo alteraciones pseudo-aleatorias (mutaciones) que generan diversidad.
La población está formada por una serie de individuos o partículas que pueden ser posibles soluciones del problema. Las partículas se representan como un conjunto de parámetros denominados genes, los cuales agrupados forman cadenas de valores denominadas cromosomas. La adaptación de un individuo depende de la evaluación de cada cromosoma usando la función de aptitud que refleja el nivel de adaptación al problema de la partícula representado por el cromosoma.
BÚSQUEDA DISPERSA [BD]
Scatter Search en inglés, se basa en mantener un conjunto relativamente pequeño de soluciones, conjunto de referencia, que contiene buenas soluciones y otras soluciones diversas. A los diferentes subconjuntos de soluciones que se forman se les aplica operaciones de recombinación y mejora. Los conceptos y principios fundamentales del método, fueron propuestos a comienzo de la década de los setenta, basados en las estrategias para combinar reglas de decisión, especialmente en problemas de secuenciación, así como en la combinación de restricciones (como el conocido método de las restricciones subrogadas).
La [BD] se basa en el principio de que la información sobre la calidad o el atractivo de un conjunto de reglas, restricciones o soluciones puede ser utilizado mediante la combinación de éstas. En concreto, dadas dos soluciones, se puede obtener una nueva mediante su combinación de modo que mejore a las que la originaron.
Las poblaciones suelen ser muy pequeñas y se basan en la especialización de sus individuos a través de la combinación de dos de ellos para conseguir otro más adecuado, pero no se basa en procesos aleatorios ni en poblaciones más grandes como otras técnicas evolutivas como puede ser [AG].
ALGORITMOS BASADOS EN COLONIAS DE HORMIGAS [ACO]
Los sistemas basados en Colonias de Hormigas [ACO] se inspiran en el comportamiento de las hormigas en la búsqueda de alimento. Inicialmente, las hormigas exploran un área cercana al hormiguero de forma aleatoria. Cuando una hormiga encuentra comida la lleva de vuelta al hormiguero. En el camino, la hormiga va depositando una sustancia química denominada feromona que guía al resto de hormigas a encontrar la comida. El rastro de feromona sirve a las hormigas para encontrar el camino más corto entre el hormiguero y la comida. Cuanto más veces una hormiga tras conseguir éxito pase por un camino dejando el rastro de hormona, más fuerte es dicho rastro dando a entender al resto de hormigas que ese camino lleva a una fuente mayor de comida; o dicho de otro modo, la probabilidad de encontrar comida siguiendo ese rastro es mayor que el de otro con menos intensidad del rastro.
Este sistema se modela normalmente mediante un grafo, donde a cada arista le corresponde un peso, determinado por las veces que una “hormiga” tuvo éxito siguiendo ese camino, y los vértices del grafo son zonas de soluciones óptimas.
ALGORITMOS BASADOS EN NUBES DE PARTÍCULAS
Los Algoritmos Basados en Nubes o Enjambres de Partículas, más conocidos por su término en inglés: Particle Swarm Optimization [PSO] son técnicas metaheurísticas inspiradas en el comportamiento del vuelo de las bandadas de aves o el movimiento de los bancos de peces. La toma de decisión por parte de cada individuo o partícula se realiza teniendo en cuenta una componente social y una componente individual, mediante las que se determina el movimiento de esta partícula para alcanzar una nueva posición.
Los algoritmos basados en nubes (enjambre o cúmulos) de partículas se aplican en diferentes campos de investigación para la optimización de problemas complejos. Como ya se ha dicho anteriormente, el algoritmo [PSO] es una técnica metaheurística poblacional basada en la naturaleza (algoritmo bio-inspirado), en concreto, en el comportamiento social del vuelo de las bandadas de aves y el movimiento de los bancos de peces (cardumen).
Es una técnica relativamente reciente desarrollado originalmente en Estados Unidos por el sociólogo James Kennedy y por el ingeniero Russ C. Eberhart en 1995.
Tal es el auge que está tomando la [PSO] dentro de la Inteligencia Artificial que hasta el novelista y productor de cine y televisión ya fallecido, Michael Crichton, escritor de best-sellers y considerado padre de los techno-thrillers como Jurassic Park, basa su novela Prey en la Inteligencia Artificial basada en Enjambre de Partículas.