Programación Genética, Algoritmos Evolutivos y Aprendizaje Inductivo: Hacia una solución al problema xvii de Smale en el caso real

Cruz Enrique Borges Hernández Departamento de Matemáticas, Estadística y Computación. Universidad de Cantabria 25 de marzo de 2011

This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.

Índice

1

El problema xvii de Smale Desarrollo histórico El programa de Shub y Smale Un algoritmo por búsqueda exhaustiva Problema de optimización

2

El problema de regresión simbólica Programación genética La selección del modelo Coevolución

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

2/70

Índice

1

El problema xvii de Smale Desarrollo histórico El programa de Shub y Smale Un algoritmo por búsqueda exhaustiva Problema de optimización

2

El problema de regresión simbólica Programación genética La selección del modelo Coevolución

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

2/70

Parte i: El problema xvii de Smale

El problema xvii de Smale

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

3/70

El problema xvii de Smale i.

Problema xvii de Smale (Smale 2000) ¿Existe algún algoritmo que aproxime un cero de n ecuaciones polinomiales con n incógnitas, coeficientes complejos y que, además, tenga complejidad polinomial en media? Respuesta positiva en Beltrán y Pardo 2009.

Teorema (Beltrán y Pardo 2009) Existe un algoritmo probabilista que encuentra con alta probabilidad un cero aproximado de sistemas de ecuaciones polinomiales con coeficientes complejos. Además el número de operaciones medio es polinomial en el tamaño de la entrada.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

4/70

El problema xvii de Smale i.

Problema xvii de Smale (Smale 2000) ¿Existe algún algoritmo que aproxime un cero de n ecuaciones polinomiales con n incógnitas, coeficientes complejos y que, además, tenga complejidad polinomial en media? Respuesta positiva en Beltrán y Pardo 2009.

Teorema (Beltrán y Pardo 2009) Existe un algoritmo probabilista que encuentra con alta probabilidad un cero aproximado de sistemas de ecuaciones polinomiales con coeficientes complejos. Además el número de operaciones medio es polinomial en el tamaño de la entrada.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

4/70

El problema xvii de Smale ii.

Problema xvii de Smale, caso real (Smale 2000) ¿Existe algún algoritmo que aproxime un cero de n ecuaciones polinomiales con n incógnitas, coeficientes reales y que, además, tenga complejidad polinomial en media?

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

5/70

¿Por qué es importante estudiar el caso real?

Aplicaciones prácticas Problema clásico. Resolución de problemas de optimización. Modelos matemáticos no lineales como por ejemplo: Redes eléctricas en corriente continua. Equilibrios de Nash. Trayectorias de las partes de un robot.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

6/70

¿Por qué es importante estudiar el caso real?

Aplicaciones prácticas Problema clásico. Resolución de problemas de optimización. Modelos matemáticos no lineales como por ejemplo: Redes eléctricas en corriente continua. Equilibrios de Nash. Trayectorias de las partes de un robot.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

6/70

¿Por qué es importante estudiar el caso real?

Aplicaciones prácticas Problema clásico. Resolución de problemas de optimización. Modelos matemáticos no lineales como por ejemplo: Redes eléctricas en corriente continua. Equilibrios de Nash. Trayectorias de las partes de un robot.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

6/70

¿Por qué es importante estudiar el caso real?

Aplicaciones prácticas Problema clásico. Resolución de problemas de optimización. Modelos matemáticos no lineales como por ejemplo: Redes eléctricas en corriente continua. Equilibrios de Nash. Trayectorias de las partes de un robot.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

6/70

¿Por qué es importante estudiar el caso real?

Aplicaciones prácticas Problema clásico. Resolución de problemas de optimización. Modelos matemáticos no lineales como por ejemplo: Redes eléctricas en corriente continua. Equilibrios de Nash. Trayectorias de las partes de un robot.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

6/70

¿Por qué es importante estudiar el caso real?

Aplicaciones prácticas Problema clásico. Resolución de problemas de optimización. Modelos matemáticos no lineales como por ejemplo: Redes eléctricas en corriente continua. Equilibrios de Nash. Trayectorias de las partes de un robot.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

6/70

¿Por qué no valen los resultados anteriores?

Problemas relacionados con el caso real Rn

es un espacio de medida nula en Cn .

La geometría de las soluciones reales es inestable y dispersa (Azaïs y Wschebor 2005). Hay más de una componente conexa en el espacio de trabajo (Borges y Pardo 2011, Manuscrito). Hay que reescribir prácticamente todos los resultados.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

7/70

¿Por qué no valen los resultados anteriores?

Problemas relacionados con el caso real Rn

es un espacio de medida nula en Cn .

La geometría de las soluciones reales es inestable y dispersa (Azaïs y Wschebor 2005). Hay más de una componente conexa en el espacio de trabajo (Borges y Pardo 2011, Manuscrito). Hay que reescribir prácticamente todos los resultados.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

7/70

Índice

1

El problema xvii de Smale Desarrollo histórico El programa de Shub y Smale Un algoritmo por búsqueda exhaustiva Problema de optimización

2

El problema de regresión simbólica Programación genética La selección del modelo Coevolución

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

8/70

Resolución de ecuaciones a lo largo de la historia.

Tipos de resolución Resolución Simbólica: Busca información universal sobre variedades algebraicas. Resolución Numérica: Busca información puntual sobre variedades algebraicas.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

9/70

Resolución de ecuaciones a lo largo de la historia.

Tipos de resolución Resolución Simbólica: Busca información universal sobre variedades algebraicas. Resolución Numérica: Busca información puntual sobre variedades algebraicas.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

9/70

La corriente simbólica.

Desarrollo histórico de la corriente simbólica Resolución por radicales (Galois y Lie 1846). Teoría de Eliminación (Bézout 1779) y Bases de Gröbner (Buchberger 1965). Kronecker (Kronecker 1893) y TERA (Giusti, Heintz, Morais, Morgenstern y Pardo 1998).

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

O(n!) n

O 22




Θ(2n )

10/70

La corriente simbólica.

Desarrollo histórico de la corriente simbólica Resolución por radicales (Galois y Lie 1846). Teoría de Eliminación (Bézout 1779) y Bases de Gröbner (Buchberger 1965). Kronecker (Kronecker 1893) y TERA (Giusti, Heintz, Morais, Morgenstern y Pardo 1998).

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

O(n!) n

O 22




Θ(2n )

10/70

La corriente simbólica.

Desarrollo histórico de la corriente simbólica Resolución por radicales (Galois y Lie 1846). Teoría de Eliminación (Bézout 1779) y Bases de Gröbner (Buchberger 1965). Kronecker (Kronecker 1893) y TERA (Giusti, Heintz, Morais, Morgenstern y Pardo 1998).

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

O(n!) n

O 22




Θ(2n )

10/70

Straight-line programs (slp) i. Definición (Straight-line programs) Dado un conjunto de terminales T y un conjunto de aplicaciones F := {opi : T ai −→ T } denominamos slp a una sucesión de operaciones op1 , . . . , opk tales que para todo 1 ≤ i ≤ k opi (x) := (x1 , . . . , xbi , opc1 (x), . . . , opci (x)) , donde cj < i para todo j ∈ {1, . . . , i}, xl ∈ T para todo l ∈ {1, . . . , bi } y bi + ci = ai . Denominaremos aplicación semántica Γ a la aplicación equivalente a realizar la cadena de operaciones opk . C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

11/70

Straight-line programs (slp) i. Definición (Straight-line programs) Dado un conjunto de terminales T y un conjunto de aplicaciones F := {opi : T ai −→ T } denominamos slp a una sucesión de operaciones op1 , . . . , opk tales que para todo 1 ≤ i ≤ k opi (x) := (x1 , . . . , xbi , opc1 (x), . . . , opci (x)) , donde cj < i para todo j ∈ {1, . . . , i}, xl ∈ T para todo l ∈ {1, . . . , bi } y bi + ci = ai . Denominaremos aplicación semántica Γ a la aplicación equivalente a realizar la cadena de operaciones opk . C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

11/70

Straight-line programs (slp) ii. Usos Modelo de computación para dar cotas inferiores de complejidad. Estructura de datos para la codificación de aplicaciones. Figura: Codificación de un slp.  u1 := x ∗ x      u2 := u1 ∗ u1    u := u ∗ x

f1 ≡

3

Figura: Representación gráfica de un slp.

f1 ≡ ∗

+ +

1

 u4 := u3 + x     u5 := u4 + u1   

+ ∗ ∗

u6 := u5 + u4 x

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

12/70

Straight-line programs (slp) ii. Usos Modelo de computación para dar cotas inferiores de complejidad. Estructura de datos para la codificación de aplicaciones. Figura: Codificación de un slp.  u1 := x ∗ x      u2 := u1 ∗ u1    u := u ∗ x

f1 ≡

3

Figura: Representación gráfica de un slp.

f1 ≡ ∗

+ +

1

 u4 := u3 + x     u5 := u4 + u1   

+ ∗ ∗

u6 := u5 + u4 x

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

12/70

Straight-line programs (slp) ii. Usos Modelo de computación para dar cotas inferiores de complejidad. Estructura de datos para la codificación de aplicaciones. Figura: Codificación de un slp.  u1 := x ∗ x      u2 := u1 ∗ u1    u := u ∗ x

