1
Download Tutorial Computación Evolutiva
Document related concepts
Transcript
Tutorial Computación Evolutiva MICAI 2006 Apizaco, Tlaxcala, Noviembre de 2006 Dr. Juan José Flores Romero [email protected] 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 [email protected] Gracias. Computación Evolutiva – p. 72/7
