![Algoritmos de optimización de la población: Evolución diferencial (Differential Evolution, DE)](https://c.mql5.com/2/61/Population_optimization_algorithms_-_Differential_evolution_600x314.jpg)
Algoritmos de optimización de la población: Evolución diferencial (Differential Evolution, DE)
Contenido:
1. Introducción
2. Descripción del algoritmo
3. Resultados de las pruebas
1. Introducción
Los métodos de optimización metaheurísticos son una clase de algoritmos que usan enfoques heurísticos para resolver problemas de optimización complejos. Se diferencian de los métodos de optimización numérica, que suelen basarse en el análisis matemático y requieren conocer el gradiente o la derivada de la función objetivo. La principal diferencia entre los métodos metaheurísticos es su capacidad de explorar grandes espacios de búsqueda y encontrar óptimos globales, incluso cuando la función tiene muchos óptimos locales o no es continuamente diferenciable. La ventaja de los métodos metaheurísticos es que pueden trabajar con una "caja negra", es decir, con una función para la que no existe una solución analítica. Se basan en principios probabilísticos estocásticos y ofrecen una buena calidad de solución.
Los algoritmos evolutivos (EA) suponen una clase distinta de métodos de optimización metaheurísticos que simulan el proceso de evolución natural para resolver problemas de optimización complejos. Se basan en los principios de la herencia, mutación, cruce y selección natural. El proceso de evolución en los algoritmos evolutivos sigue el modelo de la selección natural, en el que las soluciones mejor adaptadas tienen más probabilidades de sobrevivir y transmitir sus características a la siguiente generación. De esta forma, la población converge gradualmente hacia la solución óptima. Algunos de los algoritmos evolutivos más populares son: los algoritmos genéticos (AG), la programación evolutiva (PE), las estrategias evolutivas (EE) y la programación genética (GP). Cada uno de estos algoritmos posee sus propias características y se aplica en distintos ámbitos.
En general, los algoritmos evolutivos son herramientas potentes que sirven para resolver problemas de optimización complejos, especialmente en los casos en los que no tenemos acceso a una expresión analítica de la función o al gradiente. Permiten explorar el espacio de búsqueda y encontrar soluciones óptimas combinando información de distintas soluciones individuales.
La evolución diferencial (DE) es uno de los métodos metaheurísticos de optimización, y se diferencia de otros métodos por su sencillez y eficacia. La DE usa una población de vectores que mutan y se entrecruzan para crear nuevas soluciones. No requiere conocer el gradiente y es capaz de encontrar óptimos globales.
El algoritmo DE fue desarrollado en los años 90 por Storn y Price (publicado en "Differential Evolution - A Simple and Efficient Heuristic for global Optimization over Continuous Spaces"), y desde entonces se ha convertido en uno de los métodos de optimización más populares, que utiliza una población de vectores de parámetros para encontrar la solución óptima.
2. Descripción del algoritmo
La idea de la evolución diferencial es una combinación de sencillez y eficacia. El algoritmo de evolución diferencial usa una población de vectores que representan soluciones potenciales. Cada vector está formado por componentes que representan los valores de las variables del problema de optimización.
En la DE, el papel del agente de búsqueda lo desempeña el vector. El algoritmo comienza creando una población aleatoria de vectores; a continuación se produce un proceso iterativo en el que cada vector muta y se cruza con otros vectores de la población. La mutación se realiza añadiendo la diferencia entre dos vectores elegidos al azar entre la población a un tercer vector. Esto crea un nuevo vector que representa una posible solución a la tarea.
Tras la mutación, el vector mutado se cruza con el vector original. El cruce permite combinar la información de los dos vectores y crear nuevas soluciones. El resultado obtenido se compara con la mejor solución actual de la población: si el nuevo vector es mejor, sustituirá al antiguo y pasará a formar parte de la población. La mutación nos permite explorar el espacio de búsqueda, mientras que el cruce nos permite combinar la información de distintos vectores y crear nuevas soluciones.
Este proceso de mutación, cruce y reemplazo se repite durante varias iteraciones hasta que se alcanza una condición de parada, como un número determinado de iteraciones o alcanzar la precisión de solución requerida, en nuestro caso alcanzar 10 000 ejecuciones de la función de aptitud.
La DE es uno de los algoritmos evolutivos más usados para resolver problemas de optimización. El algoritmo diferencial utiliza un operador de diferenciación para crear nuevos candidatos partiendo de la población actual. Estas son las fórmulas básicas usadas en el algoritmo diferencial:
1. Fórmula para crear un nuevo candidato (diferenciación):
r = r1 + F * (r2 - r3)
donde:
- v - componente del nuevo vector
- r1, r2 y r3 - componentes de vectores elegidos al azar (soluciones individuales de la población)
- F - coeficiente de diferenciación, que controla el grado de variabilidad de la solución (dispersión de los valores obtenidos), por defecto, se toma en el rango (0.0;1.0]
2. Fórmula de cruce (crossover):
u = crossover (x, v)
Esta fórmula describe el proceso de cruce entre la solución actual x y un nuevo candidato v. El operador de cruce determinará qué componentes de la solución se tomarán del nuevo candidato. Es la probabilidad de usar el nuevo componente vectorial, en caso contrario el componente permanecerá inalterado, se utilizarán los valores (0,0;1,0].
Vamos a crear el pseudocódigo del algoritmo DE, que es simple y claro debido a la simplicidad del propio algoritmo (de hecho, el código resultará no ser mucho más complicado que su pseudocódigo):
- Creamos una población aleatoria de vectores
- Calculamos la función de aptitud
- Cambiamos a una solución mejor
- Mejoramos la población (sustituimos los vectores por mutantes mejores)
- Creamos un componente vectorial mutante o dejamos el mismo, lo que sea mejor.
- Repetimos desde el paso 2.
Para describir un vector en el algoritmo DE, escribiremos una estructura (así la llamaremos, S_Vector), que representará un vector en un espacio n-dimensional. La estructura tendrá los siguientes campos:
- Init (int coords): la función inicializa un vector de coordenadas de longitud dada. Crea dos matrices: "c" y "cPrev", que representan las coordenadas del vector y sus coordenadas anteriores, respectivamente. También establece los valores iniciales f y fPrev como iguales a DBL_MAX.
- c []: array que contiene las coordenadas del vector
- cPrev []: array que contiene las coordenadas del vector en la iteración anterior
- f: valor de la función de aptitud para el vector actual
- fPrev: valor de la función de aptitud vectorial en la iteración anterior
//—————————————————————————————————————————————————————————————————————————————— struct S_Vector { void Init (int coords) { ArrayResize (c, coords); ArrayResize (cPrev, coords); f = -DBL_MAX; fPrev = -DBL_MAX; } double c []; //coordinates double cPrev []; //previous coordinates double f; //fitness double fPrev; //previous fitness }; //——————————————————————————————————————————————————————————————————————————————
Un algoritmo tan elemental como DE tiene una descripción de clase igualmente simple; declararemos la clase C_AO_DE. Los campos de la clase C_AO_DE contienen información sobre el estado actual del algoritmo y sus parámetros, mientras que los métodos realizarán diversas operaciones relacionadas con la optimización de la función.
La clase contiene los siguientes campos y métodos:
- cB []: array que contiene las mejores coordenadas encontradas por el algoritmo
- fB: valor de la función de aptitud para las mejores coordenadas
- v []: array de estructuras S_Vector que representan una población de vectores
- rangeMax[]: array que contiene los valores máximos de cada coordenada del vector
- rangeMin[]: array que contiene los valores mínimos de cada coordenada del vector
- rangeStep[]: array que contiene los valores de paso para cada coordenada vectorial
- Init (int coordsP, int popSizeP, double diffWeightP, double crossProbabP): la función inicializa los parámetros del algoritmo. Toma el número de coordenadas "coordsP", el tamaño de la población "popSizeP", el peso diferencial "diffWeightP" y la probabilidad de cruce "crossProbabP".
- Moving (): la función ejecuta un paso del algoritmo de evolución diferencial
- Revision (): la función realiza una revisión de la población del vector
- SeInDiSp (double In, double InMin, double InMax, double Step): el método calcula un nuevo valor de coordenadas en un rango específico con un paso dado.
- RNDfromCI (double min, double max): la función genera un número aleatorio en el intervalo [min, max].
//—————————————————————————————————————————————————————————————————————————————— class C_AO_DE { //---------------------------------------------------------------------------- public: double cB []; //best coordinates public: double fB; //FF of the best coordinates public: S_Vector v []; //vector public: double rangeMax []; //maximum search range public: double rangeMin []; //manimum search range public: double rangeStep []; //step search public: void Init (const int coordsP, //coordinates number const int popSizeP, //population size const double diffWeightP, //differential weight const double crossProbabP); //crossover robability public: void Moving (); public: void Revision (); //---------------------------------------------------------------------------- private: int coords; //coordinates number private: int popSize; //population size private: double diffWeight; //differential weight private: double crossProbab; //crossover robability private: bool revision; private: double SeInDiSp (double In, double InMin, double InMax, double Step); private: double RNDfromCI (double min, double max); }; //——————————————————————————————————————————————————————————————————————————————
El método Init de la clase C_AO_DE inicializará los parámetros del algoritmo de evolución diferencial. El método admite cuatro parámetros:
- "coordsP" - número de coordenadas,
- "popSizeP" - tamaño de la población,
- "diffWeightP" - peso diferencial
- "crossProbabP" - probabilidad de cruce.
El método usará primero la función MathSrand para reiniciar el generador de números aleatorios. Esto garantizará que cada vez que se ejecute el algoritmo, utilizará una nueva secuencia de números aleatorios.
A continuación, el método inicializará las variables "fB" y "revisión". La variable "fB" contendrá el mejor valor de la función de aptitud encontrado por el algoritmo. Inicialmente se establece en "-DBL_MAX", que es un número muy pequeño. La variable "revision" tendrá el valor "false", lo que significa que la población de vectores aún no ha sido revisada.
A continuación, el método inicializará las variables "coords", "popSize", "diffWeight" y "crossProbab" con los valores transmitidos como parámetros.
A continuación, el método creará un array "v" de tamaño "popSize" que contendrá la población de vectores.
Después, el método creará tres arrays: "rangeMax", "rangeMin" y "rangeStep", cada una de tamaño coords (número de coordenadas).
Por último, el método creará un array "cB" del tamaño coords que contendrá las mejores coordenadas encontradas por el algoritmo.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_DE::Init (const int coordsP, //coordinates number const int popSizeP, //population size const double diffWeightP, //differential weight const double crossProbabP) //crossover robability { MathSrand ((int)GetMicrosecondCount ()); // reset of the generator fB = -DBL_MAX; revision = false; coords = coordsP; popSize = popSizeP; diffWeight = diffWeightP; crossProbab = crossProbabP; ArrayResize (v, popSize); for (int i = 0; i < popSize; i++) v [i].Init (coords); ArrayResize (rangeMax, coords); ArrayResize (rangeMin, coords); ArrayResize (rangeStep, coords); ArrayResize (cB, coords); } //——————————————————————————————————————————————————————————————————————————————
Para cambiar los vectores solución en el espacio de búsqueda, escribiremos el método "Moving" de la clase C_AO_DE. El método aplicará operadores de mutación y cruce para generar nuevos vectores candidatos y seleccionará la mejor solución basándose en la función de aptitud.
El primer bloque de código, que comienza con la condición "if (!revision)", se ejecutará solo cuando el método "Moving" se ejecute por primera vez o después de llamar al método "Init". Inicializará la población inicial de vectores con valores aleatorios dentro del rango dado y con un paso especificado en el array "rangeStep".
A continuación, el método utilizará un ciclo "for" para actualizar cada vector de la población. Para cada vector, el método seleccionará tres vectores aleatorios diferentes de la población (r1, r2, r3) que no coincidirán con el vector actual (i) y aplicará los operadores de mutación y cruce para obtener un nuevo vector candidato. El operador de mutación calculará la diferencia entre los vectores "r2" y "r3" multiplicada por el peso diferencial "diffWeight" y añadirá el resultado al vector "r1". El operador de cruce seleccionará la coordenada de un vector y la sustituirá por la coordenada correspondiente del nuevo vector candidato con la probabilidad crossProbab. Si no se cumple la probabilidad de cruce, la coordenada vectorial actual permanecerá invariable.
El lector atento, analizando el código a continuación, comprobará que el método "Moving" para cambiar vectores no implica la creación de coordenadas en el espacio distintas de las que pueden derivarse de las existentes. Así pues, la estocasticidad del algoritmo consistirá únicamente en seleccionar los vectores para el cruce, pero no en crear otros nuevos y originales. Esta característica determinará consecuencias de gran alcance que analizaremos a continuación.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_DE::Moving () { //---------------------------------------------------------------------------- if (!revision) { for (int i = 0; i < popSize; i++) { for (int c = 0; c < coords; c++) { v [i].c [c] = RNDfromCI (rangeMin [c], rangeMax [c]); v [i].c [c] = SeInDiSp (v [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } revision = true; return; } //---------------------------------------------------------------------------- double rnd = 0.0; int r = 0; int r1 = 0; int r2 = 0; int r3 = 0; for (int i = 0; i < popSize; i++) { do { r = (int)RNDfromCI (0, popSize); if (r >= popSize) r = popSize - 1; r1 = r; } while (r1 == i); do { r = (int)RNDfromCI (0, popSize); if (r >= popSize) r = popSize - 1; r2 = r; } while (r2 == i || r2 == r1); do { r = (int)RNDfromCI (0, popSize); if (r >= popSize) r = popSize - 1; r3 = r; } while (r3 == i || r3 == r1 || r3 == r2); for (int c = 0; c < coords; c++) { rnd = RNDfromCI (0, 1.0); if (rnd < crossProbab) { v [i].c [c] = v [r1].cPrev [c] + diffWeight * (v [r2].cPrev [c] - v [r3].cPrev [c]); v [i].c [c] = SeInDiSp (v [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } else { v [i].c [c] = v [i].cPrev [c]; } } } } //——————————————————————————————————————————————————————————————————————————————
Por último, necesitaremos el método "Revision", cuya clase C_AO_DE actualizará la mejor solución de la población y almacenará los valores anteriores de la función aptitud y las coordenadas del vector.
En primer lugar, el método inicializará la variable "ind" con el valor "-1". A continuación, utilizará un ciclo "for" para iterar todos los vectores de la población y comprobar si la función de aptitud del vector actual es mayor que "fB" (la mejor función de aptitud encontrada hasta el momento), entonces almacenará el índice de ese vector en la variable "ind".
Si "ind" no es igual a "-1", el método actualizará el valor de "fB" al valor de la función de aptitud del vector con el índice "ind" y almacenará sus coordenadas en el array "cB".
A continuación, el método utilizará otro ciclo "for" para iterar todos los vectores de la población y comprobará si la función de aptitud del vector actual es mayor que su valor anterior; el método almacenará el valor actual de la función de aptitud y las coordenadas del vector en los campos correspondientes v[i].fPrev y v[i].cPrev.
Este método permitirá a la clase C_AO_DE almacenar la mejor solución de la población y los valores anteriores de la función de aptitud y las coordenadas del vector para su uso posterior en la optimización de la función de aptitud.
Podemos ver que la población no se moverá más en el espacio de búsqueda hasta que se encuentre un vector que sea mejor que su versión original (padre). Este punto se añadirá al anterior.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_DE::Revision () { //---------------------------------------------------------------------------- int ind = -1; for (int i = 0; i < popSize; i++) { if (v [i].f > fB) ind = i; } if (ind != -1) { fB = v [ind].f; ArrayCopy (cB, v [ind].c, 0, 0, WHOLE_ARRAY); } //---------------------------------------------------------------------------- for (int i = 0; i < popSize; i++) { if (v [i].f > v [i].fPrev) { v [i].fPrev = v [i].f; ArrayCopy (v [i].cPrev, v [i].c, 0, 0, WHOLE_ARRAY); } } } //——————————————————————————————————————————————————————————————————————————————
3. Resultados de las pruebas
Impresión del funcionamiento del algoritmo de evolución diferencial en un banco de pruebas:
C_AO_DE:50;0.2;0.8
=============================
5 Rastrigin's; Func runs 10000 result: 80.30183306326985
Score: 0.99498
25 Rastrigin's; Func runs 10000 result: 76.15178282331799
Score: 0.94356
500 Rastrigin's; Func runs 10000 result: 52.17316317703311
Score: 0.64645
=============================
5 Forest's; Func runs 10000 result: 1.7348423083855402
Score: 0.98131
25 Forest's; Func runs 10000 result: 1.28572746338484
Score: 0.72727
500 Forest's; Func runs 10000 result: 0.20833645141168078
Score: 0.11785
=============================
5 Megacity's; Func runs 10000 result: 9.640000000000002
Score: 0.80333
25 Megacity's; Func runs 10000 result: 3.9199999999999995
Score: 0.32667
500 Megacity's; Func runs 10000 result: 0.3548
Score: 0.02957
=============================
All score: 5.57100
A partir de los valores de salida del algoritmo, vemos excelentes resultados en las pruebas.
En la visualización podemos ver la fenomenal convergencia del algoritmo, pero también podemos notar la peculiaridad anteriormente mencionada en la descripción de los métodos "Moving" y "Revision". Al crear la visualización, tras varios intentos, hemos elegido a propósito los más acertados, de hecho los resultados distan mucho de ser siempre tan buenos. Esto se debe a la degeneración de la población, cuando toda la población (hasta el último de los vectores) converge hacia un único extremo. Pero puede que no sea el óptimo global. Como ya hemos comentado, el algoritmo carece de mecanismos para seguir explorando el espacio de búsqueda creando nuevos vectores únicos. El algoritmo DE no crea nuevos vectores, sino que solo genera combinaciones a partir de vectores existentes. Esto explica la completa degeneración de la población, no se crea "sangre nueva" para diversificar la "reserva genética" de la población.
DE en la función de prueba Rastrigin.
DE en la función de prueba Forest.
DE en la función de prueba Megacity.
Un ejemplo de la gran dispersión de la convergencia. Resulta especialmente pronunciado en las funciones Forest y Megacity.
Vamos a ver la tabla de clasificación final con el nuevo participante, la DE. El algoritmo ha sido capaz de arrebatar el segundo puesto al actual líder SDSm en la prueba Forest con 10 variables. Los resultados del resto de las pruebas también son muy buenos, la DE se ha hecho con el cuarto puesto tras SSG. Cabe señalar que, en lugar de realizar la prueba habitual de 5 veces para cada una de las funciones de prueba, hemos tenido que realizar pruebas de 10 veces debido a la enorme variación de los resultados en las funciones Forest y Megacity. En la función Rastrigin suave, la dispersión de los resultados ha resultado menos pronunciada.
№ | AO | Description | Rastrigin | Rastrigin final | Forest | Forest final | Megacity (discrete) | Megacity final | Final result | ||||||
10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | |||||||
1 | SDSm | stochastic diffusion search M | 0,99809 | 1,00000 | 0,69149 | 2,68958 | 0,99265 | 1,00000 | 1,00000 | 2,99265 | 1,00000 | 1,00000 | 1,00000 | 3,00000 | 100,000 |
2 | SDS | stochastic Diffusion Search | 0,99737 | 0,97322 | 0,58904 | 2,55963 | 0,96067 | 0,93572 | 0,79649 | 2,69288 | 0,78696 | 0,93815 | 0,71804 | 2,44315 | 88,201 |
3 | SSG | saplings sowing and growing | 1,00000 | 0,92761 | 0,51630 | 2,44391 | 0,72120 | 0,65201 | 0,83760 | 2,21081 | 0,54782 | 0,61841 | 0,99522 | 2,16146 | 77,683 |
4 | DE | differential evolution | 0,98295 | 0,89236 | 0,51375 | 2,38906 | 1,00000 | 0,84602 | 0,65510 | 2,50112 | 0,90000 | 0,52237 | 0,12031 | 1,54268 | 73,099 |
5 | HS | harmony search | 0,99676 | 0,88385 | 0,44686 | 2,32747 | 0,99148 | 0,68242 | 0,37529 | 2,04919 | 0,71739 | 0,71842 | 0,41338 | 1,84919 | 70,623 |
6 | IWO | invasive weed optimization | 0,95828 | 0,62227 | 0,27647 | 1,85703 | 0,70170 | 0,31972 | 0,26613 | 1,28755 | 0,57391 | 0,30527 | 0,33130 | 1,21048 | 48,250 |
7 | ACOm | ant colony optimization M | 0,34611 | 0,16683 | 0,15808 | 0,67103 | 0,86147 | 0,68980 | 0,64798 | 2,19925 | 0,71739 | 0,63947 | 0,05579 | 1,41265 | 47,387 |
8 | MEC | mind evolutionary computation | 0,99270 | 0,47345 | 0,21148 | 1,67763 | 0,60244 | 0,28046 | 0,21324 | 1,09615 | 0,66957 | 0,30000 | 0,26045 | 1,23002 | 44,049 |
9 | SDOm | spiral dynamics optimization M | 0,69840 | 0,52988 | 0,33168 | 1,55996 | 0,59818 | 0,38766 | 0,37600 | 1,36183 | 0,35653 | 0,15262 | 0,25842 | 0,76758 | 40,289 |
10 | COAm | cuckoo optimization algorithm M | 0,92400 | 0,43407 | 0,24120 | 1,59927 | 0,57881 | 0,23477 | 0,13842 | 0,95200 | 0,52174 | 0,24079 | 0,17001 | 0,93254 | 37,830 |
11 | FAm | firefly algorithm M | 0,59825 | 0,31520 | 0,15893 | 1,07239 | 0,50637 | 0,29178 | 0,41704 | 1,21519 | 0,24783 | 0,20526 | 0,35090 | 0,80398 | 33,139 |
12 | ABC | artificial bee colony | 0,78170 | 0,30347 | 0,19313 | 1,27829 | 0,53379 | 0,14799 | 0,11177 | 0,79355 | 0,40435 | 0,19474 | 0,13859 | 0,73768 | 29,766 |
13 | BA | bat algorithm | 0,40526 | 0,59145 | 0,78330 | 1,78002 | 0,20664 | 0,12056 | 0,21769 | 0,54488 | 0,21305 | 0,07632 | 0,17288 | 0,46225 | 29,499 |
14 | CSS | charged system search | 0,56605 | 0,68683 | 1,00000 | 2,25289 | 0,13961 | 0,01853 | 0,13638 | 0,29452 | 0,07392 | 0,00000 | 0,03465 | 0,10856 | 27,930 |
15 | GSA | gravitational search algorithm | 0,70167 | 0,41944 | 0,00000 | 1,12111 | 0,31390 | 0,25120 | 0,27812 | 0,84322 | 0,42609 | 0,25525 | 0,00000 | 0,68134 | 27,807 |
16 | BFO | bacterial foraging optimization | 0,67203 | 0,28721 | 0,10957 | 1,06881 | 0,39364 | 0,18364 | 0,17298 | 0,75026 | 0,37392 | 0,24211 | 0,18841 | 0,80444 | 27,542 |
17 | EM | electroMagnetism-like algorithm | 0,12235 | 0,42928 | 0,92752 | 1,47915 | 0,00000 | 0,02413 | 0,29215 | 0,31628 | 0,00000 | 0,00527 | 0,10872 | 0,11399 | 19,002 |
18 | SFL | shuffled frog-leaping | 0,40072 | 0,22021 | 0,24624 | 0,86717 | 0,19981 | 0,02861 | 0,02221 | 0,25063 | 0,19565 | 0,04474 | 0,06607 | 0,30646 | 13,200 |
19 | MA | monkey algorithm | 0,33192 | 0,31029 | 0,13582 | 0,77804 | 0,09927 | 0,05443 | 0,07482 | 0,22852 | 0,15652 | 0,03553 | 0,10669 | 0,29874 | 11,777 |
20 | SFS | fish school search | 0,46812 | 0,23502 | 0,10483 | 0,80798 | 0,12730 | 0,03458 | 0,05458 | 0,21647 | 0,12175 | 0,03947 | 0,08244 | 0,24366 | 11,332 |
21 | IWDm | intelligent water drops M | 0,26459 | 0,13013 | 0,07500 | 0,46972 | 0,28358 | 0,05445 | 0,05112 | 0,38916 | 0,22609 | 0,05659 | 0,05054 | 0,33322 | 10,423 |
22 | PSO | particle swarm optimisation | 0,20449 | 0,07607 | 0,06641 | 0,34696 | 0,18734 | 0,07233 | 0,18207 | 0,44175 | 0,16956 | 0,04737 | 0,01947 | 0,23641 | 8,426 |
23 | RND | random | 0,16826 | 0,09038 | 0,07438 | 0,33302 | 0,13381 | 0,03318 | 0,03949 | 0,20648 | 0,12175 | 0,03290 | 0,04898 | 0,20363 | 5,054 |
24 | GWO | grey wolf optimizer | 0,00000 | 0,00000 | 0,02093 | 0,02093 | 0,06514 | 0,00000 | 0,00000 | 0,06514 | 0,23478 | 0,05789 | 0,02545 | 0,31812 | 1,000 |
Conclusiones
El algoritmo de evolución diferencial es capaz de encontrar óptimos globales muy rápidamente y tiene una convergencia excelente, si consideramos los resultados muy mediocres en pruebas individuales. La DE se utiliza ampliamente en diversos campos, como la optimización de parámetros de modelos, el ajuste de redes neuronales, la optimización de funciones en física y economía, y muchos otros. Yo recomendaría hacer múltiples ejecuciones de optimización con este algoritmo, ya que los resultados dependerán mucho de la población inicial en la primera iteración. Aumentar el tamaño de la población mientras se incrementa el número de iteraciones puede resultar útil.
Con su simplicidad y rapidez de funcionamiento, el algoritmo de evolución diferencial posee desventajas obvias, como la degeneración de la población (y como consecuencia el atasco en los extremos locales); debemos tener en cuenta esto a la hora de elegir la DE para nuestros problemas de optimización.
El algoritmo de DE analizado en este artículo es una especie de patrón a partir del cual se han creado varias modificaciones. Mis sugerencias para mejorar el algoritmo de evolución diferencial (DE) serían las siguientes:
1. La utilización de métodos adaptativos de control de parámetros: La DE tiene varios parámetros que deben ajustarse debido a su gran influencia en los resultados.El parámetro de peso diferencial recomendado por los autores es "0,2": este es el valor por defecto que hemos adoptado en el script para las pruebas de DE. Este parámetro tiene un impacto significativo en la diversidad de la población; si elegimos un valor inferior a "0,2", podemos conseguir que la convergencia del algoritmo sea aún mejor, pero obtendremos aún más variación en los resultados. Por el contrario, si aumentamos el valor de este parámetro, el algoritmo se volverá robusto frente a la degeneración de la población y el estancamiento en extremos locales, pero al mismo tiempo la calidad de la convergencia disminuirá rápidamente para un número limitado de iteraciones, propiamente, el tiempo de búsqueda aumentará de forma inevitable.
El parámetro de probabilidad de cruce también afectará a la calidad de la optimización. Los autores recomiendan un valor de "0,9", pero mis experimentos han mostrado un valor mejor, en mi opinión, de "0,8".
Considerando lo anterior, parece razonable utilizar métodos adaptativos para controlar y cambiar dinámicamente los parámetros, de modo que el algoritmo pueda ajustarse automáticamente según la tarea.
2. La utilización de diferentes estrategias de mutación y cruce.
3. La utilización de métodos híbridos: es posible combinar la DE con otros métodos de optimización, como algoritmos genéticos, métodos de optimización basados en gradientes, métodos de optimización basados en enjambres de partículas, etcétera. Esto puede mejorar el rendimiento del algoritmo y ayudarnos a mejorar la eficiencia del algoritmo en su conjunto.
4. La mejora de la convergencia: aplicar la creación de vectores aleatorios adicionales para aumentar la diversidad en la población.
5. La utilización de diferentes estrategias de selección de individuos para la mutación: este algoritmo considerará un método completamente aleatorio de selección de individuos para el cruce, pero también será posible complementar o sustituir completamente este método utilizando otras estrategias diferentes de la selección de individuos para el cruce/mutación, como la estrategia de selección de individuos basada en la aptitud. Esto puede ayudarnos a mejorar la diversidad de la población y mejorar significativamente la robustez del algoritmo frente a las interferencias.
En general, el algoritmo DE deja una muy buena impresión de su rendimiento, pero siempre debemos tener presentes las características de este interesante algoritmo o hacer algunos intentos de mejorar la evolución diferencial aplicando una combinación de diferentes estrategias y métodos. La DE ha demostrado con creces que los algoritmos pueden ser muy eficientes y seguir resultando increíblemente sencillos y rápidos. El algoritmo de evolución diferencial puede recomendarse para resolver problemas de optimización complejos con alta dimensionalidad, ya que el efecto de la caída de la diversidad durante la evolución resulta menos pronunciado cuando el número de parámetros optimizados es grande.
Figura 1. Clasificación por colores de los algoritmos según sus respectivas pruebas.
Figura 2. Histograma de los resultados de las pruebas de los algoritmos (en una escala de 0 a 100, cuanto mayor, mejor),
en el archivo hay un script para calcular la tabla de clasificación según la metodología de este artículo).
Ventajas e inconvenientes del algoritmo de evolución diferencial (DE)
Ventajas:
- Número reducido de parámetros externos.
- Aplicación sencilla.
- Velocidad de funcionamiento.
- Buena escalabilidad.
- Excelente rendimiento en diferentes tipos de funciones (teniendo en cuenta los puntos negativos).
Desventajas:
- Alta variación de los resultados.
- Tendencia a estancarse en los extremos locales.
Adjunto al artículo hay un archivo con las versiones reales actualizadas de los códigos de los algoritmos descritos en los artículos anteriores. El autor del presente artículo no se responsabiliza de la exactitud absoluta en la descripción de los algoritmos canónicos; muchos de ellos han sido modificados para mejorar las capacidades de búsqueda. Las conclusiones y juicios presentados en los artículos se basan en los resultados de los experimentos efectuados.
Traducción del ruso hecha por MetaQuotes Ltd.
Artículo original: https://www.mql5.com/ru/articles/13781
![Cómo crear un panel informativo para mostrar datos en indicadores y asesores](https://c.mql5.com/2/57/information_panel_for_displaying_data_avatar.png)
![Redes neuronales: así de sencillo (Parte 65): Aprendizaje supervisado ponderado por distancia (DWSL)](https://c.mql5.com/2/61/Neural_Networks_Made_Easy_lPart_65q_DWSL_LOGO.png)
![Plantillas listas para conectar indicadores en asesores (Parte 1): Osciladores](https://c.mql5.com/2/57/ready_made_templates_for_connecting_indicators_001_avatar.png)
![Algoritmos de optimización de la población: Algoritmo de optimización de la dinámica espiral (Spiral Dynamics Optimization, SDO)](https://c.mql5.com/2/61/Spiral_Dynamics_Optimization_SDO_LOGO.png)
![MQL5 - Lenguaje de estrategias comerciales para el terminal de cliente MetaTrader 5](https://c.mql5.com/i/registerlandings/logo-2.png)
- 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