Ejercicios Resueltos IA PDF

Preview

Summary

Serie de ejercicios de IA resuetos en detalle (por completar)...

Description

INTELIGENCIA ARTIFICIAL. CUADERNO DE PROBLEMAS. Autor : Ramos Gonz´ alez, V´ıctor.

2

Inteligencia Artificial. Cuaderno de Problemas. Autor: Ramos Gonz´ alez, V´ıctor

Segunda Edici´ on (Septiembre 2020)

INTELIGENCIA ARTIFICIAL. CUADERNO DE PROBLEMAS. Autor : Ramos Gonz´ alez, V´ıctor.

El libro contiene una colecci´ on de problemas resueltos, que abarcan algunas de las principales ´areas relacionadas con el campo de la Inteligencia Artificial, como m´etodo introductorio al desarrollo de esta disciplina. Los problemas expuestos y resueltos corresponden, en su totalidad, a los planteados en la asignatura de Inteligencia Artificial, impartida por el Dpto. de Ciencias de la Computaci´ on e Inteligencia Artificial. El material est´ a enfocado al ´ambito acad´emico, como m´ etodo de apoyo al aprendizaje de los conceptos b´ asicos que se plantean en la asignatura, especific´ andose para cada uno de los problemas propuestos el enunciado y soluci´ on del mismo, exponiendo, de manera detallada, la resoluci´ on de los mismos de tal forma que el alumno pueda entender los m´etodos de resoluci´ on y los conceptos asociados a los mismos. ´ DE LOS PROBLEMAS HA SIDO LLEVADA A CABO AVISO: LA RESOLUCION ´ PROFESOR DE LA POR EL AUTOR Y NO HA SIDO REVISADO POR NINGUN ASIGNATURA. Si encontrara alg´ un error, por favor, comun´ıquelo al correo [email protected],para que pueda ser corregido a la mayor brevedad.

2

Contenidos Contenidos

P´ agina

1. Metaheur´ısticas para la Optimizaci´ on.

7

Ejercicio 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

Ejercicio 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

Ejercicio 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

Ejercicio 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

Ejercicio 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12

Ejercicio 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

Ejercicio 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

Ejercicio 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

Ejercicio 9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

Ejercicio 10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

Ejercicio 11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

Ejercicio 12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

Ejercicio 13 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

Ejercicio 14 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

Ejercicio 15 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

Ejercicio 16 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18

Ejercicio 17 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18

Ejercicio 18 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

Ejercicio 19 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

Ejercicio 20 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

3

INTELIGENCIA ARTIFICIAL. CUADERNO DE PROBLEMAS. Autor : Ramos Gonz´ alez, V´ıctor. Ejercicio 21 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

Ejercicio 22 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

2. Espacios de Estado y Planificaci´ on.

25

Ejercicio 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

Ejercicio 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

Ejercicio 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

Ejercicio 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

Ejercicio 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

30

Ejercicio 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

Ejercicio 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

Ejercicio 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

Ejercicio 9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

36

Ejercicio 10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37

Ejercicio 11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

Ejercicio 12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39

Ejercicio 13 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

40

Ejercicio 14 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

3. Procesos de Decisi´ on de Markov

45

Ejercicio 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

46

Ejercicio 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

48

Ejercicio 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

50

Ejercicio 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

53

Ejercicio 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

55

Ejercicio 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

57

4. Conocimiento Probabil´ıstico. Redes Bayesianas.

59

Ejercicio 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

60

Ejercicio 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

61

CONTENIDOS

4

INTELIGENCIA ARTIFICIAL. CUADERNO DE PROBLEMAS. Autor : Ramos Gonz´ alez, V´ıctor. Ejercicio 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

62

Ejercicio 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

64

Ejercicio 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

65

Ejercicio 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

67

CONTENIDOS

5

INTELIGENCIA ARTIFICIAL. CUADERNO DE PROBLEMAS. Autor : Ramos Gonz´ alez, V´ıctor.

CONTENIDOS

6

Cap´ıtulo 1

Metaheur´ısticas para la Optimizaci´ on.

7

INTELIGENCIA ARTIFICIAL. CUADERNO DE PROBLEMAS. Autor : Ramos Gonz´ alez, V´ıctor.

