PDF de programación - Técnicas de Optimización de RR.NN.AA. mediante Computación Evolutiva

Sistemas Conexionistas
Sistemas Conexionistas

Técnicas de Optimización de RR.NN.AA.
Técnicas de Optimización de RR.NN.AA.

pp

mediante Computación Evolutiva
mediante Computación Evolutiva

INTRODUCCIÓN
INTRODUCCIÓN
INTRODUCCIÓN
INTRODUCCIÓN

Técnicas de programación:
Técnicas de programación:

Convencionales

Conocimiento elevado del dominio del problema
Obtención inmediata de soluciones:

p

Se sabe cómo resolver el problema

No Convencionales
No Convencionales

Conocimiento reducido del dominio del problema
Obtención de soluciones no inmediata:

No se sabe cómo resolver el problema

Técnicas de búsqueda:
Técnicas de búsqueda:

RRNNAA, Árboles de decisión, Computación Evolutiva, etc.

Ejemplos: clasificación, predicción, modelado, etc.

Algo itmos Genéticos
Algoritmos Genéticos

ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS

Inspirada en la Teoría de la Evolución:
Inspirada en la Teoría de la Evolución:

Principio de Selección Natural

Técnicas de optimización:
Técnicas de optimización:

Maximizar
Minimizar
Minimizar

Ejemplo: función objetivo:

6

4

2

0

-2

-4

-6

0

20

40

60

80

100

120

140

160

180

200

ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS

Problema: múltiples mínimos locales

Técnicas de gradiente descendente fallarían
a a a

as d g ad

d s

d

4

3
3

2

1

0

-1

-2

-3

20

25

30

35

40

45

50

55

60
Parámetros

ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS

Problema: múltiples mínimos locales

d

Técnicas de gradiente descendente fallarían
a a a

as d g ad

d s

4

3
3

2

1

0

-1

-2

-3

20

25

30

35

40

45

50

55

60
Parámetros

ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS

Algoritmo Genético
úsqu da s u á

Búsqueda simultánea en varias zonas
a as o as

a

4

3
3

2

1

0

-1

-2

-3

20

25

30

35

40

45

50

55

60
Parámetros

ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS

l

ió

l

id

it

bl

I di
Individuo: solución al problema codificada
difi d
de forma que pueda ser procesada por el
l
algoritmo genético
Codificación: cadena de bits o números reales
Genotipo vs Fenotipo
Genotipo vs. Fenotipo
Cada individuo tiene asociado un valor de ajuste

éti

que indica la bondad de ese individuo
que indica la bondad de ese individuo
Función de ajuste
Minimizar/maximizar ajuste

Naturaleza

AA.GG.

ADN

Cadena de bits o números

Población: conjunto de individuos

ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS

Población

x1

x1

x1

x1

x2 … xN

x2 … xN

x2 … xN

…

x2 … xN

25

30

35

40

45

50

55

60

4

3

2

1

0

-1

-2
2

-3

20

ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS

Genotipo

Población

x1

x1

x1

x1

x2 … xN

x2 … xN

x2 … xN

…

x2 … xN

25

30

35

40

45

50

55

60

ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS

Genes

Población

x1

x1

x1

x1

x2 … xN

x2 … xN

x2 … xN

…

x2 … xN

25

30

35

40

45

50

55

60

4

3

2

1

0

-1

-2
2

-3

20

4

3

2

1

0

-1

-2
2

-3

20

ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS

¿Fenotipo?

Población

x1

x1

x1

x1

x2 … xN

x2 … xN

x2 … xN

…

x2 … xN

25

30

35

40

45

50

55

60

4

3

2

1

0

-1

-2
2

-3

20

ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS

Ajuste de cada individuo

Población
x2 … xN

x
x
x2 … xN

x1

x
x1

x1

4

x2 … xN

…

2.67

1 93
1.93

0.87

3 x1

x2 … xN

0.21

2

1

0

-1

-2
2

-3

20

25

30

35

40

45

50

55

60

ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS

Población ordenada

Población
x2 … xN

x
x
x2 … xN

x1

x
x1

x1

4

x2 … xN

…

0.21

0 87
0.87

1.93

3 x1

x2 … xN

2.67

2

1

0

-1

-2
2

-3

20

25

30

35

40

45

50

55

60

ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS

Funcionamiento (evolución natural):
Funcionamiento (evolución natural):

Se crea una población inicial aleatoria (generación 0)

