Tutorials

NEW A Practical Guide to Benchmarking and 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. Therefore, assessing and predicting the performance of evolutionary algorithms in "the real world" requires to obtain and analyze empirical data. These data arise either from "artificial" benchmarks or from "real-world" problems themselves. This tutorial is concerned with experimentation and benchmarking algorithms. This includes the design of experimental performance studies (small or large ones) and the presentation, analysis and assessment of the obtained data and results.

The aim of the tutorial is to enable participants to
1) design a sound benchmark study,
2) identify meaningful measurements for the performance assessment, and
3) display and interpret experimental results in a meaningful and accessible way.

The ultimate goal of experimental benchmark studies is to achieve quantitatively meaningful performance assessments, generally with predictive power in regard to "the real world". The considered topics will include experimental study design, accessible presentation in form of tables, run-length distributions (data profiles), performance profiles, scatter plots, scale-up studies, success probabilities and restarts. Furthermore, the number of trials, the role of invariance, statistical significance, and the most common mistakes when conducting experimental studies are touched upon.

A selected number of techniques is exemplified for the case of benchmarking continuous domain evolutionary and non-evolutionary algorithms in a black-box scenario using the BBOB COmparing Continuous Optimizers (COCO) platform, http://coco.gforge.inria.fr/doku.php.

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 many sequential decision tasks. 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. As a result, deep learning can be scaled to utilize more of the available computing power, and extended to domains combining multiple modalities, such multiple visual and language tasks. In this tutorial, I will review
(1) neuroevolution methods that evolve fixed-topology networks, network topologies, and network construction processes,
(2) ways of combining gradient-based training with evolutionary methods, and
(3) applications of these techniques in control, robotics, artificial life, games, image processing, and language.

Demos: The tutorial draws from over 30 videos illustrating methods and applications of neuroevolution, including rocket control, multilegged walking, predator-prey coevolution, evolving morphology and behavior for virtual creatures, the NERO machine-learning video game, a Turing Test for game bots, object and scene recognition, captioning, and language and music modeling.

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.

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 does exist. Instead, a 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.

NEW Fitness Landscape Characterisation of Optimisation Problems

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 algorithm behaviour, the prediction of metaheuristic performance and the selection of algorithms.

When optimisation problems are complex, it can be useful to characterise the search landscapes to gain insight into the nature of the problem. The ultimate aim of characterising problems is to answer questions such as: How challenging is a particular problem for an algorithm? How likely is an algorithm to produce good results given a problem with a particular search landscape? Why did my algorithm perform so well/badly on this particular problem?

The aim of this tutorial is to introduce delegates to the field of FLA in a theoretical and practical way. After the tutorial, delegates should feel confident to use some of the existing FLA techniques in practice.

The tutorial will cover the following topics:
- An overview of the theory of FLA
- FLA techniques for combinatorial optimisation problems
- FLA techniques for continuous optimisation problems
- Future research directions

The tutorial will end with an interactive challenge to delegates. Working in groups, delegates will be tasked with guessing the ranks of 2D fitness landscapes based on specified FLA metrics. The winning group will receive a prize.

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 framework. It explains how the powerful capability of genetic programming is derived from modular algorithmic components: executable representations such as an abstract syntax tree, variation operators that preserve syntax and explore a variable length, hierarchical solution space, appropriately chosen programming functions and fitness function specification.

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.

Introducing Rule-based Machine Learning: Capturing Complexity

In the context of evolutionary machine learning, rule-based machine learning (RBML) algorithms are an often overlooked class of algorithms with flexible features employing an alternative paradigm of piece-wise modeling that sets them apart from other strategies, particularly with respect to modeling complexity. This tutorial will introduce the RBML paradigm and three of the most successful methodological RBML families, i.e. Learning Classifier Systems (LCS), Association Rule Learning (ARL) and Artificial Immune Systems (AIS). Particular focus will be placed on learning classifier systems (LCS), or more specifically Michigan-style LCSs, being the most prevalent and foundational of the RBML algorithms. Michigan-style LCSs combine the global search of evolutionary algorithms with the local optimization of reinforcement or supervised learning. Michigan-style LCS algorithms uniquely distribute learned patterns over a collaborative population of individually interpretable (IF: THEN) rules. This allows the algorithm to flexibly and effectively describe complex and diverse problem spaces found in behavior modeling, function approximation, classification, prediction, and data mining.

