Parallel Problem Solving from Nature – PPSN XV

The CMA-ES is one of the most powerful stochastic numerical optimizers to address difficult black-box problems. Its intrinsic time and space complexity is quadratic—limiting its applicability with increasing problem dimensionality. To circumvent this limitation, different large-scale variants of CMA-ES with subquadratic complexity have been proposed over the past ten years. To-date however, these variants have been tested and compared only in rather restrictive settings, due to the lack of a comprehensive large-scale testbed to assess their performance. In this context, we introduce a new large-scale testbed with dimension up to 640, implemented within the COCO benchmarking platform. We use this testbed to assess the performance of several promising variants of CMA-ES and the standard limited-memory L-BFGS. In all tested dimensions, the best CMA-ES variant solves more problems than L-BFGS for larger budgets while L-BFGS outperforms the best CMA-ES variant for smaller budgets. However, over all functions, the cumulative runtime distributions between L-BFGS and the best CMA-ES variants are close (less than a factor of 4 in high dimension).Our results illustrate different scaling behaviors of the methods, expose a few defects of the algorithms and reveal that for dimension larger than 80, LM-CMA solves more problems than VkD-CMA while in the cumulative runtime distribution over all functions the VkD-CMA dominates LM-CMA for budgets up to $$10^4$$ 10 4 times dimension and for all budgets up to dimension 80.

Surrogate models are employed in evolutionary algorithms to replace expensive objective function evaluations with cheaper though usually inaccurate estimates based on information gained in past iterations. Implications of the trade-off between computational savings on the one hand and potentially poor steps due to the inaccurate assessment of candidate solutions on the other are generally not well understood. We study the trade-off in the context of a surrogate model assisted $$(1+1)$$ ( 1 + 1 ) -ES by considering a simple model for single steps. Based on the insights gained, we propose a step size adaptation mechanism for the strategy and experimentally evaluate it using several test functions.

This paper presents a generalized view on the family of swarm optimization algorithms. Paper focuses on a few distinct variants of the Particle Swarm Optimization and also incorporates one type of Differential Evolution algorithm as a particle’s behavior. Each particle type is treated as an agent enclosed in a framework imposed by a basic PSO. Those agents vary on the velocity update procedure and utilized neighborhood. This way, a hybrid swarm optimization algorithm, consisting of a heterogeneous set of particles, is formed. That set of various optimization agents is governed by an adaptation scheme, which is based on the roulette selection used in evolutionary approaches. The proposed Generalized Self-Adapting Particle Swarm Optimization algorithm performance is assessed a well-established BBOB benchmark set and proves to be better than any of the algorithms its incorporating.

In this paper, we study Particle Swarm Optimization (PSO) as a collective search mechanism for individuals (such as aerial micro-robots) which are supposed to search in environments with unknown external dynamics. In order to deal with the unknown disturbance, we present new PSO equations which are evolved using Genetic Programming (GP) with a semantically diverse starting population, seeded by the Evolutionary Demes Despeciation Algorithm (EDDA), that generalizes better than standard GP in the presence of unknown dynamics. The analysis of the evolved equations shows that with only small modifications in the velocity equation, PSO can achieve collective search behavior while being unaware of the dynamic external environment, mimicking the zigzag upwind flights of birds towards the food source.

Recent work has shown that significant performance gains over state-of-the-art CMA-ES variants can be obtained by a recombination of their algorithmic modules. It seems plausible that further improvements can be realized by an adaptive selection of these configurations. We address this question by quantifying the potential performance gain of such an online algorithm selection approach. In particular, we study the advantage of structurally adaptive CMA-ES variants on the functions F1, F10, F15, and F20 of the BBOB test suite. Our research reveals that significant speedups might be possible for these functions. Quite notably, significant performance gains might already be possible by adapting the configuration only once. More precisely, we show that for the tested problems such a single configuration switch can result in performance gains of up to $$22\%$$ . With such a significant indication for improvement potential, we hope that our results trigger an intensified discussion of online structural algorithm configuration for CMA-ES variants.

Network flow optimisation has many real-world applications. The minimum cost flow problem (MCFP) is one of the most common network flow problems. Mathematical programming methods often assume the linearity and convexity of the underlying cost function, which is not realistic in many real-world situations. Solving large-sized MCFPs with nonlinear non-convex cost functions poses a much harder problem. In this paper, we propose a new representation scheme for solving non-convex MCFPs using genetic algorithms (GAs). The most common representation scheme for solving the MCFP in the literature using a GA is priority-based encoding, but it has some serious limitations including restricting the search space to a small part of the feasible set. We introduce a probabilistic tree-based representation scheme (PTbR) that is far superior compared to the priority-based encoding. Our extensive experimental investigations show the advantage of our encoding compared to previous methods for a variety of cost functions.

The Cyclic Bandwidth Sum Problem (CBSP) is an NP-Hard Graph Embedding Problem which aims to embed a simple, finite graph (the guest) into a cycle graph of the same order (the host) while minimizing the sum of cyclic distances in the host between guest’s adjacent nodes. This paper presents preliminary results of our research on the design of a Memetic Algorithm (MA) able to solve the CBSP. A total of 24 MA versions, induced by all possible combinations of four selection schemes, two operators for recombination and three for mutation, were tested over a set of 25 representative graphs. Results compared with respect to the state-of-the-art top algorithm showed that all the tested MA versions were able to consistently improve its results and give us some insights on the suitability of the tested operators.

The Lin-Kernighan-Helsgaun (LKH) algorithm is one of the most successful search algorithms for the Traveling Salesman Problem (TSP). The core of LKH is a variable depth local search heuristic developed by Lin and Kernighan (LK). Several improvements have been incorporated to LKH along the years. The best results reported in the literature were obtained by an iterative local search version known as multi-trial LKH. In multi-trial LKH, solutions generated by soft restarts of the LK heuristic are recombined using Iterative Partial Transcription (IPT). We show that IPT can be classified as a partition crossover. Partition crossovers use the features common to the parents to decompose the evaluation function. Recently, a new generalized partition crossover, known as GPX2, was proposed for the TSP. We investigate the use of GPX2 in multi-trial LKH and compare it to multi-trial LKH using IPT. Results of experiments with 11 large instances of the TSP indicate that LKH with GPX2 outperforms LKH with IPT in most of the instances, but not in all of them.

The Escherization problem is that, given a goal figure, find a closed figure that is as close as possible to the goal figure and tiles the plane. In the Koizumi and Sugihara’s formulation for the Escherization problem, the tile and goal shapes are represented as polygons whose similarity is evaluated by the Procrustes distance. In this paper, we incorporate a new distance function into their formulation, aiming at finding more satisfiable tile shapes. The proposed distance function successfully picks up tile shapes that are intuitively similar to the goal shape even when they are somewhat different from the goal shape in terms of the Procrustes distance. Due to the high computational cost for solving the formulated problem, we develop a tabu search algorithm to tackle this problem.

Orthogonal Arrays (OA) represent an interesting breed of combinatorial designs that finds applications in several domains such as statistics, coding theory, and cryptography. In this work, we address the problem of constructing binary OA through evolutionary algorithms, an approach which received little attention in the combinatorial designs literature. We focus on the representation of a feasible solution, which we encode as a set of Boolean functions whose truth tables are used as the columns of a binary matrix, and on the design of an appropriate fitness function and variation operators for this problem. We finally present experimental results obtained with genetic algorithms (GA) and genetic programming (GP) on optimizing such fitness function, and compare the performances of these two metaheuristics with respect to the size of the considered problem instances. The experimental results show that GP outperforms GA at handling this type of problem, as it converges to an optimal solution in all considered problem instances but one.

A core feature of evolutionary algorithms is their mutation operator. Recently, much attention has been devoted to the study of mutation operators with dynamic and non-uniform mutation rates. Following up on this line of work, we propose a new mutation operator and analyze its performance on the (1+1) Evolutionary Algorithm (EA). Our analyses show that this mutation operator competes with pre-existing ones, when used by the (1+1) EA on classes of problems for which results on the other mutation operators are available. We present a “jump” function for which the performance of the (1+1) EA using any static uniform mutation and any restart strategy can be worse than the performance of the (1+1) EA using our mutation operator with no restarts. We show that the (1+1) EA using our mutation operator finds a (1/3)-approximation ratio on any non-negative submodular function in polynomial time. This performance matches that of combinatorial local search algorithms specifically designed to solve this problem.Finally, we evaluate experimentally the performance of the (1+1) EA using our operator, on real-world graphs of different origins with up to $$\sim $$ ∼ 37 000 vertices and $$\sim $$ ∼ 1.6 million edges. In comparison with uniform mutation and a recently proposed dynamic scheme our operator comes out on top on these instances.

The recently introduced permutation Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA) has shown to be an effective Model Based Evolutionary Algorithm (MBEA) for permutation problems. So far, permutation GOMEA has only been used in the context of Black-Box Optimization (BBO). This paper first shows that permutation GOMEA can be improved by incorporating a constructive heuristic to seed the initial population. Secondly, the paper shows that hybridizing with job swapping neighborhood search does not lead to consistent improvement. The seeded permutation GOMEA is compared to a state-of-the-art algorithm (VNS4) for solving the Permutation Flowshop Scheduling Problem (PFSP). Both unstructured and structured instances are used in the benchmarks. The results show that permutation GOMEA often outperforms the VNS4 algorithm for the PFSP with the total flowtime criterion.

Evolutionary algorithms are bio-inspired algorithms that can easily adapt to changing environments. In this paper, we study single- and multi-objective baseline evolutionary algorithms for the classical knapsack problem where the capacity of the knapsack varies over time. We establish different benchmark scenarios where the capacity changes every $$\tau $$ τ iterations according to a uniform or normal distribution. Our experimental investigations analyze the behavior of our algorithms in terms of the magnitude of changes determined by parameters of the chosen distribution, the frequency determined by $$\tau $$ τ and the class of knapsack instance under consideration. Our results show that the multi-objective approaches using a population that caters for dynamic changes have a clear advantage on many benchmarks scenarios when the frequency of changes is not too high.

Hyper-heuristic frameworks, although intended to be cross-domain at the highest level, rely on a set of domain-specific low-level heuristics at lower levels. For some domains, there is a lack of available heuristics, while for novel problems, no heuristics might exist. We address this issue by introducing a novel method, applicable in multiple domains, that constructs new low-level heuristics for a domain. The method uses grammatical evolution to construct iterated local search heuristics: it can be considered cross-domain in that the same grammar can evolve heuristics in multiple domains without requiring any modification, assuming that solutions are represented in the same form. We evaluate the method using benchmarks from the travelling-salesman (TSP) and multi-dimensional knapsack (MKP) domain. Comparison to existing methods demonstrates that the approach generates low-level heuristics that outperform heuristic methods for TSP and are competitive for MKP.

For any population-based algorithm, the initialization of the population is a very important step. In Genetic Programming (GP), in particular, initialization is known to play a crucial role - traditionally, a wide variety of trees of various sizes and shapes are desirable. In this paper, we propose an advancement of a previously conceived Evolutionary Demes Despeciation Algorithm (EDDA), inspired by the biological phenomenon of demes despeciation. In the pioneer design of EDDA, the initial population is generated using the best individuals obtained from a set of independent subpopulations (demes), which are evolved for a few generations, by means of conceptually different evolutionary algorithms - some use standard syntax-based GP and others use a semantics-based GP system. The new technique we propose here (EDDA-V2), imposes more diverse evolutionary conditions - each deme evolves using a distinct random sample of training data instances and input features. Experimental results show that EDDA-V2 is a feasible initialization technique: populations converge towards solutions with comparable or even better generalization ability with respect to the ones initialized with EDDA, by using significantly reduced computational time.

Program synthesis is a problem domain that due to its importance is tackled by many different fields, one being Genetic Programming. Two variants, Grammar-Guided Genetic Programming (G3P) and PushGP, have been applied to a vast general program synthesis benchmark suite and solved a variety of problems although with varying success rates. While G3P achieved higher success rates on some problems, PushGP was able to find solutions to more problem instances. Reason why G3P fails at some problems might be missing functionality in the grammars or knowledge that has to discovered during the runs. In this paper the current shortcomings of G3P are analysed and the papers contributions include an example of extending grammars for program synthesis, a fairer comparison between PushGP and G3P with a more similar function set as well as new results on problems that have not been solved with G3P and one that has not been solved with PushGP.

