Tutorials

A Practical Guide to Experimentation

Many evolutionary algorithms, in particular those we use in practice, and many if not most relevant optimization problems, are not amenable to comprehensive theoretical analysis. For this reason, experimentation plays a central role in evolutionary computation and comes in three main flavours:

• explorative experiments
• systematic experimentation
• real-world problem solving

Explorative experiments serve to investigate, to improve, or to improve our understanding of algorithms. Systematic experimentation serves for the assessment of performance of algorithms and benchmarking. In this tutorial, we cover the first two flavours of experimentation which are somewhat complementary in their objectives and, to some extend, in their approach, but we also touch upon the third.

The tutorial emphasises on ways to make experimentation as effective and valuable as possible and on preventing common pitfalls. Attendees will learn how to make quick yet meaningful experiments, how to present, analyse and interpret experimental results and to measurement performance. We introduce run-length distributions (data profiles), performance profiles, scale-up studies, and connect success probabilities with restarts. Furthermore, the number of trials, the role of invariance, statistical significance, and the most common mistakes when conducting experimental studies are touched upon.

Constraint-Handling Techniques used with Evolutionary Algorithms

Evolutionary Algorithms (EAs), when used for global optimization, can be seen as unconstrained optimization techniques. Therefore, they require an additional mechanism to incorporate constraints of any kind (i.e., inequality, equality, linear, nonlinear) into their fitness function. Although the use of penalty functions (very popular with mathematical programming techniques) may seem an obvious choice, this sort of approach requires a careful fine tuning of the penalty factors to be used. Otherwise, an EA may be unable to reach the feasible region (if the penalty is too low) or may reach quickly the feasible region but being unable to locate solutions that lie in the boundary with the infeasible region (if the penalty is too severe). This has motivated the development of a number of approaches to incorporate constraints into the fitness function of an EA. This tutorial will cover the main proposals in current use, including novel approaches such as the use of tournament rules based on feasibility, multiobjective optimization concepts, hybrids with mathematical programming techniques (e.g., Lagrange multipliers), cultural algorithms, and artificial immune systems, among others. Other topics such as the importance of maintaining diversity, current benchmarks and the use of alternative search engines (e.g., particle swarm optimization, differential evolution, evolution strategies, etc.) will be also discussed (as time allows).

Evolution of Neural Networks

Evolution of artificial neural networks has recently emerged as a powerful technique in two areas. First, while the standard value-function based reinforcement learning works well when the environment is fully observable, neuroevolution makes it possible to disambiguate hidden state through memory. Such memory makes new applications possible in areas such as robotic control, game playing, and artificial life. Second, deep learning performance depends crucially on the network architecture and hyperparameters. While many such architectures are too complex to be optimized by hand, neuroevolution can be used to do so automatically. Such evolutionary AutoML can be used to achieve good deep learning performance even with limited resources, or state-of-the art performance with more effort. It is also possible to optimize other aspects of the architecture, like its size, speed, or fit with hardware. In this tutorial, I will review (1) neuroevolution methods that evolve fixed-topology networks, network topologies, and network construction processes, (2) methods for neural architecture search and evolutionary AutoML, and (3) applications of these techniques in control, robotics, artificial life, games, image processing, and language.

Evolutionary Computation: A Unified Approach

The field of Evolutionary Computation has experienced tremendous growth over the past 20 years, resulting in a wide variety of evolutionary algorithms and applications. The result poses an interesting dilemma for many practitioners in the sense that, with such a wide variety of algorithms and approaches, it is often hard to see the relationships between them, assess strengths and weaknesses, and make good choices for new application areas. This tutorial is intended to give an overview of a general EC framework that can help compare and contrast approaches, encourages crossbreeding, and facilitates intelligent design choices. The use of this framework is then illustrated by showing how traditional EAs can be compared and contrasted with it, and how new EAs can be effectively designed using it. Finally, the framework is used to identify some important open issues that need further research.

NEW Evolutionary Many-Objective Optimization

The goal of the proposed tutorial is clearly explaining difficulties of evolutionary many-objective optimization, approaches to the handling of those difficulties, and promising future research directions. Evolutionary multi-objective optimization (EMO) has been a very active research area in the field of evolutionary computation in the last two decades. In the EMO area, the hottest research topic is evolutionary many-objective optimization. The difference between multi-objective and many-objective optimization is simply the number of objectives. Multi-objective problems with four or more objectives are usually referred to as many-objective problems. It sounds that there exists no significant difference between three-objective and four-objective problems. However, the increase in the number of objectives significantly makes multi-objective problem difficult. In the first part (Part I: Difficulties), we clearly explain not only frequently-discussed well-known difficulties such as the weakening selection pressure towards the Pareto front and the exponential increase in the number of solutions for approximating the entire Pareto front but also other hidden difficulties such as the deterioration of the usefulness of crossover and the difficulty of performance evaluation of solution sets. The attendees of the tutorial will learn why many-objective optimization is difficult for EMO algorithms. After the clear explanations about the difficulties of many-objective optimization, we explain in the second part (Part II: Approaches and Future Directions) how to handle each difficulty. For example, we explain how to prevent the Pareto dominance relation from weakening its selection pressure and how to prevent a binary crossover operator from decreasing its search efficiently. We also explain some state-of-the-art many-objective algorithms. The attendees of the tutorial will learn some representative approaches to many-objective optimization and state-of-the-art many-objective algorithms. At the same time, the attendees will also learn that there still exist a large number of promising, interesting and important research directions in evolutionary many-objective optimization. Some promising research directions are explained in detail in the tutorial.

Evolutionary Multiobjective Optimization