The overall goal of this tutorial is to increase awareness of RBML algorithms as not only a viable, but often advantageous alternative to other machine learning approaches, as well as to promote a fundamental understanding of how they work, and where they can be applied. While ExSTraCS will be the focus of the demonstration, this tutorial will review and contrast many of the other major LCS algorithms available in the literature, as well as discuss statistical analysis, interpretation, and data visualization strategies for knowledge discovery. Additionally I will tie into this tutorial to the upcoming publication of an introductory textbook on LCS which should be published by GECCO 2017.

Introduction to Artificial Gene Regulatory Networks

Gene regulatory networks are a central mechanism in the regulation of gene expression in all living organisms’ cells. Their functioning is nowadays very well understood: they are based on the production of proteins enhanced or inhibited by other proteins from the inside and/or the outside of the cells. This produces complex dynamics with which cells from the same organism, with the exact same DNA, can form very different types (through cell differentiation) and have very different behaviors according to their types and positions.

This tutorial will first introduce the biology of these networks, from the genetic aspect to the dynamics of gene regulation. Then, biologically plausible models will be presented to highlight the complexity of dynamics gene regulatory networks can produce. Using that model, we will show how computational models can be designed so that a genetic algorithm can optimize the network efficiently. We will present a set of applications in which artificial gene regulatory networks are plugged into diverse virtual agents (artificial cells in an artificial embryogenesis context, direct connection to the sensors and effectors or high-level behavior regulation in others). Demos, showing the results obtained with this system, will be presented all along the tutorial.

Introduction to Randomized Continuous Optimization

Continuous optimization problems arise in many domains in academia or industry. They are commonly formulated as black-box problems that can solely return function values at queried points but no other information like gradient of the function. Typical difficulties that the optimizer then need to face are non-separability, curse of dimensionality, ill-conditioning and ruggedness of the function. In this context, randomized methods like evolution strategies are often the methods of choice.

This introductory tutorial on randomized continuous optimization will start by discussing typical difficulties of optimization problems in continuous domain. It will then introduce basics of randomized method with a specific focus on evolution strategies. In particular sampling of solutions and adaptation mechanisms will be presented. Different algorithms will be introduced including simple evolution strategies, EDAs and CMA-ES. For this latter algorithm, the most advanced notions will be presented in the companion tutorial.

Theoretical concepts related to algorithm design will also be introduced, namely progress and convergence rates and invariance.

In a last part, we will discuss how to properly assess performance of black-box methods.

Introductory Statistics for EC: A Visual Approach

In the past, it was common to see papers published in Evolutionary Computational conferences that presented experimental results without any statistical analysis performed. Fortunately, it is now becoming widely accepted that experimental results lacking proper statistical analysis must be considered anecdotal at best, or even wholly inaccurate. In many areas within EC, and especially at GECCO, if your paper does not include a proper statistical analysis it will be rejected. Yet many researchers in the GEC field still exhibit an unfortunate lack of statistical rigor when performing and analyzing experiments.

This tutorial, a staple at past GECCOs, aims at providing the basic statistical framework that all experimenters in the EC field should follow. It covers introductory topics in statistics such as the T test, confidence intervals, non-parametric statistics, and will touch on multivariate and multifactorial analysis such as the Analysis of Variance (ANOVA) and regression analysis (both linear and polynomial), time permitting.

The tutorial is presented at an introductory level, and takes a very visual approach to statistics; relying on graphics and animation to provide an intuitive understanding of the subject, instead of the traditional equations, which cater to only the initiated. In other words, it is meant for any EC researcher, independent of their mathematical training, who want to compare their newly designed EC system against established EC systems to see if there is an improvement, or who want to determine which EC system performs better on their chosen problem; i.e. nearly everyone.

It is vital, if our community is to be taken seriously, for us to continue to educate ourselves (especially new Graduate students) on the statistical techniques that are considered de rigor for experiments performed in any field, such as ours, that is stochastic in nature.

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 use of statistical models in the Linkage Tree Genetic Algorithm (LTGA). 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.

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.

