Metaheurística
Una metaheurística es un método heurístico para resolver un tipo de problema computacional general, usando los parámetros dados por el usuario sobre unos procedimientos genéricos y abstractos de una manera que se espera eficiente. Normalmente, estos procedimientos son heurísticos. El nombre combina el prefijo griego "meta" ("más allá", aquí con el sentido de "nivel superior") y "heurístico" (de ευρισκειν, heuriskein, "encontrar").
Las metaheurísticas generalmente se aplican a problemas que no tienen un algoritmo o heurística específica que dé una solución satisfactoria; o bien cuando no es posible implementar ese método óptimo. La mayoría de las metaheurísticas tienen como objetivo los problemas de optimización combinatoria, pero por supuesto, se pueden aplicar a cualquier problema que se pueda reformular en términos heurísticos, por ejemplo en resolución de ecuaciones booleanas.
Las metaheurísticas no son la panacea y suelen ser menos eficientes que las heurísticas específicas, en varios órdenes de magnitud, en problemas que aceptan este tipo de heurísticas puras.
Conceptos generales y nomenclatura
El objetivo de la optimización combinatoria es encontrar un objeto matemático finito (por ejemplo, un vector de bits o permutación) que maximice (o minimice, dependiendo del problema) una función especificada por el usuario de la metaheurística. A estos objetos se les suele llamar estados, y al conjunto de todos los estados candidatos se le llama espacio de búsqueda. La naturaleza de los estados y del espacio de búsqueda son usualmente específicos del problema.
La función a optimizar se le llama función objetivo, y se da al usuario como un procedimiento caja-negra que evalúa el estado actual o la función. Dependiendo de la metaheurística, el usuario puede tener que dar otras funciones caja-negra que produzcan un nuevo estado, generan variantes del estado actual, elijan un estado entre varios, aporten valores máximos o mínimos para la función objetivo en un conjunto de estados, y en ese estilo.
Algunas metaheurísticas mantienen en cada instante de ejecución un único estado actual, y lo cambian en cada iteración por uno nuevo. Este paso básico se conoce como transición de estado, movimiento o actualización del estado. El movimiento es colina arriba o colina abajo dependiendo de si los valores que da la función objetivo se incrementa o se decrementa. El nuevo estado puede estar construido desde la nada por un generador de estados dado por el usuario. Alternativamente, el nuevo estado puede derivar del estado actual por un mutador proporcionado por el usuario; en este caso, el nuevo estado se conoce como vecino del estado actual. Generadores y mutadores son habitualmente procedimientos probabilísticos. El conjunto de todos los nuevos estados dados por el mutador es el vecindario del estado actual.
Metaheurísticas más sofisticadas mantienen, en vez de un único estado actual, un conjunto de varios estados candidato. Así, el paso básico añade o elimina estados de este conjunto. En este caso, los procedimientos dados por el usuario seleccionan estados para ser descartados, y generan nuevos estados a añadir. El último estado puede ser generado como combinación o cruce de dos o más estados del conjunto.
Una metaheurística puede guardar información del óptimo actual, escogiendo el estado óptimo entre todos los óptimos actuales obtenidos en varias etapas del algoritmo.
Dado que el número de candidatos puede ser muy grande, normalmente, las metaheurísticas están diseñadas de manera que puedan ser interrumpidas por un tiempo máximo especificado por el usuario. Si no se interrumpen, algunas metaheurísticas exactas examinaran todos los candidatos, y usarán métodos heurísticos solo para escoger el orden de la enumeración; de hecho, siempre devolverán un óptimo real, si el tiempo máximo es lo suficientemente grande. En cambio, otras metaheurísticas dan solo una garantía probabilística pobre de poder alcanzar el óptimo, de manera que cuando el tiempo máximo se aproxima a infinito, la probabilidad de examinar cada candidato tiende a 1.
Metaheurísticas comunes
Algunas metaheurísticas muy conocidas son:
- Aceptación por umbrales (Threshold Accepting)
- Algoritmos meméticos
- Algoritmos multiarranque
- Algoritmos basados en arrecifes de coral, CRO
- Algoritmos de enjambre
- Algoritmos genéticos
- Algoritmos voraces y Ascensión de colinas
- Ascensión de colinas con reinicialización aleatoria
- Búsqueda dispersa (Scatter Search)
- Búsqueda de Vecindad Variable (Variable Neighborhood Search)
- Búsqueda en entornos variados (Variable Neighborhood Search)
- Búsqueda local iterada (Iterated Local Search)
- Búsqueda local
- Búsqueda por difusión estocástica
- Búsqueda primero el mejor
- Búsqueda tabú
- GRASP
- Inteligencia de enjambre
- Meta-RaPS
- Optimización aleatoria
- Optimización de enjambre de partículas
- Optimización extrema
- Optimización basada en colonias de hormigas
- PeSOA: Penguins Search Optimization Algorithm
- Re-encadenamiento de trayectorias (Path Relinking)
- Recocido simulado (Simulated Annealing)
Hay un número enorme de variables e híbridos propuestos, y muchas más metaheurísticas han sido probadas en problemas específicos. Este es un campo en investigación, con un gran número de publicaciones en revistas, un gran número de investigadores y usuarios, además de un gran número de aplicaciones.
Véase también
Bibliografía
C. Blum and A. Roli A. (2003). Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys 35(3) 268–308.
Enlaces externos
- DGPF A distributed framework for randomized, heuristic searches like GA and Hill Climbing which comes with a specialization for Genetic Programming and allows to combine different search algorithms.
- A toolbox of metaheuristic algorithms for MATLAB. It offers single-solution, population-based and hybrids metaheuristics. With this toolbox you can solve optimization problems defined in the MATLAB language using metaheuristic algorithms implemented in C++ and Java.
- jMetal jMetal is an object-oriented Java-based framework aimed at facilitating the development of metaheuristics for solving multi-objective optimization problems (MOPs).