Buscar por subir a la cima

Climbing to the top search (en adelante, Climbing) es una técnica de optimización matemática que pertenece a la familia de algoritmos de búsqueda local . El algoritmo es un método iterativo que comienza con una solución arbitraria al problema y luego trata de encontrar la mejor solución cambiando uno de los elementos de la solución paso a paso Si la solución da una solución mejor, se hace un incremento para obtener una nueva solución, y se hace hasta llegar a un punto en el que no se encuentra ninguna mejora.

Por ejemplo, la escalada se puede utilizar para resolver el problema del viajante de comercio . Es fácil encontrar una solución inicial en la que el vendedor visite todas las ubicaciones, pero que probablemente sea muy pobre en comparación con la solución óptima. El algoritmo comienza con esta decisión y realiza pequeños cambios en la decisión que modifican el orden en que se visitan los dos sitios. En última instancia, lo más probable es que se encuentre una ruta significativamente más corta.

Climbing encuentra soluciones óptimas en problemas de programación convexa , para otros problemas el algoritmo solo encontrará un óptimo local (una solución que no se puede mejorar moviéndose a nodos vecinos), que no es necesariamente la mejor solución ( óptimo global ) de todos posibles soluciones en ( dominios de soluciones admisibles ). Ejemplos de algoritmos que resuelven problemas convexos por búsqueda de vértices incluyen el método simplex para programación lineal y búsqueda binaria [1] . Como un intento de superar quedarse atascado en un óptimo local, puede intentar comenzar la búsqueda nuevamente (es decir, repetir la búsqueda local) o usar esquemas más complejos basados en iteración (como en la búsqueda local iterativa ), almacenamiento de memoria (como en búsqueda pasiva y búsqueda tabú ), o modificaciones de algoritmos estocásticos menos memorizados (como recocido simulado ).

La relativa simplicidad del algoritmo hace que el algoritmo sea popular entre los algoritmos de optimización. Es ampliamente utilizado en la teoría de la inteligencia artificial para llegar a un estado objetivo desde un punto de partida. El método para elegir el siguiente punto y el punto de partida puede variar, dando una serie de algoritmos relacionados. Si bien los algoritmos más avanzados, como el recocido simulado o la búsqueda tabú , pueden brindar mejores resultados, la escalada funciona igual de bien en algunas situaciones. La escalada a menudo funciona mejor que otros algoritmos cuando el tiempo de búsqueda es limitado, lo cual es importante en los sistemas en tiempo real, siempre que una pequeña cantidad de pasos converja en una buena solución (al óptimo o cerca de él). Otro caso extremo, el tipo de burbuja , se puede considerar como un algoritmo ascendente (cada permutación de elementos vecinos reduce el número de pares no ordenados), y este enfoque está lejos de ser óptimo incluso para N pequeños, ya que el número de permutaciones crece cuadráticamente.

Climbing es un algoritmo de corte de tiempo : devuelve una solución válida incluso si se interrumpe en cualquier momento.

Descripción matemática

Climbing trata de maximizar (o minimizar) la función objetivo , donde es un vector de valores continuos y/o discretos. En cada iteración, el ascenso modifica un elemento y determina si las correcciones realizadas mejoran el valor o no. (Tenga en cuenta que esto es diferente de los métodos de descenso de gradiente , que corrigen todos los elementos del vector en cada iteración de acuerdo con el gradiente ascendente). Ascendiendo, se acepta cualquier cambio que mejore y el proceso continúa hasta que alcanzamos un punto donde no se puede mejorar. ser encontrado en . Entonces decimos que es un "óptimo local". $f(\mathbf{x})$ $\mathbf{x}$ $\mathbf{x}$ $f(\mathbf{x})$ $\mathbf{x}$ $f(\mathbf{x})$ $f(\mathbf{x})$ $\mathbf{x}$

En espacios vectoriales discretos, cada valor posible se puede representar como un vértice en un gráfico . La escalada atraviesa la gráfica de vértice a vértice, siempre aumentando (o disminuyendo) localmente el valor de la función hasta alcanzar un máximo local (o un mínimo local ) . $\mathbf{x}$ $f(\mathbf{x})$ $x_{m}$