Outliers are one of the most difficult issues when dealing with real-world modeling tasks. Even a small percentage of outliers can impede a learning algorithm’s ability to fit a dataset. While robust regression algorithms exist, they fail when a dataset is corrupted by more than 50% of outliers (breakdown point). In the case of Genetic Programming, robust regression has not been properly studied. In this paper we present a method that works as a filter, removing outliers from the target variable (vertical outliers). The algorithm is simple, it uses a randomly generated population of GP trees to determine which target values should be labeled as outliers. The method is highly efficient. Results show that it can return a clean dataset when contamination reaches as high as 90%, and may be able to handle higher levels of contamination. In this study only synthetic univariate benchmarks are used to evaluate the approach, but it must be stressed that no other approaches can deal with such high levels of outlier contamination while requiring such small computational effort.

Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA) is a recent Evolutionary Algorithm (EA) in which the interactions among parts of the solution (i.e., the linkage) are learned and exploited in a novel variation operator. We present GOMGE, the extension of GOMEA to Grammatical Evolution (GE), a popular EA based on an indirect representation which may be applied to any problem whose solutions can be described using a context-free grammar (CFG). GE is a general approach that does not require the user to tune the internals of the EA to fit the problem at hand: there is hence the opportunity for benefiting from the potential of GOMEA to automatically learn and exploit the linkage. We apply the proposed approach to three variants of GE differing in the representation (original GE, SGE, and WHGE) and incorporate in GOMGE two specific improvements aimed at coping with the high degeneracy of those representations. We experimentally assess GOMGE and show that, when coupled with WHGE and SGE, it is clearly beneficial to both effectiveness and efficiency, whereas it delivers mixed results with the original GE.

The runtime performance of many evolutionary algorithms depends heavily on their parameter values, many of which are problem specific. Previous work has shown that the modification of parameter values at runtime can lead to significant improvements in performance. In this paper we discuss both the ‘when’ and ‘how’ aspects of implementing self-adaptation in a Genetic Programming system, focusing on the crossover operator. We perform experiments on Tartarus Problem instances and find that the runtime modification of crossover parameters at the individual level, rather than population level, generate solutions with superior performance, compared to traditional crossover methods.

This paper proposes a novel decomposition-based evolutionary algorithm for multi-modal multi-objective optimization, which is the problem of locating as many as possible (almost) equivalent Pareto optimal solutions. In the proposed method, two or more individuals can be assigned to each decomposed subproblem to maintain the diversity of the population in the solution space. More precisely, a child is assigned to a subproblem whose weight vector is closest to its objective vector, in terms of perpendicular distance. If the child is close to one of individuals that have already been assigned to the subproblem in the solution space, the replacement selection is performed based on their scalarizing function values. Otherwise, the child is newly assigned to the subproblem, regardless of its quality. The effectiveness of the proposed method is evaluated on seven problems. Results show that the proposed algorithm is capable of finding multiple equivalent Pareto optimal solutions.

Multi-modal multi-objective optimization problems are commonly seen in real-world applications. However, most existing researches focus on solving multi-objective optimization problems without multi-modal property or multi-modal optimization problems with single objective. In this paper, we propose a double-niched evolutionary algorithm for multi-modal multi-objective optimization. The proposed algorithm employs a niche sharing method to diversify the solution set in both the objective and decision spaces. We examine the behaviors of the proposed algorithm and its two variants as well as three other existing evolutionary optimizers on three types of polygon-based problems. Our experimental results suggest that the proposed algorithm is able to find multiple Pareto optimal solution sets in the decision space, even if the diversity requirements in the objective and decision spaces are inconsistent or there exist local optimal areas in the decision space.

Over the years, many interactive multiobjective optimization methods based on a reference point have been proposed. With a reference point, the decision maker indicates desirable objective function values to iteratively direct the solution process. However, when analyzing the performance of these methods, a critical issue is how to systematically involve decision makers. A recent approach to this problem is to replace a decision maker with an artificial one to be able to systematically evaluate and compare reference point based interactive methods in controlled experiments. In this study, a new artificial decision maker is proposed, which reuses the dynamics of particle swarm optimization for guiding the generation of consecutive reference points, hence, replacing the decision maker in preference articulation. We use the artificial decision maker to compare interactive methods. We demonstrate the artificial decision maker using the DTLZ benchmark problems with 3, 5 and 7 objectives to compare R-NSGA-II and WASF-GA as interactive methods. The experimental results show that the proposed artificial decision maker is useful and efficient. It offers an intuitive and flexible mechanism to capture the current context when testing interactive methods for decision making.