In EA practice one can distinguish two complementary approaches. The first approach uses indirect representations where a solution is encoded in a standard data structure, such as strings, vectors, or discrete permutations, and standard off-the-shelf search operators are applied to these genotypes. This is for example the case in standard genetic algorithms, evolution strategies, and some genetic programming approaches like grammatical evolution or cartesian genetic programming. To evaluate the solution, the genotype needs to be mapped to the phenotype space. The proper choice of this genotype-phenotype mapping is important for the performance of the EA search process. The second approach, the direct representation, encodes solutions to the problem in its most 'natural' space and designs search operators to operate on this 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 properties of representations are locality and redundancy.

Locality is a result of the interplay between the search operator and the genotype-phenotype mapping. 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 Population-based Evolutionary Algorithms

Populations are at the heart of evolutionary algorithms (EAs). They provide the genetic variation which selection acts upon. A complete picture of EAs can only be obtained if we understand their population dynamics. A rich theory on runtime analysis (also called time-complexity analysis) of EAs has been developed over the last 20 years. The goal of this theory is to show, via rigorous mathematical means, how the performance of EAs depends on their parameter settings and the characteristics of the underlying fitness landscapes. Initially, runtime analysis of EAs was mostly restricted to simplified EAs that do not employ large populations, such as the (1+1) EA. This tutorial introduces more recent techniques that enable runtime analysis of EAs with realistic population sizes.

The tutorial begins with a brief overview of the population-based EAs that are covered by the techniques. We recall the common stochastic selection mechanisms and how to measure the selection pressure they induce. The main part of the tutorial covers in detail widely applicable techniques tailored to the analysis of populations. We discuss random family trees and branching processes, drift and concentration of measure in populations, and level-based analyses.

To illustrate how these techniques can be applied, we consider several fundamental questions: When are populations necessary for efficient optimisation with EAs? What is the appropriate balance between exploration and exploitation and how does this depend on relationships between mutation and selection rates? What determines an EA's tolerance for uncertainty, e.g. in form of noisy or partially available fitness?

Theory for Non-Theoreticians

This tutorial addresses GECCO attendees who do not or just seldom use mathematical proofs in their everyday research activities. We provide a smooth introduction to the theory of evolutionary computation (EC). Complementing other introductory theory tutorials, we do NOT aim at equipping you with tools or theorems that can be beneficial for your research. Instead, after this tutorial, you will have a clear opinion on

- 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.

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).

NEW Evolutionary Large-Scale Global Optimization: An Introduction

Many real-world optimization problems involve a large number of decision variables. The trend in engineering optimization shows that the number of decision variables involved in a typical optimization problem has grown exponentially over the last 50 years, and this trend continues with an everincreasing rate. The proliferation of big-data analytic applications has also resulted in the emergence of large-scale optimization problems at the heart of many machine learning problems. The recent advance in the area of machine learning has also witnessed very large scale optimization problems encountered in training deep neural network architectures (so-called deep learning), some of which have over a billion decision variables. It is this “curse-of-dimensionality” that has made largescale optimization an exceedingly difficult task. Current optimization methods are often ill-equipped in dealing with such problems. It is this research gap in both theory and practice that has attracted much research interest, making large-scale optimization an active field in recent years. We are currently witnessing a wide range of mathematical and metaheuristics optimization algorithms being developed to overcome this scalability issue. Among these, metaheuristics have gained popularity due to their ability in dealing with black-box optimization problems.

In this tutorial, we provide an overview of recent advances in the field of evolutionary large-scale global optimization with an emphasis on the divide-and-conquer approaches (a.k.a. decomposition methods). In particular, we give an overview of different approaches including the non-decomposition based approaches such as memetic algorithms and sampling methods to deal with large-scale problems. This is followed by a more detailed treatment of implicit and explicit decomposition algorithms in large-scale optimization. Considering the popularity of decomposition methods in recent years, we provide a detailed technical explanation of the state-of-the-art decomposition algorithms including the differential grouping algorithm and its latest improved derivatives (such as global DG and DG2 algorithms), which outperform other decomposition algorithms on the latest large-scale global optimization benchmarks. We also address the issue of resource allocation in cooperative coevolution and provide a detailed explanation of some recent algorithms such as the contribution-based cooperative co-evolution family of algorithms. Overall, this tutorial takes the form of a critical survey of the existing methods with an emphasis on articulating the challenges in large-scale global optimization in order to stimulate further research interest in this area.

