Búsqueda local
Dr. Omar Mendoza Montoya
14/09/2021
Búsqueda local
• En los algoritmos de búsqueda de árbol y búsqueda de grafo, se explora el
espacio de búsqueda de manera sistemática, y se intenta determinar una
secuencia de acciones que solucione un problema dado.
• En ambos casos, se mantiene en memoria la estructura completa de la
búsqueda, ya que la secuencia de acciones es importante para la solución.
• En algunas situaciones, el camino desde el estado inicial hasta el estado
solución (secuencia de acciones) no es importante. El estado final o estado
solución es lo único que es relevante en la solución de muchos problemas de
búsqueda.
• En el caso del problema de las 8 reinas, no importa cómo se van poniendo las
piezas en el tablero, la posición final de las reinas es lo que es de interés.
2
Búsqueda local
• En búsqueda local, se opera sobre un solo nodo, y se realizan
movimientos a uno de los estados vecinos en el espacio de
búsqueda.
• Una posible estrategia de búsqueda local consiste en seleccionar
un estado inicial válido, y comenzar a seleccionar de manera
aleatoria el siguiente estado (caminata aleatoria).
3
• Existen dos tipos de problemas en los
cuales se suele utilizar búsqueda local:
Búsqueda local • Búsqueda de raíces de ecuaciones.
• Optimización.
4
Búsqueda de raíces de ecuaciones
• Una raíz de una función real 𝑓(𝑥) ∈ 𝑅𝑛 es un vector de números
reales 𝑥𝑟 ∈ 𝑅𝑚 para el cual 𝑓 𝑥𝑟 = 0.
Raíces
• Este problema puede formularse para espacios complejos.
5
Búsqueda de raíces de ecuaciones
Raíz
Estimación
inicial
6
Raíces de
ecuaciones
Algoritmos de Univariado Multivariado
búsqueda de Newton-
raíces de
Bracketing De un punto
Raphson
ecuaciones con Bisección
Newton-
Raphson Broyden
variables Falsa
Halley
continuas posición
Brent Secante
Newton-
Ridders
Bisección
7
Optimización
• Optimización es el proceso de encontrar soluciones óptimas.
• Problemas de optimización pueden ser encontrados en muchas
áreas:
• Ciencias naturales.
• Matemáticas.
• Ciencias de la computación.
• Economía.
• Ingeniería.
• Modelado matemático (modelos parametrizados):
• Aprendizaje estadístico y automatizado.
• Inteligencia artificial.
• Aprendizaje profundo
8
Optimización
• Un mínimo global de una función real 𝑓(𝑥) ∈ 𝑅 es un vector de valores reales
𝑥 ∗ ∈ 𝑅𝑛 para los cuales 𝑓 𝑥 ∗ ≤ 𝑓 𝑥 para toda 𝑥.
• Un máximo global de una función real 𝑓(𝑥) ∈ 𝑅 es un vector de valores reales
𝑥 ∗ ∈ 𝑅𝑛 para los cuales 𝑓 𝑥 ∗ ≥ 𝑓 𝑥 para toda 𝑥.
• Un mínimo local de una función real 𝑓(𝑥) ∈ 𝑅 es un vector de valores reales
𝑥 ∗ ∈ 𝑅𝑛 para los cuales 𝑓 𝑥 ∗ ≤ 𝑓 𝑥 para toda 𝑥 en la vecindad de 𝑥 ∗ .
• Un máximo local de una función real 𝑓(𝑥) ∈ 𝑅 es un vector de valores reales
𝑥 ∗ ∈ 𝑅𝑛 para los cuales 𝑓 𝑥 ∗ ≥ 𝑓 𝑥 para toda 𝑥 en la vecindad de 𝑥 ∗ .
• 𝑓(𝑥) usualmente es llamada función objetivo.
9
Optimización
Fuente: Artificial intelligence: A modern approach
10
Optimización
continua
Univariada Multivariada
Algoritmos de
optimización
local en espacios
Sección Brent con 1ra
Brent
dorada derivadas
continuos
Descenso de Quasi- Gradiente
Newton
gradiente Newton conjugado
11
Optimización con
restricciones
Optimización Programación Programación Métodos no Restricciones
con restricciones lineal cuadrática lineales de caja
en espacios
continuos Punto Gradiente
Simplex Elipsoide Interior point
interior proyectado
12
Optimización en espacios discretos
• Problemas NP.
• El óptimo global requiere de métodos de búsqueda exhaustiva.
• La búsqueda heurística puede reducir considerablemente el costo
computacional y los requerimientos de memoria.
• Algunas heurísticas garantizan una solución óptima para ciertos
problemas. Sin embargo, por lo general, aproximan la solución.
• Familias de heurísticas que comparten características similares y se
derivan de una misma idea se conocen como metaheurísticas.
13
Algoritmo hill climbing
• El algoritmo hill climbing (búsqueda voraz) es un algoritmo que continuamente se
mueve en la dirección que mejora el valor actual.
• Hay muchas formas de búsqueda voraz.
• En optimización en espacios continuos, el método de ascenso de gradiente
(steepest-ascent) es un ejemplo de búsqueda voraz.
• Este algoritmo suele llamarse búsqueda codiciosa local ya que continuamente
selecciona un buen vecino sin pensar en lo que sigue después.
• Otra versión de este algoritmo consistiría en escoger algún vecino de manera
aleatoria, y si el vecino mejora la solución actual, se mueve en la dirección del
vecino. Si no mejora la solución, simplemente se escoge otro posible vecino.
14
Recocido simulado
Evolución diferencial
(DE)
Metaheurísticas
(optimización Metaheurísticas
Algoritmo genético
global)
(GA)
Estrategias
evolucionarias (ES)
Optimización de enjambre
de partículas (PSO)
15
Metaheurísticas
• Una heurística es cualquier • Una metaheurística es un marco de
aproximación a la solución de un referencia algorítmico de alto nivel
problema que emplea un método independiente de un problema que
práctico que no garantiza ser óptimo, proporciona los lineamientos para
perfecto o racional, sin embargo, es desarrollar heurísticas para
suficiente para alcanzar el objetivo a problemas de optimización
corto plazo. (Wikipedia). (Scholarpedia).
16
Metaheurísticas
Búsqueda exhaustiva Heurísticas y metaheurísticas Optimización determinística
Caminata aleatoria Recocido simulado Descenso de gradiente
Algoritmos evolucionarios Newton
Enjambre de partículas Quasi-Newton
No se asume nada sobre el Más supuestos (convexidad,
problema diferenciabilidad, continuidad)
Robusto Alta sensibilidad
Alto costo computacional Eficientes
computacionalmente
17
Recocido simulado
• Un algoritmo que nunca hace movimientos en la dirección que empeora la
solución, está garantizado en que es incompleto, ya que se puede llevar a
óptimos locales fácilmente.
• En contraste, una caminata aleatoria es completa pero extremadamente
ineficiente.
• Recocido simulado (simulated annealing) es una metaheurística para
minimización que combina ambas estrategias. Es decir, permite realizar
movimientos que no necesariamente mejoran la solución actual, pero que a
la larga podrían permitir una mejor solución.
• Usualmente este algoritmo es útil para espacios discretos.
18
Recocido simulado
• En metalurgia, recocido es
el proceso para templar y
endurecer metales y vidrio a
través de calentar dichos
materiales a altas
temperaturas, para
posteriormente enfriarlos
gradualmente, permitiendo
que el material alcance un
estado cristalino de baja
energía.
19
Recocido simulado
• En este método, es necesario considerar una función objetivo (función de costo)
que permite evaluar posible soluciones (estados) de un algoritmo de búsqueda.
• Se comienza en un estado inicial s.
• En cada iteración de la heurística, se considera algún estado vecino s* del estado
actual s, y se decide probabilísticamente mover el sistema al estado s* o
permanecer en s.
• Las probabilidades de elegir un estado nuevo descienden conforme se avanza con
las iteraciones.
• Al final, se queda con un estado que sea lo suficientemente para una aplicación.
20
Recocido simulado
temperature(𝑣) = Esquema de recocido (temperatura en un instante 𝑣).
𝐸(𝑠) = Energía del estado 𝑠 (función de costo)
𝑝(𝐸1 , 𝐸2 , 𝑇)= Probabilidad de aceptar el estado 𝐸2 al pasar de un estado 𝐸1 para
un valor de temperatura 𝑇
Define initial state 𝑠
Define number of iterations 𝑘𝑚𝑎𝑥
for 𝑘 = 1 to 𝑘𝑚𝑎𝑥
T = temperature 𝑘ൗ𝑘𝑚𝑎𝑥
pick random neighbor 𝑠𝑛𝑒𝑤 =neighbor 𝑠
if 𝑝 𝐸 𝑠𝑛𝑒𝑤 , 𝐸 𝑠 , 𝑇 ≥ random(0,1) then 𝑠 = 𝑠𝑛𝑒𝑤
21
Recocido simulado
• El algoritmo comienza con un alto valor de temperatura, y
posteriormente dicha temperatura desciende de acuerdo a un
esquema de recocido.
• El esquema usualmente se selecciona de acuerdo a las
características del problema a resolver.
• Es importante tomar en consideración de que la probabilidad de
que el algoritmo termine en la solución global es 1 si se extiende
indefinidamente el esquema de recocido.
22
Recocido simulado
• Una opción común para la función de probabilidad de aceptación
es:
𝐸 −𝐸
− 2𝑇 1
𝑝(𝐸1 , 𝐸2 , T) = 𝑒
• Esta fórmula está justificada con la analogía que tiene en el
enfriamiento de sistemas físicos.
23
Bibliografía
• Artificial intelligence: a modern approach. Stuart J. Russell and Peter
Norvig. 3ra edición, 2015, Person. Capítulo 4, páginas: 120-133.
• Artificial intelligence with Python. Alberto Artasanchez and Prateek
Joshi. 2da edición, 2020, Pack. Capítulo 11.
• Simulated annealing:
https://en.wikipedia.org/wiki/Simulated_annealing
• Metaheuristics: http://www.scholarpedia.org/article/Metaheuristics
24
