Download Tutorial Computación Evolutiva

Tutorial
Computación Evolutiva
MICAI 2006
Apizaco, Tlaxcala, Noviembre de 2006
Dr. Juan José Flores Romero
juanf@umich.mx
http://lsc.fie.umich.mx/˜juan/
Universidad Michoacana
Computación Evolutiva – p. 1/7
Contenido
Optimización
Computación Evolutiva – p. 2/7
Contenido
Optimización
Evolución
Computación Evolutiva – p. 2/7
Contenido
Optimización
Evolución
Algoritmos Genéticos
Computación Evolutiva – p. 2/7
Contenido
Optimización
Evolución
Algoritmos Genéticos
Ejemplo: Rocky Mountain National Park
Computación Evolutiva – p. 2/7
Contenido
Optimización
Evolución
Algoritmos Genéticos
Ejemplo: Rocky Mountain National Park
Programación Genética
Computación Evolutiva – p. 2/7
Contenido
Optimización
Evolución
Algoritmos Genéticos
Ejemplo: Rocky Mountain National Park
Programación Genética
Ejemplo: Modelado de Empresas
Computación Evolutiva – p. 2/7
Contenido
Optimización
Evolución
Algoritmos Genéticos
Ejemplo: Rocky Mountain National Park
Programación Genética
Ejemplo: Modelado de Empresas
Referencias (libros, revistas, conferencias, sitios web)
Computación Evolutiva – p. 2/7
Contenido
Optimización
Evolución
Algoritmos Genéticos
Ejemplo: Rocky Mountain National Park
Programación Genética
Ejemplo: Modelado de Empresas
Referencias (libros, revistas, conferencias, sitios web)
Conclusiones
Computación Evolutiva – p. 2/7
Optimización
Computación Evolutiva – p. 3/7
Optimización
f (x, y) = xSen(4x) + 1.1ySen(2y)
Computación Evolutiva – p. 3/7
Optimización
f (x, y) = xSen(4x) + 1.1ySen(2y)
a ≤ x ≤ 10 and 0 ≤ y ≤ 10
Computación Evolutiva – p. 3/7
Optimización Analítica
Extremo = Lugar donde el gradiente es cero
Computación Evolutiva – p. 4/7
Optimización Analítica
Extremo = Lugar donde el gradiente es cero
∇f (x, y) = 0
∂f
= Sen(4x) + 4xCos(4x) = 0
∂x
∂f
= 1.1Sen(2y) + 2.2yCos(2y) = 0
∂y
Computación Evolutiva – p. 4/7
Optimización Analítica
Extremo = Lugar donde el gradiente es cero
∇f (x, y) = 0
∂f
= Sen(4x) + 4xCos(4x) = 0
∂x
∂f
= 1.1Sen(2y) + 2.2yCos(2y) = 0
∂y
Estas ecuaciones se resuelven obteniendo sus raíces
xm e ym
Computación Evolutiva – p. 4/7
Optimización Analítica (Cont.)
Se calcula el Laplaciano de la funcion
∂ 2f
= 8Cos(4x) − 16xSen(4x) = 0
2
∂x
∂ 2f
= 4.4Cos(2y) − 4.4ySen(2y) = 0
2
∂y
Computación Evolutiva – p. 5/7
Optimización Analítica (Cont.)
Se calcula el Laplaciano de la funcion
∂ 2f
= 8Cos(4x) − 16xSen(4x) = 0
2
∂x
∂ 2f
= 4.4Cos(2y) − 4.4ySen(2y) = 0
2
∂y
Las raíces son un mínimo cuando
∇2 f (xm , ym ) > 0
Computación Evolutiva – p. 5/7
Métodos Basados en Gradiente
Búsqueda por coordenadas
Computación Evolutiva – p. 6/7
Métodos Basados en Gradiente
Método de Rosenbrock
Computación Evolutiva – p. 7/7
Métodos Basados en Gradiente
Descenso de Gradiente
Computación Evolutiva – p. 8/7
Métodos Basados en Gradiente
Método de Direcciones Conjugadas
Computación Evolutiva – p. 9/7
Evolución
Sistemas Inspirados en la Naturaleza
Computación Evolutiva – p. 10/7
Evolución
Sistemas Inspirados en la Naturaleza
V.g. Redes Neuronales
Computación Evolutiva – p. 10/7
Evolución
Sistemas Inspirados en la Naturaleza
V.g. Redes Neuronales
Evolución x selección natural y mutación
(Darwin, 1859)
Computación Evolutiva – p. 10/7
Evolución
Sistemas Inspirados en la Naturaleza
V.g. Redes Neuronales
Evolución x selección natural y mutación
(Darwin, 1859)
Plantas y animales evolucionaron de
especies mas primitivas
Computación Evolutiva – p. 10/7
Evolución
Sistemas Inspirados en la Naturaleza
V.g. Redes Neuronales
Evolución x selección natural y mutación
(Darwin, 1859)
Plantas y animales evolucionaron de
especies mas primitivas
Codificación Genética
Computación Evolutiva – p. 10/7
Evolución
Sistemas Inspirados en la Naturaleza
V.g. Redes Neuronales
Evolución x selección natural y mutación
(Darwin, 1859)
Plantas y animales evolucionaron de
especies mas primitivas
Codificación Genética
Supervivencia del mas fuerte (apto)
Computación Evolutiva – p. 10/7
Evolución
Sistemas Inspirados en la Naturaleza
V.g. Redes Neuronales
Evolución x selección natural y mutación
(Darwin, 1859)
Plantas y animales evolucionaron de
especies mas primitivas
Codificación Genética
Supervivencia del mas fuerte (apto)
Machos Dominantes
Computación Evolutiva – p. 10/7
Evolución
Sistemas Inspirados en la Naturaleza
V.g. Redes Neuronales
Evolución x selección natural y mutación
(Darwin, 1859)
Plantas y animales evolucionaron de
especies mas primitivas
Codificación Genética
Supervivencia del mas fuerte (apto)
Machos Dominantes
Subsistencia de Especies
Computación Evolutiva – p. 10/7
Conceptos Básicos de Evolución
Computación Evolutiva – p. 11/7
Conceptos Básicos de Evolución
Genotipo = DNA = Estructura
Computación Evolutiva – p. 11/7
Conceptos Básicos de Evolución
Genotipo = DNA = Estructura
Fenotipo = Características
Computación Evolutiva – p. 11/7
Conceptos Básicos de Evolución
Herencia ← Genoma
Computación Evolutiva – p. 12/7
Conceptos Básicos de Evolución
Herencia ← Genoma
Cambios Genéticos ← Mutación/Cruza
Computación Evolutiva – p. 12/7
Conceptos Básicos de Evolución
Herencia ← Genoma
Cambios Genéticos ← Mutación/Cruza
Genoma → Mecanismo Variación Genética
Computación Evolutiva – p. 12/7
Conceptos Básicos de Evolución
Herencia ← Genoma
Cambios Genéticos ← Mutación/Cruza
Genoma → Mecanismo Variación Genética
Computación Evolutiva – p. 12/7
Conceptos Básicos de Evolución
Evolución = Adaptación a dos niveles
Computación Evolutiva – p. 13/7
Conceptos Básicos de Evolución
Evolución = Adaptación a dos niveles
Computación Evolutiva – p. 13/7
Conceptos Básicos de Evolución
Evolución = Adaptación a dos niveles
Computación Evolutiva – p. 13/7
Conceptos Básicos de Evolución
Evolución = Adaptación a dos niveles
Adaptación = Proceso de modificación progresiva de estructuras que conducen a una mejor interacción con el
medio
Computación Evolutiva – p. 13/7
Algoritmos Genéticos
Computación Evolutiva – p. 14/7
Algoritmos Genéticos
AGs es una Estrategia Evolutiva
Computación Evolutiva – p. 14/7
Algoritmos Genéticos
AGs es una Estrategia Evolutiva
Cromosoma = Cuerda de Genes
Computación Evolutiva – p. 14/7
Algoritmos Genéticos
Computación Evolutiva – p. 15/7
Algoritmos Genéticos
Original
Computación Evolutiva – p. 15/7
Algoritmos Genéticos
Original
Cruza
Computación Evolutiva – p. 15/7
Algoritmos Genéticos
Original
Cruza
Mutación
Computación Evolutiva – p. 15/7
Algoritmos Genéticos
Computación Evolutiva – p. 16/7
Algoritmos Genéticos
Computación Evolutiva – p. 17/7
Algoritmos Genéticos
Computación Evolutiva – p. 18/7
Algoritmos Genéticos
Computación Evolutiva – p. 19/7
Algoritmos Genéticos
Creates initial population.
i < Generations
Evaluation
Termination criterion satisfied?
False
Return best individual
True
Selection
Genetic operations
Computación Evolutiva – p. 20/7
Ejemplo de Optimización
Rocky Mountain National Park
Computación Evolutiva – p. 21/7
Ejemplo de Optimización
Rocky Mountain National Park
Computación Evolutiva – p. 22/7
Cromosoma
Cuantizar
Computación Evolutiva – p. 23/7
Cromosoma
Cuantizar
Binarizar
Computación Evolutiva – p. 23/7
Cromosoma
Cuantizar
Binarizar
Formar Cromosoma
Computación Evolutiva – p. 23/7
Cromosoma
Cuantizar
Binarizar
Formar Cromosoma
Definir Función de Aptitud
Computación Evolutiva – p. 23/7
Algoritmos Genéticos Binarios
Matriz de 128 x 128
Computación Evolutiva – p. 24/7
Algoritmos Genéticos Binarios
Matriz de 128 x 128
Ngene = 7 bits
Computación Evolutiva – p. 24/7
Algoritmos Genéticos Binarios
Matriz de 128 x 128
Ngene = 7 bits
27 valores para x e y
Computación Evolutiva – p. 24/7
Algoritmos Genéticos Binarios
Matriz de 128 x 128
Ngene = 7 bits
27 valores para x e y
Cromosoma = [1100011
| {z } 0011001
| {z }]
x
y
Computación Evolutiva – p. 24/7
Población Inicial
Generada Aleatoriamente
Computación Evolutiva – p. 25/7
Población Inicial
Generada Aleatoriamente
Nipop ≥ Npop
Computación Evolutiva – p. 25/7
Población Inicial
Generada Aleatoriamente
Nipop ≥ Npop
Computación Evolutiva – p. 25/7
Población Inicial
Generada Aleatoriamente
Computación Evolutiva – p. 26/7
Selección Natural
Seleccionar los mas aptos
Computación Evolutiva – p. 27/7
Selección Natural
Seleccionar los mas aptos
Ngood ≈
Npop
2
Computación Evolutiva – p. 27/7
Selección Natural
Seleccionar los mas aptos
Ngood ≈
Npop
2
Computación Evolutiva – p. 27/7
Función de Aptitud
Importancia de Términos
Computación Evolutiva – p. 28/7
Función de Aptitud
Importancia de Términos
costo(peso, volumen) = P recio + Consumo
Computación Evolutiva – p. 28/7
Función de Aptitud
Importancia de Términos
costo(peso, volumen) = P recio + Consumo
P recio = $10, 000, Consumo = 50mpg
Computación Evolutiva – p. 28/7
Función de Aptitud
Importancia de Términos
costo(peso, volumen) = P recio + Consumo
P recio = $10, 000, Consumo = 50mpg
Normalización
Computación Evolutiva – p. 28/7
Función de Aptitud
Importancia de Términos
costo(peso, volumen) = P recio + Consumo
P recio = $10, 000, Consumo = 50mpg
Normalización
costo =
P recio−P reciolo
P reciohi −P reciolo
+
Consumo−Consumolo
Consumohi −Consumolo
Computación Evolutiva – p. 28/7
Función de Aptitud
Importancia de Términos
costo(peso, volumen) = P recio + Consumo
P recio = $10, 000, Consumo = 50mpg
Normalización
costo =
P recio−P reciolo
P reciohi −P reciolo
+
Consumo−Consumolo
Consumohi −Consumolo
Ponderación
Computación Evolutiva – p. 28/7
Función de Aptitud
Importancia de Términos
costo(peso, volumen) = P recio + Consumo
P recio = $10, 000, Consumo = 50mpg
Normalización
costo =
P recio−P reciolo
P reciohi −P reciolo
+
Consumo−Consumolo
Consumohi −Consumolo
Ponderación
recio−P reciolo
Consumo−Consumolo
costo = w PPrecio
+
(1
−
w)
Consumohi −Consumolo
hi −P reciolo
Computación Evolutiva – p. 28/7
Formación de Pares
En orden de aptitud
Computación Evolutiva – p. 29/7
Formación de Pares
En orden de aptitud
Cromosoma2i−1 ⇔ Cromosoma2i
Computación Evolutiva – p. 29/7
Formación de Pares
En orden de aptitud
Cromosoma2i−1 ⇔ Cromosoma2i
Aleatoriamente
Computación Evolutiva – p. 29/7
Formación de Pares
En orden de aptitud
Cromosoma2i−1 ⇔ Cromosoma2i
Aleatoriamente
Cromosomarandom ⇔ Cromosomarandom
Computación Evolutiva – p. 29/7
Formación de Pares
Aleatorio Ponderado (Ruleta)
Computación Evolutiva – p. 30/7
Formación de Pares
Aleatorio Ponderado (Ruleta)
f ↓ ⇒ Pmate ↑
Computación Evolutiva – p. 30/7
Formación de Pares
Aleatorio Ponderado (Ruleta)
f ↓ ⇒ Pmate ↑
Por Rango
good −n+1
Pn = NP
Ngood
j=1
j
Computación Evolutiva – p. 30/7
Formación de Pares
Aleatorio Ponderado (Ruleta)
f ↓ ⇒ Pmate ↑
Por Rango
good −n+1
Pn = NP
Ngood
j=1
j
Computación Evolutiva – p. 30/7
Formación de Pares
Aleatorio Ponderado (Ruleta)
Computación Evolutiva – p. 31/7
Formación de Pares
Aleatorio Ponderado (Ruleta)
f ↓ ⇒ Pmate ↑
Computación Evolutiva – p. 31/7
Formación de Pares
Aleatorio Ponderado (Ruleta)
f ↓ ⇒ Pmate ↑
Por Costo
Cn = coston − costoNgood +1
Cn
Pn = | PNgood
|
j=1
Cj
Computación Evolutiva – p. 31/7
Formación de Pares
Aleatorio Ponderado (Ruleta)
f ↓ ⇒ Pmate ↑
Por Costo
Cn = coston − costoNgood +1
Cn
Pn = | PNgood
|
j=1
Cj
Computación Evolutiva – p. 31/7
Formación de Pares
Por Torneo
Seleccionar un subconjunto aleatorio
El mejor es el padre
Repetir para todos los padres necesarios
Computación Evolutiva – p. 32/7
Formación de Pares
Por Torneo
Seleccionar un subconjunto aleatorio
El mejor es el padre
Repetir para todos los padres necesarios
Computación Evolutiva – p. 32/7
Cruza
2 padres ⇒ 2 hijos
Computación Evolutiva – p. 33/7
Cruza
2 padres ⇒ 2 hijos
Computación Evolutiva – p. 33/7
Mutaciones
Seleccionar bit aleatoriamente
Computación Evolutiva – p. 34/7
Mutaciones
Seleccionar bit aleatoriamente
Cambiar su valor
Computación Evolutiva – p. 34/7
Mutaciones
Seleccionar bit aleatoriamente
Cambiar su valor
1 - 5% de los bits mutan en cada iteración
Computación Evolutiva – p. 34/7
Mutaciones
Seleccionar bit aleatoriamente
Cambiar su valor
1 - 5% de los bits mutan en cada iteración
Soluciones Elite no mutan
Computación Evolutiva – p. 34/7
Siguiente Generación
Descartar los mas débiles
Computación Evolutiva – p. 35/7
Siguiente Generación
Descartar los mas débiles
Computación Evolutiva – p. 35/7
Generación 2
Computación Evolutiva – p. 36/7
Generación 3
Computación Evolutiva – p. 37/7
Generación 4
Computación Evolutiva – p. 38/7
Generación 8
Computación Evolutiva – p. 39/7
Convergencia
Nevals = Nipop + Nof f spring Ngen + Nmut Ngen
Computación Evolutiva – p. 40/7
Convergencia
Nevals = Nipop + Nof f spring Ngen + Nmut Ngen
Computación Evolutiva – p. 40/7
Parámetros Continuos
Cromosoma = vector de números reales
Computación Evolutiva – p. 41/7
Parámetros Continuos
Cromosoma = vector de números reales
Cruza de un punto ⇒ no introduce nueva información
Computación Evolutiva – p. 41/7
Parámetros Continuos
Cromosoma = vector de números reales
Cruza de un punto ⇒ no introduce nueva información
ph1 n = βpmn + (1 − β)pf n
Computación Evolutiva – p. 41/7
Parámetros Continuos
Cromosoma = vector de números reales
Cruza de un punto ⇒ no introduce nueva información
ph1 n = βpmn + (1 − β)pf n
ph2 n = (1 − β)pmn + βpf n
Computación Evolutiva – p. 41/7
Parámetros Continuos
Cromosoma = vector de números reales
Cruza de un punto ⇒ no introduce nueva información
ph1 n = βpmn + (1 − β)pf n
ph2 n = (1 − β)pmn + βpf n
β = random[0, 1]
Computación Evolutiva – p. 41/7
Parámetros Continuos
Cromosoma = vector de números reales
Cruza de un punto ⇒ no introduce nueva información
ph1 n = βpmn + (1 − β)pf n
ph2 n = (1 − β)pmn + βpf n
β = random[0, 1]
Computación Evolutiva – p. 41/7
Parámetros Continuos
Cromosoma = vector de números reales
Computación Evolutiva – p. 42/7
Parámetros Continuos
Cromosoma = vector de números reales
Mutación
Computación Evolutiva – p. 42/7
Parámetros Continuos
Cromosoma = vector de números reales
Mutación
prandom = random
Computación Evolutiva – p. 42/7
Parámetros Continuos
Cromosoma = vector de números reales
Mutación
prandom = random
1 - 20% de los parámetros mutan
Computación Evolutiva – p. 42/7
Programación Genética
Θ=
a1
· · · ap
Computación Evolutiva – p. 43/7
Programación Genética
Θ=
a1
· · · ap
'$
/
aa
aa
&%
aa
aa
aa
'$
'$
∗
@
@
&%
@
@
'$
'$
15.5
&%
yt−9
&%
+
@
@
&%
@
@
'$
'$
7.3
&%
2
&%
Computación Evolutiva – p. 43/7
PG: Cruza
#
#
/ a
aa
!!
aa
!!
"!
!
aa
!
!
a
!
#
#
+ a
aa
!!
aa
!!
"!
!
aa
!
!
a
!
#
#
#
12.2
∗
@
"!
@
@
#
"!
yt−2
"!
+
#
5
@
"!
@
@
#
"!
#
10
∗
@
"!
@
@
#
"!
#
15.5
∗
@
"!
@
@
#
"!
yt−9
"!
+
#
@
"!
@
@
#
"!
7.3
"!
2
yt−1
"!
Computación Evolutiva – p. 44/7
PG: Cruza
#
#
/ a
aa
!!
aa
!!
"!
!
aa
!
!
a
!
#
#
+ a
aa
!!
aa
!!
"!
!
aa
!
!
a
!
#
#
#
12.2
+
∗
@
"!
@
@
#
yt−2
"!
"!
#
5
@
"!
@
@
#
"!
#
10
∗
@
"!
@
@
#
#
15.5
"!
12.2
"!
yt−2
"!
"!
7.3
"!
2
#
/ a
!!
aa
!!
aa
"!
!
!
aa
!!
a
#
#
+ aa
!!
aa
!!
"!
!
aa
!
!
a
!
a
#
#
#
"!
#
"!
#
@
"!
@
@
#
yt−9
+
@
"!
@
@
#
yt−1
"!
∗
∗
@
"!
@
@
#
+
#
@
"!
@
@
#
"!
7.3
#
15.5
∗
@
"!
@
@
#
"!
"!
2
yt−9
"!
+
#
5
@
"!
@
@
#
"!
#
10
∗
@
"!
@
@
#
"!
yt−1
"!
Computación Evolutiva – p. 44/7
PG: Mutación
'$
/
aa
aa
&%
aa
aa
aa
'$
'$
∗
@
@
&%
@
@
'$
'$
15.5
&%
yt−9
&%
+
@
@
&%
@
@
'$
'$
7.3
&%
2
&%
Computación Evolutiva – p. 45/7
PG: Mutación
'$
/
aa
aa
&%
aa
aa
aa
'$
'$
+
∗
@
@
&%
@
@
'$
'$
@
@
&%
@
@
'$
'$
15.5
yt−9
&%
7.3
2
&%
&%
&%
'$
/
aa
a
&%aaa
aa
aa
'$
'$
∗
@
@
&%
@
@
'$
'$
15.5
&%
yt−9
&%
/
@
@
&%
@
@
'$
'$
7.3
&%
2
&%
Computación Evolutiva – p. 45/7
Predicción de Comportamiento
Variables Observadas:
1
C
DTA
ID
NI
0.8
RE
0.6
0.4
0.2
0
2
4
6
8
10
12
Computación Evolutiva – p. 46/7
Modelos ARIMA
Qué tipo de modelos deseamos evolucionar?
Computación Evolutiva – p. 47/7
Modelos ARIMA
Qué tipo de modelos deseamos evolucionar?
Modelos Uni-Variables:
yi,n = f (yi,n−1 , yi,n−2 , . . . , yi,n−k )
donde k = ancho de ventana
Computación Evolutiva – p. 47/7
Modelos ARIMA
Qué tipo de modelos deseamos evolucionar?
Modelos Uni-Variables:
yi,n = f (yi,n−1 , yi,n−2 , . . . , yi,n−k )
donde k = ancho de ventana
Modelos Multi-Variables:
yi,n = f (y1,n−1 , y1,n−2 , . . . , y1,n−k ,
y2,n−1 , y2,n−2 , . . . , y2,n−k ,
···
ym,n−1 , ym,n−2 , . . . , ym,n−k )
donde i[1, m], m = no. de variables en el modelo
Computación Evolutiva – p. 47/7
Modelos ARIMA
yi
CC
@CC
@
@
@
@
,
,
,
i
A
A
%
%
A
%
A
%
Aa
%
aa
%
aa
a%
X
X
n−1
1
n
t
k
Computación Evolutiva – p. 48/7
Contabilidad Financiera: Qué observar?
Computación Evolutiva – p. 49/7
Modelado de los Datos
Variables Observadas:
Computación Evolutiva – p. 50/7
Modelado de los Datos
Variables Observadas:
C = Current Ratio
= Current Assets / Current Liabilities
Computación Evolutiva – p. 50/7
Modelado de los Datos
Variables Observadas:
C = Current Ratio
= Current Assets / Current Liabilities
DTA = Debt to Total Assests Ratio
= Total Debt / Total Assets
Computación Evolutiva – p. 50/7
Modelado de los Datos
Variables Observadas:
C = Current Ratio
= Current Assets / Current Liabilities
DTA = Debt to Total Assests Ratio
= Total Debt / Total Assets
ID = Inventory Days Ratio
= Cost of Goods Sold / Average Inventory
Computación Evolutiva – p. 50/7
Modelado de los Datos
Variables Observadas:
C = Current Ratio
= Current Assets / Current Liabilities
DTA = Debt to Total Assests Ratio
= Total Debt / Total Assets
ID = Inventory Days Ratio
= Cost of Goods Sold / Average Inventory
NI = Net Income Ratio
= Net Income / Net Sales
Computación Evolutiva – p. 50/7
Modelado de los Datos
Variables Observadas:
C = Current Ratio
= Current Assets / Current Liabilities
DTA = Debt to Total Assests Ratio
= Total Debt / Total Assets
ID = Inventory Days Ratio
= Cost of Goods Sold / Average Inventory
NI = Net Income Ratio
= Net Income / Net Sales
RE = Return on Equity Ratio
= Net Income / Average Equity
Computación Evolutiva – p. 50/7
Modelado de los Datos
Variables Observadas:
1
C
DTA
ID
NI
0.8
RE
0.6
0.4
0.2
0
2
4
6
8
10
12
Computación Evolutiva – p. 51/7
Resultados: Modelos Uni-Variables
C(j) → C(n-j)
Modelo para C
C(n) =
0.01781012571544 (C(3)+0.02902518088275 C(12))
( C(4)−C(1)
+0.02158214100277 C(1)) K1 +C(1)
C(10)
K1 =
161556.7762155924 (C(1)−C(7))
(K2 −61.522976) C(9)
K2 =
2557.727875019925 (0.02158214100277 C(1)+1.2325703) (C(1)−C(7))
14.074994 C(11)−C(4)
C(10) (
−61.522976)
1.586221603025962×107 C(1)2
C(10) (−
− C(11)
C(6) ( 34.452843 −C(7)−C(1))
C(9)
+C(5)+C(1))
Computación Evolutiva – p. 52/7
Resultados: Modelos Uni-Variables
Modelo para C
Computación Evolutiva – p. 53/7
Resultados: Modelos Uni-Variables
Demás Modelos
Computación Evolutiva – p. 54/7
Resultados: Modelos Uni-Variables
Coeficientes de Correlación
Variable Entrenamiento Validación
r
rv
C
0.970
−0.844
DTA
0.966
−0.887
ID
0.997
0.809
NI
0.995
0.394
RE
0.995
0.791
Computación Evolutiva – p. 55/7
Resultados: Modelos Multi-Variables
Modelo para C
RE(7)
C(n) = (RE(6) (− −RE(10)−2
N I(4)+N I(3) − N I(3) + C(6))
+C(1) C(3) N I(3) RE(7) − (43.05711 − DT A(5)) RE(4))
(.0232249679553505 K1 K2 + N I(3) (RE(6) + RE(4)
+C(3))) + C(1)
K1 = (C(1) K3 (RE(4) − RE(7)) − C(3) RE(10))
N I(4)
K2 = ( N I(3)−DT
A(6) RE(7) +
ID(10) N I(8) RE(7)
RE(10)+2 N I(4)+N I(3)
+ RE(7)
+ID(5))
I(3)−DT A(6))
K3 = ( N I(7) (−RE(7)+N
− RE(6) + N I(8) + N I(3))
RE(4)+N I(3)
Computación Evolutiva – p. 56/7
Resultados: Modelos Multi-Variables
Modelo para C
Computación Evolutiva – p. 57/7
Resultados: Modelos Multi-Variables
Demás Modelos
Computación Evolutiva – p. 58/7
Resultados: Modelos Multi-Variables
Coeficientes de Correlación
Variable Entrenamiento Validación
r
rv
C
0.998
0.889
DTA
0.836
0.666
ID
0.926
0.922
NI
0.986
−0.555
RE
0.953
−0.235
Computación Evolutiva – p. 59/7
Modelos Uni- VS. Multi-Variables
Coeficientes de Correlación
Variable
Single
Multiple
r
rv
r
rv
C
0.970 −0.844 0.998 0.889
DTA
0.966 −0.887 0.836 0.666
ID
0.997 0.809 0.926 0.922
NI
0.995 0.394 0.986 −0.555
RE
0.995 0.791 0.953 −0.235
Computación Evolutiva – p. 60/7
Modelos Uni- VS. Multi-Variables
Coeficientes de Correlación
Variable
Single
Multiple
r
rv
r
rv
C
0.970 −0.844 0.998 0.889
DTA
0.966 −0.887 0.836 0.666
ID
0.997 0.809 0.926 0.922
NI
0.995 0.394 0.986 −0.555
RE
0.995 0.791 0.953 −0.235
Funciones Demasiado Complejas
Computación Evolutiva – p. 60/7
Modelos Uni- VS. Multi-Variables
Coeficientes de Correlación
Variable
Single
Multiple
r
rv
r
rv
C
0.970 −0.844 0.998 0.889
DTA
0.966 −0.887 0.836 0.666
ID
0.997 0.809 0.926 0.922
NI
0.995 0.394 0.986 −0.555
RE
0.995 0.791 0.953 −0.235
Funciones Demasiado Complejas
rv ’s Malas
Computación Evolutiva – p. 60/7
Reducción del Conjunto de Funciones
Corrida Preliminar
Computación Evolutiva – p. 61/7
Reducción del Conjunto de Funciones
Corrida Preliminar
Perfilar Frecuencias
Computación Evolutiva – p. 61/7
Reducción del Conjunto de Funciones
Corrida Preliminar
Perfilar Frecuencias
Eliminar Funciones Poco Usadas
Computación Evolutiva – p. 61/7
Reducción del Conjunto de Funciones
Corrida Preliminar
Perfilar Frecuencias
Eliminar Funciones Poco Usadas
Eliminar Debajo del Promedio
Computación Evolutiva – p. 61/7
Reducción del Conjunto de Funciones
Corrida Preliminar
Perfilar Frecuencias
Eliminar Funciones Poco Usadas
Eliminar Debajo del Promedio
180
Frequencies for C
Average
160
140
120
100
80
60
40
20
0
2
4
6
8
10
12
Computación Evolutiva – p. 61/7
Reducción del Conjunto de Funciones
2
1
Forecast
Forecast
Original
1.8
Original
0.8
1.6
1.4
0.6
1.2
1
0.4
0.8
0.2
0.6
0.4
0
0.2
0
-0.2
0
2
4
6
8
10
12
0
1
2
4
6
8
10
12
1
Forecast
Forecast
Original
Original
0.8
0.8
0.6
0.6
0.4
0.2
0.4
0
0.2
-0.2
-0.4
0
0
2
4
6
8
10
12
0
2
4
6
8
10
12
1
Forecast
Original
0.8
0.6
0.4
0.2
0
Computación Evolutiva – p. 62/7
-0.2
0
2
4
6
8
10
12
Modelos Uni- VS. Multi-Variables
Uni
Var.
Multi
SRF
CRF
SRF
CRF
r
rv
r
rv
r
rv
r
rv
C
0.970
−0.844
0.900
−0.555
0.998
0.889
0.795
0.976
DTA
0.966
−0.887
0.838
0.954
0.836
0.666
0.768
0.604
ID
0.997
0.809
0.993
0.996
0.926
0.922
0.946
−0.683
NI
0.995
0.394
0.979
0.956
0.986
−0.555
0.994
0.939
RE
0.995
0.791
0.993
0.448
0.953
−0.235
0.981
0.821
Computación Evolutiva – p. 63/7
Modelos Reducidos
C(n) = ID(4) + N I(11)
DT A(n) = (DT A(9) + ((CA(9) − DT A(6)) ∗ (CA(3) − N I(6))))
∗((CA(10) ∗ RE(5)) ∗ ((DT A(6) + CA(10)) − DT A(7)))
ID(n) = CA(5) − (((DT A(11) + RE(5)) ∗ N I(4))
∗(RE(5) + ((DT A(1) + ID(7)) ∗ (RE(5) + DT A(11)))))
N I(n) = N I(11) − ((ID(10) ∗ ID(5)) + −0.08576300044)
RE(n) = ((RE(11) + (N I(10) − CA(9))) + (N I(10) ∗ RE(1)))
∗CA(9)
Computación Evolutiva – p. 64/7
Otros Detalles
División Eliminada para producir Modelos más Simples
Computación Evolutiva – p. 65/7
Otros Detalles
División Eliminada para producir Modelos más Simples
20 nodos máx.
Computación Evolutiva – p. 65/7
Otros Detalles
División Eliminada para producir Modelos más Simples
20 nodos máx.
Normalización de Datos -> Comparaciones Justas
Computación Evolutiva – p. 65/7
Otros Detalles
División Eliminada para producir Modelos más Simples
20 nodos máx.
Normalización de Datos -> Comparaciones Justas
Mejor de 10 Corridas
Computación Evolutiva – p. 65/7
Otros Detalles
División Eliminada para producir Modelos más Simples
20 nodos máx.
Normalización de Datos -> Comparaciones Justas
Mejor de 10 Corridas
Tiempo Total para Modelos Simples: 30m 42.684s
Intel Xeon CPU 3.00 GHz
Cache size 1024 Kb
Computación Evolutiva – p. 65/7
Otros Detalles
División Eliminada para producir Modelos más Simples
20 nodos máx.
Normalización de Datos -> Comparaciones Justas
Mejor de 10 Corridas
Tiempo Total para Modelos Simples: 30m 42.684s
Intel Xeon CPU 3.00 GHz
Cache size 1024 Kb
ECSID, Implementado en Lisp (cmulisp)
Computación Evolutiva – p. 65/7
PG en Análisis Financiero
Enfoque Novedoso para Modelar Compañías
Computación Evolutiva – p. 66/7
PG en Análisis Financiero
Enfoque Novedoso para Modelar Compañías
Modelos Razonables para Predecir Comportamiento
Computación Evolutiva – p. 66/7
PG en Análisis Financiero
Enfoque Novedoso para Modelar Compañías
Modelos Razonables para Predecir Comportamiento
Herramienta para Selección de Portafolios
Computación Evolutiva – p. 66/7
PG en Análisis Financiero
Enfoque Novedoso para Modelar Compañías
Modelos Razonables para Predecir Comportamiento
Herramienta para Selección de Portafolios
No pudimos evitar los r’s negativos
Computación Evolutiva – p. 66/7
PG en Análisis Financiero
Enfoque Novedoso para Modelar Compañías
Modelos Razonables para Predecir Comportamiento
Herramienta para Selección de Portafolios
No pudimos evitar los r’s negativos
Se requieren conjuntos de datos más grandes (otras
compañías)
Computación Evolutiva – p. 66/7
PG en Análisis Financiero
Enfoque Novedoso para Modelar Compañías
Modelos Razonables para Predecir Comportamiento
Herramienta para Selección de Portafolios
No pudimos evitar los r’s negativos
Se requieren conjuntos de datos más grandes (otras
compañías)
Reducción del Conjunto de Funciones => Reducción de
Sobre-entrenamiento y del Espacio de Búsqueda
Computación Evolutiva – p. 66/7
PG en Análisis Financiero
Enfoque Novedoso para Modelar Compañías
Modelos Razonables para Predecir Comportamiento
Herramienta para Selección de Portafolios
No pudimos evitar los r’s negativos
Se requieren conjuntos de datos más grandes (otras
compañías)
Reducción del Conjunto de Funciones => Reducción de
Sobre-entrenamiento y del Espacio de Búsqueda
Los modelos simples pueden ser intuitivos
(Descubrimiento del Conocimiento)
Computación Evolutiva – p. 66/7
Referencias - Libros
John R. Koza. Genetic Programming: On the Programming of Computers by Means of
Natural Selection, MIT Press, 1992.
John R. Koza. Genetic Programming II: Automatic Discovery of Reusable Programs,
MIT Press, May 1994.
Randy L. Haupt and Sue Ellen Haupt. Practical Genetic Algorithms. Wiley
Interscience. 2004.
Wolfgang Banzhaf, Peter Nordin, Robert E. Keller, and Frank D. Francone. Genetic
Programming: An Introduction. On the Automatic Evolution of Computer Programs and
Its Applications. Morgan Kaufmann Series in Artificial Intelligence. 1997
David E. Goldberg. Genetic Algorithms in Search, Optimization, and Machine
Learning. Addison Wesley. 1989.
Christian Jacob. Illustrating Evolutionary Computation with Mathematica. Morgan
Kaufmann Series in Artificial Intelligence. 2001.
Computación Evolutiva – p. 67/7
Referencias - Revistas
IEEE Transactions on Evolutionary Computation.
Genetic Programming and Evolvable Machines.
Springer.
Evolutionary Computation. MIT Press.
Computación Evolutiva – p. 68/7
Referencias - Conferencias
European Conference on Genetic Programming (EuroGP 2007)
Valencia, Spain, 11th April 2007, 3 days, Deadline: November 10, 2006.
Genetic and Evolutionary Computation Conference (GECCO 2007)
London, UK, 07th July 2007, 5 days, Deadline: 17th January 2007.
IEEE Congress on Evolutionary Computation (CEC 2007)
Singapore, 25th September 2007, 4 days, Deadline: 15th March 2007.
Foundations of Genetic Algorithms (FOGA 2007)
Mexico City, Mexico, 07th January 2007.
Evo* 2007.
Valencia, Espaô
sa. 11-13 de Abril, 2007.
Computación Evolutiva – p. 69/7
Referencias - Sitios Web
http://www.genetic-programming.org/
Bibliography on Genetic Programming.
http://liinwww.ira.uka.de/bibliography/Ai/genetic.programming.html
International Society for Genetic and Evolutionary Computation.
http://www.isgec.org/
Evolvica.
http://pages.cpsc.ucalgary.ca/ jacob/Evolvica/
Genetic Programming Engine.
http://gpe.sourceforge.net/
GPLAB.
http://gplab.sourceforge.net/
EC Conferences.
http://www.genetic-programming.org/gpotherconfs.html
Evolutionary Computation Conferences.
http://www-users.york.ac.uk/˜mal503/conference.htm
Computación Evolutiva – p. 70/7
Conclusiones
Computación Evolutiva ⇒ Optimizador
Computación Evolutiva – p. 71/7
Conclusiones
Computación Evolutiva ⇒ Optimizador
Algoritmos Genéticos
Computación Evolutiva – p. 71/7
Conclusiones
Computación Evolutiva ⇒ Optimizador
Algoritmos Genéticos
Parámetros binarios y continuos
Computación Evolutiva – p. 71/7
Conclusiones
Computación Evolutiva ⇒ Optimizador
Algoritmos Genéticos
Parámetros binarios y continuos
PG es mas general
Computación Evolutiva – p. 71/7
Conclusiones
Computación Evolutiva ⇒ Optimizador
Algoritmos Genéticos
Parámetros binarios y continuos
PG es mas general
Espacio de búsqueda mucho mayor
Computación Evolutiva – p. 71/7
Conclusiones
Computación Evolutiva ⇒ Optimizador
Algoritmos Genéticos
Parámetros binarios y continuos
PG es mas general
Espacio de búsqueda mucho mayor
Determinar (expresión, programa, red, etc.) que
optimice un cierto criterio (función de aptitud)
Computación Evolutiva – p. 71/7
Conclusiones
Computación Evolutiva ⇒ Optimizador
Algoritmos Genéticos
Parámetros binarios y continuos
PG es mas general
Espacio de búsqueda mucho mayor
Determinar (expresión, programa, red, etc.) que
optimice un cierto criterio (función de aptitud)
Amplio rango de aplicaciones
Computación Evolutiva – p. 71/7
FIN
Contáctenme en juanf@umich.mx
Gracias.
Computación Evolutiva – p. 72/7