PDF de programación - Algoritmo Hill Climbing

Algoritmo Hill Climbing Ing. Bruno López Takeyas



ALGORITMO HILL CLIMBING



• También es 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



http://www.itnuevolaredo.edu.mx/takeyas Email: [email protected]

Algoritmo Hill Climbing Ing. Bruno López Takeyas

Escalada Simple

- Dirigirse siempre a un estado mejor

que el actual

- 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).



http://www.itnuevolaredo.edu.mx/takeyas Email: [email protected]

Algoritmo Hill Climbing Ing. Bruno López Takeyas

Ascenso a Colina (Hill Climbing)



• Es una variante del algoritmo de

búsqueda de Best First.

• Del procedimiento de prueba existe
una realimentación que ayuda al

generador a decidirse por

cual

dirección debe moverse en el espacio

de búsqueda.

• En estos procesos se abandona la
búsqueda si no existe un estado

alternativo razonable al que se pueda

mover.

• Los algoritmos de ascenso a colina son
típicamente locales, ya que deciden

qué hacer, mirando únicamente a las


http://www.itnuevolaredo.edu.mx/takeyas Email: [email protected]

Algoritmo Hill Climbing Ing. Bruno López Takeyas

consecuencias

inmediatas de

sus

opciones.

• Puede que nunca lleguen a encontrar
una solución, si son atrapados en

estados que no son el objetivo, desde

donde no se puede hallar mejores

estados, por ejemplo:



1. Un máximo local: Estado mejor que

sus vecinos pero no es mejor que otros

que están algo más alejados.

2. Una meseta: Es un espacio de

búsqueda en el que todo un conjunto de

estados vecinos tienen igual valor.

3. Un risco: que es un tipo especial de

máximo local, imposible de atravesar con

movimientos simples.



http://www.itnuevolaredo.edu.mx/takeyas Email: [email protected]

Algoritmo Hill Climbing Ing. Bruno López Takeyas



• Hay algunas

formas que pueden

ayudar a resolver estos problemas,

aunque no existe garantía:

1. Para evitar máximos locales, regresar

a un estado anterior y explorar en una

dirección diferente.

2. Para casos de mesetas, dar un salto

grande en alguna dirección y tratar de

encontrar una nueva sección del espacio

de estados.

3. Para los riscos, aplicar dos o más

reglas, antes de realizar una prueba del

nuevo estado, esto equivale a moverse en

varias direcciones a la vez.



http://www.itnuevolaredo.edu.mx/takeyas Email: [email protected]

Algoritmo Hill Climbing Ing. Bruno López Takeyas

• En todos

los casos anteriores, el

algoritmo llega un punto más allá del

cual no se logra ningún avance.

• Cuando esto sucede es obvio que debe

empezarse de nuevo en otro punto.

• Y esto es justamente lo que hace con
ascenso de cima con reinicio aleatorio,

efectúa una serie de búsquedas de

ascenso de cima desde estados

iniciales generados aleatoriamente,

hasta para o cuando no se logra

ningún avance significativo.

• Se guarda el mejor resultado que
hasta un momento dado se haya

obtenido en las diversas búsquedas.

• Puede usar un número

fijo de

iteraciones, o puede continuar hasta

que el mejor de

los

resultados


http://www.itnuevolaredo.edu.mx/takeyas Email: [email protected]

Algoritmo Hill Climbing Ing. Bruno López Takeyas

almacenados no haya sido mejorado

para cierta cantidad de iteraciones.



• Los algoritmos de ascenso a colina, a
pesar de explorar sólo un paso

adelante, al examinar el nuevo estado

pueden incluir una cierta cantidad de

información global codificada en la

función

objetivo

o

función

heurística.

Ventajas

• Reduce el número de nodos a analizar



http://www.itnuevolaredo.edu.mx/takeyas Email: [email protected]

Algoritmo Hill Climbing Ing. Bruno López Takeyas

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
la mejor, puesto que no es

no

exhaustivo.

• Es eficiente,

porque

evita

la

exploración de una parte del espacio

de estados.


http://www.itnuevolaredo.edu.mx/takeyas Email: [email protected]

Algoritmo Hill Climbing Ing. Bruno López Takeyas

Función de evaluación



Devuelve un número que representa qué
tan cerca está un determinado estado de
la solución, cuanto mayor sea el número,
se estará más cerca de la solución.



Ejemplo: Juego 8-puzzle

• Establecer una



función de



evaluación

f(nodo)= # de casillas bien

colocadas

(maximización)



http://www.itnuevolaredo.edu.mx/takeyas Email: [email protected]

Algoritmo Hill Climbing Ing. Bruno López Takeyas



http://www.itnuevolaredo.edu.mx/takeyas Email: [email protected]

Algoritmo Hill Climbing Ing. Bruno López Takeyas

A5

C4

B6

E5

F7

G6

H9

I6



D4



Representación del

Espacio de

Estados


http://www.itnuevolaredo.edu.mx/takeyas Email: [email protected]

A=[] ó
A=Obj

F

INICIO



V



(con valor más alto)



V


F



C=Almacenar
trayectoria
(hijo, padre)

S=Sucesor de A

V[S]

>
V[A]

Termina la

búsqueda con

éxito (Recorrer C)

Generar

aleatoriamente un

nuevo Estado

inicial

Algoritmo Hill Climbing Ing. Bruno López Takeyas

Algoritmo Hill Climbing

C=A=Estado inicial

S=[] (Vacío)



V

A = S


http://www.itnuevolaredo.edu.mx/takeyas Email: [email protected]