Algoritmos genéticos en optimización multiobjetivo

En la tesis de maestría de Gutiérrez Méndez, publicada el año 2011 con el título “Optimización multiobjetivo usando algoritmos genéticos culturales”, se menciona que la optimización multiobjetivo tiene amplias aplicaciones en distintas aéreas de la ingeniería y las ciencias computacionales. Muchos de estos problemas tienen espacios de búsqueda bastante grandes por lo que, en algunos casos, no pueden ser resueltos mediante técnicas exactas en un tiempo razonable. Para resolver este tipo de problemas suelen utilizarse meta heurísticas. Dentro de las meta heurísticas destacan los algoritmos basados en computación evolutiva, los cuales simulan el proceso de selección del más apto en una computadora, a fin de resolver problemas, por ejemplo de optimización y clasificación. En los algoritmos evolutivos, las soluciones de un problema son modeladas como individuos de una población, a las cuales se les aplican operadores inspirados en la evolución biológica. Este tipo de algoritmos han sido capaces de obtener muy buenos resultados en diversos problemas del mundo real, de alta complejidad.
Nocedal y Wright, en el libro publicado el año 2006 con el título “Optimización numérica”, mencionan que existen problemas para los cuales las variables de decisión solo son validas si sus valores son enteros. A los problemas de este tipo se les denomina problemas de programación entera. Estos son un caso particular de los llamados problemas de optimización discreta. En dichos problemas los valores de las variables de decisión son tomados de un conjunto finito de elementos. En contraste, para los problemas de optimización continua, las variables de decisión toman valores de un conjunto infinito de elementos, en teoría, debido a que los reales se representan de forma finita en una computadora. Los problemas de optimización continua suelen ser más sencillos de resolver pues la información sobre la función objetivo y las restricciones en un punto particular ayudan a deducir información sobre todos los puntos cercanos. En el caso de los problemas discretos el comportamiento de la función objetivo y las restricciones pueden variar considerablemente entre dos puntos considerados cercanos. Esta idea es complementada por Dantzig y Thapa, en el libro publicado el año 1997 con el título “Introducción a la programación lineal”, quienes señalan que un caso particular de los problemas de optimización ocurre cuando la función objetivo y las restricciones son funciones lineales. En este caso se dice que se trata de un problema de programación lineal. Existen varios métodos para resolver problemas de este tipo que garantizan encontrar la solución exacta, como por ejemplo el llamado método simplex.
Jensen, en el artículo publicado el año 2003 con el título “Reducción de la complejidad del tiempo de corrida de algoritmos evolutivos multiobjetivo”, señala que cuando por lo menos una de las restricciones o la función objetivo son funciones no lineales, se dice que el problema es de programación no lineal. Para este tipo de problemas no existe un método general que garantice encontrar la mejor solución posible en tiempo polinomial. La mayoría de los algoritmos para problemas de optimización no lineal encuentran únicamente óptimos locales, es decir, puntos óptimos respecto a una región cercana, en contraste con los óptimos globales, los cuales son los mejores respecto a todos los demás puntos factibles. Según Kirkpatrick y sus colegas, en el artículo publicado el año 1983 con el título “Optimización mediante el recocido simulado”, existen métodos para resolver problemas de optimización no lineal pero generalmente requieren de la primera derivada de la función objetivo. Esta información no siempre se encuentra disponible o es costosa de calcular. En la práctica, suelen utilizarse heurísticas para resolver problemas de programación no lineal. Un ejemplo de heurística es el recocido simulado. Una familia de heurísticas bastante popular es la computación evolutiva, la cual ha mostrado resultados competitivos en una amplia variedad de problemas, según lo indica Lamont y sus colegas en el libro publicado el año 2002 con el título “Algoritmos evolutivos para resolver problemas multiobjetivo”.
Los algoritmos de optimización son métodos iterativos. Comienzan con una aproximación, posiblemente aleatoria, y generan una secuencia de estimaciones hasta alcanzar una cierta condición de paro. La estrategia que decide cómo pasar de una estimación a otra es lo que distingue a un algoritmo de otro. Nocedal y Wright, en el libro mencionado en párrafos anteriores, mencionan que un buen algoritmo de optimización debe tener las siguientes características: (1) Robustez. Debe desempeñarse bien en una amplia variedad de problemas. (2) Eficiencia. No debe requerir de recursos de cómputo excesivos. (3) Exactitud. Debe identificar la solución con precisión. Un buen algoritmo debe ofrecer un compromiso adecuado entre estas características. En el artículo de Lagunas y sus colegas, publicado el año 2013 con el título “Optimización multiobjetivo mediante algoritmos genéticos: Aplicación a controladores PID robustos”, se menciona que el problema de optimización multiobjetivo tiene sentido cuando los índices de desempeño involucrados están en conflicto, de lo contrario el problema de optimización multiobjetivo puede ser considerado como monobjetivo, ya que los mismos valores, podrían minimizar o maximizar todos los objetivos de manera simultánea. Los algoritmos genéticos han sido utilizados exitosamente en optimización multiobjetivo. Una de las primeras aplicaciones fue realizada por Fonseca y Fleming en el año 1988, en el artículo titulado “Optimización multiobjetivo y manejo de restricciones múltiples con algoritmos evolutivos”, donde se utiliza un algoritmo genético multiobjetivo para el control de una turbina de gas. En el año 2000, Herreros propuso en su tesis doctoral, titulada “Diseño de controladores robustos multiobjetivo por medio de algoritmos genéticos”, un algoritmo llamado diseño de control robusto multiobjetivo, para el diseño de controladores robustos. Para la sintonización de los controladores robustos, el problema de control, se presenta como un problema de optimización multiobjetivo, de un conjunto de funciones, donde se incluyen los parámetros del controlador.

