Evolutionary computation of optimal knot allocation in smoothing methods by multivariate splines and radial function basis spaces

Resumen

El objetivo de esta tesis doctoral ha sido el estudio, desarrollo y adaptación de una adecuada técnica de optimización multi-objetivo de tipo evolutivo (MOGA del inglés "Multi-Objective Genetic Algorithm") para el emplazamiento óptimo de los nodos (en el caso de bases de B-splines cúbicos o bicúbicos) o centros (cuando usamos funciones de base radiales) en sendos problemas de aproximación o de interpolación. Está estructurada en cuatro capítulos, redactados en inglés, aparte un resumen preliminar de la misma en castellano. Capítulo 1 Se trata de una presesentación de la tesis y una pequeña introducción a los conceptos fundamentales para seguir el resto del trabajo de investigación realizado, presentando las principales definiciones y conceptos preliminares necesarios para las técnicas de interpolación o aproximación empleadas, haciendo uso de B-splines, o bien funciones radiales, junto con un breve repaso de ciertas cuestiones teóricas generales requeridas en nuestra investigación. También se presentan de una manera somera y muy simplificada los denominados algoritmos genéticos de ordenación no-dominada (NSGA, del inglés "Non-dominated Sorting Genetic Algorithms") que se engloban en los archiconocidos algoritmos genéticos (GA en inglés) cuyo objetivo consiste en todo caso en la adaptación evolutiva, a lo largo de sucesivas generaciones que se van sucediendo de "padres" a "hijos" en un posible conjunto de soluciones o "población", a través de ciertos "genes y/o mutaciones genéticas" que favorecen una mejor valoración de cara a cierta funciones objetivo que se necesita optimizar. El problema surge cuando en muchas ocasiones estas funciones objetivo no pueden optimizarse todas a la vez sin entrar en conflicto, de manera que algunas de ellas resultan antagónicas, ya sea totalmente o en parte, de manera que hay que buscar entre un amplio conjunto de posibles "buenas" soluciones, aquella o aquellas que de alguna manera resultan más favorables en su conjunto. Surge aquí­ el conocido concepto del "frente (o frentes en el caso más general) de Pareto", que son la frontera geométrica de cierto conjunto de soluciones factibles, que de alguna manera optimizan alguna de las componentes de la función objetivo, aunque no todas a la vez. Por otro lado, como en todo algoritmo genético, también habrá que tener en cuenta ciertos "operadores de selección", "de mutación" y "de recombinación" que se usarán para ir generando las sucesivas generaciones de individuos que conformarán las poblaciones de posibles soluciones a estimar en cada momento; y, que si todo va bien, irán llevándonos a alguno de los valores óptimos de nuestro problema. Precisamente, con el objetivo de evitar caer en alguno de los posibles óptimos locales de ciertos problemas de este tipo, la denominada "fracción de Pareto" permitirá preservar en nuestra población ciertos individuos que, aunque en un principio pudieran parecer dar lugar a una evaluación peor de la función objetivo, sí­ que promueven cierta diversidad en esta población, que a la larga redundará en una mayor capacidad para salir de estos óptimos locales, con vistas a conseguir aproximar mejor el buscado óptimo global (ya sea máximo o mí­nimo). Toda esta implementación se ha llevado a cabo en MATLAB para la optimización de la localización de los nodos para los splines de suavizado de tipo cúbico (en el caso de una variable) y bicúbico (para dos variables independientes), así como para el problema de interpolación con splines naturales en una o dos variables, así como para funciones de base radial en el último capítulo. Capítulo 2 En este capítulo empezamos ya planteando y estudiando el interesante problema de la posible distribución óptima a la hora de colocar los nodos usados en la construcción de B-splines de suavizado para la aproximación de ciertos datos, tanto de una (para datos 2D) como de dos variables (para datos 3D), mediante la aplicación de un algori­tmo de tipo NSGA-II (Non Dominated Sorting Genetic Algorithm, 2nd. version) adaptado especí­ficamente para este propósito. De hecho, la aproximación de funciones, así­ como el ajuste de datos mediante curvas o superficies, es uno de los problemas fundamentales de la Matemática Aplicada y el Cálculo Científico en general, con aplicaciones en numerosí­simas ramas de la Ciencia y la Técnica: como el diseño asistido por ordenador (CAD, del inglés "Computed Aided Design"), la realidad virtual y la animación por computadora, la visión artificial y la visualización automatizada de todo tipo de imágnes médicas, geológicas, etc. Lo que proponemos en esta tesis es una metodologí­a adaptada para el emplazamiento óptimo de nodos, que en principio se pueden mover aleatoriamente en un cierto rango o intervalo de cada una de las variables involucradas, y que permite aproximar o ajustar curvas o superficies a los datos 2D/3D, usando splines de suavizado de una o dos variables independientes. Esta nueva técnica está basada fundamentalmente en el desarrollo y adaptación a este tipo de problemas de un algoritmo genético multi-objetivo con ordenamiento no-dominado, de tipo NSGA-II Revisando los ejemplos y experimentos realizados podemos comprobar de hecho que este planteamiento proporciona resultados bastante precisos, incluso para curvas o superficies con discontinuidades o picos pronunciados, determinando también de manera casi automática, tanto el número de nodos necesarios como su emplazamiento óptimo para un adecuado ajuste de curvas en el caso de B-splines cúbicos, o bicúbicos (en el caso de superficies). Las conclusiones finales son presentadas al final del capítulo, conluyendo en todo caso el buen comportamiento de la estrategia MOGA aplicada a este problema, ayudándose en todo caso del análisis del frente de Pareto para una elección adecuada también del número de nodos a emplear; aunque como regla general, el incremento de este número de nodos suele incrementar la precisión de la aproximación obtenida, pero sólo hasta cierto punto, si tuviéramos también en cuenta el esfuerzo computacional añadido. Lo que sí­ que se concluye de manera contundente es que nuestra estrategia proporciona resultados mucho mejores que otros métodos más clásicos existentes en la literatura científica relacionada, y basados en la mera selección combinatoria de nodos a partir de una distribución uniforme inicial. Capí­tulo 3 Se trata ahora de la posible obtención de la distribución óptima de nodos, tanto de una (para datos 2D) como de dos variables (para datos 3D), pero esta vez para un problema de tipo interpolatorio, mediante splines cúbicos o bi-cúbicos naturales (con condiciones de derivadas segundas nulas en la frontera de un dominio rectangular). Este caso concreto de interpolación puede resultar de especial interés, o incluso ser la clave de muchas tecnologías o procedimientos de ingenierí­a inversa, tratamiento de señales, el análisis sistemático de datos o funciones, o incluso la simple representación, almacenaje o compresión de los mismos. Y lo mismo que ocurría en el problema de la aproximación, aquí­ también varios autores han planteado diferentes métodos y estrategias para la interpolación de ciertos datos bidimensionales o tridimensionales, y todos ellos manifiestan la importancia y el efecto determinante del emplazamiento de los nodos en la precisión y efectividad del procedimiento empleado para la obtención de los resultados finales, tanto en el caso del problema de aproximación como en el de interpolación. En esta tesis, nosotros lo que hemos desarrollado y adaptado para el problema de emplazamiento óptimo de nodos, para la interpolación de un conjunto de datos usando splines cúbicos o bicúbicos, ha sido una metodología NSGA-II bi-objetivo, empleando como funciones objetivo varias versiones discretas de ciertas normas habituales en este tipo de cuestiones. Pero tenemos que resaltar que, aunque ciertos procedimientos evolutivos usando algoritmos genéticos habían sido ya propuestos en la literatura científica sobre emplazamiento óptimo de nodos para el ajuste y aproximación de problemas de una variable independiente, no hemos encontrado referencias equivalentes para el caso interpolatorio, ni tampoco para el caso de funciones de dos variables. De hecho, muchos de los algoritmos genéticos(GAs) encontrados en la literatura especializada se aplicaban fundamentalmente a ciertos planteamientos combinatorios para la selección de nodos entre una cierta partición uniforme del intervalo de partida, mientras que nosotros estamos empleando un algoritmo MOGA de tipo NSGA-II mucho más sofisticado, con una representación mediante números reales de los correspondientes cromosomas, de manera que estos nodos o puntos de interpolación se pueden mover con total libertad a lo largo del intervalo o intervalos considerados en cada una de las variables, o incluso en algunos casos pueden llegar a colisionar y desaparecer, una vez que varios de esos nodos se acerquen entre sí­ por debajo de cierta distancia umbral. Así­ pues, esta sería una de las peculiaridades y versatilidad de nuestro planteamiento, junto con la habilidad de tratar tanto con splines de una o dos variables, para interpolar (o aproximar según sea el caso) datos 2D o 3D. Capí­tulo 4 En un capí­tulo final, se estudia también de forma preliminar el interesante uso de funciones de base radial (abreviadamente RBFs, de su denominación en inglés: Radial Basis Functions), empezando por una de las familias de funciones de este tipo más conocidas y simples de implementar, como son las RBFs de tipo Gaussiano. En este caso se presenta un amplio y versátil abanico de nuevas posibilidades para la colocación óptima de los centros que se usarán para la construcción de la base de funciones radiales correspondiente, construida a partir de una cierta función generadora concreta. Así pues, según sea dicha función generadora empleada, que además puede depender de uno o varios parámetros adicionales, también podríamos ampliar mucho más el espectro de posibilidades para la obtención óptima de los nodos o centros de las funciones de base a elegir de cara al problema de aproximación a resolver, pudiéndose además tratar en este caso de una manera unificada el caso multi-dimensional, sea cual sea la dimensión (aunque de momento los experimentos numéricos presentados sólo se restringen al caso uni-dimensional). No obstante, tratándose esta última parte de un trabajo meramente preliminar, todaví­a no se ha explorado exhaustivamente todas las nuevas posibilidades de esta formulación, y quedarí­a pendiente para una posterior continuación del trabajo de investigación realizado, su aplicación a problemas multi-dimensionales, usando también funciones radiales de soporte compacto (CS-RBFs), e incluyendo además alguno de los parámetros de los que dependen las correspondientes funciones generadoras en el correspondiente proceso de optimización multi-objetivo que tratamos con los algoritmos genéticos de tipo NSGA-II y -III empleados.