Los valores de los genes de cada individuo son al azar
Inicialmente serán malas soluciones al problema
Inicialmente serán malas soluciones al problema
Es necesario evaluar cada individuo

Función de ajuste

Una vez se tiene una población, se crea una nueva

población a partir de la anterior (siguiente generación)
Se combinan individuos de la población (sobre todo los mejores)
Se combinan individuos de la población (sobre todo los mejores)

para crear individuos para la nueva población

Una vez se ha hallado la nueva población, se elimina la antigua

Se repite el punto anterior hasta que se cumpla un

criterio de parada
En la población hay un individuo lo suficientemente bueno
Han transcurrido un número de generaciones máximo prefijado
Todos los individuos de la población son iguales

ó

ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS

Generación 0

Generación 1

...

Generación n
Generación n

...

ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS

Generar población inicial

aleatoriamente (Generación 0)

Evaluar la población actual

Sí

Fin

¿Criterio

terminación
satisfecho?

No

Construir siguiente generación a partir de la
anterior combinando los individuos mediante
anterior combinando los individuos mediante

operadores genéticos

ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS

Generar población inicial

aleatoriamente (Generación 0)

Evaluar la población actual

Sí

Fin

¿Criterio

terminación
satisfecho?

No

Construir siguiente generación a partir de la
anterior combinando los individuos mediante
anterior combinando los individuos mediante

operadores genéticos

ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS

Construir siguiente generación a partir de la anterior combinando los

individuos mediante operadores genéticos
individuos mediante operadores genéticos

Crear nueva
población vacía

Seleccionar operación genética

Copia

Cruce (~90%)

Escoger un individuo
Escoger un individuo

Escoger dos individuos
Escoger dos individuos

Reproducir individuo

Cruzar individuos

Mutar los nuevos individuos con una probabilidad p

Insertar los individuos en la nueva población
Insertar los individuos en la nueva población

No

¿Población nueva

llena?
Sí

Establecer población = nueva población

Eliminar población antigua

ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS

Construir siguiente generación a partir de la anterior combinando los

individuos mediante operadores genéticos
individuos mediante operadores genéticos

Crear nueva
población vacía

Seleccionar operación genética

Copia

Cruce (~90%)

Escoger un individuo
Escoger un individuo

Escoger dos individuos
Escoger dos individuos

Reproducir individuo

Cruzar individuos

Mutar los nuevos individuos con una probabilidad p

Insertar los individuos en la nueva población
Insertar los individuos en la nueva población

No

¿Población nueva

llena?
Sí

Establecer población = nueva población

Eliminar población antigua

ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS

Selección de individuos:
d duos s

Escoge qué individuos se reproducirán para
p odu á pa a

s og qu
formar parte de la siguiente generación

Debe ofrecer a los mejores individuos una mayor

probabilidad de ser escogidos
IMPORTANTE: Los peores individuos también deben
IMPORTANTE: Los peores individuos también deben
de tener alguna posibilidad, aunque baja

Existen distintos algoritmos de selección

disponibles

ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS

Algoritmos de selección:

Torneo
o

o
Competición entre 2 o más

individuos

Ruleta
Ruleta
Selección de individuos de forma

probabilística
p

Sobrante estocástico
Sobrante estocástico
Universal estocástica
Muestreo determinístico
Muestreo determinístico
Etc.

ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS

Construir siguiente generación a partir de la anterior combinando los

individuos mediante operadores genéticos
individuos mediante operadores genéticos

Crear nueva
población vacía

Seleccionar operación genética

Copia

Cruce (~90%)

Escoger un individuo
Escoger un individuo

Escoger dos individuos
Escoger dos individuos

Reproducir individuo

Cruzar individuos

Mutar los nuevos individuos con una probabilidad p

Insertar los individuos en la nueva población
Insertar los individuos en la nueva población

No

¿Población nueva

llena?
Sí

Establecer población = nueva población

Eliminar población antigua

ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS
ALGORITMOS GENÉTICOS

Construir siguiente generación a partir de la anterior combinando los

individuos mediante operadores genéticos
individuos mediante operadores genéticos

Crear nueva
población vacía

Seleccionar operación genética

Copia

Cruce (~90%)

Escoger un individuo
Escoger un individuo

Escoger dos individuos
Escoger dos individuos

Reproducir individuo

Cruzar individuos

Mutar los nuevos individuos con una probabilidad p