b'\n_START_ARTICLE_\nMetaheur\xc3\xadstica\n_START_PARAGRAPH_\nUna metaheur\xc3\xadstica \xc3\xa9s un m\xc3\xa8tode heur\xc3\xadstic per a resoldre un tipus de problema computacional general, utilitzant els par\xc3\xa0metres donats per l\'usuari sobre uns procediments gen\xc3\xa8rics i abstractes d\'una manera que s\'espera eficient. Normalment, aquests procediments s\xc3\xb3n heur\xc3\xadstics. El nom combina el prefix grec "meta" ("m\xc3\xa9s enll\xc3\xa0", aqu\xc3\xad amb el sentit de "nivell superior") i "heur\xc3\xadstic" (de \xce\xb5\xcf\x85\xcf\x81\xce\xb9\xcf\x83\xce\xba\xce\xb5\xce\xb9\xce\xbd, heuriskein, "trobar ")._NEWLINE_Les metaheur\xc3\xadstica generalment s\'apliquen a problemes que no tenen un algorisme o heur\xc3\xadstica espec\xc3\xadfica que doni una soluci\xc3\xb3 satisfact\xc3\xb2ria, o b\xc3\xa9 quan no \xc3\xa9s possible implementar aquest m\xc3\xa8tode \xc3\xb2ptim. La majoria de les metaheur\xc3\xadstica tenen com a objectiu els problemes d\'optimitzaci\xc3\xb3 combinat\xc3\xb2ria, per\xc3\xb2 per descomptat, es poden aplicar a qualsevol problema que es pugui reformular en termes heur\xc3\xadstics, per exemple en resoluci\xc3\xb3 d\'equacions booleanes._NEWLINE_Les metaheur\xc3\xadstica no s\xc3\xb3n la panacea i solen ser menys eficients que les heur\xc3\xadstiques espec\xc3\xadfiques, en diversos ordres de magnitud, en problemes que accepten aquest tipus d\'heur\xc3\xadstiques crues.\n_START_SECTION_\nConceptes generals i nomenclatura\n_START_PARAGRAPH_\nL\'objectiu de l\'optimitzaci\xc3\xb3 combinat\xc3\xb2ria \xc3\xa9s trobar un objecte matem\xc3\xa0tic finit (per exemple, un vector de bits o permutaci\xc3\xb3) que maximitzi (o minimitzi, depenent del problema) una funci\xc3\xb3 especificada per l\'usuari de la metaheur\xc3\xadstica. 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\xc3\xb3n normalment espec\xc3\xadfics del problema._NEWLINE_La funci\xc3\xb3 a optimitzar se l\'anomena funci\xc3\xb3 objectiu, i es d\xc3\xb3na a l\'usuari com un procediment caixa-negra que avalua l\'estat actual o la funci\xc3\xb3. Depenent de la metaheur\xc3\xadstica, l\'usuari pot haver de donar altres funcions caixa-negra que produeixin un nou estat, generen variants de la configuraci\xc3\xb3, trien un estat entre diversos, aportin valors m\xc3\xa0xims o m\xc3\xadnims per a la funci\xc3\xb3 objectiu en un conjunt d\'estats, i en aquest estil._NEWLINE_Algunes metaheur\xc3\xadstica mantenen en cada instant d\'execuci\xc3\xb3 un \xc3\xbanic estat actual, i el canvien en cada iteraci\xc3\xb3 per un de nou. Aquest pas b\xc3\xa0sic es coneix com a transici\xc3\xb3 d\'estat, moviment o actualitzaci\xc3\xb3 de l\'estat. El moviment \xc3\xa9s tur\xc3\xb3 amunt o tur\xc3\xb3 avall depenent de si els valors que d\xc3\xb3na la funci\xc3\xb3 objectiu s\'incrementa o es disminueix. El nou estat pot estar constru\xc3\xaft de zero per un generador d\'estats donat per l\'usuari. Alternativament, el nou estat pot derivar de la configuraci\xc3\xb3 per un mutador proporcionat per l\'usuari, en aquest cas, el nou estat es coneix com a ve\xc3\xad de la configuraci\xc3\xb3. Generadors i commutadors s\xc3\xb3n habitualment procediments probabil\xc3\xadstics. El conjunt de tots els nous estats donats pel mutador \xc3\xa9s el ve\xc3\xafnat de la configuraci\xc3\xb3._NEWLINE_metaheur\xc3\xadstica m\xc3\xa9s sofisticades mantenen, en comptes d\'un \xc3\xbanic estat actual, un conjunt de diversos estats candidat. Aix\xc3\xad, el pas b\xc3\xa0sic 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\xc3\xb3 o encreuament de dos o m\xc3\xa9s estats del conjunt._NEWLINE_Una metaheur\xc3\xadstica pot guardar informaci\xc3\xb3 de l\'\xc3\xb2ptim actual, escollint l\'estat \xc3\xb2ptim entre tots els \xc3\xb2ptims actuals obtinguts en diverses etapes de l\'algorisme._NEWLINE_At\xc3\xa8s que el nombre de candidats pot ser molt gran, normalment, les metaheur\xc3\xadstica estan dissenyades de manera que puguin ser interrompudes per un temps m\xc3\xa0xim especificat per l\'usuari. Si no s\'interrompen, algunes metaheur\xc3\xadstica exactes examinessin tots els candidats, i faran servir m\xc3\xa8todes heur\xc3\xadstics nom\xc3\xa9s per escollir l\'ordre de l\'enumeraci\xc3\xb3, de fet, sempre tornaran un \xc3\xb2ptim real, si el temps m\xc3\xa0xim \xc3\xa9s prou gran. En canvi, altres metaheur\xc3\xadstica donen nom\xc3\xa9s una garantia probabil\xc3\xadstica pobra de poder assolir l\'\xc3\xb2ptim, de manera que quan el temps m\xc3\xa0xim s\'aproxima a infinit, la probabilitat d\'examinar cada candidat tendeix a 1.'