The hypervolume indicator measures the volume of the objective space weakly dominated by a set of solutions in multi-objective optimization problems. It is one of the most popular unary quality metrics for comparing multi-objective optimizers. The computation of the hypervolume requires exponential time on the number of objectives, hence, it becomes computationally expensive for thousands of points in more than 5 dimensions. To overcome this limitation, several methods for approximating the hypervolume have been proposed in the literature. A recent proposal uses polar coordinates to transform the hypervolume into an integral over the hypersphere that is approximated via (quasi-)Monte Carlo sampling. In this paper, we replace two key components of this proposal with: (1) Rϕ, a fast multi-dimensional generalization of the Kronecker sequence that generates sampling points in the hypercube, and (2) a simple and efficient mapping from the hypercube to the positive orthant of the hypersphere. We compare these components with other possible alternatives, including the well-known Sobol and Halton low-discrepancy sequences. Our experimental results show that combination of these two components, which we call Rϕ-FWE+, typically achieves lower approximation error at equal or lower computation cost.

Designing effective heuristics remains a labor-intensive task traditionally reserved for domain experts. While Large Language Model (LLM)-driven evolutionary search offers a path toward automated discovery, existing methods often suffer from slow convergence, primarily due to inefficient hyperparameter tuning. Delegating tuning to specialized optimizers improves performance, but it comes at the cost of code bloat and overfitting. To address these issues, we propose a pipeline that introduces a novel regularization architecture balancing performance and complexity. Specifically, we mitigate the side effects of automated tuning through two novel components: (i) symbolic pruning mutator, which combines LLM semantic guidance with Abstract Syntax Tree analysis to eliminate algorithmic redundancy; and (ii) a complexity-aware mutation gate that explicitly filters out mutations leading to excessive code growth. Our framework substantially accelerates convergence and improves generalization on standard benchmarks of the 3D Single Container Loading Problem. The discovered heuristics match state-of-the-art human designed algorithms and rediscover similar geometric principles used by experts, highlighting the framework's ability to autonomously extract meaningful domain knowledge.

Portfolio configurators tune an algorithm's parameters to produce a portfolio of parameterisations, with complementary strengths on different problem instances. However, as the portfolio size increases, the marginal contribution of each additional configuration decreases, making portfolio configuration computationally expensive. We propose a hybrid racing method that combines statistical testing (to early eliminate poorly performing configurations) and successive halving (which progressively allocates more resources to promising configurations by discarding fractions of the configuration candidate set in rounds). We connect greedy portfolio configuration approaches to the theory of submodular function optimisation, which implies an approximation ratio of 1 − 1/e for the problem in idealised form. We experimentally compare the hybrid method with pure statistical racing and pure successive halving, on algorithm configuration benchmarks from the literature. We show that the proposed hybrid racing method achieves portfolios with performance matching those configured on the full evaluation data, while usually using roughly 5% of the runs of a full evaluation, and that the method is more efficient than pure statistical racing or successive halving for portfolio configuration. Our experiments demonstrate that adaptive elimination strategies can significantly improve the efficiency of portfolio configuration methods.

Surrogate models are frequently employed as efficient substitutes for the costly execution of real-world processes. However, constructing a high-quality surrogate model often demands extensive data acquisition. A solution to this issue is to transfer pre-trained surrogate models for new tasks, provided that certain invariances exist between tasks. This study focuses on transferring non-differentiable surrogate models (e.g., random forests) from a source function to a target function, where we assume their domains are related by an unknown affine transformation, using only a limited amount of transfer data points evaluated on the target. Previous research attempts to tackle this challenge for differentiable models, e.g., Gaussian process regression, which minimizes the empirical loss on the transfer data by tuning the affine transformations. In this paper, we extend the previous work to the random forest and assess its effectiveness on a widely-used artificial problem set - Black-Box Optimization Benchmark (BBOB) testbed, and on four real-world transfer learning problems. The results highlight the significant practical advantages of the proposed method, particularly in reducing both the data requirements and computational costs of training surrogate models for complex real-world scenarios.

A widely accepted way to assess the performance of iterative black-box optimizers is to analyze their empirical cumulative distribution function (ECDF) of predefined quality targets achieved not later than a given runtime. In this work, we consider an alternative approach, based on the empirical attainment function (EAF) and we show that the target-based ECDF is an approximation of the EAF. We argue that the EAF has several advantages over the target-based ECDF. In particular, it does not require defining a priori quality targets per function, captures performance differences more precisely, and enables the use of additional summary statistics that enrich the analysis. We also show that the average area over the convergence curves is a simpler-to-calculate, but equivalent, measure of anytime performance. To facilitate the accessibility of the EAF, we integrate a module to compute it into the IOHanalyzer platform. Finally, we illustrate the use of the EAF via synthetic examples and via the data available for the black-box optimization benchmark suite.