NEW Exploratory Landscape Analysis

The selection of the best suited algorithm for an optimization problem is usually a complex and difficult task, especially for expensive Black-Box problems. Exploratory Landscape Analysis (ELA) has been conceived as approach for guiding or even automatizing this selection process. It extracts — not necessarily intuitively understandable — landscape features, based on a usually rather small initial sample of observations from the underlying optimization problem. In the extreme case, a well-distributed initial population of an evolutionary algorithm could already be sufficient to compute meaningful (numerical) features that could improve the performance of the algorithm selection models.
Until now, ELA is mostly used in the context of continuous, single-objective, global optimization problems, but it can also be transferred to other domains (e.g. discrete, multi-objective, or multimodal optimization).

We will begin this tutorial with an introduction into the general concept of (automated) algorithm selection, which is one of the main use cases of ELA, followed by a presentation of some examples from different domains, in which ELA has successfully been used to improve the algorithm selection process. Next, we will present the general idea of ELA — What is it exactly? How can it be used? What can we get out of it? What are its limitations? — and afterwards provide a detailed overview of the current state of ELA, including recently published extensions to the previously mentioned additional domains.
Also, we will discuss the differences between single- and multi-objective, as well as multimodal and global optimization problems (with a focus on continuous problems) and show how ELA features can help us to improve our understanding of the different problem landscapes and how that knowledge in return can be used to get a better comprehension of the behavior of the applied optimization algorithms.
The remainder of the tutorial will be used for an interactive live-demo, in which we will demonstrate how one can perform ELA on continuous optimization problems by using the R-packages "smoof" and "flacco".

Expressive Genetic Programming: Concepts and applications

The language in which evolving programs are expressed can have significant impacts on the dynamics and problem-solving capabilities of a genetic programming system. In GP these impacts are driven by far more than the absolute computational power of the languages used; just because a computation is theoretically possible in a language, it doesn’t mean it’s readily discoverable or leveraged by evolution. Highly expressive languages can facilitate the evolution of programs for any computable function using, as appropriate, multiple data types, evolved subroutines, evolved control structures, evolved data structures, and evolved modular program and data architectures. In some cases expressive languages can even support the evolution of programs that express methods for their own reproduction and variation (and hence for the evolution of their offspring).

This tutorial will present a range of approaches that have been taken for evolving programs in expressive programming languages. We will then provide a detailed introduction to the Push programming language, which was designed specifically for expressiveness in genetic programming systems. Push programs are syntactically unconstrained but can nonetheless make use of multiple data types and express arbitrary control structures, supporting the evolution of complex, modular programs in a particularly simple and flexible way.

Interleaved with our description of the Push language will be demonstrations of the use of analytical tools such as graph databases and program diff/merge 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’ll 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.

Generative and Developmental Systems

In evolutionary computation it is common for the genotype to map directly to the phenotype such that each gene in the genotype represents a single discrete component of the phenotype. While this convention is widespread, in nature the mapping is not direct. Instead, the genotype maps to the phenotype through a process of development, which means that each gene may be activated multiple times and in multiple places in the process of constructing the phenotype.

This tutorial will examine why such indirect mapping may be critical to the continuing success of evolutionary computation. Rather than just an artifact of nature, indirect mapping means that vast phenotypic spaces (e.g. the 100 trillion connection human brain) can be searched effectively in a space of far fewer genes (e.g. the 30,000 gene human genome). The tutorial will introduce this research area, called Generative and Developmental Systems (GDS; now part of the Complex Systems track at GECCO), by surveying milestones in the field and introducing its most profound puzzles. In particular, the first half of the tutorial will review the most historically high-impact algorithms and achievements in the field while the second half will probe more deeply into cutting-edge research and its greatest current challenges.

Most importantly, what is the right abstraction of natural development to capture its essential advantages without introducing unnecessary overhead into the search?

NEW 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 cases, this makes random mutation and random recombination unnecessary and 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^q 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.

For the TSP, these results can be use to improve the best existing TSP solvers (e.g., LKH and EAX). It can also be used to improve exact Branch and Bound algorithms such as Concorde. For k-bounded pseudo-Boolean optimization problems these new algorithms are able to solve problems with 1 million variables.

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.

