ALGORITMO DE BÚSQUEDA LOCAL Y Problemas DE
OPTIMIZACIÓN
INTRODUCCIÓN.
En esta clase nos dimos cuenta que este
algoritmo de búsqueda local es muy eficiente ya que esta usa poca memoria a
comparación de otros algoritmos y así de esa manera encuentran la solución de
manera rápida, es decir usa una cantidad constante de memoria y encuentra
soluciones en estados grandes.
MARCO TEÓRICO
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.
A veces a la ascensión de colinas se le llama
búsqueda local voraz porque toma un estado vecino bueno sin pensar hacia donde
ir después. Aunque la avaricia sea considerada uno de los siete pecados
mortales, resulta que los algoritmos avaros a menudo funcionan bastante bien.
La ascensión de colinas a menudo hace el progreso muy rápido hacia una
solución, porque es por lo general bastante fácil mejorar un estado malo.
Lamentablemente, la ascensión de colinas a menudo se atasca por los motivos
siguientes:
Máximo local: un máximo local es un pico que es más alto que cada uno de
sus estados vecinos, pero más abajo que el máximo global. Los algoritmos de
ascensión de colinas que alcanzan la vecindad de un máximo local irán hacia el
pico, pero entonces se atascaran y no podrán ir a ninguna otra parte.
Crestas: las crestas causan una secuencia de máximos locales que hace
muy difícil la navegación para los algoritmos avaros.
Meseta una meseta es un área del paisaje del espacio de estados donde la
función de evaluación es plana. Puede ser un máximo local plano, del que no
existe ninguna salida ascendente, o una tarraza por la que se pueda avanzar.
Una búsqueda de ascensión de colinas podría ser incapaz de encontrar su camino
en la meseta.
El éxito de la ascensión de colinas depende
muchísimo de la forma del paisaje del espacio de estados: si hay pocos máximos
locales y mesetas, la ascensión de colinas con reinicio aleatorio encontrara
una solución buena muy rápidamente.
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
Guardar solamente un nodo en la memoria
podría parecer una reacción extrema para el problema de limitaciones de
memoria. El algoritmo^10 de búsqueda por haz local guarda la pista de K estados
(no solo uno). Comienza con estados generados aleatoriamente. En cada paso, se
generan todos los sucesores de los K estados. Si alguno es un objetivo, paramos
el algoritmo. Por otra parte, se seleccionan los K mejores sucesores de la
lista completa y repetimos.
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.
No usan mucha memoria a diferencias de los
otros métodos, los métodos de búsqueda
local mantienen sólo un número pequeño de nodos en memoría. Los algoritmos de
búsqueda local Inician con una solución inicial generada aleatoriamente, o
hallada con algún otro algoritmo.
BIBLIOGRAFÍA
Russell, S. y Norvig, P. 2004. INTELIGENCIA
ARTIFICIAL. UN ENFOQUE MODERNO. PEARSON EDUCACION. 2 ed. Madrid.
