🌸 1.8.3 ALGORITMOS DE BÚSQUEDA LOCAL
Fundamento teórico
Los algoritmos de búsqueda local son técnicas utilizadas para encontrar soluciones aproximadas a problemas complejos mediante la exploración de soluciones vecinas, mejorando progresivamente una solución inicial hasta encontrar una opción satisfactoria u óptima.
A diferencia de otros algoritmos que exploran múltiples caminos, estos trabajan sobre una solución actual y realizan cambios pequeños para mejorarla.
Son ampliamente utilizados en Artificial Intelligence, optimización, robótica y análisis computacional.
1. Teoría de optimización
Los algoritmos de búsqueda local se basan en la optimización matemática, cuyo objetivo es encontrar la mejor solución posible dentro de un conjunto de alternativas.
Buscan:
- Minimizar costos
- Maximizar beneficios
- Mejorar eficiencia
- Optimizar recursos
👉 Su propósito es acercarse a la mejor solución.
2. Espacio de estados
Trabajan dentro de un conjunto de soluciones posibles llamado espacio de estados.
Cada estado representa una solución candidata.
El algoritmo:
- Evalúa la solución actual
- Explora estados vecinos
- Se mueve hacia una mejor solución
👉 La búsqueda se realiza localmente alrededor del estado actual.
3. Heurística
Utilizan funciones heurísticas para determinar qué tan buena es una solución.
Estas funciones permiten:
- Comparar alternativas
- Guiar la mejora progresiva
- Reducir tiempo computacional
👉 Facilitan decisiones rápidas y eficientes.
4. Racionalidad limitada – Herbert A. Simon
Simon plantea que en problemas complejos no siempre es posible encontrar la solución perfecta.
Por ello, se busca una solución suficientemente buena.
👉 Los algoritmos locales priorizan eficiencia práctica.
5. Inteligencia artificial
En inteligencia artificial, estos algoritmos son útiles cuando:
- El espacio de búsqueda es muy grande
- La solución exacta es costosa
- Se requiere rapidez
👉 Son ideales para problemas reales complejos.
Funcionamiento básico
Los algoritmos de búsqueda local siguen este proceso:
- Generar solución inicial
- Evaluar calidad
- Explorar soluciones vecinas
- Seleccionar mejor alternativa
- Repetir hasta encontrar mejora suficiente
Tipos principales
Búsqueda ascendente (Hill Climbing)
Avanza hacia soluciones cada vez mejores.
Ventaja: rapidez
Desventaja: puede quedarse en óptimos locales
Temple simulado (Simulated Annealing)
Permite aceptar soluciones peores temporalmente para evitar estancamiento.
👉 Mejora exploración.
Búsqueda tabú
Evita repetir soluciones ya evaluadas.
👉 Reduce ciclos innecesarios.
Algoritmos genéticos
Se inspiran en evolución biológica.
Usan:
- Selección
- Cruce
- Mutación
👉 Generan soluciones mejoradas progresivamente.
Ventajas
- Menor consumo computacional
- Alta velocidad
- Útiles en problemas grandes
- Flexibles
Desventajas
- No siempre encuentran solución óptima
- Pueden estancarse
- Dependen de buena heurística
Aplicaciones
- Optimización de rutas
- Diseño de redes
- Planeación logística
- Asignación de recursos
- Aprendizaje automático
Video explicativo:
Practica:
Actividad: Optimización de ruta escolar
Diseñar varias rutas para llegar a la universidad.
Comparar:
- Tiempo
- Distancia
- Consumo de recursos
Elegir la mejor usando búsqueda local.
📄 Ver práctica en PDF
Evaluación
- ¿Qué es búsqueda local?
- ¿Qué diferencia tiene con búsqueda global?
- ¿Qué es un óptimo local?
- ¿Qué ventajas tiene?
- ¿Dónde se aplica?
Conclusion:
Los algoritmos de búsqueda local son métodos heurísticos que mejoran soluciones de manera progresiva explorando alternativas cercanas, siendo herramientas esenciales para resolver problemas complejos de optimización e inteligencia artificial.
Referencias APA 7
- Stuart Russell, S., & Peter Norvig, P. (2021). Artificial intelligence: A modern approach (4th ed.). Pearson.
- Herbert A. Simon. (1957). Models of man: Social and rational. Wiley.
- Aarts, E., & Korst, J. (1988). Simulated annealing and Boltzmann machines. Wiley.
- Glover, F., & Kochenberger, G. A. (2003). Handbook of metaheuristics. Springer.
- Pearl, J. (1984). Heuristics: Intelligent search strategies for computer problem solving. Addison-Wesley.
Etiquetas: Heuristica, IA, Unidad1