INTRODUCCION
En esta clases nos dimos cuenta que en
la búsqueda local (BL), se empieza de una configuración inicial (generalmente
aleatoria) y se hacen pequeños cambios (a través de operadores) hasta alcanzar
un estado desde el cual no se puede alcanzar ningún estado mejor. Las técnicas
de BL son propensas a encontrar óptimos locales que no son la mejor solución
posible. El óptimo global es generalmente imposible de alcanzar en un tiempo
limitado, por el tamaño del espacio de soluciones.
MARCO TEORICO
Algoritmos de búsqueda local y problemas de optimización
Los algoritmos de búsqueda local funcionan con un solo estado actual (más
que múltiples caminos) y generalmente se mueve solo a los vecinos del
estado. Típicamente, los caminos seguidos por la búsqueda no se
retienen. Aunque los algoritmos de búsqueda local no son sistemáticos,
tienen dos ventajas claves: usan muy poca memoria (por lo general una
cantidad constante) y pueden encontrar a menudo soluciones razonables en
espacios de estados grandes o infinitos (continuos) para los cuales son
inadecuados los algoritmos sistemáticos.
Además de encontrar los objetivos, los algoritmos de búsqueda local son útiles para resolver problemas de optimización puros, en los cuales el objetivo es encontrar el mejor estado según una función objetivo Muchos problemas de optimización no encajan en el modelo <estándar> de búsqueda.
Para entender la búsqueda local, encontraremos muy útil considerar la forma o el paisaje del espacio de estados.
El paisaje tiene <posición> (definido por el estado) y
<elevación> (definido por el valor de la función de coste
heurística o función objetivo). Si la elevación corresponde al costo,
entonces el objetivo es encontrar el valle más bajo (un mínimo global); si la elevación corresponde a una función objetivo, entonces el objetivo es encontrar el pico más alto (un máximo global) (Puedes
convertir uno en el otro solamente al insertar un signo menos.) Los
algoritmos de búsqueda local exploran este paisaje. Un algoritmo de
búsqueda local completo siempre encuentra un objetivo si existe; un
algoritmo optimo siempre encuentran un mínimo/máximo global.
Búsqueda de Ascensión de Colinas
El algoritmo de búsqueda de ascensión de colinas es
simplemente un bucle que continuamente se mueve en dirección del valor
creciente, es decir cuesta arriba. Termina cuando alcanza <un
pico> en donde ningún vecino tiene un valor más alto. El algoritmo no
mantiene un árbol de búsqueda, sino una estructura de datos del nodo
actual que necesita solo el registro del estado y su valor de función
objetivo. La ascensión de colinas no mira delante más allá de los
vecinos inmediatos del estado actual.
Búsqueda de Temple Simulado.
Un algoritmo de
ascensión de colinas que nunca hace movimientos <cuesta abajo>
hacia estados con un valor inferior (o coste más alto) garantiza ser
incompleto, porque puede estancarse en un máximo local. En contraste, un
camino puramente aleatorio, es decir moviéndose a un sucesor elegido
uniformemente aleatorio de un conjunto de sucesores, es completo, pero
sumamente ineficaz. Por lo tanto, parece razonable intentar combinar la
ascensión de colinas con un camino aleatorio de algún modo que produzca
tanta eficacia como completitud.
El bucle interno del algoritmo del temple simulado es bastante similar a la ascensión de colinas. En vez de escoger el mejor movimiento, sin embargo, escoge un movimiento aleatorio. Si
el movimiento mejora la situación, es siempre aceptado. Por otra parte,
el algoritmo acepta el movimiento con una probabilidad menor que uno.
La probabilidad se disminuye exponencialmente con la <maldad> de
movimiento (la cantidad ΔE por la que se empeora la evaluación). La
probabilidad también disminuye cuando <la temperatura> T baja: los
<malos> movimientos son más probables al comienzo cuando la
temperatura es alta, y se hacen más improbables cuando T disminuye. Uno
puede demostrar que si el esquema disminuye Tbastante despacio, el algoritmo encontrara un óptimo global con probabilidad cerca de uno.
Búsqueda por Haz Local
A primera vista, una
búsqueda por haz local con K estados podría parecerse a ejecutar K
reinicios aleatorios en paralelo en vez de en secuencia. De hecho, los
dos algoritmos son bastantes diferentes. En una búsqueda de reinicio
aleatorio, cada proceso de búsqueda se ejecuta independientemente de los
demás. En una búsqueda por haz local la información útil es pasada entre los k hilos paralelos de búsqueda. Por
ejemplo, si un estado genera varios sucesores buenos y los otros K-1
estados generan sucesores malos, entonces el efecto es que el primer
estado dice a los demás, <￡Venid aquí, la
hierba es más verde!> El algoritmo rápidamente abandona las búsquedas
infructuosas y mueve sus recursos a donde se hace la mayor parte del
progreso.
Algoritmos Genéticos
Un algoritmo genético (o AG) es una variante de la búsqueda de haz estocástica en la que los estados sucesores se generan combinando dos estados
padres, más que modificar un solo estado. La analogía a la selección
natural es la misma que con la búsqueda de haz estocástica, excepto que
ahora tratamos con reproducción sexual más que con la reproducción
asexual.
Como en la búsqueda de haz, los AGs comienzan con un conjunto de K estados generados aleatoriamente, llamados población Cada estado, o individuo está representado como una cadena sobre un alfabeto finito (el más común, una cadenas de 0s y 1s).
CONCLUSIÓN.
En conclision dieremos los métodos de búsqueda
local, como la ascensión de colinas, operan en formulaciones completas de
estados, manteniendo solo un número pequeño de no- dos en memoria.
BIBLIOGRAFÍA
Russell, S. y Norvig, P. 2004. INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO. PEARSON EDUCACION. 2 ed. Madrid.
No hay comentarios:
Publicar un comentario