Iconter
Páginas: 13 (3016 palabras)
Publicado: 22 de junio de 2012
Optimización por Colonia de Hormigas (ACO) (Noviembre 2009)
Nataly Medina Rodríguez, CITEDI-IPN, Métodos de Optimización
Resumen—El siguiente documento presenta un análisis introductorio relacionado al tema de optimización por colonia de hormigas, mejor conocido por sus siglas en inglés ACO. Debido a que muchos problemas de optimización en configuraciones geométricas son NP-duros, el algoritmoque se propone presenta una solución aproximada, utilizando una técnica metaheurística.
Además, se presentará un problema de aplicación al algoritmo denominado como el “Problema del Agente Viajero” o TSP utilizando MATLAB.
Índice de Términos— ACO, S-ACO, Metaheurística, TSP
INTRODUCCIÓN
U
LA metaheurística es un proceso de generación iterativo que guía la búsqueda de solucionescombinando diferentes conceptos de diversos campos, como inteligencia artificial, evolución biológica, inteligencia colectiva, entre otros.
Una metaheurística es entonces, un algoritmo general el cual puede ser aplicado a diferentes problemas de optimización con pequeñas modificaciones para adaptarlos al problema en específico.
Ejemplos de metaheurísticas son el Temple Simulado, Búsqueda Tabú, BúsquedaLocal Iterativa, Cómputo Evolutivo, y Colonia de Hormigas.
El siguiente trabajo, presenta este último algoritmo basado en inteligencia colectiva (swarm intelligence).
Optimización basada en Colonias de Hormigas
La Optimización basada en Colonia de Hormigas (Ant Colony Optimization, ACO) es una metaheurística inspirada en el comportamiento que siguen las hormigas para encontrar los caminosmás corotos entre las fuentes de comida y el hormiguero, surgida a partir del trabajo inicial de Dorigo, Maniezzo y Colorni sobre Sistema de Hormigas (Ant System) [1].
Los algoritmos ACO son aptos para resolver problemas de optimización combinatoria. Se basan en una colonia de hormigas artificiales, representadas por agentes computacionales simples, que trabajan de manera cooperativa y secomunican mediante rastros de feromona artificiales.
Son esencialmente algoritmos constructivos: en cada iteración del algoritmo, cada hormiga construye una solución al problema, recorriendo un grafo de construcción. Cada arista, (p,q) del grafo representa los posibles pasos que la hormiga puede dar y tiene asociadas dos informaciones que guían el movimiento de la hormiga:
* Informaciónheurística, que mide la preferencia heurística, ηpq, de moverse desde el nodo p hasta el nodo q, o sea, recorrer la arista. Las hormigas no modifican esta información durante la ejecución del algoritmo.
* Información de los rastros de feromona artificiales, miden la “deseabilidad aprendida” del movimiento, τpq, de p a q, imitando a la feromona real depositada por las hormigas reales. Esta informaciónse modifica durante la ejecución del algoritmo dependiendo de las soluciones encontradas por las hormigas.
Una vez que cada hormiga ha generado una solución se evalúa la misma y se puede depositar una cantidad de feromona en función de la calidad de su solución.
El modo de operación genérico de un algoritmo ACO incluye dos procedimientos adicionales, la evaporación de los rastros deferomona y las acciones opcionales (daemon actions). La evaporación del rastro de feromona la lleva a cabo el entorno y se usa como un mecanismo que evita el estancamiento en la búsqueda y permite que las hormigas busquen y exploren nuevas regiones de espacio. Las acciones opcionales llamadas en inglés daemon actions, no tienen correspondencia con el comportamiento de las hormigas reales, paraimplementar tareas desde una perspectiva global.
Algunos ejemplos de estas acciones son:
* Observar la calidad de todas las soluciones generadas y depositar una nueva cantidad de feromona adicional sólo en las aristas asociadas a algunas soluciones
* Aplicar un procedimiento de búsqueda local a las soluciones generadas por las hormigas antes de actualizar los rastros de feromona.
El...
Nataly Medina Rodríguez, CITEDI-IPN, Métodos de Optimización
Resumen—El siguiente documento presenta un análisis introductorio relacionado al tema de optimización por colonia de hormigas, mejor conocido por sus siglas en inglés ACO. Debido a que muchos problemas de optimización en configuraciones geométricas son NP-duros, el algoritmoque se propone presenta una solución aproximada, utilizando una técnica metaheurística.
Además, se presentará un problema de aplicación al algoritmo denominado como el “Problema del Agente Viajero” o TSP utilizando MATLAB.
Índice de Términos— ACO, S-ACO, Metaheurística, TSP
INTRODUCCIÓN
U
LA metaheurística es un proceso de generación iterativo que guía la búsqueda de solucionescombinando diferentes conceptos de diversos campos, como inteligencia artificial, evolución biológica, inteligencia colectiva, entre otros.
Una metaheurística es entonces, un algoritmo general el cual puede ser aplicado a diferentes problemas de optimización con pequeñas modificaciones para adaptarlos al problema en específico.
Ejemplos de metaheurísticas son el Temple Simulado, Búsqueda Tabú, BúsquedaLocal Iterativa, Cómputo Evolutivo, y Colonia de Hormigas.
El siguiente trabajo, presenta este último algoritmo basado en inteligencia colectiva (swarm intelligence).
Optimización basada en Colonias de Hormigas
La Optimización basada en Colonia de Hormigas (Ant Colony Optimization, ACO) es una metaheurística inspirada en el comportamiento que siguen las hormigas para encontrar los caminosmás corotos entre las fuentes de comida y el hormiguero, surgida a partir del trabajo inicial de Dorigo, Maniezzo y Colorni sobre Sistema de Hormigas (Ant System) [1].
Los algoritmos ACO son aptos para resolver problemas de optimización combinatoria. Se basan en una colonia de hormigas artificiales, representadas por agentes computacionales simples, que trabajan de manera cooperativa y secomunican mediante rastros de feromona artificiales.
Son esencialmente algoritmos constructivos: en cada iteración del algoritmo, cada hormiga construye una solución al problema, recorriendo un grafo de construcción. Cada arista, (p,q) del grafo representa los posibles pasos que la hormiga puede dar y tiene asociadas dos informaciones que guían el movimiento de la hormiga:
* Informaciónheurística, que mide la preferencia heurística, ηpq, de moverse desde el nodo p hasta el nodo q, o sea, recorrer la arista. Las hormigas no modifican esta información durante la ejecución del algoritmo.
* Información de los rastros de feromona artificiales, miden la “deseabilidad aprendida” del movimiento, τpq, de p a q, imitando a la feromona real depositada por las hormigas reales. Esta informaciónse modifica durante la ejecución del algoritmo dependiendo de las soluciones encontradas por las hormigas.
Una vez que cada hormiga ha generado una solución se evalúa la misma y se puede depositar una cantidad de feromona en función de la calidad de su solución.
El modo de operación genérico de un algoritmo ACO incluye dos procedimientos adicionales, la evaporación de los rastros deferomona y las acciones opcionales (daemon actions). La evaporación del rastro de feromona la lleva a cabo el entorno y se usa como un mecanismo que evita el estancamiento en la búsqueda y permite que las hormigas busquen y exploren nuevas regiones de espacio. Las acciones opcionales llamadas en inglés daemon actions, no tienen correspondencia con el comportamiento de las hormigas reales, paraimplementar tareas desde una perspectiva global.
Algunos ejemplos de estas acciones son:
* Observar la calidad de todas las soluciones generadas y depositar una nueva cantidad de feromona adicional sólo en las aristas asociadas a algunas soluciones
* Aplicar un procedimiento de búsqueda local a las soluciones generadas por las hormigas antes de actualizar los rastros de feromona.
El...
Leer documento completo
Regístrate para leer el documento completo.