Article in xml format
Automatic translation
Cited by SciELO 
Cited by Google 
Similars in
SciELO 
Similars in Google 
Permalink
Información tecnológica
On-line version ISSN 0718-0764
Inf. tecnol. vol.17 no.5 La Serena 2006
http://dx.doi.org/10.4067/S0718-07642006000500011
| Información Tecnológica-Vol. 17 N°5-2006, pág.: 67-74 ECONOMIA Y GESTION Optimización Global por Intervalos: Aplicación a Problemas con Parámetros Inciertos Global Optimization by Interval Analysis: Application to Problems with Uncertain Parameters
Pedro G. Campos (1) y Héctor M. Valdés-González (2)* * autor a quien debe ser dirigida la correspondencia Resumen Este artículo presenta la aplicación de una plataforma de software, que permite realizar optimización global de criterios no lineales con restricciones utilizando análisis por intervalos. El problema ha sido abordado considerando las variables del criterio a optimizar como intervalos, así como también los parámetros con incertidumbre. Se describe la aritmética por intervalos utilizada, el algoritmo de optimización implementado y su utilización como parte de una aplicación mayor que requiere de optimización. Se presentan resultados para problemas de criterios diferenciables y no diferenciables, contrastados con otro software de optimización global, que muestran las bondades de la plataforma implementada. Palabras claves: análisis por intervalos, optimización global, parámetros inciertos, criterios no-lineales. Abstract This paper presents the application of a software platform to the problem of global optimization of non linear criteria with restrictions by interval analysis. The problem has been tackled by representing the variables and uncertain parameters of the criterion to be optimized as intervals. The mathematics of the intervals used and the optimization algorithm, together with their role in a larger application, are described. Results for differentiable and non-differentiable problems are shown and contrasted with another software for global optimization to highlight the benefits of the implemented platform. Keywords: interval analysis, global optimization, uncertain parameters, non-linear criteria INTRODUCCION La necesidad de determinar óptimos globales se presenta en numerosas disciplinas que modelan el mundo real. La optimización ha encontrado una amplia aplicación en el estudio de sistemas físicos y químicos, sistemas de planificación de la producción y calendarización de actividades, problemas de localización y transporte, asignación de recursos en sistemas financieros, y diseño en ingeniería entre otros (Leclerc, 1992; Sahinidis, 2004). A pesar de su importancia, no existen soluciones eficientes que resuelvan el problema general de optimización global (Campos, 2004). En el caso de optimización local, una función puede poseer varios óptimos locales, con significativas variaciones en sus valores. Aunque algoritmos iterativos, por ejemplo, el método de Newton y sus variantes (Luenberger, 1989), pueden encontrar uno de estos mínimos locales eficientemente, resulta difícil determinar si dicha solución local es en efecto una solución global. En este contexto, la literatura presenta diversos algoritmos para realizar optimización global, ver por ejemplo (Hansen, 1992; Leclerc, 1992; Van Iwaarden, 1996; Jaulin et al., 2001). Del mismo modo, existen diversas implementaciones de estos algoritmos (Pardalos y Romeijn, 2002; Khompatraporn, 2005; Neumaier et al., 2005), las cuales muestran distintas características en cuanto a tiempo de ejecución, exactitud de los resultados, complejidad de uso, etc. Este trabajo presenta una implementación del algoritmo de optimización global descrito en (Hansen, 1992) y sintetiza sus diferentes partes. En este sentido, se presentan las pruebas de selección que permiten descartar regiones de un espacio de soluciones que no contienen óptimos globales (Moore, 1976; Skelboe, 1974; Ichida y Fuji, 1979). El mencionado algoritmo de optimización está basado en aritmética de intervalos (Moore, 1966), lo cual permite garantizar los resultados obtenidos, ya que se considera el efecto de los errores de redondeo del procesador, lo que muy pocas implementaciones contemplan (Neumaier et al., 2005), en particular frente al problema de optimización global con parámetros inciertos. Problema para el cual, este artículo presenta un enfoque de solución basado en una plataforma implementada en lenguaje C++. Se presenta una breve explicación de su uso en una aplicación mayor que requiere de optimización global, y se muestran algunos resultados obtenidos con la plataforma sobre problemas de optimización sin restricciones publicados, los cuales son comparados con otra librería de rigurosidad similar. También se incluye el resultado sobre un problema de optimización no diferenciable con restricciones, y se consideran algunos parámetros inciertos, lo que muestra la aplicabilidad de la plataforma sobre diferentes tipos de problemas de optimización. ARITMÉTICA DE INTERVALOS Los intervalos,
De esta manera, el intervalo resultante de
Otras operaciones definidas en aritmética de intervalos pueden ser encontradas en (Moore, 1966; Hansen, 1992). Al implementar computacionalmente operaciones por intervalos, las cotas obtenidas consideran el error de redondeo, originado por la representación interna de la aritmética de punto flotante (de precisión fija) implementada en los computadores (Rump, 1992; Hansen, 1992; Leclerc, 1992). Esto se obtiene aproximando hacia la izquierda ( Funciones por intervalos Sea Si se dispone de un vector intervalo
La función Se han desarrollado muchos métodos para representar y evaluar funciones por intervalos. El más sencillo es la extensión natural por intervalos, el cual puede ser obtenido sustituyendo un argumento OPTIMIZACIÓN GLOBAL Formalmente, el problema de optimización global es definido como:
donde Existen diversos métodos para resolver el problema de optimización global, para más detalles ver por ejemplo (Leclerc, 1992; Van Iwaarden, 1996; Campos, 2004). Entre ellos, destacan los llamados métodos de cotas, que calculan cotas de la función objetivo sobre conjuntos compactos; implementados de forma apropiada, pueden producir soluciones rigurosas en optimización global. El algoritmo general que implementan los métodos por cotas es el siguiente (Leclerc, 1992): 1) Particionar el espacio inicial de búsqueda en regiones más pequeñas 2) Acotar la función (y posiblemente sus derivadas) sobre las subregiones, y 3) Rechazar (usando las cotas calculadas en el paso 2) las subregiones que definitiva-mente no contienen minimizadores globales. La unión de las regiones no rechazadas contiene todos los minimizadores globales. El espacio de búsqueda usualmente se divide en hiperrectángulos, debido a sus propiedades geométricas (Hansen, 1992; Leclerc, 1992 y Van Iwaarden, 1996). En cuanto al paso de rechazo, este puede tomar cualquiera de las siguientes formas: a) Rechazo de las subregiones cuyas cotas inferiores calculadas en el paso 2 del algoritmo sean mayores que la cota superior del mínimo global conocida hasta ese momento (en cada iteración se calcula esta última cota en base a la información disponible). b) Rechazo de las subregiones que no estén en el espacio factible (es decir, que no cumplen ciertas restricciones impuestas). c) Si la función es diferenciable: c1) Rechazo de las subregiones que no estén en el borde del espacio inicial de búsqueda donde c2) Rechazo de las subregiones donde la función es no convexa en toda la subregión. Utilizando el análisis de intervalos, se desarrolló un método que calcula cotas inferiores y superiores para funciones utilizando los principios de la aritmética de intervalos. Moore (1976), Skelboe (1974) e Ichida y Fuji (1979) desarrollaron y mejoraron un algoritmo de optimización global basado en esta aritmética. Con dicho algoritmo, se puede resolver el siguiente problema general de optimización no-lineal (Valdés-González et al., 2003):
donde El algoritmo, en forma iterativa divide Es importante notar que el trabajo con análisis por intervalos considera el error de redondeo en los cálculos, de manera que las cajas que son almacenadas en el listado contienen de forma garantizada la solución matemática exacta (inclusive sobre la frontera). El proceso iterativo termina cuando el ancho de las cajas en el listado es menor que una cierta tolerancia prescrita, denotada como Selección de Los métodos para rechazar una subcaja corresponden a pruebas de selección, las cuales son descritas a continuación: a) Prueba de factibilidad: Se puede evaluar toda b) Prueba de punto medio (Ichida y Fuji, 1979): Si ALGORITMO DE OPTIMIZACIÓN Con las pruebas anteriores, se puede escribir un sencillo algoritmo de optimización global por intervalos (Leclerc, 1992): Entrada: Salida : 1) 2) 3) 4) Ciclo principal Obtener primera caja Dividir Ejecutar pruebas de selección sobre Si Ejecutar pruebas de selección sobre Si Si el ancho de primera caja en Fin del ciclo principal. 5) Imprimir Las propiedades de este algoritmo son las siguientes: a) El listado de cajas generadas (almacenadas) es técnicamente una cola de espera. Esto significa que las cajas son añadidas al final de la cola, y son tomadas desde el principio de la misma. b) En cada iteración, se remueve una caja desde el principio de la lista. c) Las pruebas de selección se realizan sobre cada mitad d) La primera caja en el listado es siempre la más ancha, de manera que si su ancho es menor que la tolerancia prescrita e) En cada paso del proceso, las cajas que están en el listado contienen todos los puntos que son minimizadores globales de la función. f) Mientras menor sea la tolerancia g) La complejidad del algoritmo es exponencial sobre el número de variables de la función objetivo (Valdés-González et al., 2003). Este algoritmo, junto a una librería de aritmética por intervalos, fueron implementados en C++. Este lenguaje, al ser orientado a objetos, facilita en gran medida la implementación, así como el uso de la plataforma. Se implementaron las clases interval, interval_vector e interval_matrix, que proporcionan la funcionalidad de aritmética intervalar a través de sobrecarga de operadores y funciones, lo cual hace más comprensible el código fuente generado, y permite una fácil utilización de variables (objetos) de tipo intervalar, bastando crear instancias de tipo interval con sus correspondientes valores y usando los operadores aritméticos requeridos. Por estar construida mediante el paradigma orientado a objetos, la plataforma resulta ser altamente modular, así como reutilizable por otras aplicaciones de mayor envergadura, que requieran optimización global, o bien operar mediante aritmética intervalar, como por ejemplo, en la implementación del método de estimación de estados IMHSE (detalles en Campos, 2005), donde se toma como base la plataforma presentada. La fig. 1 muestra la utilización de la plataforma, que considera la librería de aritmética intervalar y la capa de optimización, en la aplicación de estimación de estados. Respecto del funcionamiento de la plataforma en comparación con otras implementaciones, se deben tomar en cuenta algunas consideraciones. En general, las implementaciones basadas en algoritmos de optimización heurísticos como Simulated Annealing o Algoritmos Genéticos, por ejemplo SIMMAN, ASA, o CGA (Neumaier, 2006), son mucho más rápidas en tiempo de ejecución que sus contrapartes basadas en algoritmos de optimización determinísticos. Esto es esperable, ya que los algoritmos heurísticos sólo buscan una solución aproximada, pudiendo detener la búsqueda antes de encontrar siquiera un óptimo global. En cuanto a librerías basadas en algoritmos determinísticos, como ICOS, Concave o BARON (Neumaier et al., 2005; Neumaier, 2006), es importante destacar que muchas veces no son rigurosas en los resultados obtenidos, entregando soluciones falsas debido, por ejemplo, al error de redondeo antes mencionado. Este problema, comentado en (khompatraporn et al., 2005), ha sido demostrado en trabajos de comparación de software de optimización global, como (Neumaier et al., 2005); esto, además del hecho que muchas veces los algoritmos son específicos para un determinado tipo de problema (Pardalos y Romeijn, 2002). Así, si bien para algunos problemas otras implementaciones pueden ser mucho más rápidas, es destacable la rigurosidad obtenida con la plataforma presentada, así como la generalidad de su aplicación.
RESULTADOS Y DISCUSIÓN A continuación se presenta una selección de problemas de optimización diferenciables y no diferenciables con restricciones, problemas en los cuales la plataforma desarrollada ha sido aplicada. En algunos de estos problemas, se considera además incertidumbre en algunos parámetros del criterio a optimizar; dicha incertidumbre es representada como internalos, es decir, el parámetro es representado por las cotas inferior y superior de todos sus posibles valores. Los resultados fueron obtenidos en un computador PC con procesador Pentium IV de 1.7 GHz y 256 MB de RAM. a) Para validar la plataforma desarrollada, se obtuvieron los resultados para cuatro problemas clásicos, llamados Six Hump Camel Back (A), Treccani (B), Schwefel 3.1 (C) y Colville4 (D), descritos en (Van Iwaarden, 1996). Los dos primeros tienen 2 variables, el tercero 3 y el último 4. Estos resultados son comparados con aquellos obtenidos utilizando el paquete de optimización global de la librería de aritmética intervalar PROFIL/BIAS, la cual presenta características similares en cuanto a rigurosidad de los resultados, ya que considera los efectos de errores de redondeo (Neumaier, 2006). Los tiempos de ejecución son presentados en la tabla 1, correspondientes a la obtención de resultados con similares niveles de garantía. PROFIL/BIAS permite la rápida obtención de resultados mediante una combinación de algoritmos locales y globales, pero en este caso sólo se consideraron resultados garantizados, es decir, aquellos obtenidos mediante el algoritmo de optimización global por intervalos. Se observa que para el problema con 4 variables, la plataforma es bastante más rápida que PROFIL-BIAS. Esto es gracias a la utilización de pruebas basadas en derivadas (Hansen, 1992, Campos, 2004) Tabla 1: Tiempos de ejecución para problemas de optimización sin restricciones en ambas implementaciones
b) Se considera un problema de optimización no diferenciable con restricciones conocido como Smiley Face" debido a la gráfica a la que da origen. Este problema se define como:
donde:
(Leclerc, 1992) asigna a este problema los valores El resultado obtenido depende de la tolerancia usada. Notar que con una tolerancia menor, se eliminan mínimos locales. Con una tolerancia También se trató el problema asociado considerando incertidumbre en los parámetros
CONCLUSIONES Una plataforma de optimización que implementa un algoritmo de optimización global por intervalos, y que permite representar incertidumbre en los parámetros de un criterio o modelo matemático ha sido presentada. La plataforma desarrollada incluye una librería de aritmética por intervalos que permite alcanzar los objetivos antes mencionados. Dicha plataforma puede ser incluida como parte de una aplicación mayor que requiera de optimización global, o bien puede prestar servicios a una aplicación independiente. Los resultados expuestos, muestran la potencialidad del algoritmo, en particular en cuanto a su propiedad de globalidad, es decir, que asegura encontrar todos los óptimos globales de una función. La garantía de las soluciones obtenidas se basa entre otros, en el hecho de contar con una librería aritmética que permite realizar cálculos en los cuales está considerado adecuadamente el error de redondeo. Finalmente, el tipo de aplicaciones presentadas en simulación nos indican la gran aplicabilidad que una plataforma como esta puede tener en la resolución de problemas de ingeniería. AGRADECIMIENTOS Este trabajo ha sido parcialmente financiado por el proyecto C-14060/17 Inicio de carrera para jóvenes investigadores de la Fundación Andes Chile, el DECOM y DIPOG de la UTA, a través de su programa de Magíster en Ingeniería de Software. REFERENCIAS Campos, P. G., Desarrollo de una plataforma de optimización global utilizando aritmética por intervalos, Memoria de Título, Ingeniería Civil en Computación e Informática, Dpto. Computación e Informática, Universidad de Tarapacá, Arica, Chile (2004). Campos, P. G., State estimation under parameter uncertainty: Approach by IMHSE Method, Tesis de Magíster, Dpto. Computación e Informática, Universidad de Tarapacá (2005). Hansen, E. R., Global Optimization using Interval Analysis 1º edición, Marcel Dekker, New York, USA (1992). Ichida, K. e Y. Fuji, An interval arithmetic method for global optimization, Computing 23, 85-97 (1979). Jaulin, L., N. Kieffer, O. Didrit y E. Walter, Applied Interval Analysis, Springer-Verlag, London (2001). Khompatraporn, C., J. D. Pinter y Z. B. Zabinsky, Comparative Assessment of Algorithms and Software for Global Optimization, Journal of Global Optimization 31(4), 613-633 (2005) Leclerc, A. P., Efficient and reliable global optimization, Tesis de Doctorado, The Ohio State University (1992). Luenberger, D. E., Programación lineal y no lineal, 1º edición, Addison-Wesley Iberoamericana (1989). Moore, R. E., Interval Analysis", 1º edición, Prentice-Hall, Englewood Cliffs, NJ, Estados Unidos (1966). Moore, R. E., On computing the range of values of a rational function of n variables over a bounded region, Computing 16, 1-15 (1976); Neumaier, A., O. Shcherbina, W. Huyer y T. Vinkó, A comparison of complete global optimization solvers, Mathematical programming 103(2), 335-356 (2005) Neumaier, A. Global Optimization, fecha de consulta 10 de marzo 2006 http://www.mat.univie.ac.at/~neum/glopt.html Pardalos, P. M. y H. E. Romeijn, Handbook of Global Optimization Vol. 2, Kluwer Academic Publishers (2002) Rump, S. M., Algorithm for verified inclusions-theory and practice (1988). Tomado de Hansen, R. E. Global Optimization using Interval Analysis, 1º edición, Marcel Dekker, New York, NY, Estados Unidos, 2-3 (1992) Sahinidis, N. V., Optimization under uncertainty: state-of-the-art and opportunities, Computers and Chemical Engineering 28, 971-983 (2004). Skelboe, S., Computation of rational interval functions, BIT 14, 87-95 (1974). Valdés-González, H, J. M. Flaus y G. Acuña, Moving horizon state estimation with global convergence using interval techniques: application to biotechnological processes, Journal of Process Control 13, 325-336 (2003). Van Iwaarden, R. J., An improved uncons-trained global optimization algorithm, Tesis de Doctorado, University of Colorado at Denver (1996).
Monseñor Subercaseaux 667 La Serena - Chile Tel.: (56-51) 2551158 Fax: (56-51) 2551158  citrevistas@gmail.com |
, se definen según (Moore, 1966) como un conjunto cerrado, acotado y conexo de números reales: 
, 
. Como resultado de un cálculo numérico realizado entre este tipo de números, se obtienen cotas superiores e inferiores para dicho resultado. De acuerdo con lo anterior, para cualquier operación binaria 
, donde 
, 
o 
, y 
son dos intervalos cualquiera, se tiene que (Van Iwaarden, 1996):
debe contener cada número que pueda resultar de 
para cada 
y cada 
. Así, considerando los intervalos 
e 
), las operaciones básicas se definen como: 
) la cota inferior del resultado, y hacia la derecha
) la cota superior. Así, se garantiza que el resultado correcto está entre dichas cotas. Debido a esta propiedad, la aritmética de intervalos ha sido usada para resolver ecuaciones diferenciales ordinarias, sistemas lineales, optimización global, estimación de estados y control de procesos garantizando resultados (ver por ejemplo Hansen, 1992; Leclerc, 1992; Van Iwaarden, 1996; Valdés-González et al., 2003).
, donde 
es el conjunto de los vectores reales por intervalos, es decir, el producto cartesiano de 
intervalos. 
es también llamado caja n-dimensional o hipercubo. Como es lógico, las operaciones básicas vistas anteriormente pueden extenderse a los vectores intervalos definidos en 
es una función de inclusión de la función 
, si 
, 
, 
y 
. De esta manera, una función de inclusión permite la evaluación de una función real a través de aritmética intervalar (Hansen, 1992). Debe notarse que 
no es única, y que cualquier intersección de funciones de inclusión es también una función de inclusión.
por su correspondiente intervalo, y reemplazando cada operación elemental (tal como 
con el correspondiente operador intervalar, obteniendo así la función de inclusión 
es una función continua real (también llamada función objetivo), 
es un conjunto compacto factible donde la función está definida, es decir, es el dominio de 
. El conjunto de todos los puntos para los cuales la función objetivo posee un valor mínimo global es denotado por 
. Este es el conjunto que contiene todos los puntos 
. Este conjunto es comúnmente llamado el conjunto de minimizadores globales.
( 
es el gradiente de la función).
es la función objetivo por intervalos (definida sobre 
, un vector intervalo), tal que 
es un conjunto de restricciones del problema. 
, y luego rechaza aquellas 
). Aquellas 
.
, 
, 
, 
usando aritmética de intervalos. Si se verifica que para algún componente 
del conjunto de restricciones, 
, entonces 
(el punto medio de 
(se debe notar que 
) y 
). Además, si 
es el valor mínimo de 
, es decir, 
es una cota superior para valor mínimo de 
. Sea 
la 
, entonces 
.
.
.
.
.
, y se actualiza 
.
.
, y se actualiza 
, entonces salir.
y 
. La solución de este problema muestra tres curvas continuas desconectadas, con un infinito número de mínimos globales sobre ellas. Estas curvas consisten en arcos del círculo 
. Notar que el círculo unitario completo, 
, corresponde a mínimos locales del problema, los cuales son eliminados por el método de optimización. Sea el espacio de búsqueda para el problema (9), según los requerimientos de (8), definido para 
y 
como 
.
se obtienen 74 cajas en el listado final. Debido a la alta tolerancia dada, el algoritmo de optimización no es capaz de descartar los óptimos locales. Notar que en todo momento los óptimos globales están presentes en el listado de cajas del resultado. 
. Con esta nueva tolerancia de optimización son descartados todos los óptimos locales, quedando 230 cajas en el listado final. Cajas que en su conjunto dan origen a la Smiley Face", lo cual muestra la aplicabilidad general del algoritmo implementado.
y 
. La incertidumbre en el parámetro 
, en tanto que en el parámetro 
. El resultado es mostrado en 