Surrogate models are widely applied in many scenarios to replace expensive executions of real-world procedures. Training a high-quality surrogate model often requires many sample points, which can be costly to obtain. We would amortize this cost if we could reuse already-trained surrogates in future tasks, provided certain invariances are retained across tasks. This paper studies transferring a surrogate model trained on a source function to a target function using a small data set. As a first step, we consider the following invariance: the domains of the source and target functions are related by an unknown affine transformation. We propose to parameterize the surrogate of the source with an affine transformation and optimize it w.r.t. an empirical loss measured with a small transfer data set sampled on the target. We select all functions from the well-known black-box optimization benchmark (BBOB) as the source and artificially generate the target with affine transformation sampled u.a.r. We experiment with a commonly used surrogate model, Gaussian process regression, where results show that the transferred surrogate significantly outperforms both the original surrogate and the one built from scratch with the transfer data set.

Experimental research is an essential component in the field of evolutionary computation (EC). The scientific method requires that empirical results are reproducible. Reproducibility of experiments also helps later researchers build upon the work of previous researchers. Interest in improving reproducibility in computer science and other empirical sciences has grown in recent years and there is a growing number of works analyzing current and best practices, obstacles and guidelines, effectiveness of journal policies, etc. Reproducibility issues in the context of EC have been a topic of discussion for a long time in the context of best practices for empirical research, but there are few studies analyzing reproducibility in EC research, and reproducibility studies themselves are extremely rare. There is room for improvement to attain the minimum standards for reproducibility encouraged in other scientific fields. Reproducibility goes beyond making implementation of algorithms publicly available. Challenges for reproducibility in EC research arise from the stochastic nature of the algorithms and, sometimes, the problems, which require multiple runs to analyze expected behavior and variance; sensitivity of the results to the computational environment, parameter settings, or implementation details; and the generalizability of conclusions to different instances of the same or related problems.This special issue of Evolutionary Computation on reproducibility features three exceptional papers that highlight different aspects of reproducibility and how to achieve it in practice.In “Using Decomposed Error for Reproducing Implicit Understanding of Algorithms” (10.1162/evco_a_00321), Caitlin A. Owen, Grant Dick, and Peter A. Whigham propose an error decomposition framework to improve the reproducibility of experiments in evolutionary machine learning. This framework takes into account information about bias, variance due to internal algorithmic choices, and variance due to training data, from multiple runs. The authors examine the behavior of three evolutionary machine learning approaches with this framework, which provides a fine-grained analysis on the decomposition of errors, and allow them to pinpoint mismatched expectations about algorithm behavior.In “The Importance of Being Constrained: Dealing with Infeasible Solutions in Differential Evolution and Beyond” (10.1162/evco_a_00333), Anna V. Kononova, Diederick Vermetten, Fabio Caraffini, Madalina-A. Mitran, and Daniela Zaharie argue that the strategy for dealing with infeasible solutions in constrained optimization problems has a significant impact on the reproducibility of experiments in heuristic optimization, and this impact grows with the dimensionality of the problem.In “A Practical Methodology for Reproducible Experimentation: An Application to the Double-Row Facility Layout Problem” (10.1162/evco_a_00317), Raúl Martín-Santamaría, Sergio Cavero, Alberto Herrán, Abraham Duarte, and J. Manuel Colmenar provide a methodology, and the software implementing it, for carrying out experiments with stochastic optimization methods. They illustrate the methodology on the double-row facility layout problem, reproducing previous results and ensuring that their own new results are fully reproducible.We believe that there is an ongoing cultural shift within computer science in general and within EC in particular, with both reviewers and funding agencies expecting and rewarding reproducibility efforts. The submission guidelines of Evolutionary Computation encourage authors to “ensure reproducibility.” Other journals have adopted “reproducibility boards” and “reproducibility badges.” Some conferences and journals have already gone a step further and require that experiments are reproducible by reviewers before publication. As a result of these efforts, we expect that the good practice standards in EC regarding reproducibility will improve in the next decade.

