Metaheurística algoritmos
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.
Campo de aplicación
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 crudas.
Nomenclatura
El objetivo de la optimización combinatoria es encontrar un objeto matemático finito 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.
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.
Metaheurísticas populares
Algunas metaheurísticas populares son las siguientes:
- Optimización aleatoria
- Búsqueda local
- Algoritmos voraces y Ascensión de colinas
- Ascensión de colinas con reinicialización aleatoria
- Búsqueda primero el mejor
- Enfriamiento simulado
- Optimización basada en colonias de hormigas
- Algoritmos de Enjambre
- Búsqueda tabú
- Algoritmos Genéticos
- Algoritmos Meméticos
- GRASP
- Meta-RaPS
- Algoritmos Multiarranque
- Inteligencia enjambre
- Búsqueda por difusión estocástica
- Optimización extrema
- Scatter Search y Path Relinking
