Métodos de optimización de la biblioteca ALGLIB (Parte I)
212
0
Contenido
- Introducción
- Métodos de optimización de la biblioteca ALGLIB:
Introducción
El paquete estándar del terminal MetaTrader 5 incluye la biblioteca ALGLIB, una poderosa herramienta para el análisis numérico que puede resultar útil para los desarrolladores de sistemas comerciales. La biblioteca ALGLIB ofrece al usuario un amplio arsenal de métodos de análisis numérico, entre los que se incluyen:
- Álgebra lineal — resolución de sistemas de ecuaciones lineales, cálculo de valores propios y vectores, descomposición de matrices.
- Optimización — métodos de optimización univariante y multivariante.
- Interpolación y aproximación — interpolación polinómica y spline, aproximación de funciones mediante métodos de mínimos cuadrados.
- Integración y diferenciación numérica — métodos de integración (trapezoidal, Simpson, etc.), diferenciación numérica.
- Métodos numéricos para resolver ecuaciones diferenciales — ecuaciones diferenciales ordinarias y métodos numéricos.
- Métodos estadísticos — estimación de parámetros, análisis de regresión, generación de números aleatorios.
- Análisis de Fourier — transformada rápida de Fourier.
Los métodos de optimización determinista presentados en ALGLIB se basan en distintas variaciones del descenso de gradiente y permiten enfoques tanto analíticos como numéricos. En este artículo, nos centraremos en los métodos numéricos, ya que son los más adecuados para las tareas prácticas de los tráders.
Debemos señalar que muchas tareas en finanzas son de naturaleza discreta, ya que los datos de precios se representan mediante puntos individuales. Por ello, nos interesan especialmente los métodos que usan representaciones numéricas de los gradientes. El usuario no necesita calcular el gradiente: de esta tarea se encargan los métodos de optimización.
El dominio de los métodos de optimización ALGLIB suele plantear dificultades por la falta de unificación en los nombres de los métodos y el orden en que se recure a los mismos. El principal objetivo de este artículo consiste en subsanar las lagunas de información sobre la biblioteca y ofrecer ejemplos sencillos de uso. Ahora esbozaremos los términos y conceptos básicos para entender mejor para qué sirven estos métodos.
Optimización — proceso de búsqueda de la mejor solución bajo unas condiciones y restricciones dadas. La búsqueda implica que existen al menos dos opciones para resolver el problema, de las que hay que elegir la mejor.
Tarea de optimización — tarea en la que es necesario encontrar la mejor solución (máxima o mínima) a partir de un conjunto de opciones posibles que cumplen determinadas condiciones. Los elementos básicos de un problema de optimización son:
- La función objetivo (Objective Function o Fitness Function). Es la función que hay que maximizar o minimizar. Por ejemplo, la maximización de beneficios o la minimización de costes (el beneficio o el coste son los criterios de optimización).
- Variables. Son parámetros que pueden modificarse para obtener el mejor resultado.
- Restricciones. Estas son las condiciones que deben cumplirse para hallar una solución óptima.
La función objetivo puede ser cualquier función definida por el usuario que tome como entrada los parámetros (a optimizar) y ofrezca como salida un valor que sirva como criterio de optimización. Por ejemplo, una función objetivo puede ser la prueba de un sistema comercial con datos históricos, donde los parámetros de la función son los ajustes del sistema comercial, mientras que el valor de salida es la calidad requerida de su funcionamiento.
Tipos de restricciones:
- Restricciones de contorno (Boundary Constraints o Box Constraints) — restricciones impuestas a los valores de las variables; por ejemplo, la variable "x" solo puede estar comprendida entre 1 y 3.
- Restricciones de igualdad lineal (Linear Equality Constraints) — restricciones bajo las cuales una expresión con variables debe ser exactamente igual a algún número. Por ejemplo, (x + y = 5) es una igualdad lineal.
- Restricciones de desigualdad lineal (Linear Inequality Constraints) — condiciones bajo las cuales una expresión con variables debe ser menor o igual que (o mayor o igual que) algún número. Por ejemplo, (x - y >= 1).
En los ejemplos siguientes, solo consideraremos las restricciones de contorno. Así pues, el artículo revelará técnicas eficaces y una forma sencilla de usar los métodos de optimización de ALGLIB con ejemplos sencillos.
Como ejemplo de problema de optimización, usaremos una función objetivo sencilla que hay que maximizar. Es una función monótona suave con un único máximo: un paraboloide invertido. Los valores de esta función se encuentran en el rango [0; 1], independientemente del número de argumentos que pertenezcan al rango [-10; 10].
//—————————————————————————————————————————————————————————————————————————————— //Paraboloid, F(Xn) ∈ [0.0; 1.0], X ∈ [-10.0; 10.0], maximization double ObjectiveFunction (double &x []) { double sum = 0.0; for (int i = 0; i < ArraySize (x); i++) { if (x [i] < -10.0 || x [i] > 10.0) return 0.0; sum += (-x [i] * x [i] + 100.0) * 0.01; } return sum /= ArraySize (x); } //——————————————————————————————————————————————————————————————————————————————
BLEIC (Boundary, Linear Equality-Inequality Constraints)
BLEIC (Boundary, Linear Equality-Inequality Constraints), algoritmo de restricciones activas — nombre de una familia de métodos utilizados para resolver problemas de optimización con igualdades y desigualdades. El nombre del método procede de la clasificación de las restricciones, que se dividen en activas en el punto actual e inactivas. El método reduce un problema con restricciones en forma de igualdades e inecuaciones a una secuencia de subtareas restringidas únicamente por igualdades. Las desigualdades activas se tratan como igualdades, mientras que las inactivas se ignoran temporalmente (aunque seguimos monitoreándolas). En términos informales, el punto actual se desplaza por el conjunto admisible "pegándose" o "despegándose" de los límites.
1. Lo que hace es buscar el mínimo o el máximo de alguna función (por ejemplo, buscar el mayor beneficio o el menor coste), considerando diversas restricciones:
- Los límites de los valores de las variables (por ejemplo, el precio no puede ser negativo)
- Las igualdades (por ejemplo, la suma de las ponderaciones del portafolio debe ser igual al 100%)
- Las desigualdades (por ejemplo, el riesgo no debe superar un determinado nivel)
2. Cómo funciona — utiliza "memoria limitada", lo cual significa que no almacena todos los cálculos intermedios, sino solo los más importantes. Avanza hacia una solución gradualmente, paso a paso:
- Valora la situación actual
- Determina el sentido del movimiento
- Da un paso en esa dirección
- Comprueba que no se infrinjan las restricciones
- Si es necesario, corrige el movimiento
3. Características:
- Requiere que la función sea "suave" (sin saltos bruscos)
- Puede hallar un mínimo local en lugar de un mínimo global
- Es sensible al planteamiento inicial (punto de partida)
Un ejemplo sencillo: imaginemos que estamos buscando un terreno para construir una casa. En este caso, como en cualquier otro, existen restricciones: la casa debe tener un tamaño determinado (igualdad), no debe encontrarse a menos de X metros de los límites de la parcela (desigualdad), debe estar situada dentro de la parcela (condiciones de los límites). Queremos las mejores vistas posibles (función objetivo). El BLEIC "desplazará" progresivamente la casa imaginaria por la parcela, respetando todas las restricciones, hasta hallar la mejor ubicación en cuanto a las vistas. Encontrará más detalles sobre este algoritmo y sobre los siguientes en la página del autor de la biblioteca.
Para utilizar el método BLEIC y otros de la biblioteca ALGLIB, necesitaremos conectar un archivo (la biblioteca se proporciona con el terminal MetaTrader 5, el usuario no necesitará instalar nada adicional).
#include <Math\Alglib\alglib.mqh> Luego escribiremos un script, a saber, un ejemplo para trabajar eficientemente con los métodos ALGLIB. Tendremos que destacar los principales pasos característicos para trabajar con métodos ALGLIB, que resaltaremos bloques de código idénticos en el color correspondiente.
1. Luego definiremos las condiciones límite de la tarea, como el número de ejecuciones de la función de aptitud (función objetivo), los rangos de los parámetros a optimizar y su paso. Para los métodos ALGLIB, tendremos que asignar los valores iniciales de los parámetros optimizados "x" (los métodos son deterministas y los resultados dependerán totalmente de los valores iniciales, por lo que aplicaremos la generación de números aleatorios en el rango de parámetros de la tarea), así como la escala "s" (los métodos son sensibles a la escala de los parámetros entre sí, en este caso fijaremos la escala en "1").
2. A continuación, declararemos los objetos necesarios para que el algoritmo funcione.
3. Luego estableceremos los parámetros externos del algoritmo (ajustes).
4. Acto seguido, analizaremos el algoritmo transmitiendo al método los rangos y pasos de los parámetros a optimizar, así como los parámetros externos del algoritmo.
5. Después realizaremos la optimización.
6. Y finalmente obtendremos los resultados de la optimización para su uso posterior.
Hay un aspecto importante a considerar: el usuario no tiene forma de influir o detener el proceso de optimización en ningún momento. El método realizará todas las operaciones de forma independiente llamando a la función de aptitud dentro de su proceso. El algoritmo puede llamar a la función de aptitud un número aleatorio de veces (no hay forma de especificar este parámetro de parada para el método BLEIC), y el usuario solo podrá controlar por sí mismo el número máximo permitido de llamadas intentando transmitir forzosamente una orden de parada al método.
//—————————————————————————————————————————————————————————————————————————————— void OnStart () { // Инициализация параметров оптимизации--------------------------------------- int numbTestFuncRuns = 10000; int params = 1000; // Создание и инициализация массивов для границ диапазона--------------------- double rangeMin [], rangeMax [], rangeStep; ArrayResize (rangeMin, params); ArrayResize (rangeMax, params); for (int i = 0; i < params; i++) { rangeMin [i] = -10; rangeMax [i] = 10; } rangeStep = DBL_EPSILON; double x []; double s []; ArrayResize (x, params); ArrayResize (s, params); ArrayInitialize (s, 1); // Генерация случайных начальных значений параметров в заданных диапазонах---- for (int i = 0; i < params; i++) { x [i] = rangeMin [i] + ((rangeMax [i] - rangeMin [i]) * rand () / 32767.0); } // Создание объектов для оптимизации------------------------------------------ C_OptimizedFunction fFunc; fFunc.Init (params, numbTestFuncRuns); CObject obj; CNDimensional_Rep frep; CMinBLEICReportShell rep; // Установка параметров алгоритма оптимизации BLEIC--------------------------- double diffStep = 0.00001; double epsg = 1e-16; double epsf = 1e-16; double epsi = 0.00001; CAlglib::MinBLEICCreateF (x, diffStep, fFunc.state); CAlglib::MinBLEICSetBC (fFunc.state, rangeMin, rangeMax); CAlglib::MinBLEICSetInnerCond (fFunc.state, epsg, epsf, rangeStep); CAlglib::MinBLEICSetOuterCond (fFunc.state, rangeStep, epsi); CAlglib::MinBLEICOptimize (fFunc.state, fFunc, frep, 0, obj); CAlglib::MinBLEICResults (fFunc.state, x, rep); // Вывод результатов оптимизации----------------------------------------------- Print ("BLEIC, best result: ", fFunc.fB, ", number of function launches: ", fFunc.numberLaunches); } //——————————————————————————————————————————————————————————————————————————————
Como el método accede a la función de aptitud por sí mismo (y no desde el programa del usuario), tendremos que envolver la llamada a la función de aptitud en una clase que herede de una clase padre en ALGLIB (estas clases padre serán diferentes para los distintos métodos). Luego declararemos la clase de envoltorio como "C_OptimisedFunction" y escribiremos los siguientes métodos en la clase:
1. Func () — método virtual que se sobrescribe en las clases derivadas.2. Init () — inicializa los parámetros de la clase. Dentro del método:
- Se inicializarán las variables asociadas al número de ejecuciones y al mejor valor de función encontrado.
- Los arrays "c" y "cB" están reservados para almacenar las coordenadas.
Variables:
- state — objeto de tipo CMinBLEICStateShell, específico para el método BLEIC, se utiliza al llamar a métodos estáticos del algoritmo y al llamar al método break.
- numberLaunches — número actual de inicios (necesario para evitar una ejecución incontrolada o demasiado larga de la función aptitud).
- maxNumbLaunchesAllowed — número máximo de inicios permitidos.
- fB — mejor valor encontrado de la función de aptitud.
- c [] — array de coordenadas actuales.
- cB [] — array para almacenar las mejores coordenadas de búsqueda.
//—————————————————————————————————————————————————————————————————————————————— // Класс для оптимизации функции, наследуется от CNDimensional_Func class C_OptimizedFunction : public CNDimensional_Func { public: C_OptimizedFunction (void) { } ~C_OptimizedFunction (void) { } // Виртуальная функция, которая будет содержать оптимизируемую функцию-------- virtual void Func (CRowDouble &x, double &func, CObject &obj); // Инициализация параметров оптимизации--------------------------------------- void Init (int coords, int maxNumberLaunchesAllowed) { numberLaunches = 0; maxNumbLaunchesAllowed = maxNumberLaunchesAllowed; fB = -DBL_MAX; ArrayResize (c, coords); ArrayResize (cB, coords); } //---------------------------------------------------------------------------- CMinBLEICStateShell state; // Состояние int numberLaunches; // Счетчик запусков double fB; // Лучшее найденное значение целевой функции (максимум) double cB []; // Координаты точки с лучшим значением функции private: //------------------------------------------------------------------- double c []; // Массив для хранения текущих координат int maxNumbLaunchesAllowed; // Максимально допустимое число вызовов функции }; //——————————————————————————————————————————————————————————————————————————————
El método "Func" de la clase "C_OptimisedFunction" está diseñado para abordar la función de aptitud del usuario. Tomará como argumentos un vector "x" (una de las variantes de los parámetros del problema optimizado que ofrece el método de optimización), un argumento "func" al que deberá devolverse el valor calculado de la función de aptitud, y un objeto "obj" (cuya finalidad no tengo clara, quizá esté reservada a la posibilidad de transmitir información adicional al/del método). Principales etapas de ejecución del método:
1. Primero se incrementará el contador "numberLaunches", que lleva la cuenta del número de llamadas al método "Func".
2. Si el número de ejecuciones supera el valor permitido "maxNumbLaunchesAllowed", la función establecerá el valor "func" en "DBL_MAX" (valor máximo de tipo "double", los métodos ALGLIB están diseñados para minimizar funciones, y este valor significa la peor solución posible). A continuación, se llamará a la función "MinBLEICRequestTermination", diseñada para indicar al método BLEIC que detenga el proceso de optimización.
3. A continuación, el ciclo copiará los valores del vector "x" en el array "c". Esto será necesario para utilizar dichos valores para la transmisión a la función de aptitud del usuario.
4. Luego se llamará a la función "ObjectiveFunction", que calculará el valor de la función objetivo para los valores actuales de la array "c". El resultado se almacenará en "ffVal", y el valor "func" se establecerá en el valor negativo "ffVal" (estamos optimizando un paraboloide invertido que necesita ser maximizado, y BLEIC minimiza la función, por lo que invertimos el valor).
5. Si el valor actual "ffVal" es superior al mejor valor anterior "fB", "fB" se actualizará y el array "cB" copiará el estado actual "c". Esto permite monitorear el mejor valor encontrado de la función objetivo con los parámetros correspondientes y consultar los datos posteriormente, de ser necesario.
La función "Func" implementará la llamada a una función de aptitud personalizada y monitoreará el número de veces que se ejecuta, actualizando los mejores resultados. También gestionará las condiciones de parada si el número de inicios supera el límite establecido.
//—————————————————————————————————————————————————————————————————————————————— // Реализация оптимизируемой функции void C_OptimizedFunction::Func (CRowDouble &x, double &func, CObject &obj) { // Увеличение счетчика запусков функции и контроль ограничений---------------- numberLaunches++; if (numberLaunches >= maxNumbLaunchesAllowed) { func = DBL_MAX; CAlglib::MinBLEICRequestTermination (state); return; } // Копирование входных координат во внутренний массив------------------------- for (int i = 0; i < x.Size (); i++) c [i] = x [i]; // Вычисление значения целевой функции---------------------------------------- double ffVal = ObjectiveFunction (c); func = -ffVal; // Обновление лучшего найденного решения-------------------------------------- if (ffVal > fB) { fB = ffVal; ArrayCopy (cB, c); } } //——————————————————————————————————————————————————————————————————————————————
Tras ejecutar el script de prueba con el algoritmo BLEIC para optimizar la función paraboloide, obtendremos el siguiente resultado en la impresión:
BLEIC, best result: 0.6861786206145579, number of function launches: 84022
Cabe señalar que, a pesar de haber solicitado detener la optimización con la ayuda del método "MinBLEICRequestTermination", el algoritmo ha continuado el proceso e intentado acceder a la función de aptitud otras 74.022 veces, superando el límite de 10.000 ejecuciones.
Ahora intentaremos no contener el BLEIC y lo dejaremos actuar como mejor le parezca. Los resultados han sido los siguientes:
BLEIC, best result: 1.0, number of function launches: 72017
Como podemos ver, el BLEIC es capaz de converger completamente a una función paraboloide, pero en este caso no resulta posible estimar de antemano el número necesario de ejecuciones de la función objetivo. Más adelante realizaremos pruebas a gran escala y analizaremos los resultados.
El paso de diferenciación resulta esencial en el algoritmo. Por lo tanto, si utilizamos un paso muy pequeño, como 1e-16 en lugar de 0,00001, el algoritmo se detendrá prematuramente, en esencia, se quedará atascado, con este resultado:
BLEIC, best result: 0.6615878186651468, number of function launches: 4002
L-BFGS (Limited-memory Broyden–Fletcher–Goldfarb–Shanno).
El algoritmo L-BFGS (Limited-memory Broyden-Fletcher-Goldfarb-Shanno) es un método de optimización eficiente diseñado de forma específica para problemas de alta dimensionalidad en los que el número de variables supera las 1.000. Pertenece a los métodos cuasi-newtonianos y utiliza memoria limitada para almacenar información sobre la curvatura de la función, evitando así la necesidad de almacenar y calcular explícitamente la matriz de Hesse completa.
El principio del algoritmo consiste en que construye y refina un modelo cuadrático de la función a optimizar utilizando los últimos M pares de valores y gradientes. Normalmente M es un número moderado entre 3 y 10, lo que reduce significativamente el coste computacional hasta O(N-M) operaciones. En cada iteración, el algoritmo calculará el gradiente en el punto actual, determinará la dirección de búsqueda utilizando los vectores almacenados y realizará una búsqueda lineal para determinar la longitud del paso. Si un paso del método cuasi-newtoniano no reduce suficientemente el valor de la función o el gradiente, se realizará un segundo ajuste direccional.
La principal característica de L-BFGS es la definición positiva del hessiano aproximado, que garantiza que la dirección del método cuasi-newtoniano será siempre la dirección de descenso, independientemente de la curvatura de la función.
En palabras simples, veamos cómo funciona el LBFGS:
1. La idea básica: el algoritmo intenta encontrar el mínimo de la función, "descendiendo" gradualmente hacia él, mientras construye un modelo simplificado (cuadrático) de la función que va refinando constantemente.
2. Cómo lo hace: memoriza los últimos M pasos (normalmente 310 pasos) y en cada paso almacena dos datos:
- donde nos encontrábamos (valor)
- por dónde es posible moverse (gradiente)
A partir de estos datos, el algoritmo construirá una aproximación de la curvatura de la función (matriz hessiana) y utilizará esta aproximación para determinar el siguiente paso.
3. Características: siempre se mueve "hacia abajo" (hacia el valor decreciente de la función), usa poca memoria (solo almacena los últimos M pasos) y funciona rápido (el coste es proporcional al tamaño de la tarea × M).
4. Ejemplo práctico. Imaginemos que bajamos una montaña con niebla:
- Solo podemos determinar la dirección de descenso en el punto actual
- Recordamos los últimos pasos y cómo ha cambiado la pendiente
- Basándonos en esta información, debemos predecir cuál es el mejor paso siguiente.
5. Limitaciones:
- Puede ser más lento para "paisajes" muy complejos
- Puede requerir una personalización adicional para mejorar el rendimiento
A diferencia del método BLEIC, en el L-BFGS es posible indicar explícitamente al método un límite en el número de ejecuciones de la función objetivo, pero no existe forma de especificar las condiciones de contorno para los parámetros a optimizar. El valor de M en el ejemplo de abajo se ha establecido en "1", el uso de otros valores no ha dado lugar a cambios notables en el rendimiento y en el comportamiento del algoritmo.
//—————————————————————————————————————————————————————————————————————————————— void OnStart () { // Инициализация параметров оптимизации--------------------------------------- int numbTestFuncRuns = 10000; int params = 1000; // Создание и инициализация массивов для границ диапазона поиска-------------- double rangeMin [], rangeMax [], rangeStep; ArrayResize (rangeMin, params); ArrayResize (rangeMax, params); for (int i = 0; i < params; i++) { rangeMin [i] = -10; rangeMax [i] = 10; } rangeStep = DBL_EPSILON; double x []; double s []; ArrayResize (x, params); ArrayResize (s, params); ArrayInitialize (s, 1); // Генерация случайных начальных значений параметров в заданных диапазонах----- for (int i = 0; i < params; i++) { x [i] = rangeMin [i] + ((rangeMax [i] - rangeMin [i]) * rand () / 32767.0); } // Создание объектов для оптимизации------------------------------------------- C_OptimizedFunction fFunc; fFunc.Init (params, numbTestFuncRuns); CObject obj; CNDimensional_Rep frep; CMinLBFGSReportShell rep; // Установка параметров алгоритма оптимизации L-BFGS--------------------------- double diffStep = 0.00001; double epsg = 1e-16; double epsf = 1e-16; CAlglib::MinLBFGSCreateF (1, x, diffStep, fFunc.state); CAlglib::MinLBFGSSetCond (fFunc.state, epsg, epsf, rangeStep, numbTestFuncRuns); CAlglib::MinLBFGSSetScale (fFunc.state, s); CAlglib::MinLBFGSOptimize (fFunc.state, fFunc, frep, 0, obj); CAlglib::MinLBFGSResults (fFunc.state, x, rep); //---------------------------------------------------------------------------- Print ("L-BFGS, best result: ", fFunc.fB, ", number of function launches: ", fFunc.numberLaunches); } //——————————————————————————————————————————————————————————————————————————————
En el L-BFGS, el tipo de la variable "state" lo estableceremos en "CMinLBFGSStateShell".
//—————————————————————————————————————————————————————————————————————————————— // Класс для оптимизации функции, наследуется от CNDimensional_Func class C_OptimizedFunction : public CNDimensional_Func { public: //-------------------------------------------------------------------- C_OptimizedFunction (void) { } ~C_OptimizedFunction (void) { } // Виртуальная функция, которая будет содержать оптимизируемую функцию--------- virtual void Func (CRowDouble &x, double &func, CObject &obj); // Инициализация параметров оптимизации---------------------------------------- void Init (int coords, int maxNumberLaunchesAllowed) { numberLaunches = 0; maxNumbLaunchesAllowed = maxNumberLaunchesAllowed; fB = -DBL_MAX; ArrayResize (c, coords); ArrayResize (cB, coords); } //---------------------------------------------------------------------------- CMinLBFGSStateShell state; // Состояние int numberLaunches; // Счетчик запусков double fB; // Лучшее найденное значение целевой функции (максимум) double cB []; // Координаты точки с лучшим значением функции private: //------------------------------------------------------------------- double c []; // Массив для хранения текущих координат int maxNumbLaunchesAllowed; // Максимально допустимое число вызовов функции }; //——————————————————————————————————————————————————————————————————————————————
Solicitaremos la detención del proceso de optimización con el comando "MinLBFGSRequestTermination".
//—————————————————————————————————————————————————————————————————————————————— // Реализация оптимизируемой функции void C_OptimizedFunction::Func (CRowDouble &x, double &func, CObject &obj) { //Увеличение счетчика запусков функции контроль ограничений------------------- numberLaunches++; if (numberLaunches >= maxNumbLaunchesAllowed) { func = DBL_MAX; CAlglib::MinLBFGSRequestTermination (state); return; } // Копирование входных координат во внутренний массив------------------------- for (int i = 0; i < x.Size (); i++) c [i] = x [i]; // Вычисление значения целевой функции---------------------------------------- double ffVal = ObjectiveFunction (c); func = -ffVal; // Обновление лучшего найденного решения-------------------------------------- if (ffVal > fB) { fB = ffVal; ArrayCopy (cB, c); } } //——————————————————————————————————————————————————————————————————————————————
Tras ejecutar el script de prueba con el algoritmo L-BFGS para optimizar la función paraboloide, obtendremos el siguiente resultado en la impresión:
L-BFGS, best result: 0.6743844728276278, number of function launches: 24006
Es muy probable que el parámetro de número máximo permitido de ejecuciones de la función objetivo no funcione, porque en realidad el algoritmo ha realizado más de 2 veces más ejecuciones.
Ahora intentaremos liberar L-BFGS y dejar que realice la optimización sin ningún límite en el número de ejecuciones:
L-BFGS, best result: 1.0, number of function launches: 52013
Tanto el L-BFGS como el BLEIC son capaces de converger completamente a una función paraboloide, pero el número de ejecuciones se vuelve incontrolable. En el siguiente vistazo general del algoritmo, mostraremos que esto puede ser un problema realmente grave si no se tiene en cuenta este matiz.
Para el L-BFGS, el paso de diferenciación será igual de importante. Si utilizamos un paso muy pequeño de 1e-16, el algoritmo se detendrá prematuramente; se atascará con este resultado:
L-BFGS, best result: 0.6746423814003036, number of function launches: 4001
NS (Nonsmooth Nonconvex Optimization Subject to box / linear / nonlinear - Nonsmooth Constraints)
El NS (Nonsmooth Nonconvex Optimization Subject to box/linear/nonlinear - Nonsmooth Constraints) es un algoritmo de optimización no suave y no convexo diseñado para resolver problemas en los que la función objetivo no es suave ni convexa. Esto significa que un rasgo puede presentar cambios bruscos, ángulos u otras particularidades. Las principales características de estos problemas son que la función objetivo puede contener puntos de discontinuidad o cambios bruscos que dificulten su análisis mediante métodos basados en el cálculo del gradiente.
Los principios del algoritmo incluyen la estimación del gradiente, donde se aplica un método de muestreo del gradiente que implica la valoración del gradiente en varios puntos aleatorios alrededor de la solución actual. Esto ayuda a evitar problemas vinculados con las características de la función. A partir de las estimaciones de gradiente obtenidas, se forma una tarea de programación cuadrática restringida (QP) cuya solución permite determinar la dirección en la que hay que moverse para mejorar la solución actual. El algoritmo funciona de forma iterativa, actualizando la solución actual en cada iteración basándose en los gradientes calculados y en la solución de la tarea QP.
En términos sencillos, vamos a analizar lo que significa esta descripción de la optimización:
1. NONSMOOTH (optimización no suave):
- La función puede presentar discontinuidades o "ruptura"
- No se requiere diferenciabilidad continua
- Pueden darse transiciones bruscas y saltos
2. NONCONVEX (No convexo):
- Una función puede tener varios mínimos y máximos locales
- El "paisaje" de la característica puede ser complejo, con "colinas" y "valles"
3. Tipos de restricciones (CONSTRAINTS): BOX (de caja), LINEAR (lineales), NONLINEAR-NONSMOOTH (no lineales, no suaves), que hemos descrito anteriormente.
Una característica de este método será la necesidad de especificar y parametrizar el solucionador AGS (método de muestreo adaptativo del gradiente). Este solucionador está diseñado para resolver problemas no suaves con restricciones de contorno, lineales y no lineales. El solucionador AGS incluye varias características importantes: procesamiento especial de restricciones, escalado de variables (para procesar problemas mal escalados) y soporte incorporado para la diferenciación numérica.
La limitación más importante del solucionador AGS reside en que no está diseñado para problemas de alta dimensionalidad. Un solo paso de AGS requiere aproximadamente 2-N estimaciones del gradiente en puntos seleccionados aleatoriamente (para comparar, L-BFGS requiere O(1) estimaciones por paso). Normalmente se necesitan O(N) iteraciones para la convergencia, lo cual conlleva O(N²) estimaciones de gradiente por sesión de optimización.
A diferencia de los métodos anteriores, el NS requiere el uso del tipo "CRowDouble" en lugar del tipo "double" para las variables de las condiciones de contorno y los valores iniciales de los parámetros optimizados del problema. Además, resulta necesario parametrizar el solucionador AGS.
//—————————————————————————————————————————————————————————————————————————————— void OnStart () { // Инициализация параметров оптимизации--------------------------------------- int numbTestFuncRuns = 10000; int params = 1000; // Создание и инициализация массивов для границ диапазона поиска-------------- CRowDouble rangeMin, rangeMax; rangeMin.Resize (params); rangeMax.Resize (params); double rangeStep; for (int i = 0; i < params; i++) { rangeMin.Set (i, -10); rangeMax.Set (i, 10); } rangeStep = DBL_EPSILON; CRowDouble x, s; x.Resize (params); s.Resize (params); s.Fill (1); // Генерация случайных начальных значений параметров в заданных диапазонах---- for (int i = 0; i < params; i++) { x.Set (i, rangeMin [i] + ((rangeMax [i] - rangeMin [i]) * rand () / 32767.0)); } // Создание объектов для оптимизации------------------------------------------ C_OptimizedFunction fFunc; fFunc.Init (params, numbTestFuncRuns); CObject obj; CNDimensional_Rep frep; CMinNSReport rep; // Установка параметров алгоритма оптимизации NS------------------------------ double diffStep = 0.00001; double radius = 0.8; double rho = 50.0; CAlglib::MinNSCreateF (x, diffStep, fFunc.state); CAlglib::MinNSSetBC (fFunc.state, rangeMin, rangeMax); CAlglib::MinNSSetScale (fFunc.state, s); CAlglib::MinNSSetCond (fFunc.state, rangeStep, numbTestFuncRuns); CAlglib::MinNSSetAlgoAGS (fFunc.state, radius, rho); CAlglib::MinNSOptimize (fFunc.state, fFunc, frep, obj); CAlglib::MinNSResults (fFunc.state, x, rep); // Вывод результатов оптимизации----------------------------------------------- Print ("NS, best result: ", fFunc.fB, ", number of function launches: ", fFunc.numberLaunches); } //——————————————————————————————————————————————————————————————————————————————
Necesitamos crear una clase de envoltorio para el método NS, ahora heredado de otra clase padre, "CNDimensional_FVec". También deberemos cambiar el método virtual a "FVec". La peculiaridad del método reside en el hecho de que resulta imposible devolver un valor de la función de aptitud igual a "DBL_MAX", porque en este caso el método finalizará con un error, a diferencia de los métodos de optimización anteriores. Por consiguiente, añadiremos un campo adicional a la clase, "fW", para monitorear la solución del peor caso durante la optimización.
//—————————————————————————————————————————————————————————————————————————————— // Класс для оптимизации функции, наследуется от CNDimensional_FVec class C_OptimizedFunction : public CNDimensional_FVec { public: //-------------------------------------------------------------------- C_OptimizedFunction (void) { } ~C_OptimizedFunction (void) { } // Виртуальная функция, которая будет содержать оптимизируемую функцию-------- virtual void FVec (CRowDouble &x, CRowDouble &fi, CObject &obj); // Инициализация параметров оптимизации--------------------------------------- void Init (int coords, int maxNumberLaunchesAllowed) { numberLaunches = 0; maxNumbLaunchesAllowed = maxNumberLaunchesAllowed; fB = -DBL_MAX; fW = DBL_MAX; ArrayResize (c, coords); ArrayResize (cB, coords); } //---------------------------------------------------------------------------- CMinNSState state; // Состояние int numberLaunches; // Счетчик запусков double fB; // Лучшее найденное значение целевой функции (максимум) double fW; // Худшее найденное значение целевой функции (максимум) double cB []; // Координаты точки с лучшим значением функции private: //------------------------------------------------------------------- double c []; // Массив для хранения текущих координат int maxNumbLaunchesAllowed; // Максимально допустимое число вызовов функции }; //——————————————————————————————————————————————————————————————————————————————
En rojo se encontrarán las cosas que no es posible hacer. En su lugar, retornaremos la peor solución que se haya encontrado durante la optimización (con un signo menos porque el método trabaja en la minimización). Y, por supuesto, deberemos cambiar el método de parada de la llamada por "MinNSRequestTermination".
//—————————————————————————————————————————————————————————————————————————————— void C_OptimizedFunction::FVec (CRowDouble &x, CRowDouble &fi, CObject &obj) { // Увеличение счетчика запусков функции и контроль ограничений---------------- numberLaunches++; if (numberLaunches >= maxNumbLaunchesAllowed) { //fi.Set (0, DBL_MAX); //Нельзя возвращать значение DBL_MAX fi.Set (0, -fW); CAlglib::MinNSRequestTermination (state); return; } // Копирование входных координат во внутренний массив------------------------- for (int i = 0; i < x.Size (); i++) c [i] = x [i]; // Вычисление значения целевой функции---------------------------------------- double ffVal = ObjectiveFunction (c); fi.Set (0, -ffVal); // Обновление лучшего и худшего найденных решений----------------------------- if (ffVal < fW) fW = ffVal; if (ffVal > fB) { fB = ffVal; ArrayCopy (cB, c); } } //——————————————————————————————————————————————————————————————————————————————
Tras ejecutar el script de prueba con el algoritmo NS para optimizar la función paraboloide, obtendremos el siguiente resultado en la impresión:
NS, best result: 0.6605212238333136, number of function launches: 1006503
Parece que para el NS, también, el parámetro de número máximo de ejecuciones permitido de la función objetivo no funcionará, porque el algoritmo ha realizado realmente más de 1 millón de ejecuciones.
Ahora intentaremos no restringir el NS y dejar que realice la optimización sin limitar el número de ejecuciones. El experimento no se ha completado, desafortunadamente no hemos podido esperar a que el script terminara de ejecutarse y hemos tenido que forzar su detención cerrando el gráfico:
Sin resultados.
Para el NS, el paso de diferenciación resulta igual de importante. Si usamos un paso muy pequeño de 1e-16, el algoritmo se detendrá prematuramente, a saber, se quedará atascado sin utilizar el número de ejecuciones de la función objetivo que tiene asignadas, con este resultado:
NS, best result: 0.6784901840822722, number of function launches: 96378
Conclusión
En este artículo, hemos introducido los métodos de optimización de la biblioteca ALGLIB en la que los métodos de gradiente calculan el gradiente numéricamente por sí mismos. Asimismo, hemos analizado las características clave de estos métodos, cuyo conocimiento permite no solo implementar la propia optimización, sino que también ayuda a evitar situaciones desagradables, como el número incontrolado de llamadas de la función objetivo.
En el próximo y último artículo sobre los métodos de optimización de ALGLIB, hablaremos con detalle de otros tres métodos. Además, pondremos a prueba todos los métodos considerados, lo cual nos permitirá identificar sus puntos fuertes y débiles en la aplicación práctica, y resumiremos los resultados de nuestro estudio. Además, visualizaremos (como siempre) el rendimiento de los algoritmos para demostrar claramente su comportamiento característico en problemas de prueba complejos. Esto nos permitirá comprender mejor cómo gestiona cada método las distintas llamadas a la optimización.
El texto del artículo ofrece códigos de script plenamente funcionales para ejecutar los métodos ALGLIB. Además, en el archivo encontrará todo lo necesario para empezar a utilizar ya mismo los métodos comentados para optimizar sus estrategias comerciales y otras tareas. Así, hemos logrado el objetivo del artículo de mostrar ejemplos sencillos e ilustrativos del uso de los métodos.
Mi especial agradecimiento a Evgeniy Chernish, que me ha ayudado a comprender las particularidades del acceso a los métodos de la biblioteca ALGLIB.
Programas usados en el artículo
| # | Nombre | Tipo | Descripción |
|---|---|---|---|
| 1 | Simple test ALGLIB BLEIC.mq5 | Script | Script de prueba para trabajar con BLEIC |
| 2 | Simple test ALGLIB LBFGS.mq5 | Script | Script de prueba para trabajar con L-BFGS |
| 3 | Simple test ALGLIB NS.mq5 | Script | Script de prueba para trabajar con NS |
Traducción del ruso hecha por MetaQuotes Ltd.
Artículo original: https://www.mql5.com/ru/articles/16133
Obtenga una ventaja sobre cualquier mercado (Parte V): Datos alternativos de FRED (Federal Reserve Economic Data) sobre el EURUSD
Ejemplo de nuevo Indicador y LSTM condicional
Redes neuronales en el trading: Transformador contrastivo de patrones (Final)
Desarrollamos un asesor experto multidivisa (Parte 19): Creando las etapas implementadas en Python
- Aplicaciones de trading gratuitas
- 8 000+ señales para copiar
- Noticias económicas para analizar los mercados financieros
Usted acepta la política del sitio web y las condiciones de uso