Many optimization problems are multiobjective in the sense that multiple, conflicting criteria need to be considered simultaneously. Due to the conflict between these objectives, usually, no single optimum solution exist. Instead, a \emph{set} of so-called Pareto-optimal solutions, for which no other solution has better function values in all objectives, does result.

In practice, Evolutionary Multiobjective Optimization (EMO) algorithms are widely used for solving these multiobjective optimization problems. Being stochastic blackbox optimizers, EMO approaches allow problems with nonlinear, nondifferentiable, or noisy objective functions to be tackled. By inherently working on sets of solutions, they allow the Pareto-optimal set to be computed or approximated in one algorithm run---opposed to classical techniques from the multicriteria decision making (MCDM) field, which aim for single solutions. Defining problems in a multiobjective way, has two further advantages:

1. The set of (Pareto-optimal) solutions may reveal design principles shared by different solutions (innovization)
2. Some single-objective problems become easier to solve using randomized search heuristics if additional objectives are added (multiobjectivization).

Within this tutorial, a comprehensive introduction to the EMO field will be given and selected research results will be presented in more detail. More specifically, we are going to (i) introduce the basic principles of EMO algorithms in comparison to classical solution-based approaches, (ii) show a few practical examples which motivate the use of EMO in terms of the mentioned innovization and multiobjectivization principles, and (iii) present a general overview of state-of-the-art algorithms and techniques. Moreover, we will present important recent research results in areas such as preference articulation, performance assessment, and benchmarking.

Though classified as introductory, this tutorial is intended for both novices and people familiar with EMO. Those without experience will learn about the foundations of multiobjective optimization and the basic working principles of state-of-the-art EMO algorithms. The recent results and open questions, highlighted after each chapter of the tutorial, can stimulate future research and/or discussions during the conference.

Evolutionary Robotics

In the same way as evolution shapes animals, is it possible to use artificial evolution to automatically design robots? This attractive vision gave birth to Evolutionary Robotics (ER), an interdisciplinary field that incorporates ideas from Biology, Robotics and Artificial Intelligence. Within the last 20 years, Evolutionary Robotics explored many research avenues, from understanding Natural Evolution thanks to ER models, to co-designing robots’ bodies and brains.
This tutorial will give an overview of the various questions addressed in ER, relying on examples from the literature. Past achievements and major contributions, as well as specific challenges in ER will be described. The tutorial will in particular focus on:

• what is evolutionary robotics?
• fitness function design and the influence of selection pressure; • evolution for physical robots and the reality gap;
• evolutionary algorithms for collective and swarm robotics;
• open questions and future challenges.

Hyper-heuristics

The automatic design of algorithms has been an early aim of both machine learning and AI, but has proved elusive. The aim of this tutorial is to introduce hyper-heuristics as a principled approach to the automatic design of algorithms. Hyper-heuristics are metaheuristics applied to a space of algorithms; i.e., any general heuristic method of sampling a set of candidate algorithms. In particular, this tutorial will demonstrate how to mine existing algorithms to obtain algorithmic primitives for the hyper-heuristic to compose new algorithmic solutions from, and to employ various types of genetic programming to execute the composition process; i.e., the search of program space.

This tutorial will place hyper-heuristics in the context of genetic programming - which differs in that it constructs solutions from scratch using atomic primitives - as well as genetic improvement - which takes a program as starting point and improves on it (a recent direction introduced by William Langdon).

The approach proceeds from the observation that it is possible to define an invariant framework for the core of any class of algorithms (often by examining existing human-written algorithms for inspiration). The variant components of the algorithm can then be generated by genetic programming. Each instance of the framework therefore defines a family of algorithms. While this allows searches in constrained search spaces based on problem knowledge, it does not in any way limit the generality of this approach, as the template can be chosen to be any executable program and the primitive set can be selected to be Turing-complete. Typically, however, the initial algorithmic primitive set is composed of primitive components of existing high-performing algorithms for the problems being targeted; this more targeted approach very significantly reduces the initial search space, resulting in a practical approach rather than a mere theoretical curiosity. Iterative refining of the primitives allows for gradual and directed enlarging of the search space until convergence.

This leads to a technique for mass-producing algorithms that can be customised to the context of end-use. This is perhaps best illustrated as follows: typically a researcher might create a travelling salesperson algorithm (TSP) by hand. When executed, this algorithm returns a solution to a specific instance of the TSP. We will describe a method that generates TSP algorithms that are tuned to representative instances of interest to the end-user. This method has been applied to a growing number of domains including; data mining/machine learning, combinatorial problems including bin packing (on- and off-line), Boolean satisfiability, job shop scheduling, exam timetabling, image recognition, black-box function optimization, wind-farm layout, and the automated design of meta-heuristics themselves (from selection and mutation operators to the overall meta-heuristic architecture).

This tutorial will provide a step-by-step guide which takes the novice through the distinct stages of automatic design. Examples will illustrate and reinforce the issues of practical application. This technique has repeatedly produced results which outperform their manually designed counterparts, and a theoretical underpinning will be given to demonstrate why this is the case. Automatic design will become an increasingly attractive proposition as the cost of human design will only increase in-line with inflation, while the speed of processors increases in-line with Moore's law, thus making automatic design attractive for industrial application. Basic knowledge of genetic programming will be assumed.

Introduction to Genetic Programming

Genetic programming emerged in the early 1990's as one of the most exciting new evolutionary algorithm paradigms. It has rapidly grown into a thriving area of research and application. While sharing the evolutionary inspired algorithm principles of a genetic algorithm, it differs by exploiting an executable genome. Genetic programming evolves a 'program' to solve a problem rather than a single solution. This tutorial introduces the basic genetic programming paradigm. It explains how the powerful capability of genetic programming is derived from modular algorithmic components: executable representations such as a parse tree, variation operators that preserve syntax and explore a variable length, hierarchical solution space, appropriately chosen programming functions and fitness function specification. It provides demos and walks through an example of GP software.