Ejercicio 1.1 Consid´ erese un modelo de enjambre de part´ıculas desplaz´ andose en R2 seg´ un el algoritmo PSO. Supongamos que en un instante t se tiene una part´ıcula en la posici´ on (5, 5) con velocidad (6, 9). La mejor posici´ on de la part´ıcula se alcanz´ o en la posici´ on (2, 3) y la mejor posici´ on de cualquier part´ıcula el enjambre se alcanz´ o en la posici´ on (1, 1). Sabiendo que se trata de un problema de minimizaci´ on, y tomando como par´ ametros que los W = 0′ 7, c1 = 0′ 1, c2 = 0′ 4, y los valores aleatorios obtenidos en este caso han sido r1 = 0′ 6 y r2 = 0′ 9 y que la funci´ on de fitness es f (x, y) = x4 + y2 + 10, ¿mejora o empeora su posici´ on la part´ıcula tras un paso del algoritmo?

Soluci´ on Datos del problema: Tipo de optimizaci´ on: Minimizaci´ on.

Par´ ametros: W = 0′ 7, c1 = 0′ 1, c2 = 0′ 4

Funci´ on de fitness : f (x, y) = x4 + y2 + 10.

~ = (1, 1) Mejores posiciones: m ~ i = (2, 3), best

Proceso de resoluci´ on:

1. Calcular x~i t+1 = x~i t + v~i t+1, de forma que, teniendo en cuenta que

