In real-world multi-objective optimization problems, it is common to find constraints that limit the feasible space, challenging the solver to explore the infeasible region and find good feasible solutions. Several evolutionary algorithms with various constraint-handling techniques have been proposed over the years. However, most focus on problems with continuous variables and constraints defined over the objective space and might not be suitable for binary problems and constraints defined on the decision space. This work proposes a multi-objective evolutionary algorithm for solving decision space-constrained multi-objective binary optimization problems. The proposed method can switch between a simple evolutionary algorithm, which optimizes constraint violation of infeasible solutions, and a random bit climber, which optimizes the objective functions of feasible solutions. We compare the performance of the proposed algorithm to other state-of-the-art evolutionary algorithms and study its behavior using SAT Constrained MNK-Landscapes. We show that the proposed algorithm can effectively optimize constraint violation of infeasible solutions, quickly find feasible solutions, and performs better than the compared algorithms in highly constrained problems with varying numbers of objectives, epistatic interactions, equality and inequality constraints, and constraint difficulty.

Game theory is a powerful tool for analyzing strategic interactions between rational agents and has been widely applied across fields such as economics, biology, and cybersecurity. In this paper, we propose a novel approach for estimating solutions to multiplayer games of simultaneous decision with continuous strategy sets, including those with infinitely many Nash Equilibria. Our method leverages the coevolution of multiple Evolutionary Algorithms (EAs): a single-objective EA models a single-objective player, while a Pareto dominance-based EA represents a multi-objective player. Each EA optimizes its player's strategies (decisions) through iterative gameplay. We analyze the key features that enable the proposed algorithm to estimate a Nash Equilibrium with minimal deviation from the analytical solution (which remains unknown to the algorithm) and to maintain stability near this solution. Experimental results show that the proposed algorithm converges to the nearest equilibrium with appropriate parameter tuning, including the secondary parent/survival selection criterion for the multi-objective EA, the fitness computation method, the mutation distribution index, and the mutation rate.

We present a novel extension to the game of FlipIt, introducing infrastructure costs and their impact on the at-tacker's success rate. This extension results in a simultaneous, continuous, multi-variable, multi-objective game, which we alge-braically solve in the case of periodic strategies. We then propose a novel fitness criterion for Co-Evolutionary Algorithms suitable for estimating Pure Strategy Nash Equilibria for such types of games. Afterward, we estimate solutions to the extended FlipIt game when game outcomes are evaluated both via analytical expectancy expressions and as the average of game simulations. The results demonstrate the effectiveness of the proposed framework for deterministic games and also hint towards its applications in stochastic games like FlipIt and even in broader multi-agent settings.

We study a distributed bit climbing algorithm for multi-objective optimization of binary problems. This algorithm decomposes the many-objective problem into a minimum number of single-objective problems, specified by the original evaluation functions and one additional scalarizing function that computes the solution hypervolume. Random bit climbers optimize sepa-rately their assigned single-objective function until they reach a local optimum and restart their search from a bounded population of non-dominated solutions collected from the solutions generated by all climbers. In this paper, we observe the climbing characteristics according to the restarting solution of the climbers to shed light on how they contribute to finding an approximation of the Pareto set. Also, we verify the effectiveness of the solution hypervolume as a scalarization function. We evaluate the method on subclasses of epistatic problems using MNK-landscapes, varying the number of objectives from 2 to 5 and the number of epistatic interactions from 1 to 20. We compare results with two popular decomposition-based multi-objective optimizers, showing that the simpler distributed bit climber performs better than the other optimizers in 2, 3, and 4 objective problems for most values of epistatic interactions.

Many-objective optimizers based on Pareto domi-nance and its extensions rely on the effectiveness of the diversity preservation mechanism embedded in survival selection to achieve good performance. This work proposes Repeated$\varepsilon$-Sampling, a survival selection method designed for elitist multi-objective algorithms to select a sample of well-distributed solutions in objective space from the non-dominated solutions set. The proposed method iteratively applies$\varepsilon$-Sampling, a procedure that uses$\varepsilon$-dominance to determine near solutions, increasing at each iteration the expansion rate used to compute$\varepsilon$-dominance, gradually eliminating near solutions in objective space, starting with the closest ones. Compared to an adaptive$\varepsilon$-Sampling method, we show that the proposed method improves the unifor-mity of the sample, leading to substantially better performance in many-objective epistatic problems in terms of convergence and diversity. We also show that a Pareto dominance-based many-objective optimizer with the proposed method finds Pareto sets with significantly better hypervolume than MOEA/D, a well-known decomposition-based algorithm.