For multiobjective optimization problems with uncertain parameters in the objective functions, different variants of minmax robustness concepts have been defined in the literature. The idea of minmax robustness is to optimize in the worst case such that the solutions have the best objective function values even when the worst case happens. However, the computation of the minmax robust Pareto optimal solutions remains challenging. This paper proposes a simple indicator based evolutionary algorithm for robustness (SIBEA-R) to address this challenge by computing a set of non-dominated set-based minmax robust solutions. In SIBEA-R, we consider the set of objective function values in the worst case of each solution. We propose a set-based non-dominated sorting to compare the objective function values using the definition of lower set less order for set-based dominance. We illustrate the usage of SIBEA-R with two example problems. In addition, utilization of the computed set of solutions with SIBEA-R for decision making is also demonstrated. The SIBEA-R method shows significant promise for finding non-dominated set-based minmax robust solutions.

The Speed-constrained Multi-objective PSO (SMPSO) is an approach featuring an external bounded archive to store non-dominated solutions found during the search and out of which leaders that guide the particles are chosen. Here, we introduce SMPSO/RP, an extension of SMPSO based on the idea of reference point archives. These are external archives with an associated reference point so that only solutions that are dominated by the reference point or that dominate it are considered for their possible addition. SMPSO/RP can manage several reference point archives, so it can effectively be used to focus the search on one or more regions of interest. Furthermore, the algorithm allows interactively changing the reference points during its execution. Additionally, the particles of the swarm can be evaluated in parallel. We compare SMPSO/RP with respect to three other reference point based algorithms. Our results indicate that our proposed approach outperforms the other techniques with respect to which it was compared when solving a variety of problems by selecting both achievable and unachievable reference points. A real-world application related to civil engineering is also included to show up the real applicability of SMPSO/RP.

1by1EA is a competitive method among existing many-objective evolutionary algorithms. However, we find that it may fail to find boundary solutions depending on the Pareto front shape. In this study, we present an improved version of 1by1EA, named 1by1EA-II, to enhance the flexibility in handling various shapes of Pareto fronts. In 1by1EA-II, the Chebyshev distances from a solution to the nadir and ideal points are alternately employed as two convergence indicators. Using the first convergence indicator, boundary solutions are preferred for a wide spread in the objective space. With the other convergence indicator, non-boundary solutions are preferred to promote diversity. We empirically compare the proposed 1by1EA-II with its original version as well as four other state-of-the-art algorithms on DTLZ and Minus-DTLZ test problems. The results show that 1by1EA-II is the most flexible algorithm.

Given the availability of high-performing local search (LS) for single-objective (SO) optimisation problems, a successful approach to tackle their multi-objective (MO) counterparts is scalarisation-based local search (SBLS). SBLS strategies solve multiple scalarisations, aggregations of the multiple objectives into a single scalar value, with varying weights. They have been shown to work specially well as the initialisation phase of other types of MO local search, e.g., Pareto local search (PLS). A drawback of existing SBLS strategies is that the underlying SO-LS method is unaware of the MO nature of the problem and returns only a single solution, discarding any intermediate solutions that may be of interest. We propose here two new SBLS initialisation strategies (ChangeRestart and ChangeDirection) that overcome this drawback by augmenting the underlying SO-LS method with an archive of nondominated solutions used to dynamically update the scalarisations. The new strategies produce better results on the bi-objective permutation flowshop problem than other five SBLS strategies from the literature, not only on their own but also when used as the initialisation phase of PLS.