Opciones

El ascenso simple selecciona el primer nodo en la dirección del vértice, mientras que el ascenso más pronunciado compara todos los descendientes y selecciona el nodo más cercano al vértice. Ambas formas fallan si no hay un nodo para escalar, lo que puede suceder si hay un máximo local que no es una solución. El ascenso más rápido es similar a la mejor búsqueda primero , que itera sobre todas las extensiones posibles de la ruta actual, no solo una.

Climb random search no comprueba todos los nodos vecinos antes de elegir un movimiento. En cambio, se elige un nodo vecino al azar y se toma una decisión (basada en la mejora dada por ese vecino) si moverse hacia ese nodo o revisar otro nodo.

El descenso de coordenadas realiza una búsqueda lineal a lo largo de una coordenada desde el punto actual en cada iteración. Algunas variantes de descenso de coordenadas eligen una dirección de coordenadas al azar en cada iteración.

La reanudación aleatoria del ascenso es un metaalgoritmo construido sobre el algoritmo de ascenso. También se conoce como escalada Shotgun Hill . El algoritmo realiza iterativamente el ascenso, eligiendo cada vez una inicial aleatoria . Se guarda el mejor valor y si un nuevo intento de escalada arroja un valor mejor que el memorizado, reemplaza el estado memorizado. $x_{0}$ $x_{m}$ $x_{m}$

La reanudación aleatoria de la escalada es, en muchos casos, un algoritmo sorprendentemente eficiente. Resulta que a menudo es más eficiente gastar recursos de CPU explorando el espacio en lugar de optimizar cuidadosamente desde el estado inicial.

Tareas

Máximos locales

La escalada no necesariamente encontrará un máximo global, puede conducir a un máximo local . Este problema no ocurre si la función es convexa. Sin embargo, dado que no todas las funciones son convexas, es posible que el ascenso no encuentre un máximo global. Otros algoritmos de búsqueda local intentan superar este problema, como la búsqueda aleatoria de vértices los paseos aleatorios y el algoritmo de recocido simulado .

Cordilleras y gargantas

Las crestas son un problema difícil de escalar cuando se optimiza en un espacio continuo. Dado que el ascenso cambia solo un elemento del vector a la vez, cada paso solo cambia en la dirección de los ejes numéricos. Si la función objetivo forma una cresta estrecha que crece en una dirección distinta a los ejes de coordenadas (en el caso de la minimización, la función forma un desfiladero estrecho que disminuye en una dirección diferente a los ejes de coordenadas), entonces el ascenso puede zigzaguear por la cresta (o descender el desfiladero). Si las laderas de la arista (o desfiladero) son muy empinadas, el ascenso puede verse obligado a realizar pasos en zigzag muy pequeños, lo que puede ocasionar un tiempo innecesariamente largo para subir por la arista (o descender el desfiladero).

Los métodos de descenso de gradiente, por otro lado, pueden moverse en la dirección en que sube una cresta o desciende un barranco. Por lo tanto, el descenso del gradiente o el método del gradiente conjugado serán más preferibles si la función objetivo es diferenciable. Escalar, sin embargo, tiene la ventaja de no requerir diferenciabilidad, por lo que escalar puede ser preferible cuando la función objetivo es compleja.

Meseta

Otro problema que a veces surge al escalar es una meseta. Una meseta ocurre cuando la superficie es lo suficientemente plana como para que los valores de la función objetivo sean indistinguibles de los valores de los nodos cercanos debido a las limitaciones de la precisión computacional de la máquina. En tales casos, el algoritmo de escalada no puede elegir la dirección del movimiento y puede ir en una dirección que no conduzca a una mejora en la función objetivo.

Pseudocódigo