This article reports using a bi-objective evolutionary algorithm interacting with a traffic simulator and data exploration methods to analyze the optimal capacity and location of charging infrastructure for electric vehicles. In this work, the focus of the study is the city of Cuenca, Ecuador. We configure a scenario with 20 candidate charging stations and 500 electric vehicles driving according to the mobility distribution observed in this city. We optimize the vehicle's travel time that requires recharging and the number of charging stations distributed in the city. Quality of Service is defined as the ratio of charged vehicles to vehicles waiting for a charge and is considered a constraint. The approximate Pareto set of solutions produced in our experiments includes a number of trade-off solutions to the formulated problem and shows that the evolutionary approach is a practical tool to find and study different layouts related to the location and capacities of charging stations. In addition, we complement the analysis of results by considering Quality of Service, charging time, and energy to determine the city's best locations. The proposed framework that combines simulated scenarios with evolutionary algorithms is a powerful tool to analyze and understand different charging station infrastructure designs.

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.

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.

There exist general transforms that convert pseudo-Boolean functions into k-bounded pseudo-Boolean functions, for all k ≥ 2. In addition to these general transforms, there can also exist specialized transforms that can be applied in special cases. New results are presented examining what happens to the "bit flip" neighborhood when transforms are applied. Transforms condense variables in a particular order. We show that different variable orderings produce different results in terms of problem difficulty. We also prove new results about the embedding of the original function in the new k-bounded function. Finally, this paper also looks at how parameter optimization problems can be expressed as high precision k-bounded pseudo-Boolean functions. This paper lays a foundation for the wider application of evolutionary algorithms to k-bounded pseudo-Boolean functions.

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.

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.

In multiobjective optimization, a scalable test problem is one that can be formulated for an arbitrary number of objectives. Scalable test problems evaluate the conceptual foundations of the so-called many-objective evolutionary algorithms. As an important class of problems, scalable test problems should contemplate a wide variety of features allowing us to evaluate and judge specific components of many-objective evolutionary algorithms. This, in fact, should promote the development of new strategies and/or methods in the design of many-objective optimization approaches. For this reason, the study of features and difficulties of this class of problems, plays a salient role in the development of many-objective approaches. As a result, a number of multiobjective scalable test problems have been proposed in recent years. In this paper, we present a review of features and limitations of existing multiobjective test problems formulated in continuous and unconstrained search spaces. We examine some features observed in some test problems which have not been properly discussed before. Additionally, we summarize a list of features and recommendations that should be considered in the design of scalable multiobjective test instances. Then, we preset a review of the state-of-the-art scalable test suites, including their features and limitations according to the recommended guidelines discussed herein. Finally, some possible paths for future research in this area are briefly discussed.

This paper proposes a series of new approaches to improve Generative Adversarial Network (GAN) for conditional image synthesis and we name the proposed model as "ArtGAN". One of the key innovation of ArtGAN is that, the gradient of the loss function w.r.t. the label (randomly assigned to each generated image) is back-propagated from the categorical discriminator to the generator. With the feedback from the label information, the generator is able to learn more efficiently and generate image with better quality. Inspired by recent works, an autoencoder is incorporated into the categorical discriminator for additional complementary information. Last but not least, we introduce a novel strategy to improve the image quality. In the experiments, we evaluate ArtGAN on CIFAR-10 and STL-10 via ablation studies. The empirical results showed that our proposed model outperforms the state-of-the-art results on CIFAR-10 in terms of Inception score. Qualitatively, we demonstrate that ArtGAN is able to generate plausible-looking images on Oxford-102 and CUB-200, as well as able to draw realistic artworks based on style, artist, and genre. The source code and models are available at: https://github.com/cs-chan/ArtGAN.

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.

