Métodos De Búsqueda Heuristica

Transcript

Tema 2: Métodos de búsqueda heurística • • • • • Búsqued Bús eda a sin in info forrmac ació ión n Métodos de escalada Bús Bú squed eda a pri rim mero el mej ejo or Des esc com omp posic ició ión n de de pro prob ble lem mas Heur He urís ísti tica cas s sob sobre re el pr proc oces eso o de de bús búsqu qued eda a Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística Búsqueda sin información • • • • Búsqueda en anchura Búsqueda en en pr profundidad Búsqueda con costos Pro Pr oble lem mas desc sco ompo pon nib ible les s Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística Búsqueda sin información • • • • Búsqueda en anchura Búsqueda en en pr profundidad Búsqueda con costos Pro Pr oble lem mas desc sco ompo pon nib ible les s Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística Sistemas de Búsqueda Operadores Base de Datos Estrategia de Control Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística Representación de un problema Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística Procedimiento Búsqueda 1. DATOS base de datos inicial 2. until DATOS satisface la condición de terminación do 3. begin 4. select alguna regla R en el conjunto de reglas que pueda ser aplicada a DATOS 5. DATOS resultado de aplicar R a DATOS 6. end Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística Estrategias de control • Estrategias irrevocables • Estrategias tentativas  – Retroactivas  – Búsqueda en grafos Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística Modelo de estrategia retroactiva BACKTRACK(LISTABD) 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. DATOS PRIMER(LISTABD) If MIEMBRO(DATOS,SUPR(LISTABD)) return FALLO If TERM(DATOS) return NADA If SINSALIDA(DATOS) return FALLO If LONGITUD(LISTABD) > LIMITE return FALLO REGLAS APLIREGL(DATOS) CICLO: if NOHAY(REGLAS) return FALLO R PRIMER(REGLAS) REGLAS SUPR(REGLAS) RDATOS R(DATOS) RLISTABD CONS(RDATOS,LISTABD) CAMINO BACKTRACK(RLISTABD) If CAMINO=FALLO go CICLO return CONS(R,CAMINO) Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística Búsqueda en profundidad retroactiva 0 1 2 8 3 1 6 4 7 5 2 2 8 3 6 4 1 7 5 3 8 3 2 6 4 1 7 5 4 8 3 2 6 4 1 7 5 5 8 3 2 6 4 1 7 5 2 8 3 1 6 4 7 5 (a) 2 8 3 1 6 4 7 5 0 1 2 8 3 1 6 4 7 5 2 2 8 3 6 4 1 7 5 3 8 3 2 6 4 1 7 5 4 8 3 2 6 4 1 7 5 6 (b) 0 7 8 6 3 2 4 1 7 5 1 2 8 3 1 6 4 7 5 2 2 8 3 6 4 1 7 5 2 8 3 6 4 1 7 5 2 8 3 1 6 4 7 5 7 Discarded before generating node 7 8 2 3 6 8 4 1 7 5 9 2 3 6 8 4 1 7 5 2 8 3 6 4 1 7 5 (c) © 1998 Morgan Kaufman Publishers Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística Búsqueda en grafos • Imposibilidad de representar el problema mediante un grafo implícito • Problema del 8-puzzle: 2 8 3 1 6 4 7 5 1 2 3 8 4 7 6 5 © 1998 Morgan Kaufman Publishers • El conjunto de nodos del grado de estados para esta representación del 8-puzzle es 9!=362.880 Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística Búsqueda en grafos • Formulación de los problemas para poder aplicar sobre ellos los métodos de búsqueda • Métodos que nos permitan representar grandes espacios de búsqueda mediante grafos implícitos • Métodos eficientes de búsqueda en grafos de gran tamaño Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística Búsqueda en grafos • Descripción para etiquetar el nodo inicial • Las funciones para transformar las descripciones de los estados: operadores • Una condición de éxito Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística Búsqueda en anchura 1. Crear una variable llamada LISTA-NODOS y asignarle el estado inicial 2. Hasta que se encuentre un estado objetivo o LISTA-NODOS esté vacía, hacer: 1. Eliminar el primer elemento de LISTA-NODOS y llamarlo E. Si LISTA-NODOS está vacía, terminar 2. Para cada regla que se empareje con el estado descrito en E hacer: 1. Aplicar la regla para generar un nuevo estado 2. Si el nuevo estado es un estado objetivo, terminar y devolver este estado 3. En caso contrario, añadir el nuevo estado al final de LISTANODO Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística Búsqueda en anchura 19 9 2 8 3 1 6 7 5 4 4 2 8 1 6 3 7 5 4 2 8 1 6 3 7 5 4 18 2 8 3 1 5 6 7 4 2 8 3 1 6 7 5 4 17 2 8 3 1 6 4 7 5 8 2 8 3 1 4 7 6 5 2 8 3 1 4 5 7 6 2 8 3 1 6 7 5 4 16 2 8 3 1 4 5 7 6 2 8 1 4 3 7 6 5 15 Start node 2 3 1 8 6 7 5 4 2 8 1 4 3 7 6 5 1 3 7 2 3 1 8 4 7 6 5 2 3 4 1 8 7 6 5 2 8 3 1 6 4 7 5 2 8 3 1 4 7 6 5 2 3 1 8 4 7 6 5 14 26 2 3 1 8 4 7 6 5 1 2 3 8 4 7 6 5 13 25 2 8 3 7 1 4 6 5 2 8 3 7 1 4 6 5 27 1 2 3 8 4 7 6 5 24 2 8 3 7 1 4 6 5 2 8 3 7 4 6 1 5 8 1 3 2 4 7 6 5 12 8 3 2 1 4 7 6 5 2 8 3 6 7 4 1 5 8 3 2 1 4 7 6 5 23 2 8 3 6 7 4 1 5 2 8 3 6 7 4 1 5 2 2 8 3 1 6 4 7 5 11 22 2 8 3 6 4 1 7 5 2 8 3 6 4 1 7 5 5 2 8 3 6 4 1 7 5 Goal node 8 3 2 1 4 7 6 5 6 2 8 3 1 4 7 6 5 1 2 3 7 8 4 6 5 21 2 3 6 8 4 1 7 5 2 8 3 6 4 5 1 7 2 8 6 4 3 1 7 5 2 3 6 8 4 1 7 5 2 3 6 8 4 1 7 5 8 6 3 2 4 1 7 5 10 20 8 3 2 6 4 1 7 5 8 3 2 6 4 1 7 5 8 3 2 6 4 1 7 5 © 1998 Morgan Kaufman Publishers Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística Búsqueda con costos 1. 2. 3. 4. 5. 6. 7. 8. Poner el nodo inicial s en una lista, llamada ABIERTOS, de nodos no expandidos. Crear una lista, llamada CERRADOS, de nodos expandidos, inicialmente vacía. Si ABIERTOS está vacía no existe solución. Terminar. Suprimir de ABIERTOS el nodo i con mínima g(i) y colocarlo en CERRADOS. Si i es un nodo objetivo se ha encontrado la solución. Terminar. En otro caso, expandir el nodo i, si no tiene sucesores ir a 3. Para cada nodo sucesor j del nodo i, insertarlo correctamente en ABIERTOS, asignando g(j)=g(i)+c(i,j). Ir a 3. Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística Descenso iterativo Depth bound = 1 Depth bound = 2 Depth bound = 3 Depth bound = 4 © 1998 Morgan Kaufman Publishers Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística Problemas descomponibles • Base de datos inicial (C,B,Z) • Operadores R1: C R2: C R3: B R4: Z (D,L) (B,M) (M,M) (B,B,M) • Objetivo Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística Resolución del problema Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística Grafo Y/O • Descomposición de problemas: arcos Y • Resolución de problemas: arcos O • Concepto de solución: subgrafo solución Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística Nueva resolución del problema Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística Ejemplo Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística Métodos de escalada • Algoritmo de escalada simple • Algoritmo de escalada por la máxima pendiente • Algunas variaciones estocásticas • Algoritmos genéticos Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística Algoritmo de escalada simple • Evaluar el estado inicial. Si también es el estado objetivo, devolverlo y terminar. En caso contrario, continuar con el estado inicial como estado actual. • Repetir hasta que se encuentre una solución o hasta que no queden nuevos operadores que aplicar al estado actual:  – Seleccionar un operador que no haya sido aplicado con anterioridad al estado actual y aplicarlo para generar un nuevo estado.  – Evaluar el nuevo estado. • Si es un estado objetivo, devolverlo y terminar. • Si no es un estado objetivo, pero es mejor que el estado actual, convertirlo en el estado actual. • Si no es mejor que el estado actual, continuar con el bucle. Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística Algoritmo de escalada por la máxima pendiente • Evaluar el estado inicial. Si también es el estado objetivo, devolverlo y terminar. En caso contrario, continuar con el estado inicial como estado actual. • Repetir hasta que se encuentre una solución o hasta que una iteración completa no produzca un cambio en el estado actual:  – Sea SUCC un estado tal que algún posible sucesor del estado actual sea mejor que este SUCC.  – Para cada operador aplicado al estado actual hacer lo siguiente: • Aplicar el operador y generar un nuevo estado • Evaluar el nuevo estado. Si es un estado objetivo, devolverlo y terminar. Si no, compararlo con SUCC. Si es mejor, asignar a SUCC este nuevo estado. Si no es mejor, dejar SUCC como está.  – Si SUCC es mejor que el estado actual, hacer que el estado actual sea SUCC. Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística Métodos de escalada Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística Algunas variaciones estocásticas • • • • Algoritmo de escalada estocástico Algoritmo de escalada de primera opción Algoritmo de escalada de reinicio aleatorio Enfriamiento simulado Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística Algoritmo de enfriamiento simulado  p = e Δ E  =| ( valor  − Δ E / kT  del estado actual ) − ( valor  del nuevo estado ) | • Los movimientos hacia estados peores pueden aceptarse • Se utiliza un programa de enfriamiento Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística Algoritmos genéticos • Se genera los estados sucesores combinado dos estados padres • Se inicia el proceso partiendo de k estados generados aleatoriamente (población) • Un estado (individuo) se representa como una cadena sobre un alfabeto finito (a menudo cadenas de 0s y 1s) • En la función de evaluación (fitness function) se asignan valores altos para los mejores estados • La siguiente generación se produce mediante las operaciones de selección, cruce y mutación. Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística Algoritmos genéticos Función de evaluación (8 reinas) = número de pares de reinas no atacadas 28 para una solución Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística Algoritmos genéticos Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística Búsqueda primero el mejor • • • • • • Algoritmo A* Búsqueda conducida mediante agendas Búsqueda dirigida Descenso iterativo A* Búsqueda primero el mejor recursiva A* con memoria acotada Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística Algoritmo A* • ABIERTOS contiene el nodo inicial, CERRADOS esta vacío • Comienza un ciclo que se repite hasta que se encuentra solución o hasta que ABIERTOS queda vacío  –  –  –  – Seleccionar el mejor nodo de ABIERTOS Si es un nodo objetivo terminar En otro caso se expande dicho nodo Para cada uno de los nodos sucesores • Si está en ABIERTOS insertarlo manteniendo la información del mejor padre • Si está en CERRADOS insertarlo manteniendo la información del mejor padre y actualizar la información de los descendientes • En otro caso, insertarlo como un nodo nuevo Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística Algoritmos de búsqueda Búsqueda Sobre grafos profundidad A* Con costo h=0 Anchura h<=h* Primero el mejor Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística Descomposición de problemas • Algoritmo Y/O* Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística Algoritmo Y/O* • GRAFO contiene el nodo de inicio. • Comienza un ciclo que se repite hasta que el nodo inicial quede resuelto o hasta que supere un valor MAXIMO  – Trazar el mejor camino actual desde inicio  – Seleccionar un nodo  – Generar los sucesores del nodo e incluirlos de forma adecuada en el GRAFO  – Propagar la información obtenida hacia arriba en el GRAFO Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística Heurísticas sobre el proceso de búsqueda • Arquitecturas combinadas de percepción y planificación • Búsqueda orientada a subobjetivos • Búsqueda jerárquica • Búsqueda con horizonte Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística Dificultades del proceso • Los procesos de percepción no siempre pueden obtener la información necesaria acerca del estado del entorno • Las acciones pueden no disponer siempre de modelos de sus efectos • Pueden haber otros procesos físicos, u otros agentes, en el mundo Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística Dificultades del proceso • En el tiempo que transcurre desde la construcción de un plan, el mundo puede cambiar de tal manera que el plan ya no sea adecuado • Podría suceder que se le requiriese al agente actuar antes de que pudiese completar una búsqueda de un estado objetivo • Aunque el agente dispusiera de tiempo suficiente, sus recursos de memoria podrían no permitirle realizar la búsqueda de un estado objetivo Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística Arquitectura percepción/planificación/actuación Sensory input Perceptual processing Goal (desired state) Current state State-space graph Planning (graph search) Find first action Action © 1998 Morgan Kaufman Publishers Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística Búsqueda orientada a subobjetivos Islands in the search space Local searches © 1998 Morgan Kaufman Publishers Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística Búsqueda jerárquica Metalevel path Metalevel search Goal Start Base-level searches © 1998 Morgan Kaufman Publishers Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística