• Author / Uploaded
• Anonymous dQZRlcoLdh

Citation preview

Inteligencia Artificial I

Curso 2005–2006

Tema 7: B´ usqueda local y algoritmos gen´ eticos Jos´ e A. Alonso Jim´ enez Francisco J. Mart´ın Mateos Jos´ e L. Ruiz Reina

Dpto. de Ciencias de la Computaci´ on e Inteligencia Artificial

Universidad de Sevilla

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.1

Introducci´ on x

x

x

Algoritmos de b´ usqueda de soluciones ´ optimas u

Buscar la mejor soluci´ on dentro de un espacio de posibles soluciones

u

Maximizar o minimizar

u

En nuestro caso, minimizar (an´ alogamente maximizar)

Mejoras iterativas u

Empezar con un estado inicial cualquiera

u

Mejorar su calidad paso a paso

Algoritmos: u

Escalada

u

Escalada con reinicio aleatorio

u

Enfriamiento simulado

u

Algoritmos gen´ eticos

u

Reparaci´ on heur´ıstica (tema 7)

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.2

B´ usqueda en escalada x

Idea de la b´ usqueda en escalada: u

Aplicar t´ ecnicas de mejora iterativa a solucionar problemas representados como espacios de estados

u

Confiar en la heur´ıstica, escogiendo en cada paso el sucesor con mejor heur´ıstica

u

No se permite recuperarse de un camino err´ oneo (no se mantiene un ´ arbol de b´ usqueda)

u

Puede verse como una escalada (ascenso o descenso) heuristica h(e’)

Estados

h(e)

e’ e

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.3

Implementaci´ on de la b´ usqueda en escalada FUNCION BUSQUEDA-EN-ESCALADA() 1. Hacer ACTUAL el nodo cuyo estado es *ESTADO-INICIAL*, cuyo camino es vac´ ıo y cuya heur´ ıstica es la de *ESTADO-INICIAL* 2. Mientras que ACTUAL sea distinto de FALLO, 2.1 Si ES-ESTADO-FINAL(ESTADO(ACTUAL)), devolver el nodo ACTUAL y terminar. 2.2 en caso contrario, 2.2.1 Hacer MEJOR-SUCESOR igual al nodo con mejor heur´ ıstica de entre SUCESORES(ACTUAL) 2.2.2 Si HEURISTICA-DEL-NODO(MEJOR-SUCESOR) < HEURISTICA-DEL-NODO(ACTUAL), 2.2.2.1 Hacer ACTUAL igual a MEJOR-SUCESOR 2.2.2.2 En caso contrario, hacer ACTUAL igual a FALLO 3. Devolver ACTUAL

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.4

Grafo de escalada para el problema del viaje Sevilla

1

H = 325.08

Cádiz

Córdoba

Huelva

Málaga

H = 348.37

H = 240.27

H = 409.15

H = 177.91

Cádiz

Córdoba

Granada

H = 348.37

H = 240.27

H = 106.26

Almería H=0

IA-I 2005–2006

2

Cc Ia

4

3

Sevilla H = 325.08

Córdoba

Jaén

Málaga

H = 240.27

H = 150.99

H = 177.91

B´ usqueda local y algoritmos gen´ eticos

7.5

8–puzzle por escalada: 1a heur´ıstica 1

2

8

3

1

6

4

7

5 H=4

2

2

8

3

2

1

6

4

1

7

5

7

H=5

2 7

3

2

1

4

1

6

5

7

IA-I 2005–2006

6

3

2

8

3

4

1

6

4

5

7

5

H=3

8

H=3

8

3

2

8

8

4

1

4

6

5

7

6

H=3

Cc Ia

H=5

H=4

3 5

2

8

3

1

6

4

7

5 H=4

B´ usqueda local y algoritmos gen´ eticos

7.6

8–puzzle por escalada: 2a heur´ıstica 1

2

8

3

1

6

4

7

5 H=5

2

2

8

3

2

1

6

4

1

7

5

7

H=6

8 6

3

2

8

3

4

1

6

4

5

7

5

H=4

H=6

3

2 7

8

3

2

1

4

1

6

5

7

H=5

3

2

8

8

4

1

4

6

5

7

6

H=3

3 5

2

8

3

1

6

4

7

H=5

5 H=5

4

2

3

2

3

2

1

8

4

1

8

4

1

7

6

5

7

6

5

7

H=4

H=2

8

3 4

6

5

H=4

5

2

3

1

8

4

7

6

5

1 7

2

3

8

4

6

5

H=1

H=3

6

2

3

1

1

8

4

8

7

6

5

7

H=2

IA-I 2005–2006

Cc Ia

2 6

3

1

2

3

4

7

8

4

6

5

5

H=0

H=2

B´ usqueda local y algoritmos gen´ eticos

7.7

Ventajas e inconvenientes x

x

x

Ventajas de la b´ usqueda en escalada: u

Eficiente en tiempo y en espacio

u

No mantiene un ´ arbol de b´ usqueda: mejora iterativa

Inconvenientes: incompletitud, dependiendo de la heur´ıstica u

Existencia de ´ optimos locales

u

Mesetas

En lo que sigue: u

Abandonaremos la representaci´ on como espacio de estados y adapteremos la b´ usqueda en escalada a problemas de optimizaci´ on en los que el camino no es importante

u

Introduciremos cierta componente aleatoria en la b´ usqueda

u

Introduciremos modificaciones para intentar superar el problema de los ´ optimos locales

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.8

Problema del viajante x

Problema: dada una lista de ciudades, pasar por todas ellas recorriendo la menor distancia posible (suponiendo que existe conexi´ on directa entre todas ellas)

CO

JA

SE HU GR AL MA

CA

x

No confundir con el problema del viaje

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.9

Problema del viajante x

x

Una posible representaci´ on: u

Estados: ciudades visitadas

u

Operadores: ir a una ciudad

u

Un operador es aplicable si la ciudad est´ a entre las que quedan por visitar

u

Aplicar una b´ usqueda que encuentre una soluci´ on ´ optima

u

Muy ineficiente en la pr´ actica

Alternativa: u

Estados: permutaci´ on de las ciudades

u

Operadores: obtener una nueva permutaci´ on, usando t´ ecnicas heur´ısticas e incluyendo cierta aleatoriedad

u

Mejorar los estados en iteraciones sucesivas

u

La bondad de los estados se cuantifica por una funci´ on objetivo (en este caso, la distancia total del circuito)

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.10

Caracter´ısticas de algunos problemas de optimizaci´ on x

Estados y soluciones al problema u

No buscamos el camino (los estados contienen toda la informaci´ on)

u

Se busca optimizar (maximizar o minimizar) respecto de una determinada funci´ on objetivo

x

Estado inicial: no est´ a claramente definido

x

Operadores:

x

u

Se puede definir cierta noci´ on de nodo “sucesor” o “vecino”

u

En algunos casos, gran cantidad de vecinos

u

Introducimos cierta componente aleatoria y restringimos la noci´ on de “nodo vecino”

Estados finales: u

Todos los estados son posibles soluciones, pero se trata de encontrar una soluci´ on buena (respecto de la funci´ on objetivo)

u

Si es posible, la mejor

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.11

Representaci´ on problema de optimizaci´ on (b´ usqueda local) x

Elecci´ on de una representaci´ on para los estados (estructura de datos)

x

Funci´ on F-OBJETIVO(ESTADO)

x

u

Funci´ on cuyo valor se trata de optimizar

u

En nuestro caso, minimizar (an´ alogamente maximizar)

Funci´ on GENERA-ESTADO-INICIAL() u

x

Si en el problema el estado inicial no est´ a claramente definido, el estado inicial puede generarse de manera aleatoria, o usando alguna t´ ecnica heur´ıstica

Funci´ on GENERA-SUCESOR(ESTADO) u

Genera un estado sucesor a uno dado

u

Define la noci´ on de “vecindad” para el problema concreto

u

Usualmente, existe cierta componente aleatoria en la generaci´ on del sucesor

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.12

Representaci´ on del problema del viajante x

x

Representaci´ on de los estados: u

Cada estado ser´ a un posible circuito, representado por una lista con todas las ciudades, sin repetir, en un orden determinado

u

Ejemplo: (malaga cadiz cordoba almeria huelva granada jaen sevilla)

Generaci´ on aleatoria del estado inicial u

x

Asumiremos que la funci´ on GENERA-ESTADO-INICIAL() obtiene un circuito inicial aleatorio

Funci´ on objetivo u

La funci´ on F-OBJETIVO(ESTADO) devuelve la distancia total del circuito

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.13

Representaci´ on del problema del viajante x

Generaci´ on de un sucesor con la funci´ on GENERA-SUCESOR(ESTADO) u

Elecci´ on aleatoria de dos ciudades e inversi´ on del camino entre ellas c1 c2

c1 c2

c8

c3

c7

c4

c6

c3

c7

c4

c6 c5

c5 x

c8

Heur´ıstica + aleatoriedad

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.14

Problema del cuadrado de puntos x

Caso particular del problema del viajante: u

Las “ciudades” est´ an representadas por pares de coordenadas

u

4n puntos situados uniformemente a lo largo de los lados de un cuadrado de lado n

u

Parametrizado y con soluci´ on conocida (escalable, adecuado para pruebas)

u

Representaci´ on an´ aloga al problema del viajante (0,n)

(n,n)

(0,3) (0,2) (0,1) (0,0) (1,0) IA-I 2005–2006

Cc Ia

(2,0)

(3,0)

(n,0) B´ usqueda local y algoritmos gen´ eticos

7.15

B´ usqueda en escalada aleatoria FUNCION ESCALADA-ALEATORIA() 1. Hacer ACTUAL igual GENERA-ESTADO-INICIAL() y VALOR-ACTUAL igual a F-OBJETIVO(ACTUAL). Hacer VECINO igual a GENERA-SUCESOR(ACTUAL) y VALOR-VECINO igual a F-OBJETIVO(VECINO) 2. Mientras VALOR-VECINO sea menor que VALOR-ACTUAL, 2.1 Hacer ACTUAL y VALOR-ACTUAL igual a VECINO y VALOR-VECINO, resp. 2.2 Hacer VECINO igual a GENERA-SUCESOR(ACTUAL) y VALOR-VECINO igual a F-OBJETIVO(VECINO) 3. Devolver ACTUAL y VALOR-ACTUAL x

Observaciones: u

Adaptaci´ on de la escalada en espacios de estados a la nueva representaci´ on

u

Posible aleatoriedad: generaci´ on de estado inicial y sucesores

u

No necesitamos caminos, luego no usamos nodos

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.16

B´ usqueda en escalada aleatoria: ejemplos x

Ejemplos > (load "viajante") ... > (escalada-aleatoria) ((CADIZ HUELVA CORDOBA JAEN ALMERIA SEVILLA GRANADA MALAGA) 1366.7968) > (escalada-aleatoria) ((SEVILLA JAEN HUELVA CORDOBA MALAGA ALMERIA GRANADA CADIZ) 1488.9255) > (escalada-aleatoria) ((SEVILLA GRANADA ALMERIA CORDOBA JAEN CADIZ MALAGA HUELVA) 1431.388)

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.17

B´ usqueda en escalada aleatoria x

Problemas: u

x

´ Optimos locales, mesetas

Idea: u

Buscar aleatoriamente el inicio de la pendiente

u

Hacer escalada (o descenso) a partir de ah´ı

u

Iterar el proceso

u

Devolver el mejor estado conseguido en alguna de las iteraciones

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.18

B´ usqueda en escalada con reinicio aleatorio FUNCION ESCALADA-CON-REINICIO-ALEATORIO(ITERACIONES) 1. Hacer MEJOR-ESTADO igual GENERA-ESTADO-INICIAL() y MEJOR-VALOR igual a F-OBJETIVO(MEJOR-ESTADO) 2. Hacer un n´ umero de veces igual a ITERACIONES lo siguiente: 2.1 Realizar una escalada aleatoria. 2.2 Si el estado obtenido tiene un valor mejor que MEJOR-VALOR, actualizar MEJOR-ESTADO y MEJOR-VALOR con el nuevo estado y valor obtenido. 3. Devolver MEJOR-ESTADO y MEJOR-VALOR

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.19

Escalada con reinicio aleatorio: ejemplo x

Problema del viajante: > (load "viajante") ... > (escalada-con-reinicio-aleatorio 50) ((JAEN CORDOBA SEVILLA CADIZ HUELVA MALAGA ALMERIA GRANADA) 1009.58923) > (escalada-con-reinicio-aleatorio 300) ((CORDOBA GRANADA ALMERIA JAEN MALAGA SEVILLA HUELVA CADIZ) 1080.9673) > (escalada-con-reinicio-aleatorio 1000) ((MALAGA CADIZ HUELVA SEVILLA CORDOBA JAEN ALMERIA GRANADA) 929.9256)

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.20

Escalada con reinicio aleatorio: ejemplo x

Problema del cuadrado de puntos (soluciones no ´ optimas): > (load "puntos") ... > (cuadrado 3) > (escalada-con-reinicio-aleatorio 10000) (((3 . 3) (3 . 2) (2 . 3) (3 . 1) (2 . 0) (3 (1 . 0) (0 . 0) (0 . 1) (0 . 3) (0 . 2) (1 17.478706) > (escalada-con-reinicio-aleatorio 100000) (((1 . 0) (0 . 0) (0 . 1) (0 . 2) (0 . 3) (1 (3 . 2) (3 . 3) (2 . 3) (3 . 0) (3 . 1) (2 15.812559)

IA-I 2005–2006

Cc Ia

. 0) . 3))

. 3) . 0))

B´ usqueda local y algoritmos gen´ eticos

7.21

Enfriamiento simulado x

x

Idea principal: u

Aceptar probabil´ısticamente estados “peores”

u

La probabilidad de que un estado peor sea aceptado var´ıa en funci´ on del incremento producido en la funci´ on objetivo

u

Permitimos as´ı salir de ´ optimos locales, sin salir del ´ optimo global

Algoritmo inspirado en el proceso f´ısico-qu´ımico de enfriamiento de metales

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.22

Enfriamiento simulado x

x

Enfriamiento de metales u

Sistema estable: m´ınimo de energ´ıa

u

Dada una temperatura, el sistema necesita tiempo para estabilizarse (perder energ´ıa)

u

Es posible pasar moment´ aneamente por estados de mayor energ´ıa, con probabilidad dada por ∆E p(∆E, T ) = e− k·T

u

Despu´ es de estabilizarse, se vuelve a bajar la temperatura, y el sistema se estabiliza nuevamente en un estado de menor energ´ıa

Programa de enfriamiento u

Al princio (T grande) mayor probabilidad de aceptaci´ on de soluciones candidatas (diversificaci´ on)

u

Al final (T peque˜ na), se aceptan pocas soluciones candidatas (intensificaci´ on)

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.23

Enfriamiento simulado: par´ ametros x

Generaci´ on del estado inicial y estados vecinos u

x

Aceptaci´ on probabil´ıstica u

x

x

Aleatoria, heur´ıstica

Probabilidad de aceptaci´ on de un estado que incrementa ∆F el valor de la funci´ on ∆F objetivo: e− T

Programa de enfriamiento, en nuestro caso: u

Temperatura inicial

u

Variaci´ on de la temperatura: T ← α · T

u

N´ umero fijo de iteraciones para cada T

Criterio de parada u

Valor suficientemente bueno de la funci´ on objetivo

u

N´ umero m´ aximo de iteraciones sin mejora

u

En nuestro caso, n´ umero fijo de iteraciones totales

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.24

Enfriamiento simulado FUNCION ENFRIAMIENTO-SIMULADO(T-INICIAL,FACTOR-DESCENSO, N-ENFRIAMIENTOS,N-ITERACIONES) 1. Crear las siguientes variables locales: 1.1 TEMPERATURA (para almacenar la temperatura actual), inicialmente con valor T-INICIAL. 1.2 ACTUAL (para almacenar el estado actual), cuyo valor inicial es GENERA-ESTADO-INICIAL(). 1.3 VALOR-ACTUAL igual a F-OBJETIVO(ACTUAL) 1.4 MEJOR (para almacenar el valor del mejor estado encontrado hasta el momento), inicialmente ACTUAL. 1.5 VALOR-MEJOR (para almacenar el valor de MEJOR), inicialmente igual a VALOR-ACTUAL 2. Iterar un n´ umero de veces igual a N-ENFRIAMIENTOS lo siguiente: 2.1 Iterar un n´ umero de veces igual a N-ITERACIONES lo siguiente: 2.1.1 Crear las siguientes variables locales: 2.1.1.1 CANDIDATA, una soluci´ on vecina de ACTUAL, generada por GENERA-SUCESOR. 2.1.1.2 VALOR-CANDIDATA, el valor de CANDIDATA. 2.1.1.3 INCREMENTO, la diferencia entre VALOR-CANDIDATA y VALOR-ACTUAL 2.1.2 Cuando INCREMENTO es negativo, o se acepta probabil´ ısticamente la soluci´ on candidata, hacer ACTUAL y VALOR-ACTUAL iguales a VECINA y VALOR-VECINA, respectivamente. 2.1.3 Si VALOR-ACTUAL es mejor que VALOR-MEJOR, actualizar MEJOR y VALOR-MEJOR con con ACTUAL y VALOR-ACTUAL, respectivamente. 2.2

Disminuir TEMPERATURA usando FACTOR-DESCENSO

3. Devolver MEJOR y VALOR-MEJOR

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.25

Enfriamiento simulado x

Ejemplo (problema del viajante) > (enfriamiento-simulado 100 0.95 100 100) ((MALAGA GRANADA ALMERIA JAEN CORDOBA SEVILLA HUELVA CADIZ) 929.92554)

x

Ejemplo (problema de los puntos) > (cuadrado 3) (0 1 2 3 4 5 6 7 8 9 10 11) > (enfriamiento-simulado 5 0.95 100 100) (((0 . 1) (0 . 0) (1 . 0) (2 . 0) (3 . 0) (3 . 1) (3 . 2) (3 . 3) (2 . 3) (1 . 3) (0 . 3) (0 . 2)) 12) > (cuadrado 4) ... > (second (enfriamiento-simulado 8 0.95 100 100)) 16 > (cuadrado 7) ... > (second (enfriamiento-simulado 15 0.95 100 100)) 28 > (cuadrado 10) ... > (second (enfriamiento-simulado 20 0.95 100 100)) 43.414215 > (second (enfriamiento-simulado 20 0.95 100 100)) 40 > (cuadrado 15) ... > (second (enfriamiento-simulado 35 0.95 100 100)) 99.498474 > (second (enfriamiento-simulado 35 0.95 500 500)) 60

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.26

Algoritmos gen´ eticos: evoluci´ on natural x

Procesos evolutivos

x

La evoluci´ on ocurre en los cromosomas de los individuos

x

Selecci´ on natural: las “buenas estructuras” sobreviven con m´ as probabilidad que las dem´ as

x

Reproducci´ on mediante cruces y mutaciones

x

Algoritmo gen´ etico: u

Aplicaci´ on de estas ideas en la b´ usqueda de soluciones ´ optimas

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.27

Algoritmos gen´ eticos x

x

Posibles soluciones representadas como individuos u

Codificaci´ on como cromosoma (lista de genes)

u

Poblaci´ on de individuos

u

Generaciones

u

Genotipo y fenotipo

Bondad de los individuos u

x

x

Seg´ un el valor de la funci´ on objetivo

Reproducci´ on de las generaciones u

Cruces: combinaci´ on de estructuras, aleatorio

u

Mutaciones: cambio de algunos genes, aleatorio

Mecanismo de evoluci´ on u

Selecci´ on probabil´ıstica de los individuos con mejor valoraci´ on

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.28

Operaciones gen´ eticas x

x

Cruces:

1 0 0 0 1 1

1 0

0 0 0 0

0 1 1 0 0 0

0 1 1

0 1 1

Mutaciones:

1 0 0 0 1 1

IA-I 2005–2006

Cc Ia

1 0 1

0 1 1

B´ usqueda local y algoritmos gen´ eticos

7.29

Algoritmo gen´ etico (pseudoc´ odigo) t := 0 Inicia-Poblaci´ on P(t) Eval´ ua-Poblaci´ on P(t) Mientras no Fin hacer P’ := Selecciona-Padres P(t) P’’ := Cruza P’ P’’’ := Muta P’’ Evalua-Poblaci´ on P’’’ P(t+1) := Selecciona-Mejores P’’’,P(t) t:= t+1 Fin-Mientras Devolver el mejor de P(t)

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.30

Par´ ametros del algoritmo gen´ etico x

x

N´ umero total de individuos en la poblaci´ on (en cada generaci´ on) Individuos que intervienen en la reproducci´ on en cada generaci´ on (padres) u

x

x

Dado como proporci´ on de la poblaci´ on total (proporci´ on de cruces)

Padres que se escogen entre los mejores u

Dado como proporci´ on del total de padres (proporci´ on de mejores)

u

Selecci´ on por ranking dentro de la poblaci´ on

Probabilidad de que ocurra una mutaci´ on u

Generalmente un n´ umero muy bajo

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.31

Selecci´ on, mutaci´ on y reproducci´ on x

x

Selecci´ on de padres: u

Un n´ umero fijo de padres se obtienen con los mejores de la poblaci´ on

u

El resto se escoge aleatoriamente de entre los restantes (para mentener as´ı la diversidad)

Cruces: u

x

Mutaci´ on: u

x

Cada gen de cada individuo se mutar´ a seg´ un la probabilidad dada

Nueva generaci´ on: u

x

Las parejas se obtiene reordenando aleatoriamente los padres y cruzando de dos en dos

Unir las dos generaciones y quedarse con los mejores (en igual n´ umero que la poblaci´ on inicial)

Atenci´ on: existen otras implementaciones de algoritmos gen´ etico u

Pero todas se basan en las mismas ideas de reproducci´ on, mutaci´ on, selecci´ on de los mejores y mantenimiento de la diversidad

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.32

Representaci´ on de problemas en algoritmos gen´ eticos x

Problemas de optimizaci´ on u

x

Variables *GENES* y *LONGITUD-INDIVIDUOS* u

x

Ejemplo en la funci´ on cuadrado: un cromosoma puede verse como un n´ umero binario de 10 d´ıgitos (en orden inverso). El fenotipo de un cromosoma es dicho n´ umero (en notaci´ on decimal)

Funci´ on F-OBJETIVO(X), valor de de la funci´ on a optimizar (actuando sobre el fenotipo) u

x

Ejemplo en la funci´ on cuadrado: (0 1) y 10, respectivamente

Funci´ on DECODIFICA(X), obtiene el fenotipo u

x

Ejemplo: encontrar el m´ınimo de la funci´ on f (x) = x2 en [0, 210) ∩ N

Ejemplo en la funci´ on cuadrado: la funci´ on que recibiendo un n´ umero natural lo eleva al cuadrado

Funci´ on ES-OPTIMO(X), criterio de parada u

Ejemplo: F-OBJETIVO(X)=0

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.33

Ejemplo de ejecuci´ on (funci´ on cuadrado) > (load "funcion-cuadrado") ... > (algoritmo-genetico-con-salida 20 10 0.75 0.6 0.1) Generacion: 1. Media: 361954.9, Mejor: (0 1 1 0 0 1 0 0 0 0), Valor: 1444 Generacion: 2. Media: 79730.6, Mejor: (0 1 1 0 0 1 0 0 0 0), Valor: 1444 Generacion: 3. Media: 22278.6, Mejor: (0 1 1 0 0 1 0 0 0 0), Valor: 1444 Generacion: 4. Media: 3537.7, Mejor: (1 1 1 1 0 0 0 0 0 0), Valor: 225 Generacion: 5. Media: 1597.3, Mejor: (0 0 1 1 0 0 0 0 0 0), Valor: 144 Generacion: 6. Media: 912.8, Mejor: (0 1 0 0 0 0 0 0 0 0), Valor: 4 Generacion: 7. Media: 345.3, Mejor: (0 1 0 0 0 0 0 0 0 0), Valor: 4 Generacion: 8. Media: 60.7, Mejor: (0 1 0 0 0 0 0 0 0 0), Valor: 4 Generacion: 9. Media: 14.0, Mejor: (0 1 0 0 0 0 0 0 0 0), Valor: 4 Generacion: 10. Media: 4.5, Mejor: (0 1 0 0 0 0 0 0 0 0), Valor: 4 Generacion: 11. Media: 3.7, Mejor: (1 0 0 0 0 0 0 0 0 0), Valor: 1 Generacion: 12. Media: 3.4, Mejor: (1 0 0 0 0 0 0 0 0 0), Valor: 1 Generacion: 13. Media: 2.4, Mejor: (0 0 0 0 0 0 0 0 0 0), Valor: 0 0

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.34

Algoritmos gen´ eticos: representaci´ on problema del viajante x

x

Genes y longitud de los individuos en el problema del viajante u

*GENES* = (almeria cadiz cordoba granada huelva jaen malaga sevilla)

u

*LONGITUD-INDIVIDUOS* = 8

Decodificaci´ on en el problema del viajante: u

x

DECODIFICA(X)= X

Criterio de parada (parar s´ olo al llegar al m´ aximo de generaciones): u

ES-OPTIMO(X)=FALSO

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.35

Algoritmos gen´ eticos: representaci´ on problema del viajante x

La codificaci´ on permite ciudades repetidas u

x

La funci´ on objetivo penaliza las repeticiones

Funci´ on objetivo: u

Penalizaci´ on por camino incompleto PENALIZACION-POR-INCOMPLETO(CAMINO)= 100 * (|CAMINO - *GENES*| + |*GENES* - CAMINO|)

u

Combinaci´ on de distancia con penalizaci´ on F-OBJETIVO(X)= 2*DISTANCIA-VIAJE(X) + 50*PENALIZACION-POR-INCOMPLETO(X)

u

Los pesos de cada componente pueden ajustarse experimentalmente

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.36

Soluci´ on al problema del viajante x

Una evaluaci´ on

;;; ;;; ;;; ;;; x

(algoritmo-genetico 100 50 0.75 0.6 0.05) Mejor individuo: (HUELVA SEVILLA CORDOBA GRANADA ALMERIA JAEN MALAGA CADIZ) Valor: 2015.8258

Varios intentos

(defun intentos (n-intentos) (loop for i from 1 to n-intentos do (let ((res (algoritmo-genetico 100 50 0.75 0.6 0.05))) (format t "~& Experimento: ~a, Mejor individuo: ~a, Valor: ~a" i res (f-objetivo res))))) ;; ;; ;; ;;

Experimento: 84, Mejor individuo: (MALAGA GRANADA ALMERIA JAEN CORDOBA SEVILLA HUELVA CADIZ), Valor: 1859.8511 (Soluci´ on ´ optima)

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.37

Algoritmos gen´ eticos: problema del cuadrado m´ agico x

x

x

Colocar en un cuadrado n × n los n´ umeros naturales de 1 a n2, de tal manera que las filas, las columnas y las diagonales principales sumen los mismo Una soluci´ on para n = 3: 4

3

8

9

5

1

2

7

6

Soluciones representadas como listas de n´ umeros entre 1 y n2 u

Admitimos repeticiones

u

La funci´ on objetivo penaliza las repeticiones

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.38

Algoritmos gen´ eticos: cuadrado m´ agico x

x

Problema parametrizado, variables globales: u

Dimensi´ on del cuadrado: N

u

Suma com´ un: SUMA=(N·(N2 + 1))/2

Funci´ on de decodificaci´ on, DECODIFICA(X): u

Un cromosoma representa al cuadrado cuya concatenaci´ on de filas es igual al cromosoma Ejemplo (para N igual a 3): > (decodifica ’(1 7 5 3 2 8 4 6 9)) ((1 7 5) (3 2 8) (4 6 9))

x

Genes y longitud de los individuos: u

*GENES* = (1 2 3 ...N2)

u

*LONGITUD-INDIVIDUOS* = N2

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.39

Algoritmos gen´ eticos: cuadrado m´ agico x

Criterio de parada: ES-OPTIMO(X) = "X es un cromosoma sin repeticiones que representa un cuadrado m´ agico"

x

La funci´ on objetivo penaliza las repeticiones: N-REPETICIONES(X)= "N´ umero de genes repetidos en X" SUMA-DIFERENCIAS(X)= "Suma de las diferencias (en valor absoluto) entre la suma de los n´ umeros de cada hilera (filas, columnas y diagonales) y SUMA" F-OBJETIVO(X)= (1 + N-REPETICIONES(X)) * SUMA-DIFERENCIAS(X)

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.40

Soluci´ on al cuadrado m´ agico x

Caso n = 3

;;; Soluciones N=3 (se encuentra f´ acilmente) ;;; ((8 1 6) (3 5 7) (4 9 2)) x

Caso n = 4

;;; Soluciones N=4 ;;; Encontrado con ;;; (algoritmo-genetico 1000 500 0.75 0.6 0.1) ;;; en la generaci´ on 125: ;;; ((7 14 9 4) (16 2 5 11) (1 15 12 6) (10 3 8 13))

IA-I 2005–2006

Cc Ia

7

14

9

4

16

2

5

11

1

15

12

6

10

3

8

13 B´ usqueda local y algoritmos gen´ eticos

7.41

Variantes x

Variantes en el cruce: cruces multipunto y uniforme

x

Variantes en la selecci´ on de indiv´ıduos u

Cada individuo i es seleccionado para ser padre con probabilidad proporcional a su valor de la funci´ on objetivo (ruleta probabil´ıstica): Fobj (i) P (i) = Pn j=1 Fobj (j)

x

Variantes en el c´ alculo de la nueva generaci´ on: u

Si el tama˜ no de la poblaci´ on es n y r es la proporci´ on de cruces,

u

se seleccionan (1 − r) · n individuos que pasan directamente a la nueva generaci´ on, y

u

u

parejas para cruzar y pasan a la nueva generaci´ on los resultados se seleccionan r·p 2 de sus cruces respectivos. la selecci´ on se hace por ruleta probabil´ıstica

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.42

Conclusi´ on x

x

x

Algoritmos gen´ eticos como proceso de b´ usqueda local u

Mejora iterativa

u

Los cruces, las mutaciones y la diversidad tratan de evitar el problema de los ´ optimos locales

F´ acil de aplicar a muchos tipos de problemas: u

optimizaci´ on

u

aprendizaje autom´ atico

u

planificaci´ on

u

...

Resultados aceptables en algunos problemas u

Aunque no son mejores que algoritmos espec´ıficos para cada problema

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.43

Bibliograf´ıa x

Rich, E. y Knight, K. Inteligencia artificial (segunda edici´ on) (McGraw–Hill Interamericana, 1994). u

x

Russell, S. y Norvig, P. Artificial Intelligence (A Modern Approach) (Prentice–Hall, 1995). u

x

x

Cap. 3: “T´ ecnicas de b´ usqueda heur´ıstica”.

Cap. 4 “Informed search methods”.

Goldberg, D.E. Genetic Algorithms (in Search, Optimization & Machine Learning) (Addison–Wesley, 1989). Grillmeyer, O. Exploring Computer Science with Scheme (Springer, 1999). u

Cap. 16 “Soft Computing: Fuzzy Logic, Neural Networks and Genetic Algorithms”.

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.44

Inteligencia Artificial I

Curso 2005–2006

Tema 7 (anexo): Implementaciones en Lisp

Dpto. de Ciencias de la Computaci´ on e Inteligencia Artificial

Universidad de Sevilla

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.45

Implementaci´ on de la b´ usqueda en escalada (defun sucesores (nodo) (let ((resultado ())) (loop for operador in *operadores* do (let ((siguiente (sucesor nodo operador))) (when siguiente (push siguiente resultado)))) (nreverse resultado))) (defun sucesor (nodo operador) (let ((siguiente-estado (aplica operador (estado nodo)))) (when siguiente-estado (crea-nodo-h :estado siguiente-estado :camino (cons operador (camino nodo)) :heuristica-del-nodo (heuristica siguiente-estado)))))

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.46

Implementaci´ on de la b´ usqueda en escalada (defun mejor (nodos minima-distancia-al-final) (let ((mejor-nodo nil)) (loop for n in nodos do (when (< (heuristica-del-nodo n) minima-distancia-al-final) (setf mejor-nodo n minima-distancia-al-final (heuristica-del-nodo n)))) mejor-nodo))

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.47

Implementaci´ on de la b´ usqueda en escalada (defun busqueda-en-escalada () (let ((actual (crea-nodo-h :estado *estado-inicial* :camino nil :heuristica-del-nodo (heuristica *estado-inicial*)))) (loop until (null actual) do (cond ((es-estado-final (estado actual)) (return actual)) (t (setf actual (mejor (sucesores actual) (heuristica-del-nodo actual))))))))

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.48

Problema del viajante para b´ usqueda local x

Lista de todas las ciudades: (defparameter *ciudades* ’(almeria cadiz cordoba granada huelva jaen malaga sevilla))

x

Generaci´ on aleatoria del estado inicial: (defun escoge-aleatoriamente (n l) (if (= n 0) ’() (let ((pos-escogida (random (length l)))) (cons (nth pos-escogida l) (escoge-aleatoriamente (- n 1) (append (subseq l 0 pos-escogida) (subseq l (1+ pos-escogida)))))))) (defun genera-estado-inicial () (escoge-aleatoriamente (length *ciudades*) *ciudades*))

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.49

Problema del viajante para b´ usqueda local x

Generaci´ on de un sucesor (aleatorio): (defparameter *lista-indices* (loop for i from 0 to (- (length *ciudades*) 1) collect i)) (defun genera-sucesor (estado) (let* ((indices (escoge-aleatoriamente 2 *lista-indices*)) (indices-ord (if (< (first indices) (second indices)) (list (first indices) (second indices)) (list (second indices) (first indices)))) (primero (first indices-ord)) (segundo (second indices-ord))) (append (subseq estado 0 primero) (reverse (subseq estado primero segundo)) (subseq estado segundo))))

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.50

Problema del viajante x

Funci´ on objetivo: (defparameter *coordenadas-ciudades* ’((almeria (409.5 93)) (cadiz ( 63 57)) (cordoba (198 207)) (granada (309 127.5)) (huelva ( 3 139.5)) (jaen (295.5 192)) (malaga (232.5 75)) (sevilla ( 90 153)))) (defun distancia (c1 c2) (sqrt (+ (expt (- (abscisa c1) (abscisa c2)) 2) (expt (- (ordenada c1) (ordenada c2)) 2)))) (defun abscisa (ciudad) (first (second (assoc ciudad *coordenadas-ciudades*)))) (defun ordenada (ciudad) (second (second (assoc ciudad *coordenadas-ciudades*)))) (defun suma-distancias (camino) (if (endp (rest camino)) 0 (+ (distancia (first camino) (second camino)) (suma-distancias (rest camino))))) (defun longitud-viaje (camino) (+ (distancia (first (last camino)) (first camino)) (suma-distancias camino))) (defun f-objetivo (estado) (longitud-viaje estado))

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.51

Problema del cuadrado de puntos x

Par´ ametros del problema (defvar *lado*) (defvar *puntos*) (defun cuadrado (n) (setf *lado* n) (crea-puntos) (crea-lista-indices)) (defun crea-puntos () (setf *puntos* (append (loop for i from 0 to *lado* collect (cons 0 i)) (loop for i from 1 to *lado* collect (cons i 0)) (loop for i from 1 to *lado* collect (cons *lado* i)) (loop for i from 1 to (1- *lado*) collect (cons i *lado*))))) (defun crea-lista-indices () (setf *lista-indices* (loop for i from 0 to (- (length *puntos*) 1) collect i)))

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.52

Problema del cuadrado de puntos x

Generaci´ on del estado inicial (defun genera-estado-inicial () (escoge-aleatoriamente (length *puntos*) *puntos*))

x

Generaci´ on de un sucesor (defun genera-sucesor (estado) (let* ((indices (escoge-aleatoriamente 2 *lista-indices*)) (indices-ord (if (< (first indices) (second indices)) (list (first indices) (second indices)) (list (second indices) (first indices)))) (primero (first indices-ord)) (segundo (second indices-ord))) (append (subseq estado 0 primero) (reverse (subseq estado primero segundo)) (subseq estado segundo))))

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.53

Problema del cuadrado de puntos x

Funci´ on objetivo (defun distancia (p1 p2) (sqrt (+ (expt (- (car p1) (car p2)) 2) (expt (- (cdr p1) (cdr p2)) 2)))) (defun suma-distancias (camino) (if (endp (rest camino)) 0 (+ (distancia (first camino) (second camino)) (suma-distancias (rest camino)))))

(defun distancia-viaje (camino) (+ (distancia (first camino) (first (last camino))) (suma-distancias camino))) (defun f-objetivo (estado) (distancia-viaje estado))

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.54

B´ usqueda en escalada aleatoria (defun escalada-aleatoria () (let* ((actual (genera-estado-inicial)) (vecino (genera-sucesor actual)) (valor-actual (f-objetivo actual)) (valor-vecino (f-objetivo vecino))) (loop while (< valor-vecino valor-actual) do (setf actual vecino valor-actual valor-vecino vecino (genera-sucesor actual) valor-vecino (f-objetivo vecino))) (list actual valor-actual)))

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.55

B´ usqueda en escalada con reinicio aleatorio (defun escalada-con-reinicio-aleatorio (iteraciones) (let* ((mejor-estado (genera-estado-inicial)) (mejor-valor (f-objetivo mejor-estado))) (loop for i from 1 to iteraciones do (let* ((resultado (escalada-aleatoria)) (estado (first resultado)) (valor (second resultado))) (when (< valor mejor-valor) (setf mejor-estado estado mejor-valor valor)))) (list mejor-estado mejor-valor)))

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.56

Enfriamiento simulado (defun enfriamiento-simulado (t-inicial factor-descenso n-enfriamientos n-iteraciones) (let* ((temperatura t-inicial) ;;; 1.1 (actual (genera-estado-inicial)) ;;; 1.2 (valor-actual (f-objetivo actual)) ;;; 1.3 (mejor actual) ;;; 1.4 (valor-mejor (f-objetivo actual))) ;;; 1.5 (loop for i from 1 to n-enfriamientos do ;;; 2 (loop for j from 1 to n-iteraciones do ;;; 2.1 (let* ((candidata (genera-sucesor actual)) (valor-candidata (f-objetivo candidata)) (incremento (- valor-candidata valor-actual))) (when (or (< incremento 0) (< (/ (random 1001) 1000.0) (exp (max (/ (- incremento) temperatura) -80)))) (setf actual candidata valor-actual valor-candidata) (when (< valor-actual valor-mejor) (setf mejor actual valor-mejor valor-actual))))) (setf temperatura ;;; 2.2 (* factor-descenso temperatura))) (list mejor valor-mejor))) ;;; 3

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.57

Algoritmo gen´ etico (par´ ametros) x

Variables globales (defvar (defvar (defvar (defvar

x

*numero-total-individuos*) *numero-total-padres*) *numero-mejores*) *probabilidad-mutacion*)

Iniciar variables globales (defun inicia-variables-globales (numero-total-individuos proporcion-cruces proporcion-mejores probabilidad-mutacion) (setf *numero-total-individuos* numero-total-individuos *numero-total-padres* (fuerza-numero-par (round (* proporcion-cruces numero-total-individuos))) *numero-mejores* (round (* *numero-total-padres* proporcion-mejores)) *probabilidad-mutacion* probabilidad-mutacion))

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.58

Generaci´ on de la poblaci´ on inicial x

Poblaci´ on inicial sin evaluar:

(defun poblacion-inicial (num-individuos num-genes) (if (= num-individuos 0) ’() (cons (individuo-aleatorio num-genes) (poblacion-inicial (1- num-individuos) num-genes)))) (defun individuo-aleatorio (num-genes) (if (= num-genes 0) ’() (cons (crea-gen) (individuo-aleatorio (1- num-genes))))) (defun crea-gen () (nth (random (length *genes*)) *genes*))

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.59

Generaci´ on de la poblaci´ on inicial x