Algoritmo de escalada en espacio discreto nodoActual = NodoInicio; bucle hacer L = VECINOS (NodoActual); nextEval = -INF; siguienteNodo = NULL; para todo x en L si (EVAL(x) > nextEval) siguienteNodo = x; nextEval = EVAL(x); si siguienteEval <= EVAL(nodoActual) //Devolver el nodo actual ya que no hay mejor nodo volver NodoActual; actualNodo = siguienteNodo; Algoritmo de escalada en espacio continuo puntoActual = PuntoInicial; // generalmente usa un vector de longitud cero stepSize = initialStepSizes; // usualmente usamos un vector de unos aceleración = algunaAceleración; // normalmente usa el valor 1.2 candidato[0] = -aceleración; candidato[1] = -1 / aceleración; candidato[2] = 0; candidato[3] = 1 / aceleración; candidato[4] = aceleración; bucle hacer antes = EVAL(puntoActual); para cada elemento i en currentPoint do mejor = -1; mejorpuntuación = -INF; para j de 0 a 4 // intenta iterar sobre cada uno de los 5 candidatos puntoActual[i] = PuntoActual[i] + tamañopaso[i] * candidato[j]; temp = EVAL(PuntoActual); puntoActual[i] = PuntoActual[i] - StepSize[i] * candidato[j]; si (temp > mejor puntuación) mejorpuntuación=temp; mejor = j; si el candidato [mejor] es 0 tamaño de paso[i] = tamaño de paso[i] / aceleración; más currentPoint[i] = currentPoint[i] + stepSize[i] * candidato[mejor]; stepSize[i] = stepSize[i] * candidato[mejor]; // acelerar if (EVAL(puntoActual) - antes) < epsilon volver PuntoActual;

Véase también

descenso de gradiente
Algoritmo codicioso
mano invisible
Desplazamiento promedio

Notas

↑ Skiena, 2010 , pág. 253.

Literatura

Stuart J. Russell, Peter Norvig. Inteligencia artificial: un enfoque moderno. - Upper Saddle River, Nueva Jersey: Prentice Hall, 2003. - págs. 111-114.
Steven Skiena. Manual de diseño de algoritmos. — 2do. - Springer Science + Business Media , 2010. - ISBN 1-849-96720-2 .

El artículo se basa en material extraído del artículo del Free On-line Dictionary of Computing (FOLDOC) con licencia de la GFDL (versión 1.3) .

Enlaces

Algoritmos de búsqueda de gráficos
Métodos no informados	Búsqueda bidireccional Búsqueda de haz Primera búsqueda de amplitud lexicográfica Primera búsqueda en amplitud Buscar por criterio de costo Primera búsqueda en profundidad Búsqueda retrospectiva Buscar por subir a la cima Búsqueda limitada en profundidad Búsqueda en profundidad primero con profundización iterativa
Métodos informados	Recorte alfa beta Método de rama y límite Buscar por primera mejor coincidencia A* B* D* Encontrar un punto de transición AIF* Búsqueda recursiva en la primera mejor coincidencia SMA*
Atajos	Algoritmo de onda Algoritmo Bellman-Ford Algoritmo de Dijkstra Algoritmo de Johnson Algoritmo de Levit Algoritmo de Floyd-Warshall Búsqueda de borde
Árbol de expansión mínimo	Algoritmo de Boruvka algoritmo de Prim Algoritmo de Kruskal
Otro	Algoritmo del Museo Británico Algoritmo de Edmonds recorrido del árbol Algoritmo del vecino más cercano en el problema del viajante de comercio

Métodos de optimización
unidimensional	método de la sección áurea Dicotomía método de parábola búsqueda de cuadrícula Método de búsqueda de bloque uniforme método fibonacci búsqueda ternaria método Piyavsky Método Strongin
orden cero	método de Gauss Método Nelder-Mead Método Hook-Jeeves método de Rosenbrock metodo powell
Primer orden	descenso de gradiente método Zeutendijk Descenso coordinado método de gradiente conjugado Métodos Cuasi-Newtonianos Algoritmo de Levenberg-Marquardt
segundo orden	método de newton Método de Newton-Raphson Algoritmo de Broyden-Fletcher-Goldfarb-Shanno (BFGS)
estocástico	Método de Montecarlo recocido simulado Algoritmos evolutivos evolución diferencial Algoritmo de hormiga método de enjambre de partículas Algoritmo de colonia de abejas Método de paseo aleatorio
Métodos de programación lineal	método símplex algoritmo de gomori método elipsoide método potencial
Métodos de programación no lineal	Programación cuadrática secuencial