En el 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, luego intenta encontrar una mejor solución haciendo un cambio incremental en la solución. Si el cambio produce una mejor solución, 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 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 hace pequeñas mejoras, como cambiar el orden en que se visitan dos ciudades. Eventualmente, es probable que se obtenga una ruta mucho más corta.
La escalada 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 ). Algunos ejemplos de algoritmos que resuelven problemas convexos mediante escalada incluyen el algoritmo simplex para programación lineal y búsqueda binaria . [1] : 253 Para intentar evitar quedarse atascado en óptimos locales, uno podría usar reinicios (es decir, búsqueda local repetida), o esquemas más complejos basados en iteraciones (como búsqueda local iterada ), o en memoria (como optimización de búsqueda reactiva y tabú búsqueda ), o en modificaciones estocásticas sin memoria (como recocido simulado ).
La relativa simplicidad del algoritmo lo convierte en una primera opción popular entre los algoritmos de optimización. Se usa ampliamente en inteligencia artificial para alcanzar un estado objetivo desde un nodo inicial. En los algoritmos relacionados se utilizan diferentes opciones para los siguientes nodos y nodos iniciales. Aunque los 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 con los sistemas en tiempo real, siempre que una pequeña cantidad de incrementos converja típicamente 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 modestos, ya que el número de intercambios requeridos crece cuadráticamente.
La escalada es un algoritmo en cualquier momento : puede devolver una solución válida incluso si se interrumpe en cualquier momento antes de que finalice.
Descripción matemática
La escalada intenta maximizar (o minimizar) una función objetivo , dónde es un vector de valores continuos y / o discretos. En cada iteración, la escalada ajustará un solo elemento en 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 en cada iteración de acuerdo con el gradiente de la colina.) Con la escalada, cualquier cambio que mejore se acepta, y el proceso continúa hasta que no se puede encontrar ningún cambio para mejorar el valor de . Luego se dice que es "óptimo localmente".
En espacios vectoriales discretos, cada valor posible para puede visualizarse como un vértice en un gráfico . La escalada seguirá el gráfico de vértice a vértice, siempre aumentando (o disminuyendo) localmente el valor de, hasta un máximo local (o mínimo local ) es alcanzado.
Variantes
En la escalada simple , se elige el primer nodo más cercano, mientras que en la escalada más empinada 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. La subida más empinada de la colina es similar a la búsqueda del mejor primero , que intenta todas las posibles extensiones de la ruta 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 muda a ese vecino o examina a otro.
El descenso de coordenadas realiza una búsqueda de línea a lo largo de una dirección de coordenadas en el punto actual en cada iteración. Algunas versiones del descenso de coordenadas eligen aleatoriamente una dirección de coordenadas diferente en cada iteración.
La escalada de colinas con reinicio aleatorio es un meta-algoritmo construido sobre el algoritmo de escalada de colinas. También se le conoce como escalada en la colina con escopeta . Realiza escalada de forma iterativa, cada vez con una condición inicial aleatoria.. El mejor se mantiene: si una nueva carrera de escalada produce una mejor que el estado 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 la CPU a explorar el espacio, que optimizar cuidadosamente desde una condición inicial. [ investigación original? ]
Problemas
Máximos locales
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, la escalada de colinas a menudo puede no alcanzar 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 .
Crestas y callejones
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 de destino 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 montañista solo puede ascender la cresta (o descender por el callejón) zigzagueando. Si los lados de la cresta (o callejón) son muy empinados, entonces el montañista puede verse obligado a dar pasos muy pequeños mientras zigzaguea hacia una mejor posición. Por lo tanto, puede llevar un tiempo excesivo para que ascienda la cresta (o descienda por el callejón).
Por el contrario, los métodos de descenso en pendiente pueden moverse en cualquier dirección en la que la cresta o el callejón puedan ascender o descender. Por lo tanto, el descenso de gradiente o el método de gradiente conjugado generalmente se prefiere al ascenso de colinas cuando la función objetivo es diferenciable. Los escaladores, sin embargo, tienen la ventaja de no requerir que la función objetivo sea diferenciable, por lo que los escaladores pueden ser preferidos cuando la función objetivo es compleja.
Meseta
Otro problema que a veces se presenta con la escalada 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 sea indistinguible del valor devuelto para las regiones cercanas debido a la precisión utilizada por la máquina para representar su valor. En tales casos, es posible que el montañista no sea 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 Discrete Space Hill Climbing es currentNode: = startNode hacer bucle L: = VECINOS (currentNode) nextEval: = −INF nextNode: = NULL para todo x en L hacer si EVAL (x)> nextEval entonces nextNode: = x nextEval: = EVAL (x) si nextEval ≤ EVAL (currentNode) entonces // Devuelve el nodo actual ya que no existen mejores vecinos devolver currentNode currentNode: = nextNode
algoritmo Continuous Space Hill Climbing es currentPoint: = initialPoint // 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) hacer bucle beforeScore: = mejor puntuación para cada elemento i en currentPoint hago beforePoint: = currentPoint [i] bestStep: = 0 para j de 0 a 3 haz // prueba cada una de las 4 ubicaciones candidatas paso: = pasoSize [i] × candidato [j] currentPoint [i]: = beforePoint + paso puntuación: = EVAL (currentPoint) si puntuación> mejor puntuación entonces bestScore: = puntuación bestStep: = paso si bestStep es 0 entonces currentPoint [i]: = beforePoint stepSize [i]: = stepSize [i] / aceleración demás currentPoint [i]: = beforePoint + bestStep stepSize [i]: = bestStep // acelerar if (bestScore - beforeScore) <épsilon entonces devuelve currentPoint
Algoritmo genético de contraste ; optimización aleatoria .
Ver también
Referencias
- Russell, Stuart J .; Norvig, Peter (2003), Inteligencia artificial: un enfoque moderno (2ª ed.), Upper Saddle River, Nueva Jersey: Prentice Hall, págs. 111-114, ISBN 0-13-790395-2
- ^ Skiena, Steven (2010). El Manual de diseño de algoritmos (2ª ed.). Springer Science + Business Media . ISBN 1-849-96720-2.
Este artículo se basa en material extraído del Diccionario gratuito de informática en línea antes del 1 de noviembre de 2008 e incorporado bajo los términos de "renovación de licencias" de la GFDL , versión 1.3 o posterior.
enlaces externos
- Escalada de colinas en Wikilibros