Tema 6: Busqueda´ local y algoritmos gen´eticosBusqueda´ en escalada x Idea de la busqueda´ en escalada: u Aplicar t´ecnicas de mejora iterativa a solucionar problemas representados

Inteligencia Artificial I Curso 2010–2011

Tema 6: Busqueda local yalgoritmos geneticos

Jose Antonio Alonso Jimenez

Francisco Jesus Martın Mateos

Jose L. Ruiz Reina

Dpto. de Ciencias de la Computacion e Inteligencia Artificial

Universidad de Sevilla

IA-I 2010–2011 CcIa Busqueda local y algoritmos geneticos 6.1

Introduccion

x Algoritmos de busqueda de soluciones optimas

u Buscar la mejor solucion dentro de un espacio de posibles soluciones

u Maximizar o minimizar

x Mejoras iterativas

u Empezar con un estado inicial cualquiera

u Mejorar su calidad paso a paso

x Algoritmos:

u Escalada

u Escalada con reinicio aleatorio

u Enfriamiento simulado

u Algoritmos geneticos

u Reparacion heurıstica (tema 5)


Busqueda en escalada

x Idea de la busqueda en escalada:

u Aplicar tecnicas 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 erroneo (no se mantiene un arbol de

busqueda)

u Puede verse como una escalada (ascenso o descenso)

e

Estados

heuristica

e’

h(e’)

h(e)


Implementacion de la busqueda 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


Grafo de escalada para el problema del viaje

Cádiz Córdoba Huelva Málaga

Cádiz Córdoba Granada Sevilla

Almería Córdoba Jaén Málaga4

3

2

1SevillaH = 325.08

H = 348.37 H = 240.27 H = 409.15 H = 177.91

H = 348.37 H = 240.27 H = 106.26 H = 325.08

H = 240.27 H = 150.99 H = 177.91H = 0


8–puzz

lepor

esc

ala

da:1

aheurı

stic

a

75

28

3

16

4

H =

4

1 2

75

28

3

14

6

H =

3

5

28

3

16

4

7

H =

5

728

3

16

4

5

H =

5

75

28

3 4

1 6

H =

3

75

23

14

8 6

H =

3

75

28

3

1

H =

4

4

67

5

28

3

16

4

H =

4

IA-I

2010

–201

1CcI a

Busq

ued

alo

caly

algo

ritm

osge

net

icos

6.6

8–puzz

lepor

esc

ala

da:2

aheurı

stic

a

5

28

3

16

4

7

H =

6

75

28

3

14

6

H =

4

728

3

16

4

5

H =

6

75

28

3

16

4

H =

5

75

28

3

14

6

H =

5

75

23

14

8 6

H =

3

75

28

3 4

1 6

H =

5

53

14

7682

H =

2

75

2 14

63

8

H =

4

728

3

14

H =

4 65

53

14

2 8

76

H =

2

753 4

6

12

8

H =

0

3 4 5

H =

2

12

78

6

75

23

14

8 6

H =

3

753

6

12

8

4

H =

1

75

28

3

16

4

H =

5

6

5

1 2

3

4

IA-I

2010

–201

1CcI a

Busq

ued

alo

caly

algo

ritm

osge

net

icos

6.7

Ventajas e inconvenientes

x Ventajas de la busqueda en escalada:

u Eficiente en tiempo y en espacio

u No mantiene un arbol de busqueda: mejora iterativa

x Inconvenientes: incompletitud, dependiendo de la heurıstica

u Existencia de optimos locales

u Mesetas

x En lo que sigue:

u Abandonaremos la representacion como espacio de estados y adaptaremos la

busqueda en escalada a problemas de optimizacion en los que el camino no es

importante

u Introduciremos cierta componente aleatoria en la busqueda

u Introduciremos modificaciones para intentar superar el problema de los optimos

locales


Problema del viajante

x Problema: dada una lista de ciudades, pasar por todas ellas recorriendola menor distancia posible (suponiendo que existe conexion directa entretodas ellas)

HU

SE

JACO

CA

GR

AL

MA

x No confundir con el problema del viaje


Problema del viajante

x Una posible representacion:

u Estados: ciudades visitadas

u Operadores: ir a una ciudad

u Un operador es aplicable si la ciudad esta entre las que quedan por visitar

u Aplicar una busqueda que encuentre una solucion optima

u Muy ineficiente en la practica

x Alternativa:u Estados: permutacion de las ciudades

u Operadores: obtener una nueva permutacion, usando tecnicas heurısticas e inclu-

yendo cierta aleatoriedad

u Mejorar los estados en iteraciones sucesivas

u La bondad de los estados se cuantifica por una funcion objetivo (en este caso, la

distancia total del circuito)


Caracterısticas de algunos problemas de optimizacion

x Estados y soluciones al problema

u No buscamos el camino (los estados contienen toda la informacion)

u Se busca optimizar (maximizar o minimizar) respecto de una determinada funcion

objetivo

x Estado inicial: no esta claramente definido

x Operadores:

u Se puede definir cierta nocion de nodo “sucesor” o “vecino”

u En algunos casos, gran cantidad de vecinos

u Introducimos cierta componente aleatoria y restringimos la nocion de “nodo vecino”

x Estados finales:u Todos los estados son posibles soluciones, pero se trata de encontrar una solucion

buena (respecto de la funcion objetivo)

u Si es posible, la mejor


Representacion problema de optimizacion (busqueda local)

x Eleccion de una representacion para los estados (estructura de datos)

x Funcion F-OBJETIVO(ESTADO)

u Funcion cuyo valor se trata de optimizar

u En nuestro caso, minimizar (analogamente maximizar)

x Funcion GENERA-ESTADO-INICIAL()

u Si en el problema el estado inicial no esta claramente definido, el estado inicial

puede generarse de manera aleatoria, o usando alguna tecnica heurıstica

x Funcion GENERA-SUCESOR(ESTADO)

u Genera un estado sucesor a uno dado

u Define la nocion de “vecindad” para el problema concreto

u Usualmente, existe cierta componente aleatoria en la generacion del sucesor


Representacion del problema del viajante

x Representacion de los estados:

u Cada estado sera un posible circuito, representado por una lista con todas las ciu-

dades, sin repetir, en un orden determinado

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

x Generacion aleatoria del estado inicialu Asumiremos que la funcion GENERA-ESTADO-INICIAL() obtiene un circuito inicial alea-

torio

x Funcion objetivo

u La funcion F-OBJETIVO(ESTADO) devuelve la distancia total del circuito


Representacion del problema del viajante

x Generacion de un sucesor con la funcion GENERA-SUCESOR(ESTADO)

u Eleccion aleatoria de dos ciudades e inversion del camino entre ellas

b

d

e

g

a

c

h

f

a

b

c

e

f

g

d

h

x Heurıstica + aleatoriedad


Problema del cuadrado de puntos

x Caso particular del problema del viajante:

u Las “ciudades” estan 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 solucion conocida (escalable, adecuado para pruebas)

u Representacion analoga al problema del viajante

(0,0)

(0,1)

(0,2)

(0,3)

(0,n) (n,n)

(1,0) (2,0) (3,0) (n,0)


Busqueda 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 Adaptacion de la escalada en espacios de estados a la nueva representacion

u Posible aleatoriedad: generacion de estado inicial y sucesores

u No necesitamos caminos, luego no usamos nodos


Busqueda en escalada aleatoria: ejemplos

x Ejemplos

> (load "viajante")

...

> (escalada-aleatoria)

((CADIZ HUELVA CORDOBA JAEN ALMERIA SEVILLA GRANADA MALAGA)

1366.7968)


((SEVILLA JAEN HUELVA CORDOBA MALAGA ALMERIA GRANADA CADIZ)

1488.9255)


((SEVILLA GRANADA ALMERIA CORDOBA JAEN CADIZ MALAGA HUELVA)

1431.388)


Busqueda en escalada aleatoria

x Problemas:uOptimos locales, mesetas

x 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


Busqueda 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 numero 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


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)


((CORDOBA GRANADA ALMERIA JAEN MALAGA SEVILLA HUELVA CADIZ)

1080.9673)


((MALAGA CADIZ HUELVA SEVILLA CORDOBA JAEN ALMERIA GRANADA)

929.9256)


Escalada con reinicio aleatorio: ejemplo

x Problema del cuadrado de puntos (soluciones no optimas):

> (load "puntos")

...

> (cuadrado 3)


(((3 . 3) (3 . 2) (2 . 3) (3 . 1) (2 . 0) (3 . 0)

(1 . 0) (0 . 0) (0 . 1) (0 . 3) (0 . 2) (1 . 3))

17.478706)


(((1 . 0) (0 . 0) (0 . 1) (0 . 2) (0 . 3) (1 . 3)

(3 . 2) (3 . 3) (2 . 3) (3 . 0) (3 . 1) (2 . 0))

15.812559)


Enfriamiento simulado

x Idea principal:

u Aceptar probabilısticamente estados “peores”

u La probabilidad de que un estado peor sea aceptado varıa en funcion del incremento

producido en la funcion objetivo

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

x Algoritmo inspirado en el proceso fısico-quımico de enfriamiento demetales


Enfriamiento simulado

x Enfriamiento de metalesu Sistema estable: mınimo de energıa

u Dada una temperatura, el sistema necesita tiempo para estabilizarse (perder

energıa)

u Es posible pasar momentaneamente por estados de mayor energıa, con probabilidad

dada por

p(∆E, T ) = e−∆Ek·T

u Despues de estabilizarse, se vuelve a bajar la temperatura, y el sistema se estabiliza

nuevamente en un estado de menor energıa

x Programa de enfriamiento

u Al principio (T grande) mayor probabilidad de aceptacion de soluciones candidatas

(diversificacion)

u Al final (T pequena), se aceptan pocas soluciones candidatas (intensificacion)


Enfriamiento simulado: parametros

x Generacion del estado inicial y estados vecinos

u Aleatoria, heurıstica

x Aceptacion probabilıstica

u Probabilidad de aceptacion de un estado que incrementa ∆F el valor de la funcion

objetivo: e−∆FT

x Programa de enfriamiento, en nuestro caso:

u Temperatura inicial

u Variacion de la temperatura: T ← α · Tu Numero fijo de iteraciones para cada T

x Criterio de parada

u Valor suficientemente bueno de la funcion objetivo

u Numero maximo de iteraciones sin mejora

u En nuestro caso, numero fijo de iteraciones totales


Enfr

iam

iento

sim

ula

do

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

aF-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

aVALOR-ACTUAL

2.

Iterar

un

numero

de

veces

igual

aN-ENFRIAMIENTOS

lo

siguiente:

2.1

Iterar

un

numerode

veces

igual

aN-ITERACIONES

lo

siguiente:

2.1.1

Crear

las

siguientes

variables

locales:

2.1.1.1

CANDIDATA,

una

solucionvecina

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,

ose

acepta

probabilısticamentela

solucion

candidata,

hacer

ACTUAL

y

VALOR-ACTUAL

iguales

aVECINA

yVALOR-VECINA,

respectivamente.

2.1.3

Si

VALOR-ACTUAL

es

mejor

que

VALOR-MEJOR,

actualizar

MEJOR

y

VALOR-MEJOR

con

con

ACTUAL

yVALOR-ACTUAL,

respectivamente.

2.2

Disminuir

TEMPERATURA

usando

FACTOR-DESCENSO

3.

Devolver

