Section: New Results

Fitness Landscape Analysis for Algorithm Understanding, Selection, Design and Configuration

Participants: Bilel Derbel, Arnaud Liefooghe (external collaborators: Sebastien Verel, Univ. Littoral, France; Hernan Aguirre, Fabio Daolio, Hugo Monzón, Miyako Sagawa and Kiyoshi Tanaka, Shinshu University, Japan)

Fitness landscape analysis of Pareto local search on bi-objective permutation flowshop scheduling problems. In [20], we study the difficulty of solving different bi-objective formulations of the permutation flowshop scheduling problem by adopting a fitness landscape analysis perspective. Our main goal is to shed the light on how different problem features can impact the performance of Pareto local search algorithms. Specifically, we conduct an empirical analysis addressing the challenging question of quantifying the individual effect and the joint impact of different problem features on the success rate of the considered approaches. Our findings support that multi-objective fitness landscapes enable to devise sound general-purpose features for assessing the expected difficulty in solving permutation flowshop scheduling problems, hence pushing a step towards a better understanding of the challenges that multi-objective randomized search heuristics have to face.

Landscape-aware automatic algorithm configuration. The proper setting of algorithm parameters is a well-known issue that gave rise to recent research investigations from the (offline) automatic algorithm configuration perspective. Besides, the characteristics of the target optimization problem is also a key aspect to elicit the behavior of a dedicated algorithm, and as often considered from a landscape analysis perspective. In [21], we show that fitness landscape analysis can open a whole set of new research opportunities for increasing the effectiveness of existing automatic algorithm configuration methods. Specifically, we show that using landscape features in iterated racing both (i) at the training phase, to compute multiple elite configurations explicitly mapped with different feature values, and (ii) at the production phase, to decide which configuration to use on a feature basis, provides significantly better results compared against the standard landscape-oblivious approach. Our first experimental investigations on NK-landscapes, considered as a benchmark family having controllable features in terms of ruggedness and neutrality, and tackled using a memetic algorithm with tunable population size and variation operators, show that a landscape-aware approach is a viable alternative to handle the heterogeneity of (black-box) combinatorial optimization problems.

Learning variable importance to guide recombination on many-objective optimization. There are numerous many-objective real-world problems in various application domains for which it is difficult or time-consuming to derive Pareto optimal solutions. In an evolutionary algorithm, variation operators such as recombination and mutation are extremely important to obtain an effective solution search. In [25], we study a machine learning-enhanced recombination that incorporates an intelligent variable selection method. The method is based on the importance of variables with respect to convergence to the Pareto front. We verify the performance of the enhanced recombination on benchmark test problems with three or more objectives using the many-objective evolutionary algorithm AϵSϵH as a baseline algorithm. Results show that variable importance can enhance the performance of many-objective evolutionary algorithms.

Closed state model for understanding the dynamics of multi-objective evolutionary algorithms. In [22], we propose the use of simple closed state models to capture, analyze and compare the dynamics of multi- and many-objective evolutionary algorithms. Two- and three-state models representing the composition of the instantaneous population are described and learned for representatives of the major approaches to multi-objective optimization, i.e. dominance, extensions of dominance, decomposition, and indicator algorithms. The model parameters are trained from data obtained running the algorithms with various population sizes on enumerable MNK-landscapes with 3, 4, 5 and 6 objectives. We show ways to interpret and use the model parameter values in order to analyze the population dynamics according to selected features. For example, we are interested in knowing how parameter values change for a given population size with the increase of the number of objectives. We also show a graphical representation capturing in one graph how the parameters magnitude and sign relate to the connections between states.