Recently, it has been shown that the current Many-Objective Evolutionary Algorithms (MaOEAs) are overspecialized in solving certain benchmark problems. This overspecialization is due to a high correlation between the Pareto fronts of the test problems with the convex weight vectors commonly used by MaOEAs. The main consequence of such overspecialization is the inability of these MaOEAs to solve the minus versions of well-known benchmarks (e.g., the DTLZ $$^{-1}$$ - 1 test suite). In furtherance of avoiding this issue, we propose a novel steady-state MaOEA that does not require weight vectors and uses a density estimator based on the IGD $$^+$$ + indicator. Moreover, a fast method to calculate the IGD $$^+$$ + contributions is integrated in order to reduce the computational cost of the proposed approach, which is called IGD $$^+$$ + -MaOEA. Our proposed approach is compared with NSGA-III, MOEA/D, IGD $$^+$$ + -EMOA (the previous ones employ convex weight vectors) and SMS-EMOA on the test suites DTLZ and DTLZ $$^{-1}$$ - 1 , using the hypervolume indicator. Our experimental results show that IGD $$^+$$ + -MaOEA is a more general optimizer than MaOEAs that need a set of convex weight vectors and it is competitive and less computational expensive than SMS-EMOA.

We present an algorithm for non-dominated sorting that is suitable for large-scale multiobjective optimisation. This algorithm is a hybrid of two previously known algorithms: the divide-and-conquer algorithm initially proposed by Jensen, and the non-dominated tree algorithm proposed by Gustavsson and Syberfeldt.While possessing the good worst-case asymptotic behaviour of the divide-and-conquer algorithm, the proposed algorithm is also very efficient in practice. In our experimental study it is shown to outperform both of its parents on the majority of problem instances, both sampled uniformly from a hypercube and having a single front, with as large as $$10^6$$ 10 6 points and up to 15 objectives.

The multiobjective evolutionary algorithm based on decomposition (MOEA/D) converts a multiobjective optimization problem (MOP) into a set of simple subproblems, and deals with them simultaneously to approximate the Pareto optimal set (PS) of the original MOP. Normally in MOEA/D, a set of weight vectors are predefined and kept unchanged during the search process. In the last few years, it has been demonstrated in some cases that a set of predefined subproblems may fail to achieve a good approximation to the Pareto optimal set. The major reason is that it is usually unable to define a proper set of subproblems, which take full consideration of the characteristics of the MOP beforehand. Therefore, it is imperative to develop a way to adaptively redefine the subproblems during the search process. This paper proposes a tree-structured decomposition and adaptation (TDA) strategy to achieve this goal. The basic idea is to use a tree structure to decompose the search domain into a set of subdomains that are related with some subproblems, and adaptively maintain these subdomains by analyzing the search behaviors of MOEA/D in these subdomains. The TDA strategy has been applied to a variety of test instances. Experimental results show the advantages of TDA on improving MOEA/D in dealing with MOPs with different characteristics.

In recent years, decomposition-based multi-objective evolutionary algorithms (MOEAs) have gained increasing popularity. However, these MOEAs depend on the consistency between the Pareto front shape and the distribution of the reference weight vectors. In this paper, we propose a decomposition-based MOEA, which uses the modified Euclidean distance ( $$d^+$$ d + ) as a scalar aggregation function. The proposed approach adopts a novel method for approximating the reference set, based on an hypercube-based method, in order to adapt the reference set for leading the evolutionary process. Our preliminary results indicate that our proposed approach is able to obtain solutions of a similar quality to those obtained by state-of-the-art MOEAs such as MOMBI-II, NSGA-III, RVEA and MOEA/DD in several MOPs, and is able to outperform them in problems with complicated Pareto fronts.

Recently it was reported that the location of a reference point has a dominant effect on the optimal distribution of solutions for hypervolume maximization when multiobjective problems have inverted triangular Pareto fronts. This implies that the use of an appropriate reference point is indispensable when hypervolume-based EMO (evolutionary multiobjective optimization) algorithms are applied to such a problem. However, its appropriate reference point specification is difficult since it depends on various factors such as the shape of the Pareto front (e.g., triangular, inverted triangular), its curvature property (e.g., linear, convex, concave), the population size, and the number of objectives. To avoid this difficulty, we propose an idea of using two reference points: one is the nadir point, and the other is a point far away from the Pareto front. In this paper, first we demonstrate that the effect of the reference point is strongly problem-dependent. Next we propose an idea of using two reference points and its simple implementation. Then we examine the effectiveness of the proposed idea by comparing two hypervolume-based EMO algorithms: one with a single reference point and the other with two reference points.