Elitism is a common feature of many-objective optimizers and has a strong impact on the performance of the algorithms. The way elitism is implemented vary among the various approaches to many-objective optimization and there are no detailed studies about their effects. In this work we focus on a multi- and many-objective optimization approach based on ε-dominance. We track the number of generations a solution remains in the population to bias survival selection or the creation of neighborhoods for parent selection. We investigate how elitist strategies affect performance of the algorithm and show that convergence and diversity can be enhanced by using different strategies for elitism on many-objective uni-modal and multi-modal problems with 4, 5, and 6 objectives.

This work investigates levels of service in urban transportation coupling a multi-objective evolutionary algorithm with the multi-agent traffic simulator MATSim. The evolutionary algorithm searches combinations of number of private/public transportation users, capacity of buses, and time interval between bus departures minimizing traffic density, travel time and fuel consumption simultaneously. MATSim simulates the movement of 27.000 agents according to the solutions of the evolutionary algorithm on a model of the traffic network of Quito city. We study the trade-off in objectives and analyze the solutions produced to gain knowledge about the conditions to achieve different levels of service. Also, we analyze particulate matter emissions for the trade-off solutions. This work is useful for decision makers to suggest policies that can improve mobility combining private and public transportation.

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.

This paper proposes an extension to the Generative Adversarial Networks (GANs), namely as ArtGAN to synthetically generate more challenging and complex images such as artwork that have abstract characteristics. This is in contrast to most of the current solutions that focused on generating natural images such as room interiors, birds, flowers and faces. The key innovation of our work is to allow back-propagation of the loss function w.r.t. the labels (randomly assigned to each generated images) to the generator from the discriminator. With the feedback from the label information, the generator is able to learn faster and achieve better generated image quality. Empirically, we show that the proposed ArtGAN is capable to create realistic artwork, as well as generate compelling real world images that globally look natural with clear shape on CIFAR-10.

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.

Urban planners face increasing challenges to design and optimize sustainable cities. Evolutionary algorithms are an important tool for design optimization and can help urban planners finding alternative optimal designs to increase the sustainability of cities. Mobility and transportation are two important components of modern cities that are amenable to simulation and their design can be improved by evolutionary means. However, traffic simulation is computationally expensive and puts a serious constraint on the number of generations allowed to artificial evolution. In addition, to grasp the implication of traffic policies for sustainability usually a significant part of the traffic in the city must be simulated. This implies that we must design our evolutionary algorithms for an effective short-term evolution on large-scale problems. This paper investigates neighborhood mutation operators to explore efficiently in few generations a large space of cycle lengths, offsets and green time settings of traffic lights. Our aim is to find settings that allow a better coordination of signals. In addition, we analyze clusters of signal settings to gain knowledge about geographical coordination patterns to provide valuable information to city planners for micro-zonification.

In this paper, we analyze the behavior and compare the performance of three state-of-the-art Multi-objective Evolutionary Algorithms (MOEAs) based on three different approaches when solving the Multi-Objective Unit Commitment Problem (MO-UCP). Particularly, we study the performance of representative Pareto-, indicator- and decomposition-based MOEAs (namely NSGA-II, SMS-EMOA and MOEA/D) when solving standard MO-UCP test instances. The MOEAs employed in our comparative study, handle binary representation while lambda-iteration method is probabilistically used for assigning the economic/environmental power real dispatch. In our experiments, each evolutionary approach adopts the window crossover and the window mutation. A detailed study of the impact of these operators is carried out when different crossover and mutation ratios are employed. The comparative study presented here, shows that for low-dimensional instances, the performance of the three evolutionary approaches became very similar. However, when the dimension of the problem (large bit strings) increases, the performance of NSGA-II and SMS-EMOA became better than MOEA/D.

Due to its simplicity and effectiveness in solving many optimization problems, Particle Swarm Optimization (PSO) has attracted the attention of many researchers in the last few years. Nonetheless, in more complicated problems (involving multi-modality, non-separable, etc.), the use of PSO becomes limited and sometimes impractical. In this paper, we proposed an algorithm which is able to deal with optimization problems having several features. More specific, we introduce a refine mechanism into the evolutionary process of PSO for deep exploration of the local search space in which a particle is located. The proposed mechanism is inspired by the animal foraging behaviour, where searching is a mixture of systematic and random movements. In contrast to other existing PSO variants which aimed to improve the exploration ability by using random walk, the proposed approach exploits the locality of the particles by performing local variations in the flight of the individuals according to a Gaussian distribution. In our study, we analyze the effects of the proposed refinement mechanism when it is coupled into different PSO variants which are adopted in our experimental analysis. We show that our proposed approach not only was able to outperform the adopted PSO variants, but also was significantly better in most of the test functions employed in our comparative study.