Most multi-objective optimisation algorithms maintain an archive explicitly or implicitly during their search. Such an archive can be solely used to store high-quality solutions presented to the decision maker, but in many cases may participate in the search process (e.g., as the population in evolutionary computation). Over the last two decades, archiving, the process of comparing new solutions with previous ones and deciding how to update the archive/population, stands as an important issue in evolutionary multi-objective optimisation (EMO). This is evidenced by constant efforts from the community on developing various effective archiving methods, ranging from conventional Pareto-based methods to more recent indicator-based and decomposition-based ones. However, the focus of these efforts is on empirical performance comparison in terms of specific quality indicators; there is lack of systematic study of archiving methods from a general theoretical perspective. In this paper, we attempt to conduct a systematic overview of multi-objective archiving, in the hope of paving the way to understand archiving algorithms from a holistic perspective of theory and practice, and more importantly providing a guidance on how to design theoretically desirable and practically useful archiving algorithms. In doing so, we also present that archiving algorithms based on weakly Pareto compliant indicators (e.g., -indicator), as long as designed properly, can achieve the same theoretical desirables as archivers based on Pareto compliant indicators (e.g., hypervolume indicator). Such desirables include the property limit-optimal, the limit form of the possible optimal property that a bounded archiving algorithm can have with respect to the most general form of superiority between solution sets.

Evolutionary multi-objective optimization algorithms (EMOAs) typically assume that all objectives that are relevant to the decision-maker (DM) are optimized by the EMOA. In some scenarios, however, there are irrelevant objectives that are optimized by the EMOA but ignored by the DM, as well as, hidden objectives that the DM considers when judging the utility of solutions but are not optimized. This discrepancy between the EMOA and the DM’s preferences may impede the search for the most-preferred solution and waste resources evaluating irrelevant objectives. Research on objective reduction has focused so far on the structure of the problem and correlations between objectives and neglected the role of the DM. We formally define here the concepts of irrelevant and hidden objectives and propose methods for detecting them, based on uni-variate feature selection and recursive feature elimination, that use the preferences already elicited when a DM interacts with a ranking-based interactive EMOA (iEMOA). We incorporate the detection methods into an iEMOA capable of dynamically switching the objectives being optimized. Our experiments show that this approach can efficiently identify which objectives are relevant to the DM and reduce the number of objectives being optimized, while keeping and often improving the utility, according to the DM, of the best solution found.

We carry out a detailed performance assessment of two interactive evolutionary multi-objective algorithms (EMOAs) using a machine decision maker that enables us to repeat experiments and study specific behaviours modeled after human decision makers (DMs). Using the same set of benchmark test problems as in the original papers on these interactive EMOAs (in up to 10 objectives), we bring to light interesting effects when we use a machine DM based on sigmoidal utility functions that have support from the psychology literature (replacing the simpler utility functions used in the original papers). Our machine DM enables us to go further and simulate human biases and inconsistencies as well. Our results from this study, which is the most comprehensive assessment of multiple interactive EMOAs so far conducted, suggest that current well-known algorithms have shortcomings that need addressing. These results further demonstrate the value of improving the benchmarking of interactive EMOAs.

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.

This paper reports on the first international competition on AI for the traveling salesman problem (TSP) at the International Joint Conference on Artificial Intelligence 2021 (IJCAI-21). The TSP is one of the classical combinatorial optimization problems, with many variants inspired by real-world applications. This first competition asked the participants to develop algorithms to solve an orienteering problem with stochastic weights and time windows (OPSWTW). It focused on two learning approaches: surrogate-based optimization and deep reinforcement learning. In this paper, we describe the problem, the competition setup, and the winning methods, and give an overview of the results. The winning methods described in this work have advanced the state-of-the-art in using AI for stochastic routing problems. Overall, by organizing this competition we have introduced routing problems as an interesting problem setting for AI researchers. The simulator of the problem has been made open-source and can be used by other researchers as a benchmark for new learning-based methods. The instances and code for the competition are available at https://github.com/paulorocosta/ai-for-tsp-competition.

In the traffic light scheduling problem, the evaluation of candidate solutions requires the simulation of a process under various (traffic) scenarios. Thus, good solutions should not only achieve good objective function values, but they must be robust (low variance) across all different scenarios. Previous work has shown that combining IRACE with evolutionary operators is effective for this task due to the power of evolutionary operators in numerical optimization. In this article, we further explore the hybridization of evolutionary operators and the elitist iterated racing of IRACE for the simulation-optimization of traffic light programs. We review previous works from the literature to find the evolutionary operators performing the best when facing this problem to propose new hybrid algorithms. We evaluate our approach over a realistic case study derived from the traffic network of Málaga (Spain) with 275 traffic lights that should be scheduled optimally. The experimental analysis reveals that the hybrid algorithm comprising IRACE plus differential evolution offers statistically better results than the other algorithms when the budget of simulations is low. In contrast, IRACE performs better than the hybrids for a high simulations budget, although the optimization time is much longer.

