Programación genética, algoritmos evolutivos y aprendizaje inductivohacia una solución al problema xvii de Smale en el caso real

Resum

El principal objetivo de esta memoria es la resolución del sistemas de ecuaciones polinomiales con coeficientes reales (problema XVII de Smale, caso real). Primero se plantea el desarrollo de un algoritmo de deformación homotópica siguiendo el programa iniciado por Shub y Smale y continuado por Beltrán y Pardo. Para ello se calcula la distribución de probabilidad del número de condicionamiento no lineal de los sistemas de ecuaciones polinomiales con coeficientes reales. A continuación se estudia el número de componentes conexas del espacio de sistemas de ecuaciones polinomiales sin raíces singulares donde se demuestra que un algoritmo de deformación homotópica siguiendo el programa anteriormente nombrado es imposible. Para resolver este problema se plantea utilizar distintos tipos de algoritmos evolutivos explotando la noción de cero aproximado. Los resultados de usar dichos algoritmos son muy satisfactorios en un gran número de ejemplos. Durante el estudio de dichos algoritmos (en particular la programación genética para la resolución del problema de regresión simbólica) se realizan diversas contribuciones originales. Para empezar, se introduce una estructura de datos straight-line programs, usada en el contexto del álgebra computacional, con el objetivo de codificar las aplicaciones. Esta nueva estructura de datos demuestra ser muy superior a la tradicionalmente usada en el problema de regresión simbólica. Posteriormente analizamos el problema de seleccionar el mejor modelo usando straight-line programs como codificación de éstos. Para ello se calcula la dimensión de Vapnik-Chervonenkis del conjunto de straight-line programs. Los resultados de usar dicha estrategia como selección de modelos en el problema de regresión simbólica demuestran que es más efectiva que el uso de otras estrategias de tipo estadístico. Finalmente se analizan diversas estrategias coevolutivas con resultados prometedores aunque no concluyentes.