Algoritme hill climbing

En ciència de la computació, l'algoritme hill climbing, també cridat algoritme d'Escalada Simple o ascens de tossals és una tècnica d'optimisació matemàtica que pertany a la família dels algoritmes de busca local. És un algoritme iterativo que comença en una solució arbitrària a un problema, després intenta trobar una millor solució variant incrementalmente un únic element de la solució. Si el canvi produïx una millor solució, un atre canvi incremental se li realisa a la nova solució, repetint este procés fins que no es puguen trobar millores. Sol cridar-se a esta busca algoritme voraç local, perque pren un estat veí "bo" sense pensar en la pròxima acció.

L'Algoritme Hill climbing és interessant per a trobar un òptim local (una solució que no pot ser millorada considerant una configuració del veïnat) pero no garantisa trobar la millor solució possible (l'òptim global) de totes les possibles solucions (l'espai de busca). La característica de que només l'òptim local pot ser garantisat pot ser remediada utilisant reinicios (busca local repetida), o esquemes més complexos basats en iteraciones, com busca local iterada, en memòria, com optimisació de busca reactiva i busca tabú, o modificacions estocàstiques, com simulated annealing.

La relativa simplicitat d'este algoritme ho fa una primera elecció popular entre els algoritmes d'optimisació. És usat àmpliament en inteligència artificial, per a alcançar un estat final des d'un nodo d'inici. L'elecció del pròxim nodo i del nodo d'inici pot ser variada per a obtindre una llista d'algoritmes de la mateixa família. Encara que algoritmes més alvançats tals com simulated annealing o busca tabú poden tornar millors resultats, en algunes situacions hill climbing opera sense diferències. El hill climbing en freqüència pot produir un millor resultat que atres algoritmes quan la cantitat de temps disponible per a realisar la busca és llimitada, per eixemple en sistemes en temps real. L'algoritme pot tornar una solució vàlida encara si és interromput en qualsevol moment ans que finalise.

Per eixemple, el hill climbing pot ser aplicat al problema del viajante. És fàcil trobar una solució inicial que visite totes les ciutats pero seria molt pobra comparada en la solució òptima. L'algoritme comença en dita solució i realisa chicotetes millores a esta, tals com intercanviar l'orde en el qual dos ciutats són visitades. Eventualment, és provable que s'obtinga una ruta més curta.

Descripció matemàtica

El hill climbing intenta maximizar (o minimisar) una funció objectiu $f(𝐱)$, a on $𝐱$ és un vector de valors discrets i/o continus. En cada iteración, el hill climbing ajustarà un únic element en $𝐱$ i determinarà si el canvi millora el valor de $f(𝐱)$. (Note que açò diferix dels métodos de descens de gradient, els quals ajusten tots els valors en $𝐱$ en cada iteración d'acort al gradient del tossal.) En hill climbing, qualsevol canvi que millore $f(𝐱)$ és acceptat, i el procés continua fins que no puga trobar-se un canvi que millore el valor de $f(𝐱)$. $𝐱$ es diu llavors que és "òptima localment".

En els espais de vectores discrets, cada valor possible per a $𝐱$ pot ser visualisat com un vèrtiç en un grafo. El hill climbing seguirà el grafo de vèrtiç en vèrtiç, sempre incrementant (o disminuint) localment el valor de $f(𝐱)$, fins a alcançar un màxim local (o un mínim local) $x_m$.

Una superfície convexa. Els algoritmes de hill climbing (hill-climbers) són apropiats per a optimisar sobre dites superfícies, i van a convergir al màxim global.

Variants

En el hill climbing simple, el primer nodo propenc és triat, mentres que en hill climbing d'ascens pronunciat tots els successors són comparats i la solució més propenca és elegida. Abdós formes fallen si no existix un nodo propenc, lo que succeïx si hi ha màxims locals en l'espai de busca que no són solucions. El hill climbing d'ascens pronunciat és similar a la busca en esgambi, la qual intenta totes les possibles extensions del camí actual en lloc de només una.

Hill climbing estocàstic no examina tots els veïns abans de decidir cóm moure's. En lloc d'això, selecciona un veí aleatori, i decidix (basat en la cantitat de progrés en eixe veí) si moure's a ell o examinar un atre.

Descens coordinat realisa una busca en llínea a lo llarc d'una direcció de coordenades a partir del punt actual en cada iteración. Algunes versions del descens coordinat elegixen aleatoriamente una direcció coordinada diferent en cada iteración.

Hill climbing de reinicie aleatori és fique-algoritme construït sobre la base de hill climbing. És també conegut com Shotgun hill climbing. Est realisa, iterativament, el hill-climbing, cada volta en una condició inicial aleatòria $x_0$. La millor $x_m$ és guardada: si una nova correguda del hill climbing produïx una millor $x_m$ que l'estat guardat, ho reemplaça.

Hill climbing de reinicie aleatori és un algoritme sorprenentment efectiu en molts casos. D'açò es deriva que en freqüència és millor gastar temps de CPU explorant l'espai, que cuidadosadament optimisar des d'una condició inicial.

Vore també

• Algoritme voraç