Metaheurística

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 crudas.

Contenido

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 sólo 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 sólo 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

  • 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


Hay un número enorme de variables e híbridos propuestos, y muchas más aplicaciones de las metaheurísticas a problemas específicos se han probado. Esta 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.
  • MHTB 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).

Wikimedia foundation. 2010.

Игры ⚽ Поможем написать реферат

Mira otros diccionarios:

  • Algoritmo voraz — Un algoritmo voraz (también conocido como ávido, devorador o goloso) es aquel que, para resolver un determinado problema, sigue una metaheurística consistente en elegir la opción óptima en cada paso local con la esperanza de llegar a una solución …   Wikipedia Español

  • Heurística — Este artículo o sección necesita referencias que aparezcan en una publicación acreditada, como revistas especializadas, monografías, prensa diaria o páginas de Internet fidedignas. Puedes añadirlas así o avisar …   Wikipedia Español

  • Matheurística — Nombramos Matheurísticas a aquellos algoritmos de optimización derivados de la interoperación de metaheurísticas y técnicas de programación matemática (PM). Una de sus características esenciales es la explotación, en alguna parte del algoritmo,… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”