NEW Learning Classifier Systems: From Principles to Modern Systems

Learning Classifier Systems (LCSs) emerged in the late 1970s and since then have attracted a lot of research attention. Originally introduced as a technique to model adaptive agents within Holland’s notion of complex adaptive systems, various enhancements toward a full-fledged Machine Learning (ML) technique with an evolutionary component at its core have appeared. Nowadays, several variations capable of dealing with most modern ML tasks exist, including online and batch-wise supervised learning, single- and multi-step reinforcement learning, and even unsupervised learning. This great flexibility, which is due to their modular and clearly defined algorithmic structure paving the way for simple and straight-forward adaptations, is unique in the field of Evolutionary Machine Learning (EML) – yielding the LCS paradigm an indisputable permanent place in the EML field. Despite this well-known blueprint comprising the building blocks bringing LCSs to function, gaining theoretical insights regarding the interplay between them has been a crucial research topic for a long time, and this still constitutes a pursued subject of active research.

In this tutorial, the main goal is to introduce exactly these building blocks of LCS-based EML and to conceptually develop a modern, generic Michigan-style LCS step by step from scratch. The resulting generic LCS is subsequently brought in line with the mostly investigated representative – Wilson’s Extended Classifier System (XCS) – which then serves as reference system for the subsequent parts. Past and recent theoretical advances in XCS research will be the subject of further discussions to provide the attendees with a feeling for the fundamental challenges and also the bounds of what can be achieved by XCS under which circumstances. To nevertheless provide a holistic view on LCSs, the tutorial starts with a sketch on the lineage and historical developments in the field, but will then quickly focus on the more prominent Michigan-style systems. The third part of the tutorial is then devoted to the state of the art in LCS research in terms of their real world applicability. The most recent advances that have led to modern systems such as XCSF for online function approximation or ExSTraCS for large-scale supervised data mining will thus be the subject of elaboration. The tutorial closes with a wrap-up regarding the distinctive potentials of LCS and with suggestions for a complementary (“traditional”) ML-centric view on this specific paradigm. With the intention to provide the audience with an impression about where LCS research stands these days and which open questions are still around, a review of most recent endeavors to tackle unsolved issues constitutes the end of the tutorial.

Model-Based Evolutionary Algorithms

In model-building evolutionary algorithms the variation operators are guided by the use of a model that conveys as much problem-specific information as possible so as to best combine the currently available solutions and thereby construct new, improved, solutions. Such models can be constructed beforehand for a specific problem, or they can be learnt during the optimization process. Well-known types of algorithms of the latter type are Estimation-of-Distribution Algorithms (EDAs) where probabilistic models of promising solutions are built and subsequently sampled to generate new solutions.

Although EDAs are the best known example, other approaches also exist, such as the Optimal Mixing EAs (e.g. the Linkage Tree Genetic Algorithm). In general, replacing traditional crossover and mutation operators by building and using models enables the use of machine learning techniques for automatic discovery of problem regularities and exploitation of these regularities for effective exploration of the search space. Using machine learning in optimization enables the design of optimization techniques that can automatically adapt to the given problem. This is an especially useful feature when considering optimization in a black-box setting. Successful applications include Ising spin glasses in 2D and 3D, graph partitioning, MAXSAT, feature subset selection, forest management, groundwater remediation design, telecommunication network design, antenna design, and scheduling.

This tutorial will provide an introduction and an overview of major research directions in this area.

Neuroevolution for Deep Reinforcement Learning Problems

In recent years, there has been a resurgence of interest in reinforcement learning (RL), particularly in the deep learning community. While much of the attention has been focused on using Value-function learning approaches (i.e. Q-Learning) or Estimated Policy Gradient-based approaches to train neural-network policies, little attention has been paid to Neuroevolution (NE) for policy search. The larger research community may have forgotten about previous successes of Neuroevolution.

Some of the most challenging reinforcement learning problems are those where reward signals are sparse and noisy. For many of these problems, we only know the outcome at the end of the task, such as whether the agent wins or loses, whether the robot arm picks up the object or not, or whether the agent has survived. Since NE only require the final cumulative reward that an agent gets at the end of its rollout in an environment, these are the types of problems where NE may have an advantage over traditional RL methods.

In this tutorial, I show how Neuroevolution can be successfully applied to Deep RL problems to help find a suitable set of model parameters for a neural network agent. Using popular modern software frameworks for RL (TensorFlow, OpenAI Gym, pybullet, roboschool), I will apply NE to continuous control robotic tasks, and show we can obtain very good results to control bipedal robot walkers, Kuka robot arm for grasping tasks, Minitaur robot, and also various existing baseline locomotion tasks common in the Deep RL literature. I will even show that NE can even obtain state-of-the-art results over Deep RL methods, and highlight ways to use NE that can lead to more stable and robust policies compared to traditional RL methods. I will also describe how to incorporate NE techniques into existing RL research pipelines taking advantage of distributed processing on Cloud Compute.

I will also discuss how to combine techniques from deep learning, such as the use of deep generative models, with Neuroevolution to solve more challenging Deep Reinforcement Learning problems that rely on high dimensional video inputs for continous robotics control, or for video game simulation tasks. We will look at combining model-based reinforcement learning approaches with Neuroevolution to tackle these problems, using TensorFlow, OpenAI Gym, and pybullet environments.

