Project topics and materials
Get Complete Project Material File(s) Now! »
Multi-objective Metaheuristics
Metaheuristics are high-level algorithms designed to quickly find good solutions for a large range of optimisation problems too difficult for exact algorithms. In-deed, many combinatorial optimisation problems are NP-hard with an number of possible solutions growing exponentially, therefore requiring approximation mechanisms in order to obtain high-quality solutions in a reasonable amount of time. However, approximation algorithms do not guaranty the optimality of the final solutions. Exact algorithms can nevertheless be used to get optimal solutions, either on small instances or sub-problems, or after reduction of the problem size. Metaheuristics can be classified into nature-inspired and local search algorithms. While the former generally involve evolution, culture, or group characteristics to simultaneously evolve multiple solutions together, the latter focus more on intensi-fying individual solutions by intensifying the search on similar solutions. In the following, we present some of the more common multi-objective metaheuristics.
Nature-inspired Algorithms
Nature-inspired algorithms, or bio-inspired algorithms, are generally inspired by biological processes, and based on abstract concepts such as evolution, environ-mental pressure, and natural selection (survival of the fittest), as well as on con-crete observations such as animal behaviour modelling. The most well known include evolutionary algorithms (EA’s) such as the genetic algorithm (GA, Hol-land, 1992), swarm algorithms such as the particle swarm optimisation algorithm (PSO, Kennedy and Eberhart, 1995) and ant colony optimisation algorithms (ACO, Dorigo et al., 1996).
As for multi-objective nature-inspired algorithms, the most popular are nowa-days recent variants based on the MOEA/D (Zhang and Li, 2007), a multi-objective EA based on decomposition; NSGA-II (Deb et al., 2000, 2002), a non-dominated sorting GA; SPEA2 (Zitzler and Thiele, 1999; Zitzler et al., 2001), a strength Pareto EA; and IBEA (Zitzler and Künzli, 2004), an indicator-based EA. The reader is re-ferred to Coello et al. (2007) or Deb (2001) for more in-depth presentations of many multi-objective population-based and evolutionary algorithms. We note in particular the existence of the MOACO framework (López-Ibáñez and Stützle, 2010a,b), which specifically provides a general multi-objective ant colony optimisation framework to use with automatic design tools. It is able to in-stantiate most of the multi-objective ACO algorithms from the literature and many combinations of components yet never investigated.
Local Search Algorithms
Local search (LS) algorithms exploit the structure of the search space to iteratively find better and better solutions. They are based on the idea that small modifica-tions in the representation of a solution may lead to either a small improvement or a small deterioration of its initial quality, leading to the notion of neighbourhood, that gives a structure to the search space by connecting close solutions. This notion is often called the proximate optimality principle (e.g., Glover and Laguna, 1997). LS algorithms are originally very efficient metaheuristics designed for single-objective problems (Hoos and Stützle, 2004). They have been adapted for multi-objective problems in various ways, either directly extended from well-known and established single-objective algorithms (e.g., Serafini, 1994; Ulungu et al., 1995; Czyzak and Jaszkiewicz, 1996; Hansen, 1997), or hybridised with and within evol-utionary algorithms (e.g., Ishibuchi and Murata, 1996; Knowles and Corne, 1999; Talbi et al., 2001).
Performance Assessment
The use of Pareto-based multi-objective algorithms leads to fronts of final solu-tions. In order to compare the performance of such algorithms, it is then necessary to be able to quantify the quality of Pareto sets.
Overview
Several characteristics of Pareto sets can be measured. Through the use of the many performance indicators proposed in the literature (Knowles and Corne, 2002; Okabe et al., 2003), three main properties of Pareto can be assessed: accuracy, di-versity, and cardinality. Accuracy: the front of solutions is close to the theoretical Pareto optimal front, either by volume or distance. Diversity: the solutions of the front are either well-distributed or well-spread. Cardinality: the front contains a large number of high-quality solutions. According to a recent survey (Riquelme et al., 2015), the most commonly used performance indicators in the literature are the following. Hypervolume (HV): (accuracy, diversity) based on the volume of the search space that contains dominated solutions (Zitzler and Thiele, 1999); Generational distance (GD): (accuracy) based on the distance of the solutions of the front to the solutions of a reference front (van Veldhuizen and Lamont, 2000); Epsilon family (ε): (all) based on the minimum factor ε (additive or multiplicat-ive) by which the front is worse than a reference front regarding all objectives (Zitzler et al., 2003); Inverted generational distance (IGD): (accuracy, diversity) similar to GD, based on the distance of the solutions of a reference front to the solutions of the given front (Coello and Cortés, 2005); Spread (∆): (diversity) based on the distribution and spread achieved among the solutions (Deb et al., 2002); Two set coverage (C): (all) based on the fraction of solutions of the front domin-ated by at least one solution of a reference front (Zitzler and Thiele, 1998). It was shown that it is generally not possible to aggregate all of these properties into a single indicator; it is thus recommended to consider multiple performance indicators, preferably ones that complement each other, in order to assess the effi-ciency multi-objective optimisation algorithms fairly (Zitzler et al., 2003). In prac-tice, the hypervolume indicator (Zitzler and Thiele, 1999) is by far the indicator the most commonly used in the multi-objective literature, while the other indicators are much less used. Finally, multi-objective performance indicators are either binary metrics, that compare two different sets of solutions (e.g., one set of solution with a reference set or a reference point), or unary metrics, that are able to give independent quality assessment. In the following, we present in more detail the hypervolume indicator and the ∆ spread indicator, that will be used in the experiments of this thesis. These two specific indicators have been chosen first because they are unary performance in-dicators, a restriction of the current automatic algorithm configurators; they are also well known and used in the literature, and the spread enable to more expli-citly consider diversity, as hypervolume is first and foremost an indicator focused on accuracy.
Permutation Flow Shop Scheduling Problem
The permutation flow shop scheduling problem (PFSP) is a classical combinatorial optimisation problem, and one of the best-known problems in the scheduling liter-ature since it models several typical problems in manufacturing. It involves a set of n jobs {J1, . . . , Jn} that need to be scheduled on a set of m machines {M1, . . . , Mm}. Each job Jk need to be processed sequentially on each of the m machines, with fixed processing times (pk,1, . . . , pk,m). Finally, machines are critical resources that can only process a single job at a time. For the permutation flow shop scheduling problem, each machine process the jobs in the same order, so that a solution may be represented by a permutation of size n. The completion times Ci,j for each job on each machine for a given permutation π = (π1, . . . , πn) are computed using Equation 1.8 to Equation 1.11.
Multi-objective Automatic Design
All of the notions presented before were originally proposed as single-objective tools, to optimise the performance of single-objective algorithms. In order to apply such tools to multi-objective algorithms, one would need to use a single perform-ance indicator, such as the hypervolume resulting of the final set of solutions (e.g., Dubois-Lacoste et al., 2011a).
However, the last few years have seen the development of many different tools either based on multi-objective optimisation or specifically designed for multi-objective optimisation. Among others, we can cite MOSAP (Horn et al., 2016), a multi-objective algorithm selection framework, S-Race and SPRINT-Race (Zhang et al., 2015, 2016, 2018), extending statistical racing for model selection according to multiple criteria, and MO-ParamILS (Blot et al., 2016), a multi-objective con-figurator for multi-objective configuration we proposed. MO-ParamILS will be presented and studied in depth in Chapter 5.
Overall Automatic Design Taxonomy Proposition
In this section, we propose a new taxonomy of automatic algorithm design. It follows and expends the temporal viewpoint already present in the Hamadi et al. (2012) taxonomy, while proposing a second, transverse, viewpoint based on the algorithmic structure of the elements being optimised. An important motive for this taxonomy is to propose a taxonomy for researchers focused on the design tools and techniques themselves, as autonomous search systems focus more to giving an autonomous black-box to non-technical end-users.
Temporal Viewpoint
The first point of view of our taxonomy is based on when are applied the algorithm design tools. Eiben et al. (1999), then Hamadi et al. (2012), separate tools that are applied before and after the first actual computational step on the given problem instance. Tools that are used to choose an algorithm and its parameters are classi-fied as offline tools, while techniques used to adapt the algorithm or its strategies during the execution are classified as online techniques.
We propose to distinguish three phases in this timeline, rather than only two. First, we have tools that only require a description of the problems and the classes of instances that will be tackled, such as the learning process of algorithm selection and parameter tuning. More precisely, they do not require to know the specific in-stance that will be solved in the future, and they are used to obtain generalisations and to give predictions. We say that they only use problem features. Then, we have tools or recommendations that use the specific features of the instance to solve. For example, the application of the mapping found using al-gorithm selection, or more generally the choice of parameter values following the algorithm designer recommendations (e.g., parameters with recommended values depending of the instance size). We say that they use a priori features. Finally, following Eiben et al. (1999), the last phase begins when the first com-putational step starts the search. Search features, directly linked to the algorithm progression and the solutions considered, are then available to be used.
One of the advantages of separating the online phase into two distinct phases is first to better compare algorithm configuration to algorithm selection, as it splits the latter into two parts the machine learning first, then the application of the resulting mapping. Furthermore, it also enables to better include recommenda-tions and rules based on manual preliminary experiments or simply intuition, that wouldn’t otherwise be considered as not suitable as generic design tools.
Table of contents :
General Introduction
Motivations
Outline
I Multi-objective Optimisation and Algorithm Design
1 Multi-objective Metaheuristics
1.1 Multi-objective Combinatorial Optimisation
1.1.1 Introduction
1.1.2 Definition
1.1.3 Solution Comparison
1.1.4 Multi-objective Metaheuristics
1.2 Performance Assessment
1.2.1 Overview
1.2.2 Hypervolume
1.2.3 Δ Spread
1.3 Permutation Problems
1.3.1 Permutation Flow Shop Scheduling Problem
1.3.2 Travelling Salesman Problem
1.3.3 Quadratic Assignment Problem
2 Automatic Algorithm Design
2.1 Preliminaries
2.2 Overview
2.2.1 Algorithm Selection
2.2.2 Algorithm Configuration / Parameter Tuning
2.2.3 Parameter Control
2.2.4 Hyper-heuristics
2.2.5 Other Fields and Taxonomies
2.2.6 Multi-objective Automatic Design
2.3 Overall Automatic Design Taxonomy Proposition
2.3.1 Temporal Viewpoint
2.3.2 Structural Viewpoint
2.3.3 Overview
2.3.4 Additional Complexity Viewpoint
II Multi-objective Local Search
3 Unified MOLS Structure
3.1 Preliminaries
3.1.1 Definitions
3.1.2 Historical Development
3.1.3 Condensed Literature Summary
3.1.4 Analysis and Discussion
3.2 MOLS Strategies
3.2.1 Set of Potential Pareto Optimal Solutions (Archive)
3.2.2 Set of Current Solutions (Memory)
3.2.3 Exploration Strategies
3.2.4 Selection Strategies
3.2.5 Termination Criteria
3.3 Escaping Local Optima
3.4 MOLS Unification Proposition
3.4.1 Main Loop
3.4.2 Local Search Exploration
3.4.3 Iterated Local Search Algorithm
3.5 Literature Instantiation
4 MOLS Instantiations
4.1 Static MOLS Algorithm
4.1.1 Algorithm
4.1.2 Configuration Space
4.2 Control Mechanisms Integration
4.2.1 Parameter Analysis
4.2.2 Knowledge Exploitation
4.2.3 Knowledge Extraction
4.2.4 Knowledge Modelling
4.2.5 Decisional Schedule
4.3 Adaptive MOLS Algorithm
4.3.1 Algorithm
4.3.2 Related adaptive MOLS Algorithms
4.4 Configuration Scheduling
4.4.1 Proposition
4.4.2 Definitions
4.4.3 Related Approaches
4.5 AMH: Adaptive MetaHeuristics
4.5.1 Motivation
4.5.2 Philosophy
4.5.3 Design and Implementation
4.5.4 Execution Flow Examples
4.6 Perspectives
III Automatic Offline Design
5 MO-ParamILS
5.1 Multi-objective Automatic Configuration
5.1.1 Definition
5.1.2 Use Cases
5.2 Single-objective ParamILS
5.2.1 Core Algorithm
5.2.2 BasicILS, FocusedILS
5.2.3 Adaptive Capping Strategies
5.2.4 Configuration Protocol
5.3 Multi-objective ParamILS
5.3.1 Motivations
5.3.2 Core Algorithm
5.3.3 Configuration Protocol
5.4 Hybrid Multi-Objective Approaches
5.4.1 Single Performance Indicator
5.4.2 Aggregation of Multiple Performance Indicators
5.5 Framework Evaluation
5.5.1 Experimental Protocol
5.5.2 Results
5.6 Perspectives
6 MOLS Configuration
6.1 Exhaustive Analysis
6.1.1 Experimental Protocol
6.1.2 Parameter Distribution Analysis
6.1.3 Optimal Configurations
6.1.4 Discussions
6.2 AAC Approaches Analysis
6.2.1 Experimental Protocol
6.2.2 Small Configuration Space Results
6.2.3 Large Configuration Space Results
6.2.4 Discussions
6.3 Analysis of Objective Correlation
6.3.1 Experimental Protocol
6.3.2 Optimised Configurations
6.3.3 Discussions
6.4 Perspectives
IV Automatic Online Design
7 MOLS Control
7.1 Adaptive MOLS Algorithm
7.1.1 Adaptive Algorithm
7.1.2 Generic Online Mechanisms
7.2 Experimental Protocol
7.3 Experimental Results
7.3.1 3-arm Results
7.3.2 2-arm Results
7.3.3 Long Term Learning Results
7.4 Discussions
7.5 Perspectives
8 MOLS Configuration Scheduling
8.1 MOLS Configurations
8.2 Experimental Protocol
8.3 Experimental Results
8.3.1 Exhaustive Enumeration
8.3.2 K = 2 Configuration Schedules
8.3.3 K = 3 Configuration Schedules
8.4 Discussions
8.5 Perspectives
General Conclusion
Contribution Summary
Future Research
Publications
Bibliography
