GECCO '18- Proceedings of the Genetic and Evolutionary Computation Conference CompanionFull Citation in the ACM Digital Library
WORKSHOP SESSION: Workshop papers: workshop surrogate-assisted evolutionary optimisation
Evaluating surrogate models for multi-objective influence maximization in social networks
One of the most relevant problems in social networks is influence maximization, that is the problem of finding the set of the most influential nodes in a network, for a given influence propagation model. As the problem is NP-hard, recent works have attempted to solve it by means of computational intelligence approaches, for instance Evolutionary Algorithms. However, most of these methods are of limited applicability for real-world large-scale networks, for two reasons: on the one hand, they require a large number of candidate solution evaluations to converge; on the other hand, each evaluation is computationally expensive in that it needs a considerable number of Monte Carlo simulations to obtain reliable values. In this work, we consider a possible solution to such limitations, by evaluating a surrogate-assisted Multi-Objective Evolutionary Algorithm that uses an approximate model of influence propagation (instead of Monte Carlo simulations) to find the minimum-sized set of most influential nodes. Experiments carried out on two social networks datasets suggest that approximate models should be carefully considered before using them in influence maximization approaches, as the errors induced by these models are in some cases too big to benefit the algorithmic performance.
Asynchronous surrogate-assisted optimization networks
This paper introduces a new, highly asynchronous method for surrogate-assisted optimization where it is possible to concurrently create surrogate models, evaluate fitness functions and do parameter optimization for the underlying problem, effectively eliminating sequential workflows of other surrogate-assisted algorithms. Using optimization networks, each part of the optimization process is exchangeable. First experiments are done for single objective benchmark functions, namely Ackley, Griewank, Schwefel and Rastrigin, using problem sizes starting from 2D up to 10D, and other EGO implementations are used as baseline for comparison. First results show that the implemented network approach is competitive to other EGO implementations in terms of achieved solution qualities and more efficient in terms of execution times.
WORKSHOP SESSION: Workshop papers: workshop industrial application of metaheuristics
Generating interpretable fuzzy controllers using particle swarm optimization and genetic programming
Autonomously training interpretable control strategies, called policies, using pre-existing plant trajectory data is of great interest in industrial applications. Fuzzy controllers have been used in industry for decades as interpretable and efficient system controllers. In this study, we introduce a fuzzy genetic programming (GP) approach called fuzzy GP reinforcement learning (FGPRL) that can select the relevant state features, determine the size of the required fuzzy rule set, and automatically adjust all the controller parameters simultaneously. Each GP individual's fitness is computed using model-based batch reinforcement learning (RL), which first trains a model using available system samples and subsequently performs Monte Carlo rollouts to predict each policy candidate's performance. We compare FGPRL to an extended version of a related method called fuzzy particle swarm reinforcement learning (FPSRL), which uses swarm intelligence to tune the fuzzy policy parameters. Experiments using an industrial benchmark show that FGPRL is able to autonomously learn interpretable fuzzy policies with high control performance.
WORKSHOP SESSION: Workshop papers: workshop parallel and distributed evolutionary inspired methods
An actor model implementation of distributed factored evolutionary algorithms
With the rise of networked multi-core machines, we have seen an increased emphasis on parallel and distributed programming. In this paper we describe an implementation of Factored Evolutionary Algorithms (FEA) and Distributed Factored Evolutionary Algorithms (DFEA) using the Actor model. FEA and DFEA are multi-population algorithms, which make them good candidates for distributed implementation. The Actor model is a robust architecture for implementing distributed, reactive programs. After walking through the translation of the serial pseudocode into an Actor implementation, we run validation experiments against an FEA baseline. The evidence supports the claim that the Actor versions preserve the semantics and operational performance of the FEA baseline. We also discuss some of the nuances of translating serial pseudocode into an actual distributed implementation.
A parallel island model for biogeography-based classification rule mining in julia
In this paper, we present a distributed island model implementation of biogeography-based optimization for classification rule mining (island BBO-RM). Island BBO-RM is an evolutionary algorithm for rule mining that uses Pittsburgh style classification rule encoding, which represents an entire ruleset (classifier) as a single chromosome. Our algorithm relies on biogeography-based optimization (BBO), an optimization technique that is inspired by species migration pattern between habitats. Biogeography-based optimization has been reported to perform well in various applications ranging from function optimization to image classification. A major limitation of evolutionary rule mining algorithms is their high computational cost and running time. To address this challenge, we have applied a distributed island model to parallelize the rule extraction phase via BBO. We have explored several different migration topologies and data windowing techniques. Our algorithm is implemented in Julia, a dynamic programming language designed for high-performance and parallel computation. Our results show that our distributed implementation is able to achieve considerable speedups when compared to a serial implementation. Without data windowing, we obtain speedups up to a factor of nine without a loss of classification accuracy. With data windowing, we obtain speedups up to a factor of 30 with a small loss of accuracy in some cases.
Effective processor load balancing using multi-objective parallel extremal optimization
The paper presents how Extremal Optimization can be used in a parallel multi-objective load balancing algorithm applied in execution of distributed programs. Extremal Optimization is used to find task migration which dynamically improves processor load balance in a distributed system. In the proposed multi-objective approach we use three objectives relevant to distributed processor load balancing in execution of program tasks. They are: computational load balance of processors, the volume of inter-processor communication and task migration metrics. In the algorithms additional criteria are used which are based on some knowledge on the influence of the computational and communication loads on task execution. The proposed algorithms are assessed by simulation experiments with distributed execution of program macro data flow graphs. Two methods of finding compromise solutions based on the Pareto front were used: one based on a geometric (Euclidean) distance of solutions and the second one based on the Manhattan (taxicab geometry) distance. The influence of the distance geometry on the final solutions is discussed.
Vectorized candidate set selection for parallel ant colony optimization
Ant Colony Optimization (ACO) is a well-established nature-inspired heuristic, and parallel versions of the algorithm now exist to take advantage of emerging high-performance computing processors. However, careful attention must be paid to parallel components of such implementations if the full benefit of these platforms is to be obtained. One such component of the ACO algorithm is next node selection, which presents unique challenges in a parallel setting. In this paper, we present a new node selection method for ACO, Vectorized Candidate Set Selection (VCSS), which achieves significant speedup over existing selection methods on a test set of Traveling Salesman Problem instances.
WORKSHOP SESSION: Workshop papers: workshop evolution in cognition
The flouted naming game: contentions and conventions in culture
Naming Games are AI platforms that can account for how conventions in language and culture are achieved. This approach, however, does not account for other cultural features such as contentions. By contentions it is meant that agents learn other agents' traits but decide not to transmit these. This work introduces a version termed Flouted Naming Game which allows convergence to stable states of cultural contentions as an alternative outcome of the Naming Game. Which regime is achieved depends on a basic asymmetry on the cognitive reward of two opposing cultural forms. Moreover, it is found that there is a sharp phase transition between the two behavioural strategies. The transition point is sensitive to population size: larger populations can maintain contentions on a wider range of parameters than smaller populations.
Meta-learning by the Baldwin effect
The scope of the Baldwin effect was recently called into question by two papers that closely examined the seminal work of Hinton and Nowlan. To this date there has been no demonstration of its necessity in empirically challenging tasks. Here we show that the Baldwin effect is capable of evolving few-shot supervised and reinforcement learning mechanisms, by shaping the hyperparameters and the initial parameters of deep learning algorithms. Furthermore it can genetically accommodate strong learning biases on the same set of problems as a recent machine learning algorithm called MAML "Model Agnostic Meta-Learning" which uses second-order gradients instead of evolution to learn a set of reference parameters (initial weights) that can allow rapid adaptation to tasks sampled from a distribution. Whilst in simple cases MAML is more data efficient than the Baldwin effect, the Baldwin effect is more general in that it does not require gradients to be backpropagated to the reference parameters or hyperparameters, and permits effectively any number of gradient updates in the inner loop. The Baldwin effect learns strong learning dependent biases, rather than purely genetically accommodating fixed behaviours in a learning independent manner.
WORKSHOP SESSION: Workshop papers: workshop new standards for benchmarking in evolutionary computation research
Maze benchmark for testing evolutionary algorithms
In this paper, a new benchmark, for testing the capability of Evolutionary Algorithms to generate maze solving Exploration Strategies is introduced. This benchmark solves three problems commonly found in other benchmarks: small maze set, all mazes belonging to the same kind of maze, and biased methods for choosing starting locations. In this benchmark, the Connectivity Based Maze Generation Algorithm is proposed for building maze sets. Mazes generated using this algorithm exhibit a property called connectivity that indicates how much the walls are connected among them. Connectivity can be used to control the diversity of the sets. Additionally, a new method for choosing starting locations, that takes into account the maze goal positions, is presented. Using the Connectivity Based Maze Generation Algorithm and the new method for choosing starting locations, two problems that test the capability of an Evolutionary Algorithm for solving mazes with similar and different connectivity are built. Example datasets are generated and experiments are performed to validate the proposed benchmark.
The impact of statistics for benchmarking in evolutionary computation research
Benchmarking theory in evolutionary computation research is a crucial task that should be properly applied in order to evaluate the performance of a newly introduced evolutionary algorithm with performance of state-of-the-art algorithms. Benchmarking theory is related to three main questions: which problems to choose, how to setup experiments, and how to evaluate performance. In this paper, we evaluate the impact of different already established statistical ranking schemes that can be used for evaluation of performance in benchmarking practice for evolutionary computation. Experimental results obtained on Black-Box Benchmarking 2015 showed that different statistical ranking schemes, used on the same benchmarking data, can lead to different benchmarking results. For this reason, we examined the merits and issues of each of them regarding benchmarking practices.
Evolving benchmark functions using kruskal-wallis test
Evolutionary algorithms are cost-effective for solving real-world optimization problems, such as NP-hard and black-box problems. Before an evolutionary algorithm can be put into real-world applications, it is desirable that the algorithm was tested on a number of benchmark problems. On the other hand, performance measure on benchmarks can reflect if the benchmark suite is representative. In this paper, benchmarks are generated based on the performance comparison among a set of established algorithms. For each algorithm, its uniquely easy (or uniquely difficult) problem instances can be generated by an evolutionary algorithm. The unique difficulty nature of a problem instance to an algorithm is ensured by the Kruskal-Wallis H-test, assisted by a hierarchical fitness assignment method. Experimental results show that an algorithm performs the best (worst) consistently on its uniquely easy (difficult) problem. The testing results are repeatable. Some possible applications of this work include: 1) to compose an alternative benchmark suite; 2) to give a novel method for accessing novel algorithms; and 3) to generate a set of meaningful training and testing problems for evolutionary algorithm selectors and portfolios.
Analysing symbolic regression benchmarks under a meta-learning approach
The definition of a concise and effective testbed for Genetic Programming (GP) is a recurrent matter in the research community. This paper takes a new step in this direction, proposing a different approach to measure the quality of the symbolic regression benchmarks quantitatively. The proposed approach is based on meta-learning and uses a set of dataset meta-features---such as the number of examples or output skewness---to describe the datasets. Our idea is to correlate these meta-features with the errors obtained by a GP method. These meta-features define a space of benchmarks that should, ideally have datasets (points) covering different regions of the space. An initial analysis of 63 datasets showed that current benchmarks are concentrated in a small region of this benchmark space. We also found out that number of instances and output skewness are the most relevant meta-features to GP output error. Both conclusions can help define which datasets should compose an effective testbed for symbolic regression methods.
WORKSHOP SESSION: Workshop papers: workshop evolutionary computation software systems
Performance assessment of multi-objective evolutionary algorithms with the R package ecr
Assessing the performance of stochastic optimization algorithms in the field of multi-objective optimization is of utmost importance. Besides the visual comparison of the obtained approximation sets, more sophisticated methods have been proposed in the last decade, e. g., a variety of quantitative performance indicators or statistical tests. In this paper, we present tools implemented in the R package ecr, which assist in performing comprehensive and sound comparison and evaluation of multi-objective evolutionary algorithms following recommendations from the literature.
Review: a web-based simulation viewer for sharing evolutionary robotics results
Evolutionary robotics researchers often need to share results that may be too difficult to describe in text and too complex to show using images. Many researchers include links to videos as supplementary materials, but videos have a predefined view of the scene and do not allow watchers to adjust the viewing angle to their preference. In this paper we present a web-based application (based on three.js) for sharing interactive animations. Specifically, our tool (called Review) enables researchers to generate simple animation log data that can be loaded in any modern web browser on a computer or mobile device. The camera in these animations is controlled by the user such that they can pan, tilt, rotate, and zoom in and out of the scene. Review is meant to improve the ability of researchers to share their evolved results with one another.
A generic distributed microservices and container based framework for metaheuristic optimization
In recent years, metaheuristics have been a convincing solution for solving many types of complex optimization problems. Efficient execution for the most variants of metaheuristics e.g. Evolutionary Algorithms (EAs) or Swarm Optimization can require lots of computational power depending on the complexity of the application. For maximizing performance, parallelization of metaheuristic algorithms represents a meaningful approach, especially for EAs featuring an inherent parallelism. However, the majority of existing distributed optimization frameworks are implemented as monolithic and non-distributed applications running on one computer instead of using the computing power of computer clusters. Additionally, the application typically cannot easily work dynamically together with other tools and services like single simulators or combinations of simulators for multi-domain simulations. In the present paper, a new distributed framework for population-based metaheuristics, which can run highly parallelized optimizations on large scale computing clusters is introduced. The framework exploits and combines two lightweight technologies namely container virtualization and microservices for a fully automated and highly scalable solution. Another main advantage of the framework is that it allows plugging in and out different metaheuristic optimization algorithms and services via its modular distributed architecture. In order to validate the new design and implementation, the EA GLEAM (General Learning Evolutionary Algorithm and Method) [2, 3] is integrated into the framework and deployed on a cluster with 4 nodes and 128 cores for benchmarking. The tested master-slave parallelization of this EA shows considerable low overhead times and hence paves the way for future applications in, e.g., smart energy systems.
Performance improvements of evolutionary algorithms in perl 6
Perl 6 is a recently released language that belongs to the Perl family but was actually designed from scratch, not as a refactoring of the Perl 5 codebase. Through its two-year-old (released) history, it has increased performance by several orders of magnitude, arriving recently to the point where it can be safely used in production. In this paper, we are going to compare the historical and current performance of Perl 6 in a single problem, OneMax, to those of other interpreted languages; besides, we will also use implicit concurrency and see what kind of performance and scaling can we expect from it.
Plushi: an embeddable, language agnostic, push interpreter
In the Push programming language, all sequences of valid symbols with balanced parentheses are syntactically valid and execute without error. Push nonetheless supports arbitrary data types and is Turing complete. This combination of features makes it useful as the target language for program induction in genetic programming systems, for which it was developed, and potentially also in other program induction systems. Prior Push implementations have generally been designed for use only within the host language in which they were implemented, often in conjunction with a specific program induction system that is written in the same host language. In this paper we present Plushi, a modular, embeddable Push interpreter that is designed to interoperate with program induction systems written in any language.
Evo-ROS: integrating evolution and the robot operating system
In this paper, we describe the Evo-ROS framework, which is intended to help bridge the gap between the evolutionary and traditional robotics communities. Evo-ROS combines an evolutionary algorithm with individual physics-based evaluations conducted using the Robot Operating System (ROS) and the Gazebo simulation environment. Our goals in developing Evo-ROS are to (1) provide researchers in evolutionary robotics with access to the extensive support for real-world components and capabilities developed by the ROS community and (2) enable ROS developers, and more broadly robotics researchers, to take advantage of evolutionary search during design and testing. We describe the details of the Evo-ROS structure and operation, followed by presentation of a case study using Evo-ROS to optimize placement of sonar sensors on unmanned ground vehicles that can experience reduced sensing capability due to component failures and physical damage. The case study provides insights into the current capabilities and identifies areas for future enhancements.
WORKSHOP SESSION: Workshop papers: workshop learning classifier systems
Modulated clustering using integrated rough sets and scatter search attribute reduction
Feature selection is an essential problem in pattern classification systems. The entire performance of the classifier is highly affected by the quality of the selected features. In this paper, we address this problem by integrating feature selection with the clustering process. A novel feature-modulated classification algorithm is proposed to improve the classification accuracy. We use a rough sets approach for feature selection based on a scatter search meta-heuristic scheme. The proposed approach sifts a compact subset of characterizing features in multi-class systems according to the clustering performance. To verify the effectiveness of our method, experimental comparisons are carried out on eleven benchmark datasets using two typical classifiers. The results indicate that the proposed method has a remarkable ability to generate effective reduced-size subsets of salient features while yielding significant classification accuracy.
Optimizing clustering to promote data diversity when generating an ensemble classifier
In this paper, we propose a method to generate an optimized ensemble classifier. In the proposed method, a diverse input space is created by clustering training data incrementally within a cycle. A cycle is one complete round that includes clustering, training, and error calculation. In each cycle, a random upper bound of clustering is chosen and data clusters are generated. A set of heterogeneous classifiers are trained on all generated clusters to promote structural diversity. An ensemble classifier is formed in each cycle and generalization error of that ensemble is calculated. This process is optimized to find the set of classifiers which can have the lowest generalization error. The process of optimization terminates when generalization error can no longer be minimized. The cycle with the lowest error is then selected and all trained classifiers of that particular cycle are passed to the next stage. Any classifier having lower accuracy than the average accuracy of the pool is discarded, and the remaining classifiers form the proposed ensemble classifier. The proposed ensemble classifier is tested on classification benchmark datasets from UCI repository. The results are compared with existing state-of-the-art ensemble classifier methods including Bagging and Boosting. It is demonstrated that the proposed ensemble classifier performs better than the existing ensemble methods.
Integrating anticipatory classifier systems with OpenAI gym
This paper explains the process of integrating ACS2 algorithm with the standardised framework for comparing reinforcement learning tasks - OpenAI Gym. The new Python library is introduced alongside with standard environments derived from LCS literature. Typical use cases enabling quick evaluation of different research problems are described.
XCSR based on compressed input by deep neural network for high dimensional data
This paper proposes the novel Learning Classifier System (LCS) which can solve high-dimensional problems, and obtain human-readable knowledge by integrating deep neural networks as a compressor. In the proposed system named DCAXCSR, deep neural network called Deep Classification Autoencoder (DCA) compresses (encodes) input to lower dimension information which LCS can deal with, and decompresses (decodes) output of LCS to the original dimension information. DCA is hybrid network of classification network and autoencoder towards increasing compression rate. If the learning is insufficient due to lost information by compression, by using decoded information as an initial value for narrowing down state space, LCS can solve high dimensional problems directly. As LCS of the proposed system, we employs XCSR which is LCS for real value in this paper since DCA compresses input to real values. In order to investigate the effectiveness of the proposed system, this paper conducts experiments on the benchmark classification problem of MNIST database and Multiplexer problems. The result of the experiments shows that the proposed system can solve high-dimensional problems which conventional XCSR cannot solve, and can obtain human-readable knowledge.
Model parameter adaptive instance-based policy optimization for episodic control tasks of nonholonomic systems
Evolutionary Computation (EC) attracts more and more attention in Reinforcement Learning (RL) with successful applications such as robot control. Instance-Based Policy (IBP) is a promising alternative to policy representations based on Artificial Neural Networks (ANNs). The IBP has been reported superior to continuous policy representations such as ANNs in the stabilization control of non-holonomic systems due to its nature of bang-bang type control, and its understandability. A difficulty in applying an EC based policy optimization to an RL task is to choose appropriate hyper-parameters such as the network structure in ANNs and the parameters of EC. The same applies to the IBP, where the critical parameter is the number of instances that determines mode flexibility. In this paper, we propose a novel RL method combining the IBP representation and optimization by the Covariance Matrix Adaptation Evolution Strategy (CMA-ES), which is a state-of-the-art general-purpose search algorithm for black-box continuous optimization. The proposed method, called IBP-CMA, is a direct policy search that adapts the number of instances during the learning process and activates instances that do not contribute to the output. In the simulation, the IBP-CMA is compared with an ANN-based RL, CMA-TWEANN.
An algebraic description of XCS
XCS and its derivatives are some of the most prominent Learning Classifier Systems (LCSs). Since XCS's design was done "algorithm first", there existed no formal basis at its inception. Over the past 20 years, several publications analysed parts of the system theoretically but the only approach to a more holistic theory of LCSs in general was never fully adapted. We present an algebraic formalisation of XCS that facilitates formal reasoning about the system and serves as a complement to earlier algorithmic descriptions. Our work is meant to give a fresh impetus to XCS and LCS theory. Since we use the programming language Haskell for our formal expressions we also describe a new abstract XCS framework in the process.
Applying accuracy-based LCS to detecting anomalous database access
Database intrusion detection (DB-IDS) is the problem of detecting anomalous queries in transaction systems like e-commerce platform. The adaptive detection algorithm is necessary to find anomaly accesses when the environment changes continuously. To solve this problem, we used accuracy-based LCS (XCS), one of the primary model of adaptive machine learning method, for detecting malicious accesses in databases. In the problem of database intrusion detection which changes the detecting targets, we found and analyzed the patterns of rule generation to show systemically how the adaptive learning of XCS algorithm is working in practical usage.
EvoNN: a customizable evolutionary neural network with heterogenous activation functions
While some attention has been given to the process of using Evolutionary Computation (EC) to optimize the activation functions within hidden layers, available activation function sets have always been hard coded by the developers, and were immutable by users.
In this paper, we present EvoNN. While many other Neuro-evolution based tools or algorithms focus primarily on the evolution of either Neural Network (NN) architecture, or its weights, EvoNN focuses on simultaneous evolution of weights and the activation functions within hidden layers. The main novely offered by EvoNN lies in that users can provide additional activation functions to the EvoNN system to be employed as part of the "alphabet" of available functions. This feature gives users a greater degree of flexibility over which functions the evolutionary optimizer can utilize.
We employ a set of three test cases where we compare EvoNN to a standard NN, and observe encouraging results showing a superior performance of the EvoNN system. We also observe this increase in performance comes at the cost of additional run time, but note that for some applications, this can be a worthwhile trade-off.
XCS-CR: determining accuracy of classifier by its collective reward in action set toward environment with action noise
Accuracy based Learning Classifier System (XCS) prefers to generalize the classifiers that always acquire the same reward, because they make accurate reward predictions. However, real-world problems have noise, which means that classifiers may not receive the same reward even if they always take the correct action. For this case, since all classifiers acquire multiple values as the reward, XCS cannot identify accurate classifiers. In this paper, we study a single step environment with action noise, where XCS's action is sometimes changed at random. To overcome this problem, this paper proposes XCS based on Collective weighted Reward (XCS-CR) to identify the accurate classifiers. In XCS each rule predicts its next reward by averaging its past rewards. Instead, XCS-CR predicts its next reward by selecting a reward from the set of past rewards, by comparing the past rewards to the collective weighted average reward of the rules matching the current input for each action. This comparison helps XCS-CR identify rewards that result from action noise. In experiments, XCS-CR acquired the optimal generalized classifier subset in 6-Multiplexer problems with action noise, similar to the environment without noise, and judged those optimal generalized classifiers correctly accurate.
Generalizing rules by random forest-based learning classifier systems for high-dimensional data mining
This paper proposes high-dimensional data mining technique by integrating two data mining methods: Accuracy-based Learning Classifier Systems (XCS) and Random Forests (RF). Concretely the proposed system integrates RF and XCS: RF generates several numbers of decision trees, and XCS generalizes the rules converted from the decision trees. The convert manner is as follows: (1) the branch node of the decision tree becomes the attribute; (2) if the branch node does not exist, the attribute of that becomes # for XCS; and (3) One decision tree becomes one rule at least. Note that # can become any value in the attribute. From the experiments of Multiplexer problems, we derive that: (i) the good performance of the proposed system; and (ii) RF helps XCS to acquire optimal solutions as knowledge by generating appropriately generalized rules.
WORKSHOP SESSION: Workshop papers: workshop landscape-aware heuristic search
Progressive gradient walk for neural network fitness landscape analysis
Understanding the properties of neural network error landscapes is an important problem faced by the neural network research community. A few attempts have been made in the past to gather insight about neural network error landscapes using fitness landscape analysis techniques. However, most fitness landscape metrics rely on the analysis of random samples, which may not represent the high-dimensional neural network search spaces well. If the random samples do not include areas of good fitness, then the presence of local optima and/or saddle points cannot be quantified. This paper proposes a progressive gradient walk as an alternative sampling algorithm for neural network error landscape analysis. Experiments show that the proposed walk captures areas of good fitness significantly better than the random walks.
Computationally efficient local optima network construction
There has been an increasing amount of research on the visualisation of search landscapes through the use of exact and approximate local optima networks (LONs). Although there are many papers available describing the construction of a LON, there is a dearth of code released to support the general practitioner constructing a LON for their problem. Furthermore, a naive implementation of the algorithms described in work on LONs will lead to inefficient and costly code, due to the possibility of repeatedly reevaluating neighbourhood members, and partially overlapping greedy paths. Here we discuss algorithms for the efficient computation of both exact and approximate LONs, and provide open source code online. We also provide some empirical illustrations of the reduction in the number of recursive greedy calls, and quality function calls that can be obtained on NK model landscapes, and discretised versions of the IEEE CEC 2013 niching competition tests functions, using the developed framework compared to naive implementations. In many instances multiple order of magnitude improvements are observed.
Filter versus wrapper feature selection based on problem landscape features
Feature selection is a complex problem used across many fields, such as computer vision and data mining. Feature selection algorithms extract a subset of features from a greater feature set which can improve algorithm accuracy by discarding features that are less significant in achieving the goal function. Current approaches are often computationally expensive, provide insignificant increases in predictor performance, and can lead to overfitting. This paper investigates the binary feature selection problem and the applicability of using filter and wrapper techniques guided by fitness landscape characteristics. It is shown that using filter methods are more appropriate for problems where the fitness does not provide sufficient information to guide search as needed by wrapper techniques.
WORKSHOP SESSION: Workshop papers: workshop exploration of inaccessible environments through hardware/software co-evolution
Evolving hardware instinctive behaviors in resource-scarce agent swarms exploring hard-to-reach environments
This work introduces a novel adaptation framework to energy-efficiently adapt small-sized circuits operating under scarce resources in dynamic environments, as autonomous swarm of sensory agents. This framework makes it possible to optimally configure the circuit based on three key mechanisms: (a) an off-line optimization phase relying on R2 indicator based Evolutionary Multi-objective Optimization Algorithm (EMOA), (b) an on-line phase based on hardware instincts and (c) the possibility to include the environment in the optimization loop. Specifically, the evolutionary algorithm is able to simultaneously determine an optimal combination of static settings and dynamic instinct for the hardware, considering highly dynamic environments. The instinct is then run on-line with minimal on-chip resources so that the circuit efficiently react to environmental changes. This framework is demonstrated on an ultrasonic communication system between energy-scarce wireless nodes. The proposed approach is environment-adaptive and enables power savings up to 45% for the same performance on the considered case studies.
A distributed epigenetic shape formation and regeneration algorithm for a swarm of robots
Living cells exhibit both growth and regeneration of body tissues. Epigenetic Tracking (ET), models this growth and regenerative qualities of living cells and has been used to generate complex 2D and 3D shapes. In this paper, we present an ET based algorithm that aids a swarm of identically-programmed robots to form arbitrary shapes and regenerate them when cut. The algorithm works in a distributed manner using only local interactions and computations without any central control and aids the robots to form the shape in a triangular lattice structure. In case of damage or splitting of the shape, it helps each set of the remaining robots to regenerate and position themselves to build scaled down versions of the original shape. The paper presents the shapes formed and regenerated by the algorithm using the Kilombo simulator.
WORKSHOP SESSION: Workshop papers: workshop black box optimization benchmarking 2018
Stopping criteria, initialization, and implementations of BFGS and their effect on the BBOB test suite
Benchmarking algorithms is a crucial task to understand them and to make recommendations for which algorithms to use in practice. However, one has to keep in mind that we typically compare only algorithm implementations and that care must be taken when making general statements about an algorithm while implementation details and parameter settings might have a strong impact on the performance. In this paper, we investigate those impacts of initialization, internal parameter setting, and algorithm implementation over different languages for the well-known BFGS algorithm. We must conclude that even in the default setting, the BFGS algorithms in Python's scipy library and in Matlab's fminunc differ widely---with the latter even changing significantly over time.
Benchmarking a variant of the CMAES-APOP on the BBOB noiseless testbed
The CMAES-APOP algorithm tracks the median of the elite objective values in each S successive iterations to decide whether we should increase or decrease or keep the population size in the next slot of S iterations. This quantity could be seen as the 25th percentile of objective function values evaluated in each iteration on λ candidate points. In this paper we propose a variant of the CMAES-APOP algorithm, in which we will track some percentiles of the objective values simultaneously. Some numerical results will show the improvement of this approach on some ill-conditioned functions, and on some multi-modal functions with weak global structure in small dimensions.
Benchmarking the PSA-CMA-ES on the BBOB noiseless testbed
We evaluate the CMA-ES with population size adaptation mechanism (PSA-CMA-ES) on the BBOB noiseless testbed. On one hand, the PSA-CMA-ES with a simple restart strategy shows performance competitive with the best 2009 portfolio on most well-structured multimodal functions. On the other hand, it is not effective on weakly-structured multimodal functions. Moreover, on most uni-modal functions, the scale-up of performance measure w.r.t. the dimension tends to be worse than the default CMA-ES, implying that the population size is adapted greater than needed on the unimodal functions. To improve performance on unimodal functions and weakly-structured multimodal functions, we additionally propose a restart strategy for the PSA-CMA-ES. The proposed strategy consists of three search regimes. The resulted restart strategy shows improved performance on unimodal functions and weakly-structured multimodal functions with a little compromise in the performance on well-structured multimodal functions. The overall performance is competitive to the BIPOP-CMA-ES.
Comparing black-box differential evolution and classic differential evolution
Recently, black-box differential evolution (BBDE) has been proposed to overcome the search biases and sensitivity to rotation of the classic differential evolution (DE). To date, BBDE has been studied only for the 'rand' strategy and even for this strategy, no systematic experimental study has been published yet. In this paper we provide such a study and further examine whether the idea from BBDE can be extended to two other DE strategies, 'best' and 'target-to-best'. We compare in detail these DE and BBDE variants using the COCO (Comparing Continuous Optimizers) platform to assess their overall performance and invariance to rotation. The results show that BBDE with the 'rand' strategy performs better than the original algorithm, but this is not true for the other two strategies. We also demonstrate that while the BBDE variants are less sensitive to rotation than the DE variants, some sensitivity to this transformation still persists and remains currently unexplained.
WORKSHOP SESSION: Workshop papers: workshop evolutionary computation for the automated design of algorithms
The automated design of probabilistic selection methods for evolutionary algorithms
Selection functions enable Evolutionary Algorithms (EAs) to apply selection pressure to a population of individuals, by regulating the probability that an individual's genes survive, typically based on fitness. Various conventional fitness based selection methods exist, each providing a unique relationship between the fitnesses of individuals in a population and their chances of selection. However, the full space of selection algorithms is only limited by max algorithm size, and each possible selection algorithm is optimal for some EA configuration applied to a particular problem class. Therefore, improved performance may be expected by tuning an EA's selection algorithm to the problem at hand, rather than employing a conventional selection method. The objective of this paper is to investigate the extent to which performance can be improved by tuning selection algorithms, employing a Hyper-heuristic to explore the space of search algorithms which encode the relationships between the fitnesses of individuals and their probability of selection. We show the improved performance obtained versus conventional selection functions on fixed instances from a benchmark problem class, including separate testing instances to show generalization of the improved performance.
Visualizing the tape of life: exploring evolutionary history with virtual reality
Understanding the evolutionary dynamics created by a given evolutionary algorithm is a critical step in determining which ones are most likely to produce desirable outcomes for a given problem. While it is relatively easy to come up with hypotheses that could plausibly explain observed evolutionary outcomes, we often fail to take the next step of confirming that our proposed mechanism accurately describes the underlying evolutionary dynamics. Visualization is a powerful tool for exploring evolutionary history as it actually played out. We can create visualizations that summarize the evolutionary history of a population or group of populations by drawing representative lineages on top of the fitness landscape being traversed. This approach integrates information about the adaptations that took place with information about the evolutionary pressures they were being subjected to as they evolved. However, these visualizations can be challenging to depict on a two-dimensional surface, as they integrate multiple forms of three-dimensional (or more) data. Here, we propose an alternative: taking advantage of recent advances in virtual reality to view evolutionary history in three dimensions. This technique produces an intuitive and detailed illustration of evolutionary processes. A demo of our visualization is available here: https://emilydolson.github.io/fitness_landscape_visualizations.
Visualising the search process for multi-objective optimisation
This paper proposes different visualisation techniques to understand the behaviour of an algorithm's entities during the search process when solving multi-objective optimisation problems. A scatter plot is used to highlight the Pareto-ranking of the entities during the search. Different fronts of the entities are indicated through the ball sizes of the scatter plot. Using a parallel coordinate plot for visualising the effect of control parameter values on the performance of an algorithm is also proposed. Possible extensions for dynamic multi-objective optimisation are also discussed.
VINE: an open source interactive data visualization tool for neuroevolution
Recent advances in deep neuroevolution have demonstrated that evolutionary algorithms, such as evolution strategies (ES) and genetic algorithms (GA), can scale to train deep neural networks to solve difficult reinforcement learning (RL) problems. However, it remains a challenge to analyze and interpret the underlying process of neuroevolution in such high dimensions. To begin to address this challenge, this paper presents an interactive data visualization tool called VINE (Visual Inspector for NeuroEvolution) aimed at helping neuroevolution researchers and end-users better understand and explore this family of algorithms. VINE works seamlessly with a breadth of neuroevolution algorithms, including ES and GA, and addresses the difficulty of observing the underlying dynamics of the learning process through an interactive visualization of the evolving agent's behavior characterizations over generations. As neuroevolution scales to neural networks with millions or more connections, visualization tools like VINE that offer fresh insight into the underlying dynamics of evolution become increasingly valuable and important for inspiring new innovations and applications.
WORKSHOP SESSION: Workshop papers: workshop medical applications of genetic and evolutionary computation
Design of HIFU treatment plans using an evolutionary strategy
High Intensity Focused Ultrasound (HIFU) is an emerging technique for non-invasive cancer treatment where malignant tissue is destroyed by thermal ablation. Since one ablation only allows a small region of tissue to be destroyed, a series of ablations has to be conducted to treat larger volumes. To maximize the treatment outcome and prevent injuries such as skin burns, complex preoperative treatment planning is carried out to determine the focal position and sonication time for each ablation. Here, we present an evolutionary strategy to design HIFU treatment plans using a map of patient specific material properties and a realistic thermal model. The proposed strategy allows high-quality treatment plans to be designed, with the average volume of mistreated and under-treated tissue not exceeding 0.1 %.
Coevolving behavior and morphology of simple agents that model small-scale robots
Humanity have long strived to create microscopic machines for various purposes. Most prominent of them employ nano-robots for medical purposes and procedures, otherwise deemed hard or impossible to perform. However, the main advantage of this kind, of machines is also their main drawback - their small size. The miniature scale they work in, brings a lot of problems, such as not having enough space for the computational power needed for their operation, or the specifics of the laws of physic that govern their behavior. In our study we focus on the former challenge, by introducing a new standpoint to the well-studied predator-prey pursuit problem (PPPP) using an implementation of very simple predator agents, using nano-robots designed to be morphologically simple. They feature direct mapping of the (few) perceived environmental variables into corresponding pairs of rotational velocities of the wheels' motors. Our previous, unpublished work showed that the classic problem with agents that use straightforward sensor, do not yield favorable results as they solve only a few of the initial test situations. We implemented genetic algorithm to evolve such a mapping that results in an optimal successful behavioral of the team of predator agents. In addition, to cope with the previously described issue, we introduced a simple change to the agents in order to improve the generality of the evolved behavior for additional test situations. Our approach is to implement an angular offset to the visibility sensor beam relative to the longitudinal axis of the agents. We added the offset to the genetic algorithm in order to define the best possible value, that introduces most efficient and consistent solution results. The successfully evolved behavior can be used in nano-robots to deliver medicine, locate and destroy cancer cells, pinpoint microscopic imaging, etc.1
Solution exploration using multi-objective genetic algorithm for determining experiment candidate
Solving problems involves the following two phases. In the first phase, detail of the problem are determined and the solution is found according to these condition. In the second phase, the results are used to narrow down any remaining ambiguities in the problem. In terms of the flow of a river, the former lies upstream of solving the problem while the latter lies downstream. Multiobjective genetic algorithms (GAs) is are able to find possible solution sets involving trade-offs among several different objective functions. In this study, we use a multiobjective GA to grasp variety types of solutions, not solve the problem directly. In other words, we use it for the upstream problem-solving step. As a case study of using multiobjective GAs to explore solutions, we identify cancer cells where the Nrf3 transcription factor is active and consider the problem of determining which genes to focus on in experiments based on that information. In this case, we selected gene candidates that are likely to be associated with Nrf3 activity and experiments (which previously had to be carried out exhaustively) are currently being carried out to confirm these results.