TechCodeview

• L'algoritme d'escalada de turons és un algorisme de cerca local que es mou contínuament en la direcció d'augment de l'elevació/valor per trobar el cim de la muntanya o la millor solució al problema. Acaba quan arriba a un valor màxim on cap veí té un valor més alt.
• L'algoritme d'escalada és una tècnica que s'utilitza per optimitzar els problemes matemàtics. Un dels exemples àmpliament discutits de l'algorisme d'escalada de turons és el problema del venedor viatjant en el qual hem de minimitzar la distància recorreguda pel venedor.
• També s'anomena cerca local cobdiciosa, ja que només mira al seu bon estat veí immediat i no més enllà.
• Un node d'algorisme d'escalada de turons té dos components que són l'estat i el valor.
• L'escalada de turons s'utilitza principalment quan hi ha una bona heurística disponible.
• En aquest algorisme, no necessitem mantenir i gestionar l'arbre o el gràfic de cerca, ja que només manté un únic estat actual.

Característiques de l'escalada de turons:

A continuació es mostren algunes característiques principals de l'algoritme d'escalada de turons:

Variant de generació i prova:Hill Climbing és la variant del mètode Generate and Test. El mètode Genera i prova produeix feedback que ajuda a decidir quina direcció moure's a l'espai de cerca.Enfocament cobdiciós:La cerca d'algoritmes d'escalada de turons es mou en la direcció que optimitza el cost.Sense marxa enrere:No fa marxa enrere en l'espai de cerca, ja que no recorda els estats anteriors.

Diagrama de l'espai estatal per a l'escalada:

El paisatge de l'espai d'estat és una representació gràfica de l'algoritme d'escalada de turons que mostra un gràfic entre diversos estats d'algorisme i funció/cost objectiu.

En l'eix Y hem pres la funció que pot ser una funció objectiu o funció de cost, i l'espai d'estats a l'eix x. Si la funció de l'eix Y és cost, l'objectiu de la cerca és trobar el mínim global i el mínim local. Si la funció de l'eix Y és funció objectiva, l'objectiu de la cerca és trobar el màxim global i el màxim local.

Diferents regions del paisatge espacial estatal:

Màxim local: El màxim local és un estat que és millor que els seus estats veïns, però també hi ha un altre estat que és superior.

Màxim global: El màxim global és el millor estat possible del paisatge espacial estatal. Té el valor més alt de funció objectiu.

Estat actual: És un estat en un diagrama de paisatge on hi ha actualment un agent.

Pla local màxim: És un espai pla del paisatge on tots els estats veïns dels estats actuals tenen el mateix valor.

Espatlla: És una regió d'altiplà que té una vora ascendent.

Tipus d'algoritme d'escalada de turons:

• Escalada senzilla:
• Pujada més pronunciada:
• Escalada estocàstica:

1. Escalada senzilla:

L'escalada de turons simple és la forma més senzilla d'implementar un algorisme d'escalada de turons. Només avalua l'estat del node veí alhora i selecciona el primer que optimitza el cost actual i el defineix com a estat actual. . Només comprova que sigui un estat successor i, si es troba millor que l'estat actual, moure's en el mateix estat. Aquest algorisme té les següents característiques:

• Menys consum de temps
• Solució menys òptima i la solució no està garantida

Algorisme per a l'escalada simple de turons:

Pas 1:Avalueu l'estat inicial, si és l'estat objectiu, retorneu l'èxit i Atureu-vos.Pas 2:Bucle Fins que es trobi una solució o no quedi cap operador nou per aplicar.Pas 3:Seleccioneu i apliqueu un operador a l'estat actual.Pas 4:Comprova el nou estat:
1. Si és l'estat de l'objectiu, retorneu l'èxit i sortiu.
2. En cas contrari, si és millor que l'estat actual, assigneu un nou estat com a estat actual.
3. Si no és millor que l'estat actual, torneu al pas 2.
Pas 5:Sortida.

2. Pujada més pronunciada:

L'algoritme d'ascens més pronunciat és una variació de l'algoritme simple d'escalada de turons. Aquest algorisme examina tots els nodes veïns de l'estat actual i selecciona un node veí més proper a l'estat objectiu. Aquest algorisme consumeix més temps a mesura que cerca diversos veïns

Algoritme per a l'ascensió més pronunciada:

Pas 1:Avalueu l'estat inicial, si és l'estat objectiu, retorneu l'èxit i atureu-vos, en cas contrari, feu l'estat actual com a estat inicial.Pas 2:Bucle fins que es trobi una solució o l'estat actual no canviï.
1. Que SUCC sigui un estat tal que qualsevol successor de l'estat actual serà millor que ell.
2. Per a cada operador que s'aplica a l'estat actual:
   1. Aplica el nou operador i genera un nou estat.
   2. Avaluar el nou estat.
   3. Si és l'estat de l'objectiu, torneu-lo i sortiu, sinó compareu-lo amb el SUCC.
   4. Si és millor que SUCC, establiu el nou estat com a SUCC.
   5. Si el SUCC és millor que l'estat actual, establiu l'estat actual a SUCC.
Pas 5:Sortida.

3. Escalada estocàstica:

L'escalada estocàstica de turons no examina per tots els seus veïns abans de moure's. Més aviat, aquest algorisme de cerca selecciona un node veí a l'atzar i decideix si es tria com a estat actual o examina un altre estat.

Problemes en l'algoritme d'escalada de turons:

1. Màxim local: Un màxim local és un estat màxim del paisatge que és millor que cadascun dels seus estats veïns, però també hi ha un altre estat present que és més alt que el màxim local.

Solució: La tècnica de retrocés pot ser una solució del màxim local en el paisatge espacial estatal. Creeu una llista del camí prometedor perquè l'algoritme pugui retrocedir a l'espai de cerca i explorar també altres camins.

2. Meseta: Un altiplà és l'àrea plana de l'espai de cerca en la qual tots els estats veïns de l'estat actual contenen el mateix valor, perquè aquest algorisme no troba cap millor direcció per moure's. Es podria perdre una recerca d'escalada a la zona de l'altiplà.

Solució: La solució per a l'altiplà és fer passos grans o molt petits mentre es cerca, per resoldre el problema. Seleccioneu aleatòriament un estat que estigui allunyat de l'estat actual, de manera que és possible que l'algoritme trobi una regió que no sigui altiplà.

3. Crestes: Una cresta és una forma especial del màxim local. Té una àrea que és més alta que els seus voltants, però té un pendent, i no s'hi pot accedir en un sol moviment.

Solució: Amb l'ús de la cerca bidireccional, o movent-nos en diferents direccions, podem millorar aquest problema.

programari del sistema

Recuit simulat:

Un algorisme d'escalada de turons que mai no fa un moviment cap a un valor inferior garantit que és incomplet perquè es pot quedar atrapat en un màxim local. I si l'algoritme aplica una caminada aleatòria, movent un successor, pot ser que es completi però no sigui eficient. Recuit simulat és un algorisme que proporciona eficiència i completitud.

En termes mecànics Recuit és un procés d'enduriment d'un metall o vidre a una temperatura elevada i després refredar-se gradualment, de manera que això permet que el metall assoleixi un estat cristal·lí de baixa energia. El mateix procés s'utilitza en el recuit simulat en què l'algorisme tria un moviment aleatori, en lloc de triar el millor moviment. Si el moviment aleatori millora l'estat, llavors segueix el mateix camí. En cas contrari, l'algorisme segueix el camí que té una probabilitat inferior a 1 o es mou cap avall i tria un altre camí.