There is a significant body of research on neutrality and its effects in single-objective optimization. Particularly, the neutrality concept has been precisely defined and the neutrality between neighboring solutions efficiently exploited in local search algorithms. The extension of neutrality to multi-objective optimization is not straightforward and its effects on the dynamics of multi-objective optimization methods are not clearly understood. In order to develop strategies to exploit neutral neighbors in multi-objective local search algorithms, it is important and necessary to clearly define neutrality in the multi-objective context. In this paper, we propose several definitions of the neutrality property between neighboring solutions. A natural definition comes from the Pareto-dominance, widely used in multi-objective optimization. In addition, definitions derived from epsilon and hypervolume indicators are also proposed as such indicators are usually used to compare sets of solutions. We analyze permutation problems under the proposed definitions of neutrality and show that each definition of neutrality leads to a particular structure of the problem.

Multi-objective evolutionary algorithms (MOEAs) based on decomposition are aggregation-based algorithms which transform a multi-objective optimization problem (MOP) into several single-objective subproblems. Being effective, efficient, and easy to implement, Particle Swarm Optimization (PSO) has become one of the most popular single-objective optimizers for continuous problems, and recently it has been successfully extended to the multi-objective domain. However, no investigation on the application of PSO within a multi-objective decomposition framework exists in the context of combinatorial optimization. This is precisely the focus of the paper. More specifically, we study the incorporation of Geometric Particle Swarm Optimization (GPSO), a discrete generalization of PSO that has proven successful on a number of single-objective combinatorial problems, into a decomposition approach. We conduct experiments on many-objective 1/0 knapsack problems i.e. problems with more than three objectives functions, substantially harder than multi-objective problems with fewer objectives. The results indicate that the proposed multi-objective GPSO based on decomposition is able to outperform two version of the well-know MOEA based on decomposition (MOEA/D) and the most recent version of the non-dominated sorting genetic algorithm (NSGA-III), which are state-of-the-art multi-objec\-tive evolutionary approaches based on decomposition.

In this article we work towards the desired future smart city in which IT and knowledge will hopefully provide a highly livable environment for citizens. To this end, we test a new concept based on intelligent LED panels (the Yellow Swarm) to guide drivers when moving through urban streets so as to finally get rid of traffic jams and protect the environment. This is a minimally invasive, low cost idea for the city that needs advanced simulations with real data coupled with new algorithms which perform well. Our proposal is to use evolutionary computation in the Yellow Swarm, which will finally help alleviate the traffic congestion, improve travel times, and decrease gas emissions, all at the same time and for a real case like the city of Quito (Ecuador).

“Ceci n'est pas une pipe” French for “This is not a pipe”. This is the description painted on the first painting in the figure above. But to most of us, how could this painting is not a pipe, at least not to the great Belgian surrealist artist Rene Magritte. He said that the painting is not a pipe, but rather an image of a pipe. In this paper, we present a study on large-scale classification of fine-art paintings using the Deep Convolutional Network. Our objectives are two-folds. On one hand, we would like to train an end-to-end deep convolution model to investigate the capability of the deep model in fine-art painting classification problem. On the other hand, we argue that classification of fine-art collections is a more challenging problem in comparison to objects or face recognition. This is because some of the artworks are non-representational nor figurative, and might requires imagination to recognize them. Hence, a question arose is that does a machine have or able to capture “imagination” in paintings? One way to find out is train a deep model and then visualize the low-level to high-level features learnt. In the experiment, we employed the recently publicly available large-scale “Wikiart paintings” dataset that consists of more than 80,000 paintings and our solution achieved state-of-the-art results (68%) in overall performance.