MEJOR

yVALOR-MEJOR

IA-I

2010

–201

1CcI a

Busq

ued

alo

caly

algo

ritm

osge

net

icos

6.25

Enfr

iam

iento

sim

ula

do

xEje

mplo

(pro

ble

ma

delvia

jante

)

>(enfriamiento-simulado

100

0.95

100

100)

((MALAGA

GRANADA

ALMERIA

JAEN

CORDOBA

SEVILLA

HUELVA

CADIZ)

929.92554)

xEje

mplo

(pro

ble

ma

de

los

punto

s)

>(cuadrado

3)

(0

12

34

56

78

910

11)

>(enfriamiento-simulado

50.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

80.95

100

100))

16

>(cuadrado

7)

...

>(second


15

0.95

100

100))

28

>(cuadrado

10)

...

>(second


20

0.95

100

100))

43.414215

>(second


20

0.95

100

100))

40

>(cuadrado

15)

...

>(second


35

0.95

100

100))

99.498474

>(second


35

0.95

500

500))

60

IA-I

2010

–201

1CcI a

Busq

ued

alo

caly

algo

ritm

osge

net

icos

6.26

Algoritmos geneticos: evolucion natural

x Procesos evolutivos

x La evolucion ocurre en los cromosomas de los individuos

x Seleccion natural: las “buenas estructuras” sobreviven con mas proba-bilidad que las demas

x Reproduccion mediante cruces y mutaciones

x Algoritmos geneticos:

u Aplicacion de estas ideas en la busqueda de soluciones optimas

u No existe un unico algoritmo genetico

u Es una denominacion para este tipo de algoritmos evolutivos


Algoritmos geneticos: representacion del problema

x Posibles soluciones representadas como individuos

u Codificacion como cromosoma (lista de genes)

u Poblacion de individuos

u Generaciones

u Genotipo y fenotipo

x Bondad de los individuosu Segun el valor de la funcion objetivo


Algoritmos geneticos: representacion del problema

x Problemas de optimizacion: un ejemplo simple

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

x Variables *GENES* y *LONGITUD-INDIVIDUOS*

u Ejemplo en la funcion cuadrado: (0 1) y 10, respectivamente

x Funcion DECODIFICA(X), obtiene el fenotipo

u En la funcion cuadrado: un cromosoma puede verse como un numero binario de

10 dıgitos (en orden inverso). El fenotipo de un cromosoma es dicho numero (en

notacion decimal)

u Ejemplo: (0 1 1 0 0 1 0 0 0 0) es un cromosoma que representa al 38

x Funcion F-OBJETIVO(X), valor de de la funcion a optimizar (actuandosobre el fenotipo)

u Ejemplo en la funcion cuadrado: la funcion que recibiendo un numero natural lo

eleva al cuadrado


Algoritmos geneticos: mecanismo evolutivo

x Reproduccion de las generaciones

u Cruces: combinacion de estructuras, aleatorio

u Mutaciones: cambio de algunos genes, aleatorio

x Mecanismo de evolucionu En general, debe ser un metodo de seleccion que favorezca a los individuos con

mejor valoracion, pero que no impida la diversidad

x En general, siempre existe una componente aleatoria


Operaciones geneticas mas comunes

x Cruces:

1 0 0 0 1 1

0110 0 0 0 1 1 0 1 1

1 0 0 0 0 0

x Mutaciones:

1 0 0 0 1 1 1 101 01


Un posible algoritmo genetico (pseudocodigo)

t := 0

Inicia-Poblacion P(t)

Evalua-Poblacion P(t)

Mientras no Fin hacer

P’ := Selecciona-Padres P(t)

P’’ := Cruza P’

P’’’ := Muta P’’

Evalua-Poblacion P’’’

P(t+1) := Selecciona-Mejores P’’’,P(t)

t:= t+1

Fin-Mientras

Devolver el mejor de P(t)


