1. No category

Teorı́a 5:
Problemas de Satisfacción de Restricciones
(PSRs)
Sistemas Inteligentes
Sistemas Inteligentes
1
Carreras: Ingenierı́a en Informática
Ingenierı́a en Computación (Optativa)
e-mail: [email protected]
Departamento de Informática
Universidad Nacional de San Luis
Argentina
Año 2015
Sistemas Inteligentes
2
Repaso
♦ Búsqueda de soluciones en un Espacio de Estados
♦ Heurı́sticas especı́ficas del dominio
♦ Definir: representación, las cuatro componentes de la def. del problema
Sistemas Inteligentes
3
Aspectos a considerar
♦ Definición formal de un Problema de Satisfacción de Restricciones (PSR)
y un Problema de Optimización (PO)
♦ Ejemplos de PSRs y POs
♦ Principales enfoques para resolver PSRs y POs
♦ Enfoques basados en formulación incremental
♦ Enfoques basados en formulación de estado completa
Bibliografı́a: Capı́tulo 6 del libro de Russell (3ra Edición) pp. 202-207 y
214-220. Libro Artificial Intelligence de Poole y Mackworth (2010) pp.
117-120 y 141-146. Capı́tulo 4 del libro de Russell (3ra Edición) pp. 120-126.
Sistemas Inteligentes
4
Definición formal de un PSR
Clase especial de problema, caracterizado por:
1. Un conjunto de variables X1, X2, . . . , Xn.
2. Por cada variable Xi, un dominio no vacı́o DXi que especifica los valores
posibles que la variable puede tomar.
3. Un conjunto de restricciones C1, C2, . . . , Cm especificando los valores
posibles de la/s variable/s.
Un estado del problema es la asignación parcial o completa de valores a
las variables
Sistemas Inteligentes
5
Definición formal de un PSR
Clase especial de problema, caracterizado por:
1. Un conjunto de variables X1, X2, . . . , Xn.
2. Por cada variable Xi, un dominio no vacı́o DXi que especifica los valores
posibles que la variable puede tomar.
3. Un conjunto de restricciones C1, C2, . . . , Cm especificando los valores
posibles de la/s variable/s.
Un estado del problema es la asignación parcial o completa de valores a
las variables
Solución de un PSR: asignación completa y consistente (que satisface
todas las restricciones)
Sistemas Inteligentes
6
Por qué formular un problema como un PSR?
1. Una gran variedad de problemas pueden ser formulados como PSR
2. Se pueden construir sistemas generales que resuelven PSR
3. Los sistemas que resuelven PSR son más rápidos que los de búsqueda
de estados (toman en cuenta las restricciones para chicar el espacio de
búsqueda)
Sistemas Inteligentes
7
Ejemplo: coloreado de mapa
Northern
Territory
Queensland
Western
Australia
South
Australia
New South Wales
Victoria
Tasmania
Variables W A, N T , Q, N SW , V , SA, T
Dominios DW A = DN T = . . . = DT = {red, green, blue}
Restricciones: las regiones adyacentes deben tener colores diferentes
por ej., W A 6= N T (de forma gral), o
(W A, N T ) ∈ {(red, green), (red, blue), (green, red), (green, blue), . . .}
Sistemas Inteligentes
8
Ejemplo: coloreado de mapa (cont)
Northern
Territory
Western
Australia
Queensland
South
Australia
New South Wales
Victoria
Tasmania
Las soluciones son asignaciones que satisfacen todas las restricciones, por ej.,
{W A = red, N T = green, Q = red, N SW = green, V = red, SA = blue, T = green}
Sistemas Inteligentes
9
Ejemplo: 8 reinas
Variables C1, C2, C3, C4, C5, C6, C7, C8
Dominios DCi = {1, 2, 3, 4, 5, 6, 7, 8}, ∀Ci
Restricciones: ningún par de reinas se ataca entre sı́
por ej., noAtaca(Ci, Cj ) ∀i, j ∈ [1 . . . 8] , i 6= j o
(C1, C2) ∈ {(1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (2, 4) . . .}
Sistemas Inteligentes
10
Definición formal de un PO
Poole y Mackworth 2010
Clase especial de problema en el que existe una relación de preferencia
entre las posibles soluciones:
1. Un conjunto de variables X1, X2, . . . , Xn con su correspondiente dominio no vacı́o DXi .
2. Una función objetivo que mapea la asignación total a un número
(real).
3. Un criterio de optimalidad para encontrar una asignación total que
maximice o minimice la función objetivo.
Un estado del problema es la asignación parcial o completa de valores a
las variables
Sistemas Inteligentes
11
Definición formal de un PO
Poole y Mackworth
Clase especial de problema en el que existe una relación de preferencia
entre las posibles soluciones:
1. Un conjunto de variables X1, X2, . . . , Xn con su correspondiente dominio no vacı́o DXi .
2. Una función objetivo que mapea la asignación total a un número
(real).
3. Un criterio de optimalidad para encontrar una asignación total que
maximice o minimice la función objetivo.
Un estado del problema es la asignación parcial o completa de valores a
las variables
Solución de un PO: asignación completa que sea óptima según el criterio
de optimalidad
Sistemas Inteligentes
12
Ejemplo: optimizar función arbitraria
Funcin a optimizar
x**2-y**2
100
50
eje Z
0
-50
-100
10
5
-10
0
-5
0
-5
5
10-10
eje Y
eje X
Variables X, Y
Dominios DX = DY = intervalo entero [−10, 10]
Función a optimizar: f (x, y) = x2 − y 2
Sistemas Inteligentes
13
Problema de Optimización Restringido
PSR + PO: un problema que además de tener una función objetivo y un
criterio de optimalidad, posee restricciones sobre las variables de la definición.
Sistemas Inteligentes
14
Ejemplo: el problema de la mochila 0/1
Dados:
1. n objetos o1, . . . , on, cada uno con un peso wi y un beneficio pi asociado.
2. una mochila de capacidad C.
Colocar dentro de la mochila aquellos elementos que satisfacen que la suma
de sus beneficios es máxima y el peso total de los elementos no sobrepasa la
capacidad de la mochila.
Variables x1, . . . , xn que indican la presencia (o no) del objeto en la mochila
Dominios Dxi = {0, 1}
Maximizar:
Restricción:
n
X
i=1
n
X
xi · pi considerando la siguiente
i=1
xi · w i ≤ C
Sistemas Inteligentes
15
Tipos de restricciones
Restricciones unarias involucran una única variable (PSR’s fáciles de resolver),
por ej., SA 6= green
Restricciones binarias involucran pares de variables (PSR puede representarse
como un grafo de restricciones),
por ej., SA 6= W A
Restricciones de orden más alto involucran 3 o más variables
Sistemas Inteligentes
16
Grafo de restricción
PSR binario: cada restricción relaciona a lo sumo dos variables
Grafo de restricción: nodos son variables, arcos muestran restricciones
NT
Northern
Territory
Q
Western
Australia
WA
SA
NSW
Queensland
South
Australia
New South Wales
V
Victoria
Victoria
T
Tasmania
Los algoritmos de PSR de propósito general usan la estructura del grafo
para acelerar la búsqueda (reducción exponencial de la complejidad). Por ej.,
Tasmania es un subprobl. independiente!
Sistemas Inteligentes
17
Enfoques para resolver PSRs
♦ Formulación incremental: El problema se plantea como los problemas de búsqueda estándar (especificando las cuatro componentes) que vimos
en teorı́as previas. Los estados están definidos por los valores asignados hasta
el momento.
♦ Algoritmos Generar-y-Probar (Generate-and-Test) (PooleMackworth 2010)
♦ Algoritmos de Vuelta Atrás (Backtracking) (y mejoras)
♦ Formulación de estado completo: Cada estado es una asignación
completa de valores a las variables.
♦ Algoritmo de Ascención de Colinas (Hill-Climbing)
♦ Algoritmo Bioinspirado PSO
Sistemas Inteligentes
18
Formulación de búsqueda incremental
Los estados están definidos por los valores asignados hasta el momento
♦ Estado inicial: la asignación vacı́a, { }
♦ Función sucesor: asignar un valor a una variable no asignada
♦ Test de objetivo: la asignación actual es completa y cumple con las
restricciones
Particularidades de búsqueda estándar aplicada a PSRs
1) Esto es igual para todos los PSRs!
2) Cada solución aparece a profundidad n con n variables
⇒ usar búsqueda primero en profundidad
3) El paso es irrelevante (orden de asignación de valores)
4) b = (n − ℓ)d a prof. ℓ, luego n!dn hojas y sólo hay dn asig. distintas!
Sistemas Inteligentes
19
Ej.: PSR con 2 variables, 3 valores posibles c/u
n = 2 variables X, Y
d = 3 valores distintos para cada variable x1, x2, x3, y1, y2, y3
Factor de branching: b = (n − l)d a prof. l
b = (2 − 0)3 a prof. 0
b = (2 − 1)3 a prof. 1
n!dn hojas ⇒ 2!32 = 2 × 9 = 18 hojas y sólo hay dn = 9 asign. distintas
{}
{X= x1}
{X= x1,Y=y1}
{X= x1,Y=y2}
{X= x2}
{X= x1,Y=y3}
{X= x2,Y=y1}
{X= x2,Y=Y2}
{X= x3}
{X= x2,Y=y3}
{X= x3,Y=y1}
{X= x3,Y=y2}
{Y= y1}
{X= x3,Y=y3}
{Y= y1,X=x1}
{Y= y1,X=x2}
{y= y2}
{Y= y1,X=x3}
{Y =y2,X=x1}
{Y= y3}
{Y= y2,X=x2}
{Y= y2,X=x3}
{Y= y3,X=x1}
Sistemas Inteligentes
{Y= y3,X=x2}
20
{Y= y3,X=x3}
Idea!!: aprovechar asignaciones conmutativas
Las asignaciones de variables son conmutativas, i.e.,
[W A = red then N T = green] es = que [N T = green then W A = red]
Considerar asignaciones a una única variable en cada nodo
⇒ b = d y hay dn hojas
{}
{X= x1}
{X= x1,Y=y1}
{X= x1,Y=y2}
{X= x2}
{X= x1,Y=y3}
{X= x2,Y=y1}
{X= x2,Y=Y2}
{X= x3}
{X= x2,Y=y3}
{X= x3,Y=y1}
{X= x3,Y=y2}
{X= x3,Y=y3}
Sistemas Inteligentes
21
Algoritmo Generar-y-Probar
Toma la idea previa y recorre el árbol usando alguno de los algoritmos de
búsqueda estándar (generalmente primero en profundidad) para asignar los
valores a las variables.
El algoritmo es esencialmente un ciclo que asigna valores a todas las variables (Generar) y luego chequea si las mismas cumplen las restricciones
(Probar).
Generar-y-Probar() retorna una solucion del PSR
Repetir
asignaciones = Generar(Variables,Dominios)
si probar(asignaciones) retornar asignaciones
Cada vez que es invocada Generar(Variables,Dominios) retorna una
asignación completa distinta {X1 = v1, . . . , Xn = vn} para cada Xi ∈
Variables y vj ∈ DXi .
Sistemas Inteligentes
22
Búsqueda con vuelta atrás
El algoritmo Generar-y-Probar sólo detecta la violación de restricciones recién cuando se han realizado todas las asignaciones de valores a variables.
Sin embargo, cada vez que asigno un valor a una variable se puede chequear
si las restricciones que afectan a las variables ya asignadas son violadas.
Búsqueda primero en profundidad para PSRs con asignaciones consistentes
(considerando una variable por vez) es llamada búsqueda con vuelta atrás
(backtracking)
Búsqueda con vuelta atrás es el algoritmo no informado básico para PSRs
Permite resolver n-reinas para n ≈ 25
Sistemas Inteligentes
23
Búsqueda con vuelta atrás
función Búsqueda-Con-Vuelta-Atrás (psr) retorna soln/falla
retornar Vuelta-Atrás-Recursiva({ }, psr)
función Vuelta-Atrás-Recursiva(asignación, psr) retorna soln/falla
si asignación es completa entonces retornar asignación
var ← Selecciona-Var-Noasignada(Variables[psr], asignación, psr)
por cada valor en Ordena-Valores-Dominio(var, asignación, psr) hacer
si valor es consistente con asignación de acuerdo a Restricciones[psr]
agregar {var = valor} a asignación
resultado ← Vuelta-Atrás-Recursiva(asignación, psr)
si resultado 6= falla entonces retornar resultado
remover {var = valor} de asignación
retornar falla
Sistemas Inteligentes
24
Ejemplo de Búsqueda con vuelta atrás
Sistemas Inteligentes
25
Ejemplo de Búsqueda con vuelta atrás
Sistemas Inteligentes
26
Ejemplo de Búsqueda con vuelta atrás
Sistemas Inteligentes
27
Ejemplo de Búsqueda con vuelta atrás
Sistemas Inteligentes
28
Mejorando la Búsqueda con vuelta atrás
Algunos aspectos que deberı́an considerarse (ganancia de velocidad) sin la
necesidad de usar heurı́sticas especı́ficas del problema:
1. ¿Cuál deberı́a ser la próxima variable a asignar? ¿En qué orden deberı́an
ser considerados sus valores?
2. ¿Podemos detectar fallas inevitables anticipadamente?
3. ¿Podemos evitar repetir asignaciones que violan restricciones (detectadas
antes)?
Sistemas Inteligentes
29
Mı́nimos valores restantes
Mı́nimos valores restantes (MVR):
elige la variable con la menor cantidad de valores legales (poda el árbol)
Si una variable se queda sin valores legales, MVR seleccionará dicha variable
y la falla será detectada inmediatamente.
La heurı́stica MVR se desempeña mejor que un ordenamiento aleatorio o
estático hasta en un factor de 1000, aunque los resultados dependen del
problema.
Sistemas Inteligentes
30
Grado heurı́stico
Permite desempatar entre variables MVR
Grado heurı́stico:
elige la variable involucrada en el mayor número de restricciones con otras
variables no asignadas (reduce el factor de ramificación)
Sistemas Inteligentes
31
Valor menos restrictivo
Dada una variable, elegir el valor menos restrictivo:
aquel que no elimina las opciones de valores legales en las variables
restantes
Allows 1 value for SA
Allows 0 values for SA
Combinando estas heurı́sticas hace factible la resolución del 1000 reinas
Sistemas Inteligentes
32
Comprobación hacia adelante
Una forma de detectar fallas anticipadamente (inferir) es con comprobación
hacia adelante (forward checking)
Idea: Registrar los valores legales restantes para las variables no asignadas
No insistir con un paso cuando alguna variable no tiene valores legales
WA
NT
Q
NSW
V
SA
T
Sistemas Inteligentes
33
Otros enfoques para resolver PSRs
Enfoques basados en Formulación de estado completo:
♦ Algoritmos de mejora iterativa
♦ Enfoques Poblacionales
Bibliografı́a: Sección 4.1, Libro de Russell (3ra. Edición-2010), pp.120-126.
Bibliografı́a especı́fica de Particle Swarm Optimization.
Sistemas Inteligentes
34
Algoritmos de mejora iterativa
En muchos problemas de optimización, el paso (costo) es irrelevante;
el estado objetivo, la solución es lo que importa
Espacio de estados = conjunto de configuraciones “completas”;
Encontrar configuración óptima, ej.,TSP
o, encontrar una configuración que satisfaga restricciones, ej., aulero
En estos casos, podemos usar algoritmos de mejora iterativa o dicho de
otra manera de búsqueda local: mantener un único estado actual, e intentar
mejorarlo (moverse a los vecinos)
Sistemas Inteligentes
35
Algoritmos de mejora iterativa
Son básicamente algoritmos de búsqueda local
Evalúan y modifican un estado (o varios)
Proceden iterativamente
El estado explora el espacio de búsqueda para encontrar el estado objetivo
Son completos si pueden encontrar siempre un objetivo/solución (si existe)
Son óptimos si encuentran el óptimo global
Sistemas Inteligentes
36
Algoritmos de mejora iterativa (búsqueda local)
Ventajas de estos algoritmos:
Utilizan muy poca memoria (usualmente una cantidad cte)
Encuentran soluciones razonables en espacios de estados grandes o infinitos (continuos) para los cuales los algoritmos sistemáticos (búsqueda en
espacios de estados) son inadecuados
El estado objetivo en sı́ mismo es una solución
Estos alg. son aptos para resolver probl. de optimización puros (el mejor
estado según una función objetivo)
Sistemas Inteligentes
37
Ejemplo: minimizar f (x, y) = x × y2
Un estado completo es un punto (x, y) con x ∈ [−5, 5] e y ∈ [−4, 4]
Funcin a optimizar
x * y**2
eje Z
80
60
40
20
0
-20
-40
-60
-80
4
3
2
1
-4
0
-2
-1
0
2
-2
4
-3
-4
eje Y
eje X
Los vecinos de un punto (x, y) podrı́an ser los puntos (x + 1, y), (x − 1, y),
(x, y + 1) y (x, y − 1).
Sistemas Inteligentes
38
Entendiendo la búsqueda local
Es útil considerar el terreno (landscape) del espacio de estado
Sistemas Inteligentes
39
Entendiendo la búsqueda local
ubicación = estado
elevación = función de costo de la heurı́stica o función objetivo
Sistemas Inteligentes
40
Ascensión de Colinas (Hill-climbing)
Conocido en la variante de variables continuas como ascenso/descenso
del gradiente
“Como escalar el Everest con niebla cerrada y con amnesia”
función Ascension-Colina( problema) retorna un estado que es máximo local
entradas: problema, un problema
local variables: actual, un nodo
vecino, un nodo
actual ← Hacer-Nodo(Estado-Inicial[problema])
hacer ciclo
vecino ← un sucesor de actual con el valor más alto
si Valor[vecino] ≤ Valor[actual] retornar Estado[actual]
actual ← vecino
fin
Sistemas Inteligentes
41
Funciones complicadas...
Funcin de Mandelbrot
mand({0,0},compl(x,y),30)
35
30
eje Z
25
20
15
10
5
1.5
1
0.5
-2
-1.5
0
-1
-0.5
-0.5
0
0.5
-1
1-1.5
eje Y
eje X
Problemas: Máximos locales, Crestas, Terrazas
Sistemas Inteligentes
42
Ascensión de Colinas (AC)
Tratando de resolver el 8-reinas, AC queda atascado en el 86 % de los casos, pudiendo resolver sólo el 14 % de las instancias; AC es rápido cuando
puede resolver el problema (en promedio 4 pasos si encuentra la sol.
considerando que existen 17 millones de estados
!!)
Mejoras:
Movimientos laterales aleatorios
escapan de las terrazas
loop infinito
sobre máximos locales planos (100 movimientos para el 8-reinas, resuelve el
94 % del 8-reinas)
AC con reinicios aleatorios supera óptimos locales—trivialmente completa
Sistemas Inteligentes
43
Variantes de la Ascención de Colinas
Ascención de Colinas estocástica (ACE): elige aleatoriamente entre
los movimientos ascendentes (usando probabilidades asociadas a las pendientes de ascensión).
Ascención de Colinas con primera elección (ACPE): genera sucesores aleatoriamente hasta encontrar uno que es mejor que el nodo actual.
Ascención de Colinas con reinicios aleatorios (ACRA): genera
estados iniciales en forma aleatoria y en cada uno aplica AC (resuelve 3
millones de reinas en menos de un minuto).
Una forma más sofisticada de introducir un comportamiento estocástico en
una búsqueda local es planteada en el algoritmo Templado Simulado.
Sistemas Inteligentes
44
Enfoques poblacionales
Particle Swarm Optimization (PSO)
Sistemas Inteligentes
45