Algoritmo Levenberg-Marquardt

En la tesis doctoral de Fernández Slezak, publicada el año 2010 con el título “Estimación de parámetros en modelos biológicos complejos: Aplicación a modelos de crecimiento tumoral”, se indica que el objetivo de la optimización es encontrar los parámetros que minimicen la distancia entre los valores experimentales y los de la simulación. Esta distancia, a la que se denomina función de costo, puede ser definida de muchas maneras. Una de las técnicas más utilizadas es la llamada minimización de cuadrados mínimos, cuya función de costo es la suma de las diferencias cuadráticas entre el modelo y los datos. Existe una enorme cantidad de algoritmos aproximados de búsqueda de mínimos locales, que pueden separarse en categorías muy diferentes, por ejemplo métodos de descenso, algoritmos genéticos, etc. Las técnicas para la optimización no lineal de la función de cuadrados mínimos, se agrupan en algoritmos de tres categorías: Métodos de descenso, métodos de búsqueda directa y métodos inspirados en fenómenos físicos. Todos los métodos de minimización no lineal son iterativos, es decir que parten de un punto inicial y el método genera una secuencia de parámetros que, en caso de converger, se acerca a un mínimo local. Entre los métodos más conocidos se encuentra el método de Gauss-Newton, descrito en el artículo de Björck, publicado el año 1996 con el título “Métodos numéricos para problemas de mínimos cuadrados”. El método de minimización Levenberg-Marquardt también pertenece a la familia de problemas llamados métodos de descenso, este algoritmo fue presentado por Levenberg en el artículo publicado el año 1944 con el título “Método para la solución de ciertos problemas no lineales en mínimos cuadrados”, el cual fue complementado con el articulo de Marquardt publicado el año 1963 con el título “Un algoritmo para estimación de mínimos cuadrados de parámetros no lineales”. Este algoritmo propone un esquema de Gauss-Newton amortiguado. Al igual que Gauss-Newton, toma la aproximación lineal del modelo y una determinada dirección de descenso.

El método de Levenberg-Marquardt es conocido hace muchos años, y es altamente utilizado en el ambiente de la optimización, en especial en la minimización de cuadrados mínimos. Por tal motivo, para el uso de este algoritmo, en muchos círculos académicos, se opta por una implementación preexistente de la vasta cantidad de opciones disponibles. Una de las bibliotecas numéricas más conocidas es Linpack, descrita por Bunch y sus colegas en la guía de usuario “Linpack” del año 1979, orientada principalmente a la implementación de rutinas relacionadas con el “algebra lineal para el cálculo de vectores y matrices”. Pensada para el cálculo en supercomputadoras, fue desarrollada a fines de la década de los años 1970 y ha estado en constante evolución desde entonces. Ha sido superada por la biblioteca Lapack, la cual es descrita por Anderson y sus colegas en la guía de usuario de “Lapack” publicada el año 1999. En conjunto con Linpack/Lapack, se desarrolló MinPack, una serie de rutinas dedicadas a la resolución de ecuaciones no lineales y problemas de minimización de cuadrados mínimos, la cual es descrita por Moré y sus colegas en el proyecto “Minpack”, publicado el año 1984.