Parametros del algoritmo genetico anterior

x El algoritmo anterior debe recibir como entrada lo siguiente:

u Numero de generaciones

u Numero total de individuos en la poblacion (en cada generacion)

u Numero de individuos que intervienen en la reproduccion (cruces, dado como pro-

porcion del total)

u Padres que se escogen entre los mejores (dado como proporcion del total de padres)

u Probabilidad de que ocurra una mutacion (generalmente, muy baja)


Seleccion, mutacion y reproduccion

x En este algoritmo, la seleccion es por ranking dentro de la poblacion

x Seleccion de padres:

u Un numero fijo de padres se obtienen con los mejores de la poblacion

u El resto se escoge aleatoriamente de entre los restantes (para mentener ası la di-

versidad)

x Cruces:u Las parejas se obtienen reordenando aleatoriamente los padres y cruzando de dos

en dosx Mutacion:

u Cada gen de cada individuo se mutara segun la probabilidad dada

x Nueva generacion:

u Unir las dos generaciones y quedarse con los mejores (en igual numero que la

poblacion inicial)


Ejemplo de ejecucion (funcion 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













0


Representacion genetica del problema del viajante

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

x Decodificacion en el problema del viajante:

u DECODIFICA(X)= X

u La codificacion permite ciudades repetidas

u La funcion objetivo debe penalizar las repeticiones


Representacion genetica del problema del viajante

x Funcion objetivo:

u Penalizacion por camino incompleto

PENALIZACION-POR-INCOMPLETO(CAMINO)=

100 * |*GENES* - CAMINO|

u Combinacion de distancia con penalizacion

F-OBJETIVO(X)=

2*DISTANCIA-VIAJE(X) + 50*PENALIZACION-POR-INCOMPLETO(X)

u Los pesos de cada componente pueden ajustarse experimentalmente


Solucion al problema del viajante

x Una evaluacion

;;; (algoritmo-genetico 100 50 0.75 0.6 0.05)

;;; Mejor individuo:

;;; (HUELVA SEVILLA CORDOBA GRANADA ALMERIA JAEN MALAGA CADIZ)

;;; Valor: 2015.8258

x 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 (Solucion optima)


Otro ejemplo: problema del cuadrado magico

x Colocar en un cuadrado n× n los numeros naturales de 1 a n2, de talmanera que las filas, las columnas y las diagonales principales sumen losmismo

x Una solucion para n = 3:

4 3 8

9 5 1

2 7 6

x Soluciones representadas como listas de numeros entre 1 y n2

u Admitimos repeticiones

u La funcion objetivo penaliza las repeticiones


Otro ejemplo: cuadrado magico

x Problema parametrizado, variables globales:

u Dimension del cuadrado: N

u Suma comun: SUMA=(N·(N2 + 1))/2

x Funcion de decodificacion, DECODIFICA(X):

u Un cromosoma representa al cuadrado cuya concatenacion de filas es igual al cro-

mosoma

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


Otro ejemplo: cuadrado magico

x La funcion objetivo penaliza las repeticiones:

N-REPETICIONES(X)= "Numero de genes repetidos en X"

SUMA-DIFERENCIAS(X)=

"Suma de las diferencias (en valor absoluto) entre la suma de

los numeros de cada hilera (filas, columnas y diagonales) y SUMA"

F-OBJETIVO(X)= (1 + N-REPETICIONES(X)) * SUMA-DIFERENCIAS(X)


Solucion al cuadrado magico

x Caso n = 3

;;; Soluciones N=3 (se encuentra facilmente)

;;; ((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 generacion 125:

;;; ((7 14 9 4) (16 2 5 11) (1 15 12 6) (10 3 8 13))

16 2 5 11

7 14 9 4

1 15 12 6

10 3 8 13


Seleccion probabilıstica

x En el algoritmo anterior, la seleccion de individuos esta basada en unmetodo tipo ranking

u Esto asegura que los mejores siempre pasan a la siguiente generacion y siempre son

escogidos para cruce

u La diversidad se garantiza introduciendo individuos seleccionados aleatoriamente

x La seleccion probabilıstica es un metodo alternativo de seleccion, quefavorece a los mejores, manteniendo la diversidad

u La idea es que la probabilidad de seleccionar un individuo sera mayor cuanto mejor

sea

u Los peores individuos se seleccionaran con menos frecuencia

u Con este metodo es posible seleccionar varias veces al mismo individuo


Seleccion probabilıstica por ruleta

x Seleccion por ruleta

u Cada individuo i es seleccionado con probabilidad proporcional a su valor de la

funcion objetivo:

P (i) =Fobj(i)∑nj=1 Fobj(j)

x Importante: con este metodo de seleccion solo podemos resolver pro-blemas de maximizacion

u Si es de minimizacion habrıa que transformar la funcion objetivo

x Algoritmo para seleccionar por ruleta:

u Calcular la suma total acumulada de los valores de la funcion objetivo de todos los

miembros de la poblacion

u Generar un numero aleatorio x entre 0 y la suma total anterior

u Recorrer la poblacion, nuevamente acumulando los valores de la funcion objetivo y

seleccionando el primer cromosoma cuya suma acumulada sea mayor o igual que x


Algoritmo genetico con seleccion por ruleta

x Vamos a definir un algoritmo genetico diferente del anterior

x Usando seleccion por ruleta

u Tanto de los individuos que pasan directamente a la siguiente generacion, como de

aquellos que se usaran para cruces

x Entrada al algoritmo:

u Numero total p de individuos de la poblacion

u Un numero r, 0 <= r <= 1, fraccion de la poblacion que sera obtenida mediante

cruces

u La probabilidad m de que ocurra una mutacion


Algoritmo genetico con seleccion por ruleta (pseudocodigo)

t := 0

Inicia-Poblacion P(t)

Evalua-Poblacion P(t)

Mientras no Fin hacer

P1 := Seleccion por ruleta de (1-r)·p individuos de P(t)

P2 := Seleccion por ruleta de (r·p) individuos de P(t)

P3 := Cruza P2

P4 := Union de P1 y P3

P(t+1) := Muta P4

Evalua-Poblacion P(t+1)

t:= t+1

Fin-Mientras

Devolver el mejor de P(t)


Conclusion

x Algoritmos geneticos como proceso de busqueda local

u Mejora iterativa

u Los cruces, las mutaciones y la diversidad tratan de evitar el problema de los

optimos locales

x Existen otras muchas implementaciones de algoritmos geneticos

u Pero todas se basan en las mismas ideas de reproduccion, mutacion, seleccion de

los mejores y mantenimiento de la diversidad

x Facil de aplicar a muchos tipos de problemas:

u optimizacion, aprendizaje automatico, planificacion,. . .

x Resultados aceptables en algunos problemas

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


Bibliografıa

x Rich, E. y Knight, K. Inteligencia artificial (segunda edicion)(McGraw–Hill Interamericana, 1994).

u Cap. 3: “Tecnicas de busqueda heurıstica”.

x Russell, S. y Norvig, P. Artificial Intelligence (A Modern Approach)3rd edition (Prentice–Hall, 2010).

u Cap. 4 “Beyond classical search”.

x Mitchell, T.M. Machine Learning (McGraw-Hill, 1997)

u Cap. 9: “Genetic Algorithms”

x Michalewicz, Z. Genetic Algorithms + Data Structures = EvolutionPrograms (Springer, 1999).

u Cap. 2 “GAs: How Do They Work?”.


Documents

Tema 6: Busqueda´ local y algoritmos gen´eticosBusqueda´ en escalada x Idea de la busqueda´ en escalada: u Aplicar t´ecnicas de mejora iterativa a solucionar problemas representados