Fitness landscape analysis provides insights into optimization problems, informing algorithms' design and identifying properties that influence performance. While understanding global landscape structure is critical, tools for analyzing and visualizing multi-objective, high-dimensional optimization problems remain limited. Recent models, such as Pareto local optima solution networks (PLOS-nets), primarily focus on small instances and binary representations, posing challenges for extension to more complex domains. To address this gap, we introduce mo-LON/D, a decomposition-based local optima network model for multi-objective landscapes. This model partitions a multi-objective problem into scalar sub-problems, constructs standard single-objective local optima networks (LONs) for each, and integrates them via a graph union. We validate mo-LON/D on fully enumerated bi-objective ρmnk-landscapes and contrast its structural features against PLOS-nets both visually and quantitatively. Despite the inherent sampling involved in scalarization, our results indicate that mo-LON/D offers comparable explanatory power (and even higher correlations) with respect to the performance of state-of-the-art algorithms. By harnessing established sampling techniques from single-objective research, mo-LON/D could potentially provide a scalable framework for characterizing complex multi-objective landscapes.

Local Optima Networks (LON)s have been used extensively to understand the global structure of optimisation problems and to study algorithm behaviour. The central idea is to compress the search space into a graph object capturing the local optima along with information on their basins of attraction and the connections between them. This enables the visualisation of high dimensional search spaces, and the extraction of metrics for characterising and contrasting different problem instances. In this paper we extend the canonical LON definition to encompass search spaces with constraints. We use a well-known pairwise comparison operator for constrained problems, and capture the features of the constraint violation landscape that present a challenge for such an operator, such as infeasible local traps. The concept of a constrained LON is illustrated through a range of problem instances. Most problems in the context of real-world applications have constraints. By including the notion of feasibility and constraint violation into the definition of LONs, it becomes possible to use this powerful analysis tool on a much wider range of real-world problems.

We present a simple neighborhood search that aims at efficiently approximating the Pareto set of particularly difficult multiobjective combinatorial optimization problems. Unlike (eli-tist) local search which exclusively accepts improving neighbors, the proposed walk explores a subset of$\lambda$neighbors only, among which the best one is accepted, whether it improves the current solution or not. This resembles the comma-selection from evolutionary computation, which is to contrast with the plus-selection. This principle was shown to better escape basins of attraction in the context of single-objective optimization. Non-elitism has also been recently revised in the context of multiobjective optimization. However, we emphasize that we do not generate random offspring here. Instead, we create a whole set of$\lambda$neighbors among which one is carefully selected, thus providing better control of the selection pressure. In order to extend the partial neighborhood walk principles to multiobjective search, we rely on decomposition: multiple scalarizing subproblems are uniformly defined and optimized (independently or cooperatively) in order to form a whole approximation set. Based on a benchmark of difficult NK-landscapes with two and three objectives, we show that even independent sub-problem solving results in a clear improvement over more advanced multiobjective decomposition approaches such as MOEA/D. We further report an in-depth analysis of the neighborhood sample size, the number of sub-problems, and the cooperation among them.

Multi-objectivization transforms a single-objective optimization problem into a multi-objective one in order to facilitate the search for high-quality solutions with respect to the original target objective. This paper focuses on the multi-objectivization strategy of adding a helper objective. Depending on its definition, the helper objective might have a positive or negative impact on optimization. For multi-objectivization to work well, it is essential to select the helper objective with care, according to the nature of the target objective. However, the design of this helper objective remains unclear: should it be completely independent of the target objective or, by contrast, correlated in some respects? We propose and analyze different methods for generating helper objectives with varying degrees of correlation to the target objective, with the aim of guiding the setting of multi-objectivization. Inspired by existing works on multi-objective NK landscapes, we are particularly interested in the joint setting of the correlation between objective-values and the similarity of variable interactions on both objectives. We approximately decompose the target function into several sub-functions based on the Walsh transform. The proposed method combines these sub-functions to create helper objectives with different levels of correlation and heterogeneity. By analyzing bi-objective instances made of a target and of a helper objective under different definitions, we gain insights into the selection of helper objectives depending on the target objective. Our experimental findings suggest that a helper objective with a positive correlation and a smoother landscape is beneficial for multi-objectivization.