Lastly, we will cover recent developments where we have seen a lot of success in the past 2 years in areas where Neuroevolution has incorporated concepts from Deep Learning/RL, and vice versa. A case study will be presented when researchers prepare to tackle both areas, and we end with a group discussion about issues with cross-community collaborations with the audience.

Representations for Evolutionary Algorithms

Successful and efficient use of evolutionary algorithms (EA) depends on the choice of the genotype, the problem representation (mapping from genotype to phenotype) and on the choice of search operators that are applied to the genotypes. These choices cannot be made independently of each other. The question whether a certain representation leads to better performing EAs than an alternative representation can only be answered when the operators applied are taken into consideration. The reverse is also true: deciding between alternative operators is only meaningful for a given representation.

Research in the last few years has identified a number of key concepts to analyse the influence of representation-operator combinations on EA performance. Relevant concepts are the locality and redundancy of representations.

Locality is a result of the interplay between the search operator and the genotype-phenotype mapping. Representations have high locality if the application of variation operators results in new solutions similar to the original ones. Representations are redundant if the number of phenotypes exceeds the number of possible genotypes. Redundant representations can lead to biased encodings if some phenotypes are on average represented by a larger number of genotypes or search operators favor some kind of phenotypes.

The tutorial gives a brief overview about existing guidelines for representation design, illustrates the different aspects of representations, gives a brief overview of models describing the different aspects, and illustrates the relevance of the aspects with practical examples.

It is expected that the participants have a basic understanding of EA principles.

Runtime Analysis of Evolutionary Algorithms: Basic Introduction

Evolutionary algorithm theory has studied the time complexity of evolutionary algorithms for more than 20 years. Different aspects of this rich and diverse research field were presented in three different advanced or specialized tutorials at last year's GECCO. This tutorial presents the foundations of this field. We introduce the most important notions and definitions used in the field and consider different evolutionary algorithms on a number of well-known and important example problems. Through a careful and thorough introduction of important analytical tools and methods, including fitness-based partitions, typical events and runs and drift analysis, by the end of the tutorial the attendees will be able to apply these techniques to derive relevant runtime results for non-trivial evolutionary algorithms. Moreover, the attendees will be fully prepared to follow the more advanced tutorials that cover more specialized aspects of the field, including the new advanced runtime analysis tutorial on realistic population-based EAs. To assure the coverage of the topics required in the specialised tutorials, this introductory tutorial will be coordinated with the presenters of the more advanced ones. In addition to custom-tailored methods for the analysis of evolutionary algorithms we also introduce the relevant tools and notions from probability theory in an accessible form. This makes the tutorial appropriate for everyone with an interest in the theory of evolutionary algorithms without the need to have prior knowledge of probability theory and analysis of randomized algorithms.

Theory for Non-Theoreticians

This tutorial addresses GECCO attendees who do not regularly use theoretical methods in their research. For these, we give a smooth introduction to the theory of evolutionary computation (EC). Complementing other introductory theory tutorials, we do not discuss mathematical methods or particular results, but explain

• what theory of evolutionary algorithms aims at,
• how research in theory of evolutionary computation is done,
• how to interpret statements from the theory literature,
• what are some important contributions of theory to our field,
• and what are the current hot topics.

CMA-ES and Advanced Adaptation Mechanisms

The Covariance-Matrix-Adaptation Evolution Strategy is nowadays considered as the state-of-the art continuous stochastic search algorithm, in particular for optimization of non-separable, ill-conditioned and rugged functions. The CMA-ES consists of different components that adapt the step-size and the covariance matrix separately.
This tutorial will focus on CMA-ES and provide the audience with an overview of the different adaptation mechanisms used within CMA-ES and
the scenarios where their relative impact is important. We will in particular present the rank-one update, rank-mu update, active CMA for the covariance matrix adaptation. Different step-size mechanisms (CSA and TPA) as well as the scenario where they should be applied will be discussed.
We will address important design principles as well as questions related to parameter tuning that always accompany algorithm design. The input parameters such as the initial mean, the initial step-size, and the population size will be discussed in relation with the ruggedness of functions. Restart strategies that automatize the input parameter tuning will be presented.

Decomposition Multi-Objective Optimization: Current Developments and Future Opportunities

Evolutionary multi-objective optimization (EMO) has been a major research topic in the field of evolu- tionary computation for many years. It has been generally accepted that combination of evolutionary algorithms and traditional optimization methods should be a next generation multi-objective optimization solver. As the name suggests, the basic idea of the decomposition-based technique is to transform the original complex problem into simplified subproblem(s) so as to facilitate the optimization. Decomposition methods have been well used and studied in traditional multi-objective optimization. MOEA/D decom- poses a multi-objective problem into a number of subtasks, and then solves them in a collaborative manner. MOEA/D provides a very natural bridge between multi-objective evolutionary algorithms and traditional decomposition methods. It has been a commonly used evolutionary algorithmic framework in recent years.
Within this tutorial, a comprehensive introduction to MOEA/D will be given and selected research results will be presented in more detail. More specifically, we are going to (i) introduce the basic principles of MOEA/D in comparison with other two state-of-the-art EMO frameworks, i.e., Pareto- and indicator-based frameworks; (ii) present a general overview of state-of-the-art MOEA/D variants and their applications; (iii) discuss the future opportunities for possible further developments.
The intended audience of this tutorial can be both novices and people familiar with EMO or MOEA/D. In particular, it is self-contained that foundations of multi-objective optimization and the basic working principles of EMO algorithms will be included for those without experience in EMO to learn. Open questions will be posed and highlighted for discussion at the latter session of this tutorial.

Dynamic Parameter Choices in Evolutionary Computation

