Back to results

University of Ioannina

New approaches in parallel algorithm portfolios for metaheuristic optimization

Abstract

dc:description

Optimization 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

Rights

dc:rights
Statement dc:rights
  • BY_NC_ND
Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/43248

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Souravlias, Dimitrios; Σουραβλιάς, Δημήτριος. New approaches in parallel algorithm portfolios for metaheuristic optimization. University of Ioannina, 2017. http://hdl.handle.net/10442/hedi/43248