The hardness of the Unconstrained Binary Quadratic Program (UBQP) problem is due its rugged landscape. Various algorithms have been proposed for UBQP, including the Landscape Smoothing Iterated Local Search (LSILS). Different from other UBQP algorithms, LSILS tries to smooth the rugged landscape by building a convex combination of the original UBQP and a toy UBQP. In this paper, our study further investigates the impact of smoothing rugged landscapes using different toy UBQP problems, including a toy UBQP with matrix$\hat{\boldsymbol{Q}}^{1}$(construct by “$+/-1$‘), a toy UBQP with matrix$\hat{\boldsymbol{Q}}^{2}$(construct by “$+/-\mathrm{i}$’) and a toy UBQP with matrix$\hat{\boldsymbol{Q}}^{3}$(construct randomly). We first assess the landscape flatness of the three toy UBQPs. Subsequently, we test the efficiency of LSILS with different toy UBQPs. Results reveal that the toy UBQP with$\hat{\boldsymbol{Q}}^{1}$(construct by “$+/-1$”) exhibits the flattest landscape among the three, while the toy UBQP with$\hat{Q}^{3}$(construct randomly) presents the most non-flat landscape. Notably, LSILS using the toy UBQP with$\hat{\boldsymbol{Q}}^{2}$(construct by “$+/\cdot \mathbf{i})$emerges as the most effective, while$\hat{\boldsymbol{Q}}^{3}$(construct randomly) has the poorest result. These findings contribute to a detailed understanding of landscape smoothing techniques in optimizing UBQP.

The design of automated landscape-aware techniques requires low-cost features that characterize the structure of the target optimization problem. This paper approximates network-based landscape models of multi-objective optimization problems, which were constructed by full search space enumeration in previous studies. Specifically, we propose a sampling method using dominance-based local search for constructing an approximation of the Pareto local optimal solution network (PLOS-net) and its variant, the compressed PLOS-net. Both models are valuable to visualize and compute features on the distribution of Pareto local optima. We conduct experiments with multi-objective nk-landscapes and compare the features of full-enumerated PLOS-nets with that of approximate PLOS-nets. We analyze the correlation between landscape features and the performance of well-established multi-objective evolutionary and local search algorithms. Our results show that approximated networks can predict algorithm performance and provide recommendation for algorithm selection with the same level of accuracy, even though they are much more computationally affordable compared to full-enumerated networks. We finally illustrate how the approximate PLOS-net scale to large-size instances.

It is a common held assumption that problems with many objectives are harder to optimize than problems with two or three objectives. In this paper, we challenge this assumption and provide empirical evidence that increasing the number of objectives tends to reduce the difficulty of the landscape being optimized. Of course, increasing the number of objectives brings about other challenges, such as an increase in the computational effort of many operations, or the memory requirements for storing non-dominated solutions. More precisely, we consider a broad range of multi- and many-objective combinatorial benchmark problems, and we measure how the number of objectives impacts the dominance relation among solutions, the connectedness of the Pareto set, and the landscape multimodality in terms of local optimal solutions and sets. Our analysis shows the limit behavior of various landscape features when adding more objectives to a problem. Our conclusions do not contradict previous observations about the inability of Pareto-optimality to drive search, but we explain these observations from a different perspective. Our findings have important implications for the design and analysis of many-objective optimization algorithms.

The structure of local optima in multi-objective combinatorial optimization and their impact on algorithm performance are not yet properly understood. In this paper, we are interested in the representation of multi-objective landscapes and their multi-modality. More specifically, we revise and extend the network of Pareto local optimal solutions (PLOS-net), inspired by the well-established local optima network from single-objective optimization. We first define a compressed PLOS-net which allows us to enhance its perception while preserving the important notion of connectedness between local optima. We then study an alternative visualization of the (compressed) PLOS-net that focuses on good-quality solutions, improves the distinction between connected components in the network, and generalizes well to landscapes with more than 2 objectives. We finally define a number of network metrics that characterize the PLOS-net, some of them being strongly correlated with search performance. We visualize and experiment with small-size multiobjective nk-landscapes, and we disclose the effect of PLOS-net metrics against well-established multi-objective local search and evolutionary algorithms.