For offline data-driven multiobjective optimization problems (MOPs), no new data is available during the optimization process. Approximation models (or surrogates) are first built using the provided offline data, and an optimizer, for example, a multiobjective evolutionary algorithm, can then be utilized to find Pareto optimal solutions to the problem with surrogates as objective functions. In contrast to online data-driven MOPs, these surrogates cannot be updated with new data and, hence, the approximation accuracy cannot be improved by considering new data during the optimization process. Gaussian process regression (GPR) models are widely used as surrogates because of their ability to provide uncertainty information. However, building GPRs becomes computationally expensive when the size of the dataset is large. Using sparse GPRs reduces the computational cost of building the surrogates. However, sparse GPRs are not tailored to solve offline data-driven MOPs, where good accuracy of the surrogates is needed near Pareto optimal solutions. Treed GPR (TGPR-MO) surrogates for offline data-driven MOPs with continuous decision variables are proposed in this paper. The proposed surrogates first split the decision space into subregions using regression trees and build GPRs sequentially in regions close to Pareto optimal solutions in the decision space to accurately approximate tradeoffs between the objective functions. TGPR-MO surrogates are computationally inexpensive because GPRs are built only in a smaller region of the decision space utilizing a subset of the data. The TGPR-MO surrogates were tested on distance-based visualizable problems with various data sizes, sampling strategies, numbers of objective functions, and decision variables. Experimental results showed that the TGPR-MO surrogates are computationally cheaper and can handle datasets of large size. Furthermore, TGPR-MO surrogates produced solutions closer to Pareto optimal solutions compared to full GPRs and sparse GPRs.

Facility location problems (FLPs) are one of the most studied problem classes in supply chain management. However, despite the high number of research outputs, complex FLPs with large decision spaces and multi-objective formulations remain hard to solve. In this paper we introduce a multi-objective mathematical model for the FLP in personalised medicine, and apply a multi-stage algorithmic approach to solve it. In this case, the supply chain is circular and follows an on-demand and batch specific approach where the patient is also the donor. We solve the problem in a multi-stage manner, each stage optimising a sub-space of the larger decision space. In each stage we free up more decision variables to optimise, until eventually all decision variables defining the complete problem are made available for optimisation. A variant of the NSGA-II algorithm is used as solution method to solve both the complete problem and the different problem stages. Our results suggest that the multi-stage approach is able to find better solutions when compared to an approach that is given an equivalent number of evaluations but optimises the complete problem at once.

Quantum and quantum-inspired optimisation algorithms are designed to solve problems represented in binary, quadratic and unconstrained form. Combinatorial optimisation problems are therefore often formulated as Quadratic Unconstrained Binary Optimisation Problems (QUBO) to solve them with these algorithms. Moreover, these QUBO solvers are often implemented using specialised hardware to achieve enormous speedups, e.g. Fujitsu's Digital Annealer (DA) and D-Wave's Quantum Annealer. However, these are single-objective solvers, while many real-world problems feature multiple conflicting objectives. Thus, a common practice when using these QUBO solvers is to scalarise such multi-objective problems into a sequence of single-objective problems. Due to design trade-offs of these solvers, formulating each scalarisation may require more time than finding a local optimum. We present the first attempt to extend the algorithm supporting a commercial QUBO solver as a multi-objective solver that is not based on scalarisation. The proposed multi-objective DA algorithm is validated on the bi-objective Quadratic Assignment Problem. We observe that algorithm performance significantly depends on the archiving strategy adopted, and that combining DA with non-scalarisation methods to optimise multiple objectives outperforms the current scalarised version of the DA in terms of final solution quality.

We consider a type of constrained optimization problem, where the violation of a constraint leads to an irrevocable loss, such as breakage of a valuable experimental resource/platform or loss of human life. Such problems are referred to as safe optimization problems (SafeOPs). While SafeOPs have received attention in the machine learning community in recent years, there was little interest in the evolutionary computation (EC) community despite some early attempts between 2009 and 2011. Moreover, there is a lack of acceptable guidelines on how to benchmark different algorithms for SafeOPs, an area where the EC community has significant experience in. Driven by the need for more eficient algorithms and benchmark guidelines for SafeOPs, the objective of this paper is to reignite the interest of the EC community in this problem class. To achieve this we (i) provide a formal definition of SafeOPs and contrast it to other types of optimization problems that the EC community is familiar with, (ii) investigate the impact of key SafeOP parameters on the performance of selected safe optimization algorithms, (iii) benchmark EC against state-of-the-art safe optimization algorithms from the machine learning community, and (iv) provide an open-source Python framework to replicate and extend our work.