Cloud-native applications add a layer of abstraction to the underlying distributed computing system, defining a high-level, self-scaling and self-managed architecture of different microservices linked by a messaging bus. Creating new algorithms that tap these architectural patterns and at the same time employ distributed resources efficiently is a challenge we will be taking up in this paper. We introduce KafkEO, a cloud-native evolutionary algorithms framework that is prepared to work with different implementations of evolutionary algorithms and other population-based metaheuristics by using micro-populations and stateless services as the main building blocks; KafkEO is an attempt to map the traditional evolutionary algorithm to this new cloud-native format. As far as we know, this is the first architecture of this kind that has been published and tested, and is free software and vendor-independent, based on OpenWhisk and Kafka. This paper presents a proof of concept, examines its cost, and tests the impact on the algorithm of the design around cloud-native and asynchronous system by comparing it on the well known BBOB benchmarks with other pool-based architectures, with which it has a remarkable functional resemblance. KafkEO results are quite competitive with similar architectures.

We consider the deployment of island-based evolutionary algorithms (EAs) on irregular computational environments plagued with different kind of glitches. In particular we consider the effect that factors such as network latency and transient process suspensions have on the performance of the algorithm. To this end, we have conducted an extensive experimental study on a simulated environment in which the performance of the island-based EA can be analyzed and studied under controlled conditions for a wide range of scenarios in terms of both the intensity of glitches and the topology of the island-based model (scale-free networks and von Neumann grids are considered). It is shown that the EA is resilient enough to withstand moderately high latency rates and is not significantly affected by temporary island deactivations unless a fixed time-frame is considered. Combining both kind of glitches has a higher toll on performance, but the EA still shows resilience over a broad range of scenarios.

The increasing demands on processing large-scale data from both industry and academia have boosted the emergence of data-intensive clustering computing platforms. Among them, Hadoop MapReduce has been widely adopted in the evolutionary computation community to implement a variety of parallel evolutionary algorithms, owing to its scalability and fault-tolerance. However, the recently proposed in-memory Spark clustering computing framework is more suitable for iterative computing than disk-based MapReduce and often boosts the speedup by several orders of magnitude. In this paper we will parallelize three mostly cited versions of particle swarm optimizers on Spark, in order to solve computationally expensive problems. First we will utilize the simple but powerful Amdahl’s law to analyze the master-slave model, that is, we do quantitative analysis based on Amdahl’s law to answer the question on which kinds of optimization problems the master-slave model could work well. Then we will design a publicly available Spark-based software framework which parallelizes three different particle swarm optimizers in a unified way. This new framework can not only simplify the development workflow of Spark-based parallel evolutionary algorithms, but also benefit from both functional programming and object-oriented programming. Numerical experiments on computationally expensive benchmark functions show that a super-linear speedup could be obtained via the master-slave model. All the source code are put at the complementary GitHub project for free access.

We propose PHYSH (Parallel HYbridization for Simple Heuristics), a framework to ease the design and implementation of hybrid metaheuristics via cooperative parallelism. With this framework, the user only needs encode each of the desired metaheuristics and may rely on PHYSH for parallelization, cooperation and hybridization. PHYSH supports the combination of population-based and single-solution metaheuristics and enables the user to control the tradeoff between intensification and diversification. We also provide an open-source implementation of this framework which we use to model the Quadratic Assignment Problem (QAP) with a hybrid solver, combining three metaheuristics. We present experimental evidence that PHYSH brings significant improvements over competing approaches, as witness the performance on representative hard instances of QAP.

Conditional preference networks (CP-nets) have recently emerged as a popular language capable of representing ordinal preference relations in a compact and structured manner. In the literature, CP-nets have been developed for modeling and reasoning in mainly toy-sized combinatorial problems, but rarely tested in real-world applications. Learning preferences expressed by passengers is an important topic in sustainable transportation and can be used to improve existing journey planning systems by providing personalized information to the passengers. Motivated by such needs, this paper studies the effect of using CP-nets in the context of personalized and context-aware journey planning. We present a case study where we learn to predict the journey choices by the passengers based on their historical choices in a multi-modal urban transportation network. The experimental results indicate the benefit of the conditional preference in passengers’ modeling in context-aware journey planning.

