Enciclopedia/Diccionario de Psicología y Neurociencias:
ıllı Metaheurística wiki: info, libros pdf y vídeos
- Detalles
- Categoría: PSICOLOGIA (WIKINFO)
Metaheurística
Una metaheurística es un procedimiento heurístico para solucionar un género de inconveniente computacional general, utilizando los factores dados por el usuario sobre unos procedimientos genéricos y abstractos de una forma que se espera eficaz. En general, estos procedimientos son heurísticos. El nombre combina el prefijo heleno "meta" ("más allí", acá con el sentido de "nivel superior") y "heurístico" (de e???s?e??, heuriskein, "localizar"). Las metaheurísticas normalmente se aplican a inconvenientes que no tienen un algoritmo o bien heurística concreta que dé una solución satisfactoria; o cuando no es posible incorporar ese procedimiento inmejorable. La mayor parte de las metaheurísticas tienen como objetivo los inconvenientes de optimización combinatoria, mas lógicamente, se pueden aplicar a cualquier inconveniente que se pueda reelaborar en términos heurísticos, por servirnos de un ejemplo en resolución de ecuaciones booleanas. Las metaheurísticas no son la panacea y acostumbran a ser menos eficaces que las heurísticas concretas, en múltiples órdenes de magnitud, en inconvenientes que admiten esta clase de heurísticas puras. El objetivo de la optimización combinatoria es localizar un objeto matemático finito (por poner un ejemplo, un vector de bits o bien permutación) que maximice (o bien minimice, en dependencia del inconveniente) una función concretada por el usuario de la metaheurística. A estos objetos se les acostumbra a llamar estados, y al conjunto de todos y cada uno de los estados aspirantes se le llama espacio de busca. La naturaleza de los estados y del espacio de busca son generalmente concretos del inconveniente. La función a optimar se le llama función objetivo, y se da al usuario como un procedimiento caja-negra que valora el estado actual o bien la función. En dependencia de la metaheurística, el usuario puede tener que dar otras funciones caja-negra que generen un nuevo estado, producen variaciones del estado actual, escojan un estado entre múltiples, aporten valores máximos o bien mínimos para la función objetivo en un conjunto de estados, y en ese estilo. Algunas metaheurísticas sostienen en todos y cada momento de ejecución un solo estado actual, y lo cambian en todos y cada iteración por uno nuevo. Este paso básico se conoce como transición de estado, movimiento o bien actualización del estado. El movimiento es colina arriba o bien colina abajo en dependencia de si los valores que da la función objetivo se acrecienta o bien se decrementa. El nuevo estado puede estar construido desde la nada por un generador de estados dado por el usuario. De forma alternativa, el nuevo estado puede derivar del estado actual por un mutador proporcionado por el usuario; en un caso así, el nuevo estado se conoce como vecino del estado actual. Generadores y mutadores son frecuentemente procedimientos probabilísticos. El conjunto de todos y cada uno de los nuevos estados dados por el mutador es el vecindario del estado actual. Metaheurísticas más complejas sostienen, en lugar de un solo estado actual, un conjunto de múltiples estados aspirante. De esta manera, el paso básico agrega o bien suprime estados de este conjunto. En un caso así, los procedimientos dados por el usuario eligen estados para ser descartados, y producen nuevos estados a incorporar. El último estado puede ser generado como combinación o bien cruce de 2 o bien más estados del conjunto. Una metaheurística puede guardar información del inmejorable actual, eligiendo el estado perfecto entre todos y cada uno de los inmejorables actuales conseguidos en múltiples etapas del algoritmo. Dado que el número de aspirantes puede ser realmente grande, generalmente, las metaheurísticas están diseñadas de forma que puedan ser interrumpidas por un tiempo máximo concretado por el usuario. Si no se interrumpen, ciertas metaheurísticas precisas examinaran todos y cada uno de los aspirantes, y emplearán métodos heurísticos solo para seleccionar el orden de la enumeración; en verdad, siempre y en toda circunstancia van a devolver un inmejorable real, si el tiempo máximo es suficientemente grande. En cambio, otras metaheurísticas dan solo una garantía probabilística pobre de poder lograr el perfecto, de forma que cuando el tiempo máximo se acerca a infinito, la probabilidad de examinar cada aspirante tiende a 1. C. Blum and A. Roli A. (dos mil tres). Metaheuristics in combinatorial optimization: Overview and ideal comparison. ACM Computing Surveys 35(tres) 268–308.