El uso de heurísticas para la solución de problemas de alta complejidad se ha vuelto muy popular en años recientes, debido a su flexibilidad, eficacia y facilidad de uso. Sin embargo, esta popularidad ha propiciado a la vez el desarrollo de una amplia gama de heurísticas para búsqueda y optimización, muchas de las cuales tienen inspiración biológica (p.ej., los algoritmos evolutivos, la optimización mediante cúmulos de partículas, los sistemas inmunes artificiales, la optimización mediante colonias de hormigas, etc.). Tal diversidad de métodos suele provocar confusiones entre aquellos interesados en abordar un problema en particular y son muy pocos los estudios que intenten identificar ventajas o desventajas de una heurística con respecto a otras, en un problema (o clase de problemas) en particular. Un enfoque alternativo para abordar esta problemática es el uso de las hiperheurísticas. El término hiperheurística fue introducido por primera vez por Peter Cowling, y se define como un enfoque que opera en un alto nivel de abstracción y gestiona la elección de una heurística de bajo nivel para ser aplicada en un momento dado, dependiendo de las características de la región del espacio de búsqueda que se esté explorando. La idea clave en las hiperheurísticas es utilizar un conjunto de heurísticas conocidas para transformar el estado de un problema. Esto implica que el usuario no tiene que elegir una heurística en particular para resolver su problema, sino que puede usar una combinación de varias de ellas, buscando combinar sus bondades y compensar las desventajas que algunas de ellas pudieran tener. Pese a sus obvias ventajas, las hiperheurísticas han sido usadas principalmente en optimización combinatoria, y existe poco trabajo en torno a su aplicación en problemas de optimización en los cuales las variables se expresan mediante números reales. Si además el problema tiene restricciones, el uso de hiperheurísticas se torna aún más escaso. En esta tesis se aborda precisamente este tipo de problemas y se propone una nueva hiperheurística basada en variantes de la Evolución Diferencial (ED) para resolver problemas de optimización con restricciones en los cuales las variables son números reales. La principal contribución de esta tesis es un nuevo mecanismo de selección para coordinar los diferentes modelos de Evolución Diferencial incorporados a la hiperheurística propuesta. El nuevo enfoque hiperheurístico aquí propuesto se compara con respecto al algoritmo denominado Constrained Differential Evolution (CDE) o “Evolución Diferencial Restringida”, usando un conjunto de problemas de prueba estándar tomados de la literatura especializada. Los resultados obtenidos indican que la hiperheurística propuesta constituye una alternativa viable para combinar distintos modelos de la Evolución Diferencial para resolver problemas de optimización con restricciones en espacios de búsqueda continuos.
Abstract
The use of heuristics for the solution of high complexity problems has become very popular in recent years, mainly because of their flexibility, efficacy and ease of use. However, this popularity has simultaneously fostered the development of a wide variety of heuristics for search and optimization, many of which have a biological inspiration (e.g., evolutionary algorithms, particle swarm optimization, artificial immune systems, ant colony optimization, etc.). Such a diversity of methods tends to confuse those interested in tackling a particular problem, and there are very few studies that attempt to identify advantages or disadvantages of a metaheuristic with respect to others, in a particular problem (or class of problems). An alternative approach to tackle this problem is the use of hyperheuristics. The term hyperheuristic was originally introduced by Peter Cowling, and is defined as an approach that operates at a high level of abstraction and manages the selection of a low level metaheuristic to be applied at a certain moment, depending on the characteristics of the region of the search space which is being currently explored. The key idea when using hyperheuristics is to use a set of known heuristics in order to transform the state of a problem. This implies that the user does not have to choose one specific metaheuristic to solve his/her problem, but can instead use a combination of several of them, aiming to combine their advantages and to compensate the disadvantages that some of them may have. In spite of their obvious advantages, hyperheuristics have been mainly used in combinatorial optimization, and there is little work regarding their use in optimization problems in which the decision variables are expressed by real numbers. Furthermore, if the problem has constraints, the use of hyperheuristics is even more scarce. In this thesis, we precisely deal with this type of problems, and we propose a new hyperheuristic based on Differential Evolution (DE) variants to solve constrained optimization problems in which the decision variables are real numbers. The main contribution of this thesis is a new selection mechanism to coordinate the different Differential Evolution models incorporated into the proposed hyperheuristic. The new hyperheuristic approach introduced here is compared with respect to an algorithm called Constrained Differential Evolution (CDE), using a set of standard test problems taken from the specialized literature. The obtained results indicate that the proposed hyperheuristic constitutes a viable alternative to combine different Differential Evolution models with the aim of solving constrained optimization problems in continuous search spaces.