One of the most challenging problems in solving optimization problems with evolutionary algorithms (EAs) is the choice of the parameters, which allow to adjust the behavior of the algorithms to the problem at hand. Suitable parameter values need to be found, for example, for the population size, the mutation strength, the crossover rate, the selective pressure, etc. The choice of these parameters can have a crucial impact on the performance of the algorithm and need thus to be executed with care.

In the early years of evolutionary computation there had been a quest to determine universally "optimal" parameter choices. At the same time, researchers have soon realized that different parameter choices can be optimal in different stages of the optimization process: in the beginning of an optimization process, for example, one may want to allow a larger mutation rate to increase the chance of finding the most promising regions of the search space ("exploration" phase) while later on, a small mutation rate guarantees the search to stay focused ("exploitation" phase). Such dynamic parameter choices are today standard in continuous optimization. Quite surprisingly, however, the situation is much different in discrete optimization, where non-static parameter choices have never lived up to their impact.

The ambition of this tutorial is to contribute to a paradigm change towards a more systematic use of dynamic parameter choices. To this end, we survey existing techniques to automatically select parameter values on the fly. We will discuss both experimental and theoretical results that demonstrate the unexploited potential of non-static parameter choices. Our tutorial thereby addresses experimentally as well as theory-oriented researchers alike.
No specific background is required to follow this tutorial.

Evolutionary Computation for Digital Art

Evolutionary algorithms have been used in various ways to create or guide the creation of digital art. In this tutorial we present techniques from the thriving field of biologically inspired art. We show how evolutionary computation methods can be used to enhance artistic creativity and lead to software systems that help users to create artistic work.

We start by providing a general introduction into the use of evolutionary computation methods for digital art and highlight different application areas. This covers different evolutionary algorithms including genetic programming for the creation of artistic images.
Afterwards, we discuss evolutionary algorithms to create artistic artwork in the context of image transition and animation. We show how the connection between evolutionary computation methods and a professional artistic approach finds application in digital animation and new media art, and discuss the different steps of involving evolutionary algorithms for image transition into the creation of paintings. Afterwards, we give an overview on the use of aesthetic features to evaluate digital art. The feature-based approach complements the existing evaluation through human judgments/analysis and allows to judge digital art in a quantitative way. Finally, we outline directions for future research and discuss some open problems.

Next Generation Genetic Algorithms