Ordenaci´ on de la poblaci´ on (defun evalua-cromosoma (cromosoma) (f-objetivo (decodifica cromosoma))) (defun ordena-poblacion-por-valor (poblacion) (sort poblacion #’< :key #’evalua-cromosoma)) (defun poblacion-inicial-ordenada (num-individuos num-genes) (ordena-poblacion-por-valor (poblacion-inicial num-individuos num-genes)))

x

Ejemplo (funci´ on cuadrado):

> (poblacion-inicial-ordenada ((0 0 1 0 1 1 0 0 0 0) (0 0 1 (0 0 1 1 0 0 1 1 1 0) (1 1 0 (0 0 0 0 1 0 1 1 0 1) (1 0 0 (0 0 1 1 0 1 1 0 1 1)) IA-I 2005–2006

10 10) 0 1 0 1 1 0 0) (1 1 1 0 1 1 1 1 0 0) 1 1 0 0 1 0 1) (1 1 0 1 1 1 0 1 0 1) 0 1 0 0 0 1 1) (0 1 1 1 1 0 1 0 1 1) Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.60

Cruces x

Cruce en un punto seleccionado aleatoriamente (defun cruza-pareja (individuo1 individuo2) (let ((posicion-cruce (1+ (random (- *longitud-individuos* 1))))) (list (append (subseq individuo1 0 posicion-cruce) (subseq individuo2 posicion-cruce)) (append (subseq individuo2 0 posicion-cruce) (subseq individuo1 posicion-cruce)))))

x

Ejemplo (funci´ on cuadrado): > (cruza-pareja ((1 1 1 1 1 1 0 > (cruza-pareja ((1 0 1 0 1 0 0

IA-I 2005–2006

’(1 0 0 ’(1 0 0

1 1 1 0) (0 0 1 0 0) (1

1 0 1 1

1 0 0 1

1 0 1 1

Cc Ia

1 0 0 1

1 0 1 0

1) ’(0 0 0 0 0 0 0 0 0 0)) 1 1 1 1) 0) ’(1 1 1 1 1 0 0 0 0 0)) 1 0 1 0))

B´ usqueda local y algoritmos gen´ eticos

7.61

Mutaciones x

Mutaci´ on probabil´ıstica de un gen: (defun muta-individuo (ind) (if (endp ind) nil (cons (if (< (random 100) (* *probabilidad-mutacion* 100)) (crea-gen) (first ind)) (muta-individuo (rest ind)))))

x

Ejemplo (funci´ on cuadrado, con probabilidad de mutaci´ on 0,1): > (muta-individuo ’(1 1 1 1 1 1 1 1 1 1)) (1 1 1 1 1 1 1 1 1 1) > (muta-individuo ’(1 1 1 1 1 1 1 1 1 1)) (1 1 0 1 1 1 1 1 1 1)

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.62

M´ etodos de reproducci´ on x

Obtenci´ on de una nueva generaci´ on

(defun nueva-generacion (g) (supervivientes (une-dos-generaciones (muta (cruza (selecciona-padres g))) g))) x

Selecci´ on de padres (defun selecciona-padres (g) (let ((mejores (subseq g 0 *numero-mejores*)) (numero-restantes-padres (- *numero-total-padres* *numero-mejores*)) (restantes (subseq g *numero-mejores*))) (append mejores (escoge-aleatoriamente numero-restantes-padres restantes))))

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.63

M´ etodos de reproducci´ on x

Cruce de padres (defun cruza (g) (cruza-de-dos-en-dos (reordena-aleatoriamente g))) (defun reordena-aleatoriamente (l) (escoge-aleatoriamente (length l) l)) (defun cruza-de-dos-en-dos (g) (if (endp g) nil (append (cruza-pareja (first g) (second g)) (cruza-de-dos-en-dos (cddr g)))))

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.64

M´ etodos de reproducci´ on x

Mutaci´ on de la poblaci´ on (defun muta (g) (if (endp g) ’() (cons (muta-individuo (first g)) (muta (cdr g)))))

x

Supervivencia de los mejores (defun une-dos-generaciones (g1 g2) (append g1 g2)) (defun supervivientes (poblacion) (subseq (ordena-poblacion-por-valor poblacion) 0 *numero-total-individuos*))

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.65

M´ etodos de reproducci´ on x

Ejemplo de obtenci´ on de una nueva generaci´ on (en el problema de la funci´ on cuadrado): > (setf poblacion-inicial (poblacion-inicial-ordenada *numero-total-individuos* *longitud-individuos*)) ((1 1 0 1 1 0 0 0 0 1) (1 1 1 1 1 0 0 0 0 1) (0 1 1 1 0 1 1 0 0 1) (1 1 1 1 0 1 1 1 0 1) (1 1 0 1 0 1 0 1 1 1) (0 1 1 1 0 1 0 1 1 1) (1 1 0 1 1 1 0 1 1 1) (1 1 0 1 1 1 0 1 1 1) (0 0 0 1 0 0 1 1 1 1) (1 1 0 0 0 1 1 1 1 1)) > (setf poblacion-siguiente (nueva-generacion poblacion-inicial)) ((1 0 0 1 1 0 0 1 1 0) (0 0 0 1 0 0 1 1 1 0) (1 0 0 1 0 0 1 1 1 0) (1 1 0 1 1 0 1 1 1 0) (1 1 1 0 0 1 1 1 1 0) (0 0 0 0 1 1 1 1 1 0) (1 0 0 0 1 1 1 1 1 0) (1 1 1 0 1 1 1 1 1 0) (1 1 1 0 1 1 1 1 1 0) (1 1 0 1 1 1 1 1 1 0))

x

Mejora de la poblaci´ on: Media Valor Media Valor

valores individuos poblacion-inicial mejor individuo poblacion-inicial valores individuos poblacion-siguiente mejor individuo poblacion-siguiente

IA-I 2005–2006

Cc Ia

= = = =

545886.3 290521 230295.2 167281

B´ usqueda local y algoritmos gen´ eticos

7.66

Algoritmo gen´ etico (defun algoritmo-genetico (num-generaciones numero-total-individuos proporcion-cruces proporcion-mejores probabilidad-mutacion) (inicia-variables-globales numero-total-individuos proporcion-cruces proporcion-mejores probabilidad-mutacion) (let* ((generacion-actual (poblacion-inicial-ordenada *numero-total-individuos* *longitud-individuos*)) (mejor-individuo (first generacion-actual)) (n-gen 1) (final (or (es-optimo mejor-individuo) (> n-gen num-generaciones)))) (loop until final do (setf generacion-actual (nueva-generacion generacion-actual) mejor-individuo (first generacion-actual) n-gen (1+ n-gen) final (or (es-optimo mejor-individuo) (> n-gen num-generaciones)))) (decodifica mejor-individuo)))

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.67

Representaci´ on problema del viajante (alg. gen´ eticos) x

Genes y longitud de los individuos (defparameter *genes* ’(almeria cadiz cordoba granada huelva jaen malaga sevilla)) (defparameter *longitud-individuos* 8)

x

Decodificaci´ on (defun decodifica (x) x)

x

Criterio de parada: (defun es-optimo (x) (declare (ignore x)) nil)

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.68

Representaci´ on problema del viajante x

La codificaci´ on permite ciudades repetidas u

x

La funci´ on objetivo penaliza las repeticiones

Funci´ on objetivo: u

Penalizaci´ on por camino incompleto (defun penalizacion-por-incompleto (camino) (* 100 (+ (length (set-difference camino *genes*)) (length (set-difference *genes* camino)))))

u

Combinaci´ on de distancia con penalizaci´ on (defun f-objetivo (x) (+ (* 2 (distancia-viaje x)) (* 50 (penalizacion-por-incompleto x))))

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.69

Problema cuadrado m´ agico x

Problema parametrizado: (defvar *n*) (defun asigna-suma () (defparameter *suma* (/ (* *n* (+ (expt *n* 2) 1)) 2))) (defun asigna-genes () (defparameter *genes* (loop for i from 1 to (expt *n* 2) collect i))) (defun asigna-longitud-individuos () (defparameter *longitud-individuos* (expt *n* 2))) (defun cuadrado-magico-genetico (n) (setf *n* n) (asigna-suma) (asigna-genes) (asigna-longitud-individuos) (list ’cuadrado-magico-genetico n))

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.70

Problema cuadrado m´ agico x

Decodificaci´ on (defun decodifica (l) (if (endp l) ’() (cons (subseq l 0 *n*) (decodifica (subseq l *n*))))) ;;; Ejemplo (para *n* igual a 3): ;;; > (decodifica ’(1 7 5 3 2 8 4 6 9)) ;;; ((1 7 5) (3 2 8) (4 6 9))

x

Columnas y diagonales (defun columnas (l) (loop for i from 0 to (- *n* 1) collect (mapcar #’(lambda (x) (nth i x)) l))) (defun diagonales (l) (let ((lista-posiciones (loop for i from 0 to (- *n* 1) collect i))) (list (mapcar #’(lambda (i x) (nth i x)) lista-posiciones l) (mapcar #’(lambda (i x) (nth i x)) (reverse lista-posiciones) l)))) ;;; ;;; ;;; ;;; ;;;

Ejemplo (para *n* igual a 3): > (columnas ’((1 7 5) (3 2 8) (4 6 9))) ((1 3 4) (7 2 6) (5 8 9)) > (diagonales ’((1 7 5) (3 2 8) (4 6 9))) ((1 2 9) (5 2 4))

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.71

Problema cuadrado m´ agico x

Criterio de parada: (defun no-repetidos (l) (if (endp l) t (and (not (member (first l) (rest l))) (no-repetidos (rest l))))) (defun todos-suman (n l) (if (endp l) t (and (= n (apply #’+ (first l))) (todos-suman n (rest l))))) (defun es-optimo (m) (let ((l (decodifica m))) (and (todos-suman *suma* (append l (columnas l) (diagonales l))) (no-repetidos m))))

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.72

Problema cuadrado m´ agico x

Funci´ on objetivo: (defun suma-diferencias (l) (apply #’+ (mapcar #’(lambda (s) (abs (- s *suma*))) l))) (defun ocurrencias (x l) (cond ((endp l) 0) ((equal x (first l)) (1+ (ocurrencias x (rest l)))) (t (ocurrencias x (rest l))))) (defun numero-repeticiones (l) (if (endp l) 0 (+ (ocurrencias (first l) (rest l)) (numero-repeticiones (rest l))))) (defun f-objetivo (x) (* (suma-diferencias (suma-hileras (append x (columnas x) (diagonales x)))) (1+ (numero-repeticiones (apply #’append x)))))

IA-I 2005–2006

Cc Ia

B´ usqueda local y algoritmos gen´ eticos

7.73