f1 ≡

3

Figura: Representación gráfica de un slp.

f1 ≡ ∗

+ +

1

 u4 := u3 + x     u5 := u4 + u1   

+ ∗ ∗

u6 := u5 + u4 x

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

12/70

Straight-line programs (slp) ii. Usos Modelo de computación para dar cotas inferiores de complejidad. Estructura de datos para la codificación de aplicaciones. Figura: Codificación de un slp.  u1 := x ∗ x      u2 := u1 ∗ u1    u := u ∗ x

f1 ≡

3

Figura: Representación gráfica de un slp.

f1 ≡ ∗

+ +

1

 u4 := u3 + x     u5 := u4 + u1   

+ ∗ ∗

u6 := u5 + u4 x

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

12/70

La corriente numérica.

Desarrollo histórico de la corriente numérica Aproximación de radicales (Mesopotamia ∼1800 AEC). Método de Newton (Newton 1711). Deformación Homotópica (Shub y Smale 1996). Búsquedas Exhaustivas (Cucker, Krick, Malajovich y Wschebor 2008). Conjuntos Cuestores (Beltrán y Pardo 2008). Heurísticas (Bates, Hauenstein, Sommese y Wampler 2010).

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

13/70

La corriente numérica.

Desarrollo histórico de la corriente numérica Aproximación de radicales (Mesopotamia ∼1800 AEC). Método de Newton (Newton 1711). Deformación Homotópica (Shub y Smale 1996). Búsquedas Exhaustivas (Cucker, Krick, Malajovich y Wschebor 2008). Conjuntos Cuestores (Beltrán y Pardo 2008). Heurísticas (Bates, Hauenstein, Sommese y Wampler 2010).

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

13/70

La corriente numérica.

Desarrollo histórico de la corriente numérica Aproximación de radicales (Mesopotamia ∼1800 AEC). Método de Newton (Newton 1711). Deformación Homotópica (Shub y Smale 1996). Búsquedas Exhaustivas (Cucker, Krick, Malajovich y Wschebor 2008). Conjuntos Cuestores (Beltrán y Pardo 2008). Heurísticas (Bates, Hauenstein, Sommese y Wampler 2010).

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

13/70

La corriente numérica.

Desarrollo histórico de la corriente numérica Aproximación de radicales (Mesopotamia ∼1800 AEC). Método de Newton (Newton 1711). Deformación Homotópica (Shub y Smale 1996). Búsquedas Exhaustivas (Cucker, Krick, Malajovich y Wschebor 2008). Conjuntos Cuestores (Beltrán y Pardo 2008). Heurísticas (Bates, Hauenstein, Sommese y Wampler 2010).

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

13/70

La corriente numérica.

Desarrollo histórico de la corriente numérica Aproximación de radicales (Mesopotamia ∼1800 AEC). Método de Newton (Newton 1711). Deformación Homotópica (Shub y Smale 1996). Búsquedas Exhaustivas (Cucker, Krick, Malajovich y Wschebor 2008). Conjuntos Cuestores (Beltrán y Pardo 2008). Heurísticas (Bates, Hauenstein, Sommese y Wampler 2010).

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

13/70

La corriente numérica.

Desarrollo histórico de la corriente numérica Aproximación de radicales (Mesopotamia ∼1800 AEC). Método de Newton (Newton 1711). Deformación Homotópica (Shub y Smale 1996). Búsquedas Exhaustivas (Cucker, Krick, Malajovich y Wschebor 2008). Conjuntos Cuestores (Beltrán y Pardo 2008). Heurísticas (Bates, Hauenstein, Sommese y Wampler 2010).

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

13/70

El método de Newton i.

Definición (Operador de Newton) Raíz de la aproximación lineal a la aplicación f el punto x. Nf (x) := x − Dx−1 (f )f (x).

Definición (Método de Newton) Aplicación iterada del operador de Newton sobre el punto x0 . xn := Nf (xn−1 ) = Nfn (x0 ).

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

14/70

El método de Newton i.

Definición (Operador de Newton) Raíz de la aproximación lineal a la aplicación f el punto x. Nf (x) := x − Dx−1 (f )f (x).

Definición (Método de Newton) Aplicación iterada del operador de Newton sobre el punto x0 . xn := Nf (xn−1 ) = Nfn (x0 ).

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

14/70

El método de Newton ii. f (x)

x0 C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

x

15/70

El método de Newton ii. f (x)

x3 x2 C.E. Borges

x1

x0

Hacia una solución al problema xvii de Smale en el caso real

x

15/70

El método de Newton ii.

¿Cómo escogemos x0 ?

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

16/70

Índice

1

El problema xvii de Smale Desarrollo histórico El programa de Shub y Smale Un algoritmo por búsqueda exhaustiva Problema de optimización

2

El problema de regresión simbólica Programación genética La selección del modelo Coevolución

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

17/70

El programa de Shub y Smale i.

Definición (Cero aproximado) x0 es un cero aproximado si el método de Newton cumple: kxn+1 − xn k ≤

1 kx1 − x0 k . 22n −1

α-Teorema (Shub y Smale 1993) Si α(f , x0 ) < α0 entonces x0 es un cero aproximado.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

18/70

El programa de Shub y Smale i.

Definición (Cero aproximado) x0 es un cero aproximado si el método de Newton cumple: kxn+1 − xn k ≤

1 kx1 − x0 k . 22n −1

α-Teorema (Shub y Smale 1993) Si α(f , x0 ) < α0 entonces x0 es un cero aproximado.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

18/70

El programa de Shub y Smale ii.

γ-Teorema (Shub y Smale 1993) Si ζ es una raíz de f entonces existe una bola de centro ζ y radio Rζ := γ(f , ζ) tal que todos sus puntos son ceros aproximados.

Definición (Radio de convergencia) Denominaremos radio de convergencia el menor de los valores Rζ .

Corolario (Distancia entre raíces h) La distancia mínima h entre dos raíces cualesquiera del sistema es al menos dos veces el valor del radio de convergencia.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

19/70

El programa de Shub y Smale ii.

γ-Teorema (Shub y Smale 1993) Si ζ es una raíz de f entonces existe una bola de centro ζ y radio Rζ := γ(f , ζ) tal que todos sus puntos son ceros aproximados.

Definición (Radio de convergencia) Denominaremos radio de convergencia el menor de los valores Rζ .

Corolario (Distancia entre raíces h) La distancia mínima h entre dos raíces cualesquiera del sistema es al menos dos veces el valor del radio de convergencia.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

19/70

El programa de Shub y Smale ii.

γ-Teorema (Shub y Smale 1993) Si ζ es una raíz de f entonces existe una bola de centro ζ y radio Rζ := γ(f , ζ) tal que todos sus puntos son ceros aproximados.

Definición (Radio de convergencia) Denominaremos radio de convergencia el menor de los valores Rζ .

Corolario (Distancia entre raíces h) La distancia mínima h entre dos raíces cualesquiera del sistema es al menos dos veces el valor del radio de convergencia.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

19/70

El programa de Shub y Smale iii. Principales problemas Información puntual. Resultados teóricos inmanejables. Computacionalmente costosas de calcular.

Definición (Condicionamiento normalizado) El condicionamiento normalizado µnorm (f , x) de un sistema de ecuaciones f en un punto x es la inversa de una distancia desde el punto (f , x) a la variedad discriminante Σ.

µ-Teorema (Shub y Smale 1993) γ(f , x) < cµnorm (f , x). C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

20/70

El programa de Shub y Smale iii. Principales problemas Información puntual. Resultados teóricos inmanejables. Computacionalmente costosas de calcular.

Definición (Condicionamiento normalizado) El condicionamiento normalizado µnorm (f , x) de un sistema de ecuaciones f en un punto x es la inversa de una distancia desde el punto (f , x) a la variedad discriminante Σ.

µ-Teorema (Shub y Smale 1993) γ(f , x) < cµnorm (f , x). C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

20/70

El programa de Shub y Smale iii. Principales problemas Información puntual. Resultados teóricos inmanejables. Computacionalmente costosas de calcular.

Definición (Condicionamiento normalizado) El condicionamiento normalizado µnorm (f , x) de un sistema de ecuaciones f en un punto x es la inversa de una distancia desde el punto (f , x) a la variedad discriminante Σ.

µ-Teorema (Shub y Smale 1993) γ(f , x) < cµnorm (f , x). C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

20/70

El programa de Shub y Smale iii. Principales problemas Información puntual. Resultados teóricos inmanejables. Computacionalmente costosas de calcular.

Definición (Condicionamiento normalizado) El condicionamiento normalizado µnorm (f , x) de un sistema de ecuaciones f en un punto x es la inversa de una distancia desde el punto (f , x) a la variedad discriminante Σ.

µ-Teorema (Shub y Smale 1993) γ(f , x) < cµnorm (f , x). C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

20/70

El programa de Shub y Smale iii. Principales problemas Información puntual. Resultados teóricos inmanejables. Computacionalmente costosas de calcular.

Definición (Condicionamiento normalizado) El condicionamiento normalizado µnorm (f , x) de un sistema de ecuaciones f en un punto x es la inversa de una distancia desde el punto (f , x) a la variedad discriminante Σ.

