ALGORITMO HILL CLIMBING

Bruno López T (2019), Expresa que el algoritmo Hill Climbing:

es también conocido como el método de ascenso de colinas

Usa una técnica de mejoramiento iterativo
Comienza a partir de un punto (punto actual) en el espacio de búsqueda
Si el nuevo punto es mejor, se transforma en el punto actual, si no, otro punto vecino es seleccionado y evaluado
El método termina cuando no hay mejorías, o cuando se alcanza un número predefinido de iteraciones.

Ascensión a colina

Según Skiena, S (2010) El algoritmo de ascensión en colina es una técnica de optimización matemática que pertenece a la familia de búsqueda local. Es un algoritmo interactivo que se inicia con un problema, a continuación, intenta encontrar la solución por incrementable que sea el cambio del elemento de la solución…

Tiene la capacidad de encontrar un óptimo local (una solución que no se puede mejorar teniendo en cuenta una configuración de vecino) pero no es necesariamente garantía de hallar la mejor solución posible (el óptimo global) de todos los posibles resultados (el espacio de búsqueda). En problemas convexos, en ascenso es óptima. Ejemplos de algoritmos que resuelven problemas convexos por bajada incluyen el algoritmo simplex para programación lineal y búsqueda binaria

Método de ascenso de colina

Inteligencia Artificial (2011), Afirma que es un método de búsqueda escalar que esta basado en la primera búsqueda a profundidad. La heurística es utilizada para mejorar la eficiencia de la búsqueda.

En cada paso, se puede estimar si una elección es probable que sea mejor que otro y el orden de las opciones en consecuencia.

Escalada Simple

– Dirigirse siempre a un estado mejor que el actual simple

– Función Heurística de proximidad

– No se mantiene reporte de los estados anteriores

– Es un método local, sus movimientos están determinados por ser mejores que los previos.

Escalada por máxima pendiente

Buscar no solamente un estado mejor que el actual, sino el mejor de todos los estados posibles (Máxima Pendiente).

Demostración:

Bruno López T (2019) Ejemplo: Juego 8-puzzle

• Establecer una función de evaluación (nodo)= # de casillas bien colocadas (maximización)

• Establecer una función de evaluación

Algoritmo:

1-Q forma un elemento de una cola que consiste en el nodo raíz.

2-Hasta que Q está vacía o el objetivo se ha alcanzado, determinar si el primer elemento de Q es la meta.

a) si lo es, no hacer nada.
b) si no es eliminar el elemento de Q, mas o menos los niños el primer elemento es, en su caso, mediante la estimación de la distancia restante y agregar esta lista ordenada al frente

3-si el objetivo es alcanzado, el éxito, el fracaso más.

Características

• Informado: Utiliza información del estado por elegir un nodo u otro.

• No exhaustivo: No explora todo el espacio de estados. Como máximo, sólo encuentra una solución.

• Encuentra buenas soluciones, pero no la mejor, puesto que no es exhaustivo.

• Es eficiente, porque evita la exploración de una parte del espacio de estados.

Ventajas

• Reduce el número de nodos a analizar

Desventajas

Inteligencia Artificial (2011) Las desventajas de esta técnica pueden visualizarse considerando la analogía escalada:

Local máximo: si el escalador se inicia en las faldas, se pasa mucho tiempo de subir a la cumbre de las estribaciones y la decepción de que no son el objetivo.

Mesetas: si comienza en una llanura en alguna parte va a vagar sin rumbo por comparación local no determinada la dirección puesta.

Riscos: si el se encuentra en la cima de la colina de suave pendiente, la mayoría de movimientos los llevara hacia abajo, pero él no está en la cumbre.

“Se trata de una búsqueda completa”

Buscar costo: con una búsqueda variable, ya que es imposible determinar lo que, en su caso, la mejora de la naturaleza desafía dicha evaluación.No optima: este algoritmo no necesariamente se encuentra la ruta más eficiente a través del espacio de estados.

Complejidad Computacional

(Cohen, Greiner, y Schuurmans, 1994). Dado que la evaluación que se utiliza sólo se fija en el estado actual, en escalada no sufre de problemas de espacio computacionales.

La fuente de su complejidad computacional surge del tiempo necesario para explorar el espacio del problema. Aleatorio-reinicio de escalada puede llegar a soluciones óptimas polinómica para la mayoría de los espacios de problemas…

aplicación

Según Cohen, Greiner, y Schuurmans, (1994) Colina de escalada puede aplicarse a cualquier problema donde el estado actual permite una función de evaluación precisa…Colina Escalada se ha utilizado en los modelos de aprendizaje inductivo.

Gerkey, Thrun, y Gordon, (2005) Su algoritmo permite robots para elegir si trabajar solo o en equipo mediante el uso de escalada. Robots ejecutoras Parroquia están, por tanto, “colectivamente bajadas de acuerdo con gradientes de progreso local, pero estocásticamente hacer movimientos laterales o hacia abajo para ayudar al escape del sistema de máximos locales.”