Resolviendo problemas complejos con técnicas metaheurísticas avanzadas

Abstract

Los problemas de optimización complejos, aquellos que no se pueden resolver en tiempo polinomial, están cobrando una mayor notoriedad en la actualidad: telecomunicaciones, bioinformática, planificación, ambientes industriales, etc. En estos y otros campos de investigación, a menudo, es esencial modelar y resolver tareas de optimización, de aprendizaje o de estudio para aplicaciones que no admiten una formulación fácil. En esta clase de problemas, la búsqueda de una solución requiere una exploración organizada a través del espacio de búsqueda. El objetivo de las líneas de investigación, que se vienen desarrollando desde hace más de una década, consiste en aplicar técnicas metaheurísticas a problemas de optimización tanto presentes en el mundo real como aquellos que revisten un carácter teórico pero con aplicaciones en varios campos, analizando distintas posibilidades para sacar el máximo partido a dichas técnicas y ofrecer así soluciones de gran calidad con recursos computacionales al alcance de cualquier institución. Algunos de los problemas seleccionados para estudiar en este proyecto presentan características (conexiones epistáticas entre las variables de decisión, multimodalidad, discontinuidad, dinamismo, etc.) que los hacen interesantes para analizar el comportamiento de distintas propuestas algorítmicas, ya sea cuando se ejecutan en secuencia o en forma distribuida y/o paralela. Otras clases de problemas resultan de interés por la complejidad inherente a su formulación y requieren la propuesta de algoritmos que ofrezcan soluciones de calidad en tiempo de cómputos razonables, tal es el caso de los problemas bioinformáticos y de los problemas dinámicos. Los resultados de esta investigación nos permitirán proporcionar herramientas de software para resolver problemas comunes en la mayoría de las pequeñas y medianas empresas de la región en el sector productivo y en la logística de las mismas. Sin duda, los resultados serán útiles para realizar una transferencia tecnológica a organizaciones de muy distintas características, que necesiten optimizar sus recursos o utilizar nuevas tecnologías.

Optimization problems, those that can not be solved in polynomial time, are becoming more important: telecommunications, bioinformatics, scheduling, industrial environments, etc. Often in these and other areas of research, the modeling and solving of optimization, learning or study tasks for applications that do not support a simple formulation are essential. In this class of problems, finding a solution requires an organized exploration through the search space. The aim of the research, developed for more than a decade, is to apply metaheuristic techniques for optimization problems, present in the real world and in the theoretical field but with applications in several areas. Different possibilities for getting the most appropiate techniques are analyzed, in order to offer high quality solutions with computational resources available to any institution. Some of the problems selected for study in this project have characteristics (epistatic connections among the decision variables, multimodality, discontinuity, dynamism, etc..) that make them interesting in order to analyze the performance of different algorithmic proposals, either when they run in sequence or in a distributed and/or parallel way. Other kinds of problems are interesting due to the complexity in its formulation and the need for algorithms that offer high quality solutions in reasonable computational time, as in the case of bioinformatic and dynamic problems. The results of this research will enable us to provide software tools for solving common problems in most of the small and medium-sized production companies in the region. Certainly, the results will be useful for a technological transfer to organizations of very different characteristics, which need to optimize their resources and to use new technologies.