Resumen

    En el mundo en que vivimos existe una enorme cantidad de problemas de optimización con restricciones prácticamente en todas las áreas del conocimiento. En esta tesis se plantea una mejora a los algoritmos con manejo de restricciones. Esto en sí es una aportación importante debido a su extensa aplicabilidad.

     El modelo matemático de un problema de optimización con restricciones está conformado por una función objetivo, f, y un conjunto de funciones de restricciones de igualdad y desigualdad, h y g, respectivamente. Dichas funciones son funciones escalares de las variables del problema: f : Rn --> R, h : Rn --> R y g : Rn --> R. El subconjunto de todos los puntos que satisfacen las restricciones del problema es llamado región factible.

    El manejo de restricciones es una tarea díficil, en la que las técnicas de programación matemática tienen varias limitaciones, por ejemplo, cuando la función objetivo y/o las restricciones son no diferenciables o discontinuas o no se pueden expresar de manera algebraica, o cuando la región factible es disjunta. Los Algoritmos Evolutivos (AEs) han podido resolver funciones que tienen estas características. Sin embargo, no cuentan con un mecanismo explícito para manejo de restricciones. El problema principal de las técnicas para el manejo de restricciones en los AEs consiste en lograr el balance correcto entre dar prioridad a la minimización del valor de la función objetivo o darle prioridad a la minimización de la violación a las restricciones.

    En esta tesis, se propone  un nuevo criterio de selección entre soluciones candidatas a un problema de optimización con restricciones y se incorpora al algoritmo de Evolución Diferencial (ED). El algoritmo resultante es llamado Evolución Diferencial para Problemas de optimización con Restricciones (EDPR). Dicho algoritmo es comparado contra dos de los AEs más conocidos en la literatura especializada: la jerarquización estocástica y Diversity-DE.

    Finalmente, teniendo como objetivo mejorar los resultados obtenidos con el algoritmo EDPR se propone un algoritmo híbrido basado en el algoritmo EDPR y el método de Nelder-Mead llamado Híbrido de Evolución Diferencial y el método Simplex para Problemas de optimización con Restricciones (HEDSPR). La idea de este híbrido surge del hecho de que los AEs son capaces de lidiar con problemas de optimización complejos que las técnicas clásicas no pueden resolver. Sin embargo, los AEs tienen un costo computacional mucho mayor que las técnicas clásicas. Por tal motivo, se buscó usar el método de Nelder-Mead para acelerar la convergencia a soluciones de buena calidad. Los resultados obtenidos con este algoritmo son comparados contra los resultados del EDPR, evidenciando las ventajas que el híbrido propuesto nos puede ofrecer en algunos casos.

    In the world in which we live, there exist numerous optimization problems, practically in every application domain. Such problems are subject to a number of constraints, since we always aim to find the best solution given a certain set of circunstances. For that reason, during the last few years, several optimization methods have been developed, in order to deal with such different types of problems. However, an improvement to the existing algorithms means an important contribution (due to their wide applicability).

    The mathematical model for an optimization problem with constraints is denoted by an objetive function and a set of equality and inequality constraint functions, h y g, respectively. These functions are scalar functions of the variables of the problem: f : Rn --> R, h : Rn -->  R y g : Rn --> R. The subset of all points that satisfy all constraints is called feasible region.

     Constraint handling is a difficult task in which the mathematical programming techniques have several limitations, for instance, when the objective function and/or the constraints are non-differentiable or discontinuous or when they cannot be expressed in algebraic form, or when the feasible region is disjoint. Evolutionary algorithms (EAs) have been able to solve functions with these features. However, EAs do not have an explicit mechanism for handling constraints. The main problem of constraint handling techniques used with EAs consists of achieving the proper balance between giving priority to the minimization of the objective function value or to the minimization of the constraints violation.

    In this thesis, we propose a new selection criterion for candidate solutions to a constrained optimization problem, and we incorporate to differential evolution (DE) algorithm. The resulting EA is called “Differential Evolution for Constrained Optimization Problems” (DECOP). Such algorithm is compared against two of the most well-known EAs from the specialized literature: stochastic ranking and Diversity-DE.

    Finally, and having as a goal the improvement of the results obtained by our DECOP, we propose a hybrid algorithm based on DECOP and the Nelder-Mead method. This approach is called “Hybrid of Differential Evolution and the Simplex Method for Constrained Optimization Problems” (HDESMCO). Its core idea departs  from the fact that EAs are capable of dealing with complex optimization problems that the classical techniques cannot solve. However, EAs have a much higher computational cost than the classical techniques. Therefore, the intention was to use the Nelder- Mead method to accelerate convergence towards good quality solutions. The results obtained by HDESMCO are compared with respect to the results obtained by DECOP, making evident what are the advantages that the proposed hybrid approach can offer in some cases.