Algoritmos metahuristicos

La Metaheurística de Optimización Basada en
Colonias de Hormigas: Modelos y Nuevos Enfoques*
Sergio Alonso, Oscar Cordón, Iñaki Fernández de Viana, Francisco Herrera
Departamento de Ciencias de la Computación e Inteligencia Artificial, E.T.S. Ingeniería
Informática, C/ Periodista Daniel Saucedo Aranda s/n, 18071 Granada (España)
zerjio@zerjio.com, ocordon@decsai.ugr.es, ijfviana@ugr.es,herrera@decsai.ugr.es

Abstract. En este trabajo se ofrece una perspectiva general de la metaheurística
de Optimización Basada en Colonias de Hormigas, describiendo varios de los
modelos algorítmicos existentes, y poniendo un especial énfasis en el Sistema
de la Mejor-Peor Hormiga y en algunas de las nuevas tendencias existentes en
el campo como, por ejemplo, la Paralelización de Colonias deHormigas.
Palabras Clave. Optimización Basada en Colonias de Hormigas, Sistema de la
Mejor-Peor Hormiga, Paralelización de Colonias de Hormigas, Viajante de
Comercio

1 Introducción
Existen problemas de optimización combinatoria complejos en diversos campos
como la economía, el comercio, la ingeniería, la industria o la medicina. Sin embargo,
a menudo estos problemas son muy difíciles deresolver en la práctica. El estudio de
esta dificultad inherente para resolver dichos problemas tiene cabida en el campo de
la teoría de las Ciencias de la Computación, ya que muchos de ellos pertenecen a la
clase de problemas NP-duros, lo que significa que no existe un algoritmo conocido
que los resuelva en un tiempo polinomial [47].
Día tras día, siguen apareciendo nuevos problemas de estetipo, lo que ha dado
lugar a que se hayan realizado muchas propuestas de algoritmos para tratar de
solucionarlos. Las técnicas existentes se pueden clasificar básicamente en algoritmos
exactos o aproximados. Los algoritmos exactos intentan encontrar una solución
óptima y demostrar que la solución obtenida es de hecho la óptima global; estos
algoritmos incluyen técnicas como, por ejemplo: procesosde vuelta atrás
(backtracking), Ramificación y poda (
branch and bound), programación dinámica,
etc. [84, 13]. Debido a que los algoritmos exactos muestran un rendimiento pobre
para muchos problemas se han desarrollado múltiples tipos de algoritmos
aproximados que proporcionan soluciones de alta calidad para estos problemas

*

Trabajo realizado en el marco del proyecto “Mejora deMetaheurísticas mediante Hibridación
y sus Aplicaciones” de la Universidad de Granada.

combinatorios (aunque no necesariamente la óptima) en un tiempo computacional
breve.
Los algoritmos aproximados se pueden clasificar en dos tipos principales:
algoritmos constructivos y algoritmos de búsqueda local. Los primeros se basan en
generar soluciones desde cero añadiendo componentes a cada soluciónpaso a paso.
Un ejemplo bien conocido son las heurísticas de construcción voraz o heurísticas
greedy [13]. Su gran ventaja es la velocidad: normalmente son muy rápidas y,
además, a menudo devuelven soluciones razonablemente buenas. Sin embargo, no
puede garantizarse que dichas soluciones sean óptimas con respecto a pequeños
cambios a nivel local. En consecuencia, una mejora típica es refinarla solución
obtenida por la heurística voraz utilizando una búsqueda local. Los algoritmos de
búsqueda local intentan repetidamente mejorar la solución actual con movimientos a
soluciones vecinas (con la esperanza de que sean mejores). El caso más simple son los
algoritmos de mejora iterativos: si en el vecindario de la solución actual s se
encuentra una solución mejor s´, ésta reemplaza lasolución actual y se continua la
búsqueda a partir de s´; si no se encuentra una solución mejor en el vecindario, el
algoritmo termina en un óptimo local.
Desafortunadamente, los algoritmos de mejora iterativos pueden estancarse en
soluciones de baja calidad (óptimos locales muy lejanos al óptimo global). Para
permitir una mejora adicional en la calidad de las soluciones, la investigación en...