This paper proposes an efficient optimization method to solve the Chance Constrained Problem (CCP) described as the critical fractile formula. To approximate the Cumulative Distribution Function (CDF) in CCP with an improved empirical CDF, the truncated Halton sequence is proposed. A sample saving technique is also contrived to solve CCP by using Differential Evolution efficiently. The proposed method is applied to a practical engineering problem, namely the design of SAW filter.

Morphologically evolving robot systems need to include a learning period right after ‘birth’ to acquire a controller that fits the newly created body. In this paper, we investigate learning one skill in particular: walking in a given direction. To this end, we apply the HyperNEAT algorithm guided by a fitness function that balances the distance travelled in a direction and the deviation between the desired and the actually travelled directions. We validate this method on a variety of modular robots with different shapes and sizes and observe that the best controllers produce trajectories that accurately follow the correct direction and reach a considerable distance in the given test interval.

Workforce Scheduling and Routing Problems (WSRP) are very common in many practical domains, and usually have a number of objectives of interest to the end-user. Illumination algorithms such as Map-Elites (ME) have recently gained traction in application to design problems, in providing multiple diverse solutions as well as illuminating the solution space in terms of user-defined characteristics, but typically require significant computational effort to produce the solution archive. We investigate whether ME can provide an effective approach to solving WSRP, a repetitive problem in which solutions have to be produced quickly and often. The goals of the paper are two-fold. The first is to evaluate whether ME can provide solutions of competitive quality to an evolutionary algorithm in terms of a single objective function, and the second to examine its ability to provide a repertoire of solutions that maximise user choice. We find that very small computational budgets favour the EA in terms of quality, but ME outperforms the EA at larger budgets, provides a more diverse array of solutions, and lends insight to the end-user.

An iterative computer-aided ideation procedure is introduced, building on recent quality-diversity algorithms, which search for diverse as well as high-performing solutions. Dimensionality reduction is used to define a similarity space, in which solutions are clustered into classes. These classes are represented by prototypes, which are presented to the user for selection. In the next iteration, quality-diversity focuses on searching within the selected class. A quantitative analysis is performed on a 2D airfoil, and a more complex 3D side view mirror domain shows how computer-aided ideation can help to enhance engineers’ intuition while allowing their design decisions to influence the design process.

Wave energy is a widely available but still largely unexploited energy source, which has not yet reached full commercial development. A common design for a wave energy converter is called a point absorber (or buoy), which either floats on the surface or just below the surface of the water. Since a single buoy can only capture a limited amount of energy, large-scale wave energy production requires the deployment of buoys in large numbers called arrays. However, the efficiency of these arrays is affected by highly complex constructive and destructive intra-buoy interactions. We tackle the multi-objective variant of the buoy placement problem: we are taking into account the highly complex interactions of the buoys, while optimising critical design aspects: the energy yield, the necessary area, and the cable length needed to connect all buoys – while considering realistic wave conditions for the first time, i.e., a real wave spectrum and waves from multiple directions. To make the problem computationally feasible, we use sparse incomplete LU decomposition for solving systems of equations, and caching of integral computations. For the optimisation, we employ modern multi-objective solvers that are customised to the buoy placement problems. We analyse the wave field of final solutions to confirm the quality of the achieved layouts.

The tropical rainforests are the largest reserves of terrestrial carbon and therefore, the future of these rainforests is a question that is of immense importance in the geoscience research community. With the recent severe Amazonian droughts in 2005 and 2010 and on-going drought in the Congo region for more than two decades, there is growing concern that these forests could succumb to precipitation reduction, causing extensive carbon release and feedback to the carbon cycle. However, there is no single ecosystem model that quantifies the relationship between vegetation health in these rainforests and climatic factors. Small scale studies have used statistical correlation measure and simple linear regression to model climate-vegetation interactions, but suffer from the lack of comprehensive data representation as well as simplistic assumptions about dependency of the target on the covariates. In this paper we use genetic programming (GP) based symbolic regression for discovering equations that govern the vegetation climate dynamics in the rainforests. Expecting micro-regions within the rainforests to have unique characteristics compared to the overall general characteristics, we use a modified regression-tree based hierarchical partitioning of the space to build individual models for each partition. The discovery of these equations reveal very interesting characteristics about the Amazon and the Congo rainforests. Our method GP-tree shows that the rainforests exhibit tremendous resiliency in the face of extreme climatic events by adapting to changing conditions.