Modelado y autooptimización de metaheurísticas e hiperheurísticas parametrizadas paralelas aplicadas a problemas de optimización en ciencias e ingeniería

Abstract

En este trabajo se estudia la aplicación de esquemas parametrizados paralelos de metaheurísticas e hiperheurísticas a problemas de optimización en ciencias e ingeniería. Un objetivo a conseguir es la aplicación eficiente de estos métodos, por lo que es necesario el uso de modelos que permitan su autooptimización durante la ejecución a través de la selección adecuada de parámetros característicos del sistema computacional y del paradigma de paralelismo empleado. La utilización de un esquema parametrizado de metaheurísticas permite aplicar fácilmente diferentes metaheurísticas a problemas de optimización, simplemente modificando algunos parámetros metaheurísticos. Además, puesto que muchos de estos problemas tienen una elevada carga computacional se hace indispensable la introducción de paralelismo en el esquema. Así, se consideran dos paradigmas que pueden ser complementarios: paralelismo local de memoria compartida y paralelismo global de paso de mensajes. El uso de algoritmos paralelos persigue un objetivo claro: la reducción del tiempo de ejecución, suponiendo un enfoque diferente para la resolución de los problemas de optimización. Debido a que obtener una buena metaheurística para un problema de optimización concreto puede ser un proceso costoso, se aporta también como novedad el desarrollo de hiperheurísticas basadas en esquemas metaheurísticos parametrizados, entendidas como algoritmos de más alto nivel cuya finalidad es la selección automática de la mejor metaheurística para un problema o conjunto de problemas dados. Como la estructura de las hiperheurísticas se basa en el esquema parametrizado de metaheurísticas, se puede considerar en este caso la misma metodología de modelado y autooptimización, pero a un nivel superior de abstracción. La aplicación de las hiperheurísticas basadas en un esquema metaheurístico paralelo con un modelo teórico del tiempo de ejecución permite una selección automática de los parámetros de paralelismo óptimos, dando como resultado algoritmos eficientes tanto en calidad de los resultados como en rapidez en alcanzarlos.

PALABRAS CLAVE: minimización de coste eléctrico, optimización de constantantes cinéticas, autooptimización, esquemas metaheurísticos parametrizados, hiperheurísticas, modelado de esquemas metaheurísticos paralelos, esquemas metaheurísticos en memoria compartida, esquemas metaheurísticos de paso de mensajes, computación heterogénea.

TÉRMINOS TESAURO: 120300 CIENCIA DE LOS ORDENADORES

CLASIFICACIÓN UNESCO: 120300 CIENCIA DE LOS ORDENADORES

ABSTRACT

In this work the application of parallel parameterized schemes of metaheuristics and hyperheuristics to optimization problems in science and engineering is studied. One goal is the efficient application of these methods, so it is necessary to use models that allow method auto-tuning during the execution through the proper selection of the characteristic parameters of parallelism and of the computer system used. The use of a parameterized metaheuristic scheme allows the easy application of different metaheuristics to optimization problems, simply by modifying some metaheuristic parameters. Furthermore, since many of these problems have a high computational cost, the introduction of parallelism in the scheme is indispensable. Thus, we consider two complementary paradigms: local shared-memory parallelism and global message-passing parallelism. The use of parallel algorithms pursues a clear objective: to reduce the execution time by assuming a different approach for solving the optimization problems. Because getting a good metaheuristic for a specific optimization problem can be a costly process, the development of hyperheuristics based on parameterized metaheuristic schemes is an advance. A hyperheuristic can be understood as an algorithm of higher level whose purpose is the automatic selection of the best metaheuristic for a given problem or set of problems. As the hyperheuristic structure is based on the parameterized metaheuristic scheme, the same modeling and auto-tuning methodology can be considered in this case, but at a higher level of abstraction. Applying the hyperheuristics based on a parallel metaheuristic scheme with a theoretical model of the execution time allows automatic selection of optimal parallelism parameters, resulting in an efficient algorithm both in quality of the results and in speed of achieving them.

KEYWORDS: electrical cost minimization, kinetic constants optimization, auto-tuning, parameterized metaheuristic schemes, hyperheuristics, parallel metaheuristic schemes modelling, shared-memory metaheuristic schemes, message-passing metaheuristic schemes, heterogeneous computing.