The design of effective features enabling the development of automated landscape-aware techniques requires to address a number of inter-dependent issues. In this paper, we are interested in contrasting the amount of budget devoted to the computation of features with respect to: (i) the effectiveness of the features in grasping the characteristics of the landscape, and (ii) the gain in accuracy when solving an unknown problem instance by means of a feature-informed automated algorithm selection approach. We consider multi-objective combinatorial landscapes where, to the best of our knowledge, no in depth investigations have been conducted so far. We study simple cost-adjustable sampling strategies for extracting different state-of-the-art features. Based on extensive experiments, we report a comprehensive analysis on the impact of sampling on landscape feature values, and the subsequent automated algorithm selection task. In particular, we identify different global trends of feature values leading to non-trivial cost-vs-accuracy trade-off(s). Besides, we provide evidence that the sampling strategy can improve the prediction accuracy of automated algorithm selection. Interestingly, this holds independently of whether the sampling cost is taken into account or not in the overall solving budget.

So far, multi-objective NK landscapes have been investigated under the assumption of a homogeneous nature of the involved objectives in terms of difficulty. However, we argue that problems with heterogeneous objectives, e.g., in terms of multi-modality, can be challenging for multi-objective evolutionary algorithms, and deserve further considerations. In this paper, we propose a model of multi-objective NK landscapes, where each objective has a different degree of variable interactions (K), as a benchmark to investigate heterogeneous multi-objective optimization problems. We show that the use of a rank-annotated neighborhood network with labeled local optimal solutions, together with landscape metrics extracted from the heterogeneous objectives, thoroughly characterize bi-objective NK landscapes with a different level of heterogeneity among the objectives.

Understanding the landscape underlying NK models is of fundamental interest. Different representations have been proposed to better understand how the ruggedness of the landscape is influenced by the model parameters, such as the problem dimension, the degree of non-linearity and the structure of variable interactions. In this paper, we propose to use neural embedding, that is a continuous vectorial representation obtained as a result of applying a neural network to a prediction task, in order to investigate the characteristics of NK landscapes. The main assumption is that neural embeddings are able to capture important features that reflect the difficulty of the landscape. We propose a method for constructing NK embeddings, together with metrics for evaluating to what extent this embedding space encodes valuable information from the original NK landscape. Furthermore, we study how the embedding dimensionality and the parameters of the NK model influence the characteristics of the NK embedding space. Finally, we evaluate the performance of optimizers that solve the continuous representations of NK models by searching for solutions in the embedding space.

In this article, we propose an indicator-based branch and bound (I-BB) approach for multi-objective combinatorial optimization that uses a best-first search strategy. In particular, assuming maximizing objectives, the next node to be processed is chosen with respect to the quality of its upper bound. This quality is given by a binary quality indicator, such as the binary hypervolume or the ε-indicator, with respect to the archive of solutions maintained by the branch and bound algorithm. Although the I-BB will eventually identify the efficient set, we are particularly interested in analyzing its anytime behavior as a heuristic. Our experimental results, conducted on a multi-objective knapsack problem with 2, 3, 5, and 7 objectives, indicate that the I-BB can often outperform the naive depth-first and breadth-first search strategies, both in terms of runtime and anytime performance. The improvement is especially significant when the branching order for the decision variables is random, which suggests that the I-BB is particularly relevant when more favorable (problem-dependent) branching orders are not available.

In this paper, we demonstrate the application of features from landscape analysis, initially proposed for multi-objective combinatorial optimisation, to a benchmark set of 1 200 randomly-generated multiobjective interpolated continuous optimisation problems (MO-ICOPs). We also explore the benefits of evaluating the considered landscape features on the basis of a fixed-size sampling of the search space. This allows fine control over cost when aiming for an efficient application of feature-based automated performance prediction and algorithm selection. While previous work shows that the parameters used to generate MO-ICOPs are able to discriminate the convergence behaviour of four state-of-the-art multi-objective evolutionary algorithms, our experiments reveal that the proposed (black-box) landscape features used as predictors deliver a similar accuracy when combined with a classification model. In addition, we analyse the relative importance of each feature for performance prediction and algorithm selection.

In recent years, there has been a continuous stream of development in evolutionary multi-objective optimization (EMO) algorithms. The large quantity of existing algorithms introduces difficulty in selecting suitable algorithms for a given problem instance. In this paper, we perform instance space analysis on discrete multi-objective optimization problems (MOPs) for the first time under three different conditions. We create visualizations of the relationship between problem instances and algorithm performance for instance features previously identified using decision trees, as well an independent feature selection. The suitability of these features in discriminating between algorithm performance and understanding strengths and weaknesses is investigated. Furthermore, we explore the impact of various definitions of “good” performance. The visualization of the instance space provides an alternative method of algorithm discrimination by showing clusters of instances where algorithms perform well across the instance space. We validate the suitability of existing features and identify opportunities for future development.

