7/18/2019 Algoritmos de Búsqueda Local y Problemas de Optimización

http://slidepdf.com/reader/full/algoritmos-de-busqueda-local-y-problemas-de-optimizacion-56967071547dd 1/10

 

ESCUELA SUPERIOR POLITÉCNICA AGROPECUARIA DEMANABÍ MANUEL FÉLIX LÓPEZ

CARRERA INFORMÁTICA

SEMESTRE SÉPTIMO PERÍODO ABRIL-SEPT/2015

TEMA:

ALGORITMOS DE BÚSQUEDA LOCAL Y PROBLEMAS DEOPTIMIZACIÓN

MATERIA:

INTELIGENCIA ARTIFICIAL II

AUTORA:

LUISA KATERINE FARIAS CHICA

FACILITADORA:

ING. HIRAIDA SANTANA

MISIÓN

Formación de profesionales íntegros que conjuguen ciencia, tecnología y valores ensu accionar, comprometidos con la sociedad en el manejo adecuado de programas

y herramientas computacionales de última generación.

VISIÓN

Ser referente en la formación de profesionales de prestigio en el desarrollo deaplicaciones informáticas y soluciones de hardware.

CALCETA, JUNIO 2015

7/18/2019 Algoritmos de Búsqueda Local y Problemas de Optimización

http://slidepdf.com/reader/full/algoritmos-de-busqueda-local-y-problemas-de-optimizacion-56967071547dd 2/10

 

La clase impartida en este día ayudo a despejar muchasdudas ya que notamos que los algoritmos de búsquedas sehan diseñado para explorar los espacios de búsquedas estase consigue manteniendo uno o más caminos en memoria yregistrando que alternativas se van explorando en cadapunto es por eso que le vamos hablar acerca de losalgoritmos de búsqueda local y problemas de optimización. 

Entender los algoritmos de búsqueda locales y problemas deoptimización.

 

7/18/2019 Algoritmos de Búsqueda Local y Problemas de Optimización

http://slidepdf.com/reader/full/algoritmos-de-busqueda-local-y-problemas-de-optimizacion-56967071547dd 3/10

 

Los algoritmos de búsqueda que hemos visto hasta ahora sediseñan para explorar sistemáticamente espacios debúsqueda. Esta forma sistemática se alcanza manteniendouno o más caminos en memoria y registrando que alternativasse han explorado en cada punto a lo largo del camino ycuáles no. Cuando se encuentra un objetivo, el camino a eseobjetivo también constituye una solución al problema.

Estos algoritmo de búsqueda local se pueden llegar aentender mejor con el siguiente gráfico.

Funcionan con un

solo estado actual

•Generalmente se

mueve solo a los

vecinos de

estado.

•No son

sistemáticos

Ventajas

•Usan muy poca

memoria

•Encuentran

soluciones enespacios de

estado grandes e

infinitos

Utilidad

•Para resolver

problemas de

optimización,

buscando la

mejor función

objetivo

7/18/2019 Algoritmos de Búsqueda Local y Problemas de Optimización

http://slidepdf.com/reader/full/algoritmos-de-busqueda-local-y-problemas-de-optimizacion-56967071547dd 4/10

•  Paisaje de espacio de estados: Tiene elevación y

posición•  Mínimo global: Si la elevación corresponde al costo,

entonces el objetivo es encontrar el valle más bajo

•  Máximo global: la función objetivo es encontrar el picomás alto

Un paisaje del espacio de estados unidimensional en el cualla elevación corresponde a la función objetivo. El objetivo es

encontrar el máximo global. La búsqueda de ascensión decolinas modifica el estado actual para tratar de mejorarlo,como se muestra con la flecha. Se definen en el texto variosrasgos topográficos.

A veces a la ascensión de colinas se le llama búsqueda localvoraz porque toma un estado vecino bueno sin pensar haciadonde ir después. Aunque la avaricia sea considerada uno

7/18/2019 Algoritmos de Búsqueda Local y Problemas de Optimización

http://slidepdf.com/reader/full/algoritmos-de-busqueda-local-y-problemas-de-optimizacion-56967071547dd 5/10

de los siete pecados mortales, resulta que los algoritmosavaros a menudo funcionan bastante bien.

La ascensión de colinas a menudo hace el progreso muyrápido hacia una solución, porque es por lo general bastantefácil mejorar un estado malo. Por ejemplo, desde el estado dela Figura 4.12(a), se realizan solamente cinco pasos para

alcanzar el estado de la Figura 4.12 (b), que tiene h= 1 y escasi una solución.

