GECCO '21: Proceedings of the Genetic and Evolutionary Computation ConferenceFull Citation in the ACM Digital Library
SESSION: General evolutionary computation and hybrids
In the last two decades, significant effort has been made to solve computationally expensive optimization problems using surrogate models. Regardless of whether surrogates are the primary drivers of an algorithm or improve the convergence of an existing method, most proposed concepts are rather specific and not very generalizable. Some important considerations are selecting a baseline optimization algorithm, a suitable surrogate methodology, and the surrogate's involvement in the overall algorithm design. This paper proposes a probabilistic surrogate-assisted framework (PSAF), demonstrating its applicability to a broad category of single-objective optimization methods. The framework injects knowledge from a surrogate into an existing algorithm through a tournament-based procedure and continuing the optimization run on the surrogate's predictions. The surrogate's involvement is determined by updating a replacement probability based on the accuracy from past iterations. A study of four well-known population-based optimization algorithms with and without the proposed probabilistic surrogate assistance indicates its usefulness in achieving a better convergence. The proposed framework enables the incorporation of surrogates into an existing optimization algorithm and, thus, paves the way for new surrogate-assisted algorithms dealing with challenges in less frequently addressed computationally expensive functions, such as different variable types, large dimensional problems, multiple objectives, and constraints.
Most evolutionary algorithms have parameters, which allow a great flexibility in controlling their behavior and adapting them to new problems. To achieve the best performance, it is often needed to control some of the parameters during optimization, which gave rise to various parameter control methods. In recent works, however, similar advantages have been shown, and even proven, for sampling parameter values from certain, often heavy-tailed, fixed distributions. This produced a family of algorithms currently known as "fast evolution strategies" and "fast genetic algorithms".
However, only little is known so far about the influence of these distributions on the performance of evolutionary algorithms, and about the relationships between (dynamic) parameter control and (static) parameter sampling. We contribute to the body of knowledge by presenting an algorithm that computes the optimal static distributions, which describe the mutation operator used in the well-known simple (1+λ) evolutionary algorithm on a classic benchmark problem OneMax. We show that, for large enough population sizes, such optimal distributions may be surprisingly complicated and counter-intuitive. We investigate certain properties of these distributions, and also evaluate the performance regrets of the (1 + λ) evolutionary algorithm using standard mutation operators.
Accurately predicting the performance of different optimization algorithms for previously unseen problem instances is crucial for high-performing algorithm selection and configuration techniques. In the context of numerical optimization, supervised regression approaches built on top of exploratory landscape analysis are becoming very popular. From the point of view of Machine Learning (ML), however, the approaches are often rather naïve, using default regression or classification techniques without proper investigation of the suitability of the ML tools. With this work, we bring to the attention of our community the possibility to personalize regression models to specific types of optimization problems. Instead of aiming for a single model that works well across a whole set of possibly diverse problems, our personalized regression approach acknowledges that different models may suite different types of problems. Going one step further, we also investigate the impact of selecting not a single regression model per problem, but personalized ensembles. We test our approach on predicting the performance of numerical optimization heuristics on the BBOB benchmark collection.
We consider multi-solution optimization and generative models for the generation of diverse artifacts and the discovery of novel solutions. In cases where the domain's factors of variation are unknown or too complex to encode manually, generative models can provide a learned latent space to approximate these factors. When used as a search space, however, the range and diversity of possible outputs are limited to the expressivity and generative capabilities of the learned model. We compare the output diversity of a quality diversity evolutionary search performed in two different search spaces: 1) a predefined parameterized space and 2) the latent space of a variational autoencoder model. We find that the search on an explicit parametric encoding creates more diverse artifact sets than searching the latent space. A learned model is better at interpolating between known data points than at extrapolating or expanding towards unseen examples. We recommend using a generative model's latent space primarily to measure similarity between artifacts rather than for search and generation. Whenever a parametric encoding is obtainable, it should be preferred over a learned representation as it produces a higher diversity of solutions.
The impact of hyper-parameter tuning for landscape-aware performance regression and algorithm selection
Automated algorithm selection and configuration methods that build on exploratory landscape analysis (ELA) are becoming very popular in Evolutionary Computation. However, despite a significantly growing number of applications, the underlying machine learning models are often chosen in an ad-hoc manner.
We show in this work that three classical regression methods are able to achieve meaningful results for ELA-based algorithm selection. For those three models - random forests, decision trees, and bagging decision trees - the quality of the regression models is highly impacted by the chosen hyper-parameters. This has significant effects also on the quality of the algorithm selectors that are built on top of these regressions.
By comparing a total number of 30 different models, each coupled with 2 complementary regression strategies, we derive guidelines for the tuning of the regression models and provide general recommendations for a more systematic use of classical machine learning models in landscape-aware algorithm selection. We point out that a choice of the machine learning model merits to be carefully undertaken and further investigated.
We handle min-max black-box optimization problems in which the scenario variable to be maximized is discrete and the design variable to be minimized is a continuous vector. To reduce the number of objective function calls, which are assumed to be computationally expensive, we propose an approach that samples a subset of scenarios at each iteration to approximate the worst-case objective function and apply the covariance matrix adaptation evolution strategy to the approximated worst-case objective function. In addition, we develop an adaptation mechanism for the probability of sampling each scenario. Moreover, we introduce the notion of support scenarios to characterize min-max optimization problems with discrete scenario variables and design test problems with various characteristics of support scenarios. Empirical evaluations reveal that the proposed approach learns to sample the set of support scenarios, being more efficient than sampling all the scenarios, especially when the available scenarios outnumber the support scenarios.
Parallel differential evolution applied to interleaving generation with precedence evaluation of tentative solutions
This paper proposes a method to improve the CPU utilization of parallel differential evolution (PDE) by incorporating the interleaving generation mechanism. Previous research proposed the interleaving generation evolutionary algorithm (IGEA) and its improved variants (iIGEA). IGEA reduces the computation time by generating new offspring, which parents have been determined even when all individuals have not evaluated. However, the previous research only used a simple EA method, which is not suitable for practical use. For this issue, this paper explores the applicability of IGEA and iIGEA to practical EA methods. In particular, we choose differential evolution (DE), which is widely used in real-world applications, and propose IGDE and its improved variant, iIGDE. We conduct experiments to investigate the effectiveness of IGDE with several features of the evaluation time on a simulated parallel computing environment. The experimental results reveal that the IGDE variants have higher CPU utilization than a simple PDE and reduce the computation time required for optimization. Besides, iIGDE outperforms the original IGDE for all features of the evaluation time.
The evolution of advanced persistent threats (APTs) spurs us to explore computational models of coevolutionary dynamics arising from efforts to secure cyber systems from them. In a first for evolutionary algorithms, we incorporate known threats and vulnerabilities into a stylized "competition" that pits cyber attack patterns against mitigations. Variations of attack patterns that are drawn from the public CAPEC catalog offering Common Attack Pattern Enumeration and Classifications. Mitigations take two forms: software updates or monitoring, and the software that is mitigated is identified by drawing from the public CVE dictionary of Common Vulnerabilities and Exposures. In another first, we quantify the outcome of a competition by incorporating the public Common Vulnerability Scoring System - CVSS. We align three abstract models of population-level dynamics where APTs interact with defenses with three competitive, coevolutionary algorithm variants that use the competition. A comparative study shows that the way a defensive population preferentially acts, e.g. shifting to mitigating recent attack patterns, results in different evolutionary outcomes, expressed as different dominant attack patterns and mitigations.
In the domain of partial classification, recent studies about multiobjective local search (MOLS) have led to new algorithms offering high performance, particularly when the data are imbalanced. In the presence of such data, the class distribution is highly skewed and the user is often interested in the least frequent class. Making further improvements certainly requires exploiting complementary solving techniques (notably, for the rule mining problem). As Constraint Programming (CP) has been shown to be effective on various combinatorial problems, it is one such promising complementary approach. In this paper, we propose a new hybrid combination, based on MOLS and CP that are quite orthogonal. Indeed, CP is a complete approach based on powerful filtering techniques whereas MOLS is an incomplete approach based on Pareto dominance. Experimental results on real imbalanced datasets show that our hybrid approach is statistically more efficient than a simple MOLS algorithm on both training and tests instances, in particular, on partial classification problems containing many attributes.
As computing power grows, the automated specialization and design of evolutionary algorithms (EAs) to tune their performance to individual problem classes becomes more attractive. To this end, a significant amount of research has been conducted in recent decades, utilizing a wide range of techniques. However, few techniques have been devised which automate the design of the overall structure of an EA. Most EA implementations rely solely on the traditional evolutionary cycle of parent selection, reproduction, and survival selection, and those with unique structures typically replace this with another static, hand-made cycle. Existing techniques for modifying the evolutionary structure use representations which are either loosely structured and highly stochastic, or which are constrained and unable to easily evolve complicated pathways. The ability to easily evolve complex evolutionary pathways would greatly expand the heuristic space which can be explored during specialization, potentially allowing for the representation of EAs which outperform the traditional cycle. This work proposes a methodology for the automated design of the evolutionary process by introducing a novel directed-graph-based representation, created to be mutable and flexible, permitting a black-box designer to produce reusable, high-performance EAs. Experiments show that our methodology can produce high-performance EAs demonstrating intelligible strategies.
Many real-world applications have the time-linkage property, and the only theoretical analysis is recently given by Zheng, et al. (TEVC 2021) on their proposed time-linkage OneMax problem, OneMax(0,1n). However, only two elitist algorithms (1 + 1) EA and (μ + 1) EA are analyzed, and it is unknown whether the non-elitism mechanism could help to escape the local optima existed in OneMax(0,1n). In general, there are few theoretical results on the benefits of the non-elitism in evolutionary algorithms. In this work, we analyze on the influence of the non-elitism via comparing the performance of the elitist (1 + λ) EA and its non-elitist counterpart (1, λ) EA. We prove that with probability 1 - o(1) (1 + λ) EA will get stuck in the local optima and cannot find the global optimum, but with probability 1, (1, λ) EA can reach the global optimum and its expected runtime is O(n3+c log n) with [EQUATION] for the constant c ≥ 1. Noting that a smaller offspring size is helpful for escaping from the local optima, we further resort to the compact genetic algorithm where only two individuals are sampled to update the probabilistic model, and prove its expected runtime of O(n3 log n). Our computational experiments also verify the efficiency of the two non-elitist algorithms.