HILL CLIMBING SEARCH

En ciencias de la computación, la escalada es una optimización matemática técnica que pertenece a la familia de búsqueda local. Es un algoritmo iterativo que comienza con una solución arbitraria a un problema, a continuación, intenta encontrar una solución mejor forma incremental de cambiar un solo elemento de la solución. Si el cambio produce una mejor solución, un cambio gradual que se haga a la nueva solución, repetir hasta que no haya más mejoras se pueden encontrar.

Escalada Hill es bueno para encontrar un óptimo local (una buena solución que se encuentra relativamente cerca de la solución inicial), pero no está garantizado para encontrar la mejor solución posible (el óptimo global ) de todas las soluciones posibles (el espacio de búsqueda ).

La relativa simplicidad del algoritmo que hace que una elección popular el primer lugar entre la optimización de algoritmos. Se utiliza ampliamente en la inteligencia artificial , para llegar a un estado final de un nodo de inicio. Elección del siguiente nodo y el nodo de partida se puede variar para dar una lista de algoritmos relacionados. A pesar de algoritmos más avanzados tales como recocido simulado o búsqueda tabú puede dar mejores resultados, en algunas situaciones colina escalada funciona igual de bien. De subida de pendientes a menudo se puede producir un resultado mejor que otros algoritmos cuando la cantidad de tiempo disponible para realizar una búsqueda se limita, por ejemplo con sistemas de tiempo real.


Descripción matemática

Escalada intentos Hill para maximizar (o minimizar) un objetivo de la función , Donde es un vector de valores continuos o discretos.

En cada iteración, la escalada se modifica un solo elemento en y determinar si el cambio mejora el valor de . (Tenga en cuenta que esta diferencia de gradiente de descenso métodos, que modifica todos los valores en en cada iteración de acuerdo a la pendiente de la colina.) Con la escalada, cualquier cambio que mejora la es aceptada, y el proceso continúa hasta que no cambia se pueden encontrar para mejorar el valor de . Entonces se dice que es "óptimo local".

En los espacios vectoriales discretos, cada valor posible para puede ser visualizado como un vértice en un grafo . La escalada seguirá la gráfica de vértice a vértice, siempre a nivel local aumentando (o disminuyendo) el valor de , hasta un máximo local(o mínimo local) X m se alcanza.

Variantes

En colina simple escalada, cuanto más cerca del primer nodo que se elija, mientras que en el ascenso más empinado cerro subir todos los sucesores se comparan y el más cercano a la solución elegida es. Ambas formas de error si no hay ningún nodo más cercano, lo que puede suceder si hay máximos locales en el espacio de búsqueda que no son soluciones. Ascensión colina Steepest escalada es similar al de sesiones de la búsqueda mejor , que trata de todas las extensiones posibles de la ruta actual en lugar de uno solo.

Aleatorios reiniciar la escalada es un meta-algoritmo basado en la parte superior de la escalada algoritmo colina. También es conocida como colina escopeta escalada. Es iterativa se en escalada, cada vez con una condición inicial aleatoria x 0. La mejor m x se mantiene: si una carrera nueva escalada de la colina produce una x m mejor que el estado almacenado, que sustituye el estado almacenado.

Una visualización de una superficie con dos máximos locales. (Sólo uno de ellos es el máximo nivel mundial.) Si un escalador de montaña se inicia en una mala ubicación, puede converger con la máxima más baja.

Un problema con la escalada es que se encuentra sólo máximos locales . A menos que la heurística es convexa, no podrá alcanzar un máximo global. Otros algoritmos de búsqueda local de tratar de superar este problema, tales como colina estocástico escalada , paseos aleatorios y recocido simulado .

Cordilleras y Vida

Las crestas son un reto para los escaladores de montaña que optimizan los espacios continuos. Debido a que los escaladores colina sólo modifica un elemento en el vector a la vez, cada paso se mueve en un eje de dirección-alineados. Si la función objetivo crea una cresta estrecha que sube en un tercer eje alineado a la dirección (o si el objetivo es reducir al mínimo, un estrecho callejón que desciende en dirección del eje no alineados), el escalador de montaña sólo se puede subir a la canto (o bajar por el callejón) por el zig-zag. Si los lados de la cresta (o el callejón) son muy empinadas, el escalador de montaña puede ser obligado a tomar medidas muy pequeñas, ya que en zig-zag hacia una mejor posición. Por lo tanto, es posible que una duración excesiva de tiempo para que pueda subir a la cresta (o bajar por el callejón).

Por el contrario, los métodos de gradiente de descenso puede moverse en cualquier dirección que la cresta o callejón puede ascender o descender. Por lo tanto, el descenso del gradiente es generalmente preferible a la escalada en la función objetivo es diferenciable. Escaladores Hill, sin embargo, tienen la ventaja de no requerir la función objetivo a ser diferenciable, por lo que los escaladores colina puede ser preferible cuando la función objetivo es compleja.

Meseta

Otro problema que a veces ocurre con la escalada es la de una meseta. Una meseta se encuentra en el espacio de búsqueda es plana, o lo suficientemente plana que el valor devuelto por la función de destino se confunde con el valor devuelto de regiones cercanas debido a la precisión utilizada por el equipo que representará a su valor. En tales casos, el escalador monte no se puede ser capaz de determinar en qué dirección se debe intensificar, y puede caminar en una dirección que no conduce a la mejora.



En Pseudocódigo Seria:

Discreta Hill Escalada Espacio Algoritmo

CurrentNode = startNode;
bucle do
L = VECINOS (CurrentNode);
nextEval =-INF;
NextNode = NULL;
para todo x en L
if (EVAL (x) nextEval>)
NextNode = x;
nextEval = EVAL (x);
si nextEval <= EVAL (CurrentNode) / / Nodo de retorno de corriente, ya que no existen vecinos más volver CurrentNode; CurrentNode = NextNode; Hill Espacio continua escalada Algoritmo punto actual initialPoint = / / el vector cero grados de magnitud es común stepSize = initialStepSizes; / / un vector de todos los 1 es común = aceleración someAcceleration / / un valor como 1.2 es común candidatos [0] = aceleración; candidatos [1] = -1 / aceleración; candidatos [2] = 0; candidatos [3] = 1 / aceleración; candidatos [4] = aceleración; bucle do antes = EVAL (punto actual); para cada elemento i en el punto actual se mejor = -1; bestScore =-INF; para j 0-4 / / tratar cada uno de los 5 lugares candidatos punto actual [i] = punto actual [i] + stepSize [i] * candidato [j]; temp = EVAL (punto actual); punto actual [i] = punto actual [i] - stepSize [i] * candidato [j]; si (temperatura> bestScore)
bestScore = temp;
mejor = j;
si el candidato [mejor] no es 0
punto actual [i] = punto actual [i] + stepSize [i] * candidato [mejores];
stepSize [i] = stepSize [i] * candidato [mejores]; / / acelerar
if (EVAL (punto actual) - antes) retorno punto actual;