En la investigación de operaciones y ciencias de la computación , el algoritmo de optimización de colonias de hormigas ( ACO ) es una técnica probabilística para resolver problemas computacionales que puede reducirse a encontrar buenos caminos a través de gráficos . Las hormigas artificiales representan métodos de agentes múltiples inspirados en el comportamiento de hormigas reales. La comunicación basada en feromonas de las hormigas biológicas es a menudo el paradigma predominante utilizado. [2] Las combinaciones de hormigas artificiales y algoritmos de búsqueda local se han convertido en un método de elección para numerosas tareas de optimización que involucran algún tipo de gráfico., por ejemplo, rutas de vehículos y rutas de Internet .
Como ejemplo, la optimización de colonias de hormigas [3] es una clase de algoritmos de optimización modelados en las acciones de una colonia de hormigas . Las 'hormigas' artificiales (por ejemplo, agentes de simulación) localizan soluciones óptimas moviéndose a través de un espacio de parámetros que representa todas las soluciones posibles. Las hormigas reales depositan feromonas que se dirigen unas a otras hacia los recursos mientras exploran su entorno. Las 'hormigas' simuladas registran de manera similar sus posiciones y la calidad de sus soluciones, de modo que en posteriores iteraciones de simulación, más hormigas localizan mejores soluciones. [4] Una variación de este enfoque es el algoritmo de las abejas , que es más análogo a los patrones de alimentación de la abeja melífera , otro insecto social.
Este algoritmo es miembro de la familia de algoritmos de colonias de hormigas, en métodos de inteligencia de enjambre , y constituye algunas optimizaciones metaheurísticas . Propuesto inicialmente por Marco Dorigo en 1992 en su tesis doctoral, [5] [6] el primer algoritmo tenía como objetivo buscar un camino óptimo en un gráfico, basado en el comportamiento de las hormigas que buscaban un camino entre su colonia y una fuente de alimento. . Desde entonces, la idea original se ha diversificado para resolver una clase más amplia de problemas numéricos y, como resultado, han surgido varios problemas que se basan en diversos aspectos del comportamiento de las hormigas. Desde una perspectiva más amplia, ACO realiza una búsqueda basada en modelos [7] y comparte algunas similitudes con la estimación de algoritmos de distribución .
Descripción general
En el mundo natural, las hormigas de algunas especies (inicialmente) deambulan al azar y, al encontrar comida, regresan a su colonia mientras establecen senderos de feromonas . Si otras hormigas encuentran un camino así, es probable que no sigan viajando al azar, sino que sigan el camino, regresen y lo refuercen si finalmente encuentran comida (ver Comunicación de hormigas ). [8]
Sin embargo, con el tiempo, el rastro de feromonas comienza a evaporarse, reduciendo así su fuerza atractiva. Cuanto más tiempo le toma a una hormiga viajar por el camino y regresar, más tiempo tienen las feromonas para evaporarse. En comparación, un camino corto se recorre con más frecuencia y, por lo tanto, la densidad de feromonas se vuelve mayor en los caminos más cortos que en los más largos. La evaporación de feromonas también tiene la ventaja de evitar la convergencia a una solución localmente óptima. Si no hubiera evaporación en absoluto, los caminos elegidos por las primeras hormigas tenderían a resultar excesivamente atractivos para las siguientes. En ese caso, la exploración del espacio de la solución estaría restringida. La influencia de la evaporación de feromonas en los sistemas de hormigas reales no está clara, pero es muy importante en los sistemas artificiales. [9]
El resultado general es que cuando una hormiga encuentra un camino bueno (es decir, corto) desde la colonia a una fuente de alimento, es más probable que otras hormigas sigan ese camino, y la retroalimentación positiva eventualmente lleva a que muchas hormigas sigan un solo camino. La idea del algoritmo de la colonia de hormigas es imitar este comportamiento con "hormigas simuladas" caminando alrededor del gráfico que representa el problema a resolver.
Redes ambientales de objetos inteligentes
Se requieren nuevos conceptos ya que la "inteligencia" ya no está centralizada, sino que se puede encontrar en todos los objetos minúsculos. Se sabe que los conceptos antropocéntricos conducen a la producción de sistemas de TI en los que el procesamiento de datos, las unidades de control y las fuerzas de cálculo están centralizados. Estas unidades centralizadas han aumentado continuamente su rendimiento y pueden compararse con el cerebro humano. El modelo del cerebro se ha convertido en la última visión de las computadoras. Las redes ambientales de objetos inteligentes y, tarde o temprano, una nueva generación de sistemas de información aún más difundidos y basados en la nanotecnología, cambiarán profundamente este concepto. Los pequeños dispositivos que pueden compararse con los insectos no disponen de una gran inteligencia por sí solos. De hecho, su inteligencia puede clasificarse como bastante limitada. Por ejemplo, es imposible integrar una calculadora de alto rendimiento con el poder de resolver cualquier tipo de problema matemático en un biochip que se implanta en el cuerpo humano o se integra en una etiqueta inteligente diseñada para rastrear artículos comerciales. Sin embargo, una vez que esos objetos están interconectados, disponen de una forma de inteligencia que se puede comparar con una colonia de hormigas o abejas. En el caso de ciertos problemas, este tipo de inteligencia puede ser superior al razonamiento de un sistema centralizado similar al cerebro. [10]
La naturaleza ofrece varios ejemplos de cómo los organismos minúsculos, si todos siguen la misma regla básica, pueden crear una forma de inteligencia colectiva a nivel macroscópico. Las colonias de insectos sociales ilustran perfectamente este modelo que difiere mucho de las sociedades humanas. Este modelo se basa en la cooperación de unidades independientes con un comportamiento simple e impredecible. [11] Se mueven por el área circundante para realizar ciertas tareas y solo poseen una cantidad muy limitada de información para hacerlo. Una colonia de hormigas, por ejemplo, representa numerosas cualidades que también se pueden aplicar a una red de objetos ambientales. Las colonias de hormigas tienen una capacidad muy alta para adaptarse a los cambios en el entorno, así como una fuerza enorme para lidiar con situaciones en las que un individuo no puede llevar a cabo una tarea determinada. Este tipo de flexibilidad también sería muy útil para redes móviles de objetos que se están desarrollando constantemente. Los paquetes de información que se mueven de una computadora a un objeto digital se comportan de la misma manera que lo harían las hormigas. Se mueven por la red y pasan de un nudo a otro con el objetivo de llegar lo más rápido posible a su destino final. [12]
Sistema de feromonas artificiales
La comunicación basada en feromonas es una de las formas de comunicación más efectivas que se observa ampliamente en la naturaleza. La feromona es utilizada por insectos sociales como abejas, hormigas y termitas; tanto para comunicaciones entre agentes como entre agentes y enjambres. Debido a su viabilidad, las feromonas artificiales se han adoptado en sistemas robóticos de múltiples robots y enjambres. La comunicación basada en feromonas se implementó por diferentes medios, como químicos [13] [14] [15] o físicos (etiquetas RFID, [16] luz, [17] [18] [19] [20] sonido [21] ) formas . Sin embargo, esas implementaciones no pudieron replicar todos los aspectos de las feromonas como se ve en la naturaleza.
El uso de luz proyectada fue presentado en un artículo de IEEE de 2007 por Garnier, Simon, et al. como una configuración experimental para estudiar la comunicación basada en feromonas con micro robots autónomos. [22] Otro estudio presentó un sistema en el que las feromonas se implementaron a través de una pantalla LCD horizontal en la que se movían los robots, y los robots tenían sensores de luz orientados hacia abajo para registrar los patrones debajo de ellos. [23] [24]
Algoritmo y fórmulas
En los algoritmos de optimización de colonias de hormigas, una hormiga artificial es un agente computacional simple que busca buenas soluciones a un problema de optimización dado. Para aplicar un algoritmo de colonia de hormigas, el problema de optimización debe convertirse en el problema de encontrar el camino más corto en un gráfico ponderado. En el primer paso de cada iteración, cada hormiga construye estocásticamente una solución, es decir, el orden en el que se deben seguir los bordes del gráfico. En el segundo paso, se comparan los caminos encontrados por las diferentes hormigas. El último paso consiste en actualizar los niveles de feromonas en cada borde.
el procedimiento ACO_MetaHeuristic es mientras no se termina hacer generateSolutions () daemonActions () pheromoneUpdate () repetir el procedimiento de finalización
Selección de borde
Cada hormiga necesita construir una solución para moverse por la gráfica. Para seleccionar el siguiente borde en su recorrido, una hormiga considerará la longitud de cada borde disponible desde su posición actual, así como el nivel de feromonas correspondiente. En cada paso del algoritmo, cada hormiga se mueve desde un estado a estado , correspondiente a una solución intermedia más completa. Así, cada hormiga calcula un conjunto de expansiones factibles a su estado actual en cada iteración, y se mueve a una de estas en probabilidad. Para hormiga, la probabilidad de mudarse de estado a estado depende de la combinación de dos valores, el atractivo del movimiento, calculado por alguna heurística que indica la conveniencia a priori de ese movimiento y el nivel del camino del movimiento, lo que indica qué tan competente ha sido en el pasado para realizar ese movimiento en particular. El nivel del sendero representa una indicación a posteriori de la conveniencia de ese movimiento.
En general, el la hormiga se mueve del estado a estado con probabilidad
dónde
es la cantidad de feromona depositada para la transición del estado a , 0 ≤ es un parámetro para controlar la influencia de , es la conveniencia de la transición de estado ( conocimiento a priori , típicamente, dónde es la distancia) y ≥ 1 es un parámetro para controlar la influencia de . y representan el nivel de la pista y el atractivo para las otras posibles transiciones de estado.
Actualización de feromonas
Los senderos generalmente se actualizan cuando todas las hormigas han completado su solución, aumentando o disminuyendo el nivel de senderos correspondientes a movimientos que fueron parte de soluciones "buenas" o "malas", respectivamente. Un ejemplo de una regla de actualización de feromonas global es
dónde es la cantidad de feromona depositada para una transición de estado , es el coeficiente de evaporación de feromonas , es el número de hormigas y es la cantidad de feromona depositada por la hormiga, normalmente dada para un problema de TSP (con movimientos correspondientes a arcos de la gráfica) por
dónde es el costo de la la gira de la hormiga (normalmente la duración) y es una constante.
Extensiones comunes
Estas son algunas de las variaciones más populares de los algoritmos ACO.
Sistema de hormigas (AS)
El sistema de hormigas es el primer algoritmo ACO. Este algoritmo corresponde al presentado anteriormente. Fue desarrollado por Dorigo. [25]
Sistema de colonias de hormigas (ACS)
En el algoritmo del sistema de colonias de hormigas, el sistema de hormigas original se modificó en tres aspectos: (i) la selección de bordes está sesgada hacia la explotación (es decir, favoreciendo la probabilidad de seleccionar los bordes más cortos con una gran cantidad de feromona); (ii) mientras construyen una solución, las hormigas cambian el nivel de feromonas de los bordes que están seleccionando aplicando una regla local de actualización de feromonas; (iii) al final de cada iteración, solo la mejor hormiga puede actualizar los rastros aplicando una regla de actualización de feromonas global modificada. [26]
Sistema de hormigas elitista
En este algoritmo, la mejor solución global deposita feromona en su rastro después de cada iteración (incluso si este rastro no ha sido revisado), junto con todas las otras hormigas. La estrategia elitista tiene como objetivo dirigir la búsqueda de todas las hormigas para construir una solución que contenga enlaces de la mejor ruta actual.
Sistema de hormigas máximo-mínimo (MMAS)
Este algoritmo controla las cantidades máximas y mínimas de feromonas en cada rastro. Solo el mejor recorrido global o el mejor recorrido de iteración pueden agregar feromonas a su estela. Para evitar el estancamiento del algoritmo de búsqueda, el rango de posibles cantidades de feromonas en cada camino se limita a un intervalo [τ max , τ min ]. Todos los bordes se inicializan a τ max para forzar una mayor exploración de soluciones. Los senderos se reinicializan a τ max cuando se acercan al estancamiento. [27]
Sistema de hormigas basado en rangos (ASrank)
Todas las soluciones se clasifican según su longitud. Solo un número fijo de las mejores hormigas en esta iteración pueden actualizar sus pruebas. La cantidad de feromona depositada se pondera para cada solución, de modo que las soluciones con trayectos más cortos depositen más feromonas que las soluciones con trayectos más largos.
Colonia de hormigas ortogonal continua (COAC)
El mecanismo de depósito de feromonas de COAC permite a las hormigas buscar soluciones de manera colaborativa y eficaz. Mediante el uso de un método de diseño ortogonal, las hormigas en el dominio factible pueden explorar sus regiones elegidas de manera rápida y eficiente, con una capacidad de búsqueda global mejorada y precisión. El método de diseño ortogonal y el método de ajuste de radio adaptativo también se pueden extender a otros algoritmos de optimización para ofrecer ventajas más amplias en la resolución de problemas prácticos. [28]
Optimización recursiva de colonias de hormigas
Es una forma recursiva de sistema de hormigas que divide todo el dominio de búsqueda en varios subdominios y resuelve el objetivo en estos subdominios. [29] Se comparan los resultados de todos los subdominios y los mejores se promueven al siguiente nivel. Los subdominios correspondientes a los resultados seleccionados se subdividen aún más y el proceso se repite hasta que se obtiene una salida de la precisión deseada. Este método ha sido probado en problemas de inversión geofísica mal planteados y funciona bien. [30]
Convergencia
Para algunas versiones del algoritmo, es posible demostrar que es convergente (es decir, es capaz de encontrar el óptimo global en un tiempo finito). La primera evidencia de convergencia para un algoritmo de colonia de hormigas se hizo en 2000, el algoritmo del sistema de hormigas basado en gráficos, y más tarde para los algoritmos ACS y MMAS. Como la mayoría de las metaheurísticas , es muy difícil estimar la velocidad teórica de convergencia. Un análisis de desempeño de un algoritmo continuo de colonias de hormigas con respecto a sus diversos parámetros (estrategia de selección de bordes, métrica de medición de distancia y tasa de evaporación de feromonas) mostró que su desempeño y tasa de convergencia son sensibles a los valores de los parámetros elegidos, y especialmente al valor de la tasa de evaporación de feromonas. [31] En 2004, Zlochin y sus colegas [32] demostraron que los algoritmos de tipo COAC podrían ser métodos asimilados de descenso de gradiente estocástico , sobre la entropía cruzada y el algoritmo de estimación de distribución . Propusieron estas metaheurísticas como un " modelo basado en la investigación ".
Aplicaciones
Los algoritmos de optimización de colonias de hormigas se han aplicado a muchos problemas de optimización combinatoria , que van desde la asignación cuadrática hasta el plegamiento de proteínas o los vehículos de enrutamiento y muchos métodos derivados se han adaptado a problemas dinámicos en variables reales, problemas estocásticos, objetivos múltiples e implementaciones paralelas . También se ha utilizado para producir soluciones casi óptimas al problema del viajante de comercio . Tienen una ventaja sobre el recocido simulado y los enfoques de algoritmos genéticos de problemas similares cuando el gráfico puede cambiar dinámicamente; el algoritmo de la colonia de hormigas se puede ejecutar de forma continua y adaptarse a los cambios en tiempo real. Esto es de interés en los sistemas de enrutamiento de redes y transporte urbano.
El primer algoritmo ACO se denominó sistema hormiga [25] y tenía como objetivo resolver el problema del viajante de comercio, en el que el objetivo es encontrar el viaje de ida y vuelta más corto para unir una serie de ciudades. El algoritmo general es relativamente simple y se basa en un conjunto de hormigas, cada una de las cuales realiza uno de los posibles viajes de ida y vuelta por las ciudades. En cada etapa, la hormiga elige moverse de una ciudad a otra de acuerdo con algunas reglas:
- Debe visitar cada ciudad exactamente una vez;
- Una ciudad lejana tiene menos posibilidades de ser elegida (la visibilidad);
- Cuanto más intenso sea el rastro de feromonas trazado en un borde entre dos ciudades, mayor será la probabilidad de que se elija ese borde;
- Habiendo completado su viaje, la hormiga deposita más feromonas en todos los bordes que atravesó, si el viaje es corto;
- Después de cada iteración, los rastros de feromonas se evaporan.
Problema de programación
- Problema de ordenamiento secuencial (SOP) [33]
- Problema de programación del taller de trabajos (JSP) [34]
- Problema de programación de la tienda abierta (OSP) [35] [36]
- Problema del taller de flujo de permutación (PFSP) [37]
- Problema de tardanza total de una sola máquina (SMTTP) [38]
- Problema de tardanza ponderada total de una sola máquina (SMTWTP) [39] [40] [41]
- Problema de programación de proyectos con recursos limitados (RCPSP) [42]
- Problema de programación de talleres grupales (GSP) [43]
- Problema de tardanza total de una sola máquina con tiempos de configuración dependientes de la secuencia (SMTTPDST) [44]
- Problema de programación del taller de flujo de varias etapas (MFSP) con tiempos de configuración / cambio dependientes de la secuencia [45]
Problema de ruta del vehículo
- Problema de generación de rutas para vehículos capacitados (CVRP) [46] [47] [48]
- Problema de generación de rutas para vehículos de varios depósitos (MDVRP) [49]
- Problema de generación de rutas para vehículos de período (PVRP) [50]
- Problema de generación de rutas para vehículos de reparto dividido (SDVRP) [51]
- Problema de generación de rutas de vehículos estocásticos (SVRP) [52]
- Problema de generación de rutas para vehículos con recogida y entrega (VRPPD) [53] [54]
- Problema de generación de rutas para vehículos con ventanas de tiempo (VRPTW) [55] [56] [57] [58]
- Problema de generación de rutas de vehículos dependiente del tiempo con ventanas de tiempo (TDVRPTW) [59]
- Problema de enrutamiento de vehículos con ventanas de tiempo y trabajadores de servicios múltiples (VRPTWMS)
Problema de asignación
- Problema de asignación cuadrática (QAP) [60]
- Problema de asignación generalizado (GAP) [61] [62]
- Problema de asignación de frecuencia (FAP) [63]
- Problema de asignación de redundancia (RAP) [64]
Establecer problema
- Establecer problema de portada (SCP) [65] [66]
- Problema de partición (SPP) [67]
- Problema de partición del árbol de gráficos con restricciones de peso (WCGTPP) [68]
- Problema del árbol de cardinalidad l ponderado en arco (AWlCTP) [69]
- Problema de varias mochilas (MKP) [70]
- Problema de conjunto independiente máximo (MIS) [71]
Problema de tamaño del dispositivo en el diseño físico nanoelectrónico
- La optimización basada en la optimización de colonias de hormigas (ACO) del circuito amplificador de detección basado en CMOS de 45 nm podría converger en soluciones óptimas en un tiempo mínimo. [72]
- La síntesis de circuitos reversibles basada en la optimización de colonias de hormigas (ACO) podría mejorar significativamente la eficiencia. [73]
Optimización y síntesis de antenas
Para optimizar la forma de las antenas, se pueden utilizar algoritmos de colonias de hormigas. Como ejemplo se pueden considerar antenas etiquetas RFID basadas en algoritmos de colonias de hormigas (ACO), [75] vibradores loopback y unloopback 10 × 10 [74]
Procesamiento de imágenes
El algoritmo ACO se utiliza en el procesamiento de imágenes para la detección de bordes de imágenes y el enlace de bordes. [76] [77]
- Detección de bordes:
El gráfico aquí es la imagen 2-D y las hormigas atraviesan desde un píxel depositando feromonas. El movimiento de las hormigas de un píxel a otro está dirigido por la variación local de los valores de intensidad de la imagen. Este movimiento provoca que la mayor densidad de feromona se deposite en los bordes.
Los siguientes son los pasos involucrados en la detección de bordes usando ACO: [78] [79] [80]
Paso 1: inicialización:
lugar aleatorio hormigas en la imagen dónde . Matriz de feromonasse inicializan con un valor aleatorio. El mayor desafío en el proceso de inicialización es determinar la matriz heurística.
Existen varios métodos para determinar la matriz heurística. Para el siguiente ejemplo, la matriz heurística se calculó en función de las estadísticas locales: las estadísticas locales en la posición del píxel (i, j).
Dónde es la imagen de tamaño
, que es un factor de normalización
se puede calcular utilizando las siguientes funciones:
El parámetro en cada una de las funciones anteriores ajusta las formas respectivas de las funciones.
Paso 2 Proceso de construcción:
el movimiento de la hormiga se basa en 4 píxeles conectados u 8 píxeles conectados . La probabilidad con la que se mueve la hormiga viene dada por la ecuación de probabilidad
Paso 3 y Paso 5 Proceso de actualización:
la matriz de feromonas se actualiza dos veces. en el paso 3 el rastro de la hormiga (dado por ) se actualiza donde, como en el paso 5, se actualiza la tasa de evaporación de la estela que viene dada por la siguiente ecuación.
, dónde es el coeficiente de desintegración de feromonas
Paso 7 Proceso de decisión: una
vez que las hormigas K se han movido una distancia fija L para la iteración N, la decisión de si es un borde o no se basa en el umbral T en la matriz de feromonasτ. El umbral para el siguiente ejemplo se calcula según el método de Otsu .
Borde de imagen detectado usando ACO:
Las imágenes a continuación se generan usando diferentes funciones dadas por la ecuación (1) a (4). [81]
- Enlace de borde: [82] ACO también ha demostrado su eficacia en algoritmos de enlace de borde.
Otras aplicaciones
- Predicción de quiebras [83]
- Clasificación [84]
- Enrutamiento de red orientado a la conexión [85]
- Enrutamiento de red sin conexión [86] [87]
- Minería de datos [84] [88] [89] [90]
- Flujos de efectivo descontados en la programación de proyectos [91]
- Recuperación de información distribuida [92] [93]
- Diseño de redes de energía y electricidad [94]
- Problema de programación del flujo de trabajo de la cuadrícula [95]
- Diseño de péptidos inhibidores para interacciones proteína-proteína [96]
- Sistema de prueba inteligente [97]
- Diseño de circuitos electrónicos de potencia [98]
- Plegado de proteínas [99] [100] [101]
- Identificación del sistema [102] [103]
Dificultad de definición
Con un algoritmo ACO, la ruta más corta en un gráfico, entre dos puntos A y B, se construye a partir de una combinación de varias rutas. [104] No es fácil dar una definición precisa de qué algoritmo es o no es una colonia de hormigas, porque la definición puede variar según los autores y usos. En términos generales, los algoritmos de colonias de hormigas se consideran metaheurísticas pobladas con cada solución representada por una hormiga moviéndose en el espacio de búsqueda. [105] Las hormigas marcan las mejores soluciones y tienen en cuenta las marcas anteriores para optimizar su búsqueda. Pueden verse como algoritmos probabilísticos de múltiples agentes que utilizan una distribución de probabilidad para realizar la transición entre cada iteración . [106] En sus versiones para problemas combinatorios, utilizan una construcción iterativa de soluciones. [107] Según algunos autores, lo que distingue a los algoritmos ACO de otros parientes (como los algoritmos para estimar la distribución o la optimización del enjambre de partículas) es precisamente su aspecto constructivo. En los problemas combinatorios, es posible que eventualmente se encuentre la mejor solución, aunque ninguna hormiga resulte eficaz. Así, en el ejemplo del problema del vendedor ambulante, no es necesario que una hormiga recorra realmente la ruta más corta: la ruta más corta se puede construir a partir de los segmentos más fuertes de las mejores soluciones. Sin embargo, esta definición puede ser problemática en el caso de problemas en variables reales, donde no existe una estructura de 'vecinos'. El comportamiento colectivo de los insectos sociales sigue siendo una fuente de inspiración para los investigadores. La amplia variedad de algoritmos (para optimización o no) que buscan la autoorganización en sistemas biológicos ha llevado al concepto de " inteligencia de enjambre ", [10] que es un marco muy general en el que encajan los algoritmos de colonias de hormigas.
Algoritmos de Stigmergy
En la práctica, existe un gran número de algoritmos que afirman ser "colonias de hormigas", sin compartir siempre el marco general de optimización por colonias de hormigas canónicas. [108] En la práctica, el uso de un intercambio de información entre hormigas a través del medio ambiente (un principio llamado " estigmergia ") se considera suficiente para que un algoritmo pertenezca a la clase de algoritmos de colonias de hormigas. Este principio ha llevado a algunos autores a crear el término "valor" para organizar métodos y comportamientos basados en la búsqueda de alimento, clasificación de larvas, división del trabajo y transporte cooperativo. [109]
Métodos relacionados
- Los algoritmos genéticos (GA) mantienen un conjunto de soluciones en lugar de solo una. El proceso de encontrar soluciones superiores imita el de la evolución, con soluciones que se combinan o muta para alterar el conjunto de soluciones, y se descartan las soluciones de calidad inferior.
- Un algoritmo de estimación de distribución (EDA) es un algoritmo evolutivo que sustituye a los operadores de reproducción tradicionales por operadores guiados por modelos. Dichos modelos se aprenden de la población mediante el empleo de técnicas de aprendizaje automático y se representan como modelos gráficos probabilísticos, a partir de los cuales se pueden muestrear nuevas soluciones [110] [111] o generar a partir de un cruce guiado. [112] [113]
- El recocido simulado (SA) es una técnica de optimización global relacionada que atraviesa el espacio de búsqueda generando soluciones vecinas de la solución actual. Siempre se acepta a un vecino superior. Un vecino inferior se acepta probabilísticamente en función de la diferencia de calidad y un parámetro de temperatura. El parámetro de temperatura se modifica a medida que avanza el algoritmo para alterar la naturaleza de la búsqueda.
- La optimización de búsqueda reactiva se centra en combinar el aprendizaje automático con la optimización, agregando un ciclo de retroalimentación interno para autoajustar los parámetros libres de un algoritmo a las características del problema, de la instancia y de la situación local en torno a la solución actual.
- La búsqueda tabú (TS) es similar al recocido simulado en que ambos atraviesan el espacio de la solución probando mutaciones de una solución individual. Mientras que el recocido simulado genera solo una solución mutada, la búsqueda tabú genera muchas soluciones mutadas y pasa a la solución con la menor adecuación de las generadas. Para evitar el ciclismo y fomentar un mayor movimiento a través del espacio de la solución, se mantiene una lista tabú de soluciones parciales o completas. Está prohibido pasar a una solución que contenga elementos de la lista tabú, que se actualiza a medida que la solución atraviesa el espacio de la solución.
- Los algoritmos del sistema inmunológico artificial (AIS) se basan en los sistemas inmunitarios de los vertebrados.
- Optimización de enjambres de partículas (PSO), un método de inteligencia de enjambres
- Gotas de agua inteligentes (IWD), un algoritmo de optimización basado en enjambres basado en gotas de agua natural que fluyen en los ríos
- Algoritmo de búsqueda gravitacional (GSA), un método de inteligencia de enjambre
- Método de agrupación de colonias de hormigas (ACCM), un método que hace uso del enfoque de agrupación, extendiendo el ACO.
- Búsqueda de difusión estocástica (SDS), una técnica de optimización y búsqueda global probabilística basada en agentes que se adapta mejor a problemas en los que la función objetivo se puede descomponer en múltiples funciones parciales independientes
Historia
Los inventores son Frans Moyson y Bernard Manderick . Los pioneros del campo incluyen a Marco Dorigo , Luca Maria Gambardella . [114]
Cronología de algoritmos de optimización de colonias de hormigas.
- 1959, Pierre-Paul Grassé inventó la teoría de la estigmergia para explicar el comportamiento de la construcción de nidos en termitas ; [115]
- 1983, Deneubourg y sus colegas estudiaron el comportamiento colectivo de las hormigas ; [116]
- 1988, y Moyson Manderick tienen un artículo sobre la autoorganización entre las hormigas; [117]
- 1989, el trabajo de Goss, Aron, Deneubourg y Pasteels sobre el comportamiento colectivo de las hormigas argentinas , que dará la idea de algoritmos de optimización de colonias de hormigas; [118]
- 1989, implementación de un modelo de comportamiento para la alimentación por Ebling y sus colegas; [119]
- En 1991, M. Dorigo propuso el sistema de hormigas en su tesis doctoral (que fue publicada en 1992 [6] ). Cinco años después se publicó un informe técnico extraído de la tesis y en coautoría de V. Maniezzo y A. Colorni [120] ; [25]
- 1994, Appleby y Steward of British Telecommunications Plc publicaron la primera aplicación a las redes de telecomunicaciones [121]
- 1995, Gambardella y Dorigo propusieron ant-q , [122] la versión preliminar del sistema de colonias de hormigas como primera estensión del sistema de hormigas. [25]
- 1996, Gambardella y Dorigo propusieron un sistema de colonias de hormigas [123]
- 1996, publicación del artículo sobre el sistema de hormigas; [25]
- 2000, Hoos y Stützle inventan el sistema de hormigas máximo-mínimo ; [27]
- 1997, Dorigo y Gambardella propusieron un sistema de colonias de hormigas hibridado con búsqueda local; [26]
- 1997, Schoonderwoerd y sus colegas publicaron una aplicación mejorada para redes de telecomunicaciones ; [124]
- 1998, Dorigo lanza la primera conferencia dedicada a los algoritmos ACO; [125]
- 1998, Stützle propone implementaciones paralelas iniciales ; [126]
- 1999, Gambardella, Taillard y Agazzi propusieron macs-vrptw , primer sistema de colonias de hormigas múltiples aplicado a problemas de rutas de vehículos con ventanas de tiempo, [55]
- 1999, Bonabeau, Dorigo y Theraulaz publican un libro que trata principalmente de hormigas artificiales [127]
- 2000, número especial de la revista Future Generation Computer Systems sobre algoritmos de hormigas [128]
- 2000, primeras aplicaciones a la programación , secuencia de programación y satisfacción de restricciones ;
- 2000, Gutjahr proporciona la primera evidencia de convergencia para un algoritmo de colonias de hormigas [129]
- 2001, primer uso de algoritmos COA por empresas ( Eurobios y AntOptima );
- 2001, IREDI y sus colegas publicaron el primer multi-objetivo algoritmo [130]
- 2002, primeras aplicaciones en el diseño de horarios, redes bayesianas;
- 2002, Bianchi y sus colegas sugirieron el primer algoritmo para problemas estocásticos ; [131]
- 2004, Dorigo y Stützle publican el libro Ant Colony Optimization con MIT Press [132]
- 2004, Zlochin y Dorigo muestran que algunos algoritmos son equivalentes al descenso de gradiente estocástico , el método de entropía cruzada y algoritmos para estimar la distribución [32]
- 2005, primeras aplicaciones a problemas de plegamiento de proteínas .
- En 2012, Prabhakar y sus colegas publican una investigación relacionada con el funcionamiento de hormigas individuales que se comunican en tándem sin feromonas, reflejando los principios de la organización de redes informáticas. El modelo de comunicación se ha comparado con el Protocolo de control de transmisión . [133]
- 2016, primera aplicación al diseño de secuencias de péptidos. [96]
- 2017, integración exitosa del método de toma de decisiones multicriterio PROMETHEE en el algoritmo ACO ( algoritmo HUMANT ). [134]
Referencias
- ^ Waldner, Jean-Baptiste (2008). Nanocomputadoras e inteligencia de enjambre . Londres: ISTE John Wiley & Sons . pag. 225. ISBN 978-1-84704-002-2.
- ^ Monmarché Nicolas, Guinand Frédéric y Siarry Patrick (2010). Hormigas artificiales . Wiley-ISTE. ISBN 978-1-84821-194-0.
- ^ Dorigo, Gambardella, M, LM (1997). "Enfoque de aprendizaje para el problema del viajante de comercio". Transacciones IEEE sobre Computación Evolutiva . 1 (1): 214. doi : 10.1109 / 4235.585892 .
- ^ Optimización de colonia de hormigas por Marco Dorigo y Thomas Stützle, MIT Press, 2004. ISBN 0-262-04219-3
- ^ A. Colorni, M. Dorigo et V. Maniezzo, Optimización distribuida por colonias de hormigas , actes de la première conférence européenne sur la vie artificielle, París, Francia, Elsevier Publishing, 134-142, 1991.
- ^ a b M. Dorigo, Optimización, aprendizaje y algoritmos naturales , tesis doctoral, Politecnico di Milano, Italia, 1992.
- ^ Zlochin, Mark; Birattari, Mauro; Meuleau, Nicolas; Dorigo, Marco (1 de octubre de 2004). "Búsqueda basada en modelos para la optimización combinatoria: una encuesta crítica". Anales de investigación operativa . 131 (1–4): 373–395. CiteSeerX 10.1.1.3.427 . doi : 10.1023 / B: ANOR.0000039526.52305.af . ISSN 0254-5330 . S2CID 63137 .
- ^ Fladerer, Johannes-Paul; Kurzmann, Ernst (noviembre de 2019). SABIDURÍA DE LOS MUCHOS: cómo crear autoorganización y cómo utilizar la inteligencia colectiva ... en las empresas y en la sociedad a partir del mana . LIBROS BAJO DEMANDA. ISBN 9783750422421.
- ^ Marco Dorigo y Thomas Stültze, Optimización de colonias de hormigas, p.12. 2004.
- ^ a b Waldner, Jean-Baptiste (2008). Nanocomputadoras e inteligencia de enjambre . Londres: ISTE John Wiley & Sons. pag. 214. ISBN 978-1-84704-002-2.
- ^ Waldner, Jean-Baptiste (2007). Inventer l'Ordinateur du XXIème Siècle . Londres: Hermes Science . págs. 259-265. ISBN 978-2-7462-1516-0.
- ^ Waldner, Jean-Baptiste (2008). Nanocomputadoras e inteligencia de enjambre . Londres: ISTE John Wiley & Sons. pag. 215. ISBN 978-1-84704-002-2.
- ^ Lima, Danielli A. y Gina MB Oliveira. " Un modelo de memoria de hormigas autómatas celulares de búsqueda de alimento en un enjambre de robots ". Modelado matemático aplicado 47, 2017: 551-572.
- ^ Russell, R. Andrew. " Hormigas, ¿un ejemplo a seguir para los robots? ". Robótica y Automatización, 1999. Actas. 1999 IEEE International Conference on. Vol. 4. IEEE, 1999.
- ^ Fujisawa, Ryusuke, et al. " Diseño de la comunicación de feromonas en robótica de enjambres: comportamiento de búsqueda de alimento en grupo mediado por sustancias químicas ". Swarm Intelligence 8.3 (2014): 227-246.
- ^ Sakakibara, Toshiki y Daisuke Kurabayashi. " Sistema de feromonas artificiales que utiliza rfid para la navegación de robots autónomos ". Revista de Ingeniería Biónica 4.4 (2007): 245-253.
- ^ Arvin, Farshad, et al. " Investigación de agregación basada en señales en entornos estáticos y dinámicos con un enjambre de robots móviles ". Comportamiento adaptativo (2016): 1-17.
- ^ Farshad Arvin, et al. " Imitación de agregación de abejas con comportamiento colectivo de robots enjambres ". Revista Internacional de Sistemas de Inteligencia Computacional 4.4 (2011): 739-748.
- ^ Schmickl, Thomas y col. " Póngase en contacto: toma de decisiones cooperativa basada en colisiones de robot a robot ". Agentes autónomos y sistemas multiagente 18.1 (2009): 133-155.
- ^ Garnier, Simon y col. " ¿Las hormigas necesitan estimar las propiedades geométricas de las bifurcaciones de senderos para encontrar una ruta eficiente? Un banco de pruebas de robótica de enjambres " . PLoS Comput Biol 9.3 (2013): e1002903.
- ^ Arvin, Farshad, et al. " Agregación basada en señales con un enjambre de robots móviles: un método novedoso basado en datos difusos ". Comportamiento adaptativo 22.3 (2014): 189-206.
- ^ Garnier, Simon y col. " Alicia en la tierra de las feromonas: una configuración experimental para el estudio de robots parecidos a hormigas ". 2007 Simposio IEEE Swarm Intelligence. IEEE, 2007.
- ^ Farshad Arvin y col. " COSΦ: sistema de feromonas artificiales para la investigación de enjambres robóticos ". Conferencia Internacional IEEE / RSJ sobre Robots y Sistemas Inteligentes (IROS) 2015.
- ^ Krajník, Tomáš, et al. " Un práctico sistema de localización multirobot ". Revista de sistemas inteligentes y robóticos 76.3-4 (2014): 539-562.
- ^ a b c d e M. Dorigo, V. Maniezzo, et A. Colorni, Ant system: optimización por una colonia de agentes cooperantes , IEEE Transactions on Systems, Man, and Cybernetics - Part B, volume 26, numéro 1, páginas 29-41, 1996.
- ^ a b M. Dorigo et LM Gambardella, Sistema de colonia de hormigas: un enfoque de aprendizaje cooperativo para el problema del vendedor ambulante , IEEE Transactions on Evolutionary Computation, volumen 1, numéro 1, páginas 53-66, 1997.
- ^ a b T. Stützle et HH Hoos, MAX MIN Ant System , Future Generation Computer Systems, volumen 16, páginas 889-914, 2000
- ^ X Hu, J Zhang y Y Li (2008). Métodos ortogonales basados en la búsqueda de colonias de hormigas para la resolución de problemas de optimización continua. Revista de ciencia y tecnología de la computación , 23 (1), pp.2-18.
- ^ Gupta, DK; Arora, Y .; Singh, Reino Unido; Gupta, JP, "Optimización recursiva de colonias de hormigas para la estimación de parámetros de una función", avances recientes en tecnología de la información (RAIT), 2012 1ra Conferencia Internacional sobre, vol., No., Págs. 448-454, 15-17 de marzo de 2012
- ^ Gupta, DK; Gupta, JP; Arora, Y .; Shankar, U., " Optimización recursiva de colonias de hormigas: una nueva técnica para la estimación de parámetros de función a partir de datos de campo geofísicos ", Near Surface Geophysics, vol. 11, no. 3, págs. 325-339
- ^ VKOjha, A. Abraham y V. Snasel, ACO para la optimización continua de funciones: un análisis de rendimiento , 14a Conferencia internacional sobre diseño y aplicaciones de sistemas inteligentes (ISDA), Japón, página 145-150, 2017, 978-1-4799-7938 -14/7 de 2014 IEEE.
- ^ a b M. Zlochin, M. Birattari, N. Meuleau, et M. Dorigo, Búsqueda basada en modelos para la optimización combinatoria: una encuesta crítica , Annals of Operations Research, vol. 131, págs. 373-395, 2004.
- ^ LM Gambardella, M. Dorigo, "Un sistema de colonia de hormigas hibridado con una nueva búsqueda local para el problema de ordenamiento secuencial", INFORMS Journal on Computing, vol. 12 (3), págs. 237-255, 2000.
- ^ D. Martens, M. De Backer, R. Haesen, J. Vanthienen, M. Snoeck, B. Baesens, Clasificación con optimización de colonias de hormigas , IEEE Transactions on Evolutionary Computation, volumen 11, número 5, páginas 651-665, 2007 .
- ^ B. Pfahring, "Búsqueda de múltiples agentes para programación abierta: adaptación del formalismo Ant-Q", Informe técnico TR-96-09, 1996.
- ^ C. Blem, " Beam-ACO, optimización de la hibridación de colonias de hormigas con búsqueda de haces. Una aplicación para la programación de tiendas abiertas ", Informe técnico TR / IRIDIA / 2003-17, 2003.
- ^ T. Stützle, "Un enfoque de hormiga para el problema del taller de flujo", Informe técnico AIDA-97-07, 1997.
- ^ A. Bauer, B. Bullnheimer, RF Hartl y C. Strauss, "Minimizar la tardanza total en una sola máquina mediante la optimización de colonias de hormigas", Revista de Europa Central para Investigación de Operaciones y Economía, vol.8, no.2, pp.125 -141, 2000.
- ^ M. den Besten, "Hormigas para el problema de tardanza ponderada total de una sola máquina", Tesis de maestría, Universidad de Amsterdam, 2000.
- ^ M, den Bseten, T. Stützle y M. Dorigo, "Optimización de colonias de hormigas para el problema de tardanza ponderada total", Actas de PPSN-VI, Sexta Conferencia Internacional sobre Solución de Problemas Paralelos desde la Naturaleza, vol. 1917 de Lecture Notes in Computer Science , páginas 611-620, 2000.
- ^ D. Merkle y M. Middendorf, " Un algoritmo de hormiga con una nueva regla de evaluación de feromonas para problemas de tardanza total ", Aplicaciones del mundo real de la informática evolutiva, vol. 1803 de Lecture Notes in Computer Science, páginas 287-296, 2000.
- ^ D. Merkle, M. Middendorf y H. Schmeck, "Optimización de colonias de hormigas para la programación de proyectos con recursos limitados", Actas de la Conferencia de Computación Genética y Evolutiva (GECCO 2000), pp.893-900, 2000.
- ^ C. Blum, " ACO aplicado a la programación de talleres grupales: un estudio de caso sobre intensificación y diversificación [ enlace muerto permanente ] ", Actas de ANTS 2002, vol. 2463 de Lecture Notes in Computer Science, páginas 14 a 27, 2002.
- ^ C. Gagné, WL Price y M. Gravel, " Comparación de un algoritmo ACO con otras heurísticas para el problema de programación de una sola máquina con tiempos de configuración dependientes de la secuencia ", Journal of the Operational Research Society, vol.53, pp.895-906 , 2002.
- ^ AV Donati, V. Darley, B. Ramachandran, "Un algoritmo Ant-Bidding para el problema de programación de Flowshop multietapa: Optimización y transiciones de fase", capítulo de libro en Avances en metaheurística para optimización dura, Springer, ISBN 978-3-540-72959-4 , páginas 111-138, 2008.
- ^ Toth, Paolo; Vigo, Daniele (2002). "Modelos, relajaciones y enfoques exactos para el problema de enrutamiento de vehículos capacitados". Matemáticas aplicadas discretas . 123 (1-3): 487-512. doi : 10.1016 / S0166-218X (01) 00351-1 .
- ^ JM Belenguer y E. Benavent, "Un algoritmo de plano de corte para el problema de enrutamiento de arco capacitado", Computers & Operations Research, vol.30, no.5, pp.705-728, 2003.
- ^ TK Ralphs, "Ramal y corte en paralelo para enrutamiento de vehículos capacitados", Computación paralela, vol.29, pp.607-629, 2003.
- ^ Salhi, S .; Sari, M. (1997). "Una heurística compuesta de varios niveles para el problema de mezcla de flotas de vehículos de varios depósitos". Revista europea de investigación operativa . 103 : 95-112. doi : 10.1016 / S0377-2217 (96) 00253-6 .
- ^ Angelelli, Enrico; Speranza, Maria Grazia (2002). "El problema de las rutas periódicas de los vehículos con las instalaciones intermedias". Revista europea de investigación operativa . 137 (2): 233–247. doi : 10.1016 / S0377-2217 (01) 00206-5 .
- ^ Ho, Sin C .; Haugland, Dag (2002). "Una heurística de búsqueda tabú para el problema de enrutamiento de vehículos con ventanas de tiempo y entregas divididas". Investigación de Computación y Operaciones . 31 (12): 1947-1964. CiteSeerX 10.1.1.8.7096 . doi : 10.1016 / S0305-0548 (03) 00155-2 .
- ^ Secomandi, Nicola. "Comparación de algoritmos de programación neurodinámica para el problema de enrutamiento de vehículos con demandas estocásticas". Computers & Operations Research : 2000. CiteSeerX 10.1.1.392.4034 .
- ^ WP Nanry y JW Barnes, " Resolviendo el problema de recogida y entrega con ventanas de tiempo mediante la búsqueda tabú reactiva ", Investigación sobre transporte Parte B, vol.34, no. 2, páginas 107-121, 2000.
- ^ R. Bent y PV Hentenryck, " Un algoritmo híbrido de dos etapas para problemas de enrutamiento de vehículos de recogida y entrega con ventanas de tiempo ", Computers & Operations Research, vol.33, no.4, pp.875-893, 2003.
- ^ a b LM Gambardella, E. Taillard, G. Agazzi, "MACS-VRPTW: un sistema de colonias de hormigas múltiples para problemas de enrutamiento de vehículos con ventanas de tiempo", en D. Corne, M. Dorigo y F. Glover, editores, nuevas ideas en Optimization, McGraw-Hill, Londres, Reino Unido, págs. 63-76, 1999.
- ^ Bachem, A .; Hochstättler, W .; Malich, M. (1996). "La heurística comercial simulada para resolver problemas de rutas de vehículos". Matemáticas aplicadas discretas . 65 (1-3): 47-72. doi : 10.1016 / 0166-218X (95) 00027-O .
- ^ Hong, Sung-Chul; Park, Yang-Byung (1999). "Una heurística para el enrutamiento de vehículos bi-objetivo con restricciones de ventana de tiempo". Revista Internacional de Economía de la Producción . 62 (3): 249-258. doi : 10.1016 / S0925-5273 (98) 00250-3 .
- ^ Russell, Robert A .; Chiang, Wen-Chyuan (2006). "Búsqueda de dispersión para el problema de generación de rutas de vehículos con ventanas de tiempo". Revista europea de investigación operativa . 169 (2): 606–622. doi : 10.1016 / j.ejor.2004.08.018 .
- ^ AV Donati, R. Montemanni, N. Casagrande, AE Rizzoli, LM Gambardella, " Problema de enrutamiento de vehículos dependiente del tiempo con un sistema de colonias de hormigas múltiples ", European Journal of Operational Research, vol.185, no.3, pp.1174– 1191, 2008.
- ^ "Sistema Ant MAX-MIN para problemas de asignación cuadrática". 1997. CiteSeerX 10.1.1.47.5167 . Cite journal requiere
|journal=
( ayuda ) - ^ R. Lourenço y D. Serra " Heurística de búsqueda adaptativa para el problema de asignación generalizada ", Mathware & soft computing, vol.9, no.2-3, 2002.
- ^ M. Yagiura, T. Ibaraki y F. Glover, " Un enfoque de cadena de eyección para el problema de asignación generalizada ", INFORMS Journal on Computing, vol. 16, no. 2, págs. 133-151, 2004.
- ^ KI Aardal, SPM van Hoesel , AMCA Koster, C. Mannino y Antonio. Sassano, "Modelos y técnicas de solución para el problema de asignación de frecuencia", A Quarterly Journal of Operations Research, vol.1, no.4, pp.261-317, 2001.
- ^ YC Liang y AE Smith, " Un algoritmo de optimización de colonias de hormigas para el problema de asignación de redundancia (RAP) [ enlace muerto permanente ] ", IEEE Transactions on Reliability, vol.53, no.3, pp.417-423, 2004.
- ^ G. Leguizamon y Z. Michalewicz, " Una nueva versión del sistema de hormigas para problemas de subconjuntos ", Actas del Congreso de 1999 sobre Computación Evolutiva (CEC 99), vol.2, pp.1458-1464, 1999.
- ^ R. Hadji, M. Rahoual, E. Talbi y V. Bachelet "Colonias de hormigas para el problema de cobertura de conjuntos", Actas abstractas de ANTS2000, pp.63-66, 2000.
- ^ V Maniezzo y M Milandri, " Un marco basado en hormigas para problemas muy restringidos ", Actas de ANTS2000, pp.222-227, 2002.
- ^ R. Cordone y F. Maffioli, " Sistema de hormigas coloreadas y búsqueda local para diseñar redes de telecomunicaciones locales [ enlace muerto permanente ] ", Aplicaciones de la informática evolutiva: Actas de los talleres de Evo, vol.2037, pp.60-69, 2001.
- ^ C. Blum y MJ Blesa, " Metaheurísticas para el problema del árbol de cardinalidad k ponderado por los bordes ", Informe técnico TR / IRIDIA / 2003-02, IRIDIA, 2003.
- ^ S. Fidanova, "Algoritmo ACO para MKP usando información heurística diversa" , Métodos numéricos y aplicaciones, vol.2542, pp.438-444, 2003.
- ^ G. Leguizamon, Z. Michalewicz y Martin Schutz, " Un sistema de hormigas para el problema del conjunto máximo independiente ", Actas del Congreso Argentino de Ciencias de la Computación de 2001, vol.2, pp.1027-1040, 2001.
- ^ O. Okobiah, SP Mohanty y E. Kougianos, " Algoritmo de colonia de hormigas asistido por metamodelo Kriging ordinario para la optimización rápida del diseño analógico Archivado el 4 de marzo de 2016 en Wayback Machine ", en Actas del 13 ° Simposio internacional de IEEE sobre calidad electrónica Diseño (ISQED), págs.458--463, 2012.
- ^ M. Sarkar, P. Ghosal y SP Mohanty, " Síntesis de circuito reversible utilizando el método Quinne-McCluskey basado en ACO y SA Archivado el 29 de julio de 2014, en la Wayback Machine ", en Actas del 56.o Simposio Internacional del Medio Oeste de IEEE sobre circuitos y Systems (MWSCAS), 2013, págs.416--419.
- ^ a b c Ermolaev SY, Slyusar VI Antena de síntesis basada en el algoritmo de optimización de colonias de hormigas // Proc. ICATT'2009, Lviv, Ucrania 6 - 9 de octubre de 2009. - Páginas 298 - 300 [1]
- ^ Marcus Randall, Andrew Lewis, Amir Galehdar, David Thiel. Uso de la optimización de colonias de hormigas para mejorar la eficiencia de las antenas RFID de líneas de meandro pequeñas .// En la 3ª Conferencia internacional de informática en red y e-ciencia de IEEE [2] , 2007
- ^ S. Meshoul y M Batouche, " Sistema de colonias de hormigas con dinámica extrema para la coincidencia de puntos y estimación de pose ", Actas de la 16ª Conferencia Internacional sobre Reconocimiento de Patrones, vol.3, pp.823-826, 2002.
- ^ H. Nezamabadi-pour, S. Saryazdi y E. Rashedi, " Detección de bordes mediante algoritmos de hormigas ", Soft Computing, vol. 10, no 7, págs. 623-628, 2006.
- ^ Tian, Jing; Yu, Weiyu; Xie, Shengli (2008). Congreso IEEE 2008 sobre Computación Evolutiva (Congreso Mundial IEEE sobre Inteligencia Computacional) . págs. 751–756. doi : 10.1109 / CEC.2008.4630880 . ISBN 978-1-4244-1822-0. S2CID 1782195 .
- ^ Gupta, Charu; Gupta, Sunanda. "Detección de bordes de una imagen basada en la técnica de optimización de colonias de hormigas" .
- ^ Jevtić, A .; Quintanilla-Domínguez, J .; Cortina-Januchs, MG; Andina, D. (2009). Detección de bordes mediante algoritmo de búsqueda de colonias de hormigas y mejora de contraste multiescala . Conferencia Internacional IEEE sobre Sistemas, Hombre y Cibernética, 2009. SMC 2009 . págs. 2193–2198. doi : 10.1109 / ICSMC.2009.5345922 . ISBN 978-1-4244-2793-2. S2CID 11654036 .
- ^ "Intercambio de archivos - Optimización de colonias de hormigas (ACO)" . MATLAB Central .
- ^ Jevtić, A .; Melgar, I .; Andina, D. (2009). 2009 35ª Conferencia Anual de IEEE Industrial Electronics . 35ª Conferencia Anual de Electrónica Industrial IEEE, 2009. IECON '09. págs. 3353–3358. doi : 10.1109 / IECON.2009.5415195 . ISBN 978-1-4244-4648-3. S2CID 34664559 .Mantenimiento de CS1: ubicación ( enlace )
- ^ Zhang, Y. (2013). "Un modelo basado en reglas para la predicción de quiebras basado en un algoritmo de colonia de hormigas genético mejorado" . Problemas matemáticos en ingeniería . 2013 : 753251. doi : 10.1155 / 2013/753251 .
- ^ a b D. Martens, M. De Backer, R. Haesen, J. Vanthienen, M. Snoeck, B. Baesens, " Clasificación con optimización de colonias de hormigas ", Transacciones IEEE sobre computación evolutiva, volumen 11, número 5, páginas 651 —665, 2007.
- ^ GD Caro y M. Dorigo, "Ampliación de AntNet para enrutamiento de calidad de servicio de mejor esfuerzo", Actas del primer taller internacional sobre optimización de colonias de hormigas (ANTS'98), 1998.
- ^ GD Caro y M. Dorigo " AntNet: un enfoque de agentes móviles para el enrutamiento adaptativo ", Actas de la trigésima primera conferencia internacional de Hawái sobre ciencia de sistemas, vol.7, pp.74-83, 1998.
- ^ GD Caro y M. Dorigo, " Dos algoritmos de colonias de hormigas para el enrutamiento de mejor esfuerzo en redes de datagramas ", Actas de la Décima Conferencia Internacional IASTED sobre Computación y Sistemas Paralelos y Distribuidos (PDCS'98), pp.541-546, 1998 .
- ^ D. Martens, B. Baesens, T. Fawcett " Encuesta editorial: inteligencia de enjambre para minería de datos ", aprendizaje automático, volumen 82, número 1, págs. 1-42, 2011
- ^ RS Parpinelli, HS Lopes y A. A Freitas, " Un algoritmo de colonia de hormigas para el descubrimiento de reglas de clasificación ", Minería de datos: un enfoque heurístico, pp.191-209, 2002.
- ^ RS Parpinelli, HS Lopes y A. A Freitas, " Minería de datos con un algoritmo de optimización de colonias de hormigas ", IEEE Transactions on Evolutionary Computation, vol.6, no.4, pp.321-332, 2002.
- ^ WN Chen, J. ZHANG y H. Chung, " Optimización de flujos de efectivo descontados en la programación de proyectos: un enfoque de optimización de colonia de hormigas ", Transacciones IEEE sobre sistemas, hombre y cibernética - Parte C: Aplicaciones y revisiones Vol.40 No .5 págs. 64-77, enero de 2010.
- ^ D. Picard, A. Revel, M. Cord, "Una aplicación de la inteligencia de enjambre a la recuperación de imágenes distribuidas", Ciencias de la información, 2010
- ^ D. Picard, M. Cord, A. Revel, " Recuperación de imágenes en redes: Aprendizaje activo mediante el algoritmo Ant ", Transacciones IEEE sobre multimedia, vol. 10, no. 7, págs.1356-1365 - noviembre de 2008
- ^ Warner, Lars; Vogel, Ute (2008). Optimización de redes de suministro de energía mediante optimización de colonias de hormigas (PDF) . Informática ambiental y ecología industrial - 22º Congreso Internacional de Informática para la Protección del Medio Ambiente. Aquisgrán, Alemania: Shaker Verlag. ISBN 978-3-8322-7313-2. Consultado el 9 de octubre de 2018 .
- ^ WN Chen y J. ZHANG "Enfoque de optimización de colonias de hormigas para problemas de programación de flujo de trabajo de cuadrícula con varios requisitos de QoS", Transacciones IEEE sobre sistemas, hombre y cibernética - Parte C: Aplicaciones y revisiones, vol. 31, núm. 1, págs. 29-43, enero de 2009.
- ^ a b Zaidman, Daniel; Wolfson, Haim J. (1 de agosto de 2016). "PiñaColada: algoritmo de diseño ad-hoc de colonia de hormigas inhibidor de péptidos" . Bioinformática . 32 (15): 2289–2296. doi : 10.1093 / bioinformatics / btw133 . ISSN 1367-4803 . PMID 27153578 .
- ^ Xiao. M.Hu, J. ZHANG y H. Chung, " Un sistema de prueba inteligente integrado con un método de composición de prueba basado en la optimización de colonias de hormigas ", Transacciones IEEE sobre sistemas, hombre y cibernética - Parte C: Aplicaciones y revisiones, vol. 39, núm. 6, págs. 659-669, diciembre de 2009.
- ^ J. ZHANG, H. Chung, WL Lo y T. Huang, " Algoritmo extendido de optimización de colonias de hormigas para el diseño de circuitos electrónicos de potencia ", Transacciones de IEEE en electrónica de potencia. Vol.24, No.1, pp.147-162, enero de 2009.
- ^ XM Hu, J. ZHANG, J. Xiao y Y. Li, " Protein Folding in Hydrophobic-Polar Lattice Model: A Flexible Ant-Colony Optimization Approach ", Protein and Peptide Letters, Volumen 15, Número 5, 2008, pág. 469-477.
- ^ A. Shmygelska, RA Hernández y HH Hoos, " Un algoritmo de optimización de colonias de hormigas para el problema de plegamiento de proteínas 2D HP [ enlace muerto permanente ] ", Actas del 3er Taller internacional sobre algoritmos de hormigas / ANTS 2002, Lecture Notes in Computer Science, vol.2463, págs. 40-52, 2002.
- ^ M. Nardelli; L. Tedesco; A. Bechini (2013). Comportamiento de reticulado cruzado del plegamiento de ACO general para proteínas en el modelo HP . Proc. De ACM SAC 2013 . págs. 1320-1327. doi : 10.1145 / 2480362.2480611 . ISBN 9781450316569. S2CID 1216890 .
- ^ L. Wang y QD Wu, "Identificación de parámetros del sistema lineal basada en el algoritmo del sistema de hormigas", Actas de la Conferencia IEEE sobre aplicaciones de control, págs. 401-406, 2001.
- ^ KC Abbaspour, R. Schulin, MT Van Genuchten, " Estimación de los parámetros hidráulicos del suelo insaturado mediante la optimización de colonias de hormigas ", Avances en los recursos hídricos, vol. 24, no. 8, págs. 827-841, 2001.
- ^ Shmygelska, Alena; Hoos, Holger H. (2005). "Un algoritmo de optimización de colonias de hormigas para el problema de plegamiento de proteínas polares hidrofóbicas 2D y 3D" . BMC Bioinformática . 6 : 30. doi : 10.1186 / 1471-2105-6-30 . PMC 555464 . PMID 15710037 .
- ^ Fred W. Glover, Gary A. Kochenberger, Manual de metaheurística , [3] , Springer (2003)
- ^ http://www.multiagent.fr/extensions/ICAPManager/pdf/LauriCharpillet2006.pdf
- ^ WJ Gutjahr, algoritmos ACO con convergencia garantizada a la solución óptima , [4] , (2002)
- ^ Santpal Singh Dhillon, Ant enrutamiento, búsqueda y algoritmos de estimación de topología para redes ad hoc , [5] , IOS Press, (2008)
- ^ A. Ajith; G. Crina; R. Vitorino (éditeurs), Stigmergic Optimization , Studies in Computational Intelligence, volumen 31, 299 páginas, 2006. ISBN 978-3-540-34689-0
- ^ Pelikan, Martin; Goldberg, David E .; Cantú-Paz, Erick (1 de enero de 1999). BOA: El algoritmo de optimización bayesiano . Actas de la Primera Conferencia Anual sobre Computación Genética y Evolutiva - Volumen 1 . Gecco'99. págs. 525–532. ISBN 9781558606111.
- ^ Pelikan, Martin (2005). Algoritmo de optimización jerárquico bayesiano: hacia una nueva generación de algoritmos evolutivos (1ª ed.). Berlín [ua]: Springer. ISBN 978-3-540-23774-7.
- ^ Thierens, Dirk (11 de septiembre de 2010). "El algoritmo genético del árbol de vinculación". Resolución de problemas paralelos desde la naturaleza, PPSN XI . págs. 264-273. doi : 10.1007 / 978-3-642-15844-5_27 . ISBN 978-3-642-15843-8. S2CID 28648829 . Falta o vacío
|title=
( ayuda ) - ^ Martins, Jean P .; Fonseca, Carlos M .; Delbem, Alexandre CB (25 de diciembre de 2014). "Sobre el desempeño de algoritmos genéticos de árbol de ligamiento para el problema de la mochila multidimensional". Neurocomputación . 146 : 17-29. doi : 10.1016 / j.neucom.2014.04.069 .
- ^ Manderick, Moyson, Bernard, Frans (1988). "El comportamiento colectivo de las hormigas: un ejemplo de autoorganización en paralelismo masivo". Stanford: Actas del Simposio de primavera de AAAI sobre modelos paralelos de inteligencia. Cite journal requiere
|journal=
( ayuda ) - ^ P.-P. Grassé, La reconstruction du nid et les coordinations inter-individuelles chez Belicositermes natalensis et Cubitermes sp. La théorie de la Stigmergie: Essai d'interprétation du comportement des termites constructeurs , Insectes Sociaux, numéro 6, p. 41-80, 1959.
- ^ JL Denebourg, JM Pasteels y JC Verhaeghe, Comportamiento probabilístico en hormigas: ¿una estrategia de errores? , Revista de Biología Teórica, numéro 105, 1983.
- ^ F. Moyson, B. Manderick, El comportamiento colectivo de las hormigas: un ejemplo de autoorganización en paralelismo masivo , Simposio de primavera de Actes de AAAI sobre modelos paralelos de inteligencia, Stanford, Californie, 1988.
- ^ S. Goss, S. Aron, J.-L. Deneubourg y J.-M. Pasteels, Atajos autoorganizados en la hormiga argentina , Naturwissenschaften, volumen 76, páginas 579-581, 1989
- ^ M. Ebling, M. Di Loreto, M. Presley, F. Wieland, et D. Jefferson, Un modelo de búsqueda de hormigas implementado en el sistema operativo Time Warp , Actas de la multiconferencia SCS sobre simulación distribuida, 1989
- ^ Dorigo M., V. Maniezzo et A. Colorni, La retroalimentación positiva como estrategia de búsqueda , técnica de rapport numéro 91-016, Dip. Elettronica, Politecnico di Milano, Italia, 1991
- ^ Appleby, S. & Steward, S. Agentes de software móviles para control en redes de telecomunicaciones, BT Technol. J., 12 (2): 104-113, abril de 1994
- ^ LM Gambardella y M. Dorigo, "Ant-Q: un enfoque de aprendizaje por refuerzo para el problema del viajante de comercio", Actas de ML-95, Duodécima Conferencia Internacional sobre Aprendizaje Automático, A. Prieditis y S. Russell (Eds.), Morgan Kaufmann, págs. 252–260, 1995
- ^ LM Gambardella y M. Dorigo, "Solución de TSP simétricos y asimétricos por colonias de hormigas", Actas de la Conferencia IEEE sobre Computación evolutiva, ICEC96, Nagoya, Japón, 20-22 de mayo, págs. 622-627, 1996;
- ^ R. Schoonderwoerd, O. Holland, J. Bruten et L. Rothkrantz, Equilibrio de carga basado en Ant en redes de telecomunicaciones , Adaptive Behavior, volumen 5, numéro 2, páginas 169-207, 1997
- ^ M. Dorigo, ANTS '98, De colonias de hormigas a hormigas artificiales: Primer taller internacional sobre optimización de colonias de hormigas, ANTS 98 , Bruxelles, Belgique, octubre de 1998.
- ^ T. Stützle, Estrategias de paralelización para la optimización de colonias de hormigas , Actas de PPSN-V, Quinta Conferencia Internacional sobre la resolución de problemas paralelos de la naturaleza, Springer-Verlag, volumen 1498, páginas 722-731, 1998.
- ^ É. Bonabeau, M. Dorigo et G. Theraulaz, Inteligencia de enjambre , Oxford University Press, 1999.
- ^ M. Dorigo, G. Di Caro et T. Stützle, Número especial sobre "Algoritmos de hormigas " , Future Generation Computer Systems, volumen 16, numéro 8, 2000
- ^ WJ Gutjahr, Un sistema de hormigas basado en gráficos y su convergencia , Future Generation Computer Systems, volumen 16, páginas 873-888, 2000.
- ^ S. Iredi, D. Merkle et M. Middendorf, Optimización de bi-criterio con algoritmos de hormigas multicolonias, Optimización evolutiva de criterios múltiples, Primera Conferencia Internacional (EMO'01), Zurich, Springer Verlag, páginas 359-372, 2001.
- ^ L. Bianchi, LM Gambardella et M.Dorigo, Un enfoque de optimización de colonias de hormigas para el problema del viajante viajante probabilístico , PPSN-VII, Séptima Conferencia Internacional sobre Resolución de Problemas Paralelos desde la Naturaleza, Lecture Notes in Computer Science, Springer Verlag, Berlín, Alemania , 2002.
- ^ M. Dorigo y T. Stützle, Optimización de colonias de hormigas , MIT Press, 2004.
- ^ B. Prabhakar, KN Dektar, DM Gordon, "La regulación de la actividad de forrajeo de colonias de hormigas sin información espacial", PLOS Computational Biology, 2012. URL: http://www.ploscompbiol.org/article/info%3Adoi%2F10. 1371% 2Fjournal.pcbi.1002670
- ^ Mladineo, Marko; Veza, Ivica; Gjeldum, Nikola (2017). "Resolución de problemas de selección de socios en redes de producción ciberfísicas mediante el algoritmo HUMANT". Revista Internacional de Investigación en Producción . 55 (9): 2506–2521. doi : 10.1080 / 00207543.2016.1234084 . S2CID 114390939 .
Publicaciones (seleccionadas)
- M. Dorigo , 1992. Optimización, aprendizaje y algoritmos naturales , tesis doctoral, Politecnico di Milano, Italia.
- M. Dorigo, V. Maniezzo & A. Colorni, 1996. " Ant System: Optimization by a Colony of Cooperating Agents ", IEEE Transactions on Systems, Man, and Cybernetics – Part B, 26 (1): 29–41.
- M. Dorigo & LM Gambardella , 1997. " Sistema de colonia de hormigas: un enfoque de aprendizaje cooperativo para el problema del vendedor ambulante ". Transacciones IEEE sobre computación evolutiva, 1 (1): 53–66.
- M. Dorigo, G. Di Caro y LM Gambardella, 1999. " Algoritmos de hormigas para optimización discreta ". Vida artificial, 5 (2): 137-172.
- E. Bonabeau, M. Dorigo y G. Theraulaz, 1999. Swarm Intelligence: From Natural to Artificial Systems , Oxford University Press. ISBN 0-19-513159-2
- M. Dorigo y T. Stützle, 2004. Optimización de colonias de hormigas , MIT Press. ISBN 0-262-04219-3
- M. Dorigo, 2007. "Optimización de colonias de hormigas" . Scholarpedia.
- C. Blum, 2005 " Optimización de colonias de hormigas: Introducción y tendencias recientes ". Reseñas de física de la vida, 2: 353-373
- M. Dorigo, M. Birattari & T. Stützle, 2006 Optimización de colonias de hormigas: hormigas artificiales como técnica de inteligencia computacional . TR / IRIDIA / 2006-023
- Mohd Murtadha Mohamad, "Planificación del movimiento de robots articulados mediante la estrategia de hormigas forrajeras", Journal of Information Technology - Special Issues in Artificial Intelligence, Vol.20, No. 4 pp. 163-181, diciembre de 2008, ISSN 0128-3790 .
- N. Monmarché, F. Guinand & P. Siarry (eds), "Artificial Ants", agosto de 2010 Tapa dura 576 págs. ISBN 978-1-84821-194-0 .
- A. Kazharov, V. Kureichik, 2010. " Algoritmos de optimización de colonias de hormigas para resolver problemas de transporte ", Journal of Computer and Systems Sciences International, vol. 49. No. 1. págs. 30–43.
- CM. Pintea, 2014, Avances en computación bioinspirada para el problema de optimización combinatoria , Springer ISBN 978-3-642-40178-7
- K. Saleem, N. Fisal, MA Baharudin, AA Ahmed, S. Hafizah y S. Kamilah, "Protocolo de enrutamiento auto optimizado inspirado en la colonia de hormigas basado en la arquitectura de capas cruzadas para redes de sensores inalámbricos", WSEAS Trans. Commun., Vol. 9, no. 10, págs. 669–678, 2010. ISBN 978-960-474-200-4
- K. Saleem y N. Fisal, "Algoritmo mejorado de colonia de hormigas para enrutamiento asegurado de datos auto optimizados en redes de sensores inalámbricos", Networks (ICON) 2012, 18ª Conferencia Internacional IEEE, págs. ISBN 978-1-4673-4523-1
- Abolmaali S, Roodposhti FR. Optimización de la cartera mediante el método de colonia de hormigas: estudio de caso sobre la bolsa de valores de Teherán. Diario de contabilidad. 2018 marzo; 8 (1).
enlaces externos
- Página de optimización de colonias de hormigas de Scholarpedia
- Página de inicio de optimización de colonia de hormigas
- "Optimización de colonias de hormigas": comunidad científica y de investigación rusa
- AntSim: simulación de algoritmos de colonias de hormigas
- MIDACO-Solver Software de optimización de propósito general basado en la optimización de colonias de hormigas (Matlab, Excel, VBA, C / C ++, R, C #, Java, Fortran y Python)
- Universidad de Kaiserslautern, Alemania, AG Wehn: Applet de optimización de colonia de hormigas Visualización de viajante de ventas resuelto por el sistema de hormigas con numerosas opciones y parámetros (Java Applet)
- Simulador de granja de hormigas
- Simulación de algoritmo Ant (subprograma Java)
- Marco del sistema Java Ant Colony