Optimización global intervalarpredicción, acotación y separabilidad

Resumen

La vida cotidiana está llena de problemas de optimización: la organización de productos dentro de un almacén, la organización de los paquetes y productos en las furgonetas de una empresa de transportes, la fabricación de envases con las dimensiones óptimas para maximizar el almacenamiento y/o minimizar el material empleado, el diseño de piezas industriales que se ajusten a unas determinadas cualidades o el encontrar la mezcla adecuada de distintas materias primas de tal modo que se mejore el producto final y se minimice su coste son algunos ejemplos de problemas de optimización. La calidad de la solución hallada permitirá ahorrar en costes de producción y fabricación, mejorar el tiempo de fabricación, mejorar la organización y gestión de los recursos, obtener mejores productos con un menor coste, etc. Las áreas donde se hace necesaria la resolución de problemas de optimización son muy diversos: Ingeniería, Química, Economía, Robótica, etc. Podemos distinguir dos tipos de problemas de optimización desde un punto de vista estrictamente matemático: la optimización lineal y la optimización no lineal. Los problemas de optimización lineal son aquellos en los que únicamente intervienen funciones lineales. Son bien conocidos y en general su dificultad depende del número de restricciones lineales. Los problemas de optimización no lineal pertenecen a la clase de problemas NP-Completos, es decir, no existe una solución en tiempo polinómico, por lo que a medida que el número de variables del problema aumenta, el tiempo para resolverlo crece exponencialmente. Una segunda distinción de los problemas de optimización se realiza entre optimización combinatoria y optimización continua, aunque ambas clases de problemas pueden aparecer mezclados. Esta tesis se enmarca dentro de los problemas de optimización continua no lineal donde el valor de las variables varía libremente dentro de unos límites. En general, un problema de optimización puede contener muchas soluciones que son válidas o factibles dentro de los parámetros o de la región de búsqueda, conocidas como óptimos locales. Los algoritmos que encuentran soluciones locales son denominados algoritmos de optimización local. La mejor solución de todas las locales es el óptimo global y la búsqueda del mismo se conoce como optimización global. Comúnmente, la búsqueda del óptimo global consiste en la búsqueda del mínimo valor global de la función que queremos minimizar, puesto que los problemas de maximización pueden reescribirse como uno de minimización. El mejor valor, u óptimo global, de la función en la región de búsqueda es único, pero puede encontrarse en distintas localizaciones, lo que hace que el problema sea aún más complicado. Esta tesis se enmarca en el ámbito de la optimización global. Una clasificación clásica de las estrategias existentes para resolver los problemas de optimización global las divide en dos: estrategias de búsqueda estocásticas y estrategias de búsqueda deterministas. Las estrategias de búsqueda estocásticas se basan en muestrear la función objetivo con un conjunto finito de puntos iniciales escogidos al azar y en la generación de nuevos puntos aleatorios basándose en criterios heurísticos. Estos métodos no aseguran que el mínimo global sea obtenido al finalizar el proceso de búsqueda si el número de muestras no es lo suficientemente grande, o dicho de otra forma, solo garantizan el encontrar la solución global cuando el número de muestras tiende a infinito. Asimismo, este tipo de estrategias suelen utilizar un número elevado de iteraciones del algoritmo para tratar de mejorar la solución obtenida en iteraciones anteriores. Ese número de iteraciones suele establecerse al inicio. Las estrategias de búsqueda deterministas generan una secuencia de pasos fijos cuando el algoritmo se ejecuta para el mismo problema. Estas estrategias pueden obtener una aproximación del óptimo global con la precisión deseada, aunque no pueden garantizar que su localización sea la correcta. Los métodos que exploran todo el espacio de búsqueda se conocen como métodos exhaustivos. Estos métodos aseguran la localización del mínimo global con la precisión deseada al finalizar el proceso. Uno de los métodos exhaustivos más usados son los algoritmos de ramificación y acotación (branch-and-bound). Este algoritmo construye un árbol de búsqueda en donde los nodos activos corresponden a regiones del espacio de búsqueda donde puede encontrarse la solución global. El nodo más prometedor es el primero en visitarse y dividirse. Los criterios para elegir el nodo más prometedor se basan en cuestiones heurísticas y se conoce como estrategia de selección. Si en la estrategia de selección no influyen factores aleatorios, el algoritmo tendrá un comportamiento determinista. Si aquellos nodos que han sido rechazados o eliminados son aquellos en los que se ha verificado que no contienen una solución global, la solución obtenida será una solución rigurosa. Utilizaremos la aritmética de intervalos para garantizar que los nodos eliminados no contienen el óptimo global. Con la aritmética de intervalos podemos obtener cotas superior e inferior del rango real de la función objetivo. Si un nodo tiene una cota inferior mayor que el mejor valor global del mínimo conocido hasta el momento, podemos descartar ese nodo ya que en su interior no encontraremos la solución. Además, otras muchas de las propiedades de la aritmética de intervalos permiten acelerar la resolución del problema, como por ejemplo el test de monotonía. Al final del proceso se obtiene una lista de nodos que determina la región o regiones donde se localiza el mínimo de la función y cotas superiores e inferiores de su valor. Cuanto mayor sea la precisión deseada para la solución, menor será el tamaño de la región o regiones obtenidas en donde se encuentra el mínimo global y mayor el tiempo de cómputo necesario para encontrarla. Los algoritmos de ramificación y acotación intervalares son uno de los pocos métodos que obtienen una solución rigurosa a los problemas de optimización global. Esta tesis se enmarca en el estudio de estos métodos exhaustivos, rigurosos y deterministas. Los algoritmos de ramificación y acotación pueden requerir una enorme cantidad de cómputo y memoria. Debido a estos grandes requerimientos, se deben utilizar mecanismos que aceleren el proceso de búsqueda y minimicen los requisitos de memoria. El proceso de mejora de los algoritmos de ramificación y acotación puede ir orientado a descubrir nuevas técnicas o procedimientos en el ámbito secuencial del algoritmo de optimización, o bien, a estudiar nuevos métodos y estrategias que presenten algoritmos paralelos que hagan uso de múltiples procesadores de forma eficiente. El objetivo general de esta tesis es encontrar nuevos mecanismos que permitan acelerar la convergencia de los algoritmos de ramificación y acotación intervalares, tanto secuenciales como paralelos. La organización de esta tesis es como sigue. El capítulo 1 introduce y clasifica los problemas de optimización y enmarca en esta clasificación a los problemas de optimización global continua, en los que estamos interesados. El capítulo 2 describe las características y propiedades fundamentales de la aritmética de intervalos. El capítulo 3 estudia en profundidad la resolución de problemas de optimización global mediante algoritmos de ramificación y acotación intervalares con una extensa revisión bibliográfica. En el capítulo 4 se estudia la estimación de la carga computacional en los algoritmos de ramificación y acotación. Este valor puede emplearse para decidir los recursos computacionales necesarios para distribuir la carga de trabajo entre varios procesadores, lo que puede mejorar el rendimiento de los algoritmos paralelos de ramificación y acotación. Se presentan tres estrategias diferentes y se estudia la calidad de las mismas. Los resultados obtenidos en las predicciones muestran que se pueden obtener buenas estimaciones del número de nodos pendientes por evaluar a partir de la mitad de la ejecución y en algunos casos, incluso desde etapas más tempranas. El capítulo 5 presenta un nuevo método de acotación basado en la separación de términos de la función objetivo. Se desarrolla toda la base teórica para funciones unidimensionales y se estudia su rendimiento sobre un conjunto de funciones de prueba. Los resultados obtenidos son bastante prometedores. Se pretende extender este estudio a funciones de más de una dimensión en trabajos futuros. El capítulo 6 presenta un nuevo algoritmo secuencial de ramificación y acotación para funciones objetivo aditivamente separables con variables comunes, se estudian sus propiedades y se presentan nuevos mecanismos de aceleración. Los resultados empíricos muestran que se puede mejorar la eficiencia en la optimización de una función aditivamente separable con variables comunes con este algoritmo específico.