On the one hand, surrogate-assisted evolutionary algorithms are established as a method of choice for expensive black-box optimization problems. On the other hand, the growth in computing facilities has seen a massive increase in potential computational power, granted the users accommodate their approaches with the offered parallelism. While a number of studies acknowledge the impact of parallelism for single-objective expensive optimization assisted by surrogates, extending such techniques to the multi-objective setting has not yet been properly investigated, especially within the state-of-the-art decomposition framework. We first highlight the different degrees of parallelism in existing surrogate-assisted multi-objective evolutionary algorithms based on decomposition (S-MOEA/D). We then provide a comprehensive analysis of the key steps towards a successful parallel S-MOEA/D approach. Through an extensive benchmarking effort relying on the well-established bbob-biobj test functions, we analyze the performance of the different algorithm designs with respect to the problem dimensionality and difficulty, the amount of parallel cores available, and the supervised learning models considered. In particular, we show the difference in algorithm scalability based on the selected surrogate-assisted approaches, the performance impact of distributing the model training task and the efficacy of the designed parallel-surrogate methods.

Anytime algorithms for optimization problems are of particular interest since they allow to trade off execution time with result quality. However, the selection of the best anytime algorithm for a given problem instance has been focused on a particular budget for execution time or particular target result quality. Moreover, it is often assumed that these anytime preferences are known when developing or training the algorithm selection methodology. In this work, we study the algorithm selection problem in a context where the decision maker's anytime preferences are defined by a general utility function, and only known at the time of selection. To this end, we first examine how to measure the performance of an anytime algorithm with respect to this utility function. Then, we discuss approaches for the development of selection methodologies that receive a utility function as an argument at the time of selection. Then, to illustrate one of the discussed approaches, we present a preliminary study on the selection between an exact and a heuristic algorithm for a bi-objective knapsack problem. The results show that the proposed methodology has an accuracy greater than 96% in the selected scenarios, but we identify room for improvement.

We consider the design and analysis of surrogate-assisted algorithms for expensive multi-objective combinatorial optimization. Focusing on pseudo-boolean functions, we leverage existing techniques based on Walsh basis to operate under the decomposition framework of MOEA/D. We investigate two design components for the cheap generation of a promising pool of offspring and the actual selection of one solution for expensive evaluation. We propose different variants, ranging from a filtering approach that selects the most promising solution at each iteration by using the constructed Walsh surrogates to discriminate between a pool of offspring generated by variation, to a substitution approach that selects a solution to evaluate by optimizing the Walsh surrogates in a multi-objective manner. Considering bi-objective NK landscapes as benchmark problems offering different degree of non-linearity, we conduct a comprehensive empirical analysis including the properties of the achievable approximation sets, the anytime performance, and the impact of the order used to train the Walsh surrogates. Our empirical findings show that, although our surrogate-assisted design is effective, the optimal integration of Walsh models within a multi-objective evolutionary search process gives rise to particular questions for which different trade-off answers can be obtained.

Building a surrogate model of an objective function has shown to be effective to assist evolutionary algorithms (EAs) to solve real-world complex optimisation problems which involve either computationally expensive numerical simulations or costly physical experiments. However, their effectiveness mostly focuses on small-scale problems with less than 10 decision variables. The scalability of surrogate assisted EAs (SAEAs) have not been well studied yet. In this paper, we propose a Gaussian process surrogate model assisted EA for medium-scale expensive multi-objective optimisation problems with up to 50 decision variables. There are three distinctive features of our proposed SAEA. First, instead of using all decision variables in surrogate model building, we only use those correlated ones to build the surrogate model for each objective function. Second, rather than directly optimising the surrogate objective functions, the original multi-objective optimisation problem is transformed to a new one based on the surrogate models. Last but not the least, a subset selection method is developed to choose a couple of promising candidate solutions for actual objective function evaluations thus to update the training dataset. The effectiveness of our proposed algorithm is validated on benchmark problems with 10, 20, 50 variables, comparing with three state-of-the-art SAEAs.