In spite of the success of the multi-objective evolutionary algorithm based on decomposition (MOEA/D), the generation of weights for problems having many objectives, continues to be an open research problem. In this paper, we introduce a new methodology based on low-discrepancy sequences to generate the weights vectors employed by MOEA/D. We analyze and compare the proposed methodology using different low-discrepancy sequences and its impact in the search process of MOEA/D. The proposed approach is evaluated in problems having many objective functions (up to 15 objectives). We show the flexibility and ease of use of this type of sequences when adopting them to generate the weights of MOEA/D.

Two preferred approaches to implement selection in many-objective optimization are based on scalarizing functions and ε-dominance. This work introduces a Chebyshev Achievement Function in the parent selection step of the Adaptive ε-Sampling ε-Hood many-objective optimizer and studies the combined effect of the exploitative power offered by the scalarizing function with the highly dynamic and explorative features of the many-objective optimizer. Two parent selection methods are investigated to exploit solutions closer to the ideal point of the dynamically changing neighborhoods created by the many-objective optimizer. These parent selection methods are compared with the random selection within the neighborhood method used by the original many-objective optimizer. The algorithms are tested using many-objective problems with unimodal and multimodal fitness functions, fixing the number of generations with various population sizes and fixing the number of evaluations using various combinations of number of generations and population size.

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.

Many multiobjective evolutionary algorithms rely on the nondominated sorting procedure to determine the relative quality of individuals with respect to the population. In this paper, we propose a new method to decrease the cost of this procedure. Our approach is to determine the nondominated individuals at the start of the evolutionary algorithm run and to update this knowledge as the population changes. In order to do this efficiently, we propose a special data structure called the M-front, to hold the nondominated part of the population. The M-front uses the geometric and algebraic properties of the Pareto dominance relation to convert orthogonal range queries into interval queries using a mechanism based on the nearest neighbor search. These interval queries are answered using dynamically sorted linked lists. Experimental results show that our method can perform significantly faster than the state-of-the-art Jensen-Fortin's algorithm, especially in many-objective scenarios. A significant advantage of our approach is that, if we change a single individual in the population we still know which individuals are dominated and which are not.

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.

Nondominated sorting and diversity estimation procedures are an essential part of many multiobjective optimization algorithms. In many cases these procedures are the computational bottleneck of the entire algorithm. We present the methods to decrease the cost of these procedures for multiobjective differential evolution (DE) algorithms. Our approach is to compute domination ranks and crowding distances for the population at the beginning of the algorithm and use a combination of well known data structures to efficiently update these attributes. Experiments show that the cost of improved nondominated sorting is sub-quadratic in the number of individuals. In practice using our methods the overall DE algorithm can run 2 to 100 times faster.

This work investigates two methods to search practically desirable solutions expanding the objective space with additional fitness functions associated to particular decision variables. The aim is to find solutions around preferred values of the chosen variables while searching for optimal solutions in the original objective space. Solutions to be practically desirable are constrained to be within a certain distance from the present non-dominated solutions set computed in the original objective space. The proposed methods are compared with an algorithm that simply restricts the range of decision variables around the preferred values and an algorithm that expands the space without constraining the distance from optimality. Our results show that the proposed methods can effectively find practically desirable solutions.

Self-controlling dominance area of solutions (S-CDAS) reclassifies solutions in each front obtained by non-domination sorting to realize fine-grained ranking of solutions and improve the search performance of multi-objective evolutionary algorithms (MOEAs) in many-objective optimization problems (MaOPs). In this work, we further improve search performance of S-CDAS in MaOPs by analyzing genetic diversity in many-objective problems and enhancing crossover operators. First, we analyze genetic diversity in the population and the contribution of the conventional genetic operators when we increase the number of objectives, showing that the genetic diversity in the population significantly increases and offspring created by conventional crossover come to be not selected as parents because the operator becomes too disruptive and its effectiveness decrease. To overcome this problem, we implement crossover controlling the number of crossed genes (CCG) in S-CDAS and verify its effectiveness. Through performance verification using many-objective knapsack problems with 4-10 objectives, we show that the search performance of S-CDAS noticeably improves when we restrict the number of crossed genes. Also, we show that the effectiveness of CCG operator becomes significant as we increase the number of objectives. Furthermore, we show that offspring created by CCG are selected as parents more often than conventional crossover.

