Metaheurística

Una metaheurística és un método heurístic per a resoldre un tipo de problema computacional general, usant els paràmetros donats per l'usuari sobre uns procediments genèrics i abstractes d'una manera que s'espera eficient. Normalment, estos procediments són heurístics. El nom combina el prefix grec "meta" ("més allà", ací en el sentit de "nivell superior") i "heurístic" (de ευρισκειν, heuriskein, "trobar").

Les metaheurísticas generalment s'apliquen a problemes que no tenen un algoritme o heurística específica que done una solució satisfactòria; o be quan no és possible implementar eixe método òptim. La majoria de les metaheurísticas tenen com a objectiu els problemes d'optimisació combinatòria, pero per supost, es poden aplicar a qualsevol problema que es puga reformular en térmens heurístics, per eixemple en resolució d'equacions booleanas.

Les metaheurísticas no són la panacea i solen ser menys eficients que les heurístiques específiques, en varis órdens de magnitut, en problemes que accepten este tipo d'heurístiques pures.

Conceptes generals i nomenclatura

L'objectiu de l'optimisació combinatòria és trobar un objecte matemàtic finit (per eixemple, un vector de bits o permutació) que maximizar (o minimise, depenent del problema) una funció especificada per l'usuari de la metaheurística. A estos objectes se'ls sol cridar estats, i al conjunt de tots els estats candidats se li crida espai de busca. La naturalea dels estats i de l'espai de busca són usualment específics del problema.

La funció a optimisar se li crida funció objectiu, i es dona a l'usuari com un procediment caixa-negra que evalua l'estat actual o la funció. Depenent de la metaheurística, l'usuari pot tindre que donar unes atres funciones caixa-negra que produïxquen un nou estat, generen variants de l'estat actual, elegixquen un estat entre varis, aporten valors màxims o mínims per a la funció objectiu en un conjunt d'estats, i en eixe estil.

Algunes metaheurísticas mantenen en cada instant d'eixecució un únic estat actual, i ho canvien en cada iteración per un nou. Este pas bàsic es coneix com a transició d'estat, moviment o actualisació de l'estat. El moviment és tossal dalt o tossal avall depenent de si els valors que dona la funció objectiu s'incrementa o es decrementa. El nou estat pot estar construït des del no res per un generador d'estats donat per l'usuari. Alternativament, el nou estat pot derivar de l'estat actual per un mutador proporcionat per l'usuari; en este cas, el nou estat es coneix com a veí de l'estat actual. Generadors i mutadores són habitualment procediments provabilístics. El conjunt de tots els nous estats donats pel mutador és el veïnat de l'estat actual.

Metaheurísticas més sofisticades mantenen, en lloc d'un únic estat actual, un conjunt de varis estats candidat. Aixina, el pas bàsic afig o elimina estats d'este conjunt. En este cas, els procediments donats per l'usuari seleccionen estats per a ser descartats, i generen nous estats a afegir. L'últim estat pot ser generat com a combinació o creuament de dos o més estats del conjunt.

Una metaheurística pot guardar informació del òptim actual, triant l'estat òptim entre tots els òptims actuals obtinguts en vàries etapes de l'algoritme.

Ya que el número de candidats pot ser molt gran, normalment, les metaheurísticas estan dissenyades de manera que puguen ser interrompudes per un temps màxim especificat per l'usuari. Si no s'interrompen, algunes metaheurísticas exactes examinaren tots els candidats, i usaran métodos heurístics sol per a triar l'orde de l'enumeració; de fet, sempre tornaran un òptim real, si el temps màxim és lo suficientment gran. En canvi, atres metaheurísticas donen solament una garantia provabilística pobra de poder alcançar l'òptim, de manera que quan el temps màxim s'aproxima a infinit, la provabilitat d'examinar cada candidat tendix a 1.

Metaheurísticas comuns

Erro al crear miniatura:

Este diagrama presenta una manera de classificar algunes de les Metaheurísticas més conegudes. Un element entre dos categories indica que es pot colocar en una o en l'atra segons l'enfocament.

Algunes metaheurísticas molt conegudes són:

Hi ha un número enorme de variables i híbrits proposts, i moltes més metaheurísticas han segut provades en problemes específics. Est és un camp en investigació, en un gran número de publicacions en revistes, un gran número d'investigadors i usuaris, ademés d'un gran número d'aplicacions.

Vore també

Bibliografia

C. Blum and A. Roli A. (2003). Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys 35(3) 268–308.

Este artícul conté una traducció derivada de «Metaheurística» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.