El algoritmo Levenberg-Marquardt calcula el Jacobiano del modelo con respecto a los parámetros, y utilizando éste busca un mínimo local. El Jacobiano es necesario en cada iteración para calcular la dirección hacia el mínimo local. Debido a que no es bastante difícil el cálculo analítico el Jacobiano es estimado a través de un algoritmo. Para estimar el Jacobiano es necesario realizar numerosas corridas del modelo; por ejemplo, para aproximarlo numéricamente utilizando el método de diferencias finitas centradas es necesario duplicar la cantidad de parámetros variables, que forman parte de las evaluaciones del modelo. El modelo a ser minimizado es muy intensivo en poder de cómputo, por lo que el cálculo del Jacobiano también demanda mucho. Por este motivo se realiza una implementación en paralelo para el cálculo efectivo del Jacobiano. Cada corrida necesaria para la estimación es independiente de la otra, por lo que es trivialmente paralelizable. La implementación de este algoritmo es muy sencilla utilizando un modelo Cliente-Servidor. Al necesitar la estimación del Jacobiano, se reservan nodos para procesamiento. La función para calcular el Jacobiano corre en un nodo principal que distribuye las tareas entre los nodos esclavos disponibles, que sólo espera los parámetros con los cuales deben correr y la señal de inicio. Al recibir esta información, el nodo esclavo ejecuta el modelo con los parámetros recibidos. Luego el amo espera a que cada nodo esclavo haya terminado y junta los resultados de todas las ejecuciones. Por último, realiza el cálculo devolviendo la estimación del Jacobiano.

El algoritmo de retropropagación ha demostrado converger de forma lenta hacia el error mínimo, en especial cuando se tiene una gran cantidad de patrones de entrada. A la fecha existen variados algoritmos que convergen a una velocidad mayor que el algoritmo de retropropagación, como el algoritmo de Levenberg-Marquardt, descrito de manera formal por Bishop, en el libro publicado el año 1995 con el título “Redes neuronales para reconocimiento de patrones”. Hudson y sus colegas, en la guía de usuario publicada el año 2013 con el título “Matlab: Caja de herramientas para redes neuronales”, menciona que este algoritmo se aplica a redes neuronales con un número de patrones de pequeño o mediano tamaño, ya que ocupa demasiada memoria en el cálculo, por lo que su complejidad en cálculos es mayor. Esta mayor complejidad se debe a que se tiene que combinar el gradiente y la aproximación de Gauss-Newton de la matriz Hessiana de la función del error en la regla de actualización de los pesos. El cálculo de la matriz Hessiana es muy costoso computacionalmente hablando, por ello la complejidad del algoritmo crece.

Sistemas de bases de datos difusas

En la tesis de grado de Sanchis, publicado el año 2015 con el título “Bases de datos relacionales difusas”, se señala que las bases de datos tradicionales son bastante limitadas, no permiten almacenar ni tratar con datos imprecisos, sin embargo las personas manejan datos imprecisos muy a menudo y de manera muy eficiente. A la definición del formato interno de una base de datos difusa, y su esquema global de implementación, se le denomina “Interface difusa para sistemas relacionales”. En la tesis doctoral de Martínez, publicada el año 2008 con el título “Sistema de gestión de bases de datos relacionales difusas multipropósito: Una ontología para la representación del conocimiento difuso”, se menciona que los elementos que forman parte del tratamiento impreciso pueden ser representados de diversas maneras. De ese modo, una distribución de posibilidad normalizada puede representarse mediante parábolas, hipérbolas, etc. Sin embargo, la implementación de la “Interface difusa para sistemas relacionales”, propuesta en la tesis doctoral de Galindo del año 1999 titulada “Tratamiento de la imprecisión en bases de datos relacionales: Extensión del modelo y adaptación de los sistemas de gestión de bases de datos actuales”, y su servidor de consultas imprecisas, construidos sobre el “Modelo generalizado para bases de datos relacionales difusas”, propuesto en la tesis doctoral de Medina del año 1994 titulada “Bases de datos relacionales difusas: Modelo teórico y aspectos de su implementación”, asume la representación trapezoidal descrita por cuatro puntos. Esta simplificación se explica en función de la contradicción que supone representar datos intrínsecamente imprecisos mediante distribuciones de posibilidad definidas de forma altamente precisa, que además añaden el factor del incremento asociado al costo computacional. Los valores que pueden formar parte de un dominio generalizado difuso pueden dividirse en dos grupos: (1) Datos precisos. También llamados crisp o clásicos. Dado que lo que se almacena son datos clásicos, el almacenamiento dependerá directamente de la capacidad de representación del sistema de gestión de la base de datos relacional difusa, sobre el que se aplique la implementación. (2) Datos imprecisos. También llamados difusos, se corresponden con datos de dos subtipos, datos imprecisos sobre un referencial ordenado, que engloban a todos aquellos datos descritos mediante una distribución de posibilidad construida sobre un conjunto referencial discreto o continúo ordenado, con una relación de orden definida.