This work investigates e-ranking and e-box non-domination sorting, two methods that incorporate e-dominance concepts to estimate density of solutions and control the number of rank-1 solution for many-objective optimization. We study how convergence and spread of solutions are affected by rankings that are based on local information of the distribution of solutions without considering closeness-to-dominance information. We also study the robustness of the methods to parameters settings, and how the methods react when extreme solutions are enforced or not. MNK-Landscapes are used as test problems in our study.

In this work, we propose a novel multi-objective evolutionary algorithm (MOEA) that uses Pareto partial dominance, which calculates dominance between solutions using only r objective functions selected from m objective functions to induce appropriate selection pressure in the evolution process of MOEA. Also, we temporally switch r objective functions amongmCrcombinations in every interval generations Igto optimize all of the objective functions throughout the entire evolution process. In this work, we use many-objective 0/1 knapsack problems to verify the search performance of the proposed Pareto partial dominance MOEA (PPD-MOEA). Simulation results show that there is an optimum value for the number of objective functions r to be considered in Pareto partial dominance, and the interval (generation numbers) Igto maximize the entire search performance. Also, the search performance of PPD-MOEA is superior to NSGA-II and recent state-of-the-art MOEAs, i.e., IBEA, CDAS and MSOPS. Additionally, to further enhance the search performance of PPD-MOEA, we propose a hybrid archiving strategy which uses both conventional NSGA-II and CDAS to select well-spread and well-converged solutions simultaneously when updating the archive population. Simulation results show that the hybrid archiving strategy further improves the search performance of PPD-MOEA by enhancing convergence while maintaining diversity in the archive population.

This work compares the performance among objective space partitioning with adaptive ε-ranking, subvector dominance assignment, and epsilon dominance assignment methods that have been recently proposed for many-objective optimization. These three methods enhance selection using different strategies to recalculate the primary or secondary ranking of solutions and have been implemented using the framework of NSGA-II. The first method focuses on the primary ranking of solutions by partitioning the objective space into lower dimensional subspaces and re-ranking solutions within each subspace using an adaptive epsilon-ranking procedure. On the other hand, the latter two methods focus on the secondary ranking of solutions, replacing crowding distance with a substitute assignment distance. As test problems, we use scalable MNK-Landscapes with 4 ‹ M ‹ 10 objectives, N=100 bits, varying the number of epistatic interactions per bit K in the range 0 ‹ K ‹ 50.

The proliferation of all kinds of devices with different security requirements and constraints, and the arms-race nature of the security problem are increasingly demanding the development of tools to help on the automatic design of Boolean functions with security application. Nowadays, the design of strong cryptographic Boolean functions is a multiobjective problem. However, so far evolutionary multiobjective algorithms have been largely overlooked and not much is known about this problem from a multiobjective optimization perspective. In this work we focus on non-linearity related criteria and explore a multiobjective evolutionary approach aiming to find several balanced functions of similar characteristics satisfying multiple criteria. We show that the multiobjective approach is an efficient alternative to single objective optimization approaches presented so far. We also argue that it is a better framework for automatic design of cryptographic Boolean functions.

In this paper, we propose δ-similar elimination to induce a better distribution of non-dominated solutions and distribute more fairly selection pressure among them in order to improve the search performance of multiobjective evolutionary algorithms in combinatorial optimization problems. With the proposed method similar individuals are eliminated in the process of evolution by using the distance between individuals in objective space. We investigate four eliminating methods to verify the effects of δ-similar elimination and compare the search performance of enhanced NSGA-II by our method and by controlled elitism, which emphasizes the inclusion of lateral diversity.

This work studies and compares the effects on performance of local dominance and local recombination applied with different locality in multiobjective evolutionary algorithms on combinatorial multiobjective problems. For this purpose, we introduce a method that creates a neighborhood around each individual and assigns a local dominance rank after rotating the principal search direction of the neighborhood by using polar coordinates in objective space. For recombination a different neighborhood determined around a random principle search direction is created. The neighborhood sizes for dominance and recombination are separately controlled by two different parameters. Experimental results show that the optimum locality of dominance is different from the optimum locality of recombination. Additionally, it is shown that the performance of the algorithm that applies local dominance and local recombination with different locality is significantly better than the performance of algorithms applying local dominance alone, local recombination alone, or dominance and recombination globally as conventional approaches do

