En análisis numérico, la escalada es una técnica de optimización matemática que pertenece a la familia de la búsqueda local . Es un algoritmo iterativo que comienza con una solución arbitraria a un problema y luego intenta encontrar una mejor solución realizando un cambio incremental en la solución. Si el cambio produce una solución mejor, se realiza otro cambio incremental en la nueva solución, y así sucesivamente hasta que no se puedan encontrar más mejoras.
Por ejemplo, la escalada de colinas se puede aplicar al problema del viajante de comercio . Es fácil encontrar una solución inicial que visite todas las ciudades, pero probablemente será muy pobre en comparación con la solución óptima. El algoritmo comienza con una solución de este tipo y le realiza pequeñas mejoras, como cambiar el orden en que se visitan dos ciudades. Con el tiempo, es probable que se obtenga una ruta mucho más corta.
Hill Climbing encuentra soluciones óptimas para problemas convexos ; para otros problemas solo encontrará óptimos locales (soluciones que no pueden mejorarse con ninguna configuración vecina), que no son necesariamente la mejor solución posible (el óptimo global ) de todas las soluciones posibles ( el espacio de búsqueda ). Ejemplos de algoritmos que resuelven problemas convexos mediante la escalada de colinas incluyen el algoritmo simplex para programación lineal y búsqueda binaria . [1] : 253 Para intentar evitar quedarse atascado en los óptimos locales, se podrían usar reinicios (es decir, búsqueda local repetida) o esquemas más complejos basados en iteraciones (como la búsqueda local iterada ) o en la memoria (como la optimización de búsqueda reactiva y tabú). search ), o en modificaciones estocásticas sin memoria (como el recocido simulado ).
La relativa simplicidad del algoritmo lo convierte en una primera opción popular entre los algoritmos de optimización. Se utiliza ampliamente en inteligencia artificial , para alcanzar un estado objetivo desde un nodo inicial. En algoritmos relacionados se utilizan diferentes opciones para los siguientes nodos y los nodos iniciales. Aunque algoritmos más avanzados, como el recocido simulado o la búsqueda tabú, pueden dar mejores resultados, en algunas situaciones la escalada funciona igual de bien. La escalada de colinas a menudo puede producir un mejor resultado que otros algoritmos cuando la cantidad de tiempo disponible para realizar una búsqueda es limitada, como ocurre con los sistemas en tiempo real, siempre que una pequeña cantidad de incrementos generalmente converjan en una buena solución (la solución óptima). o una aproximación cercana). En el otro extremo, la clasificación de burbujas puede verse como un algoritmo de escalada (cada intercambio de elementos adyacentes disminuye el número de pares de elementos desordenados), sin embargo, este enfoque está lejos de ser eficiente incluso para N modesto, ya que el número de intercambios requeridos crece cuadráticamente.
La escalada de colinas es un algoritmo en cualquier momento : puede devolver una solución válida incluso si se interrumpe en cualquier momento antes de que finalice.
La escalada intenta maximizar (o minimizar) una función objetivo , donde es un vector de valores continuos y/o discretos. En cada iteración, la escalada ajustará un solo elemento y determinará si el cambio mejora el valor de . (Tenga en cuenta que esto difiere de los métodos de descenso de gradiente , que ajustan todos los valores en cada iteración de acuerdo con la pendiente de la colina). Al subir una colina, se acepta cualquier cambio que mejore y el proceso continúa hasta que no se puede encontrar ningún cambio. para mejorar el valor de . Entonces se dice que es "localmente óptimo".
En espacios vectoriales discretos, cada valor posible de puede visualizarse como un vértice en un gráfico . La escalada seguirá la gráfica de vértice a vértice, siempre aumentando (o disminuyendo) localmente el valor de , hasta alcanzar un máximo local (o mínimo local ) .
En la escalada simple , se elige el primer nodo más cercano, mientras que en la escalada con ascenso más pronunciado se comparan todos los sucesores y se elige el más cercano a la solución. Ambas formas fallan si no hay un nodo más cercano, lo que puede suceder si hay máximos locales en el espacio de búsqueda que no son soluciones. El ascenso más empinado es similar a la búsqueda del mejor primero , que intenta todas las extensiones posibles del camino actual en lugar de solo una.
La escalada estocástica no examina a todos los vecinos antes de decidir cómo moverse. Más bien, selecciona un vecino al azar y decide (en función de la cantidad de mejora en ese vecino) si se traslada a ese vecino o examina a otro.
El descenso de coordenadas realiza una búsqueda lineal a lo largo de una dirección de coordenadas en el punto actual en cada iteración. Algunas versiones de descenso de coordenadas eligen aleatoriamente una dirección de coordenadas diferente en cada iteración.
La escalada de colinas con reinicio aleatorio es un metaalgoritmo construido sobre el algoritmo de escalada de colinas. También se le conoce como escalada de escopeta . Iterativamente sube colinas, cada vez con una condición inicial aleatoria . Lo mejor se conserva: si una nueva tanda de escalada produce un estado mejor que el almacenado, reemplaza el estado almacenado.
La escalada de colinas con reinicio aleatorio es un algoritmo sorprendentemente eficaz en muchos casos. Resulta que a menudo es mejor dedicar tiempo de CPU a explorar el espacio que optimizarlo cuidadosamente desde una condición inicial. [ ¿investigacion original? ]
La escalada no necesariamente encontrará el máximo global, sino que puede converger en un máximo local . Este problema no ocurre si la heurística es convexa. Sin embargo, como muchas funciones no son convexas, a menudo es posible que la escalada de colinas no alcance un máximo global. Otros algoritmos de búsqueda local intentan superar este problema, como la escalada estocástica de colinas , los paseos aleatorios y el recocido simulado .
Las crestas son un problema desafiante para los escaladores que optimizan en espacios continuos. Debido a que los escaladores solo ajustan un elemento en el vector a la vez, cada paso se moverá en una dirección alineada con el eje. Si la función objetivo crea una cresta estrecha que asciende en una dirección no alineada con el eje (o si el objetivo es minimizar, un callejón estrecho que desciende en una dirección no alineada con el eje), entonces el escalador solo puede ascender la cresta (o descender el callejón) en zigzag. Si los lados de la cresta (o callejón) son muy empinados, entonces el escalador puede verse obligado a dar pasos muy pequeños mientras zigzaguea hacia una mejor posición. Por lo tanto, puede que le lleve un tiempo excesivo ascender la cresta (o descender el callejón).
Por el contrario, los métodos de descenso en gradiente pueden moverse en cualquier dirección en la que la cresta o el callejón pueda ascender o descender. Por lo tanto, generalmente se prefiere el descenso de gradiente o el método de gradiente conjugado a la escalada de colinas cuando la función objetivo es diferenciable. Sin embargo, los escaladores de colinas tienen la ventaja de no requerir que la función objetivo sea diferenciable, por lo que pueden ser preferidos cuando la función objetivo es compleja.
Otro problema que a veces ocurre al escalar colinas es el de una meseta. Se encuentra una meseta cuando el espacio de búsqueda es plano, o lo suficientemente plano como para que el valor devuelto por la función de destino no se pueda distinguir del valor devuelto para regiones cercanas debido a la precisión utilizada por la máquina para representar su valor. En tales casos, el escalador puede no ser capaz de determinar en qué dirección debe dar un paso y puede desviarse en una dirección que nunca conduce a una mejora.
Algoritmo de pseudocódigo Espacio discreto Escalada de colinas es nodoactual := nodoinicial bucle hacer L := VECINOS(NodoActual) siguienteEval := −INF siguienteNodo := NULL para todo x en L, haga si EVAL(x) > nextEval entonces siguienteNodo := x siguienteEval := EVAL(x) si nextEval ≤ EVAL(currentNode) entonces // Devuelve el nodo actual ya que no existen mejores vecinos devolver el nodo actual NodoActual := NodoSiguiente
algoritmo de escalada espacial continua es currentPoint :=inicialPoint // el vector de magnitud cero es común stepSize := initialStepSizes // un vector de todos unos es común aceleración: = alguna aceleración // un valor como 1,2 es común candidato[0] := −aceleración candidato[1] := −1 / aceleración candidato[2] := 1 / aceleración candidato[3] := aceleración mejor puntuación: = EVAL (punto actual) bucle hacer antes de la puntuación: = mejor puntuación para cada elemento i en currentPoint hacer antes del punto: = punto actual [i] mejor paso := 0 para j de 0 a 3 haz // prueba cada una de las 4 ubicaciones candidatas paso := tamaño de paso[i] × candidato[j] PuntoActual[i] :=PuntoAntes + paso puntuación: = EVAL (punto actual) si puntaje > mejor puntaje entonces mejor puntuación: = puntuación mejorPaso := paso si bestStep es 0 entonces PuntoActual[i] :=PuntoAntes tamaño de paso[i] := tamaño de paso[i] / aceleración demás PuntoActual[i] :=PuntoAntes + MejorPaso tamaño de paso[i] := mejorPaso // aceleración si (bestScore - beforeScore) <épsilon entonces devuelve currentPoint
Algoritmo genético de contraste ; optimización aleatoria .
Escalada de colinas en Wikilibros
