En la historia de la computación hemos encontrado información relevante que enmarca y sitúa este tipo de concepto, creo que es muy enriquecedor dar una visión amplia de lo que es una técnica de computación avanzada y muy utilizada en nuestros días.
Remontándonos muy atrás, podríamos decir que todo empieza con Charles R. Darwin y su teoría de la evolución; en su obra “El origen de las especies” publicada en 1859 basa la teoría de la evolución en el proceso de selección natural. Básicamente la teoría de la evolución biológica viene a decir que las especies cambian con el tiempo y van evolucionando para adaptarse al entorno que las rodea. Es una adaptación evolutiva basada en 3 principios fundamentales: Número de individuos limitado, la naturaleza evoluciona individuos de iguales propiedades y los individuos más fuertes suelen prevalecer. La deficiencia de la teoría de Darwin es que no explicaba las razones intrínsecas de esta evolución. Años más tarde un monje Checoslovaco daría la clave que le faltaba a la teoría evolutiva, la transmisión cromosómica.
Gregor Mendel fue el padre de las leyes de la genética moderna y en 1886 publicó su artículo “Estudios sobre la hibridación de plantas”, dónde tras más de 28.000 ensayos con plantas de guisantes formuló tres leyes para demostrar las normas que regían la transferencia genética de “padres” a “hijos” y teorizó sobre la existencia de genes dominantes y recesivos. En la transmisión genética radicaba la clave de la selección y evolución natural que Darwin había descrito años antes.
Con el conocimiento de la teoría de la evolución y las normas sobre la transferencia evolutiva, en 1970 John Holland definió una estrategia de cálculo de búsqueda de soluciones óptimas basadas en las mismas normas en las que se basaba la selección natural. Con esta estrategia se desarrolló la técnica de cálculo evolutiva denominada como “Algoritmos genéticos”, donde una población inicial irá evolucionando con cálculos y variaciones que surgirán de cruces de los más aptos y mutaciones aleatorias. Todo esto, orientado para la búsqueda de una solución que cumpla con el óptimo de un problema o con una solución dada por “aceptable”.
Los pasos básicos para la aplicación y cálculo mediante un algoritmo genético son los siguientes: Se parte de una población inicial de soluciones al problema, se seleccionan los mejores “individuos” (cálculos intermedios de mayor calidad), se recombinan para mejorar las posibles soluciones, a continuación, se introducen “las mutaciones aleatorias” (reconfiguración numérica para mejorar o empeorar el resultado de manera más rápida) y los resultados se transmitirán a la siguiente generación. Estos pasos se repetirán hasta un número de iteraciones fijado o hasta que no haya un valor óptimo calculado mejor durante un número concreto de repeticiones y evoluciones.
La metodología de cálculo de los algoritmos genéticos utiliza lo que se denomina conceptualmente como los “operadores genéticos”: Selección, reproducción, cruce y mutación.
El concepto de selección es la generación aleatoria de una población inicial que puede representar una muestra aceptable de las posibles soluciones al problema de optimización buscado. Se intentará que la población inicial tenga una suficiente de diversidad. Se aplicará una primera “evaluación”, que dará los primeros valores o resultados de aptitud para saber la “bondad” inicial de los resultados que pueden evolucionar hasta encontrar el óptimo buscado.
Una vez elegidos estos elementos mejor posicionados en aptitud se aplicará el operador “reproducción” donde estos elementos se combinan imitando la descendencia directa y transmitiendo el valor a la siguiente generación. Es similar a la clonación de un individuo o a la transmisión cromosómica de padres a hijos.
La fase de cruce es donde se combinan o mezclan los individuos seleccionados en la fase anterior; la etapa de cruce combina valores de diferentes padres de una manera que puedan dar lugar a unos hijos mejorados cualitativamente. Existen varias metodologías de cálculo para el cruce y se basan fundamentalmente en cómo realizar los cálculos de combinación de los “cromosomas” (unidades de las posibles soluciones).
Llegados a este punto se introduce una modificación aleatoria en el “cromosoma”, que es lo que se conoce como “mutación”, para intentar alcanzar posibles soluciones del espectro de posibilidades que podrían no estar cubiertas en la selección de la población actual.
Cuando hemos cumplido con las fases de los operadores genéticos se seleccionan los mejores “individuos” (“soluciones del problema de optimización”) y se plantea la selección de la población de la siguiente generación.
Estos pasos se repetirán hasta que los criterios de convergencia o paro definidos por el usuario se cumplan.
Esta técnica es una de las herramientas de cálculo que se identifican dentro del “espectro” de las herramientas de la “inteligencia artificial”. Como innumerables ejemplos más que nos rodean, a veces las mejores metodologías para resolver problemas complejos se basan en “imitar” a la madre naturaleza así que quizás debiéramos estar más atentos a los pequeños detalles de todo lo que está a nuestro alrededor.
A continuación, observaremos una resolución de problemas utilizando algoritmos genéticos de la revista de la Revista de Matemáticas de la Universidad de Costa Rica:
El problema de estimación de parámetros para sistemas definidos por ecuaciones diferenciales ordinarias o problema inverso descrito por sistemas de ecuaciones diferenciales ordinarias, es ya un problema clásico y ha sido considerado por varios autores sobre todo en los últimos tiempos. Diferentes métodos y puntos de vista han sido propuestos, incluso considerando problemas con estructuras especiales y estrategias y conceptos estadísticos ([1]), ([11]) y ([15]). También han sido diseñados nuevos esquemas de integración numérica con el objetivo de estudiar y resolver los llamados problemas rígidos descritos por sistemas de ecuaciones diferenciales ordinarias ([5]), ([8]) y ([4]), los que aparecen con mucha frecuencia en modelos que describen reacciones químicas y otras áreas de las ciencias aplicadas. Teniendo en cuenta, que el interés esencial de este trabajo es la solución numérica del problema de estimación de parámetros en modelos dinámicos definidos por sistemas de ecuaciones diferenciales ordinarias, abordado como un problema de optimización, el mismo tiene como objetivo, además de mostrar el problema y su discretización, tratar la adecuación y validación de los algoritmos evolutivos para la resolución del mismo.
Sea el siguiente problema continuo de optimización:
donde: x ∈ < lo que significa que se está modelando un proceso dinámico definido por un sistema n-dimensional de ecuaciones diferenciales ordinarias, las cuales dependen de un vector p-dimensional de parámetros desconocidos µ. También se considera un conjunto de datos o mediciones x1, x2..., xs del vector variable observado y de dimensión n, en diferentes instantes de tiempo {τ1, τ2,...,τs} y se desea minimizar J, una suma de funciones residuales. En trabajos anteriores, en los que se usaron técnicas deterministas ([6]) se presentó la idea de usar esquemas de integración numérica como restricciones, en lugar de las ecuaciones diferenciales, transformando el problema continuo en un problema discreto que puede resolverse de una manera más sencilla y exigiendo diferenciabilidad para cada una de las funciones que intervienen en el modelo. Dicha transformación depende directamente del método o sistema de integración que se utilice. En este trabajo se formuló el siguiente problema discreto en el cual, el sistema de ecuaciones diferenciales es sustituido por un esquema de paso simple:
Donde las funciones Ki representan las fórmulas explícitas de Runge-Kutta y las fórmulas de integración de Rosenbrock y bi, los coeficientes correspondientes al esquema utilizado. De manera general, las funciones Ki pueden ser tomadas de diferentes formas según los esquemas de integración numérica que se utilicen. Considerando que la partición de integración debe contener al conjunto de tiempos de medición {τ1, τ2, ..., τs}, de modo que a cada índice de medición i ∈ {1, 2, ..., s} corresponde un índice de integración, se define cierta correspondencia entre los índices construyendo un conjunto que contiene los índices de integración correspondientes a las mediciones, lo que permite expresar la función objetivo Gei dependiendo de la función característica de dicho conjunto de índices. En este trabajo, con el objetivo de abordar el problema que se ha descrito, se procedió haciendo un tipo de enfoque de “método directo” para la solución del problema inverso, tal y como se desarrolló en ([7]) para resolver el citado problema aproximado, pero se utilizó una estrategia no determinística, que se describe a continuación.
Para analizar resultados de algoritmos propuestos, se consideraron numerosos ejemplos, aunque en esta sección sólo se muestran los resultados obtenidos con algunos de los más ilustrativos:
Las figuras 1(a) y 1(b) muestran la evolución de los parámetros µ1 y µ2, observándose la buena adaptación del algoritmo y las figuras 2(a) y 2(b), una superposición de las variables de estado, estimadas (representadas con líneas discontinuas) y los datos (línea continua), contra el tiempo, mostrándose la buena aproximación a los datos.
Referencias:
-
Beivide, A. (2019, 20 mayo). Algoritmos genéticos. iAgua. https://www.iagua.es/blogs/alejandro-beivide/algoritmos-geneticos
-
Revista de Matematica: Teor ´ ´ıa y Aplicaciones 2006 13(2) : 139–150 cimpa – ucr – ccss issn: 1409-2433
-
Bard, J. (1974) Non linear Parameter Estimation. Academic Press Inc.
-
Butcher, J.C.(1987) The Numerical Analysis of Ordinary Differential Equations. John Wiley, New York.
-
Dennis, J.E.; Schnabel, R.B. (1983) Numerical Methods for Unconstrained Optimization and Non Linear Equations. Prentice-Hall Series in Computational Mathematics, New Jersey.
-
Enright, W.H.(1976) “Second derivate multi-step methods for Stiff Ordinary Differential Equations”, Numerical Analysis 2(2).
-
Gear, W.C.(1971) Numerical Initial Value Problems in ODE. Prentice-Hall, New Jersey.
-
G´omez, J.A.; Marrero, A. (2000) “Computing gradients of inverse problems in ODE models”, Revista de Investigaci´on Operativa, ALIO 9(1,2,3): 179–206.
-
G´omez, J.A & Marrero, A. (2000) “Convergence of discrete approximations of inverse problems in ODE models”, Revista Investigaci´on Operativa, ALIO 9(1,2,3): 207–224.