These results have the potential to revolutionized evolutionary computation. The methods are decidedly not black box optimizers, and the new algorithms trivially solve many black box benchmarks: ONEMAX, Leading Ones and Trap functions are solved in O(n) time using only 1 evaluation.

NEW Non-Static Parameter Choices in Evolutionary Computation

When applying evolutionary algorithms to optimization problems, the user often has to decide upon a number of parameters; for example, the population size, the mutation strength, the crossover rate, 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, for example, one may want to allow a larger mutation rate so as to increase the chance of finding the most promising regions of the search space ("exploration phase") while later on a smaller mutation rate guarantees the search to stay focused ("exploitation phase"). Quite surprisingly, this intuitive concept of dynamic parameter choices has never played an important role for discrete optimization with evolutionary computation methods - neither in empirical, nor in theoretical investigations. Most recently, the topic has been revived by a series of theoretical and experimental works proving strict superiority of dynamic parameter settings for a number of different discrete optimization processes. The aim of this tutorial is to survey and discuss parameter update schemes that have been proposed in the EC literature. The tutorial addresses both experimentally- as well as theory-oriented researchers.

NEW Recent Advances in Evolutionary Multi-Criterion Optimization

Evolutionary multi-criterion optimization (EMO) has become an established subfield within the evolutionary computation (EC) field, simply because of its appeal and importance to practical problems. Real-world problems usually involve multiple conflicting criteria and resulting outcomes in these problems are a number of trade-off solutions. EC methods became useful in solving these problems compared to their classical counterparts, since they can find and store multiple solutions in their populations and they provide an implicit parallel search. The EMO research was started in early nineties (more than two decades ago) and many different methodologies have been suggested since then. Software companies have emerged having specialized products for solving multi-criterion problems in industrial set-ups.

In the past 20 years, besides developing new methodologies, EMO field has also found new directions for research and application, which are relatively unknown to many EC researchers who are not directly working in EMO area. Some of these new ideas have deep-rooted applications to other EC areas and EMO researchers can borrow key EC findings to improve EMO algorithms and applications. The new ideas need to be explored and nurtured further, requiring deep theoretical, algorithmic, and application-oriented studies. In this tutorial, we shall introduce and discuss some of the recent advances in EMO field so that EC researchers and practitioners, in general, and EMO researchers, in particular, can make a comprehensive scope and directions of research in EMO area.

NEW Sequential Experimentation by Evolutionary Algorithms

