Búsqueda, Optimización y Aprendizaje

Eduardo Morales

• • Objetivo General (archivo en PDF)
  • Temario
  • Bibliografía
  • Evaluación (archivo en PDF de la primera tarea)
  
  
• 1. Búsqueda (archivo en PDF de la primera tarea)
  • 1.1 Ejemplos e Ideas
  • 1.2 Optimización vs. Satisfacción de Restricciones
  • 1.3 Representación
  • 1.4 Representación Basada en Estados vs. Reducción de Problemas
  
  
• 2. Procedimientos de Búsqueda Clásicos (archivo en PDF)
  • 2.1 Introducción
  • 2.2 Búsqueda ciega o sin información
    • 2.2.1 Breadth-first search (búsqueda a lo ancho)
      • 2.2.1.1 Búsqueda de Costo Uniforme
    • 2.2.2 Depth-first o Búsqueda en Profundidad (LIFO)
      • 2.2.2.1 Backtracking
      • 2.2.2.2 Búsqueda con Profundidad Limitada (depth-limited)
      • 2.2.2.3 Búqueda de Profundidad Iterativa (iterative o progressive deepening)
    • 2.2.3 Búsqueda Bidireccional
    • 2.2.4 Evitando Estados Repetidos
    • 2.2.5 Búsqueda en grafos AND/OR
  • 2.3 Búsqueda con Información
    • 2.3.1 Hill-Climbing
    • 2.3.2 Best-First
    • 2.3.3 GBF (o BF para grafos AND/OR)
    • 2.3.4 Híbridos
    • 2.3.5 Beam-Search
    • 2.3.6 Mejor Solución
    • 2.3.7 Branch and Bound
    • 2.3.8 Dynamic Programming
    • 2.3.9 A$^*$ (Minimizando el costo total del camino)
    • 2.3.10 Extensiones
      • 2.3.10.1 IDA$^*$
      • 2.3.10.2 A$_{\epsilon }^*$
      • 2.3.10.3 MA$^*$
      • 2.3.10.4 SMA$^*$
      • 2.3.10.5 Mejoras Dinámicas
  • 2.4 Cómo Inventar Heurísticas
  • 2.5 Satisfacción de Restricciones
  • 2.6 Búsqueda en Lisp y Prolog
  • 2.7 MACRO-Operadores
  
  
• 3. Juegos (archivo en PDF)
  • 3.1 Introducción
  • 3.2 MiniMax
    • 3.2.1 Tamaño de Búsqueda
    • 3.2.2 Algoritmo Minimax
    • 3.2.3 Alternativas
  • 3.3 Alpha-Beta
    • 3.3.1 Algoritmo Alfa-Beta
    • 3.3.2 Análisis
  • 3.4 SSS$^*$ (Stockman 79)
  • 3.5 SCOUT (Pearl 80)
  • 3.6 Estrategias de Juego
  • 3.7 Juegos con eventos externos
  • 3.8 Hombres vs. Máquinas
  
  
• 4. Búqueda Local y Variantes (archivo en PDF)
  • 4.1 Introducción
  • 4.2 Búsqueda Local (Local Search)
    • 4.2.1 Fast Local Search
    • 4.2.2 Random Restart y Multistart Methods
    • 4.2.3 Guided Local Search
      • 4.2.3.1 Búsqueda local en TSP
      • 4.2.3.2 Búsqueda local guiada en TSP
  • 4.3 Variable Neighbourhood Search
  • 4.4 Búsqueda Local Iterativa (Iterated local search)
  • 4.5 Greedy Randomized Adaptive Search (GRASP)
  
  
• 5. Búsqueda Tabú (archivo en PDF)
  • 5.1 Introducción
  • 5.2 Algoritmo
  • 5.3 Niveles de Aspiración
  • 5.4 Intensificación y Diversificación
  • 5.5 The Reactive Tabu Search
  • 5.6 Continuous RTS
    • 5.6.1 Optimizador Local (Affine Shaker)
    • 5.6.2 Búsqueda por regiones
  
  
• 6. Recocido Simulado (archivo en PDF)
  • 6.1 Introducción
  • 6.2 Algoritmo de Metropolis
  • 6.3 Recocido Simulado
  • 6.4 Convergencia Asintótica y Cadenas de Markov
  • 6.5 Aproximaciones
  • 6.6 Implementación
  • 6.7 Paralelización
  • 6.8 Variantes
  
  
• 7. Redes Neuronales en optimización combinatoria (archivo en PDF)
  • 7.0.1 Historia
  • 7.1 Máquinas de Boltzmann
    • 7.1.1 Máquinas de Boltzmann Secuenciales
    • 7.1.2 Máquinas de Boltzmann Paralelas
    • 7.1.3 Estrategia para usar Máquinas de Boltzmann en problemas de optimización combinatoria
    • 7.1.4 Ejemplo: el problema de Max Cut
    • 7.1.5 Discusión
  • 7.2 Redes de Hopfield
  • 7.3 Mapas autorganizados de Kohonen
  
  
• 8. Scatter Search y Path Relinking (archivo en PDF)
  • 8.1 Scatter Search
  • 8.2 Path Relinking
  
  
  • 9. Algoritmos Genéticos (archivo en PDF)
    • 9.1 Introducción
      • 9.1.1 Programación Evolutiva
      • 9.1.2 Estrategias Evolutivas
      • 9.1.3 Algoritmos Genéticos
    • 9.2 Anatomía de un GA
    • 9.3 Algoritmo Básico
    • 9.4 El teorema de esquemas
    • 9.5 Puntos a considerar en GA
    • 9.6 GA para Cambiar Parámetros
    • 9.7 GA para Cambiar Estructuras de Datos
    • 9.8 GA para Cambiar Código
      • 9.8.1 The Pitt Approach
      • 9.8.2 Michigan approach
      • 9.8.3 XCS: sistema clasificador genético
      • 9.8.4 Otros aspectos a considerar
      • 9.8.5 Programación Genética
      • 9.8.6 Conocimiento del dominio
      • 9.8.7 Otros temas
    • 9.9 Algoritmos Meméticos
    • 9.10 Poblaciones Estadísticas
      • 9.10.1 PBIL (Population-based Incremental Learning)
      • 9.10.2 BOA: The Bayesian Optimization Algorithm
    
    
  • 10. Optimización basada en Colonia de Hormigas (archivo en PDF)
    • 10.1 Introducción
    • 10.2 TSP y el Ant System
    • 10.3 Extensiones
    
    
  • 11. Aprendizaje por Refuerzo (archivo en PDF)
    • 11.1 Introducción
      • 11.1.1 Modelos de Comportamiento Óptimo
      • 11.1.2 Recompensa diferida y modelo Markoviano
    • 11.2 Métodos de Solución de MDPs
      • 11.2.1 Programación Dinámica
      • 11.2.2 Monte Carlo
      • 11.2.3 Diferencias Temporales (Temporal Difference)
    • 11.3 Trazas de Elegibilidad (eligibility traces)
    • 11.4 Planeación y Aprendizaje
    • 11.5 Generalización en Aprendizaje por Refuerzo
    • 11.6 Aplicaciones a Juegos y Control
    • 11.7 Algunos desarrollos recientes
    
    
  • About this document ...