Algoritmos de optimización de la población: Algoritmo de gotas de agua inteligentes (Intelligent Water Drops, IWD)
171
0
Contenido:
1. Introducción
2. Descripción del algoritmo
3. Versión modificada de SDSm
4. Resultados de las pruebas
1. Introducción
El cauce del río es una de las creaciones más exquisitas de la naturaleza, en la que cada gota de agua juega su papel en la singular danza de la vida. Con cada kilómetro de recorrido, el río forma sus nuevas fronteras, irradiando majestuosamente su energía y sabiduría. Al igual que este fenómeno natural, el algoritmo de optimización de gotas de agua inteligentes (IWD) busca la armonía y la perfección en su funcionamiento utilizando los principios de la autoorganización y las interacciones entre partículas. Este algoritmo refleja la grandeza de la naturaleza y su capacidad para crear y mantener el equilibrio, lo cual lo convierte en una herramienta importante en el campo de la optimización de procesos y la resolución de problemas complejos.
Cualquier río tiene su propio valle formado por procesos de erosión por la acción de las aguas superficiales y subterráneas. La parte más baja de este valle, labrada en la tierra por el caudal del río, se denomina cauce. A través de este canal se transporta la mayor parte del caudal del río y de la carga del cauce.
El relieve del canal está en cambio constante. Las rocas y la arena arrastradas por el agua forman crestas y rollos que atraviesan el canal en ángulo agudo. En los recodos, los ríos pueden trazar un nuevo camino y formar antiguos cauces, tramos del antiguo cauce que poco a poco se convierten en un lago con su propio ecosistema, y más tarde se secan o permanecen como pantano.
Al observar los ríos en la naturaleza, nos damos cuenta de los muchos giros y vueltas que dan en su camino. La preguntas que surgen son: ¿por qué se crearon estos giros? ¿Existe alguna lógica o razón detrás de ellos? Y si es así, ¿podemos explotar los mecanismos presentes en los ríos y, en consecuencia, diseñar y desarrollar algoritmos inteligentes basados en ellos? El algoritmo IWD es un intento de modelizar algunos de los procesos que acaecen en los ríos naturales y aplicarlos después en forma de algoritmo.
El algoritmo IWD es uno de los algoritmos de desarrollo relativamente reciente en el campo de la inteligencia de enjambre: este algoritmo imita la dinámica de los sistemas fluviales. Se basa en poblaciones en el que cada gota representa una solución, mientras que el uso compartido de gotitas durante la búsqueda da lugar a mejores soluciones.
En 2007, el científico iraní Hamed Shah-Hosseini desarrolló un algoritmo sobre el comportamiento de las gotas de agua inteligentes. En el algoritmo IWD, varias gotas de agua artificiales, mediante interacción, son capaces de cambiar su entorno de tal forma que encuentran el camino óptimo por la vía de menor resistencia. El algoritmo IWD es un algoritmo de optimización constructivo orientado a la población.
2. Descripción del algoritmo
El IWD es un modelo en el que las gotas de agua encuentran el mejor camino hacia su destino cambiando el cauce del río. A este proceso contribuyen tres parámetros importantes. Por su propia velocidad, las gotas son capaces de arrastrar la tierra del fondo del río, y cuanto mayor sea la velocidad, mayor será la cantidad de tierra que cada gota sea capaz de arrastrar consigo, por lo que el camino quedará más libre para los agentes posteriores. La velocidad del arroyo aumenta donde no hay suelo que desbrozar. La trayectoria óptima será la que tenga la menor cantidad de tierra y la mayor velocidad. Utilizando el IWD, puede aplicarse una estrategia de optimización en la que agentes aleatorios interactúen inteligentemente entre sí de tal forma que modifiquen conjuntamente el cauce y creen una trayectoria óptima en la que no se encuentre suelo alguno y el caudal de los agentes sea el máximo posible.
Principios básicos:
- una gota de agua prefiere un camino con menos tierra a uno con más tierra
- una gota de agua prefiere una ruta más corta cuando tiene que elegir entre varias rutas en su camino desde la fuente hasta el destino
- La facilidad o dureza del camino viene determinada por la cantidad de tierra que haya en él; un cauce con más tierra se considerará duro, mientras que uno con menos tierra se considerará fácil.
En la naturaleza, se observan muchas gotas de agua en los ríos, donde forman enormes masas (enjambres de gotas de agua). Las formas en que fluyen los ríos naturales fueron creadas por enjambres de gotas de agua. Los enjambres de gotas de agua (ríos) forman parte de un entorno que ha sido alterado significativamente por el enjambre y que también se encuentra sujeto a cambios futuros. Además, el propio entorno influye notablemente en las trayectorias de las gotas de agua. Las orillas del río les ofrecen resistencia. Por ejemplo, para un enjambre de gotas de agua ofrecen más resistencia las partes del entorno que constituyen la tierra dura, que las partes de la tierra blanda. El curso natural de un río es el resultado de la competencia entre las gotas de agua y el medio ambiente, que ofrece resistencia al movimiento de las gotas de agua.
Una de las características de las gotas de agua que fluyen por un río es su velocidad. Otra característica es el suelo, del que cada río puede arrastrar una determinada cantidad. Así, una gota de agua es capaz de transportar cierta cantidad de tierra de un lugar a otro. Este suelo se transfiere de partículas rápidas a partículas lentas, es decir, la tierra arrastrada por el río junto con la corriente rápida se asentará en un lugar con la corriente lenta.
Durante este periodo de traslado se producirán tres cambios evidentes:
- aumentará la velocidad de la gota de agua
- aumentará la saturación de tierra de la gota de agua
- entre estos dos puntos, la cantidad de tierra en el canal disminuirá (puntos del gráfico)
Antes hemos señalado que cada gota de agua tiene una velocidad diferente. Dicha velocidad desempeña un papel directo en la acumulación de tierra en el cauce del río. Una gota de agua con una velocidad elevada arrastra más tierra que una gota con una velocidad inferior. Así, las gotas de agua con mayor velocidad se llevan más tierra del fondo del río que las gotas de agua con menor velocidad. De esta manera, la eliminación de la tierra está relacionada con la velocidad de la gota de agua.
La velocidad de una gota de agua aumenta más en las trayectorias bajas del cauce que en las trayectorias altas. Así, una trayectoria con poco suelo permite a la gota de agua actual arrastrar más tierra y ganar más velocidad, mientras que una trayectoria con más niveles de tierra provoca una reducción de la velocidad.
Por ello, en el algoritmo IWD, las gotas se caracterizan por dos propiedades principales:
- velocidad
- suelo
Ambas propiedades pueden cambiar durante el funcionamiento del algoritmo. Las gotas en IWD se desplazan desde el origen hasta el destino y empiezan su viaje con una velocidad inicial y una cantidad de tierra cero. Durante dicho viaje, las gotas se mueven en un entorno del que remueven algo de tierra y pueden coger velocidad. Se supone que la IWD se ejecuta de forma iterativa. Desde la ubicación actual a la siguiente, la velocidad de la gota aumenta en una cantidad no linealmente proporcional a la inversa de la tierra entre las dos ubicaciones:
vel = vel (t-1) + Av / [Bv + Cv * soil^2(i,j)]
donde: Av, Bv, Cv son los coeficientes de velocidad (parámetros de entrada), y soil (i,j) es la cantidad de tierra entre los vértices del gráfico.
Por consiguiente, una trayectoria con menos tierra permitirá que la gota IWD se mueva más rápidamente que una trayectoria con más tierra.
La gota IWD arrastra tierra a medida que se desplaza por el entorno. Esta tierra se retira del camino que enlaza ambos lugares. La cantidad de tierra añadida a una gota de IWD es proporcional de forma no lineal al tiempo necesario para desplazar la IWD desde su ubicación actual a la siguiente. Este intervalo de tiempo se calcula usando leyes físicas sencillas para el movimiento lineal:
time(i,j,vel) = R / vel
donde: R es la distancia entre dos puntos.
La cantidad de tierra añadida a la gota:
dSoil(i,j) = As / [Bs + Cs * time(i,j,vel)]
donde: As, Bs, Cs son los coeficientes de recuperación de la tierra.
Y la nueva cantidad de tierra en el camino entre los puntos tendrá este aspecto:
soil (i+1,j+1) = Po * soil(i,j) + Pn * dSoil(i,j)
donde: Po y Pn son los coeficientes del proceso de cambio de la cantidad de tierra.
Así, el tiempo que se tarda en moverse será inversamente proporcional a la velocidad de desplazamiento y directamente proporcional a la distancia entre dos puntos. Podemos decir que la tierra es una medida cuantitativa de la información del entorno. Estas fórmulas determinan la preferencia de las gotas por elegir trayectorias con baja presencia de cauce frente a las de alta presencia. Esta selección de trayectorias se realiza aplicando una distribución aleatoria uniforme a las trayectorias disponibles. La probabilidad de seleccionar el siguiente camino será inversamente proporcional al nivel de cauce de los caminos disponibles. Por lo tanto, los caminos con niveles de cauce más bajos tendrán más posibilidades de ser seleccionados por las gotas IWD.
El algoritmo IWD original fue desarrollado por el autor para resolver problemas de búsqueda de caminos óptimos, al igual que los problemas de búsqueda de grafos y los problemas del viajante de comercio. Sin embargo, este algoritmo no resulta apropiado para los problemas que consideramos en nuestras pruebas. Por ello, deberemos adaptar el algoritmo IWD para resolver nuestros problemas de optimización. En cambio, los algoritmos descritos en los artículos «Algoritmos de optimización de la población» son capaces de resolver problemas de cualquier tipo, incluidos los de búsqueda de grafos. En artículos anteriores ya presentamos un algoritmo similar altamente especializado que requería un rediseño, a saber, la "Colonia de Hormigas (ACO)".
Para adaptar la IWD de forma que pueda resolver cualquier problema de optimización, y para que la IWD compita con otros algoritmos poblacionales, deberemos definir primero cómo aplicar el proceso de sedimentación y movimiento de la tierra. No podemos seguir el enfoque utilizado en el algoritmo ACO, en el que las feromonas equivalen al valor de la función de aptitud. En el caso de la IWD, la tierra será un indicador dinámico y no se corresponderá proporcionalmente con la aptitud.
Hemos tenido la idea de dividir las coordenadas en sectores, de forma similar a dividir un valle fluvial en secciones con la misma superficie. La idea es que si la posición de la gota (agente) mejora, la cantidad de tierra en los sectores correspondientes en todas las coordenadas disminuirá. El cambio cuantitativo de la tierra vendrá determinado por la diferencia en el cambio de la función de aptitud en las dos últimas iteraciones, normalizada en todas las caídas por la diferencia entre el cambio máximo y mínimo en la aptitud.
El comportamiento del movimiento de las gotas se basará en una selección aleatoria de los sectores que tengan menor cantidad de tierra, es decir, donde la probabilidad sea proporcional a la cantidad de tierra del sector correspondiente. Las mejores coordenadas de todos los sectores se almacenarán en el "canal" de almacenamiento global. Después de que la gota seleccione un sector, se intentará mejorar la coordenada almacenada de forma que la probabilidad de la nueva coordenada obedezca a una ley cuadrática, según la cual la nueva coordenada se situará más cerca de la coordenada anterior con mayor probabilidad que más lejos. La anchura del sector en el que se situará la nueva coordenada vendrá determinada por un parámetro externo y se expresará en partes del tamaño del sector. En la figura 1 se ilustra la partición de coordenadas en sectores y la distribución de probabilidad de una nueva coordenada.
Figura 1. Partición de las coordenadas en sectores y distribución de la probabilidad de elegir una nueva coordenada en la vecindad de la mejor coordenada conocida.
Basándonos en las afirmaciones anteriores y en los conceptos del algoritmo IWD, podemos componer un pseudocódigo desglosado paso a paso:
- Generación aleatoria de gotas (primera iteración)
- Cálculo de FF
- Actualización del mejor resultado global
- Generación aleatoria de gotas (segunda iteración)
- Cálculo de FF
- Actualización del mejor resultado global
- Cálculo del cambio de altura de cada gota (altura actual y altura anterior)
- Actualización de altitudes por sector
- Nuevas gotas (selección probabilística de un sector, una gota en la vecindad de una zanja conocida)
- Cálculo de FF
- Actualización del mejor resultado global
- Repetimos desde el punto 7
Analicemos ahora el código.
Representaremos el agente de búsqueda "drop" como una estructura S_Drop, que contendrá los siguientes campos:
- Init (int coords): la función inicializa el objeto estructura, tomando como argumento el número de coordenadas "coords". Dentro de la función, los arrays "c" y "rSection" se redimensionan al número de coordenadas especificado, y se inicializan las variables "f", "fPrev" y "altChange".
- c: array para almacenar coordenadas
- rSection: array para almacenar los sectores del río
- f: puntuación de aptitud (fitness) para una gota (drop) determinada
- fPrev: valor anterior del indicador de aptitud
- altChange: cambio de altitud
struct S_Drop { void Init (int coords) { ArrayResize (c, coords); ArrayResize (rSection, coords); f = -DBL_MAX; fPrev = -DBL_MAX; altChange = 0.0; } double c []; //coordinates int rSection []; //river section (número de celdas: número de coordenadas, valor de celdas: índice del sector en la coordenada) double f; //fitness double fPrev; //previous fitness double altChange; //change in altitude };
Necesitaremos un repositorio donde almacenar la descripción del río (las mejores coordenadas de profundidad y las profundidades en sí), así que llamaremos a la estructura, S_Riverbed:
- riverbedDepth: array para almacenar la profundidad del cauce del río; el número de celdas del array se corresponde con el número de sectores de la coordenada, mientras que el valor de cada celda será la profundidad del cauce del río en el sector correspondiente.
- coordOnSector: array para almacenar la coordenada específica de la ubicación más profunda en un sector; el número de celdas de la matriz se corresponderá con el número de sectores en la coordenada, mientras que el valor de cada celda será la coordenada en el sector correspondiente.
//—————————————————————————————————————————————————————————————————————————————— struct S_Riverbed //cauce del río { double riverbedDepth []; //riverbed depth double coordOnSector []; //coordinate on the sector }; //——————————————————————————————————————————————————————————————————————————————
Declaremos la clase C_AO_IWDm (m - modificada), que implementará un algoritmo de optimización artificial basado en las gotas de agua. Aquí tenemos una descripción de cada elemento de la clase:
Propiedades de la clase:
- cB: array para almacenar las mejores coordenadas
- fB: almacena el valor de la función objetivo para las mejores coordenadas
- p: array para las partículas (gotas de agua)
- los arrays "rangeMax", "rangeMin" y "rangeStep" se utilizan para definir el rango de búsqueda
Métodos de la clase:
- Init: inicializa un objeto de clase C_AO_IWDm con los parámetros especificados: "coordsP" - número de coordenadas, "popSizeP" - tamaño de la población, "sectorsNumberP" - número de sectores, "waterViscosityP" - viscosidad del agua.
- Moving: realiza el movimiento de las gotas de agua
- Revision: realiza la revisión del estado de las gotas de agua
- coords: número de coordenadas
- popSize: número de gotas
- sectoresNumbe: número de sectores
- waterViscosity: coeficiente de viscosidad del agua, en partes del tamaño del sector
- sectorSpace : tamaño del sector
- rb: array de coordenadas, para describir el cauce del río
- iterationCounter
- revision: bandera que indica la necesidad de revisión
- SeInDiSp: calcula un nuevo valor de coordenadas en un intervalo especificado con un tamaño de paso dado.
- RNDfromCI: genera un número aleatorio dentro de un intervalo especificado
- Scale: escala un número a un intervalo especificado.
//—————————————————————————————————————————————————————————————————————————————— class C_AO_IWDm { //---------------------------------------------------------------------------- public: double cB []; //best coordinates public: double fB; //FF of the best coordinates public: S_Drop p []; //particles (drops) 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 int sectorsNumberP, //sectors number const double waterViscosityP); //water viscosity (>= 1) public: void Moving (); public: void Revision (); //---------------------------------------------------------------------------- private: int coords; //coordinates number private: int popSize; //population size private: int sectorsNumber; //sectors number private: double waterViscosity; //water viscosity private: double sectorSpace []; //sector space private: S_Riverbed rb []; //riverbed private: int iterationCounter; private: double SeInDiSp (double In, double InMin, double InMax, double Step); private: double RNDfromCI (double min, double max); private: double Scale (double In, double InMIN, double InMAX, double OutMIN, double OutMAX, bool revers); }; //——————————————————————————————————————————————————————————————————————————————
El método Init inicializa un objeto de la clase C_AO_IWDm con los parámetros indicados: número de coordenadas, número de gotas, número de sectores, viscosidad del agua.
Este método efectúa las siguientes acciones:
1. Reinicia el generador de números aleatorios.
2. Inicializa el valor de la función objetivo "fB" con el valor "-DBL_MAX".
3. Pone a cero el contador de iteraciones
4. Establece el número de coordenadas "coords", así como el tamaño de la población "popSize" en los valores especificados.
5. Establece el número de sectores "sectorsNumber" y la viscosidad del agua "waterViscosity" en los valores especificados.
6. Cambia el tamaño del array "sectorSpace" en "coord".
7. Cambia el tamaño del array "p" en "popSize" e inicializa cada gota de agua en el array "p".
8. Cambia los tamaños de los arrays "rangeMax", "rangeMin", "rangeStep" y "cB" a"coords".
9. Cambia el tamaño del array "rb" a "coords" e inicializa cada elemento del array "rb", incluidos los arrays "riverbedDepth" y "coordOnSector", estableciendo sus valores por defecto.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_IWDm::Init (const int coordsP, //coordinates number const int popSizeP, //population size const int sectorsNumberP, //sectors number const double waterViscosityP) //water viscosity (>= 1) { MathSrand ((int)GetMicrosecondCount ()); // reset of the generator fB = -DBL_MAX; iterationCounter = 0; coords = coordsP; popSize = popSizeP; sectorsNumber = sectorsNumberP; waterViscosity = waterViscosityP; ArrayResize (sectorSpace, coords); ArrayResize (p, popSize); for (int i = 0; i < popSize; i++) p [i].Init (coords); ArrayResize (rangeMax, coords); ArrayResize (rangeMin, coords); ArrayResize (rangeStep, coords); ArrayResize (cB, coords); ArrayResize (rb, coords); for (int i = 0; i < coords; i++) { ArrayResize (rb [i].riverbedDepth, sectorsNumber); ArrayResize (rb [i].coordOnSector, sectorsNumber); ArrayInitialize (rb [i].riverbedDepth, 0.0); ArrayInitialize (rb [i].coordOnSector, -DBL_MAX); } } //——————————————————————————————————————————————————————————————————————————————
Analicemos ahora el método Moving () por partes.
Este bloque de código se ejecutará solo en la primera y segunda iteraciones. Este calcula y establece el tamaño de cada sector "sectorSpace" para cada coordenada. El tamaño del sector se determinará dividiendo el rango de valores "rangeMax - rangeMin" por el número de sectores "sectorsNumber".
A continuación, se ejecutará la inicialización de las gotas con valores iniciales basados en valores aleatorios en rangos especificados con distribución uniforme.
//---------------------------------------------------------------------------- if (iterationCounter == 0) { for (int i = 0; i < coords; i++) sectorSpace [i] = (rangeMax [i] - rangeMin [i]) / sectorsNumber; } //1,4------------------------------------------------------------------------- if (iterationCounter == 0 || iterationCounter == 1) { double min = 0.0; double max = 0.0; int s = 0; for (int i = 0; i < popSize; i++) { p [i].fPrev = p [i].f; for (int c = 0; c < coords; c++) { s = (int)(RNDfromCI (0, sectorsNumber)); if (s >= sectorsNumber) s = sectorsNumber - 1; p [i].rSection [c] = s; min = rangeMin [c] + sectorSpace [c] * s; max = min + sectorSpace [c]; p [i].c [c] = SeInDiSp (RNDfromCI (min, max), rangeMin [c], rangeMax [c], rangeStep [c]); } } for (int i = 0; i < popSize; i++) p [i].fPrev = p [i].f; return; }
A continuación, el fragmento de código realizará el cálculo y la normalización de los cambios de altura "altChange" para cada gota de la población. La única sutileza en este código consistirá en comprobar la igualdad del cambio de altura máximo y mínimo para evitar la división por "0", en cuyo caso supondremos que no ha habido ningún cambio en las alturas de las gotas.
El valor "altChange" de cada gota se calculará como un valor normalizado que se normalizará en un intervalo de 0 a 1. La normalización se realizará restando "minAltChange" a "altChange" y dividiendo el resultado por la diferencia entre "maxAltChange" y "minAltChange".
//7--------------------------------------------------------------------------- double maxAltChange = -DBL_MAX; double minAltChange = DBL_MAX; double altChange = 0.0; double randSC = 0.0; //random selection component double maxRC = 0.0; double nowRC = 0.0; int indSector = 0; for (int i = 0; i < popSize; i++) { altChange = fabs (p [i].f - p [i].fPrev); p [i].altChange = altChange; if (altChange < minAltChange) minAltChange = altChange; if (altChange > maxAltChange) maxAltChange = altChange; } if (minAltChange == maxAltChange) { for (int i = 0; i < popSize; i++) { p [i].altChange = 0.0; } } else { for (int i = 0; i < popSize; i++) { altChange = p [i].altChange; p [i].altChange = (altChange - minAltChange) / (maxAltChange - minAltChange); } }
El siguiente fragmento de código actualiza la profundidad del cauce para cada coordenada si el valor actual de la función de aptitud es mayor que el valor anterior para la caída correspondiente. Esto permitirá tener en cuenta los cambios de elevación e influirá en la forma del cauce del río. Así, cada vez que una gota haya mejorado su posición consideraremos que el cauce del río ha cambiado.
//8--------------------------------------------------------------------------- for (int i = 0; i < popSize; i++) { if (p [i].f > p [i].fPrev) { for (int c = 0; c < coords; c++) { rb [c].riverbedDepth [p [i].rSection [c]] += p [i].altChange; } } }
En el siguiente fragmento de código, se realizarán dos acciones principales para cambiar las coordenadas de los agentes que proporcionan la estrategia de búsqueda:
- la gota selecciona aleatoriamente otra gota de la población y le toma prestado el número de sector, se garantizan las propiedades combinatorias del algoritmo
- la gota selecciona un sector del río al azar en proporción a la profundidad conocida en cada sector
Una vez seleccionado un sector, generaremos una nueva coordenada para la gota con una distribución uniforme si el sector ha sido tomado de otra gota, y con una distribución de función cuadrática si el sector se ha seleccionado a partir de la información almacenada en el cauce del río. El valor obtenido para cada coordenada se situará en el intervalo admisible.
//9--------------------------------------------------------------------------- for (int i = 0; i < popSize; i++) { for (int c = 0; c < coords; c++) { n = (int)(RNDfromCI (0, popSize)); if (n >= popSize) n = popSize - 1; if (p [n].f > p [i].f) { p [i].rSection [c] = p [n].rSection [c]; min = rangeMin [c] + sectorSpace [c] * p [i].rSection [c]; max = min + sectorSpace [c]; p [i].c [c] = SeInDiSp (RNDfromCI (min, max), rangeMin [c], rangeMax [c], rangeStep [c]); } else { randSC = RNDfromCI (0.0, 1.0); nowRC = rb [c].riverbedDepth [0] * randSC; maxRC = nowRC; indSector = 0; for (int r = 1; r < sectorsNumber; r++) { nowRC = rb [c].riverbedDepth [r] * randSC; if (nowRC > maxRC) { maxRC = nowRC; indSector = r; } } if (rb [c].coordOnSector [indSector] == -DBL_MAX) { min = rangeMin [c] + sectorSpace [c] * indSector; max = min + sectorSpace [c]; p [i].c [c] = RNDfromCI (min, max); } else { double x = RNDfromCI (-1.0, 1.0); double y = x * x; double pit = 0.0; double dif = Scale (y, 0.0, 1.0, 0.0, sectorSpace [c] * waterViscosity, false); pit = rb [c].coordOnSector [indSector]; pit += x > 0.0 ? dif : -dif; p [i].c [c] = pit; } min = rangeMin [c] + sectorSpace [c] * indSector; max = min + sectorSpace [c]; p [i].c [c] = SeInDiSp (p [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); p [i].rSection [c] = indSector; } } }
A continuación, actualizaremos el valor de aptitud anterior "fPrev" para cada gota de agua si el valor actual de la función de aptitud `f` es mayor que el valor anterior. Esto nos permite seguir los cambios en la función objetivo y usar esta información en el algoritmo para tomar decisiones sobre la elección del siguiente paso.
for (int i = 0; i < popSize; i++) { if (p [i].f > p [i].fPrev) p [i].fPrev = p [i].f; }
Y, por último, está el método Revision. Está diseñado para actualizar la mejor solución "cB" y su correspondiente valor de función de aptitud. Si en la iteración actual se encuentra una solución mejor, guardaremos la coordenada del sector correspondiente. De este modo, el cauce recordará los lugares más profundos de cada sector en cada coordenada. En este método incrementaremos en uno el contador de iteraciones "iterationCounter", para que en el método Moving podamos orientarnos y realizar las acciones correspondientes a las iteraciones.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_IWDm::Revision () { //3,6,11---------------------------------------------------------------------- for (int i = 0; i < popSize; i++) { if (p [i].f > fB) { fB = p [i].f; ArrayCopy (cB, p [i].c, 0, 0, WHOLE_ARRAY); for (int c = 0; c < coords; c++) { rb [c].coordOnSector [p [i].rSection [c]] = p [i].c [c]; } } else { for (int c = 0; c < coords; c++) { if (rb [c].coordOnSector [p [i].rSection [c]] == -DBL_MAX) { rb [c].coordOnSector [p [i].rSection [c]] = p [i].c [c]; } } } } iterationCounter++; } //——————————————————————————————————————————————————————————————————————————————
3. Versión modificada de SDSm
Comentaremos los resultados del algoritmo IWDm más adelante, pero nos han dado una idea para intentar mejorar otro algoritmo (el mejor de la clasificación): el SDS, porque tanto IWDm como SDS utilizan entidades similares (sectores y restaurantes, respectivamente). El método utilizado en IWD, es decir, el refinamiento de coordenadas usando una distribución de probabilidad cuadrática, ha contribuido a mejorar aún más el SDS: la mejor técnica de refinamiento de posiciones ha tenido un gran impacto en los resultados finales de las pruebas. La única diferencia es que en el SDSm la distribución se trunca si está orientada hacia un restaurante vecino.
Asimismo, hemos introducido cambios en el método de revisión del algoritmo SDS y, debido a cambios significativos en la distribución de las nuevas coordenadas dentro del restaurante (antes era uniforme) y en los resultados de las pruebas, hemos asignado al algoritmo el índice "m".
En el código, vemos que la distribución de la variable aleatoria es ahora responsabilidad de la función Research, que toma como argumentos el factor de amplitud de la distribución, la dirección del restaurante, el tamaño del restaurante, el valor mínimo posible en la coordenada, el paso en la coordenada, la aptitud en el paso anterior y la coordenada que intentamos mejorar.
En el algoritmo SDSm, intentaremos mejorar tres tipos de coordenadas (platos en restaurantes):
- la coordenada del candidato entrevistado
- la mejor coordenada en un restaurante seleccionado al azar (al igual que en IWDm para el cauce del río en SDSm almacenaremos las mejores coordenadas para todos los restaurantes, es como almacenar una lista de los mejores platos en todos los restaurantes de la ciudad).
- nuestras propias coordenadas para el restaurante correspondiente.
Podríamos haber puesto los coeficientes de la anchura de la distribución de probabilidad en los parámetros externos, pero no lo hemos hecho, hemos puesto los mejores valores en mi opinión.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_SDSm::Revision () { /* el código aquí es el antiguo, sin cambios */ for (int i = 0; i < populationSize; i++) { for (int c = 0; c < coords; c++) { n = (int)(RNDfromCI (0, populationSize)); if (n >= populationSize) n = populationSize - 1; if (cands [n].fPrev > cands [i].fPrev) { cands [i].raddr [c] = cands [n].raddrPrev [c]; Research (0.25, cands [i].raddr [c], restSpace [c], rangeMin [c], rangeStep [c], cands [n].cPrev [c], cands [i].c [c]); } else { rnd = RNDfromCI (0.0, 1.0); if (rnd < probabRest) { n = (int)(RNDfromCI (0, restNumb)); if (n >= restNumb) n = restNumb - 1; cands [i].raddr [c] = n; Research (1.0, cands [i].raddr [c], restSpace [c], rangeMin [c], rangeStep [c], rb [c].coordOnSector [n], cands [i].c [c]); } else { cands [i].raddr [c] = cands [i].raddrPrev [c]; Research (0.25, cands [i].raddr [c], restSpace [c], rangeMin [c], rangeStep [c], cands [i].cPrev [c], cands [i].c [c]); } } } } } //——————————————————————————————————————————————————————————————————————————————
Y aquí está la misma característica "mágica" de Research que ha mejorado al anterior líder de la prueba en más de un 12%.
La función hace lo siguiente:
- genera un número aleatorio en el rango [-1,0;1,0],
- el valor obtenido se escala al incremento correspondiente al tamaño del restaurante con el coeficiente de escala de distribución
- se añade a la coordenada actual que se está refinando
- se definen los límites del restaurante
- el número se convierte en valores aceptables según el paso del parámetro optimizado con truncamiento a lo largo de los límites del restaurante
//—————————————————————————————————————————————————————————————————————————————— void C_AO_SDSm::Research (const double ko, const int raddr, const double restSpaceI, const double rangeMinI, const double rangeStepI, const double pitOld, double &pitNew) { double x = RNDfromCI(-1.0, 1.0); double y = x * x; double pit = pitOld; double min = 0.0; double max = 0.0; double dif = Scale(y, 0.0, 1.0, 0.0, restSpaceI * ko, false); pit += x > 0.0 ? dif : -dif; min = rangeMinI + restSpaceI * raddr; max = min + restSpaceI; pitNew = SeInDiSp (pit, min, max, rangeStepI); } //——————————————————————————————————————————————————————————————————————————————
4. Resultados de las pruebas
Impresión del funcionamiento del algoritmo IWD en el banco de pruebas:
C_AO_IWDm:50;10;3.0
=============================
5 Rastrigin's; Func runs 10000 result: 63.304838882364926
Score: 0.78438
25 Rastrigin's; Func runs 10000 result: 49.20424466627239
Score: 0.60967
500 Rastrigin's; Func runs 10000 result: 39.68464591598694
Score: 0.49172
=============================
5 Forest's; Func runs 10000 result: 0.6975685023058024
Score: 0.39458
25 Forest's; Func runs 10000 result: 0.19878497533879688
Score: 0.11244
500 Forest's; Func runs 10000 result: 0.0569274044494088
Score: 0.03220
=============================
5 Megacity's; Func runs 10000 result: 3.44
Score: 0.28667
25 Megacity's; Func runs 10000 result: 1.088
Score: 0.09067
500 Megacity's; Func runs 10000 result: 0.28480000000000005
Score: 0.02373
=============================
All score: 2.82606
Los resultados se encuentran, por decirlo suavemente, por debajo de la media en la tabla comparativa.
Impresión del funcionamiento del algoritmo SDSm en el banco de pruebas:
C_AO_SDSm:100;100;0.05
=============================
5 Rastrigin's; Func runs 10000 result: 80.65976429448276
Score: 0.99942
25 Rastrigin's; Func runs 10000 result: 79.95659847225565
Score: 0.99071
500 Rastrigin's; Func runs 10000 result: 57.23107170601535
Score: 0.70913
=============================
5 Forest's; Func runs 10000 result: 1.7241883676504082
Score: 0.97529
25 Forest's; Func runs 10000 result: 1.497160007591401
Score: 0.84687
500 Forest's; Func runs 10000 result: 0.29481739063639945
Score: 0.16676
=============================
5 Megacity's; Func runs 10000 result: 10.559999999999999
Score: 0.88000
25 Megacity's; Func runs 10000 result: 6.824000000000001
Score: 0.56867
500 Megacity's; Func runs 10000 result: 1.2384
Score: 0.10320
=============================
All score: 6.24004
Los resultados del SDSm, en cambio, son realmente impresionantes.
En la visualización animada del algoritmo IWDm se observa cierto grado de capacidad para agrupar zonas de búsqueda potencialmente buenas, especialmente con la función Rastrigin. Sin embargo, las partes largas y suaves del gráfico de convergencia también muestran que el algoritmo se atasca.
IWDm en la función de prueba Rastrigin.
IWDm en la función de prueba Forest.
IWDm en la función de prueba Megacity.
En este artículo, hemos analizado el algoritmo IWDm, que ocupa el puesto 19 entre 22 algoritmos, es decir, el cuarto por la cola, superando al conocido y popular algoritmo PSO. El IWDm funciona mejor en rasgos suaves. La mejora constante del gráfico de convergencia en las tres funciones de prueba da esperanzas de que el algoritmo siga convergiendo cuando aumente el número de iteraciones, pero entonces se perderá el sentido práctico y la conveniencia de su aplicación: la condición de las pruebas de prueba es rígida, 10000 iteraciones, ni más ni menos.
También destaca el algoritmo SDSm modificado, que ha obtenido 7 de los 9 primeros puestos posibles. Este algoritmo resulta un auténtico "todoterreno" entre los algoritmos de optimización. La mejora de los resultados del SDSm con respecto al SDS convencional en las funciones "afiladas" Forest y Megacity discreta compleja resulta especialmente notable (en esta última función, la mejora es de casi el 30% con 1 000 parámetros). Así, además del principal protagonista del artículo, la IWD, vemos un nuevo y espléndido invitado a la mesa, el SDSm. La animación del funcionamiento de SDS se puede ver aquí, y para observar el funcionamiento de SDSm deberemos ejecutar el script de prueba del archivo, que se encuentra en la carpeta con SDS.
| № | 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 | 1,00000 | 1,00000 | 1,00000 | 3,00000 | 1,00000 | 1,00000 | 1,00000 | 3,00000 | 100,000 |
| 2 | SDS | stochastic Diffusion Search | 0,99737 | 0,97322 | 0,58904 | 2,55963 | 0,96778 | 0,93572 | 0,79649 | 2,69999 | 0,78696 | 0,93815 | 0,71804 | 2,44315 | 88,208 |
| 3 | SSG | saplings sowing and growing | 1,00000 | 0,92761 | 0,51630 | 2,44391 | 0,72654 | 0,65201 | 0,83760 | 2,21615 | 0,54782 | 0,61841 | 0,99522 | 2,16146 | 77,678 |
| 4 | HS | harmony search | 0,99676 | 0,88385 | 0,44686 | 2,32747 | 0,99882 | 0,68242 | 0,37529 | 2,05653 | 0,71739 | 0,71842 | 0,41338 | 1,84919 | 70,647 |
| 5 | IWO | invasive weed optimization | 0,95828 | 0,62227 | 0,27647 | 1,85703 | 0,70690 | 0,31972 | 0,26613 | 1,29275 | 0,57391 | 0,30527 | 0,33130 | 1,21048 | 48,267 |
| 6 | ACOm | ant colony optimization M | 0,34611 | 0,16683 | 0,15808 | 0,67103 | 0,86785 | 0,68980 | 0,64798 | 2,20563 | 0,71739 | 0,63947 | 0,05579 | 1,41265 | 47,419 |
| 7 | MEC | mind evolutionary computation | 0,99270 | 0,47345 | 0,21148 | 1,67763 | 0,60691 | 0,28046 | 0,21324 | 1,10061 | 0,66957 | 0,30000 | 0,26045 | 1,23002 | 44,061 |
| 8 | COAm | cuckoo optimization algorithm M | 0,92400 | 0,43407 | 0,24120 | 1,59927 | 0,58309 | 0,23477 | 0,13842 | 0,95629 | 0,52174 | 0,24079 | 0,17001 | 0,93254 | 37,845 |
| 9 | FAm | firefly algorithm M | 0,59825 | 0,31520 | 0,15893 | 1,07239 | 0,51012 | 0,29178 | 0,41704 | 1,21894 | 0,24783 | 0,20526 | 0,35090 | 0,80398 | 33,152 |
| 10 | ABC | artificial bee colony | 0,78170 | 0,30347 | 0,19313 | 1,27829 | 0,53774 | 0,14799 | 0,11177 | 0,79750 | 0,40435 | 0,19474 | 0,13859 | 0,73768 | 29,784 |
| 11 | BA | bat algorithm | 0,40526 | 0,59145 | 0,78330 | 1,78002 | 0,20817 | 0,12056 | 0,21769 | 0,54641 | 0,21305 | 0,07632 | 0,17288 | 0,46225 | 29,488 |
| 12 | CSS | charged system search | 0,56605 | 0,68683 | 1,00000 | 2,25289 | 0,14065 | 0,01853 | 0,13638 | 0,29555 | 0,07392 | 0,00000 | 0,03465 | 0,10856 | 27,914 |
| 13 | GSA | gravitational search algorithm | 0,70167 | 0,41944 | 0,00000 | 1,12111 | 0,31623 | 0,25120 | 0,27812 | 0,84554 | 0,42609 | 0,25525 | 0,00000 | 0,68134 | 27,807 |
| 14 | BFO | bacterial foraging optimization | 0,67203 | 0,28721 | 0,10957 | 1,06881 | 0,39655 | 0,18364 | 0,17298 | 0,75317 | 0,37392 | 0,24211 | 0,18841 | 0,80444 | 27,549 |
| 15 | 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 | 18,981 |
| 16 | SFL | shuffled frog-leaping | 0,40072 | 0,22021 | 0,24624 | 0,86717 | 0,20129 | 0,02861 | 0,02221 | 0,25211 | 0,19565 | 0,04474 | 0,06607 | 0,30646 | 13,201 |
| 17 | MA | monkey algorithm | 0,33192 | 0,31029 | 0,13582 | 0,77804 | 0,10000 | 0,05443 | 0,07482 | 0,22926 | 0,15652 | 0,03553 | 0,10669 | 0,29874 | 11,771 |
| 18 | SFS | fish school search | 0,46812 | 0,23502 | 0,10483 | 0,80798 | 0,12825 | 0,03458 | 0,05458 | 0,21741 | 0,12175 | 0,03947 | 0,08244 | 0,24366 | 11,329 |
| 19 | IWDm | intelligent water drops M | 0,26459 | 0,13013 | 0,07500 | 0,46972 | 0,28568 | 0,05445 | 0,05112 | 0,39126 | 0,22609 | 0,05659 | 0,05054 | 0,33322 | 10,434 |
| 20 | PSO | particle swarm optimisation | 0,20449 | 0,07607 | 0,06641 | 0,34696 | 0,18873 | 0,07233 | 0,18207 | 0,44313 | 0,16956 | 0,04737 | 0,01947 | 0,23641 | 8,431 |
| 21 | RND | random | 0,16826 | 0,09038 | 0,07438 | 0,33302 | 0,13480 | 0,03318 | 0,03949 | 0,20747 | 0,12175 | 0,03290 | 0,04898 | 0,20363 | 5,056 |
| 22 | GWO | grey wolf optimizer | 0,00000 | 0,00000 | 0,02093 | 0,02093 | 0,06562 | 0,00000 | 0,00000 | 0,06562 | 0,23478 | 0,05789 | 0,02545 | 0,31812 | 1,000 |
Conclusiones
El algoritmo IWD original fue desarrollado por el autor para resolver problemas de búsqueda del camino más corto, como la logística del transporte, el enrutamiento de redes y la búsqueda de caminos óptimos en sistemas de información geográfica. En este trabajo no se han considerado sus capacidades y el rendimiento en estas tareas específicas, mientras que el nuevo algoritmo IWDm modificado, presentado como algoritmo universal, no ha logrado mostrar resultados impresionantes. Desgraciadamente, aumentando el número de sectores no se ha aumentado la eficacia del algoritmo.
No obstante, el trabajo sobre el algoritmo IWDm ha dejado la sensación de que aún no se ha aprovechado todo el potencial de este elegante algoritmo. La idea de dividir el espacio de búsqueda en sectores y considerar su clasificación basándose en la modelización del movimiento de la tierra en el cauce del río parece muy interesante. Como han demostrado los resultados, un enfoque de este tipo, como mantener los mejores platos en cada restaurante y, posiblemente, utilizar el desplazamiento de probabilidad de un nuevo punto en la vecindad del punto anterior, ha mejorado significativamente el rendimiento del algoritmo SDS.
Y lo que es importante, si aumentamos el número de restaurantes en el nuevo SDSm (el parámetro por defecto es 100) y dividimos las coordenadas en áreas más pequeñas (SDS utiliza el parámetro 1000), los resultados empeorarán. Esto significa que, con este enfoque, la elección de un restaurante individual adquirirá mayor importancia, y un punto concreto de su vecindad dejará de ser relevante (el algoritmo se convierte en un SDS normal). De ello podemos deducir que la distribución de probabilidad cuadrática tiene una influencia máxima en las coordenadas a partir de un determinado tamaño de sector. Se trata de una especie de equilibrio entre los distintos métodos presentes en el algoritmo.
La conclusión más importante de este artículo es que no podemos afirmar inequívocamente qué técnica o método utilizado en las estrategias de búsqueda individuales es el mejor o el peor. La aplicación de distintos métodos puede tanto empeorar algunos algoritmos como mejorar notablemente otros. Lo importante es la combinación de los métodos usados en los algoritmos de optimización, no los métodos por separado.
Figura 2. Clasificación por colores de los algoritmos según sus respectivas pruebas.
Histograma con los resultados de los algoritmos de prueba en la figura 3 (en una escala de 0 a 100, cuanto más mejor; en el archivo hay un script para calcular la tabla de clasificación según la metodología de este artículo):
Figura 3. Histograma con los resultados finales de las pruebas del algoritmo.
Ventajas e inconvenientes del algoritmo de gotas de agua inteligentes modificado (IWDm):
Ventajas:
1. Número reducido de parámetros externos.
Desventajas:
1. Malos resultados sobre funciones suaves y discretas.
2. Baja convergencia.
3. Tendencia a estancarse en los extremos locales.
Adjunto al artículo encontrará un archivo con 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/13730
Validación cruzada simétrica combinatoria en MQL5
Desarrollo de un sistema de repetición (Parte 41): Inicio de la segunda fase (II)
Patrones de diseño en MQL5 (Parte I): Patrones de creación (Creational Patterns)
Cómo desarrollar un agente de aprendizaje por refuerzo en MQL5 con integración RestAPI (Parte 4): Organización de funciones en clases en MQL5
- 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