New developments in Gray Box Optimization makes it possible to construct new forms of Genetic Algorithms that do not use random mutation or random recombination. Instead, for certain classes of NP Hard problems (ranging from MAXSAT to the Traveling Salesman Problem), it is possible to exactly compute the location of improving moves (often in constant time), and to use highly efficient forms of greedy deterministic recombination. In some domains, this makes random mutation and random recombination obsolete. Deterministic “Partition Crossover” can be applied to k-bounded pseudo-Boolean optimization problems such as MAXSAT and NK Landscapes as well as problems such as the Traveling Salesman Problem (TSP). Partition Crossover locally decomposes a recombination graph into q subgraphs in O(n) time. It can then identify the best of 2!possible offspring. For example, for q=40, partition crossover returns the best of one trillion (2!") possible offspring. If the parents are local optima, the offspring are guaranteed to be locally optimal in the largest hyperplane subspace containing both parents, and offspring are typically also local optima in the full space. This allows partition crossover to directly “tunnel” between local optima, moving directly from local optimum to local optimum. New innovations in this tutorial include the use of ``articulation points” to discover new additional decompositions of k-bounded pseudo-Boolean functions. And new work has shown how large industrial and ``crafted” MAX-kSAT problems can be optimized using these methods: the results are competitive with current state of the art Iterative Local Search Methods. Other recent results also use a similar form of local decomposition coupled with greedy and deterministic optimization. When applied to multiply constrained scheduling problems, the genetic algorithm is able to solve industrial problems with unto 1 billion variables.

NEW Recent Advances in Fitness Landscape Analysis

Fitness landscape analysis (FLA) can be used to characterise optimisation problems by analysing the underlying search space in terms of the objective to be optimised. There have been many recent advances in the field of FLA on the development of methods and measures that have been shown to be effective in the understanding of complex problems, algorithm behaviour, and the selection of algorithms.

This tutorial is aimed at delegates interested in developing a deeper understanding of the complexities of search spaces and how these impact on the performance of algorithms.

The tutorial will cover both discrete and continuous domains and will include the following topics:

- Fundamental concepts of fitness landscapes
- Local optima networks (LONs) for understanding global structure and modelling high dimensional spaces
- Case study: LONs applied to feature selection for classification
- Case study: Landscape-aware algorithm selection for Constraint-handling

NEW Recent Advances in Particle Swarm Optimization Analysis and Understanding

The main objective of this tutorial will be to inform particle swarm optimization (PSO) practitioners of the many common misconceptions and falsehoods that are actively hindering a practitioner’s successful use of PSO in solving challenging optimization problems. While the behaviour of PSO’s particles has been studied both theoretically and empirically since its inception in 1995, most practitioners unfortunately have not utilized these studies to guide their use of PSO. This tutorial will provide a succinct coverage of common PSO misconceptions, with a detailed explanation of why the misconceptions are in fact false, and how they are negatively impacting results. The tutorial will also provide recent theoretical results about PSO particle behaviour from which the PSO practitioner can now make better and more informed decisions about PSO and in particular make better PSO parameter selections. The tutorial will focus on the following important aspects of PSO behaviour

• Understanding why the random variables used in the velocity update should not be scalars, but rather vectors of random values
• Exploring the effects of different ways in which velocity can be initialized
• Clearning up issues with reference to velocity clamping
• Influence of social topology and different iteration strategies on performance
• Understanding PSO control parameters, and how to use them more efficiently. The importance of parameter selection will be illustrated with an interactive demo where audience members will vote for/suggest control parameters. From the set of audience selected control parameters relative performance ranking, based on popular benchmark suites, of these configuration will be given in relation to a very extensive set of possible configurations. This demo will clearly illustrate why the subsequent theoretical discussion on control parameters is so import for effective PSO use.
• Existing theoretical PSO results and what they mean to a PSO practitioner
• Roaming behaviour of PSO particles
• Understanding why PSO struggles with large-scale optimization problems
• Known stability criteria of PSO algorithms
• Effects of particle stability of PSO’s performance
• How to derive new stability criteria for PSO variants and verify them
• Control parameter tuning, and self-adaptive control parameters
• Is the PSO a local optimizer or a global optimizer?

With the knowledge presented in this tutorial a PSO practitioner will gain up to date theoretical insights into PSO behaviour and as a result be able to make informed choices when utilizing PSO.

NEW Semantic Genetic Programming

Semantic genetic programming is a rapidly growing trend in Genetic Programming (GP) that aims at opening the ‘black box’ of the evaluation function and make explicit use of more information on program behavior in the search. In the most common scenario of evaluating a GP program on a set of input-output examples (fitness cases), the semantic approach characterizes program with a vector of outputs rather than a single scalar value (fitness). The past research on semantic GP has demonstrated that the additional information obtained in this way facilitates designing more effective search operators. In particular, exploiting the geometric properties of the resulting semantic space leads to search operators with attractive properties, which have provably better theoretical characteristics than conventional GP operators. This in turn leads to dramatic improvements in experimental comparisons.
The aim of the tutorial is to give a comprehensive overview of semantic methods in genetic programming, illustrate in an accessible way the formal geometric framework for program semantics to design provably good mutation and crossover operators for traditional GP problem domains, and to analyze rigorously their performance (runtime analysis). A recent extension of this framework to Grammatical Evolution will be also presented. Other promising emerging approaches to semantics in GP will be reviewed. In particular, the recent developments in the behavioural programming and approaches that automatically acquire a multi-objective characterization of programs will be covered as well. Current challenges and future trends in semantic GP will be identified and discussed.
Efficient implementation of semantic search operators may be challenging. We will illustrate very efficient, concise and elegant implementations of these operators, which are available for download from the web.

Sequential Experimentation by Evolutionary Algorithms

This tutorial addresses applications of Evolutionary Algorithms (EAs) to global optimization tasks where the objective function cannot be calculated (no explicit model nor a simulation exist), but rather requires a measurement/assay ("wet experiment") in the real-world – e.g., in pharmaceuticals, biocatalyst design, protein expression, quantum processes – to mention only a few.

The use of EAs for experimental optimization is placed in its historical context with an overview of the landmark studies in this area carried out in the 1960s at the Technical University of Berlin. At the same time, statistics-based Design of Experiments (DoE) methodologies, rooted in the late 1950s, constitute a gold-standard in existing laboratory equipment, and are therefore reviewed as well at an introductory level to EC audience.

The main characteristics of experimental optimization work, in comparison to optimization of simulated systems, are discussed, and practical guidelines for real-world experiments with EAs are given. For example, experimental problems can constrain the evolution due to overhead considerations, interruptions, changes of variables, missing assays, imposed population-sizes, and target assays that have different evaluation times (in the case of multiple objective optimization problems).

Selected modern-day case studies show the persistence of experimental optimization problems today. These cover experimental quantum systems, combinatorial drug discovery, protein expression, and others. These applications can throw EAs out of their normal operating envelope, and raise research questions in a number of different areas ranging across constrained EAs, multiple objective EAs, robust and reliable methods for noisy and dynamic problems, and metamodeling methods for expensive evaluations.

Simulation Optimization

The optimization of parameters of a simulation model is usually denoted as Simulation Optimization. This is a typical problem in the design and optimization of complex systems, where a solution can only be evaluated by means of running a simulation. On the one hand, simulation optimization is black box optimization, which suits evolutionary algorithms well. On the other hand, simulation models are often stochastic, which affects the selection step in evolutionary algorithms. Furthermore, running a simulation is usually computationally expensive, so the number of solutions that can be evaluated is limited.

This tutorial will survey various simulation optimization techniques and then explain in more detail what it takes to successfully apply evolutionary algorithms for simulation optimization. It will brie y cover parallelization and surrogate models to reduce the runtime, but then focus in particular on the handling of noise. The tutorial assumes that the audience is familiar with evolutionary computation.

Solving Complex Problems with Coevolutionary Algorithms

Coevolutionary algorithms (CoEAs) go beyond the conventional paradigm of evolutionary computation in having the potential to answer questions about what to evolve against (competition) and / or establish how multi-agent behaviours can be discovered (cooperation). Competitive coevolution can be considered from the perspective of discovering tests that distinguish between the performance of candidate solutions. Cooperative coevolution implies that mechanisms are adopted for distributing fitness across more than one individual. In both these variants, the evolving entities engage in interactions that affect all the engaged parties, and result in search gradients that may be very different from those observed in conventional evolutionary algorithm, where fitness is defined externally. This allows CoEAs to model complex systems and solve problems that are difficult or not naturally addressed using conventional evolution.

This tutorial will begin by first establishing basic frameworks for competitive and cooperative coevolution and noting the links to related formalisms (interactive domains and test-based problems). We will identify the pathologies that potentially appear when assuming such coevolutionary formulations (disengagement, forgetting, mediocre stable states) and present the methods that address these issues. Compositional formulations will be considered in which hierarchies of development are explicitly formed leading to the incremental complexification of solutions. The role of system dynamics will also be reviewed with regards to providing additional insight into how design decisions regarding, say, the formulation assumed for cooperation, impact on the development of effective solutions. We will also present the concepts of coordinate systems and underlying objectives and how they can make search/learning more effective. Other covered developments will include hybridization with local search and relationships to shaping.

The concepts covered in the tutorial will be illustrated with numerous examples and applications, including the cooperative development of programs (Rubik’s Cube, Arcade Learning Environment, ViZDoom), competitive coevolution of game strategies (Othello), and machine learning (learning from data streams and object recognition).

Visualization in Multiobjective Optimization

Multiobjective optimization algorithms usually produce a set of trade-off solutions approximating the Pareto front where no solution from the set is better than any other in all objectives (this is called an approximation set). While there exist many measures to assess the quality of approximation sets, no measure is as effective as visualization, especially if the Pareto front is known and can be visualized as well. Visualization in evolutionary multiobjective optimization is relevant in many aspects, such as estimating the location, range, and shape of the Pareto front, assessing conflicts and trade-offs between objectives, selecting preferred solutions, monitoring the progress or convergence of an optimization run, and assessing the relative performance of different algorithms.

This tutorial will provide a comprehensive overview of methods used in multiobjective optimization for visualizing either individual approximation sets resulting from a single algorithm run or multiple approximation sets stemming from repeated runs. The methods will be organized in a recently proposed taxonomy of visualization methods and analyzed according to a methodology for assessing and comparing visualization methods. The methodology uses a list of requirements for visualization methods and benchmark approximation sets in a similar way as performance metrics and benchmark test problems are used for comparing optimization algorithms.

NEW Concurrency in evolutionary algorithms

This tutorial will first describe the current paradigms of concurrent programming, including mainly channel-based concurrency, and which languages work with it. It will then proceed to examine the changes evolutionary algorithms have to undergo in order to properly leverage these kind of software architectures.
It will be addressed mainly to students who have some knowledge of programming techniques, as well as those who understand basic concepts of evolutionary algorithms and want to advance on the its basic architecture and its implementations. Eventually, the attendee will be able to reformulate existing evolutionary algorithms in a concurrent setting and know basic concepts on how to implement them using concurrent languages such as Go, Scala or Perl 6.

The tutorial will have the following outline:

• Why it is now the moment of concurrent algorithms and languages.
• Basic concepts of concurrency.
• Functional programming and what it's got to do with concurrent programming.
• The concept of state and how it's related to concurrent programming.
• Stateless algorithms HOWTO
• How to eliminate state from evolutionary algorithms
• Levels of concurrency and programming patterns for concurrent evolutionary algorithms
• Issues and challenges in concurrent evolutionary algorithms.

Nowadays, concurrency has the promise of bringing high-performance computing to the most plain vanilla desktop, since the increase in power in CPUs has been due mainly to architectural, and not physical, changes. However, the existence of languages that can use this concurrency properly is not so mainstream, with just a few languages implementing core functionalities to work with concurrent primitives, data structures and functions. Most languages are based in a relatively old concept, communicating sequential processes, which make different threads only share state through communication; this has led to the rise of functional languages (which do not have side effect and do not change state in pure functions) and reactive architectures (which instead of working sequentially, impose a certain sequence on data flow. This tutorial will explain these basic concepts, and then will apply it to evolutionary algorithms, seeing how the canonical evolutionary algorithm can be changed to a stateless algorithm, while keeping the bioinspired spirit and leveraging concurrency.

NEW Creative Evolutionary Computation

Creativity is a core ability that was fostered throughout human evolution: it has enabled new ways of solving problems and doing art, but it has also led to discoveries through unconventional ways. Can computational processes be creative? Who should judge and what should be critiqued? How can artificial evolution help such computational processes? In turn, how can evolutionary search benefit from computational creativity?

To address the above questions, in this tutorial we use principles such as unconventional search, deception, value, novelty, surprise, and quality diversity as overarching elements for connecting evolutionary computation (EC) and computational creativity (CC). In particular, we will explore the research area in which bio-inspired algorithmic design meets creativity and search and, hence, we attempt to incorporate foundational ideas and concepts from evolutionary computation in the computational creativity domain. EC areas such as divergent search and quality diversity could benefit from theoretical approaches of computational creativity and empirical implementations of CC-inspired algorithms. Similarly, we argue that CC research and practice can only help in advancing work on EA theory and algorithm design.

Detailed Content:
The proposed structure of the tutorial covers the following topics:

• Introduction to Computational Creativity
  • Basic Notions and Definitions
  • What is Creativity? What is Computational Creativity (CC)? Evaluation of CC
  • Domains of CC: from problem solving to art
• Artificial Evolution for Computational Creativity
  • What makes evolution ideal for CC?
  • Value, Novelty and Surprise as drivers of Evolution
• Core Domains of CC via evolution
  • Problem Solving (e.g. maze navigation)
  • Art & Music
  • Digital Games
  • Mathematical & Algorithmic Discovery
• Next Steps
  • Future challenges and open questions
  • Emotion as a driver for CC

Evolutionary Computation and Evolutionary Deep Learning for Image Analysis, Signal Processing and Pattern Recognition

The intertwining disciplines of image analysis, signal processing and pattern recognition are major fields of computer science, computer engineering and electrical and electronic engineering, with past and on-going research covering a full range of topics and tasks, from basic research to a huge number of real-world industrial applications.

Among the techniques studied and applied within these research fields, evolutionary computation (EC) including evolutionary algorithms, swarm intelligence and other paradigms is playing an increasingly relevant role. Recently, evolutionary deep learning has also attracted very good attention to these fields. The terms Evolutionary Image Analysis and Signal Processing and Evolutionary Computer Vision are more and more commonly accepted as descriptors of a clearly defined research area and family of techniques and applications. This has also been favoured by the recent availability of environments for computer hardware and systems such as GPUs and grid/cloud/parallel computing systems, whose architecture and computation paradigm fit EC algorithms extremely well, alleviating the intrinsically heavy computational burden imposed by such techniques and allowing even for real-time applications.

The tutorial will introduce the general framework within which Evolutionary Image Analysis, Signal Processing and Pattern Recognition can be studied and applied, sketching a schematic taxonomy of the field and providing examples of successful real-world applications. The application areas to be covered will include edge detection, segmentation, object tracking, object recognition, motion detection, image classification and recognition. EC techniques to be covered will include genetic algorithms, genetic programming, particle swarm optimisation, evolutionary multi-objective optimisation as well as memetic/hybrid paradigms. In particular, we will discuss the detection of relevant set of features for classification based on an information-theoretical approach derived from complex system analysis. We take a focus on the use of evolutionary deep learning idea for image analysis --- this includes automatic learning architectures, learning parameters and transfer functions of convolutional neural networks (and autoencoders and genetic programming if time allows). The use of GPU boxes will be discussed for real-time/fast object classification. We will show how such EC techniques can be effectively applied to image analysis and signal processing problems and provide promising results.

NEW Exploratory Landscape Analysis

Whenever one performs optimization on a (continuous) problem, having at least a vague idea of its landscape structure usually is very beneficial, as this allows to select and/or configure a suitable, well-performing optimization algorithm. However, characterizing problem landscapes poses (at least) two challenges: (i) one wants to avoid spending major parts of the overall budget on the characterization of the landscape (as this would reduce the budget that is left for the optimizer), and (ii) the properties should be automatically measurable/computable (otherwise one would always depend on the availability of some expert, i.e., a real person). As a result, over the last decade an entire research area - denoted Exploratory Landscape Analysis (ELA) - has developed around the topic of automated and feature-based problem characterization for continuous optimization problems.
Within this tutorial, we will first introduce the general concepts of automated algorithm selection - being one of the main use cases of ELA - as well as ELA itself. Next, we will provide a detailed overview of its state of the art, succeeded by a brief presentation of exemplary success stories for the usage of ELA. Amongst others, this will include studies on algorithm selection and configuration, the detection of funnel structures, or the comparison of common optimization benchmarks. Moreover, we will address how ELA actually helps to improve our understanding of problem characteristics (and thus the problems themselves), as well as the search behavior of optimization algorithms.
The remainder of the tutorial will be used for an interactive live-demo, in which our participants will perform ELA on some continuous optimization problems.

Push

Push is a general purpose, multi-type, Turing complete programming language for programs that evolve in an evolutionary computation system. Initially developed in 2000, it has been used for a range of research projects and applications, including the production of human-competitive results and state-of-the-art work on general program synthesis.

Push and systems that evolve Push programs (such as PushGP) are available in a variety of host languages. However, the core concepts of Push are simple enough that programmers should also be able to build their own Push systems relatively quickly, and to incorporate them into their own evolutionary computation systems. This tutorial will present examples and best practices that will help participants to use Push effectively in their own work, whether they use existing libraries or develop their own.

Push has unusually simple syntax, which makes it particularly easy to randomly generate and vary valid programs. It nonetheless supports rich data and control structures, which in most other languages involve syntax restrictions that can be difficult to maintain during evolutionary change. Furthermore, the data and control structures used by a Push program can themselves emerge through the evolutionary process.

This tutorial will provide a detailed introduction to the Push programming language, and will demonstrate the use of the PushGP genetic programming system with open source libraries in Python (PyshGP) and Clojure (Clojush). Participants will be invited to install and interact with these libraries during the tutorial.

Interleaved with our description and demonstrations of Push and PushGP will be demonstrations of the use of analytical tools to explore ways in which evolved Push programs are actually taking advantage of the language’s expressive features. We will illustrate, for example, the effective use of multiple types and type-appropriate functions, the evolution and modification of code blocks and looping/recursive constructs, and the ability of Push programs to handle multiple, potentially related tasks. We will also briefly illustrate Push-based "autoconstructive evolution" systems, in which evolutionary methods co-evolve with solutions to problems.

We will conclude with a brief review of over a decade of Push-based research, including the production of human-competitive results, along with recent enhancements to Push that are intended to support the evolution of complex and robust software systems.

Theory of Estimation-of-Distribution Algorithms

Estimation-of-distribution algorithms (EDAs) are general metaheuristics for optimization that represent a more recent and popular alternative to classical approaches like evolutionary algorithms. In a nutshell, EDAs typically do not directly evolve populations of search points but build probabilistic models of promising solutions by repeatedly sampling and selecting points from the underlying search space. However, until recently the theoretical knowledge of the working principles of EDAs was relatively limited.

In the last few years, there has been made significant progress in the theoretical understanding of EDAs. This tutorial provides an up-to-date overview of the most commonly analyzed EDAs and the most important theoretical results in this area, ranging from convergence to runtime analyses. Different algorithms and objective functions, including optimization under uncertainty (i. e. noise) are covered. The tutorial will present typical benchmark functions and tools relevant in the theoretical analysis. It will be demonstrated that some EDAs are very sensitive with respect to their parameter settings and that their runtime can be optimized for very different choices of learning parameters. Altogether, the tutorial with make the audience familiar with the state of the art in the theory of EDAs and the most useful techniques for the analysis. We will conclude with open problems and directions for future research.