En este estudio se introduce un nuevo algoritmo para la metaheurística de optimización de colonias de hormigas (ACO) que se ha desarrollado para resolver problemas de optimización global con variables de decisión continuas. El algoritmo propuesto, denominado ACO-FRS, comprende una estrategia para la selección de regiones factibles para el proceso de optimización y realiza la exploración del espacio de solución de forma similar al proceso que realizan las hormigas para la búsqueda de alimento. Se han evaluado 4variantes de este algoritmo empleando varios problemas clásicos de optimización global, y los resultados obtenidos se han comparado con los informados en la literatura para otros algoritmos del tipo ACO para espacios continuos. En general, los resultados obtenidos indican que la inclusión de una selección de regiones factibles permite realizar una búsqueda global mediante la eventual exploración de regiones con bajos niveles de feromonas, aumentando así la viabilidad del método para la localización de la solución del problema de optimización.
This study introduces a new algorithm for the ant colony optimization (ACO) method, which has been proposed to solve global optimization problems with continuous decision variables. This algorithm, namely ACO-FRS, involves a strategy for the selection of feasible regions during optimization search and it performs the exploration of the search space using a similar approach to that used by the ants during the search of food. Four variants of this algorithm have been tested in several benchmark problems and the results of this study have been compared with those reported in literature for other ACO-type methods for continuous spaces. Overall, the results show that the incorporation of the selection of feasible regions allows the performing of a global search to explore those regions with low level of pheromone, thus increasing the feasibility of ACO for finding the global optimal solution.
La mejora de las capacidades de cómputo y la formulación rigurosa de los problemas con modelos precisos ha abierto la posibilidad de plantear diversos problemas de ingeniería altamente no lineales y complejos como problemas de optimización. En ingeniería química, como ejemplo de los diversos campos de aplicación, la optimización es clave para la calendarización de actividades y la operación de reactores, los procesos de separación, el análisis de redes de intercambiadores de calor y el diseño de plantas completas [1]. Sin el uso de técnicas de optimización, los procesos industriales no serían tan eficientes como ahora. En varias aplicaciones es necesario encontrar el óptimo global, y no solo un óptimo local, ya que el primero es obviamente mejor que el segundo en términos del valor de la función objetivo planteada. Incluso en algunas aplicaciones, el óptimo global es la única solución correcta y con significado físico para el sistema analizado.
Los métodos de optimización global se pueden clasificar en 2 grandes grupos: técnicas deterministas y estocásticas (o probabilísticas). Los métodos actuales de optimización global deterministas pueden ser demasiado costosos (en términos de esfuerzo computacional), sobre todo para problemas multivariables, y en algunos casos requieren reformulaciones del problema dependiendo de las características del modelo utilizado. En el caso de las técnicas estocásticas de optimización global (SGO, por sus siglas en inglés) intervienen elementos probabilísticos y, por consiguiente, se utilizan números aleatorios durante la búsqueda del óptimo global. Las técnicas SGO tienen diferentes características que son atractivas para el campo de la ingeniería: son simples y fáciles de implementar, no requieren estimaciones previas, pueden resolver una gran variedad de problemas, tienen la capacidad de proveer resultados robustos para problemas altamente no lineales con múltiples variables de decisión y generalmente presentan una rápida convergencia hacia la solución óptima [1–3]. Estos métodos explotan diversas estrategias numéricas basadas en conceptos heurísticos para diversificar e intensificar la búsqueda en algunas áreas promisorias durante la localización del óptimo global, escapando así de los mínimos locales de la función objetivo.
En particular, las técnicas SGO que adaptan ideas de comportamientos naturales de poblaciones de individuos se catalogan como métodos de inteligencia de enjambre, y estos métodos de optimización normalmente se consideran efectivos para la resolución de diferentes tipos de problemas. En particular, el algoritmo de optimización con colonias de hormigas (ACO, por sus siglas en inglés) está inspirado en la capacidad de las hormigas (en una colonia) para interactuar de manera eficaz en el proceso de búsqueda de alimento [4]. Hasta la fecha se han probado diferentes algoritmos de optimización del tipo ACO en problemas diversos, y los resultados indican que estos poseen un desempeño destacado, especialmente en problemas con múltiples variables y espacios discretos [5,6]. En particular, ACO ha encontrado aplicaciones en la resolución de problemas reales de las ciencias básicas y aplicadas. Concretamente, este método se ha probado con éxito en problemas clásicos tales como el problema del vendedor viajero [4,7,8], el problema de asignación cuadrática [6,9,10], la determinación de rutas de vehículos [11–13], aplicaciones industriales de problemas de calendarización [14,15], la optimización dinámica de procesos químicos [16], entre otros. Es conveniente indicar que los algoritmos del tipo ACO inicialmente se diseñaron para aplicaciones en optimización combinatoria, es decir, problemas de optimización discretos [6].
Es necesario señalar que la mayor parte de los problemas de optimización asociados a aplicaciones de ingeniería y diseño se catalogan como problemas de optimización continuos, puesto que las variables de optimización pueden tomar cualquier valor numérico real dentro de los límites establecidos. Generalmente, estos problemas presentan un número significativo de variables de optimización y las funciones objetivo son altamente no lineales y, por tanto, para su resolución se requieren métodos robustos y preferiblemente con una rápida convergencia. Bajo esta perspectiva, los métodos de optimización estocásticos basados en la metaheurística de ACO son una opción atractiva para la resolución efectiva de este tipo de problemas.
La primera aplicación de colonias artificiales de hormigas para la resolución de funciones continuas la realizaron Bilchev y Pramee [17,18]. Estos trabajos solo utilizaron procedimientos de búsqueda local como parte del algoritmo ACO. Posteriormente, Wodrich y Bilchev [19] extendieron estas estrategias para la resolución de problemas de optimización global mediante la inclusión del concepto de hormigas «locales y globales». Las hormigas «globales» usan mecanismos de caminata aleatoria y difusión de rastro de feromonas, mientras que las hormigas «locales» tienen la capacidad de percibir el rastro de feromonas que han depositado las hormigas «globales». El algoritmo descrito se conoce como ACO-continuo (CACO), y su desempeño numérico fue mejorado posteriormente en otros estudios mediante la implementación de nuevos conceptos en la etapa de búsqueda global [14,20,21]. Por otra parte, API es otro algoritmo basado en el comportamiento de hormigas enfocado a espacios continuos [22]. El mecanismo base de API imita el comportamiento particular de la especie Pachycondyla apicalis en el proceso de caza de presas. En API, cada hormiga busca de forma independiente una solución mejor, aunque todas las hormigas empiezan desde el mismo punto, es decir, el nido. La exploración global se lleva a cabo mediante una caminata en tándem, en la que toda la colonia cambia su posición para cazar en otras regiones. Este algoritmo también utiliza una estrategia de reclutamiento para refinar la búsqueda; a dicha búsqueda local se la conoce como captura de presas, donde las hormigas utilizan mecanismos de comunicación directa y poseen una memoria limitada. En otro estudio, Dréo y Siarry [23] propusieron el algoritmo continuo de colonia de hormigas cooperativas (CIAC), en el cual se demuestra que es posible llevar a cabo la tarea de reclutamiento sin tener en cuenta los rastros de feromonas típicos de las estrategias ACO y el proceso de búsqueda se basa en relaciones entre individuos. Pourtakdoust y Nobahari [24] propusieron el algoritmo CACS, donde la función probabilística discreta basada en feromonas se reemplaza por una función de densidad de probabilidad del tipo gaussiana (normal) cuyos parámetros de media y varianza adaptan las hormigas de manera dinámica en cada iteración. Recientemente, Socha y Dorigo [25] propusieron un nuevo algoritmo ACO para espacios continuos, identificado como ACOR, que mantiene un archivo de las soluciones generadas en iteraciones previas. Las soluciones en el archivo se ordenan considerando el valor de la función objetivo y posteriormente se clasifican para asignar un factor de peso a cada solución. Dicho peso corresponde al rastro de feromonas y, al igual que en CACS, las hormigas usan distribuciones de probabilidad en cada paso de construcción de una solución. Finalmente, De França et al. [26] reportaron otro algoritmo tipo ACO para espacios continuos que está basado en una modificación de las funciones gaussianas para adaptar simultáneamente todas las dimensiones de la distribución aleatoria y generar nuevos individuos en cada iteración.
Cabe mencionar que los resultados de estudios comparativos reportados en la literatura [25] indican que los algoritmos ACO existentes para espacios continuos aún pueden presentar problemas de convergencia prematura para la localización del óptimo global. A pesar de que existen estrategias del tipo ACO que se han aplicado a la resolución de problemas continuos, todavía existen áreas de oportunidad para mejorar el desempeño numérico de los algoritmos ACO para la resolución de problemas multivariables. Hasta la fecha, una posibilidad inexplorada para mejorar el desempeño numérico de ACO consiste en almacenar la información del rastro de feromonas en cada dimensión del archivo de soluciones y adaptar el concepto de regiones factibles propio de los problemas combinatoriales que inicialmente fueron el campo de aplicación de las estrategias ACO. Teniendo en cuenta lo anterior, en este estudio se ha propuesto un algoritmo de optimización alternativo, referido como ACO con selección de región factible (ACO-FRS), con el propósito de fortalecer el desempeño de dicha metaheurística en la resolución de problemas multivariables con espacios continuos. Específicamente, ACO-FRS realiza la exploración del espacio de solución de forma similar al proceso que realizan las hormigas para buscar y recolectar alimento, explorando diferentes regiones y siendo capaces de encontrar el camino más corto después de un determinado tiempo. El desempeño de este algoritmo alternativo se ilustra con diferentes funciones objetivo clásicas del área de optimización global. Además, los resultados obtenidos con ACO-FRS se han comparado con el desempeño numérico de los algoritmos CACS [24], ACOR[25] y MACACO [26].
2Descripción de la metaheurística de colonias de hormigasLos estudios del desempeño colectivo de las hormigas abarcan el análisis de su comportamiento cuando buscan y transportan forraje (alimento), la división de labores, la organización de sus cementerios y el envío de ayuda. En particular, la búsqueda de forraje es el comportamiento que más se ha modelado debido a que genera un mecanismo complejo y eficiente con individuos no tan sofisticados [27]. En la literatura, Deneubourg et al. [28] describieron un ejemplo particular de comunicación indirecta entre individuos basada en deposiciones de químicos (feromonas) en la región por la que la hormiga ha explorado y encontrado alimento. Con base en dicho mecanismo de comunicación, Dorigo [4] propuso el primer algoritmo que modelaba la tarea de recolección de forraje como una estrategia colectiva, cuyas primeras implementaciones representaron el surgimiento de los algoritmos de optimización del tipo colonia de hormigas.
En la figura 1a se presenta el pseudocódigo para la modelación del proceso decisivo de una hormiga real, que se describe como la serie de pasos que una hormiga artificial realiza cuando pretende elegir entre NR rutas potenciales. La probabilidad de selección p(z) es proporcional a la concentración de feromonas de la ruta z con respecto a las demás. Cuando el proceso de decisión mostrado en la figura 1a lo realiza un conjunto de hormigas (agentes), y este forma parte de un mecanismo de búsqueda de rutas más cortas, dicho proceso se conoce como construcción de la solución y es una de las 3actividades básicas de la metaheurística ACO [29,30]. Dichas actividades se presentan en la metaheurística mostrada en la figura 1b, donde se modela el comportamiento de búsqueda y transporte de forraje que ha sido la base para la codificación de la mayor parte de los algoritmos de ACO reportados en la literatura.
Dorigo y Stützle [31] desarrollaron el algoritmo simple de optimización con colonia de hormigas (SACO) como una propuesta sencilla para analizar las propiedades de la metaheurística ACO. En el presente estudio se toma como base la estructura conceptual de dicho algoritmo y se adapta a espacios continuos. A continuación se presenta una breve descripción del mecanismo de optimización de SACO considerando el problema clásico de optimización combinatoria donde se requiere encontrar el camino más corto entre 2nodos de una gráfica G=(V,E), donde V es el conjunto de vértices (nodos) y E es la matriz de conexiones entre los nodos. La longitud Lk del camino construido, en una etapa (k) de un proceso iterativo, se calcula como el número de saltos entre nodos desde el inicio hasta el destino. Como parte de la primera actividad en SACO, se asocia una concentración inicial (valor aleatorio pequeño) de feromonas o rastro de feromonas τij a cada posible conexión entre dos nodos (i,j). Un determinado número de hormigas k=1,2,…,NA, que corresponde a una etapa del proceso iterativo, se ubica en el nodo de inicio. Usando la lógica de decisión de la figura 1a, cada hormiga construye un camino (solución) hacia el nodo destino. Si una hormiga k se localiza temporalmente en el nodo i, esta seleccionará el nodo j∈Nik considerando la siguiente probabilidad de transición [31]:
donde Nik es el conjunto de nodos factibles conectados a i para la hormiga k. Dicha probabilidad varía conforme se realiza el proceso de minimización o, en otras palabras, en función del tiempo t. La constante α toma valores positivos y se utiliza para amplificar la influencia de la concentración de feromonas. Si, para algún nodo i, una hormiga k encuentra Nik=0, entonces el nodo predecesor de i se incluye en Nik. Esta situación puede causar que se generen lazos internos mientras se construye la solución. Una vez que todas las hormigas han construido un camino completo desde el nodo de origen hasta el nodo destino, se eliminan todos los lazos internos (en caso de presentarse) y cada hormiga recorre nuevamente el camino construido hasta el nodo de origen de manera determinista. En este proceso se deposita una cantidad específica de feromonas Δτijk(t) en cada conexión. Las conexiones actualizan su concentración de feromonas mediante la siguiente expresión [31]:
La intensificación del rastro de feromonas para el camino recorrido es el resultado de la cantidad depositada por cada hormiga en cada conexión, y para la evaluación de dicha cantidad se pueden considerar cualquiera de las siguientes estrategias [27]:
a) Evaluación explícita. El incremento en la concentración o intensidad del rastro contiene información sobre la calidad de la solución generada. Para SACO, la calidad de la solución (del camino construido) se expresa simplemente como el inverso de la longitud del camino, es decir:
b) Evaluación implícita. Las hormigas hacen uso del efecto de longitud diferencial de camino a través de la búsqueda que realizan otros agentes [31]. Con esta evaluación, la selección del camino más corto es el resultado del mecanismo de retroalimentación positiva que caracteriza el comportamiento de las hormigas en una colonia, que describen Deneubourg et al. [28]. Es decir, el incremento Δτijk(t) es independiente de la calidad de la solución y todas las hormigas exitosas depositan la misma cantidad de feromonas, donde:
En SACO, el proceso natural de evaporación del rastro de feromonas se realiza mediante la siguiente expresión:
donde ρ∈[0, 1] y la matriz τ contienen el valor del rastro de feromonas en cada conexión. La constante ρ determina la tasa de evaporación de las feromonas, provocando que las hormigas «olviden» sus decisiones previas. Este proceso iterativo se detiene hasta cumplir con algún criterio de paro. Para SACO, y en general para la metaheurística de ACO, se pueden aplicar criterios de paro simples. Así, el algoritmo puede terminar la búsqueda cuando, por ejemplo, se ha excedido el número máximo de iteraciones (IterMAX), o cuando se ha encontrado una solución aceptable, considerando que f(xk(t))≤¿, donde xk(t) representa una solución en el tiempo t, o alternativamente cuando todas las hormigas (o la mayor parte de ellas) siguen el mismo camino.3Descripción del algoritmo ACO-FRS para optimización en espacios continuos
En este estudio se ha propuesto un algoritmo alternativo para ACO, denominado ACO con selección de región factible (ACO-FRS), para incrementar el desempeño de esta metaheurística en la resolución de problemas de optimización con variables de decisión continuas. Específicamente, el primer paso en ACO-FRS es la generación de un archivo de regiones r, donde cada región representa un punto o solución ri (i=1,…NR). Es conveniente indicar que este concepto se utiliza en la mayoría de los algoritmos ACO para espacios continuos. Sin embargo, la manera en que se almacena la información correspondiente a los niveles de feromonas en ACO-FRS es ampliamente diferente, por ejemplo, al correspondiente para el método CACO [32]. Es decir, si hay un total de nvar variables de decisión, se deposita una cantidad de feromona en todos los componentes rij(j=1,…,nvar) de dichas regiones, mientras que en CACO esta información se almacena solo por región. Los niveles de feromonas se almacenan en la matriz τ, de dimensión NR×nvar, donde cada elemento τij indica la concentración de feromonas de la i-ésima región para la j-ésima variable de decisión. El parámetro NR es sintonizable y puede considerarse similar al número de individuos para los algoritmos basados en población donde su valor generalmente depende del número de variables de optimización (nvar) y el tipo de problema. En la figura 2 se presenta el algoritmo base de ACO-FRS que se utilizó como estructura general para el desarrollo y la evaluación de las variantes analizadas en este estudio. La inicialización de las regiones se realiza mediante una generación aleatoria de puntos en el dominio de solución, identificándose la mejor solución, que se almacena en un vector utilizado como comparación (rB). En este primer paso se deben establecer los valores de los parámetros del algoritmo, que se describen en la tabla 1.
Condiciones para la evaluación del algoritmo propuesto ACO-FRS
| Parámetro | Valor sugerido | Tipo | Descripción |
| NR | 10*nvar | Sintonizable | Número de regiones almacenadas |
| NA | NR | Fijo | Número de hormigas (o regiones recorridas) por iteración |
| τ0 | NR | Fijo | Rastro inicial de feromonas |
| NSR | 2*nvar | Sintonizable | Número de regiones factibles preseleccionadas |
| SP | 0,5 | Sintonizable | Probabilidad de búsqueda de camino |
| Δτinten | 1 | Fijo | Depósito de rastro de feromonas por componente |
| Δτevep | 1 | Fijo | Decremento en la concentración del rastro de feromonas |
En el proceso iterativo, una hormiga k solo observará un número limitado de regiones mediante el proceso de selección de regiones factibles (Nk). Aquí, Nk=rak,rβk,…,rNSRk es un conjunto aleatorio de NSR elementos de la matriz de regiones (con al menos 2 elementos diferentes: α≠β). El parámetro sintonizable NSR determina el grado de influencia que tendrá el rastro de feromonas, y su límite máximo es NR. Con esta preselección de la información disponible, el algoritmo es capaz de realizar una búsqueda global debido a que, ocasionalmente, se tendrán en cuenta regiones con baja concentración de feromonas. Uno de los componentes clave de la metaheurística ACO es la actividad de construcción del vector de solución. Como se observa en el proceso iterativo del pseudocódigo de la figura 2, en ACO-FRS el paso de construcción del vector de solución se realiza por dimensión. Cada componente dimensional de cada región rij posee una probabilidad de selección p cuando una hormiga k explora, en un momento dado, (t). Por tanto, considerando la ecuación (1), el proceso de selección está dado por la siguiente expresión:
donde las regiones factibles Nk son diferentes para cada hormiga k.
Una vez realizadas todas las selecciones, estas forman parte del subconjunto Mk∈Nk, que contiene los elementos rsjj,k con j=1,…,nvar. Cada hormiga definirá su componente dimensional xj, igual al valor del componente seleccionado, o realizará una búsqueda de camino con una probabilidad dada SP, donde SP∈ [0,1]. La desviación de la región seleccionada puede interpretarse como un mecanismo de exploración, y en la tabla 2 se presentan los operadores sugeridos. Especialmente, se utilizan algunas regiones almacenadas en el archivo r para definir la magnitud de la desviación, y esta acción es el principal mecanismo con el que ACO-FRS realiza la exploración de espacios continuos. Por ejemplo, el operador «A» para la búsqueda de camino está dado por:
donde la magnitud de la desviación del elemento rsj,k está limitada por la diferencia entre dicho elemento y el elemento aleatorio α que pertenece al conjunto de regiones factibles. Como se puede observar, la desviación puede tomar diferentes direcciones, ya que el número aleatorio generado para la ponderación tiene límites ∈ (−1, 1).
Variantes ACO-FRS analizadas
| Código | Operador de búsqueda de camino | Intensificación−τ | ||
| ACO-FRS (1) | A. | rsjj,k+U[−1,1]∗abs(rsjj,k−rαj,k) | A. | τsjj,k←τsjj,k+1 |
| ACO-FRS (2) | B. | rsjj,k+U[0,1]∗(rαj,k−rβj,k) | A. | τsjj,k←τsjj,k+1 |
| ACO-FRS (3) | A. | rsjj,k+U[−1,1]∗abs(rsjj,k−rαj,k) | B. | τsjj,k←τsjj,k+1τscoj,k←sjj,k |
| ACO-FRS (4) | B. | rsjj,k+U[0,1]∗(rαj,k−rβj,k) | B. | τsjj,k←τsjj,k+1τscoj,k←sjj,k |
Cuando una hormiga ha definido los valores de todas las dimensiones, se dice que la hormiga ha construido una solución, es decir, ha creado una nueva región o punto de prueba xk. Para dicho punto, se examina el valor de la función objetivo y este remplazará una región existente CO solo si f (xk) es menor que f(rsco); es decir, para cada dimensión j se tiene que:
Es conveniente indicar que CO es una región de comparación y puede ser cualquiera de las regiones correspondientes a los componentes seleccionados mediante el rastro de feromona (Mk=rS11,k,rS22,k,…,rnvarnvark). Si la región generada mejora el valor de la función objetivo de la mejor región rB en la iteración t, dicha región será actualizada mediante:
La intensificación del rastro de feromonas se realiza con la siguiente ecuación:
donde Δτint es un valor constante, como se puede ver en la tabla 1. Las estrategias de intensificación sugeridas para las variantes del algoritmo ACO-FRS se muestran en la tabla 2. La ecuación (10) es una adaptación de la ecuación (2) y permite que el algoritmo realice una evaluación implícita en los depósitos de feromonas. Se puede observar que, después del proceso de inicialización, se realiza una iteración t hasta que todas las hormigas k=1,…,NA han explorado una región. Entonces, el número de hormigas es el número de ocasiones en que se evalúa una nueva región por iteración. Finalmente, cuando todas las hormigas de la colonia han explorado el espacio de búsqueda se lleva a cabo la evaporación de feromonas de la siguiente manera:donde Δτevap es un valor constante. El mecanismo de evaporación anterior permite una reducción homogénea de la intensidad del rastro de feromonas para todas las regiones y concuerda con el proceso de intensificación implícito presentado en la ecuación (10). En la implementación del algoritmo mostrado en la figura 2 se incluyeron 3 posibles criterios de paro para finalizar el proceso de optimización. El primer criterio corresponde al máximo número de iteraciones (IterMAX), un segundo criterio corresponde al máximo número de funciones que evaluar (NFEMAX), mientras que el último criterio finaliza la búsqueda cuando se ha realizado un determinado número de iteraciones sin mejora en la mejor solución encontrada (SCMAX). En este último criterio de paro se contabilizan las iteraciones donde no ha cambiado el mejor valor de la función objetivo encontrado por el algoritmo, es decir, si f(rB(t))=f(rB(t−1)) para el caso de un problema de minimización.
A diferencia del método CACO [32], en el algoritmo propuesto ACO-FRS cada hormiga puede realizar una búsqueda eficiente sin ser catalogada como «local» o «global». Concretamente, en ACO-FRS se omiten las edades de las regiones, que se utilizan en CACO para redirigir la búsqueda. Ninguna de las 2 situaciones se observa en los algoritmos de ACO discretos, y esta característica garantiza una mayor similitud del mecanismo de ACO-FRS con la metaheurística básica de ACO. Por otra parte, la estrategia con la que se aborda la exploración en problemas con espacios continuos (es decir, operador de búsqueda de camino) difiere de las implementaciones con funciones de densidad de probabilidad de los métodos CACS, ACOR y MACACO. Finalmente, el proceso de búsqueda de ACO-FRS difiere de los algoritmos basados en población, ya que es posible que un miembro de la población (un vector de la matriz r) no cambie, no se utilice o no se compare al terminar una iteración.
4Resultados y discusión4.1Comparación de las variantes propuestas para ACO-FRSEn primera instancia, se desarrollaron e implementaron 4 variantes del método propuesto ACO-FRS para evaluar 2 operadores de búsqueda de camino para la generación de una nueva región y 2 estrategias de actualización de feromonas para las regiones exitosas. Dichas variantes se describen en la tabla 2. Para la estrategia A de generación o desviación de la región seleccionada rSjj,k se elige un componente dimensional de una región aleatoria B para definir la distancia que se moverá la hormiga, mientras que en la estrategia B se intercambia información mediante la selección de 2 regiones diferentes (rα y rβ) del conjunto Nk. El operador de búsqueda de camino puede generar valores fuera de los límites de la variable de optimización (xminj y xmaxj); por tanto, se deben verificar dichos valores, tal como se muestra en la figura 2. Por otro lado, el rastro de feromonas se actualiza con aumentos unitarios en las estrategias de intensificación de τ, situación que concuerda con el proceso de evaporación propuesto. En la estrategia A de actualización del rastro de feromonas solo se intensifican los valores de las feromonas de las regiones seleccionadas τsjj, mientras que en la estrategia B se actualiza el rastro de la región de comparación τscoj. Para realizar la evaluación de los algoritmos propuestos se ha considerado un valor τo=NR y, con objeto de evitar valores indefinidos de probabilidad de selección (cuando τij=0), se realiza un ajuste de valores posterior a la evaporación que restringe la intensidad del rastro a valores positivos iguales o mayores que 1. Finalmente, a pesar de que NA es independiente de NR, el uso de valores distintos para estos 2 parámetros modifica el proceso de intensificación del rastro de feromonas y, como consecuencia, se ha considerado NA=NR. En general, las condiciones de evaluación de las 4 variantes de ACO-FRS analizadas en este estudio se presentan en la tabla 1 y los 4 códigos mostrados en la tabla 2 se implementaron en Matlab®.
La tabla 3 proporciona los detalles de las funciones seleccionadas para evaluar el desempeño del método de optimización propuesto. La primer columna de dicha tabla, con el encabezado ID, proporciona las etiquetas para identificar las diferentes funciones evaluadas. Es conveniente indicar que estos problemas se han utilizado para evaluar el desempeño numérico de diferentes métodos estocásticos de optimización, puesto que contienen algunas características y dificultades asociadas a diferentes problemas de optimización en ingeniería y diseño. Dichas funciones corresponden a problemas continuos de optimización global sin restricciones cuyas dimensiones varían entre 2 y 20 y que presentan diferente número de óptimos locales. Los problemas seleccionados se utilizaron como punto de partida para comparar las diferentes variantes propuestas para el código base de ACO-FRS, además de entender el comportamiento general del algoritmo y analizar su desempeño en el proceso de resolución de estas funciones objetivo clásicas del área. Por tanto, los resultados de las pruebas con estos problemas son útiles para identificar las debilidades y fortalezas del código propuesto y permiten comparar los resultados obtenidos con estudios previos.
Problemas de optimización clásicos utilizados para la evaluación de las estrategias propuestas para ACO-FRS
| ID | Nombre de la función, Fobj | Variables de decisión, nvar | Mínimo global y vector de posición |
| B1-B4 | Zakharov | nvar=2,5,10 y 20 | 0 |
| Fobj=∑i=1nvarui2+∑i=1nvar0.5iui2+∑i=1nvar0.5iui4 | −5≤ui≤10 | u=(0,…,0) | |
| B5-B8 | Rosenbrock | nvar=2,5,10 y 20 | 0 |
| Fobj=∑i=1nvar100(ui2−ui+1)2+(ui−1)2 | −5≤ui≤10 | u=(1,…,1) | |
| B9 | Goldstein y Price | nvar=2 | 3 |
| Fobj=[1+(u1+u2+1)2(19−14u1+3u12−14u2+6u1u2+3u22)]∗[30+(2u1−3u22)2(18−32u1+12u12+48u2−36u1u2+27u22)] | −2≤ui≤2 | u=(0,-1) | |
| B10 | Modificada de Himmelblau | nvar=0 | 0 |
| Fobj=(u12+u2−11)2+(u1+u22−7)2+0.1((u1−3)2+(u2−2)2) | −6≤ui≤6 | u=(3,2) | |
| B11 | Rastrigin | nvar=20 | 0 |
| Fobj=10D+∑i=1nvar(ui2−10cos(2πui)) | −600≤ui≤600 | u=(0,…,0) | |
| B12 | Griewank | nvar=20 | 0 |
| Fobj=∑i=1nvarui2/d−∏i=1nvarcos(ui/i) | −600≤ui≤600(d=D) | u=(0,…,0) | |
| B13-B14 | Hartman | nvar=3 y 6 | Para ηvar=3, -3.862782 |
| Fobj=∑i=14ciexp−∑j=1nvaraji(uj−pij)2 | 0≤ui≤1 | u=(0.114614,0.555649,0.852547)Para ηvar=6, -3.322368u=(0.201690,0.150011,0.476874,0.275332,0.311652,0.657301) | |
| B15-B17 | Shekel | nvar=4 | Para m=5, -10.15 |
| Fobj=−∑i=1m1∑j=1nvar(uj−aij)2−ci | 0≤ui≤10(m=5, 7y10) | u=(4,4,4,4)Para m=7, -10.40u=(4,4,4,4)Para m=10, -10.53u=(4,4,4,4) | |
Se evaluó el desempeño numérico de las variantes propuestas para ACO-FRS considerando la confiabilidad del método para localizar el óptimo global, la cual se mide en términos del número de ocasiones en que el algoritmo localizó el óptimo global para 100 pruebas numéricas con estimaciones iniciales aleatorias. Esta métrica se conoce como tasa de éxito (SR). Adicionalmente, se evaluó la eficiencia computacional del método estocástico en términos del número de funciones evaluadas (NFE). El promedio de funciones evaluadas se analizó usando solamente las pruebas exitosas. Es decir, una prueba se consideró exitosa si se obtenía el óptimo global con un error absoluto de 10×10–5 o menor con respecto al valor de la función objetivo. Los resultados obtenidos para el conjunto de funciones reportado en la tabla 3 empleando las diferentes estrategias para ACO-FRS se presentan en la figura 3. Para el análisis de esta información, se presenta la tasa de éxito global (GSR) de cada estrategia probada. La tasa de éxito global está definida por la siguiente expresión:
donde SRi es la tasa de éxito del problema i y nb es el total de problemas utilizados para la evaluación del desempeño numérico del método estocástico, respectivamente. Hay que señalar que los resultados del método de optimización de la figura 3 se reportan utilizando IterMAX como único criterio de paro. En dicha figura se puede apreciar que los algoritmos ACO-FRS (1) y (3) presentan mayores tasas de éxito para bajas iteraciones (IterMAX<250) en comparación con los algoritmos restantes. Sin embargo, para un número mayor de iteraciones (IterMAX>1.500) los algoritmos ACO-FRS (2) y (4) presentan un mejor desempeño. Estos resultados indican que la tasa de éxito global y el desempeño numérico de las variantes propuestas para ACO-FRS son dependientes del esfuerzo cómputo, como se muestra en la figura 3. En particular, ningún algoritmo superó el 50% de GSR empleando IterMAX<250 y ACO-FRS (4) presenta la mejor GSR=71% para IterMAX>1.500. Estos resultados son consistentes con otros estudios reportados en la literatura en que se ha evaluado el desempeño numérico de diferentes métodos estocásticos y se ha determinado la dependencia entre el esfuerzo numérico y la eficacia del algoritmo para localizar el óptimo global [33,34]. En general, las estrategias de intensificación y diversificación de los métodos estocásticos dependen del esfuerzo numérico del algoritmo y de las características de los problemas de optimización; como consecuencia, las tasas de convergencia de los métodos estocásticos varían en función del número de funciones evaluadas. Con fines ilustrativos, en la tabla 4 se presentan las tasas de convergencia de los algoritmos ACO-FRS (3) y ACO-FRS (4) para todos los problemas de optimización considerados en este estudio. Como se puede observar en esta tabla, ambos métodos de optimización presentan una baja tasa de convergencia para localizar el óptimo global de la función de Rosenbrock. De acuerdo con la literatura [35], la localización del óptimo global de esta función es difícil y normalmente los métodos de optimización estocásticos presentan problemas de convergencia, especialmente cuando el número de variables de optimización es mayor a 5, debido a que el número de óptimos locales de la función objetivo se incrementa con respecto a la dimensión del problema. Al igual que otros métodos de optimización estocásticos, el método ACO-FRS es inefectivo para escapar de los óptimos locales de esta función objetivo y, por tanto, las tasas de convergencia al óptimo global son bajas.
Comportamiento numérico de los métodos ACO-FRS (3) y ACO-FRS (4) en la minimización global de problemas multivariables con espacios continuos
| Problema | Algoritmo | IterMAX | ||||||
| ID | 50 | 100 | 250 | 500 | 750 | 1.000 | 1.500 | |
| B1 | ACO-FRS (4) | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| ACO-FRS (3) | 0 | 0 | 0 | 0 | 0 | 0 | 17 | |
| B2 | ACO-FRS (4) | 0 | 0 | 0 | 96 | 100 | 100 | 100 |
| ACO-FRS (3) | 0 | 0 | 0 | 100 | 100 | 100 | 100 | |
| B3 | ACO-FRS (4) | 0 | 3 | 100 | 100 | 100 | 100 | 100 |
| ACO-FRS (3) | 0 | 25 | 100 | 100 | 100 | 100 | 100 | |
| B4 | ACO-FRS (4) | 98 | 100 | 100 | 100 | 100 | 100 | 100 |
| ACO-FRS (3) | 99 | 100 | 100 | 100 | 100 | 100 | 100 | |
| B5 | ACO-FRS (4) | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| ACO-FRS (3) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| B6 | ACO-FRS (4) | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| ACO-FRS (3) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| B7 | ACO-FRS (4) | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| ACO-FRS (3) | 0 | 0 | 0 | 1 | 0 | 0 | 1 | |
| B8 | ACO-FRS (4) | 0 | 0 | 1 | 3 | 19 | 33 | 78 |
| ACO-FRS (3) | 0 | 0 | 1 | 4 | 16 | 35 | 54 | |
| B9 | ACO-FRS (4) | 10 | 84 | 100 | 100 | 100 | 99 | 99 |
| ACO-FRS (3) | 13 | 84 | 97 | 97 | 99 | 99 | 100 | |
| B10 | ACO-FRS (4) | 13 | 62 | 92 | 99 | 99 | 100 | 97 |
| ACO-FRS (3) | 29 | 68 | 86 | 93 | 96 | 97 | 94 | |
| B11 | ACO-FRS (4) | 0 | 0 | 0 | 0 | 0 | 0 | 47 |
| ACO-FRS (3) | 0 | 0 | 0 | 1 | 27 | 35 | 33 | |
| B12 | ACO-FRS (4) | 0 | 0 | 0 | 100 | 100 | 100 | 100 |
| ACO-FRS (3) | 0 | 0 | 100 | 100 | 100 | 100 | 100 | |
| B13 | ACO-FRS (4) | 100 | 100 | 100 | 100 | 100 | 100 | 100 |
| ACO-FRS (3) | 100 | 100 | 100 | 100 | 99 | 99 | 100 | |
| B14 | ACO-FRS (4) | 3 | 91 | 89 | 84 | 86 | 93 | 93 |
| ACO-FRS (3) | 44 | 86 | 92 | 88 | 90 | 94 | 87 | |
| B15 | ACO-FRS (4) | 0 | 22 | 28 | 44 | 48 | 42 | 48 |
| ACO-FRS (3) | 1 | 32 | 44 | 39 | 39 | 34 | 47 | |
| B16 | ACO-FRS (4) | 0 | 45 | 55 | 72 | 61 | 64 | 71 |
| ACO-FRS (3) | 1 | 61 | 51 | 60 | 53 | 57 | 62 | |
| B17 | ACO-FRS (4) | 0 | 54 | 67 | 72 | 72 | 84 | 75 |
| ACO-FRS (3) | 3 | 63 | 71 | 67 | 75 | 70 | 73 | |
En la tabla 5 se muestran los promedios de funciones evaluadas para las 100 pruebas numéricas realizadas en cada función objetivo empleando SCMAX como criterio de paro y fijando IterMAX (sin incluir NFEMAX como criterio de paro). Al examinar los resultados para los problemas individuales, se puede apreciar que los algoritmos ACO-FRS (1) y (3) son capaces de encontrar el óptimo global en el problema de Zakharov (D=20), a diferencia de los restantes algoritmos. En el problema de Rosenbrock (D=20), solamente ACO-FRS (4) localizó el óptimo global bajo la tolerancia establecida. Es importante mencionar que la tolerancia establecida supone un esfuerzo numérico significativo para la resolución de los problemas B5 a B8. Para la función objetivo de Zakharov (D=10), prácticamente todos los algoritmos finalizaron su proceso iterativo tras haber acumulado el máximo número de iteraciones establecido sin cumplir con el criterio SCMAX; una situación similar se presentó en la función de Rastrigin, pero solo para los algoritmos ACO-FRS (2) y (4). Por otra parte, los resultados obtenidos muestran que los algoritmos ACO-FRS (2) y (4) presentan un mayor NFE cuando se utiliza el criterio de convergencia SCMAX. Ambos algoritmos poseen el mismo mecanismo de aproximación a la región seleccionada (estrategia de generación B) y solo difieren en la estrategia de actualización de feromonas. La estrategia de generación B utiliza mayor información del archivo o matriz de regiones r (al incluir la región rβ≠rα), factor que puede explicar el mejor desempeño de los algoritmos que la poseen.
Eficiencia de las variantes de ACO-FRS en los problemas de optimización global sin restricción empleando SCMAX como criterio de paro
| Problema | NFE para | |||||
| ID | Nombre de la función | ACO-FRS (1) | ACO-FRS (2) | ACO-FRS (3) | ACO-FRS (4) | |
| B1 | Zakharov (nvar=20) | SCMAX=6nvar | 300.200 | – | 300.200 | – |
| SCMAX=12nvar | 300.200 | – | 300.200 | – | ||
| B2 | Zakharov (nvar=10) | SCMAX=6nvar | 150.100 | 150.100 | 149.690 | 150.100 |
| SCMAX=12nvar | 150.100 | 150.100 | 150.100 | 150.100 | ||
| B3 | Zakharov (nvar=5) | SCMAX=6nvar | 67.197 | 73.058 | 70.052 | 72.725 |
| SCMAX=12nvar | 74.709 | 75.050 | 74.786 | 75.050 | ||
| B4 | Zakharov (nvar=2) | SCMAX=6nvar | 4.501 | 4.286 | 4.156 | 3.727 |
| SCMAX=12nvar | 26.967 | 27.012 | 26.060 | 27.231 | ||
| B5 | Rosenbrock (nvar=20) | SCMAX=6nvar | – | – | – | – |
| SCMAX=12nvar | – | – | – | – | ||
| B6 | Rosenbrock (nvar=10) | SCMAX=6nvar | – | – | – | – |
| SCMAX=12nvar | – | – | – | – | ||
| B7 | Rosenbrock (nvar=5) | SCMAX=6nvar | – | – | – | – |
| SCMAX=12nvar | – | – | – | – | ||
| B8 | Rosenbrock (nvar=2) | SCMAX=6nvar | – | – | – | – |
| SCMAX=12nvar | – | – | – | 1.060 | ||
| B9 | Goldstein and Price | SCMAX=6nvar | 2.523 | 2.602 | 2.503 | 2.638 |
| SCMAX=12nvar | 3.566 | 3.836 | 3.438 | 3.764 | ||
| B10 | Modificada de Himmelblau | SCMAX=6nvar | 3.170 | 2.651 | 2.863 | 2.527 |
| SCMAX=12nvar | 5.141 | 5.425 | 5.106 | 4.952 | ||
| B11 | Rastrigin | SCMAX=6nvar | 230.897 | 300.200 | 223.556 | 300.200 |
| SCMAX=12nvar | 252.656 | 300.200 | 249.275 | 300.200 | ||
| B12 | Griewank | SCMAX=6nvar | 130.086 | 239.800 | 127.216 | 226.722 |
| SCMAX=12nvar | 155.256 | 262.452 | 151.382 | 250.562 | ||
| B13 | Hartman (nvar=3) | SCMAX=6nvar | 3.653 | 4.002 | 3.573 | 3.845 |
| SCMAX=12nvar | 4.505 | 4.751 | 4.332 | 4.497 | ||
| B14 | Hartman (nvar=6) | SCMAX=6nvar | 12.959 | 15.232 | 12.581 | 14.909 |
| SCMAX=12nvar | 15.690 | 18.323 | 15.671 | 17.895 | ||
| B15 | Shekel (M=5) | SCMAX=6D | 7.957 | 9.055 | 7.669 | 8.996 |
| SCMAX=12D | 9.361 | 10.202 | 9.011 | 9.741 | ||
| B16 | Shekel (M=7) | SCMAX=6D | 8.036 | 9.188 | 7.636 | 8.984 |
| SCMAX=12D | 9.065 | 10.682 | 9.174 | 10.666 | ||
| B17 | Shekel (M=10) | SCMAX=6D | 8.118 | 9.115 | 7.742 | 8.870 |
| SCMAX=12D | 9.123 | 11.006 | 8.964 | 10.528 | ||
El símbolo «–» indica que NFE no es reportado dado que el método estocástico presenta 0% de SR
Con fines ilustrativos, en la figura 4 se presentan los historiales de convergencia de las estrategias ACO-FRS (2) y (4) en el proceso de minimización del problema B11. En este problema se minimiza la función de Rastrigin para 20 variables, cuyo mínimo global es cero, y esta gráfica solamente presenta el mejor valor para la función objetivo encontrado en cada iteración (fcalc). Se observa que para la mayor parte del proceso de minimización, ACO-FRS (4) genera mejores fcalc. Además, se puede apreciar que ACO-FRS (2) requiere más iteraciones para mejorar significativamente fcalc, lo que se puede verificar en la forma del perfil de convergencia del método. En el valor máximo de iteraciones permitidas, ACO-FRS (4) generó una solución con mejor precisión.
En síntesis, los resultados de las 4 variantes de ACO-FRS para la resolución de los problemas de optimización global seleccionados indican que la estrategia de generación B utilizada en los algoritmos ACO-FRS (2) y (4) proporciona un mejor desempeño, especialmente cuando se utiliza un esfuerzo numérico IterMAX>500. Una vez realizadas pruebas en problemas particulares (p.ej., los resultados de la figura 4 para la función de Rastrigin) se ha identificado la estrategia ACO-FRS (4) como el algoritmo propuesto y sugerido para la resolución de los problemas de optimización multivariables y con varios óptimos locales en espacios continuos. Con este algoritmo se pueden obtener tasas de convergencia superiores al 70% si se utiliza un esfuerzo numérico apropiado.
Con fines ilustrativos, se comparó el desempeño numérico del algoritmo ACO-FRS (4) con los resultados obtenidos para otros algoritmos del tipo ACO para espacios continuos. Los métodos utilizados para la comparación fueron CACS [24], ACOR[25] y MACACO [26]. En particular, se evaluó el desempeño numérico de este conjunto de métodos estocásticos en la resolución de 6 problemas con 30 variables de optimización, que se describen en la tabla 6. En esta comparación se utilizó NFEMAX como criterio de paro y se empleó un valor de 1×106 para cada problema y algoritmo de optimización, con excepción de la función de Rosenbrock, donde el número máximo de funciones evaluadas fue 6×106. Los resultados numéricos de CACS, ACOR y MACACO se obtuvieron de la literatura [26], donde dichos algoritmos se implementaron con las condiciones ya mencionadas. Es importante indicar que los parámetros de ACO-FRS (4) utilizados en esta evaluación corresponden a los valores reportados en la tabla 1. En la tabla 7 se presentan los valores de la media y la desviación estándar de las funciones objetivo utilizadas en el comparativo de los métodos del tipo ACO. Los resultados obtenidos indican que ACO-FRS (4) ofrece el mejor desempeño numérico y es más robusto en la mayoría de los problemas seleccionados. Los valores de las desviaciones estándar para el conjunto de problemas de optimización que se obtuvieron con ACO-FRS (4) son significativamente inferiores a los valores reportados para los otros métodos estocásticos (tabla 7). Solamente MACACO muestra una superioridad numérica a ACO-FRS (4) en el problema de Rastrigin (nvar=30). En general, los desempeños numéricos de ACO-FRS (4) y MACACO son superiores a los desempeños de los métodos ACOR y CACS en la resolución de estos problemas de optimización multivariables.
Problemas de optimización multivariables utilizados para la comparación de ACO-FRS con otros métodos del tipo ACO para espacios continuos
| ID | Nombre de la función, Fobj | Variables de decisión, nvar y rango | Mínimo global y vector de posición |
| B18 | Sphere | nvar=30 | 0 |
| Fobj=∑i=1nvarui2 | −100≤ui≤100 | u=(0,…,0) | |
| B19 | Rosenbrock | nvar=30 | 0 |
| Fobj=∑i=1nvar−1100ui+1−ui22+ui−12 | −30≤ui≤30 | u=(1,…,1) | |
| B20 | Rastrigin | nvar=30 | 0 |
| Fobj=10nvar+∑i=1nvarui2−10cos2πui | −5.12≤ui≤5.12 | u=(0,…,0) | |
| B21 | Griewank | nvar=30 | 0 |
| Fobj=1+0.00025∑i=1nvarui−∏i=1nvarcosuii | −500≤ui≤500 | u=(0,…,0) | |
| B22 | Schwefel | nvar=30 | −12569.4866 |
| Fobj=−∑i=1nvaruisinui | −500≤ui≤500 | u=(420.968,..., 420.968) | |
| B23 | Salomon | nvar=30 | 0 |
| Fobj=1−cos2π∑i=1nvarui2+0.1∑i=1nvarui2 | −100≤ui≤100 | u=(0,…,0) |
Media y desviación estándar de la mejor solución obtenida por ACOR,, CACS, MACACO y ACO-FRS en problemas de optimización multivariables
| ID | Nombre de la función | ACOR | CACS | MACACO | ACOFRS |
| Valor promedio y desviación estándar de la función objetivoa | |||||
| B18 | Sphere | 0±0,00 | 0±0,00 | 0±0,00 | 0±0,00 |
| B19 | Rosenbrock | 29,93±35,14 | 1,23±1,91 | 7,48±11,68 | 0,01434±0,00061 |
| B20 | Rastrigin | 101,65±21,01 | 57,17±14,14 | 0,00058±0,00009 | 27,25±3,63 |
| B21 | Griewank | 0,09±0,18 | 0,02±0,02 | 0±0,00 | 0±0,00 |
| B22 | Schwefel | −8.703,26±721,53 | −8.934,57±633,78 | −12.569,49±0,01 | −12.569,49±0,00 |
| B23 | Salomon | 3,05±1,43 | 0,33±0,05 | 0,15±0,05 | 0,12±0,03 |
En negrita se indica el método con mejor desempeño.
Los métodos estocásticos basados en la metaheurística de colonia de hormigas son capaces de abordar problemas en espacios continuos sin requerir modificaciones mayores en su estructura básica. Para el caso del algoritmo ACO-FRS propuesto en este trabajo, la inclusión de una selección de regiones factibles permite realizar una búsqueda global mediante la eventual exploración de regiones con bajos niveles de feromonas, aumentando así la confiabilidad del método para la localización de la solución del problema de optimización. De las 4 versiones de ACO-FRS evaluadas en los problemas clásicos de optimización global, los resultados obtenidos indicaron que se consiguieron mejores desempeños mediante la aplicación del operador de búsqueda de camino en el que se combina la información de 2 regiones diferentes para definir la magnitud de desviación de la región seleccionada, en combinación con la estrategia de intensificación de feromonas que aumenta la probabilidad de selección de la región de comparación. Al realizar la comparación de la estrategia de optimización desarrollada con otros algoritmos del tipo ACO se observa un desempeño destacable y se demuestra la capacidad de ACO-FRS en la resolución de problemas multimodales con un número significativo de variables de decisión. Es conveniente indicar que en futuras implementaciones de ACO-FRS se puede considerar una evaluación explícita para el incremento en el nivel de feromonas para mejorar el desempeño numérico del algoritmo. Además, la estrategia de optimización desarrollada se puede adaptar fácilmente para la resolución de problemas con variables mixtas (enteras y continuas) con el objeto de convertirlo en un algoritmo de uso general. Los autores del presente trabajo analizarán estos temas en posteriores estudios.
Los autores agradecen las facilidades y el financiamiento otorgado por el Instituto Tecnológico de Aguascalientes y la Universidad de Guanajuato para la realización del presente estudio.