We expose and contrast the impact of landscape characteristics on the performance of search heuristics for black-box multiobjective combinatorial optimization problems. A sound and concise summary of features characterizing the structure of an arbitrary problem instance is identified and related to the expected performance of global and local dominance-based multiobjective optimization algorithms. We provide a critical review of existing features tailored to multiobjective combinatorial optimization problems, and we propose additional ones that do not require any global knowledge from the landscape, making them suitable for large-size problem instances. Their intercorrelation and their association with algorithm performance are also analyzed. This allows us to assess the individual and the joint effect of problem features on algorithm performance, and to highlight the main difficulties encountered by such search heuristics. By providing effective tools for multiobjective landscape analysis, we highlight that multiple features are required to capture problem difficulty, and we provide further insights into the importance of ruggedness and multimodality to characterize multiobjective combinatorial landscapes.

Parallelization is an important paradigm for solving massive optimization problems. Understanding how to fully benefit form the aggregated computing power and what makes a parallel strategy successful is a difficult issue. In this study, we propose a simple parallel iterative tabu search (PITS) and study its effectiveness with respect to different experimental settings. Using the quadratic assignment problem (QAP) as a case study, we first consider different small- and medium-size instances from the literature and then tackle a large-size instance that was rarely considered due the its inherent solving difficulty. In particular, we show that a balance between the number of function evaluations each parallel process is allowed to perform before resuming the search is a critical issue to obtain an improved quality.

Extracting a priori knowledge informing about the landscape underlying an unknown optimization problem has been proved extremely useful for different purposes, such as designing finely-tuned algorithms and automated solving techniques. Focusing on continuous domains, substantial progress has been achieved with the development of the so-called exploratory landscape analysis (ELA) approach, which provides a unified methodology for integrating features into sophisticated machine learning techniques. In particular, much efforts have been devoted to the systematic design of algorithm selection models aiming at improving existing state-of-art solvers. Nonetheless, designing the ELA features themselves is a bottleneck that can prevent further advances. The contribution of this paper is thereby two fold. Firstly, we consider the design of insightful features on the basis of the search tree constructed by the so-called SOO global optimizer, which is shown to imply an informative sampling of the search space using a limited budget. Secondly, we provide empirical evidence on the relevance of the proposed features and their potential in complementing existing ELA features for both predicting high-level problem properties, and selecting algorithms from a portfolio of available solvers. Our empirical findings are based on a comprehensive analysis using the diverse set of BBOB functions and solvers from the COCO platform.

A number of surrogate-assisted evolutionary algorithms are being developed for tackling expensive multiobjective optimization problems. On the one hand, a relatively broad range of techniques from both machine learning and multiobjective optimization can be combined for this purpose. Different taxonomies exist in order to better delimit the design choices, advantages and drawbacks of existing approaches. On the other hand, assessing the relative performance of a given approach is a difficult task, since it depends on the characteristics of the problem at hand. In this paper, we focus on surrogate-assisted approaches using objective space decomposition as a core component. We propose a refined and fine-grained classification, ranging from EGO-like approaches to filtering or pre-screening. More importantly, we provide a comprehensive comparative study of a representative selection of state-of-the-art methods, together with simple baseline algorithms. We rely on selected benchmark functions taken from the bbob-biobj benchmarking test suite, that provides a variable range of objective function difficulties. Our empirical analysis highlights the effect of the available budget on the relative performance of each approach, and the impact of the training set and of the machine learning model construction on both solution quality and runtime efficiency.

The working principles of the well-established multi-objective evolutionary algorithm Moea/d relies on the iterative and cooperative improvement of a number of single-objective sub-problems obtained by decomposition. Besides the definition of sub-problems, selection and replacement are, like in any evolutionary algorithm, the two core elements of Moea/d. We argue that these two components are however loosely coupled with the maintained population. Thereby, we propose to re-design the working principles of Moea/d by adopting a set-oriented perspective, where a many-to-one mapping between sub-problems and solutions is considered. Selection is then performed by defining a neighborhood relation among solutions in the population set, depending on the corresponding sub-problem mapping. Replacement is performed following an elitist mechanism allowing the population to have a variable, but bounded, cardinality during the search process. By conducting a comprehensive empirical analysis on a range of combinatorial multi- and many-objective NK-landscapes, we show that the proposed approach leads to significant improvements, especially when dealing with an increasing number of objectives. Our findings indicate that a set-oriented design can constitute a sound alternative for strengthening the practice of multi- and many-objective evolutionary optimization based on decomposition.

