Departamento de Computación

La optimización numérica tiene una amplia aplicación en diversas disciplinas que modelan problemas del mundo real, como por ejemplo, las mejoras al rendimiento de un sistema, la planeación de procesos, la asignacióin de recursos financieros, el diseño en ingeniería y el desarrollo de modelos. Estos problemas presentan criterios a maximizar o minimizar y/o restricciones que deben ser cumplidas. En la solución de problemas de optimización se toman decisiones mediante la elección sistemática de valores de las variables de decisión, las cuales se definen en un espacio de búsqueda específico. Las restricciones, por su parte, se refieren a que una solución es aceptable sólo si se cumplen ciertas condiciones pre-establecidas por el usuario o por los requerimientos de diseño. Se han desarrollado numerosas técnicas de programaciór matemática para resolver distintos tipos de problemas de optimización. Sin embargo, su uso resulta inadecuado en diversos casos: por ejemplo, cuando las funciones no son diferenciables o presentan discontinuidades, cuando la funcin objetivo es altamente no lineal, cuando el espacio de búsqueda está altamente restringido o cuando la dimensionalidad del problema es muy elevada. Una alternativa para resolver este tipo de problemas son los denominados algoritmos memóticos (AMs), cuyo funcionamiento se basa en la combinación estrat5gica de mecanismos de búsqueda global con mecanismos de búsqueda local. Mientras un mecanismo global explora el espacio completo de búsqueda, el local explota determinadas regiones de Nésreste, a fin de refinar las soluciones obtenidas. La principal contribución de esta tesis es el diseño y la implementación de un algoritmo memóico para la solución de problemas de optimización en espacios restringidos. Este algoritmo se compone de lo siguiente: un mecanismo de búsqueda global basado en evolución diferencial (ED), un método para el manejo de restricciones denominado jerarquías estocsticas (JE) y un procedimiento de búsqueda local que usa el operador de cruza simplex (SPX), el cual explota 2 vecindarios definidos por las *n* mejores y las* n* peores soluciones de cada generación. El algoritmo memótico propuesto es validado usando un conjunto de problemas de prueba estádar tomado de la literatura especializada. Sus resultados se comparan con respecto a los de cuatro algoritmos representativos del estado del arte en el área. Así mismo, se realiza un análisis estadístico de resultados, empleando el anáisis de varianza (ANOVA) y un méodo de remuestreo (*bootstrap*). Los resultados obtenidos indicaron que el algoritmo memótico propuesto fue el que encontrób los mejores resultados al conjunto de pruebas adoptado, presentando además un comportamiento robusto.

Abstract

Numerical optimization has a wide applicability in a variety of disciplines that model real-world problems, such as performance improvements of a system, process planning, financial resources assignment, engineering design and model development. These problems have criteria to be maximized or minimized and/or constraints that must be satisfied. When solving optimization problems, decisions are made through thesystematic selection of values of the decision variables, which define a specific search space. Constraints, on the other hand, refer to considering a solution as acceptable, only if it fulfills certain conditions that are pre-established by the user of by the design requirements.