University of Ioannina
New approaches in parallel algorithm portfolios for metaheuristic optimization
Abstract
dc:descriptionOptimization problems are ubiquitous in science and engineering. Their plethora and diversity have offered ample ground for the development of numerous optimization methods, leading to an increasing expansion of the available algorithmic artillery. However, both theoretical and experimental evidence suggest that the existence of a universal optimization algorithm capable of tackling all optimization problems equally well is highly improbable. Thus, the ability to identify the most appropriate algorithm eventually determines the boundary between success and failure when challenging optimization problems are confronted. A crucial decision in solving optimization problems is the selection of an appropriate optimization algorithm. This is a non-trivial task and usually requires deep knowledge of the problem and experience from the practitioner's side. Whenever the available information on the problem is limited, preliminary experimentation is needed for the selection of the most promising algorithm among a set of candidates through a trial-and-error procedure. This phase is error-prone as well as time-consuming. In fact, it may require more time than the solution of the problem itself due to the computational intensity of the involved statistical methodologies. Moreover, it does not take directly into consideration the online dynamic of each algorithm, i.e., its performance fluctuations during execution. Algorithm Portfolios were proposed as models that combine a number of algorithms into a joint algorithmic framework. Their constituent algorithms are either interchangeably executed on a single processing unit or run concurrently on multiple processors, according to a prescribed resources allocation plan. This plan is usually determined prior to the portfolio’s application based on preliminary experiments or historical performance data of the algorithms. However, the assignment of predefined portions of computational resources may be inefficient, since it neglects the online dynamic of the constituent algorithm. In such cases, the dynamic allocation of resources during the execution of the portfolio can be highly beneficial. The main goals of the dissertation are the justification of the use of metaheuristic algorithm portfolios in demanding optimization problems of various types, and the development of new parallel algorithm portfolio models with adaptive resources allocation plans. Firstly, motivation for the use of algorithm portfolios is provided. The impact of appropriate computational budget allocation in contemporary metaheuristics is identified, and two simplistic parallel algorithm portfolio models are introduced. The first one can be used with any optimization algorithm and it is demonstrated on the design of bijective S-boxes, which is an important problem in cryptography. The second model is suitable for population-based algorithms and it is demonstrated on the traffic light scheduling problem. Secondly, two new parallel algorithm portfolio models with sophisticated resources allocation mechanisms are proposed. The first model defines an algorithm portfolio with trading-based budget allocation, which introduces a market-based environment where the constituent algorithms of the portfolio can trade their solutions for additional running time. The model is autonomous and allows the algorithms to individually interact whenever specific conditions (e.g., search stagnation) are met. It is demonstrated on three challenging problems, namely the detection of circulant weighing matrices in combinatorics, the lot-sizing planning in production environments with returns and remanufacturing, and the transportation of commodities in humanitarian logistics. The second proposed model is a forecasting-based parallel algorithm portfolio where time series forecasting techniques are employed to predict the performance of its constituent algorithms. The predictions are used to assign computational resources to the constituent algorithms, accordingly. The model is demonstrated on the detection of circulant weighing matrices in combinatorics.
Degree
thesis:*- Grantor dc:publisher
- University of Ioannina
- Year dc:date
- 2017
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Souravlias, Dimitrios
- Σουραβλιάς, Δημήτριος
Subjects
dc:subject × 15- Παράλληλα χαρτοφυλάκια αλγορίθμων
- Μεταευρετικοί αλγόριθμοι
- Υπολογιστική βελτιστοποίηση
- Parallel algorithm portfolios
- Metaheuristic
- Algorithms
- Computational optimization
- Φυσικές Επιστήμες
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Επιστήμες Μηχανικού και Τεχνολογία
- Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ
- Natural Sciences
- Computer and Information Sciences
- Engineering and Technology
- Electrical Engineering, Electronic Engineering, Information Engineering
Rights
dc:rights- Statement dc:rights
-
- BY_NC_ND
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/43248