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

Author

Cutillas Lozano, José Matías

Director

Giménez Cánovas, Domingo

Date of defense

2014-09-24

Pages

208 p.



Department/Institute

Universidad de Murcia. Departamento de Informática y Sistemas

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


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

Algoritmos; 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

Subjects

510 - Fundamental and general considerations of mathematics; 62 - Engineering. Technology in general

Knowledge Area

Ciencias

Documents

TJMCL.pdf

1.525Mb

 

Rights

ADVERTENCIA. El acceso a los contenidos de esta tesis doctoral y su utilización debe respetar los derechos de la persona autora. Puede ser utilizada para consulta o estudio personal, así como en actividades o materiales de investigación y docencia en los términos establecidos en el art. 32 del Texto Refundido de la Ley de Propiedad Intelectual (RDL 1/1996). Para otros usos se requiere la autorización previa y expresa de la persona autora. En cualquier caso, en la utilización de sus contenidos se deberá indicar de forma clara el nombre y apellidos de la persona autora y el título de la tesis doctoral. No se autoriza su reproducción u otras formas de explotación efectuadas con fines lucrativos ni su comunicación pública desde un sitio ajeno al servicio TDR. Tampoco se autoriza la presentación de su contenido en una ventana o marco ajeno a TDR (framing). Esta reserva de derechos afecta tanto al contenido de la tesis como a sus resúmenes e índices.

This item appears in the following Collection(s)