~ − x~i t ) v~i t+1 = W · v~i t + c1 · r1 · (m ~ i − x~i t ) + c2 · r2 · (best

Entonces: v~i t+1 = 0′ 7 · (6, 9) + 0′ 1 · 0′ 6 · ((2, 3) − (5, 5)) + 0′ 4 · 0′ 9 · ((1, 1) − (5, 5)) = (2′ 58, 4′ 74) De forma que ahora: x~i t+1 = x~i t + v~i t+1 = (5, 5) + (2′ 58, 4′ 74) = (7′ 58, 9′ 74)

2. Comprobar si el valor fitness en x~i t+1 es mayor (empeoramiento) o menor (mejora) que la de x~i t . De forma, que, dado que se tiene: f (5, 5) = 54 + 52 + 10 = 660

f (7′ 58, 9′ 74) = 7′ 584 + 9′ 742 + 10 = 3406′ 106

Por tanto, dado que f (~ xi t ) < f(x~i t+1) entonces se ha empeorado. CAP´ITULO 1. METAHEUR´ISTICAS PARA LA OPTIMIZACI ´ON.

8

INTELIGENCIA ARTIFICIAL. CUADERNO DE PROBLEMAS. Autor : Ramos Gonz´ alez, V´ıctor.

Ejercicio 1.2 El problema de Coloreado de mapas se plantea de manera gen´ erica como sigue: dado un mapa con N pa´ıses y M colores distintos, asignar un color a cada pa´ıs de tal manera que aquellos que sean fronterizos no queden pintados con el mismo color. Se pide: 1. Plantear el problema como un problema de optimizaci´ on. (Indicaci´ on: Se puede definir una funci´ on sobre cada posible forma de colorear el mapa, de manera que, si existe un coloreado v´ alido del mapa, entonces e´ste corresponda con un m´ınimo de dicha funci´ on ¿c´ omo definir´ıas dicha funci´ on?). 2. Plantear el problema de forma que pueda ser resuelto mediante la aplicaci´ on del m´ etodo de Enfriamiento simulado, esto es, definir la representaci´ on de los estados, las funciones genera estado inicial, genera sucesor y la funci´ on de valoraci´ on. 3. Plantear el problema de forma que pueda ser resuelto mediante la aplicaci´ on del m´ etodo de Algoritmos gen´ eticos, esto es, definir la representaci´ on de los estados mediante genes y longitud de cromosomas, las funciones decodifica y fitness. Soluci´ on 1. Una soluci´ on ser´ıa v´ alida si no existen dos pa´ıses fronterizos tal que ambos posean el mismo color, de forma que lo que hay que optimizar (minimizando) el n´ umero de pa´ıses fronterizos que poseen el mismo color. De forma que podemos plantear la funci´ on de valoraci´ on como: f (c1 , c2 , ..., cn ) =

n n X X

faux(ci , cj )

i=1 j=i+1

faux((x1 , c1 ), (x2 , c2 )) =



1 si c1 = c2 ∧ (son fronterizos(x1 , x2 )) 0 e.o.c.

2. Para representar el problema para que pueda ser abordado mediante Enfriamiento Simulado hemos de dar una representaci´ on para los estados, y definir las funciones genera estado inicial, genera sucesor y la funci´ on de valoraci´ on. Estados: lista de longitud n (n´ umero de pa´ıses) cuyas posiciones toman valores 1, 2, . . . , M (colores). genera estado inicial: Funci´on que genera un estado aleatorio, asignando de forma aleatoria un color a cada una de las posiciones de la lista. genera sucesor: Se elige una posici´on al azar de la lista y se cambia el color. valora: cuenta el n´ umero de pares de pa´ıses fronterizos con el mismo color. La funci´ on planteada en el primer apartado realiza precisamente este c´ alculo.

CAP´ITULO 1. METAHEUR´ISTICAS PARA LA OPTIMIZACI ´ON.

9

INTELIGENCIA ARTIFICIAL. CUADERNO DE PROBLEMAS. Autor : Ramos Gonz´ alez, V´ıctor. 3. Para dar una representaci´ on al problema de manera que pueda ser resuelto mediante la aplicaci´ on del m´etodo de Algoritmos gen´eticos hemos de definir los genes, longitud de cromosomas, decodifica y fitness. genes: valores enteros en {1, 2, . . . , M} (colores). longitud cromosomas : n´ umero de pa´ıses, n. decodifica: El cromosoma se puede decodificar como una lista en la que cada posici´ on un pa´ıs y su valor el color asignado al mismo. fitness : cuenta el n´ umero de pares de pa´ıses fronterizos con el mismo color. La funci´ on planteada en el primer apartado realiza precisamente este c´ alculo.

Ejercicio 1.3 El problema de N-Reinas se plantea de manera gen´ erica como sigue: dado un tablero de ajedrez N × N , colocar N reinas en el tablero de forma que cualesquiera dos, no se ataquen entre s´ı. Se pide modelar el problema para que pueda ser abordado mediante la t´ ecnica de Algoritmos gen´eticos, esto es, se pide dar genes, longitud de los cromosomas y las funciones decodifica y fitness.

Soluci´ on Si lo plante´ asemos como un problema de optimizaci´ on, podr´ıamos plantear el objetivo como la minimizaci´ on del n´ umero de pares de reinas que ocupan posiciones incompatibles (misma fila, misma columna, misma diagonal principal y secundaria). Para dar una representaci´ on para un Algoritmo Gen´ etico :

genes : Cada uno de ellos corresponde a un valor entero perteneciente al rango [0, N − 1]. longitud de los cromosomas : N . decodifica: El cromosoma se puede decodificar como una lista en la que cada posici´on representa una columna del tablero y el valor representa la fila que ocupa la reina de dicha columna. fitness : cuenta el n´ umero de pares de reinas que ocupan posiciones incompatibles. Con el dise˜ no que hemos dado, no es posible que dos reinas ocupen una misma columna, ya que ´estas est´ an representadas en distintos genes del cromosoma y estos toman un u ´ nico valor. Si utilizamos cruces y mutaciones dedicados a permutaciones, no puede haber dos reinas en la misma fila ya que en cada cromosoma todos los genes toman valores distintos. De forma que la funci´ on fitness ha de contar u ´ nicamente las posiciones inv´ alidas por diagonal, de forma que dadas dos posiciones del cromosoma i, j, con i 6= j, hay incompatibilidad si y s´ olo si |i − j| = |decodifica[i] − decodif ica[j]|. CAP´ITULO 1. METAHEUR´ISTICAS PARA LA OPTIMIZACI ´ON.

10

INTELIGENCIA ARTIFICIAL. CUADERNO DE PROBLEMAS. Autor : Ramos Gonz´ alez, V´ıctor.

Ejercicio 1.4 Supong´ ase que se tienen n trabajadores que han de realizar n tareas, y que conocemos el tiempo qi,j de realizaci´ on por parte del trabajador i-´ esimo (ti ) de la tarea j-´ esima (Tj ). El problema consiste en encontrar la asignaci´ on de tareas a los trabajadores (una u ´nica tarea por trabajador), de manera que el tiempo de realizaci´ on de las tareas sea m´ınimo. Para la comprensi´ on del problema presentamos un ejemplo para n = 4, de forma que los tiempos qi,j vienen dados seg´ un la siguiente tabla. Se dan tambi´ en dos posibles asignaciones (la segunda o ´ptima):

Trabajadores

Tareas qi,j

T1

T2

T3

T4

t1

12

43

15

7

t2

9

10

6

4

t3

5

13

29

2

t4

4

11

17

9

t1 ← T2 , t2 ← T3 , t3 ← T1 , t4 ← T4 Tiempo de realizaci´ on: 43 + 6 + 5 + 9 = 63 t1 ← T4 , t2 ← T3 , t3 ← T1 , t4 ← T2 Tiempo de realizaci´ on: 7 + 6 + 5 + 11 = 29

Se pide dar una representaci´ on del problema (para el caso general n) de forma que pueda ser resuelto mediante la t´ ecnica de Algoritmos Gen´ eticos. Concretamente se pide definir los genes, longitud de los cromosomas, y las funciones decodifica y fitness. Soluci´ on Si planteamos el problema como problema de optimizaci´on el objetivo corresponder´ıa a la minimizaci´ on de la sima de los tiempos individuales empleados en la realizaci´ on de las tareas. Para dar una representaci´ on para un Algoritmo Gen´etico : genes : Corresponden a valores en el rango [1, n], con n el n´ umero de tareas. longitud del cromosoma : Corresponde al n´ umero de trabajadores equivalente al n´ umero de tareas (n). decodifica: El cromosoma se puede decodificar como una lista en la que cada posici´on representa un trabajador y el valor que toma representa la tarea asignada. fitness : Corresponde a la suma de los tiempos qi,j seg´ un la asignaci´ on realizada. Si utilizamos cruces y mutaciones est´ andar tendremos que penalizar la repetici´ on de valor (que equivale a repetici´ on de tareas). Mejor, podemos utilizar cruces y mutaciones dedicadas a permutaciones. De forma que: (tomando decodifica(c) como una lista cuya primera posici´on es la posici´ on 1) fitness(c) =

n X

qi,decodif ica(c)[i]

i=1

CAP´ITULO 1. METAHEUR´ISTICAS PARA LA OPTIMIZACI ´ON.

11

INTELIGENCIA ARTIFICIAL. CUADERNO DE PROBLEMAS. Autor : Ramos Gonz´ alez, V´ıctor.

Ejercicio 1.5 Supong´ ase que se han de realizar n tareas T1 , . . . , Tn , y que se tienen m trabajadores para realizarlas t1 , . . . , tm , de forma que se tienen algunas restricciones: Un mismo trabajador no puede realizar varias tareas simult´ aneamente, pero s´ı puede hacerlo en distintos instantes. No todas las tareas pueden ser realizadas por todos los trabajadores. Existen o ´rdenes de precedencia entre tareas, de forma que para realizar una tarea Tj es necesario que otra est´ e realizada Ti . Expresaremos estas restricciones como Ti < Tj . De forma que el problema consiste en planificar la realizaci´ on de las tareas, estableciendo, para cada una de las tareas, el trabajador encargado de la tarea y el momento en que se debe realizar, de forma que, finalmente, todas las tareas est´ en realizadas, y de forma que la realizaci´ on del conjunto de tareas se lleve a cabo en el menor tiempo posible. Se pide modelar el problema, de forma que pueda ser abordado mediante la t´ ecnica de Algoritmos Gen´ etico. Concretamente se pide definir los genes, longitud de los cromosomas, y las funciones decodifica y fitness. Soluci´ on Para abordar el problema como problema de optimizaci´ on podemos establecer como funci´ on objetivo la minimizaci´ on del tiempo total de realizaci´ on del conjunto de tareas, de forma que se cumplan todas las restricciones. Para dar una representaci´ on adecuada para el uso de Algoritmos Gen´ eticos :

genes : Sea S =

n P

Qj , siendo Qj el tiempo de realizaci´ on de la tarea Tj por parte del

j=1

trabajador que m´ as tarda en realizarla (de aquellos que pueden hacerla). Los genes corresponder´ıan a pares (x, y) tal que: • x ∈ {1, . . . , m}. • y ∈ {1, . . . , S}. longitud del cromosoma : Corresponde al n´ umero de tareas (n). decodifica: El cromosoma se puede decodificar como una lista en la que cada posici´on representa una tarea y el valor que toma (x, y) representa el trabajador encargado d...