µ-Teorema (Shub y Smale 1993) γ(f , x) < cµnorm (f , x). C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

20/70

El programa de Shub y Smale iii. Principales problemas Información puntual. Resultados teóricos inmanejables. Computacionalmente costosas de calcular.

Definición (Condicionamiento normalizado) El condicionamiento normalizado µnorm (f , x) de un sistema de ecuaciones f en un punto x es la inversa de una distancia desde el punto (f , x) a la variedad discriminante Σ.

µ-Teorema (Shub y Smale 1993) γ(f , x) < cµnorm (f , x). C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

20/70

El programa de Shub y Smale iii. Principales problemas Información puntual. Resultados teóricos inmanejables. Computacionalmente costosas de calcular.

Definición (Condicionamiento normalizado) El condicionamiento normalizado µnorm (f , x) de un sistema de ecuaciones f en un punto x es la inversa de una distancia desde el punto (f , x) a la variedad discriminante Σ.

µ-Teorema (Shub y Smale 1993) γ(f , x) < cµnorm (f , x). C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

20/70

Principales resultados i.

Cotas µnorm caso real (Borges y Pardo 2008) El valor esperado para el µnorm de un sistema de ecuaciones polinomiales con coeficientes reales f está acotado superior e inferiormente por una cantidad polinomial en D y N .

Cota radio de convergencia (Borges y Pardo 2008) El valor esperado para el radio de convergencia h está acotado inferiormente por una cantidad inversamente proporcional a un polinomio en D y N .

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

21/70

Principales resultados i.

Cotas µnorm caso real (Borges y Pardo 2008) El valor esperado para el µnorm de un sistema de ecuaciones polinomiales con coeficientes reales f está acotado superior e inferiormente por una cantidad polinomial en D y N .

Cota radio de convergencia (Borges y Pardo 2008) El valor esperado para el radio de convergencia h está acotado inferiormente por una cantidad inversamente proporcional a un polinomio en D y N .

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

21/70

Algoritmos de deformación homotópica complejos i. Cn

(ζd , f )

ζd

f

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

C P(d)

22/70

Algoritmos de deformación homotópica complejos i. Cn

(ζd , f )

ζd

f

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

C P(d)

22/70

Algoritmos de deformación homotópica complejos i. Cn

(ζd , f )

ζd

ζc (ζc , g)

g

C.E. Borges

f

Hacia una solución al problema xvii de Smale en el caso real

C P(d)

22/70

Algoritmos de deformación homotópica complejos i. Cn

(ζd , f )

ζd

ζc (ζc , g)x0

g

C.E. Borges

f

Hacia una solución al problema xvii de Smale en el caso real

C P(d)

22/70

Algoritmos de deformación homotópica complejos i. Cn

(ζd , f )

ζd

ζc (ζc , g)x0

g ft 1

C.E. Borges

f

Hacia una solución al problema xvii de Smale en el caso real

C P(d)

22/70

Algoritmos de deformación homotópica complejos i. Cn

(ζd , f )

ζd

x1 ζc (ζc , g)x0

g ft 1

C.E. Borges

f

Hacia una solución al problema xvii de Smale en el caso real

C P(d)

22/70

Algoritmos de deformación homotópica complejos i. Cn

(ζd , f )

ζd

x1 ζc (ζc , g)x0

g ft ft 1 2

C.E. Borges

f

Hacia una solución al problema xvii de Smale en el caso real

C P(d)

22/70

Algoritmos de deformación homotópica complejos i. Cn

(ζd , f )

ζd x2 x1 ζc (ζc , g)x0

g ft ft 1 2

C.E. Borges

f

Hacia una solución al problema xvii de Smale en el caso real

C P(d)

22/70

Algoritmos de deformación homotópica complejos i. Cn

ζd x2 x3 x4 x5 x6 x7

x8

(ζd , f )

x9

x1 ζc (ζc , g)x0

g ft ft ft ft ft ft ft ft ft 1 2 3 4 5 6 7 8 9

C.E. Borges

f

Hacia una solución al problema xvii de Smale en el caso real

C P(d)

22/70

Algoritmos de deformación homotópica complejos ii.

Definición (Sucesión de Newton) A toda sucesión de puntos xk con las propiedades anteriores la denominaremos sucesión de Newton.

Definición (Homotopía lineal) Si la curva entre dos sistemas es lineal y la partición uniforme decimos que aplicamos una homotopía lineal.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

23/70

Algoritmos de deformación homotópica complejos ii.

Definición (Sucesión de Newton) A toda sucesión de puntos xk con las propiedades anteriores la denominaremos sucesión de Newton.

Definición (Homotopía lineal) Si la curva entre dos sistemas es lineal y la partición uniforme decimos que aplicamos una homotopía lineal.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

23/70

Algoritmos de deformación homotópica complejos iii. Existencia de homotopía (Shub y Smale 1996) Para cualquier curva que una dos sistemas sin cruzar la variedad discriminante Σ existe una partición k del intervalo [0, 1] que solo depende de la longitud y del peor condicionamiento µnorm de los sistemas a lo largo de la curva de forma que el procedimiento anterior genera una sucesión de Newton.

Homotopía lineal (Shub y Smale 1994) Existe un sistema g tal que, para todo sistema f no perteneciente a Σ la homotopía lineal entre f y g genera una sucesión de Newton usando un número de pasos polinomial en n, N y el condicionamiento µnorm de los sistemas a lo largo de la recta.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

24/70

Algoritmos de deformación homotópica complejos iii. Existencia de homotopía (Shub y Smale 1996) Para cualquier curva que una dos sistemas sin cruzar la variedad discriminante Σ existe una partición k del intervalo [0, 1] que solo depende de la longitud y del peor condicionamiento µnorm de los sistemas a lo largo de la curva de forma que el procedimiento anterior genera una sucesión de Newton.

Homotopía lineal (Shub y Smale 1994) Existe un sistema g tal que, para todo sistema f no perteneciente a Σ la homotopía lineal entre f y g genera una sucesión de Newton usando un número de pasos polinomial en n, N y el condicionamiento µnorm de los sistemas a lo largo de la recta.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

24/70

Algoritmos de deformación homotópica complejos iv. Conjetura del singleton (Shub y Smale 1994) Usando la homotopía lineal el siguiente sistema produce siempre sucesiones de Newton. 1/2

d1 X0d1 −1 X1 = 0 .. . dn1/2 X0dn −1 Xn = 0.

Teorema del conjunto cuestor (Beltrán y Pardo 2008) Existe un conjunto de sistemas G tal que: Es fácil generar sistemas en G. Se conoce al menos una raíz de todos los sistemas. La homotopía lineal genera, con alta probabilidad, una sucesión de Newton usando un número polinomial de pasos en n y N . C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

25/70

Algoritmos de deformación homotópica complejos iv. Conjetura del singleton (Shub y Smale 1994) Usando la homotopía lineal el siguiente sistema produce siempre sucesiones de Newton. 1/2

d1 X0d1 −1 X1 = 0 .. . dn1/2 X0dn −1 Xn = 0.

Teorema del conjunto cuestor (Beltrán y Pardo 2008) Existe un conjunto de sistemas G tal que: Es fácil generar sistemas en G. Se conoce al menos una raíz de todos los sistemas. La homotopía lineal genera, con alta probabilidad, una sucesión de Newton usando un número polinomial de pasos en n y N . C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

25/70

Algoritmos de deformación homotópica reales. Teorema (Borges y Pardo 2011, Manuscrito) El número de componentes conexas del espacio de sistemas no singulares es al menos D. Existen componentes conexas que no son convexas. En particular, la conjetura singleton es FALSA sobre los reales.

Homotopía isobárica (Borges y Pardo 2011, Manuscrito) Dado un sistema f y una raíz ζ se tiene que existe una curva contenida en la misma componente conexa y cuyo condicionamiento µnorm es constante a lo largo de ella.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

26/70

Algoritmos de deformación homotópica reales. Teorema (Borges y Pardo 2011, Manuscrito) El número de componentes conexas del espacio de sistemas no singulares es al menos D. Existen componentes conexas que no son convexas. En particular, la conjetura singleton es FALSA sobre los reales.

Homotopía isobárica (Borges y Pardo 2011, Manuscrito) Dado un sistema f y una raíz ζ se tiene que existe una curva contenida en la misma componente conexa y cuyo condicionamiento µnorm es constante a lo largo de ella.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

26/70

Algoritmos de deformación homotópica reales. Teorema (Borges y Pardo 2011, Manuscrito) El número de componentes conexas del espacio de sistemas no singulares es al menos D. Existen componentes conexas que no son convexas. En particular, la conjetura singleton es FALSA sobre los reales.

Homotopía isobárica (Borges y Pardo 2011, Manuscrito) Dado un sistema f y una raíz ζ se tiene que existe una curva contenida en la misma componente conexa y cuyo condicionamiento µnorm es constante a lo largo de ella.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

26/70

Algoritmos de deformación homotópica reales. Teorema (Borges y Pardo 2011, Manuscrito) El número de componentes conexas del espacio de sistemas no singulares es al menos D. Existen componentes conexas que no son convexas. En particular, la conjetura singleton es FALSA sobre los reales.