Local search algorithms have shown good performance for several multi-objective combinatorial optimization problems. These approaches naturally stop at a local optimal set (LO-set) under given definitions of neighborhood and preference relation among subsets of solutions, such as set-based dominance relation, hypervolume or epsilon indicator. It is an open question how LO-sets under different set preference relations relate to each other. This paper reports an in-depth experimental analysis on multi-objective nk-landscapes. Our results reveal that, whatever the preference relation, the number of LO-sets typically increases with the problem non-linearity, and decreases with the number of objectives. We observe that strict LO-sets of bounded cardinality under set-dominance are LO-sets under both epsilon and hypervolume, and that LO-sets under hyper-volume are LO-sets under set-dominance, whereas LO-sets under epsilon are not. Nonetheless, LO-sets under set-dominance are more similar to LO-sets under epsilon than under hypervolume. These findings have important implications for multi-objective local search. For instance, a dominance-based approach with bounded archive gets more easily trapped and might experience difficulty to identify an LO-set under epsilon or hypervolume. On the contrary, a hypervolume-based approach is expected to perform more steps before converging to better approximations.

Pareto Local Search (PLS) is a simple, yet effective optimization approach dedicated to multi-objective combinatorial optimization. It can however suffer from a high computational cost, especially when the size of the Pareto optimal set is relatively large. Recently, incorporating decomposition in PLS had revealed a high potential, not only in providing high-quality approximation sets, but also in speeding-up the search process. Using the bi-objective Unconstrained Binary Quadratic Programming (bUBQP) problem as an illustrative benchmark, we demonstrate some shortcomings in the resulting decomposition-guided Parallel Pareto Local Search (PPLS), and we propose to revisit the PPLS design accordingly. For instances with a priori unknown Pareto front shape, we show that a simple pre-processing technique to estimate the scale of the Pareto front can help PPLS to better balance the workload. Furthermore, we propose a simple technique to deal with the critically-important scalability issue raised by PPLS when deployed over a large number of computing nodes. Our investigations show that the revisited version of PPLS provides a consistent performance, suggesting that decomposition-guided PPLS can be further generalized in order to improve both parallel efficiency and approximation quality.

Although several sequential heuristics have been proposed for dealing with the Unconstrained Binary Quadratic Programming (UBQP), very little effort has been made for designing parallel algorithms for the UBQP. This paper propose a novel decentralized parallel search algorithm, called Parallel Elite Biased Tabu Search (PEBTS). It is based on D2TS, a state-of-the-art sequential UBQP metaheuristic. The key strategies in the PEBTS algorithm include: (i) a lazy distributed cooperation procedure to maintain diversity among different search processes and (ii) finely tuned bit-flip operators which can help the search escape local optima efficiently. Our experiments on the Tianhe-2 supercomputer with up to 24 computing cores show the accuracy of the efficiency of PEBTS compared with a straightforward parallel algorithm running multiple independent and non-cooperating D2TS processes.

This work proposes 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.