Lamentablemente, la ascensión de colinas a menudo se

atasca por los motivos siguientes:

7/18/2019 Algoritmos de Búsqueda Local y Problemas de Optimización

http://slidepdf.com/reader/full/algoritmos-de-busqueda-local-y-problemas-de-optimizacion-56967071547dd 6/10

 

 

Es un algoritmo voraz, que no mantiene un árbol de

búsqueda, sino sólo la representación del estado actualy el valor de su función objetivo. Mantiene unaestructura de datos del nodo actual que necesita sólo elregistro del estado y su valor de función objetivo.

 

No se mira más allá de los vecinos inmediatos del estadoactual.

 

Escoge el vecino que tiene un mejor valor de la funciónobjetivo.

 

Finaliza cuando alcanza un "extremo" (máximo o

mínimo, depende del pateamiento)

Para templar o endurecer metales y cristales calentándolos a

una temperatura alta y luego gradualmente enfriarlos, así

7/18/2019 Algoritmos de Búsqueda Local y Problemas de Optimización

http://slidepdf.com/reader/full/algoritmos-de-busqueda-local-y-problemas-de-optimizacion-56967071547dd 7/10

permite al material fundirse en un estado cristalino de energíabaja.

Guardar solamente un nodo en la memoria podría pareceruna reacción extrema para el problema de limitaciones dememoria. El algoritmo10 de búsqueda por ha* local guarda lapista de /estados (no solo uno). Comienza con estadosgenerados aleatoriamente. En cada paso, se generan todoslos sucesores de los /estados. Si alguno es un objetivo,paramos el algoritmo.

7/18/2019 Algoritmos de Búsqueda Local y Problemas de Optimización

http://slidepdf.com/reader/full/algoritmos-de-busqueda-local-y-problemas-de-optimizacion-56967071547dd 8/10

Sólo se consideran los descendientes cuya función deestimación es mejor que la del padre (poda del espacio debúsqueda)., que se puede usar una pila y guardar los hijosmejores que el padre para poder volver atrás, pero en

general el coste es prohibitivo.

Es un algoritmo de ascensión de colinas estocástica queelegimos un sucesor de entre todos los posibles según unadistribución de probabilidad y el sucesor puede ser peor, sehacen pasos aleatorios por el espacio de soluciones.

Se identifican los elementos del problema de búsqueda conlos del problema físico:• Temperatura: parámetro de control principal

• Energía:  función heurística sobre la calidad de la soluciónf(n)•  Función que determina la elección de un estado sucesor: F(Δf ,T), depende de la temperatura y la diferencia entre lacalidad de los nodos, a menor temperatura menorprobabilidad de elegir sucesores peores• Estrategia de enfriamiento: parámetros que determinan elnúmero de iteraciones de la búsqueda, disminución de la

temperatura y número de pasos para cada temperatura.

7/18/2019 Algoritmos de Búsqueda Local y Problemas de Optimización

http://slidepdf.com/reader/full/algoritmos-de-busqueda-local-y-problemas-de-optimizacion-56967071547dd 9/10

 

Los métodos de búsqueda local, como la ascensión decolinas, operan en formulaciones completas de estados,manteniendo solo un número pequeño de no- dos enmemoria en si estos algoritmos de búsqueda son simplementealgoritmos de búsquedas se han diseñado para explorar losespacios de búsquedas que se continúan manteniendo uno o

más caminos en memoria y registrando que alternativas sevan explorando en cada punto.

7/18/2019 Algoritmos de Búsqueda Local y Problemas de Optimización

http://slidepdf.com/reader/full/algoritmos-de-busqueda-local-y-problemas-de-optimizacion-56967071547dd 10/10

 

Russell, s.2008.inteligencia artificial un enfoque moderno.Segunda edición. Pearson education. Madrid-España

Macías, J 2013. ALGORITMO DE BÚSQUEDA DE ASCENSIÓN DECOLINAS. (En línea). EC. Consultado, 06 de junio. 2015.Formato PDF. Disponibleen: https://prezi.com/z135qjn4tnya/algoritmos-de-busqueda-local-y-problemas-de-optimizacion

Sanchez, L 2013. Métodos de búsqueda de soluciones. (Enlínea). EC. Consultado, 06 de junio. 2015. Formato PDF.Disponibleen: hhttp://www.sanchezcrespo.org/Docencia/IA/IA%20-%20Tema%203B%20-%20Busquedas%20v1.3.pdfttps://prezi.com/z135qjn4tnya/algor itmos-de-busqueda-local-y-problemas-de-optimizacion