Metaheurística
Una metaheurística és un mètode heurístic per a resoldre un tipus de problema computacional general, utilitzant els paràmetres donats per l'usuari sobre uns procediments genèrics i abstractes d'una manera que s'espera eficient. Normalment, aquests procediments són heurístics. El nom combina el prefix grec "meta" ("més enllà", aquí amb el sentit de "nivell superior") i "heurístic" (de ευρισκειν, heuriskein, "trobar ").
Les metaheurística generalment s'apliquen a problemes que no tenen un algorisme o heurística específica que doni una solució satisfactòria, o bé quan no és possible implementar aquest mètode òptim. La majoria de les metaheurística tenen com a objectiu els problemes d'optimització combinatòria, però per descomptat, es poden aplicar a qualsevol problema que es pugui reformular en termes heurístics, per exemple en resolució d'equacions booleanes.
Les metaheurística no són la panacea i solen ser menys eficients que les heurístiques específiques, en diversos ordres de magnitud, en problemes que accepten aquest tipus d'heurístiques crues.
Conceptes generals i nomenclatura
[modifica]L'objectiu de l'optimització combinatòria és trobar un objecte matemàtic finit (per exemple, un vector de bits o permutació) que maximitzi (o minimitzi, depenent del problema) una funció especificada per l'usuari de la metaheurística. A aquests objectes se'ls sol anomenar estats, i al conjunt de tots els estats candidats se l'anomena espai de cerca. La naturalesa dels estats i de l'espai de cerca són normalment específics del problema.
La funció a optimitzar se l'anomena funció objectiu, i es dona a l'usuari com un procediment caixa-negra que avalua l'estat actual o la funció. Depenent de la metaheurística, l'usuari pot haver de donar altres funcions caixa-negra que produeixin un nou estat, generen variants de la configuració, trien un estat entre diversos, aportin valors màxims o mínims per a la funció objectiu en un conjunt d'estats, i en aquest estil.
Algunes metaheurística mantenen en cada instant d'execució un únic estat actual, i el canvien en cada iteració per un de nou. Aquest pas bàsic es coneix com a transició d'estat, moviment o actualització de l'estat. El moviment és turó amunt o turó avall depenent de si els valors que dona la funció objectiu s'incrementa o es disminueix. El nou estat pot estar construït de zero per un generador d'estats donat per l'usuari. Alternativament, el nou estat pot derivar de la configuració per un mutador proporcionat per l'usuari, en aquest cas, el nou estat es coneix com a veí de la configuració. Generadors i commutadors són habitualment procediments probabilístics. El conjunt de tots els nous estats donats pel mutador és el veïnat de la configuració.
metaheurística més sofisticades mantenen, en comptes d'un únic estat actual, un conjunt de diversos estats candidat. Així, el pas bàsic afegeix o elimina estats d'aquest conjunt. En aquest cas, els procediments donats per l'usuari seleccionen estats per ser descartats, i generen nous estats a afegir. El darrer estat pot ser generat com combinació o encreuament de dos o més estats del conjunt.
Una metaheurística pot guardar informació de l'òptim actual, escollint l'estat òptim entre tots els òptims actuals obtinguts en diverses etapes de l'algorisme.
Atès que el nombre de candidats pot ser molt gran, normalment, les metaheurística estan dissenyades de manera que puguin ser interrompudes per un temps màxim especificat per l'usuari. Si no s'interrompen, algunes metaheurística exactes examinessin tots els candidats, i faran servir mètodes heurístics només per escollir l'ordre de l'enumeració, de fet, sempre tornaran un òptim real, si el temps màxim és prou gran. En canvi, altres metaheurística donen només una garantia probabilística pobra de poder assolir l'òptim, de manera que quan el temps màxim s'aproxima a infinit, la probabilitat d'examinar cada candidat tendeix a 1.
metaheurístiques comuns
[modifica]Algunes metaheurístiques molt conegudes són
- Optimització aleatòria
- Recerca local
- Algorisme voraç i ascensió de turons
- Ascensió de turons amb reinicialització aleatòria
- Recerca primer el millor
- Refredament simulat
- Optimització basada en colònies de formigues
- Algorisme d'eixam
- Recerca tabú
- algorisme genètic
- algorisme memètic
- GRASP
- Meta-raps
- Algorismes multiarrencada
- Intel·ligència eixam
- Recerca difusió estocàstica
- Optimització extrema
- Recerca dispersa i reencadenament de trajectòries
- PeSOA: Penguins Search Optimization Algorithm
Hi ha un nombre enorme de variables i híbrids proposats, i moltes més aplicacions de les metaheurística a problemes específics s'han provat. Aquesta és un camp en recerca, amb un gran nombre de publicacions en revistes, un gran nombre d'investigadors i usuaris, a més d'un gran nombre d'aplicacions.
Vegeu també
[modifica]Bibliografia
[modifica]- C. Blum and A. Roli A. (2003). Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys 35 (3) 268-308.
- M. Gendreau and J. Potvin (2010). Handbook of Metaheuristics, Second Edition. International Series in Operations Research and Management Saciences ISOR 146. ISBN 978-1-4419-1663-1
Enllaços externs
[modifica]