We consider a new class of expensive, resource-constrained optimization problems (here arising from molecular discovery) where costs are associated with the experiments (or evaluations) to be carried out during the optimization process. In the molecular discovery problem, candidate compounds to be optimized must be synthesized in an iterative process that starts from a set of purchasable items and builds up to larger molecules. To produce target molecules, their required resources are either used from already-synthesized items in storage or produced themselves on-demand at an additional cost. Any remaining resources from the production process are stored for reuse for the next evaluations. We model these resource dependencies with a directed acyclic production graph describing the development process from granular purchasable items to evaluable target compounds. Moreover, we develop several resource-eficient algorithms to address this problem. In particular, we develop resource-aware variants of Random Search heuristics and of Bayesian Optimization and analyze their performance in terms of anytime behavior. The experimental results were obtained from a real-world molecular optimization problem. Our results suggest that algorithms that encourage exploitation by reusing existing resources achieve satisfactory results while using fewer resources overall.

The stochastic nature of iterative optimization heuristics leads to inherently noisy performance measurements. Since these measurements are often gathered once and then used repeatedly, the number of collected samples will have a significant impact on the reliability of algorithm comparisons. We show that care should be taken when making decisions based on limited data. Particularly, we show that the number of runs used in many benchmarking studies, e.g., the default value of 15 suggested by the COCO environment, can be insufficient to reliably rank algorithms on well-known numerical optimization benchmarks.

Expensive black-box combinatorial optimization problems arise in practice when the objective function is evaluated by means of a simulator or a real-world experiment. Since each fitness evaluation is expensive in terms of time or resources, the number of possible evaluations is typically several orders of magnitude smaller than in non-expensive problems. Classical optimization methods are not useful in this scenario. In this paper, we propose and analyze UMM, an estimation-of-distribution (EDA) algorithm based on a Mallows probabilistic model and unbalanced rank aggregation (uBorda). Experimental results on black-box versions of LOP and PFSP show that UMM outperforms the solutions obtained by CEGO, a Bayesian optimization algorithm for combinatorial optimization. Nevertheless, a slight modification to CEGO, based on the different interpretations for rankings and orderings, significantly improves its performance, thus producing solutions that are slightly better than those of UMM and dramatically better than the original version. Another benefit of UMM is that its computational complexity increases linearly with both the number of function evaluations and the permutation size, which results in computation times an order of magnitude shorter than CEGO, making it specially useful when both computation time and number of evaluations are limited.

Improvements to the design of interactive Evolutionary Multiobjective Algorithms (iEMOAs) are unlikely without quantitative assessment of their behaviour in realistic settings. Experiments with human decision-makers (DMs) are of limited scope due to the difficulty of isolating individual biases and replicating the experiment with enough subjects, and enough times, to obtain confidence in the results. Simulation studies may help to overcome these issues, but they require the use of realistic simulations of decision-makers. Machine decision-makers (MDMs) provide a way to carry out such simulation studies, however, studies so far have relied on simple utility functions. In this paper, we analyse and compare two state-of-the-art iEMOAs by means of a MDM that uses a sigmoid-shaped utility function. This sigmoid utility function is based on psychologically realistic models from behavioural economics, and replicates several realistic human behaviours. Our findings are that, on a variety of well-known benchmarks with two and three objectives, the two iEMOAs do not consistently recover the most-preferred points. We hope that these findings provide an impetus for more directed design and analysis of future iEMOAs.

We address challenges of decision problems when managers need to optimize several conflicting objectives simultaneously under uncertainty. We propose visualization tools to support the solution of such scenario-based multiobjective optimization problems. Suitable graphical visualizations are necessary to support managers in understanding, evaluating, and comparing the performances of management decisions according to all objectives in all plausible scenarios. To date, no appropriate visualization has been suggested. This paper fills this gap by proposing two visualization methods: a novel extension of empirical attainment functions for scenarios and an adapted version of heatmaps. They help a decision-maker in gaining insight into realizations of trade-offs and comparisons between objective functions in different scenarios. Some fundamental questions that a decision-maker may wish to answer with the help of visualizations are also identified. Several examples are utilized to illustrate how the proposed visualizations support a decision-maker in evaluating and comparing solutions to be able to make a robust decision by answering the questions. Finally, we validate the usefulness of the proposed visualizations in a real-world problem with a real decision-maker. We conclude with guidelines regarding which of the proposed visualizations are best suited for different problem classes.

