Optimización de colonia de hormigas (ant colony optimization o ACO) está inspirado en el rastro y seguimiento de feromonas realizado por las hormigas como medio de comunicación.
Los caminos de feromonas sirven como información distribuida que las hormigas usan en forma probabílistica para construir soluciones a un problema y que las hormigas adaptan para reflejar su experiencia.
ACO es una estrategia de construcción, donde la solución se forma probabilísticamente al ir añadiendo componentes de soluciones parciales considerando: (i) heurísticas para resolver el problema particular y (ii) trazas de feromona.
Para la representación de un problema se requiere definir: (i) un conjunto de componentes y (ii) estados definidos en términos de secuencias de componentes (transiciones entre estados).
ACO construye soluciones moviendose en un grafo de construcción, donde los vértices son componentes del problema y los arcos conecciones entre estos componentes.
Para construir una solución siguen cierta política dada por las restricciones del problema.
Los componentes y las conecciones pueden tener asociadas cierta cantidad de feromona e información heurística acerca del problema.
Al añadir un componente en una solución parcial, puede actualizar la cantidad de feromona (on-line step-by-step pheromone trail).
También al llegar a una solución completa, puede ver todos los pasos que se siguieron y también actualizar los niveles de feromona del camino (online delayed pheromone update).
Las hormigas se mueven concurrentemente e independientemente.
Además ACO incluye dos procedimientos adicionales: (1) evaporación (pheromone trail evaporation) y (2) demonios (daemon actions).
El proceso de evaporación define como decrecer la cantidad de feromona en el tiempo.
Acciones tipo demonio pueden usarse para acciones centrales/globales que no pueden lograrse con las hormigas individuales.
Los procedimientos generales se muestran en la tabla 10.1.