This tutorial addresses applications of Evolutionary Algorithms (EAs) to optimization tasks where the function evaluation cannot be done through a computer simulation, but requires the execution of an experiment in the real-world (e.g., pharmaceuticals, biocatalyst design, protein engineering, quantum processes, wind tunnel experiments, to mention 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. Statistical Design of Experiments (DoE) methodologies from the late 50s are also reviewed, and it is shown how relatives of these approaches are converging in modern sequential DoE/EA hybrid methods.

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 objective function values, population sizes that are determined by the experimental platform, and objective functions that have differing evaluation times (in the case of multiobjective optimization problems).

A series of modern-day case studies shows the persistence of experimental optimization problems today. These cover experimental quantum systems, real DNA and RNA evolution, combinatory drug discovery, tuning of operating conditions, coffee and chocolate processing, and others. These applications can push EA methods outside of their normal operating envelope, and raise research questions in a number of different areas ranging across constrained EAs, multiobjective EAs, robust and reliable methods for noisy and dynamic problems, and metamodeling methods for expensive evaluations.

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 (soccer, MsPacMan, Rubik’s Cube), competitive coevolution of game strategies (Othello), and machine learning (learning from data streams and object recognition).

Theory of Swarm Intelligence

Social animals as found in fish schools, bird flocks, bee hives, and ant colonies are able to solve highly complex problems in nature. This includes foraging for food, constructing astonishingly complex nests, and evading or defending against predators. Remarkably, these animals in many cases use very simple, decentralized communication mechanisms that do not require a single leader. This makes the animals perform surprisingly well, even in dynamically changing environments. The collective intelligence of such animals is known as swarm intelligence and it has inspired popular and very powerful optimization paradigms, including ant colony optimization (ACO) and particle swarm optimization (PSO).

The reasons behind their success are often elusive. We are just beginning to understand when and why swarm intelligence algorithms perform well, and how to use swarm intelligence most effectively. Understanding the fundamental working principles that determine their efficiency is a major challenge.

This tutorial will give a comprehensive overview of recent theoretical results on swarm intelligence algorithms, with an emphasis on their efficiency (runtime/computational complexity). In particular, the tutorial will show how techniques for the analysis of evolutionary algorithms can be used to analyze swarm intelligence algorithms and how the performance of swarm intelligence algorithms compares to that of evolutionary algorithms.
The results shed light on the working principles of swarm intelligence algorithms, identify the impact of parameters and other design choices on performance, and thus help to use swarm intelligence more effectively.

The tutorial will be divided into a first, larger part on ACO and a second, smaller part on PSO. For ACO we will consider simple variants of the MAX-MIN ant system. Investigations of example functions in pseudo-Boolean optimization demonstrate that the choices of the pheromone update strategy and the evaporation rate have a drastic impact on the running time. We further consider the performance of ACO on illustrative problems from combinatorial optimization: constructing minimum spanning trees, solving shortest path problems with and without noise, and finding short tours for the TSP.

For particle swarm optimization, the tutorial will cover results on PSO for pseudo-Boolean optimization as well as a discussion of theoretical results in continuous spaces.

Automated Offline Design of Algorithms

Most optimization algorithms, including evolutionary algorithms and metaheuristics, and general-purpose solvers for integer or constraint programming, have often many parameters that need to be properly designed and tuned for obtaining the best results on a particular problem. Automatic (offline) algorithm design methods help algorithm users to determine the parameter settings that optimize the performance of the algorithm before the algorithm is actually deployed. Moreover, automatic offline algorithm design methods may potentially lead to a paradigm shift in algorithm design because they enable algorithm designers to explore much larger design spaces than by traditional trial-and-error and experimental design procedures. Thus, algorithm designers can focus on inventing new algorithmic components, combine them in flexible algorithm frameworks, and let final algorithm design decisions be taken by automatic algorithm design techniques for specific application contexts.

This tutorial is structured into two main parts. In the first part, we will give an overview of the algorithm design and tuning problem, review recent methods for automatic algorithm design, and illustrate the potential of these techniques using recent, notable applications from the presenters' and other researchers work. In the second part of the tutorial will focus on a detailed discussion of more complex scenarios, including multi-objective problems, anytime algorithms, heterogeneous problem instances, and the automatic generation of algorithms from algorithm frameworks. The focus of this second part of the tutorial is, hence, on practical but challenging applications of automatic algorithm design. The second part of the tutorial will demonstrate how to tackle algorithm design tasks using our irace software (http://iridia.ulb.ac.be/irace), which implements the iterated racing procedure for automatic algorithm design. We will provide a practical step-by-step guide on using irace for the typical algorithm design scenario.

Evolutionary Computation and Cryptology

Evolutionary Computation (EC) has been used with great success on various real-world problems. One domain abundant with numerous difficult problems is cryptology. Cryptology can be divided into cryptography, that informally speaking considers methods how to ensure secrecy (but also authenticity, privacy, etc.), and cryptanalysis, that deals with methods how to break cryptographic systems.

Although not always in an obvious way, EC can be applied to problems from both domains. This tutorial will first give a brief introduction to cryptology intended for general audience (therefore, omitting proofs and mathematics behind many concepts). Afterwards, we concentrate on several topics from cryptology that are successfully tackled up to now with EC and discuss why those topics are suitable to apply EC.

However, care must be taken since there exists a number of problems that seem to be impossible to solve with EC and one needs to realize the limitations of the heuristics. We will discuss the choice of appropriate EC techniques (GA, GP, CGP, ES, multi-objective optimization, etc) for various problems and elaborate on the importance of that choice. Furthermore, we will discuss the gap between the cryptographic community and EC community and what does that mean for the results. By doing that, we give a special emphasis on the perspective that cryptography presents a source of benchmark problems for the EC community.

To conclude, we will present a number of topics we consider to be a strong research choice that can have a real-world impact. In that part, we give a special attention to cryptographic problems where cryptographic community successfully applied EC, but where those problems remained somewhat out of the focus of the EC community.

This tutorial will also present some live demos of EC in action when dealing with cryptographic problems. We will present several problems, ways of encoding solutions, impact of the algorithms choice and finally, we will run some experiments to show the results and discuss how to assess them from cryptographic perspective.

NEW Evolutionary Computation in Network Management and Security

Cyberspace is becoming more and more challenging to secure due to the increasing vulnerabilities and the complex interactions between cyber systems, physical infrastructures and users/attackers that can operate anywhere on the Internet. Cyber security is the body of technologies, processes and practices designed and developed to protect the systems, networks and data in cyberspace. In this tutorial, we will first introduce the topics of network management and cyber security for general audience. Then, we will discuss how evolutionary computing techniques can help in these tasks to improve best practices.

Network management includes tasks such as network and system discovery, monitoring, performance analysis, fault prediction and diagnosis. Cyber security includes tasks such as network security, application security and information security. In the computing context, the term security implies cyber security. Ensuring cyber security requires coordinated efforts of network management and information systems.

Currently, one of the most problematic elements of network management and security is the quickly and constantly evolving nature of the systems and attacks. To address this challenge, advisory organizations such as NIST promote more proactive and adaptive approaches. This results in a shift toward continuous monitoring and real-time assessments of the current situations on our networks and systems. Such a shift for adaptive and proactive approaches may provide many opportunities for the evolutionary computing community. We will give an overview of different researches done up to now in the network management and security field as well as discuss new and open problems that are suitable for evolutionary computing techniques going forward in this field. Finally, we will present numerous examples, applications and live demos to illustrate the concepts in this tutorial.

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;
• encodings of controllers and morphologies;
• evolution for physical robots and the reality gap;
• embodied evolution and collective robotics systems;
• open questions and future challenges.

Intelligent Systems for Smart Cities

The concept of Smart Cities can be understood as a holistic approach to improve the level of development and management of the city in a broad range of services by using information and communication technologies.

It is common to recognize six axes of work in them: i) Smart Economy, ii) Smart People, iii) Smart Governance, iv) Smart Mobility, v) Smart Environment, and vi) Smart Living. In this tutorial we first focus on a capital issue: smart mobility. European citizens and economic actors need a transport system which provides them with seamless, high-quality door-to-door mobility. At the same time, the adverse effects of transport on the climate, the environment and human health need to be reduced. We will show many new systems based in the use of bio-inspired techniques to ease the road traffic flow in the city, as well as allowing a customized smooth experience for travellers (private and public transport).