The influence of epistasis on the performance of evolutionary algorithms (EAs) is being increasingly investigated for single objective combinatorial optimization problem. Kauffman's NK-landscapes model of epistatic interactions, particularly, has been the center of several studies and is considered as a good test problem generator. However, epistasis and NK-landscapes in the context of multiobjective evolutionary algorithm (MOEAs) are almost unexplored subjects. In this work we present an extension of Kauffman's NK-landscapes model of epistatic interactions to multiobjective MNK-landscapes. MNK-landscapes present several desirable features and hold the potential of becoming an important class of scalable test problems generator for multiobjective combinatorial optimization. In order to meaningfully use MNK-landscapes as a benchmark tool we first need to understand how the parameters of the landscapes relate to multiobjective concepts. This paper is a first step towards understanding the properties of MNK-landscapes from a multiobjective standpoint.

Epistasis and NK-landscapes in the context of multiobjective evolutionary algorithms (MOEAs) are almost unexplored subjects. We have presented an extension of Kauffman's NK-landscapes to multiobjective MNK-landscapes and gave some insights into their properties from a multiobjective standpoint. These properties allow us to meaningfully use MNK-landscapes as a benchmark tool and as a means to understand better the working principles of MOEAs. In this work we present four multiobjective random bit climbers (moRBCs) and use them to study the effects of elitism and population climbing on scalable random epistatic problems. Each moRBC implements a different kind of elitism in order to understand better its working principles. We conduct experiments on MNK-landscapes with M = {2, 3, 5} objectives, N = 100 bits, varying the epistatic interactions K from 0 to 50. Results by an elitist nondominated sorting multiobjective genetic algorithm (NSGA-II) are also included for comparison.

In this paper, we propose a calculation method of local dominance and enhance multiobjective evolutionary algorithms by performing a distributed search based on local dominance. In this method, we first transform all fitness vectors of individuals to polar coordinate vectors in the objective function space. Then we divide the population into several sub-populations by using declination angles. We calculate local dominance for individuals belonging to each sub-population based on the local search direction, and apply selection, recombination, and mutation to individual within each sub-population. We pick up NSGA-II and SPEA2 as two representatives of the latest generation of multiobjective evolutionary algorithms and enhance them with our model. We verify the effectiveness of the proposed method obtaining Pareto optimal solutions satisfying diversity conditions by comparing the search performance between the conventional algorithms and their enhanced versions.

We examine the behavior of a parallel varying mutation genetic algorithm (GA) on epistatic problems using NK-landscapes. We discuss properties of NK-landscapes and show that mutation strategy is an important factor to improve the performance of GAs on epistatic problems. The effect of (extinctive) selection is also highlighted. Similar to recent works, we conduct our study on relatively larger landscapes than previous studies in order to be a step closer to problems found in real world applications.

In previous work we have presented a model of genetic algorithm (GA) that applies varying mutations parallel to standard crossover & mutation putting them in a cooperative-competitive standing with each other (Aguirre et al., 1999). An improved GA based on this model (GA-SRM) using an adaptive mechanism for parallel mutation significantly improves the performance of GAs (Aguirre et al., 2001). Now, we introduce a self-adaptive mechanism within the parallel mutation operator of GA-SRM and show that the model is an appropriate framework to effectively use and develop further self-adaptation within GAs.

We have presented an empirical model of genetic algorithms (GA) that puts parallel genetic operators in a cooperative-competitive stand with each other. An improved GA (GA-SRM) based on this model remarkably improves the search performance of a single population GA. We extend GA-SRM to distributed GAs in order to improve the performance of multiple population GAs. Simulation results verify that the parallel genetic operators in GA-SRM, CM and SRM, can successfully contribute to improve the search performance of distributed GAs.

We extend an improved GA (GA-SRM) to the multi-objective flowshop scheduling problem (FSP) in order to obtain better pareto-optimum solutions (POS). Two kinds of cooperative-competitive genetic operators in GA-SRM, CM and SRM, are extended to ones suitable for FSP in which solutions (individuals) are represented as permutations. Simulation results verify that GA-SRM shows better performance for the multi-objective optimization problem (MOP), and consequently better POS are obtained than conventional approaches with canonical GA.