Homotopía isobárica (Borges y Pardo 2011, Manuscrito) Dado un sistema f y una raíz ζ se tiene que existe una curva contenida en la misma componente conexa y cuyo condicionamiento µnorm es constante a lo largo de ella.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

26/70

Algoritmos de deformación homotópica reales. Teorema (Borges y Pardo 2011, Manuscrito) El número de componentes conexas del espacio de sistemas no singulares es al menos D. Existen componentes conexas que no son convexas. En particular, la conjetura singleton es FALSA sobre los reales.

Homotopía isobárica (Borges y Pardo 2011, Manuscrito) Dado un sistema f y una raíz ζ se tiene que existe una curva contenida en la misma componente conexa y cuyo condicionamiento µnorm es constante a lo largo de ella.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

26/70

Índice

1

El problema xvii de Smale Desarrollo histórico El programa de Shub y Smale Un algoritmo por búsqueda exhaustiva Problema de optimización

2

El problema de regresión simbólica Programación genética La selección del modelo Coevolución

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

27/70

Cota sobre la norma de las raíces de un sistema.

Caja de zapatos (Borges y Pardo 2008) Sea n = m, la probabilidad de que la norma de todas las raíces de un sistema de ecuaciones polinomiales con coeficientes reales f sea mayor que H , con H ∈ O(Dε−2 ), es menor que 1 − ε.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

28/70

Prueba α∗ para ceros aproximados i. Definición (α∗ ) α∗ (f , x) := kNf (x) − xk µnorm (f , x).

α∗ -Teorema (Borges y Pardo 2011, Manuscrito) Dado un sistema de ecuaciones polinomiales f y un punto afín x0 de norma acotada por H . Entonces, x0 es un cero aproximado de f con probabilidad 1 − ε si se cumple alguna de las siguientes condiciones: 1 2