This tutorial will then discuss on potential applications of intelligent systems for energy (like adaptive lighting in streets), environmental applications (like mobile sensors for air pollution), smart building (intelligent design), and several other applications linked to smart living, tourism, and smart municipal governance.

NEW Multiagent Systems and Agent-based Modeling and Simulation

Based on concepts that are well grounded on artificial and computational intelligence, and with the recent advances in information and communication technologies, a new paradigm that considers social interactions among intelligent actors was introduced: the area of multiagent systems (MAS) and agent-based modeling and simulation (ABMS). This area studies neither just physical systems nor agents in isolation, but the agent as part of a social space. This is important in our modern world where embedded processing is ubiquitous and thus part of our social fabric.

The term agent has been used within the GECCO community in various contexts (e.g., swarm intelligence), but it seems that both the GECCO and the AAMAS (the premier conference on MAS) communities do not really take advantage of the potential of working together. Few researchers do have publications in both communities, despite the fact that EcoMAS is a traditional workshop held together with GECCO.

The goal of this tutorial is twofold: (a) about one-third of the time will be devoted to cover basic material about MAS (because I deem the material on single agent's architecture to be of less interest to this community) and ABMS (since this simulation paradigm is highly used by the computational intelligence community), and hence provide the audience a sense of the basic principles; and (b) about two-thirds of the time will cover the most recent advances in MAS, including the highly relevant topic of multiagent learning, one of the obvious interfaces between these two communities, as well evolutionary game theory as proxy for MAS.

The scope will include: introduction to autonomous agents and multiagent systems; agents coordination; agent-based modeling and simulation; distributed constraint optimization (DCOP); stochastic planning with Markov decision processes (MDP); multiagent learning; game theory and stochastic games as multiagent interactions; consensus reaching via social choice. If time and infrastructure permits, exercises using Netlogo can be covered as well.