METAHEURISTICAS
GUILLERMO JIMENEZ LOZANO
UNIVERSIDAD NACIONAL DE COLOMBIA SEDE MANIZALES,
FACULTAD DE ADMINISTRACION,
Carrera 27 No 64 – 60, MANIZALES, CALDAS, COLOMBIA
gjimenezl@[Link]
GTA GAIA (Grupo de Ambientes Inteligentes Adaptativos)
EDUARDO ANTONIO CANO PLATA
UNIVERSIDAD NACIONAL DE COLOMBIA SEDE MANIZALES,
FACULTAD DE INGENIERIA Y ARQUITECTURA,
Carrera 27 No 64 – 60, MANIZALES, CALDAS, COLOMBIA
eacanopl@[Link]
GTA GREDyP (Grupo de Redes y Distribución de Potencia)
ABSTRACT
In Operations Research, some experts have been developed many tools for application in practical problems. One of
those is the Metaheuristics methodology, which consist of approximations used to solve combinatorial
optimization problems, where is not feasible to apply traditional methods.
In real life there are complex optimization problems to solve in the most appropriated way. In recent years it has worked
hard on this area in order to find efficient algorithms, which are called the Metaheuristics.
This methodology focuses on different processes, among which we can mention: problems without algorithm associated
to its solution, algorithms very complex to solve the problem; algorithms that consume a lot of machine resources, as
well in other cases there is uncertainty about its real solution.
The most common methods of solving the problems of Metaheuristics are; Simulated Annealing, Tabu Search, GRASP,
Genetic Algorithms, Memetic Algorithms, Artificial Neural Networks, Ant Colony and Particle Swarm, among others.
The present work shows some alternative solutions for optimization problems to which it is not feasible to
apply traditional algorithms. It should be noted that this work explains those most common Metaheuristics procedures.
Key words: Metaheuristics, Optimization, Operations Research, Algorithms.
RESUMEN
Las personas que trabajan en Investigación de Operaciones han desarrollado diversas herramientas para su aplicación en
problemas prácticos. Uno de ellos bastante empleado en la actualidad corresponde a las Metaheurísticas, las cuales son
aproximaciones que se utilizan para solucionar problemas de Optimización Combinatoria, a los que no es factible
aplicarles los métodos tradicionales.
En la vida real se encuentran problemas complejos de optimización a los cuales se pretende dar solución de la manera
más apropiada. En los últimos años se ha trabajado bastante en este campo con la finalidad de hallar algoritmos
eficientes, a los cuales se denomina Metaheurísticos.
Tal metodología aborda diferentes procesos, entre los que se pueden citar: problemas sin algoritmo asociado a su
solución; algoritmos demasiado complejos para resolver el problema planteado; algoritmos que al ser implementados
consumen muchos recursos de máquina; además en otros casos no se tiene certeza acerca de su verdadera solución.
Los métodos de solución más usuales en los problemas de Metaheurísticas son los siguientes: Recocido Simulado,
Búsqueda Tabú, GRASP, Algoritmos Genéticos, Algoritmos Meméticos, Redes Neuronales Artificiales, Colonias de
Hormigas y Partículas Swarm, entre otros.
Con el presente trabajo se pretende mostrar algunas alternativas de solución para problemas de optimización a los cuales
no es factible aplicarles los algoritmos tradicionales. Es de advertir que se presentan aquellos procedimientos
Metaheurísticos más usuales.
Palabras clave: Metaheurísticas, Optimización, Investigación de Operaciones, Algoritmos.
1 Introducción
Los procedimientos Metaheurísticos son una clase de métodos aproximados que están diseñados para resolver problemas
difíciles de optimización combinatoria, en los que los heurísticos clásicos no son ni efectivos ni eficientes. Los
Metaheurísticos proporcionan un marco general para crear nuevos algoritmos híbridos combinando diferentes conceptos
derivados de: inteligencia artificial, evolución biológica y mecanismos estadísticos.
Los procedimientos Metaheurísticos más empleados son: Recocido Simulado, Búsqueda Tabú, GRASP, Redes
Neuronales Artificiales y Algoritmos Genéticos. En la búsqueda de la mejora de las soluciones a los problemas de tipo
combinatorio en el último tiempo se han empleado técnicas tales como Colonia de Hormigas y Partículas Swarm, entre
otras.
El trabajo presenta inicialmente el Recocido Simulado, continúa con la Búsqueda Tabú, sigue con las Redes Neuronales
Artificiales, luego se presentan los Algoritmos Genéticos, después se muestran los Algoritmos Meméticos, a
continuación se habla de las Colonias de Hormigas y finalmente Partículas Swarm.
2 Estado del Arte
2.1 Recocido simulado
El resolver un problema combinatorio se resume a encontrar la ''mejor'' / ''óptima'' solución dentro de un conjunto finito
o contablemente infinito de alternativas. Asumimos que la calidad de la solución es cuantificable y comparable con
cualquier otra solución y que las soluciones son finitas.
Una instancia de un problema combinatorio se puede formalizar por un par (S, f) donde el espacio solución S denota el
conjunto finito de todas las posibles soluciones y f denota la función de costo: f : S → . Lo que se trata (en
minimización) es encontrar una solución iopt ∈ S tal que f (iopt) ≤ f (i) para toda i ∈ S. Los algoritmos de búsqueda
local constituyen una clase de algoritmos aproximados basados en la exploración de vecinos. Estos presuponen que
existe una función de costo y una estructura de vecindad. La estructura de vecindad define para cada i ∈ S un conjunto
Si ⊂ S que son cercanos a i en algún sentido. Se asume que j ∈ Si ⇔ i ∈ Sj. El mecanismo de generación se define
como la forma de seleccionar una solución j en la vecindad Si de la solución i. Los algoritmos de búsqueda local
normalmente iteran partiendo de una solución aleatoria, generando un vecino que sea mejor hasta que se llegue a una
solución que no tiene mejores vecinos.
2.2 BUSQUEDA TABU
La Búsqueda Tabú, es una estrategia para resolver problemas de optimización combinatoria. Este algoritmo combina
búsqueda local con una heurística para evitar parar en mínimos locales y entrar en ciclos. La idea básica de búsqueda
tabú es continuar cuando se llega a un mínimo local al permitir movimientos que no mejoran la solución. Para no
regresar a soluciones pasadas y ciclarse, usa una memoria temporal, llamada lista tabú, que guarda la historia reciente de
la búsqueda.
Elementos claves en búsqueda tabú:
• Restricciones Tabú: Restringir la búsqueda al clasificar ciertos movimientos como prohibidos (tabú), para
evitar caer en soluciones recientemente generadas.
• Criterio de aspiración: Liberar la búsqueda por medio de una función de memoria a corto plazo (olvido
estratégico).
Se crea un subconjunto T ⊆ S usando información histórica extendiéndola t iteraciones en el pasado.
La membresía en T puede ser por medio de condiciones a cumplir (no necesariamente un índice de soluciones pasadas).
2
2.3 GRASP (GREEDY RANDOMIZED ADAPTIVE SEARCH)
GRASP es un método de multi-inicio o iterativo en donde cada iteración tiene dos fases: (i) construcción y (ii) búsqueda
local. En la fase de construcción se encuentra una solución factible cuya vecindad es investigada hasta llegar a un
mínimo local. La mejor solución es guardada.
La selección del elemento a incorporar se determina mediante una evaluación greedy de todos los elementos candidatos
(incremento en la función de costo al aumentar algún elemento). Esta evaluación crea una lista de candidatos restringida
formada por los mejores elementos (los que incrementen menos la función de costo). Esta lista puede estar restringida en
cuanto a la cantidad de elementos (cardinalidad) o en cuanto a la calidad de los elementos.
El elemento que se incorpora en la construcción de la solución, se selecciona aleatoriamente dentro de la lista de
candidatos restringida. Una vez incorporado se actualiza la lista de candidatos y se reevalúan los costos incrementales.
El algoritmo de búsqueda local puede ser con el mejor candidato o el primer candidato que mejore la solución actual.
También se han hecho extensiones para no seleccionar el elemento de la lista de candidatos restringida aleatoriamente,
sino siguiendo ciertas preferencias de acuerdo al lugar que ocupan.
2.4 Redes neuronales artificiales
Red Neuronal Biológica
Una red neuronal biológica es una estructura que permite desarrollar un elemento sintético para verificar las hipótesis
que conciernen a los sistemas biológicos; las neuronas y las conexiones entre ellas constituyen la clave para el
procesamiento de la información. Se estima que el cerebro humano contiene más de cien mil millones de neuronas y
sinapsis en el sistema nervioso humano. Se debe tener en cuenta que aunque el tiempo de conmutación de la neurona es
de unos pocos milisegundos, es casi un millón de veces menor que los actuales elementos de los computadores, aquellas
tienen una conectividad miles de veces superior que los actuales supercomputadores.
Red Neuronal Artificial
3
Una red neuronal artificial o neurocomputadora o red conexionista o procesador paralelo distribuido entre otros es una
simplificación de una red neuronal biológica y corresponde a sistemas constituidos intencionalmente para hacer uso de
algunos principios organizacionales que se parecen a los del cuerpo humano.
Una neurona artificial puede representarse en forma gráfica como una entrada (dendritas), un bloque llamado elemento
de proceso (neurona) y una salida (axón). Es un sistema compuesto por un gran número de elementos básicos, agrupados
en capas y que se encuentran altamente interconectados; esta estructura posee varias entradas y salidas, las cuales serán
entrenadas para reaccionar, de una manera deseada, a los estímulos de entrada. Estos sistemas emulan, de una cierta
manera, al cerebro humano. Requieren aprender a comportarse y alguien debe encargarse de enseñarles o entrenarles,
teniendo como base un conocimiento previo del entorno del problema.
Esta tecnología es bastante útil en problemas muy especiales. En línea general, estos usos se dan cuando se tienen
muchos datos históricos disponibles y nadie sabe exactamente la estructura y los parámetros que pueden modelar tales
datos. Es decir las cantidades grandes de datos y de alta incertidumbre, con respecto a la manera como los datos se
producen. Los ejemplos son valores comunes (pronóstico), riesgo de préstamo, tiempo local, reconocimiento de patrones
y minería de datos. Pueden ser puestos en ejecución de varias maneras, pueden ser hechos por hardware usando
transistores del efecto de campo o los amplificadores operacionales, pero la mayoría de las redes neuronales se
construyen con software. Hay herramientas muy buenas y flexibles disponibles, las cuales pueden emular muchas clases
de neuronas, de conexiones sinápticas, y de estructuras.
Redes Neuronales Biológicas Redes Neuronales Artificiales
Neuronas Unidades de proceso
Conexiones sinápticas Conexiones ponderadas
Efectividad de las sinapsis Peso de las conexiones
Efecto excitatorio o inhibitorio de una conexión Signo del peso de una conexión
Efecto combinado de las sinapsis Función de propagación o de red
Activación (tasa de disparo) Función de activación (salida)
Atendiendo al tipo de entrenamiento, una posible taxonomía de las redes neuronales artificiales es:
Redes Neuronales
FIJO NO SUPERVISADO SUPERVISADO
Red de Hamming Mapa de características Basadas en decisión
Red de Hopfield Aprendizaje competitivo Perceptrón
Adaline (LMS)
Perceptrón Multicapa
Modelos Temporales Dinámicos
Modelos Ocultos de Markov
Elemento básico - neurona artificial: Es básicamente una unidad de proceso conectada con otras unidades a través de
conexiones sinápticas. La estructura de interconexión de elementos básicos. Un ejemplo es el perceptrón de múltiples
capas entrenado con el algoritmo de la “propagación del error hacia atrás”.
Es una red compuesta por varias capas de neuronas basadas en funciones exponenciales y las conexiones sinápticas se
determinan para disminuir un error cuadrático. Otro ejemplo es el mapa de auto-organización de Kohonen, en el cual
solamente la salida se sabe. Una neurona artificial es un elemento con las entradas, la salida y la memoria que se pueden
poner en ejecución con software o hardware. Tiene entradas (i) se cargan y se agregan para compararlas .con un umbral
(t).
2.5 Algoritmos genéticos
4
John Holland desde pequeño, se preguntaba cómo logra la SNNS crear seres cada vez más perfectos. Lo curioso era que
todo se lleva a cabo a base de interacciones locales entre individuos y entre estos y lo que les rodea. No sabía la
respuesta, pero tenía una cierta idea de como encontarrla: tratando de hacer pequeños modelos de la naturaleza, que
tuvieran alguna de sus características y viendo como funcionaban, para luego extrapolar sus conclusiones a la totalidad.
De hecho, ya de pequeño hacía simulaciones de batallas célebres con todos sus elementos: copiaba mapas y los cubría
luego de pequeños ejércitos que se enfrentaban entre sí.
Los algoritmos genéticos son métodos sistemáticos para la resolución de problemas de búsqueda y optimización que
aplican a estos los mismos métodos de la evolución biológica: selección basada en la población, reproducción sexual y
mutación. Los algoritmos genéticos son métodos de optimización, que tratan de resolver el mismo conjunto de
problemas que se ha contemplado anteriormente, es decir, hallar (xi,...,xn) tales que F(xi,...,xn) sea máximo. En un
algoritmo genético, tras parametrizar el problema en una serie de variables, (xi,...,xn) se codifican en un cromosoma.
Todas los operadores utilizados por un algoritmo genético se aplicarán sobre estos cromosomas, o sobre poblaciones de
ellos. En el algoritmo genético va implícito el método para resolver el problema; son solo parámetros de tal método los
que están codificados, a diferencia de otros algoritmos evolutivos como la programación genética. Hay que tener en
cuenta que un algoritmo genético es independiente del problema, lo cual lo hace un algoritmo robusto, por ser útil para
cualquier problema, pero a la vez débil, pues no está especializado en ninguno.
Las soluciones codificadas en un cromosoma compiten para ver cuál constituye la mejor solución (aunque no
necesariamente la mejor de todas las soluciones posibles). El ambiente, constituido por las otras soluciones, ejercerá una
presión selectiva sobre la población, de forma que sólo los mejor adaptados (aquellos que resuelvan mejor el problema)
sobrevivan o leguen su material genético a las siguientes generaciones, igual que en la evolución de las especies. La
diversidad genética se introduce mediante mutaciones y reproducción sexual. En la naturaleza lo único que hay que
optimizar es la supervivencia y eso significa a su vez maximizar diversos factores y minimizar otros. Un algoritmo
genético, sin embargo, se usará habitualmente para optimizar sólo una función, no diversas funciones relacionadas entre
sí simultáneamente. La optimización que busca diferentes objetivos simultáneamente, denominada multimodal o
multiobjetivo, también se suele abordar con un algoritmo genético especializado. Por lo tanto, un algoritmo genético
consiste en lo siguiente: hallar de qué parámetros depende el problema, codificarlos en un cromosoma y aplicar los
métodos de la evolución: selección y reproducción sexual con intercambio de información y alteraciones que generan
diversidad.
2.6 Algoritmos miméticos
Son procedimientos basados en población y se han mostrado como técnicas más rápidas que los Algoritmos Genéticos
para algunos tipos de problemas. Básicamente combinan procedimientos de Búsqueda Local con operadores de cruce o
de mutación, por lo que algunos investigadores los han visto como Algoritmos Genéticos Híbridos o Algoritmos
Genéticos Paralelos o Métodos de Búsqueda Local Genética. El método, descrito originalmente en el trabajo de Moscato
(1989), está ganando amplia aceptación en particular en los conocidos problemas de Optimización Combinatoria, donde
grandes problemas se han solucionado en forma óptima y donde otros metaheurísticos han fallado. Un reciente tutorial
sobre meméticos puede encontrarse en Moscato y Cotta (2001).
2.7 Colonias de hormigas
Estableciendo una observación a la naturaleza con respecto al comportamiento de las hormigas, donde estas se
comunican por medio de una sustancia química llamada feromona, para encontrar el mejor camino entre el nido y el
alimento, en el último tiempo se ha empezado a estudiar el Ant Colony System (ACS), es decir, los sistemas de colonias
de hormigas, basados en el comportamiento de las hormigas reales, de acuerdo a su conducta colectiva. Lo que se
pretende es trabajar en el computador con métodos de simulación para encontrar el camino más corto entre sus nidos y
las fuentes de su alimentación, lo cual se guarda en la denominada matriz de feromonas. Las principales aplicaciones del
algoritmo de la Colonia de Hormigas corresponde al problema del transporte y al problema del agente viajero, entre
otros.
2.8 Partículas swarm
Este método de optimización se basa en el comportamiento grupal de algunos animales, tales como una bandada de
pájaros, un cardumen de peces o un enjambre de abejas. Este algoritmo de solución se genera a partir de dicha población
y la manera como se comportan frente a determinadas situaciones, o sea, como enfrentan la dificultad. Este algoritmo
5
conocido como Particles Swarm (PS), es decir, nube de partículas, trabaja de la siguiente manera: cada uno de estos
grupos de animales busca comida y no sabe donde está, ninguno de los individuos sabe donde está la comida, pero
conocen la distancia a la misma; la alternativa más eficiente es seguir al individuo que se encuentra más cerca de la
comida. Algunas aplicaciones del algoritmo de la nube de partículas corresponden a diversos problemas
multidimensionales, identificación de procesos, optimización de funciones numéricas, entrenamiento de redes
neuronales, entre otros.
3 APLICACIONES
Algunas de las aplicaciones principales en las que se utilizan las Metaheurísticas son: modelos logísticos en industrias de
automóviles, transporte escolar, enrutamiento, localización, optimización en grafos, asignación, horario, programación y
manufactura, transporte, sistemas de potencia, telecomunicaciones, diseño de redes, dibujo de grafos y mapas, biología,
problemas de corte bidimensional, secuenciación de proyectos con recursos parcialmente renovables, planificación
logística, planificación de la producción en una empresa de madera enchapada, entre otras.
4 CONCLUSIONES
Como se puede observar las aplicaciones de las Metaheurístcas son bastante amplias, por lo que se podría pensar en
problemas que son de bastante uso cotidiano, tanto en los sectores industriales, comerciales y de servicios, así como en
los entornos académicos, para la programación de horarios en instituciones de educación superior, por ejemplo. Es de
advertir que en muchos de estos casos se vuelven de mucho interés para las Metaheurísticas por el tamaño del problema
a tratar o por la cantidad de variables que en él intervienen. Debido a lo anterior queda un camino despejado para las
aplicaciones.
AGRADECIMIENTOS
Queremos expresar nuestros más sinceros agradecimientos a la Universidad Nacional de Colombia Sede Manizales, a las
Facultades de Administración y de Ingeniería y Arquitectura, respectivamente.
REFERENCIAS
[1] J. F. Alegre M. Metaheurísticos: Aplicaciones a Modelos Logísticos en la Industria del Automóvil. Universidad
de Burgos. España. 2004.
[2] E. Crespo, R. Martí. J. Pacheco. Procedimientos Metaheurísticos en Economía y Empresa. Tirant lo Blanch.
Valencia. Espanña. 2007.
[3] C. R. Delgado S. Nuevas Técnicas Metaheurísticas. Universidad de Burgos. España. 2002.
[4] A. Díaz, F. Glover, H. M. Ghaziri, J. L. González, M. Laguna, P. Moscato, F. T. Tseng. Optimización
Heurística y Redes Neuronales. Editorial Paraninfo. España. 1996.
[5] A. Duarte M., J. J. Pantrigo F., M. Gallego C. Metaheurísticas. Universidad Rey Juan Carlos. Madrid. España.
2007.
[6] F. S. Hillier, G. J. Lieberman Introducción a la Investigación de Operaciones. Mc Graw-Hill. México. 2010.
[7] G. Jiménez L. Optimización. Universidad Nacional de Colombia Sede Manizales. Departamento de Informática
y Computación. Manizales. Colombia. 2009.
[8] I. H. Osman, J. P. Kelly. Meta–Heuristics: Theory & Applications. Kluwer Academic Publishers. 1996.
[9] M. G. C. Resende. A Probabilistic Heuristic for a Computationally Difficult Set Covering Problem. Operations
Research Letters. Vol. 8. E. U. A. 1989.
[10] J. Kennedy, R. Eberhart. Particle Swarm Optimization. New York. 1995.
6
7
