Subir colinas

En análisis numérico , el ascenso de colinas es una técnica de optimización matemática que pertenece a la familia de la búsqueda local .

Se trata de un algoritmo iterativo que parte de una solución arbitraria a un problema y, a continuación, intenta encontrar una solución mejor mediante modificaciones incrementales . Si la modificación produce una solución mejor, se realiza otra modificación incremental a la nueva solución, y así sucesivamente hasta que no se puedan encontrar más mejoras.

Por ejemplo, el algoritmo de ascenso de colinas se puede aplicar al problema del viajante . Es fácil encontrar una solución inicial que visite todas las ciudades, pero probablemente será muy deficiente en comparación con la solución óptima. El algoritmo parte de dicha solución y realiza pequeñas mejoras, como cambiar el orden en que se visitan dos ciudades. Finalmente, es probable que se obtenga una ruta mucho más corta.

El algoritmo de ascenso de colinas 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 entre todas las soluciones posibles (el espacio de búsqueda ).

Ejemplos de algoritmos que resuelven problemas convexos mediante ascenso de colina incluyen el algoritmo simplex para programación lineal y la búsqueda binaria . ^{[ 1 ] : 253}

Para intentar evitar quedarse atascado en ó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 memoria (como la optimización de búsqueda reactiva y la búsqueda tabú ), o en modificaciones estocásticas sin memoria (como el recocido simulado ).

La relativa simplicidad del algoritmo lo convierte en una 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 nodos siguientes y los nodos iniciales. Aunque algoritmos más avanzados como el recocido simulado o la búsqueda tabú pueden ofrecer mejores resultados, en algunas situaciones el ascenso de colina funciona igual de bien. El ascenso de colina suele producir un mejor resultado que otros algoritmos cuando el tiempo disponible para realizar una búsqueda es limitado, como en los sistemas en tiempo real, siempre que un pequeño número de incrementos converja en una buena solución (la solución óptima o una aproximación cercana). En el otro extremo, el ordenamiento de burbuja puede considerarse un algoritmo de ascenso de colina (cada intercambio de elementos adyacentes disminuye el número de pares de elementos desordenados), pero este enfoque dista mucho de ser eficiente incluso para N modesto, ya que el número de intercambios necesarios crece cuadráticamente.

El algoritmo de ascenso de colinas es un algoritmo que funciona en cualquier momento : puede devolver una solución válida incluso si se interrumpe en cualquier momento antes de que finalice.

El método de ascenso de colinas intenta maximizar (o minimizar) una función objetivo.${\displaystyle f(\mathbf {x} )}$, dónde${\displaystyle \mathbf {x} }$es un vector de valores continuos y/o discretos. En cada iteración, el ascenso de colinas ajustará un solo elemento en${\displaystyle \mathbf {x} }$y determinar si el cambio mejora el valor de${\displaystyle f(\mathbf {x} )}$. (Tenga en cuenta que esto difiere de los métodos de descenso de gradiente , que ajustan todos los valores en${\displaystyle \mathbf {x} }$en cada iteración según la pendiente de la colina.) Con el ascenso de colinas, cualquier cambio que mejore${\displaystyle f(\mathbf {x} )}$se acepta y el proceso continúa hasta que no se pueda encontrar ningún cambio para mejorar el valor de${\displaystyle f(\mathbf {x} )}$. Entonces${\displaystyle \mathbf {x} }$Se dice que es "localmente óptimo".

En espacios vectoriales discretos, cada valor posible para${\displaystyle \mathbf {x} }$puede visualizarse como un vértice en un grafo . El ascenso de colinas seguirá el grafo de vértice a vértice, aumentando (o disminuyendo) siempre localmente el valor de${\displaystyle f(\mathbf {x} )}$, hasta un máximo local (o mínimo local )${\displaystyle x_{m}}$se alcanza.

En el método de ascenso de colinas simple , se elige el primer nodo más cercano, mientras que en el método de ascenso de colinas de máxima pendiente se comparan todos los sucesores y se elige el más cercano a la solución. Ambos métodos fallan si no hay un nodo más cercano, lo que puede ocurrir si existen máximos locales en el espacio de búsqueda que no son soluciones. El método de ascenso de colinas de máxima pendiente es similar a la búsqueda primero en amplitud , que prueba todas las posibles extensiones de la ruta actual en lugar de solo una. ^{[ 2 ]}

El método de ascenso de colina estocástico no examina a todos los vecinos antes de decidir cómo moverse. En cambio, selecciona un vecino al azar y decide (en función de la mejora que haya experimentado) si moverse a ese vecino o examinar otro. El método de ascenso de colina de primera elección implementa el ascenso de colina estocástico generando vecinos aleatoriamente hasta que se genera uno mejor, el cual se elige posteriormente. Este método funciona bien cuando los estados tienen muchos sucesores posibles (por ejemplo, miles). ^{[ 3 ]}

El método de 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 este método seleccionan aleatoriamente una dirección de coordenadas diferente en cada iteración.

El algoritmo de ascenso de colinas con reinicio aleatorio es un metaalgoritmo construido sobre el algoritmo de ascenso de colinas. También se conoce como ascenso de colinas tipo escopeta . Realiza el ascenso de colinas de forma iterativa, cada vez con una condición inicial aleatoria.${\displaystyle x_{0}}$. El mejor${\displaystyle x_{m}}$se mantiene: si una nueva carrera de ascenso a la colina produce un mejor${\displaystyle x_{m}}$que el estado almacenado, reemplaza el estado almacenado.

• Descenso de gradiente
• Algoritmo voraz
• Tâtonnement
• Desplazamiento a la media
• Algoritmo de búsqueda A*

• Russell, Stuart J.; Norvig , Peter (2003), Inteligencia artificial: un enfoque moderno (2.ª  ed.), Upper Saddle River, Nueva Jersey: Prentice Hall, pp. 111–114 , ISBN  0-13-790395-2

• Lasry, George (2018). Una metodología para el criptoanálisis de cifrados clásicos con metaheurísticas de búsqueda (PDF) . Kassel University Press . ISBN 978-3-7376-0459-8.

• Escalada de colinas en Wikibooks