Sanchis, en la tesis doctoral citada, menciona que para la representación y el tratamiento de información imprecisa en el ámbito de las bases de datos relacionales, se han presentado varios modelos a lo largo de los años. Entre ellos, destacan: (1) Aproximaciones que no emplean la lógica difusa, y que se basan en el modelo original de Codd, descrito en el artículo publicado el año 1979 con el título “Extendiendo el modelo de base de datos relacional para capturar mayor significado”. (2) Aproximaciones que usan distribuciones de posibilidad para representar la información difusa a nivel de tuplas, como la de Raju y Majumdar, descritas en el artículo del año 1988 titulado “Dependencias funcionales difusas y descomposición sin pérdidas de sistemas de bases de datos relacionales difusas”. Este modelo también se ha denominado “Modelo básico de bases de datos”. (3) Aproximaciones que utilizan las relaciones de similitud para representar la información difusa, son aquellos desarrollados por Buckles y Petri, en el artículo publicado el año 1982 con el título “Una representación difusa de los datos para bases de datos relacionales”, Shenoi y Melton, en el artículo del año 1989 titulado “Relaciones de proximidad en bases de datos relacionales difusas” y Rundensteiner y sus colegas, en el artículo publicado el año 1989 con el título “Sobre las medidas de proximidad en los modelos de datos relacionales difusos”. (4) Aproximaciones que usan distribuciones de posibilidad para representar la información difusa a nivel de atributo. Algunas de estas son las de Prade y Testemale, descritas en el artículo publicado el año 1987 con el título “Base de datos relacional difusa: cuestiones de representación y reducción utilizando medidas de similaridad”, Umano y sus colegas, en el artículo de 1980 titulado “Proceso de recuperación de bases de datos difusas”, además de Zemankova y Kaendel, en el artículo del año 1985 titulado “Implementación de imprecisión en los sistemas de información”. (5) Aproximaciones mixtas que combinan diferentes técnicas para representar la información imprecisa y conseguir representar el máximo de información posible. Estas aproximaciones se basan en la propuesta de un modelo difuso que combina distribuciones de posibilidad y relaciones de similitud a la vez, como la base de datos difusa extendida basada en posibilidad propuesta en el artículo de Ma y sus colegas, publicado el año 2000 con el título “Medida semántica de datos difusos en bases de datos relacionales difusas extendidas basadas en posibilidad”, Rundensteiner y sus colegas en el artículo del año 1989 titulado “Sobre las medidas de proximidad en los modelos de datos relacionales difusos”, además de Chen y sus colegas, en el artículo de 1992 titulado “Tratamiento general de redundancia de datos en un modelo de datos relacional difuso”, o la extensión hecha por Medina y sus colegas denominada “Modelo generalizado para bases de datos relacionales difusas”, descrita en la tesis doctoral citada anteriormente.

El modelo generalizado para bases de datos relacionales difusas surge como una integración de algunas tendencias para resolver el problema de la representación y consulta de información imprecisa en el seno del modelo relacional. Dicho modelo define formalmente una base de datos relacional difusa a través de las definiciones de los siguientes conceptos: (1) Dominio difuso generalizado. Se trata de una extensión del concepto de dominio relacional que amplía el rango de valores que un atributo puede tomar. Entre algunos de estos valores se encuentran: El valor nulo, el valor no aplicable, el valor desconocido, un conjunto de asignaciones escalares o numéricas posibles, distribuciones de posibilidad construidas sobre dominios escalares o numéricos, etc. (2) Relación difusa generalizada. Define una relación incluyendo el concepto de dominio difuso generalizado. (3) Comparadores difusos generalizados. Extienden el concepto de comparador para incluir las comparaciones entre valores que existen en el dominio difuso generalizado. (4) Operaciones de bases de datos. Proyección y selección difusa.