Experimental studies are prevalent in Evolutionary Computation (EC), and concerns about the reproducibility and replicability of such studies have increased in recent times, reflecting similar concerns in other scientific fields. In this article, we discuss, within the context of EC, the different types of reproducibility and suggest a classification that refines the badge system of the Association of Computing Machinery (ACM) adopted by ACM Transactions on Evolutionary Learning and Optimization (https://dlnext.acm.org/journal/telo). We identify cultural and technical obstacles to reproducibility in the EC field. Finally, we provide guidelines and suggest tools that may help to overcome some of these reproducibility obstacles.

A recent comparison of well-established multiobjective evolutionary algorithms (MOEAs) has helped better identify the current state-of-the-art by considering (i) parameter tuning through automatic configuration, (ii) a wide range of different setups, and (iii) various performance metrics. Here, we automatically devise MOEAs with verified state-of-the-art performance for multi- and many-objective continuous optimization. Our work is based on two main considerations. The first is that high-performing algorithms can be obtained from a configurable algorithmic framework in an automated way. The second is that multiple performance metrics may be required to guide this automatic design process. In the first part of this work, we extend our previously proposed algorithmic framework, increasing the number of MOEAs, underlying evolutionary algorithms, and search paradigms that it comprises. These components can be combined following a general MOEA template, and an automatic configuration method is used to instantiate high-performing MOEA designs that optimize a given performance metric and present state-of-the-art performance. In the second part, we propose a multiobjective formulation for the automatic MOEA design, which proves critical for the context of many-objective optimization due to the disagreement of established performance metrics. Our proposed formulation leads to an automatically designed MOEA that presents state-of-the-art performance according to a set of metrics, rather than a single one.

Early works on external solution archiving have pointed out the benefits of unbounded archivers and there have been great advances, theoretical and algorithmic, in bounded archiving methods. Moreover, recent work has shown that the populations of most multi- and many-objective evolutionary algorithms (MOEAs) lack the properties that one would desire when trying to find a bounded Pareto-optimal front. Despite all these results, many recent MOEAs are still being proposed, analyzed and compared without considering any kind of archiver assuming their additional computational cost is not justified. In this paper, we investigate the effect of using various kinds of archivers, improving over previous studies in several aspects: (i) the parameters of MOEAs with and without an external archiver are tuned separately using automatic configuration methods; (ii) we consider a comprehensive range of problem scenarios (number of objectives, function evaluations, computation time limit); (iii) we employ multiple, complementary quality metrics; and (iv) we study the effect of unbounded archivers and two state-of-the-art bounded archiving methods. Our results show that both unbounded and bounded archivers are beneficial even for many-objective problems. We conclude that future proposals and comparisons of MOEAs must include archiving as an algorithmic component.

Adaptive Operator Selection (AOS) is an approach that controls discrete parameters of an Evolutionary Algorithm (EA) during the run. In this paper, we propose an AOS method based on Double Deep Q-Learning (DDQN), a Deep Reinforcement Learning method, to control the mutation strategies of Differential Evolution (DE). The application of DDQN to DE requires two phases. First, a neural network is trained offline by collecting data about the DE state and the benefit (reward) of applying each mutation strategy during multiple runs of DE tackling benchmark functions. We define the DE state as the combination of 99 different features and we analyze three alternative reward functions. Second, when DDQN is applied as a parameter controller within DE to a different test set of benchmark functions, DDQN uses the trained neural network to predict which mutation strategy should be applied to each parent at each generation according to the DE state. Benchmark functions for training and testing are taken from the CEC2005 benchmark with dimensions 10 and 30. We compare the results of the proposed DE-DDQN algorithm to several baseline DE algorithms using no online selection, random selection and other AOS methods, and also to the two winners of the CEC2005 competition. The results show that DE-DDQN outperforms the non-adaptive methods for all functions in the test set; while its results are comparable with the last two algorithms.

The configuration of algorithms is a laborious and difficult process. Thus, it is advisable to automate this task by using appropriate automatic configuration methods. The [Formula: see text] method is among the most widely used in the literature. By default, [Formula: see text] initializes its search process via uniform sampling of algorithm configurations. Although better initialization methods exist in the literature, the mixed-variable (numerical and categorical) nature of typical parameter spaces and the presence of conditional parameters make most of the methods not applicable in practice. Here, we present an improved initialization method that overcomes these limitations by employing concepts from the design and analysis of computer experiments with branching and nested factors. Our results show that this initialization method is not only better, in some scenarios, than the uniform sampling used by the current version of [Formula: see text], but also better than other initialization methods present in other automatic configuration methods.

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.

Research on multi-objective evolutionary algorithms (MOEAs) has produced over the past decades a large number of algorithms and a rich literature on performance assessment tools to evaluate and compare them. Yet, newly proposed MOEAs are typically compared against very few, often a decade older MOEAs. One reason for this apparent contradiction is the lack of a common baseline for comparison, with each subsequent study often devising its own experimental scenario, slightly different from other studies. As a result, the state of the art in MOEAs is a disputed topic. This article reports a systematic, comprehensive evaluation of a large number of MOEAs that covers a wide range of experimental scenarios. A novelty of this study is the separation between the higher-level algorithmic components related to multi-objective optimization (MO), which characterize each particular MOEA, and the underlying parameters-such as evolutionary operators, population size, etc.-whose configuration may be tuned for each scenario. Instead of relying on a common or "default" parameter configuration that may be low-performing for particular MOEAs or scenarios and unintentionally biased, we tune the parameters of each MOEA for each scenario using automatic algorithm configuration methods. Our results confirm some of the assumed knowledge in the field, while at the same time they provide new insights on the relative performance of MOEAs for many-objective problems. For example, under certain conditions, indicator-based MOEAs are more competitive for such problems than previously assumed. We also analyze problem-specific features affecting performance, the agreement between performance metrics, and the improvement of tuned configurations over the default configurations used in the literature. Finally, the data produced is made publicly available to motivate further analysis and a baseline for future comparisons.

Multiobjective evolutionary algorithms (MOEAs) are typically proposed, studied, and applied as monolithic blocks with a few numerical parameters that need to be set. Few works have studied how the algorithmic components of these evolutionary algorithms can be classified and combined to produce new algorithmic designs. The motivation for studies of this latter type stem from the development of flexible software frameworks and the usage of automatic algorithm configuration methods to find novel algorithm designs. In this paper, we propose an MOEA template and a new conceptual view of its components that surpasses existing frameworks in both number of algorithms that can be instantiated from the template and flexibility to produce novel algorithmic designs. We empirically demonstrate the flexibility of our proposed framework by automatically designing MOEAs for continuous and combinatorial optimization problems. The automatically designed algorithms are often able to outperform six traditional MOEAs from the literature, even after tuning their numerical parameters.

Multiobjective optimization problems are problems with several, typically conflicting, criteria for evaluating solutions. Without any a priori preference information, the Pareto optimality principle establishes a partial order among solutions, and the output of the algorithm becomes a set of nondominated solutions rather than a single one. Various ant colony optimization (ACO) algorithms have been proposed in recent years for solving such problems. These multiobjective ACO (MOACO) algorithms exhibit different design choices for dealing with the particularities of the multiobjective context. This paper proposes a formulation of algorithmic components that suffices to describe most MOACO algorithms proposed so far. This formulation also shows that existing MOACO algorithms often share equivalent design choices, but they are described in different terms. Moreover, this formulation is synthesized into a flexible algorithmic framework, from which not only existing MOACO algorithms may be instantiated, but also combinations of components that were never studied in the literature. In this sense, this paper goes beyond proposing a new MOACO algorithm, but it rather introduces a family of MOACO algorithms. The flexibility of the proposed MOACO framework facilitates the application of automatic algorithm configuration techniques. The experimental results presented in this paper show that the automatically configured MOACO framework outperforms the MOACO algorithms that inspired the framework itself. This paper is also among the first to apply automatic algorithm configuration techniques to multiobjective algorithms.

The usage of preference models in algorithms for multi-objective optimization has recently received an increasing attention by the research community. Motivated by this trend, we experimentally study the impact that the integration of preference models into evolutionary multi-objective search algorithms has on performance. In this article, we consider three preference models, ranging from rather simple to more complex ones; these are (i) reference point, (ii) guided dominance, and (iii) Promethee II. As a benchmark problem we consider multi-objective traveling salesman problem instances of various sizes and with a varying number of objectives.

The automatic configuration of algorithms is a dynamic field of research. Its potential for producing highly performing algorithms may change the way we design algorithms. So far, automatic algorithm configuration tools have almost exclusively been applied to configure single-objective algorithms. In this paper, we investigate the usage of automatic algorithm configuration tools to improve multi-objective algorithms. In fact, this is the first article we are aware of where state-of-the-art multi-objective optimizers are configured in an automatic way. This automatic configuration is done for five variants of multi-objective flow-shop problems. Our experimental results show that we can reach at least the same and often a better final quality than a recently proposed state-of-the-art algorithm for these problems.

Reducing the energy consumption of water distribution networks has never had more significance. The greatest energy savings can be obtained by carefully scheduling the operations of pumps. Schedules can be defined either implicitly, in terms of other elements of the network such as tank levels; or explicitly, by specifying the time during which each pump is on/off. The traditional representation of explicit schedules is a string of binary values with each bit representing pump on/off status during a particular time interval. In this paper, we formally define and analyze two new explicit representations based on time-controlled triggers, where the maximum number of pump switches is established beforehand and the schedule may contain fewer than the maximum number of switches. In these representations, a pump schedule is divided into a series of integers with each integer representing the number of hours for which a pump is active/inactive. This reduces the number of potential schedules compared to the binary representation, and allows the algorithm to operate on the feasible region of the search space. We propose evolutionary operators for these two new representations. The new representations and their corresponding operations are compared with the two most-used representations in pump scheduling, namely, binary representation and level-controlled triggers. A detailed statistical analysis of the results indicates which parameters have the greatest effect on the performance of evolutionary algorithms. The empirical results show that an evolutionary algorithm using the proposed representations is an improvement over the results obtained by a recent state of the art hybrid genetic algorithm for pump scheduling using level-controlled triggers.

MAX-MIN Ant System (MMAS) is an ant colony optimization (ACO) algorithm that was originally designed to start with a very explorative search phase and then to make a slow transition to an intensive exploitation of the best solutions found during the search. This design leads to a rather slow initial convergence of the algorithm, and, hence, to poor results if the algorithm does not run for sufficient time. This article illustrates that varying the parameter settings of MMAS while solving an instance may significantly improve the anytime search behavior of MMAS. Even rather simple pre-scheduled variations of the parameter settings that only depend on the number of iterations or the computation time show improvement over fixed parameter settings. The degree of improvement, however, is not uniform across problems. In particular, the improvement is very strong in the traveling salesman problem (TSP) but small, if at all noticeable, in the quadratic assignment problem (QAP). This paper also presents an adaptive parameter variation specifically designed for the TSP. The experimental results show that the pre-scheduled variations are comparable to the proposed adaptive variation in terms of the anytime behavior of MMAS.

Over the last few years, there have been a number of proposals of ant colony optimization (ACO) algorithms for tackling multiobjective combinatorial optimization problems. These proposals adapt ACO concepts in various ways, for example, some use multiple pheromone matrices and multiple heuristic matrices and others use multiple ant colonies.

The goal of multiobjective optimization is to find a set of best compromise solutions for typically conflicting objectives. Due to the complex nature of most real-life problems, only an approximation to such an optimal set can be obtained within reasonable (computing) time. To compare such approximations, and thereby the performance of multiobjective optimizers providing them, unary quality measures are usually applied. Among these, thehypervolume indicator(orS-metric) is of particular relevance due to its favorable properties. Moreover, this indicator has been successfully integrated into stochastic optimizers, such as evolutionary algorithms, where it serves as a guidance criterion for finding good approximations to the Pareto front. Recent results show that computing the hypervolume indicator can be seen as solving a specialized version of Klee's Measure Problem. In general, Klee's Measure Problem can be solved with${\cal O}(n \log n + n^{d/2}\log n)$comparisons for an input instance of size$n$in$d$dimensions; as of this writing, it is unknown whether a lower bound higher than$\Omega (n \log n)$can be proven. In this paper, we derive a lower bound of$\Omega (n\log n)$for the complexity of computing the hypervolume indicator in any number of dimensions$d≫1$by reducing the so-calleduniformgapproblem to it. For the 3-D case, we also present a matching upper bound of${\cal O}(n\log n)$comparisons that is obtained by extending an algorithm for finding the maxima of a point set.

a water distribution network, where customer demands, initial tank levels and electricity tariffs are known, the goal is to find the optimal pump schedule over a time period, typically 24 hours, such that the cost of energy consumed by pumps (CE) and maintenance costs are minimised and constraints are satisfied. The electricity tariff is typically divided into an expensive peak and cheaper off-peak periods, while the actual amount of energy consumed by a pump depends on several dynamic factors. For a given schedule, its energy cost can be calculated using a hydraulic simulator (EPANET [1] in our case). On the other hand, maintenance costs are typically assumed to increase with the number of pump switches (NS), since frequent switching, that is, turning on a pump which was previously off, causes wear and tear. Typically, this objective is incorporated

This paper presents a recursive, dimension-sweep algorithm for computing the hypervolume indicator of the quality of a set of n non-dominated points in d > 2 dimensions. It improves upon the existing HSO (Hypervolume by Slicing Objectives) algorithm by pruning the recursion tree to avoid repeated dominance checks and the recalculation of partial hypervolumes. Additionally, it incorporates a recent result for the three-dimensional special case. The proposed algorithm achieves O(nd−2log n) time and linear space complexity in the worst-case, but experimental results show that the pruning techniques used may reduce the time complexity exponent even further.

Significant operational cost and energy savings can be achieved by optimising the schedules of pumps, which pump water from source reservoirs to storage tanks, in water distribution networks. Despite the fact that pump scheduling problem involves several conflictive objectives, few studies have considered multi-objective optimisation in terms of Pareto optimality. Our approach links a well-known multi-objective optimiser, SPEA2, with a hydraulic simulator, EPANET, in order to provide a Pareto set of explicit schedules. Since only fixed speed pumps and fixed time intervals are considered, we use a natural binary representation and simple and straightforward initialisation and recombination operators. Unlike earlier studies, feasibility constraints are handled by a methodology based on the dominance relation rather than using penalty functions or reparation mechanisms. We test the proposed approach using a network instance and an assessment of the results is carried out by means of empirical attainment surfaces. The results show that the proposed approach is able to obtain better schedules than the state-of-the-art single-objective algorithm for this network instance and within the same number of function evaluations.