α∗ (f , x0 ) ≤ α0 . αc∗ (f , x0 ) ≤ α0 donde αc∗ (f , x0 ) := α∗ (f , xk ) y xk es una iteración de Newton de k ∈ O(log log((nD)2 N ε−3 ) pasos.

En particular, testear el ser cero aproximado está en BPP. C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

29/70

Prueba α∗ para ceros aproximados i. Definición (α∗ ) α∗ (f , x) := kNf (x) − xk µnorm (f , x).

α∗ -Teorema (Borges y Pardo 2011, Manuscrito) Dado un sistema de ecuaciones polinomiales f y un punto afín x0 de norma acotada por H . Entonces, x0 es un cero aproximado de f con probabilidad 1 − ε si se cumple alguna de las siguientes condiciones: 1 2

α∗ (f , x0 ) ≤ α0 . αc∗ (f , x0 ) ≤ α0 donde αc∗ (f , x0 ) := α∗ (f , xk ) y xk es una iteración de Newton de k ∈ O(log log((nD)2 N ε−3 ) pasos.

En particular, testear el ser cero aproximado está en BPP. C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

29/70

Prueba α∗ para ceros aproximados i. Definición (α∗ ) α∗ (f , x) := kNf (x) − xk µnorm (f , x).

α∗ -Teorema (Borges y Pardo 2011, Manuscrito) Dado un sistema de ecuaciones polinomiales f y un punto afín x0 de norma acotada por H . Entonces, x0 es un cero aproximado de f con probabilidad 1 − ε si se cumple alguna de las siguientes condiciones: 1 2

α∗ (f , x0 ) ≤ α0 . αc∗ (f , x0 ) ≤ α0 donde αc∗ (f , x0 ) := α∗ (f , xk ) y xk es una iteración de Newton de k ∈ O(log log((nD)2 N ε−3 ) pasos.

En particular, testear el ser cero aproximado está en BPP. C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

29/70

Algoritmo exhaustivo i.

Caja de zapato H Distancia entre raíces h

=⇒

Construimos un retículo L con al menos un cero aproximado.

Algoritmo exhaustivo En particular, realizando la prueba α∗ sobre todos los puntos del retículo L obtenemos un algoritmo que resuelve el problema xvii de Smale.

PROBLEMA El cardinal de L es de orden O(Dn N ε−2 )

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

30/70

Algoritmo exhaustivo i.

Caja de zapato H Distancia entre raíces h

=⇒

Construimos un retículo L con al menos un cero aproximado.

Algoritmo exhaustivo En particular, realizando la prueba α∗ sobre todos los puntos del retículo L obtenemos un algoritmo que resuelve el problema xvii de Smale.

PROBLEMA El cardinal de L es de orden O(Dn N ε−2 )

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

30/70

Algoritmo exhaustivo i.

Caja de zapato H Distancia entre raíces h

=⇒

Construimos un retículo L con al menos un cero aproximado.

Algoritmo exhaustivo En particular, realizando la prueba α∗ sobre todos los puntos del retículo L obtenemos un algoritmo que resuelve el problema xvii de Smale.

PROBLEMA El cardinal de L es de orden O(Dn N ε−2 )

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

30/70

Índice

1

El problema xvii de Smale Desarrollo histórico El programa de Shub y Smale Un algoritmo por búsqueda exhaustiva Problema de optimización

2

El problema de regresión simbólica Programación genética La selección del modelo Coevolución

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

31/70

Algoritmos de optimización i.

Primer intento Transformar el problema: encontrar ζ ∈ Rn : f (ζ) = 0 en encontrar ζ ∈ Rn : min kf (ζ)k . kζk≤H

¡Podemos usar algoritmos de optimización!

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

32/70

Algoritmos de optimización i.

Primer intento Transformar el problema: encontrar ζ ∈ Rn : f (ζ) = 0 en encontrar ζ ∈ Rn : min kf (ζ)k . kζk≤H

¡Podemos usar algoritmos de optimización!

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

32/70

Problemas algoritmos de optimización i. El resultado puede estar MUY alejado de una raíz.

2

1

−1,5

−1

−0,5

0,5

1

1,5

−1 C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

33/70

Algoritmos de optimización ii.

Segundo intento Transformar el problema: encontrar ζ ∈ Rn : f (ζ) = 0 en encontrar ζ ∈ Rn : min α∗ (f , x). kζk≤H

¡Podemos usar el α∗ -teorema!

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

34/70

Algoritmos de optimización ii.

Segundo intento Transformar el problema: encontrar ζ ∈ Rn : f (ζ) = 0 en encontrar ζ ∈ Rn : min α∗ (f , x). kζk≤H

¡Podemos usar el α∗ -teorema!

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

34/70

Algoritmos evolutivos i. Algoritmo evolutivos Decimos que un procedimiento es un «algoritmo» evolutivo si su comportamiento está gobernado por la siguiente cadena de Markov: pk := Tf (pk−1 ), donde pi denota una distribución de probabilidad sobre el espacio de soluciones y Tf es la aplicación de transferencia que modifica dichas distribuciones en base a una función fitness f .

Resultados empíricos (Koza 1992) Empíricamente se han mostrado más eficientes que una búsqueda aleatoria a la hora de resolver diversos problemas de optimización. C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

35/70

Algoritmos evolutivos i. Algoritmo evolutivos Decimos que un procedimiento es un «algoritmo» evolutivo si su comportamiento está gobernado por la siguiente cadena de Markov: pk := Tf (pk−1 ), donde pi denota una distribución de probabilidad sobre el espacio de soluciones y Tf es la aplicación de transferencia que modifica dichas distribuciones en base a una función fitness f .

Resultados empíricos (Koza 1992) Empíricamente se han mostrado más eficientes que una búsqueda aleatoria a la hora de resolver diversos problemas de optimización. C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

35/70

Algoritmos evolutivos ii. Elementos comunes Población de candidatos a solución. Mecanismos para transformar las poblaciones. Función fitness de cada candidato a solución. Se guardan los mejores elementos de la población.

Ejemplos Algoritmos Genéticos (GA) Evolución Diferencial (DE) Enfriamiento Simulado (SA) Enjambres de Partículas (PSO) C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

36/70

Algoritmos evolutivos ii. Elementos comunes Población de candidatos a solución. Mecanismos para transformar las poblaciones. Función fitness de cada candidato a solución. Se guardan los mejores elementos de la población.

Ejemplos Algoritmos Genéticos (GA) Evolución Diferencial (DE) Enfriamiento Simulado (SA) Enjambres de Partículas (PSO) C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

36/70

Algoritmos evolutivos ii. Elementos comunes Población de candidatos a solución. Mecanismos para transformar las poblaciones. Función fitness de cada candidato a solución. Se guardan los mejores elementos de la población.

Ejemplos Algoritmos Genéticos (GA) Evolución Diferencial (DE) Enfriamiento Simulado (SA) Enjambres de Partículas (PSO) C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

36/70

Algoritmos evolutivos ii. Elementos comunes Población de candidatos a solución. Mecanismos para transformar las poblaciones. Función fitness de cada candidato a solución. Se guardan los mejores elementos de la población.

Ejemplos Algoritmos Genéticos (GA) Evolución Diferencial (DE) Enfriamiento Simulado (SA) Enjambres de Partículas (PSO) C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

36/70

Algoritmos evolutivos ii. Elementos comunes Población de candidatos a solución. Mecanismos para transformar las poblaciones. Función fitness de cada candidato a solución. Se guardan los mejores elementos de la población.

Ejemplos Algoritmos Genéticos (GA) Evolución Diferencial (DE) Enfriamiento Simulado (SA)

Operadores de cruce y mutación. Distintas formas de sustituir la población.

Enjambres de Partículas (PSO) C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

36/70

Algoritmos evolutivos ii. Elementos comunes Población de candidatos a solución. Mecanismos para transformar las poblaciones. Función fitness de cada candidato a solución. Se guardan los mejores elementos de la población. Similar al anterior

Ejemplos Algoritmos Genéticos (GA) Evolución Diferencial (DE)

Operador de cruce con tres elementos.

Enfriamiento Simulado (SA) Enjambres de Partículas (PSO) C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

36/70

Algoritmos evolutivos ii. Elementos comunes Población de candidatos a solución. Mecanismos para transformar las poblaciones. Función fitness de cada candidato a solución. Se guardan los mejores elementos de la población.

Ejemplos Algoritmos Genéticos (GA) Evolución Diferencial (DE) Enfriamiento Simulado (SA) Enjambres de Partículas (PSO) C.E. Borges

Grandes cambios en las primeras poblaciones, luego más suaves. Se aceptan todos los cambios positivos y algunos de los negativos.

Hacia una solución al problema xvii de Smale en el caso real

36/70

Algoritmos evolutivos ii. Elementos comunes Población de candidatos a solución. Mecanismos para transformar las poblaciones. Función fitness de cada candidato a solución. Se guardan los mejores elementos de la población.

Ejemplos Algoritmos Genéticos (GA) Evolución Diferencial (DE) Enfriamiento Simulado (SA)

Se mantiene una élite global y otra local. En el mecanismo evolutivo se tienen en cuenta ambas élites.

Enjambres de Partículas (PSO) C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

36/70

Protocolo de experimentación i.

Diseño del experimento Generamos 300 sistemas de ecuaciones polinomiales dados por slp de longitud lineal en n, donde n es el número de variables. Cada polinomio del sistema tendrá grado al menos 2. Realizamos pruebas para n ∈ {3, 5, 7, 10} Usamos los 4 algoritmos evolutivos enunciados anteriormente. La función de fitness será α∗ o αc∗ . La condición de parada será: haber encontrado un cero aproximado o haber realizado 100 generaciones.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

37/70

Protocolo de experimentación i.

Diseño del experimento Generamos 300 sistemas de ecuaciones polinomiales dados por slp de longitud lineal en n, donde n es el número de variables. Cada polinomio del sistema tendrá grado al menos 2. Realizamos pruebas para n ∈ {3, 5, 7, 10} Usamos los 4 algoritmos evolutivos enunciados anteriormente. La función de fitness será α∗ o αc∗ . La condición de parada será: haber encontrado un cero aproximado o haber realizado 100 generaciones.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

37/70

Protocolo de experimentación i.

Diseño del experimento Generamos 300 sistemas de ecuaciones polinomiales dados por slp de longitud lineal en n, donde n es el número de variables. Cada polinomio del sistema tendrá grado al menos 2. Realizamos pruebas para n ∈ {3, 5, 7, 10} Usamos los 4 algoritmos evolutivos enunciados anteriormente. La función de fitness será α∗ o αc∗ . La condición de parada será: haber encontrado un cero aproximado o haber realizado 100 generaciones.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

37/70

Protocolo de experimentación i.

Diseño del experimento Generamos 300 sistemas de ecuaciones polinomiales dados por slp de longitud lineal en n, donde n es el número de variables. Cada polinomio del sistema tendrá grado al menos 2. Realizamos pruebas para n ∈ {3, 5, 7, 10} Usamos los 4 algoritmos evolutivos enunciados anteriormente. La función de fitness será α∗ o αc∗ . La condición de parada será: haber encontrado un cero aproximado o haber realizado 100 generaciones.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

37/70

Protocolo de experimentación i.

Diseño del experimento Generamos 300 sistemas de ecuaciones polinomiales dados por slp de longitud lineal en n, donde n es el número de variables. Cada polinomio del sistema tendrá grado al menos 2. Realizamos pruebas para n ∈ {3, 5, 7, 10} Usamos los 4 algoritmos evolutivos enunciados anteriormente. La función de fitness será α∗ o αc∗ . La condición de parada será: haber encontrado un cero aproximado o haber realizado 100 generaciones.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

37/70

Protocolo de experimentación i.

Diseño del experimento Generamos 300 sistemas de ecuaciones polinomiales dados por slp de longitud lineal en n, donde n es el número de variables. Cada polinomio del sistema tendrá grado al menos 2. Realizamos pruebas para n ∈ {3, 5, 7, 10} Usamos los 4 algoritmos evolutivos enunciados anteriormente. La función de fitness será α∗ o αc∗ . La condición de parada será: haber encontrado un cero aproximado o haber realizado 100 generaciones.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

37/70

Algoritmo exhaustivo ii. ¿Porqué es imposible que funcione el algoritmo exhaustivo?

Resumen descriptivo del retículo n D H 3 18,78 987,46 5 328,02 17 247,4 7 6 066,85 3,19 · 105 10 3,21 · 105 1,69 · 107

C.E. Borges

h 4,18 · 10−6 1,07 · 10−7 7,31 · 10−9 2,1 · 10−9

]L 4,13 · 1027 1,85 · 1055 2,33 · 10105 3,55 · 10160

Hacia una solución al problema xvii de Smale en el caso real

38/70

Resultados experimentales i. Resultados fitness α∗ n 3 5 7 10

PSO DE SA GA 77,67 % 60,67 % 59,33 % 60,33 % 67,33 % 13,33 % 15,67 % 13,33 % 63,33 % 1,67 % 0,67 % 2% 39,67 % 1 % 1% 0,67 %

n 3 5 7 10

(a) Porcentaje de acierto

PSO 0,2 0,58 0,98 1,75

DE 0,32 0,65 0,89 1,55

SA 0,32 0,66 0,92 1,66

GA 0,33 0,68 0,96 1,74

(b) Tiempo de ejecución (s)

Resultados fitness αc∗ n PSO 3 88 % 5 94 % 7 94,67 % 10 85,33 %

DE 87,67 % 87,33 % 70,33 % 25,33 %

SA 86,67 % 82,33 % 71,67 % 27,67 %

(c) Porcentaje de acierto C.E. Borges

GA 82,33 % 49,67 % 20,67 % 4,67 %

n 3 5 7 10

PSO 0,9 1,43 3,88 19,93

DE 0,94 3,07 12,59 47,05

SA 0,95 2,78 10,98 45,14

GA 0,98 3,14 13,55 49,86

(d) Tiempo de ejecución (s)

Hacia una solución al problema xvii de Smale en el caso real

39/70

Resultados experimentales i. Resultados fitness α∗ n 3 5 7 10

PSO DE SA GA 77,67 % 60,67 % 59,33 % 60,33 % 67,33 % 13,33 % 15,67 % 13,33 % 63,33 % 1,67 % 0,67 % 2% 39,67 % 1 % 1% 0,67 %

n 3 5 7 10

(e) Porcentaje de acierto

PSO 0,2 0,58 0,98 1,75

DE 0,32 0,65 0,89 1,55

SA 0,32 0,66 0,92 1,66

GA 0,33 0,68 0,96 1,74

(f) Tiempo de ejecución (s)

Resultados fitness αc∗ n PSO 3 88 % 5 94 % 7 94,67 % 10 85,33 %

DE 87,67 % 87,33 % 70,33 % 25,33 %

SA 86,67 % 82,33 % 71,67 % 27,67 %

(g) Porcentaje de acierto C.E. Borges

GA 82,33 % 49,67 % 20,67 % 4,67 %

n 3 5 7 10

PSO 0,9 1,43 3,88 19,93

DE 0,94 3,07 12,59 47,05

SA 0,95 2,78 10,98 45,14

GA 0,98 3,14 13,55 49,86

(h) Tiempo de ejecución (s)

Hacia una solución al problema xvii de Smale en el caso real

39/70

Parte ii: El problema de regresión simbólica

El problema de regresión simbólica

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

40/70

El problema de regresión i. Problema (Regresión simbólica) Dada una muestra de puntos, encontrar la función que mejor los aproxima dentro de un espacio de funciones dado. f (x)

x C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

41/70

El problema de regresión i. Problema (Regresión simbólica) Dada una muestra de puntos, encontrar la función que mejor los aproxima dentro de un espacio de funciones dado. f (x)

f (x)

x C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

41/70

El problema de regresión i. Problema (Regresión simbólica) Dada una muestra de puntos, encontrar la función que mejor los aproxima dentro de un espacio de funciones dado. f (x)

f (x) x10

x1

x x x x x 8 x2 x3 4 5 6 7

x9

x0 C.E. Borges

x Hacia una solución al problema xvii de Smale en el caso real

41/70

El problema de regresión i. Problema (Regresión simbólica) Dada una muestra de puntos, encontrar la función que mejor los aproxima dentro de un espacio de funciones dado. f (x)

g(x)

x C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

41/70

El problema de regresión ii: Cuando el espacio de búsqueda es conocido.

Regresión numérica Interpolación. Mínimos cuadrados. Descenso de gradiente.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

42/70

El problema de regresión ii: Cuando el espacio de búsqueda es conocido.

Regresión numérica Interpolación. Mínimos cuadrados. Descenso de gradiente.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

42/70

El problema de regresión ii: Cuando el espacio de búsqueda es conocido.

Regresión numérica Interpolación. Mínimos cuadrados. Descenso de gradiente.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

42/70

El problema de regresión simbólica i: Cuando el espacio de búsqueda es desconocido.

Regresión en espacios de funciones La fuerza bruta no es una opción. Búsqueda de la expresión simbólica del regresor. Construcción de un programa que evalúe el regresor. ¡Programación genética!

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

43/70

El problema de regresión simbólica i: Cuando el espacio de búsqueda es desconocido.

Regresión en espacios de funciones La fuerza bruta no es una opción. Búsqueda de la expresión simbólica del regresor. Construcción de un programa que evalúe el regresor. ¡Programación genética!

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

43/70

El problema de regresión simbólica i: Cuando el espacio de búsqueda es desconocido.

Regresión en espacios de funciones La fuerza bruta no es una opción. Búsqueda de la expresión simbólica del regresor. Construcción de un programa que evalúe el regresor. ¡Programación genética!

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

43/70

El problema de regresión simbólica i: Cuando el espacio de búsqueda es desconocido.

Regresión en espacios de funciones La fuerza bruta no es una opción. Búsqueda de la expresión simbólica del regresor. Construcción de un programa que evalúe el regresor. ¡Programación genética!

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

43/70

El problema de regresión simbólica i: Cuando el espacio de búsqueda es desconocido.

Regresión en espacios de funciones La fuerza bruta no es una opción. Búsqueda de la expresión simbólica del regresor. Construcción de un programa que evalúe el regresor. ¡Programación genética!

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

43/70

Índice

1

El problema xvii de Smale Desarrollo histórico El programa de Shub y Smale Un algoritmo por búsqueda exhaustiva Problema de optimización

2

El problema de regresión simbólica Programación genética La selección del modelo Coevolución

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

44/70

Programación genética con slp i. Definición (Programación genética) La programación genética consiste en desarrollar programas informáticos mediante la evolución de estructuras de datos sin intervención humana.

Estructuras de datos para codificar programas Koza 1992: árboles. Alonso, Montaña, Puente y Borges 2009: slp.

Ventajas de los slp sobre los árboles Reutilizar operaciones ya realizadas. Permite representaciones más compactas. Menos propensas al código basura al permitir el código no efectivo. C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

45/70

Programación genética con slp i. Definición (Programación genética) La programación genética consiste en desarrollar programas informáticos mediante la evolución de estructuras de datos sin intervención humana.

Estructuras de datos para codificar programas Koza 1992: árboles. Alonso, Montaña, Puente y Borges 2009: slp.

Ventajas de los slp sobre los árboles Reutilizar operaciones ya realizadas. Permite representaciones más compactas. Menos propensas al código basura al permitir el código no efectivo. C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

45/70

Programación genética con slp i. Definición (Programación genética) La programación genética consiste en desarrollar programas informáticos mediante la evolución de estructuras de datos sin intervención humana.

Estructuras de datos para codificar programas Koza 1992: árboles. Alonso, Montaña, Puente y Borges 2009: slp.

Ventajas de los slp sobre los árboles Reutilizar operaciones ya realizadas. Permite representaciones más compactas. Menos propensas al código basura al permitir el código no efectivo. C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

45/70

Programación genética con slp i. Definición (Programación genética) La programación genética consiste en desarrollar programas informáticos mediante la evolución de estructuras de datos sin intervención humana.

Estructuras de datos para codificar programas Koza 1992: árboles. Alonso, Montaña, Puente y Borges 2009: slp.

Ventajas de los slp sobre los árboles Reutilizar operaciones ya realizadas. Permite representaciones más compactas. Menos propensas al código basura al permitir el código no efectivo. C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

45/70

Programación genética con slp i. Definición (Programación genética) La programación genética consiste en desarrollar programas informáticos mediante la evolución de estructuras de datos sin intervención humana.

Estructuras de datos para codificar programas Koza 1992: árboles. Alonso, Montaña, Puente y Borges 2009: slp.

Ventajas de los slp sobre los árboles Reutilizar operaciones ya realizadas. Permite representaciones más compactas. Menos propensas al código basura al permitir el código no efectivo. C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

45/70

Programación genética con slp ii: Operadores genéticos: cruce (representación gráfica).

Figura: Padre 1 Γ1 ≡

Figura: Padre 2 Γ2 ≡

∗

+ ∗

+

+

+ ∗

∗

∗ + y

x

x

y

Figura: Hijo 1

Figura: Hijo 2

Γs1 ≡

Γs2 ≡

∗

+

+ ∗

∗ ∗

∗

+

∗ x

y

+ x

C.E. Borges

y

Hacia una solución al problema xvii de Smale en el caso real

46/70

Protocolo experimentación ii.

Diseño del experimento Generamos dos conjuntos de conceptos: Polinomios de grado acotado. slp0 s.

Generamos 300 muestras que contienen: 30 puntos de aprendizaje (con o sin errores). 200 puntos de validación (sin errores).

Diagramas de cajas y bigotes con el error cuadrático medio sobre los puntos de validación. Resultados de los contrastes de hipótesis cruzados sobre los errores de validación.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

47/70

Protocolo experimentación ii.

Diseño del experimento Generamos dos conjuntos de conceptos: Polinomios de grado acotado. slp0 s.

Generamos 300 muestras que contienen: 30 puntos de aprendizaje (con o sin errores). 200 puntos de validación (sin errores).

Diagramas de cajas y bigotes con el error cuadrático medio sobre los puntos de validación. Resultados de los contrastes de hipótesis cruzados sobre los errores de validación.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

47/70

Protocolo experimentación ii.

Diseño del experimento Generamos dos conjuntos de conceptos: Polinomios de grado acotado. slp0 s.

Generamos 300 muestras que contienen: 30 puntos de aprendizaje (con o sin errores). 200 puntos de validación (sin errores).

Diagramas de cajas y bigotes con el error cuadrático medio sobre los puntos de validación. Resultados de los contrastes de hipótesis cruzados sobre los errores de validación.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

47/70

Protocolo experimentación ii.

Diseño del experimento Generamos dos conjuntos de conceptos: Polinomios de grado acotado. slp0 s.

Generamos 300 muestras que contienen: 30 puntos de aprendizaje (con o sin errores). 200 puntos de validación (sin errores).

Diagramas de cajas y bigotes con el error cuadrático medio sobre los puntos de validación. Resultados de los contrastes de hipótesis cruzados sobre los errores de validación.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

47/70

Protocolo experimentación ii.

Diseño del experimento Generamos dos conjuntos de conceptos: Polinomios de grado acotado. slp0 s.

Generamos 300 muestras que contienen: 30 puntos de aprendizaje (con o sin errores). 200 puntos de validación (sin errores).

Diagramas de cajas y bigotes con el error cuadrático medio sobre los puntos de validación. Resultados de los contrastes de hipótesis cruzados sobre los errores de validación.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

47/70

Protocolo experimentación ii.

Diseño del experimento Generamos dos conjuntos de conceptos: Polinomios de grado acotado. slp0 s.

Generamos 300 muestras que contienen: 30 puntos de aprendizaje (con o sin errores). 200 puntos de validación (sin errores).

Diagramas de cajas y bigotes con el error cuadrático medio sobre los puntos de validación. Resultados de los contrastes de hipótesis cruzados sobre los errores de validación.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

47/70

Protocolo experimentación ii.

Diseño del experimento Generamos dos conjuntos de conceptos: Polinomios de grado acotado. slp0 s.

Generamos 300 muestras que contienen: 30 puntos de aprendizaje (con o sin errores). 200 puntos de validación (sin errores).

Diagramas de cajas y bigotes con el error cuadrático medio sobre los puntos de validación. Resultados de los contrastes de hipótesis cruzados sobre los errores de validación.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

47/70

Protocolo experimentación ii.

Diseño del experimento Generamos dos conjuntos de conceptos: Polinomios de grado acotado. slp0 s.

Generamos 300 muestras que contienen: 30 puntos de aprendizaje (con o sin errores). 200 puntos de validación (sin errores).

Diagramas de cajas y bigotes con el error cuadrático medio sobre los puntos de validación. Resultados de los contrastes de hipótesis cruzados sobre los errores de validación.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

47/70

Resultados experimentales ii.

Comparativa cruces slp0 s 1 punto. 2 puntos. Uniforme. slp.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

48/70

Resultados experimentales ii. Comparativa cruces para slp0 s i.

Diagramas de cajas y bigotes: cruces para slp SLPl(F, T )

0.0

0.00

0.1

0.04

0.2

0.3

0.08

0.4

0.12

0.5

PR n [X]

1 Punto

C.E. Borges

2 Puntos

Uniforme

slp

1 Punto

2 Puntos

Uniforme

Hacia una solución al problema xvii de Smale en el caso real

slp

49/70

Resultados experimentales ii. Comparativa cruces para slp0 s ii.

Contrastes de hipótesis: cruces para slp PR n [X ]

1 Punto 2 Puntos Uniforme 1 Punto 1 0,85 1 2 Puntos 0,43 1 1 Uniforme 4,23 · 10−2 0,11 1 −9 −8 slp 2,26 · 10 1,07 · 10 2,15 · 10−5 SLPl (F, T ) 1 Punto 2 Puntos Uniforme 1 Punto 1 0,91 1 2 Puntos 0,12 1 1 Uniforme 2,19 · 10−2 7,14 · 10−2 1 −6 −5 slp 3,81 · 10 7,99 · 10 1,34 · 10−2

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

slp 1 1 1 1 slp 1 1 1 1

50/70

Resultados Experimentales iii.

Comparativa estructuras de datos slp0 s. Árboles.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

51/70

Resultados experimentales iii. Comparativa estructura de datos.

Diagramas de cajas y bigotes: estructuras de datos SLPl(F, T )

0.00

0.00

0.02

0.05

0.04

0.10

0.06

0.15

0.08

0.20

0.10

PR n [X]

slp

C.E. Borges

arbol

slp

Hacia una solución al problema xvii de Smale en el caso real

arbol

52/70

Resultados experimentales iii. Comparativa estructura de datos.

Contrastes de hipótesis: estructuras de datos PR n [X ] slp arbol

C.E. Borges

slp 1 0,79

arbol 8,07 · 10−2 1

SLPl (F, T ) slp arbol

slp 1 1

arbol 7,16 · 10−3 1

Hacia una solución al problema xvii de Smale en el caso real

53/70

Índice

1

El problema xvii de Smale Desarrollo histórico El programa de Shub y Smale Un algoritmo por búsqueda exhaustiva Problema de optimización

2

El problema de regresión simbólica Programación genética La selección del modelo Coevolución

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

54/70

Selección del modelo: La dimensión Vapnik–Chervonenkis.

Navaja de Ockham (Ockham 1495) La pluralidad no se debe postular sin necesidad.

Idea Asignar el fitness de los modelos de acuerdo a su error empírico más una penalización en función de su complejidad.

Capacidad de clasificación Cantidad de puntos que el modelo puede clasificar sin error.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

55/70

Selección del modelo: La dimensión Vapnik–Chervonenkis.

Navaja de Ockham (Ockham 1495) La pluralidad no se debe postular sin necesidad.

Idea Asignar el fitness de los modelos de acuerdo a su error empírico más una penalización en función de su complejidad.

Capacidad de clasificación Cantidad de puntos que el modelo puede clasificar sin error.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

55/70

Selección del modelo: La dimensión Vapnik–Chervonenkis.

Navaja de Ockham (Ockham 1495) La pluralidad no se debe postular sin necesidad.

Idea Asignar el fitness de los modelos de acuerdo a su error empírico más una penalización en función de su complejidad.

Capacidad de clasificación Cantidad de puntos que el modelo puede clasificar sin error.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

55/70

Selección del modelo: La dimensión Vapnik–Chervonenkis.

Navaja de Ockham (Ockham 1495) La pluralidad no se debe postular sin necesidad.

Idea Asignar el fitness de los modelos de acuerdo a su error empírico más una penalización en función de su complejidad.

Capacidad de clasificación Cantidad de puntos que el modelo puede clasificar sin error.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

55/70

Selección del modelo: La dimensión Vapnik–Chervonenkis.

Navaja de Ockham (Ockham 1495) La pluralidad no se debe postular sin necesidad.

Idea Asignar el fitness de los modelos de acuerdo a su error empírico más una penalización en función de su complejidad.

Capacidad de clasificación Cantidad de puntos que el modelo puede clasificar sin error.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

55/70

Selección del modelo: La dimensión Vapnik–Chervonenkis.

Navaja de Ockham (Ockham 1495) La pluralidad no se debe postular sin necesidad.

Idea Asignar el fitness de los modelos de acuerdo a su error empírico más una penalización en función de su complejidad.

Capacidad de clasificación Cantidad de puntos que el modelo puede clasificar sin error.

Teorema (Montaña, Alonso, Borges y Crespo 2009) La dimensión de Vapnik–Chervonenkis de un modelo construido mediante slp0 s es polinomial en el número de operaciones no escalares que posea. C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

55/70

Resultados experimentales iv.

Comparativa fitness muestras con ruido Error cuadrático medio. Criterio de información de Akaike. Criterio de información bayesiano. Minimización del riesgo estructural.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

56/70

Resultados experimentales iv. Comparativa muestras con ruido i.

Diagramas de cajas y bigotes: fitness de muestras con ruido SLPl(F, T )

0.0

0.0

0.1

0.5

0.2

0.3

1.0

0.4

1.5

0.5

PR n [X]

MSE

C.E. Borges

AIC

BIC

SRM

MSE

AIC

Hacia una solución al problema xvii de Smale en el caso real

BIC

SRM

57/70

Resultados experimentales iv. Comparativa muestras con ruido ii.

Contrastes de hipótesis: fitness de muestras con ruido PR MSE AIC BIC SRM n [X ] MSE 1 0,94 0,93 1 −3 AIC 8,81 · 10 1 0,73 0,8 BIC 5,82 · 10−3 0,91 1 0,94 SRM 3,44 · 10−3 7,02 · 10−2 7,16 · 10−2 1 SLPl (F, T ) MSE AIC BIC SRM −5 −5 MSE 1 4,67 · 10 1,67 · 10 0,81 −2 AIC 1,51 · 10 1 0,11 0,77 BIC 5 · 10−3 0,75 1 0,63 −3 −4 −5 SRM 8,72 · 10 2,53 · 10 2,19 · 10 1

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

58/70

Índice

1

El problema xvii de Smale Desarrollo histórico El programa de Shub y Smale Un algoritmo por búsqueda exhaustiva Problema de optimización

2

El problema de regresión simbólica Programación genética La selección del modelo Coevolución

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

59/70

Ajuste de constantes: Coevolución

Coevolución slp0 s

con constantes paramétricas. Ajustar los valores de dichos parámetros para minimizar el error: Algoritmo evolutivo de co-evolución cooperativa heterogénea. Descenso de gradiente.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

60/70

Ajuste de constantes: Coevolución

Coevolución slp0 s

con constantes paramétricas. Ajustar los valores de dichos parámetros para minimizar el error: Algoritmo evolutivo de co-evolución cooperativa heterogénea. Descenso de gradiente.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

60/70

Ajuste de constantes: Coevolución

Coevolución slp0 s

con constantes paramétricas. Ajustar los valores de dichos parámetros para minimizar el error: Algoritmo evolutivo de co-evolución cooperativa heterogénea. Descenso de gradiente.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

60/70

Ajuste de constantes: Coevolución

Coevolución slp0 s

con constantes paramétricas. Ajustar los valores de dichos parámetros para minimizar el error: Algoritmo evolutivo de co-evolución cooperativa heterogénea. Descenso de gradiente.

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

60/70

Resultados experimentales v.

Fitness de las constantes Mejor fitness de la población (normal). Fitness del mejor individuo de la población (élite). Mínimo entre el fitness del mejor individuo de la población y otros escogidos al azar (mínimo). Media entre el fitness del mejor individuo de la población y otros escogidos al azar (media).

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

61/70

Resultados experimentales v. Comparativa estructura de datos: fitness de constantes i.

Diagramas de cajas y bigotes: fitness de constantes SLPl(F, T )

0.00

0.00

0.02

0.05

0.04

0.10

0.06

0.15

0.08

0.20

0.10

PR n [X]

normal

C.E. Borges

elite

minimo

media

normal

elite

minimo

Hacia una solución al problema xvii de Smale en el caso real

media

62/70

Resultados experimentales v. Comparativa estructura de datos: fitness de constantes ii.

Contrastes de hipótesis: fitness de constantes PR normal n [X ] normal 1 élite 0,97 mínimo 0,97 media 0,99 SLPl (F, T ) normal normal 1 élite 0,86 mínimo 0,93 media 0,75

C.E. Borges

élite mínimo media −3 0,2 8,72 · 10 0,14 −2 1 8,49 · 10 0,49 0,97 1 0,87 0,94 0,31 1 élite mínimo media 0,63 0,3 7,54 · 10−2 1 0,52 0,17 0,85 1 0,27 0,95 0,78 1

Hacia una solución al problema xvii de Smale en el caso real

63/70

Resultados experimentales vi.

Estrategias coevolutivas Separados: bloque fijo de generaciones dedicado a programación genética seguido del resto de generaciones dedicadas a la evolución de constantes (S). Turnos: alternación de turnos de generaciones dedicados a la programación genética con generaciones dedicadas a la evolución de constantes (G E).

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

64/70

Resultados experimentales vi. Comparativa estrategias de coevolución i.

Diagramas de cajas y bigotes: estrategias de coevolución SLPl(F, T )

0.00

0.00

0.02

0.05

0.04

0.10

0.06

0.15

0.08

0.20

0.10

PR n [X]

S−90

C.E. Borges

S−75

G20−E5

G30−E2

GP

S−90

S−75

G20−E5

Hacia una solución al problema xvii de Smale en el caso real

G30−E2

GP

65/70

Resultados experimentales vi. Comparativa estrategias de co-evolución ii.

Contrastes de hipótesis: estrategias de coevolución PR n [X ]

S-90 S-75 G20-E5 G30-E2 GP S-90 1 0,13 0,89 0,83 0,11 S-75 0,68 1 0,87 0,98 0,3 G20-E5 0,48 4,88 · 10−2 1 0,4 1,86 · 10−2 G30-E2 0,5 0,16 0,65 1 2,58 · 10−2 GP 0,96 0,91 1 1 1 SLPl (F, T ) S-90 S-75 G20-E5 G30-E2 GP S-90 1 0,1 0,15 0,24 0,13 S-75 1 1 0,73 0,94 0,65 G20-E5 1 0,59 1 0,78 0,55 G30-E2 0,89 0,45 0,51 1 0,4 GP 1 0,82 0,75 0,98 1 C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

66/70

Conclusiones y trabajos futuros

Conclusiones y trabajos futuros

C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

67/70

Conclusiones. Problema xvii de Smale Algoritmo exhaustivo de complejidad exponencial. Test en BPP para la propiedad ser cero aproximado. Diversos algoritmos evolutivos con buen comportamiento empírico.

Problema de regresión simbólica Uso de la estructura de datos slp para la codificación de conceptos. Importancia de los bloques semánticos en los operadores genéticos. Cálculo de la dimensión VC del conjunto de slp0 s. Diversos estrategias algorítmicas co-evolutivas. C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

68/70

Conclusiones. Problema xvii de Smale Algoritmo exhaustivo de complejidad exponencial. Test en BPP para la propiedad ser cero aproximado. Diversos algoritmos evolutivos con buen comportamiento empírico.

Problema de regresión simbólica Uso de la estructura de datos slp para la codificación de conceptos. Importancia de los bloques semánticos en los operadores genéticos. Cálculo de la dimensión VC del conjunto de slp0 s. Diversos estrategias algorítmicas co-evolutivas. C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

68/70

Conclusiones. Problema xvii de Smale Algoritmo exhaustivo de complejidad exponencial. Test en BPP para la propiedad ser cero aproximado. Diversos algoritmos evolutivos con buen comportamiento empírico.

Problema de regresión simbólica Uso de la estructura de datos slp para la codificación de conceptos. Importancia de los bloques semánticos en los operadores genéticos. Cálculo de la dimensión VC del conjunto de slp0 s. Diversos estrategias algorítmicas co-evolutivas. C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

68/70

Conclusiones. Problema xvii de Smale Algoritmo exhaustivo de complejidad exponencial. Test en BPP para la propiedad ser cero aproximado. Diversos algoritmos evolutivos con buen comportamiento empírico.

Problema de regresión simbólica Uso de la estructura de datos slp para la codificación de conceptos. Importancia de los bloques semánticos en los operadores genéticos. Cálculo de la dimensión VC del conjunto de slp0 s. Diversos estrategias algorítmicas co-evolutivas. C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

68/70

Conclusiones. Problema xvii de Smale Algoritmo exhaustivo de complejidad exponencial. Test en BPP para la propiedad ser cero aproximado. Diversos algoritmos evolutivos con buen comportamiento empírico.

Problema de regresión simbólica Uso de la estructura de datos slp para la codificación de conceptos. Importancia de los bloques semánticos en los operadores genéticos. Cálculo de la dimensión VC del conjunto de slp0 s. Diversos estrategias algorítmicas co-evolutivas. C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

68/70

Conclusiones. Problema xvii de Smale Algoritmo exhaustivo de complejidad exponencial. Test en BPP para la propiedad ser cero aproximado. Diversos algoritmos evolutivos con buen comportamiento empírico.

Problema de regresión simbólica Uso de la estructura de datos slp para la codificación de conceptos. Importancia de los bloques semánticos en los operadores genéticos. Cálculo de la dimensión VC del conjunto de slp0 s. Diversos estrategias algorítmicas co-evolutivas. C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

68/70

Conclusiones. Problema xvii de Smale Algoritmo exhaustivo de complejidad exponencial. Test en BPP para la propiedad ser cero aproximado. Diversos algoritmos evolutivos con buen comportamiento empírico.

Problema de regresión simbólica Uso de la estructura de datos slp para la codificación de conceptos. Importancia de los bloques semánticos en los operadores genéticos. Cálculo de la dimensión VC del conjunto de slp0 s. Diversos estrategias algorítmicas co-evolutivas. C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

68/70

Conclusiones. Problema xvii de Smale Algoritmo exhaustivo de complejidad exponencial. Test en BPP para la propiedad ser cero aproximado. Diversos algoritmos evolutivos con buen comportamiento empírico.

Problema de regresión simbólica Uso de la estructura de datos slp para la codificación de conceptos. Importancia de los bloques semánticos en los operadores genéticos. Cálculo de la dimensión VC del conjunto de slp0 s. Diversos estrategias algorítmicas co-evolutivas. C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

68/70

Trabajos futuros. Problema xvii de Smale Estudiar homotopías con puntos iniciales complejos y puntos finales reales. Tratar de fundamentar teóricamente el comportamiento observado en los algoritmos evolutivos presentados.

Problema de regresión simbólica Aplicar otros algoritmos evolutivos y/o formas de codificar los slp. Probar otras estrategias co-evolutivas. Tratar problemas a escala real: Modelado automático de sistemas complejos en ingeniería de procesos. Búsqueda de curvas de carga de edificios. C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

69/70

Trabajos futuros. Problema xvii de Smale Estudiar homotopías con puntos iniciales complejos y puntos finales reales. Tratar de fundamentar teóricamente el comportamiento observado en los algoritmos evolutivos presentados.

Problema de regresión simbólica Aplicar otros algoritmos evolutivos y/o formas de codificar los slp. Probar otras estrategias co-evolutivas. Tratar problemas a escala real: Modelado automático de sistemas complejos en ingeniería de procesos. Búsqueda de curvas de carga de edificios. C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

69/70

Trabajos futuros. Problema xvii de Smale Estudiar homotopías con puntos iniciales complejos y puntos finales reales. Tratar de fundamentar teóricamente el comportamiento observado en los algoritmos evolutivos presentados.

Problema de regresión simbólica Aplicar otros algoritmos evolutivos y/o formas de codificar los slp. Probar otras estrategias co-evolutivas. Tratar problemas a escala real: Modelado automático de sistemas complejos en ingeniería de procesos. Búsqueda de curvas de carga de edificios. C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

69/70

Trabajos futuros. Problema xvii de Smale Estudiar homotopías con puntos iniciales complejos y puntos finales reales. Tratar de fundamentar teóricamente el comportamiento observado en los algoritmos evolutivos presentados.

Problema de regresión simbólica Aplicar otros algoritmos evolutivos y/o formas de codificar los slp. Probar otras estrategias co-evolutivas. Tratar problemas a escala real: Modelado automático de sistemas complejos en ingeniería de procesos. Búsqueda de curvas de carga de edificios. C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

69/70

Trabajos futuros. Problema xvii de Smale Estudiar homotopías con puntos iniciales complejos y puntos finales reales. Tratar de fundamentar teóricamente el comportamiento observado en los algoritmos evolutivos presentados.

Problema de regresión simbólica Aplicar otros algoritmos evolutivos y/o formas de codificar los slp. Probar otras estrategias co-evolutivas. Tratar problemas a escala real: Modelado automático de sistemas complejos en ingeniería de procesos. Búsqueda de curvas de carga de edificios. C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

69/70

Trabajos futuros. Problema xvii de Smale Estudiar homotopías con puntos iniciales complejos y puntos finales reales. Tratar de fundamentar teóricamente el comportamiento observado en los algoritmos evolutivos presentados.

Problema de regresión simbólica Aplicar otros algoritmos evolutivos y/o formas de codificar los slp. Probar otras estrategias co-evolutivas. Tratar problemas a escala real: Modelado automático de sistemas complejos en ingeniería de procesos. Búsqueda de curvas de carga de edificios. C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

69/70

Trabajos futuros. Problema xvii de Smale Estudiar homotopías con puntos iniciales complejos y puntos finales reales. Tratar de fundamentar teóricamente el comportamiento observado en los algoritmos evolutivos presentados.

Problema de regresión simbólica Aplicar otros algoritmos evolutivos y/o formas de codificar los slp. Probar otras estrategias co-evolutivas. Tratar problemas a escala real: Modelado automático de sistemas complejos en ingeniería de procesos. Búsqueda de curvas de carga de edificios. C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

69/70

Trabajos futuros. Problema xvii de Smale Estudiar homotopías con puntos iniciales complejos y puntos finales reales. Tratar de fundamentar teóricamente el comportamiento observado en los algoritmos evolutivos presentados.

Problema de regresión simbólica Aplicar otros algoritmos evolutivos y/o formas de codificar los slp. Probar otras estrategias co-evolutivas. Tratar problemas a escala real: Modelado automático de sistemas complejos en ingeniería de procesos. Búsqueda de curvas de carga de edificios. C.E. Borges

Hacia una solución al problema xvii de Smale en el caso real

69/70

Programación Genética, Algoritmos Evolutivos y Aprendizaje Inductivo: Hacia una solución al problema xvii de Smale en el caso real

Cruz Enrique Borges Hernández Departamento de Matemáticas, Estadística y Computación. Universidad de Cantabria 25 de marzo de 2011

This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.