In this article, we attempt to understand and to contrast the impact of problem features on the performance of randomized search heuristics for black-box multiobjective combinatorial optimization problems. At first, we measure the performance of two conventional dominance-based approaches with unbounded archive on a benchmark of enumerable binary optimization problems with tunable ruggedness, objective space dimension, and objective correlation ([Formula: see text]MNK-landscapes). Precisely, we investigate the expected runtime required by a global evolutionary optimization algorithm with an ergodic variation operator (GSEMO) and by a neighborhood-based local search heuristic (PLS), to identify a ([Formula: see text]approximation of the Pareto set. Then, we define a number of problem features characterizing the fitness landscape, and we study their intercorrelation and their association with algorithm runtime on the benchmark instances. At last, with a mixed-effects multilinear regression we assess the individual and joint effect of problem features on the performance of both algorithms, within and across the instance classes defined by benchmark parameters. Our analysis reveals further insights into the importance of ruggedness and multimodality to characterize instance hardness for this family of multiobjective optimization problems and algorithms.

Subset selection constitutes an important stage of any evolutionary multiobjective optimization algorithm when truncating the current approximation set for the next iteration. This appears to be particularly challenging when the number of solutions to be removed is large, and when the approximation set contains many mutually non-dominating solutions. In particular, indicator-based strategies have been intensively used in recent years for that purpose. However, most solutions for the indicator-based subset selection problem are based on a very simple greedy backward elimination strategy. In this paper, we experiment additional heuristics that include a greedy forward selection and a greedy sequential insertion policies, a first-improvement hill-climbing local search, as well as combinations of those. We evaluate the effectiveness and the efficiency of such heuristics in order to maximize the enclosed hypervolume indicator of candidate subsets during a hypothetical evolutionary process, or as a post-processing phase. Our experimental analysis, conducted on randomly generated as well as structured two-, three- and four-objective mutually non-dominated sets, allows us to appreciate the benefit of these approaches in terms of quality, and to highlight some practical limitations and open challenges in terms of computational resources.

A large spectrum of quality indicators has been proposed so far to assess the performance of discrete Pareto set approximations in multiobjective optimization. Such indicators assign, to any solution set, a real-value reflecting a given aspect of approximation quality. This is an important issue in multiobjective optimization, not only to compare the performance and assets of different approximate algorithms, but also to improve their internal selection mechanisms. In this paper, we adopt a statistical analysis to experimentally investigate by how much a selection of state-of-the-art quality indicators agree with each other for a wide range of Pareto set approximations from well-known two- and three-objective continuous benchmark functions. More particularly, we measure the correlation between the ranking of low-, medium-, and high-quality limited-size approximation sets with respect to inverted generational distance, additive epsilon, multiplicative epsilon, R2, R3, as well as hypervolume indicator values. Since no pair of indicators obtains the same ranking of approximation sets, we confirm that they emphasize different facets of approximation quality. More importantly, our statistical analysis allows the degree of compliance between these indicators to be quantified.

We propose the first large-scale message passing distributed scheme for parallelizing the computational flow of Moea/d, a popular decomposition-based evolutionary multiobjective optimization algorithm. We show how synchronicity and workload granularity can impact both quality and computing time, in an extremely fine-grained configuration where each individual in the Moea/d population is mapped to a single distributed processing unit. More specifically, we deploy our distributed protocol using a large-scale environment of 128 computing cores and conduct a throughout analysis using a broad range of bi-objective combinatorial ρMNK-landscapes. Besides being able to show significant speed-ups while maintaining competitive search quality, our experimental results provide insights into the behavior of the proposed scheme in terms of quality/speedup trade-offs; thus pushing a step towards the achievement of effective and efficient parallel decomposition-based approaches for large-scale multi-objective optimization.

Computationally hard multi-objective combinatorial optimization problems are common in practice, and numerous evolutionary multi-objective optimization (EMO) algorithms have been proposed to tackle them. Our aim is to understand which (and how) problem features impact the search performance of such approaches. In this paper, we consider two prototypical dominance-based algorithms: a global EMO strategy using an ergodic variation operator (GSEMO) and a neighborhood-based local search heuristic (PLS). Their respective runtime is estimated on a benchmark of combinatorial problems with tunable ruggedness, objective space dimension, and objective correlation ($\rho$MNK-landscapes). In other words, benchmark parameters define classes of instances with increasing empirical problem hardness; we enumerate and characterize the search space of small instances. Our study departs from simple performance comparison to systematically analyze the correlations between runtime and problem features, contrasting their association with search performance within and across instance classes, for both chosen algorithms. A mixed-model approach then allows us to further generalize from the experimental design, supporting a sound assessment of the joint impact of instance features on EMO search performance.

MOEA/D is an aggregation-based evolutionary algorithm which has been proved extremely efficient and effective for solving multi-objective optimization problems. It is based on the idea of decomposing the original multi-objective problem into several single-objective subproblems by means of well-defined scalarizing functions. Those single-objective subproblems are solved in a cooperative manner by defining a neighborhood relation between them. This makes MOEA/D particularly interesting when attempting to plug and to leverage single-objective optimizers in a multi-objective setting. In this context, we investigate the benefits that MOEA/D can achieve when coupled with CMA-ES, which is believed to be a powerful single-objective optimizer. We rely on the ability of CMA-ES to deal with injected solutions in order to update different covariance matrices with respect to each subproblem defined in MOEA/D. We show that by cooperatively evolving neighboring CMA-ES components, we are able to obtain competitive results for different multi-objective benchmark functions.

In this work we study the effects of population size on selection and performance scalability of two dominance-based algorithms applied to many-objective optimization. Our aim is to understand the relationship between the size of the Pareto optimal set, a characteristic of the many-objective problem at hand, the population size and the ability of the algorithm to retain Pareto optimal solutions in its population and find new ones. This work clarifies important issues of the dynamics of evolutionary algorithms on many-objective landscapes, particularly related to survival selection. It shows that optimal solutions are dropped from the population in favor of suboptimal solutions that appear non-dominated when survival selection is applied. It also shows that this selection lapse, the dropping of optimal solution, affects the discovery of new optimal solutions and is correlated to population size and the distribution of solutions that survival selection renders. Selection makes less mistakes with larger populations and when the distribution of solutions is better controlled. The results of this study will be helpful to properly set population size and have a clearer idea about the performance expectation of the algorithm.

In this paper, we formalize a multiobjective local search paradigm by combining set-based multiobjective optimization and neighborhood-based search principles. Approximating the Pareto set of a multiobjective optimization problem has been recently defined as a set problem, in which the search space is made of all feasible solution-sets. We here introduce a general set-based local search algorithm, explicitly based on a set-domain search space, evaluation function, and neighborhood relation. Different classes of set-domain neighborhood structures are proposed, each one leading to a different set-based local search variant. The corresponding methodology generalizes and unifies a large number of existing approaches for multiobjective optimization. Preliminary experiments on multiobjective NK-landscapes with objective correlation validates the ability of the set-based local search principles. Moreover, our investigations shed the light to further research on the efficient exploration of large-size set-domain neighborhood structures.

MOTIVATION: In this article, we consider the bicriteria pairwise sequence alignment problem and propose extensions of dynamic programming algorithms for several problem variants with a novel pruning technique that efficiently reduces the number of states to be processed. Moreover, we present a method for the construction of phylogenetic trees based on this bicriteria framework. Two exemplary cases are discussed. RESULTS: Numerical results on a real dataset show that this approach is very fast in practice. The pruning technique saves up to 90% in memory usage and 80% in CPU time. Based on this method, phylogenetic trees are constructed from real-life data. In addition of providing complementary information, some of these trees match those obtained by the Maximum Likelihood method. AVAILABILITY AND IMPLEMENTATION: Source code is freely available for download at URL http://eden.dei.uc.pt/paquete/MOSAL, implemented in C and supported on Linux, MAC OS and MS Windows.

In this article, a local search approach is proposed for three variants of the bi-objective binary knapsack problem, with the aim of maximizing the total profit and minimizing the total weight. First, an experimental study on a given structural property of connectedness of the efficient set is conducted. Based on this property, a local search algorithm is proposed and its performance is compared to exact algorithms in terms of runtime and quality metrics. The experimental results indicate that this simple local search algorithm is able to find a representative set of optimal solutions in most of the cases, and in much less time than exact algorithms.

This article presents CoBRA, a new evolutionary algorithm, based on a coevolutionary scheme, to solve bi-level optimization problems. It handles population-based algorithms on each level, each one cooperating with the other to provide solutions for the overall problem. Moreover, in order to evaluate the relevance of CoBRA against more classical approaches, a new performance assessment methodology, based on rationality, is introduced. An experimental analysis is conducted on a bi-level distribution planning problem, where multiple manufacturing plants deliver items to depots, and where a distribution company controls several depots and distributes items from depots to retailers. The experimental results reveal significant enhancements, particularly over the lower level, with respect to a more classical approach based on a hierarchical scheme.

VEGAS (Varying Evolvability-Guided Adaptive Search) is a new methodology proposed to deal with the neutrality property that frequently appears on combinatorial optimization problems. Its main feature is to consider the whole evaluated solutions of a neutral network rather than the last accepted solution. Moreover, VEGAS is designed to escape from plateaus based on the evolvability of solutions, and on a multi-armed bandit by selecting the more promising solution from the neutral network. Experiments are conducted on NK-landscapes with neutrality. Results show the importance of considering the whole identified solutions from the neutral network and of guiding the search explicitly. The impact of the level of neutrality and of the exploration-exploitation trade-off are deeply analyzed.

Fitness landscape analysis aims to understand the geometry of a given optimization problem in order to design more efficient search algorithms. However, there is a very little knowledge on the landscape of multiobjective problems. In this work, following a recent proposal by Zitzler et al. (2010), we consider multiobjective optimization as a set problem. Then, we give a general definition of set-based multiobjective fitness landscapes. An experimental set-based fitness landscape analysis is conducted on the multiobjective NK-landscapes with objective correlation. The aim is to adapt and to enhance the comprehensive design of set-based multiobjective search approaches, motivated by an a priori analysis of the corresponding set problem properties.