Optimización global basada en aritmetica de intervalos y ramificación y acotacionparalelizacion

Abstract

Esta tesis trata el problema de Optimización Global, el cual está relacionado con la caracterización y computación del máximo o mínimo global de funciones no lineales. Este tipo de problemas pertenecen a la clase de problemas NP-Duros, por lo que se propone el procesamiento paralelo para reducir su tiempo de ejecución. Los algoritmos presentados están basados en el análisis de intervalos, ya que permite a obtención de información global a un coste bajo. La información obtenida por la Aritmética de Intervalos ha sido utilizada como regla de acotación en algoritmos de Ramificación y Acotación para encontrar las soluciones rigurosas en varios problemas de Optimización Global. El primer problema resuelto ha sido el de encontrar la mínima raíz de una función unidimensional. También se ha resuelto el problema de encontrar la mínima de las mínimas raíces en un conjunto de funciones unidimensionales. Para el problema general de encontrar el mínimo de una función n-dimensional se ha presentado un nuevo parámetro que estima la probabilidad de que una subregión contenga un mínimo y por lo tanto la carga computacional que tiene asociada. Este parámetro se ha utilizado para mejorar las etapas realizadas en los algoritmos de Ramificación y Acotación, concretamente: para determinar el nivel de división ha realizar en una subregión para establecer un nuevo criterio de eliminación heurístico y para desarrollar nuevas reglas de selección. También se ha utilizado este parámetro para implementar un nuevo algoritmo que permite evitar los altos requerimientos de memoria que pueden aparecer en los algoritmos de Optimización Global basados en intervalos, a costa de perder la garantía de que las soluciones encontradas son las globales. Desde el punto de vista del paralelismo, seha usado el nuevo parámetro como estimador de la carga computacional en las estrategias de balanceo dinámico sobre computadores paralelos de