Tutorials

Complex Networks

Complex networks are everywhere around us. They play a central role in many ways, from internet-mediated social networks, to transportation, biological processes, and the transmission of information among others. This tutorial will provide an overview and synthesis of state-of-the-art knowledge on complex networks, thus allowing researchers to better understand their structure, function, and dynamics.

The following subjects will be treated.

• What are complex networks? Examples from several fields and fundamental structural features.
• Characterization of complex networks: network statistics.
• Models of complex networks: Erdos-Renyi random graphs, Watts-Strogatz small worlds, preferential attachment and Barabasi-Albert growing networks.
• Networks embedded in physical space, random geometric graphs.
• Network evolution: Dynamical complex networks.
• Dynamics on networks: epidemic spreading.
• Applications of complex network theory in population-based metaheuristics and to the fitness landscapes of hard problems.

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 se 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 nature in the sense that multiple, conflicting criteria need to be optimized simultaneously. Due to the conflict between objectives, usually, no single optimal solution exists. Instead, the optimum corresponds to a set of so-called Pareto-optimal solutions for which no other solution has better function values in all objectives.

Evolutionary Multiobjective Optimization (EMO) algorithms are widely used in practice for solving multiobjective optimization problems due to several reasons. As randomized blackbox algorithms, EMO approaches allow to tackle problems with nonlinear, nondifferentiable, or noisy objective functions. As set-based algorithms, they allow to compute or approximate the full set of Pareto-optimal solutions in one algorithm run---opposed to classical solution-based techniques from the multicriteria decision making (MCDM) field. Using EMO approaches in practice has two other advantages: they allow to learn about a problem formulation, for example, by automatically revealing common design principles among (Pareto-optimal) solutions (innovization) and it has been shown that certain single-objective problems become easier to solve with randomized search heuristics if the problem is reformulated as a multiobjective one (multiobjectivization).

This tutorial aims at giving a broad introduction to the EMO field and at presenting some of its recent research results in more detail. More specifically, I am 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, I will present some of the most important research results in areas such as indicator-based EMO, preference articulation, and performance assessment.

Though classified as introductory, this tutorial is intended for both novices and regular users of EMO. Those without any knowledge will learn about the foundations of multiobjective optimization and the basic working principles of state-of-the-art EMO algorithms. Open questions, presented throughout the tutorial, can serve for all participants as a starting point for future research and/or discussions during the conference.

Evolving Neural Networks

Neuroevolution, i.e. evolution of artificial neural networks, has recently emerged as a powerful technique for solving challenging reinforcement learning problems. Compared to traditional (e.g. value-function based) methods, neuroevolution is especially strong in domains where the state of the world is not fully known: The state can be disambiguated through recurrency, and novel situations handled through pattern matching. In this tutorial, I will review (1) neuroevolution methods that evolve fixed-topology networks, network topologies, and network construction processes, (2) ways of combining traditional neural network learning algorithms with evolutionary methods, and (3) applications of neuroevolution to control, robotics, artificial life, and games.

Demos: The tutorial includes 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, and a Turing Test for game bots.

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, including live demos, will illustrate and reinforce the issues of practical application. This technique has continually 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: 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. 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 a unique and often overlooked class of algorithms with flexible features that set them apart from other strategies, particularly with respect to modeling complex systems. Learning classifier systems (LCS), or more specifically Michigan-style LCSs, being the most prevalent and archetypical of the RBML algorithms, will be the focus of this tutorial. These algorithms 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.

This proposed tutorial will improve and expand upon the one I presented last year in collaboration with Dr. Will Browne. I will focus on presenting an accessible, gentle introduction to how RBML algorithms work, and to what types of problems they have been or could be applied to, discussing their advantages and drawbacks with respect to other machine learning approaches. Furthermore, I will incorporate a guided, hands-on demonstration of how to get an LCS algorithm up and running, using the LCS algorithm I developed called ‘ExSTraCS 2.0’ published earlier this year. ExSTraCS provides not only a convenient example implementation, as it is clearly annotated, coded in python, and designed to be as user friendly as possible, but it is a very powerful tool for real-world applications. Specifically in the recent publication of ExSTraCS 2.0, we demonstrated that in addition to having been applied successfully to a study in genetic epidemiology, this algorithm was the first ever to report solving the extremely complex 135-bit multiplexer computer science benchmark problem directly. 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 also 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 of which I am a co-author with Dr. Will Browne. Specifically, we had previously coded and posted some easy code for an ‘educational’-learning classifier system (eLCS) also freely available online. We will pair code and analysis demonstrations directly with eLCS and ExSTrACS, as two clear, and available examples of Learning Classifier Systems.

NEW 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, ill-conditioning and ruggedness of the function. In this context, randomized methods like evolution strategies have their raison d'etre.

This tutorial will start by discussing typical difficulties of optimization problems in continuous domain. It will then introduce basics of randomized method in continuous domain with a specific focus on evolution strategies. In particular sampling of solutions and adaptation mechanism 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.

DEMO: In this tutorial, we will run some randomized algorithms in python and illustrate how they behave. We will demonstrate the importance of invariance properties by comparing the results of different algorithms on functions with/without transformations in objective and search spaces.

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

NEW 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?

NEW Theory for Non-Theoreticians

This tutorial addresses GECCO attendees who do not or just seldomly 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, as well as
- the limits of what theory can offer to more applied approaches to EC.

NEW Biased Random-Key Genetic Algorithms

A biased random-key genetic algorithm (BRKGA) is a general search procedure for finding optimal or near-optimal solutions to hard combinatorial optimization problems. It is derived from the random-key genetic algorithm of Bean (1994), differing in the way solutions are combined to produce offspring. BRKGAs have three key features that specialize genetic algorithms:

1) A fixed chromosome encoding using a vector of N random keys or alleles over the real interval [0, 1), where the value of N depends on the instance of the optimization problem;

2) A well-defined evolutionary process adopting parameterized uniform crossover to generate offspring and thus evolve the population;

3) The introduction of new chromosomes called mutants in place of the mutation operator usually found in evolutionary algorithms.

Such features simplify and standardize the procedure with a set of self-contained tasks from which only one is problem-dependent: that of decoding a chromosome, i.e. using, the keys to construct asolution to the underlying optimization problem, from which the objective function value or fitness can be computed. BRKGAs have the additional characteristic that, under a weak assumption, crossover always produces feasible offspring and, therefore, a repair or healing procedure to recover feasibility is not required in a BRKGA.

In this tutorial we review the basic components of a BRKGA and introduce an Application Programming Interface (API) for quick implementations of BRKGA heuristics. We then apply the framework to a number of hard combinatorial optimization problems, including 2-D and 3-D packing problems, network design problems, routing problems, scheduling problems, and data mining. We conclude with a brief review of other domains where BRKGA heuristics have been applied.

Blind No More: Deterministic Mutation and Recombination Operators for Evolutionary Algorithms and Local Search

Most local search algorithms have relied on enumerating a neighborhood of solutions in order to locate improving moves. Local search then moves to a local optima. After reaching a local optima, some kind of exploration strategy might be used to escape the local optima: the result might be some form of Tabu search or other Interated Local Search strategy. Similar, evolutionary algorithms have also long relied on random mutation and random recombination operators to generate new candidate solutions.

However, for certain problem domains it is possible to exactly compute the best improving move and the best possible recombination move. This can be illustrated by looking at pseudo-Boolean optimization problems where the representation has the form of a bit string and the objective function returns a real value. We will assume that the pseudo-Boolean functions are k-bounded. This means that the objective function is a linear combination of subfunctions, where each subfunctions takes at most k bits as input.

MAX-kSAT and NK-Landscapes are k-bounded. But all compressible pseudo-Boolean optimization problems can be reduced to a quadratic (k=2) pseudo-Boolean optimization problem. We have been able to prove it is possible to exactly identify all improving moves in O(n) time when no variable appears in more than q subfunction. Furthermore, this result can be generalized for Hamming Balls of radius r: we can identify all improving moves for within a Hamming radius r in O(n) time. We current have results for n=10,000 and r=7 for NK-landscapes, where the Hamming Ball has n to power r = 1 billion neighbors. In some cases we can prove the results are generating a global optima. This means that we no longer need to enumerate Hamming distance 1 neighborhoods, or to use random mutations to locate improving moves.

We can also prove that there exists deterministic forms of recombination that are also guaranteed to return the best possible offspring. These operator rely on localized problem decomposition. Our methods identify p partitions of interaction. Variables within a partition must be inherited together. However, bits in different partitions can be linearly recombined. Given p partitions, recombination can be done in O(n) time such that crossover returns the best solutions out of 2 to power p offspring. If p = 30, then crossover is guaranteed to return the best out of 1 billion possible offspring. This type of operator is not restricted to pseudo-Boolean optimization. We have also developed “Partition Crossover” operators for the Traveling Salesman Problem.

NEW 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. Recent variants for large-scale optimization will be also presented, where we will see how the design principles are applied and the parameters are tuned.

We will demonstrate the ease of using different adaptation mechanisms and different parameter settings within the CMA-ES module (in Python). We will run the CMA-ES with different settings and visualize their behavior on some benchmark problems and see how different algorithmic components and different parameter settings have impact on the performance. The CMA-ES is impremented in different programming languages such as Matlab/Octave, Python, C++, Java, etc. They can be found in https://www.lri.fr/~hansen/cmaes_inmatlab.html

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

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?

Semantic Genetic Programming

Semantic genetic programming is a recent, 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 a 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 number of realworld applications of this framework will be also presented. Other promising emerging approaches to semantics in GP will be reviewed. In particular, the recent developments in the behavioral programming, which aims at characterizing the entire program behavior (and not only program outputs) 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.

NEW 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 briefly cover parallelization and surrogate models to reduce the runtime, but then focus in particular on the handling of noise.

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 control problems (keepaway soccer, tractor control) evolution 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.

NEW 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. This tutorial will provide a comprehensive overview of methods used in multiobjective optimization for visualizing either individual approximation sets or the probabilistic distribution of multiple approximation sets through the empirical attainment function (EAF).

This tutorial will be among the first comprehensive presentations of visualization methods for multiobjective optimization and will be valuable to students, researchers, algorithm designers and end users dealing with multiobjective optimization problems. Tutorial attendees will become aware of the many ways of visualizing approximation sets and the EAF, and learn about the advantages and limitations of each method.

Contents of the tutorial:

- Requirements for visualization methods
- Benchmark approximation sets that can be used for comparing visualization methods in a similar way as performance metrics and benchmark test problems are used for comparing optimization algorithms
- Two groups of methods used for visualizing individual approximation sets (for each method we will demonstrate its outcome on the benchmark approximation sets and discuss its advantages and limitations):
-- General methods (not designed for multiobjective optimization): scatter plot matrix, bubble chart, radial coordinate visualization, parallel coordinates, heatmaps, Sammon mapping, neuroscale, self-organizing maps, principal component analysis and isomap
-- Specific methods (able to handle the unique features of approximation sets): distance and distribution charts, interactive decision maps, hyper-space diagonal counting, two-stage mapping, level diagrams, hyper-radial visualization, Pareto shells, seriated heatmaps, multidimensional scaling and prosections
- Visualization of EAF values and differences

We will demonstrate how each of the introduced methods visualizes the benchmark approximation sets. In addition, for some of the methods (such as parallel coordinates, prosections and direct volume rendering) animations will be used to show their additional capabilities.

Automatic (Offline) Configuration 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 configured (i.e., tuned) for obtaining the best results on a particular problem. Automatic (offline) algorithm configuration methods help algorithm users to determine the parameter settings that optimize the performance of the algorithm before the algorithm is actually deployed. Moreover, automatic algorithm configuration methods may potentially lead to a paradigm shift in algorithm design and configuration 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 configuration techniques for specific application contexts.

This tutorial will be divided in two parts. The first part will give an overview of the algorithm configuration problem, review recent methods for automatic algorithm configuration, and illustrate the potential of these techniques using recent, notable applications from the presenters' and other researchers work. 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 configuration. The second part of the tutorial will demonstrate how to tackle these configuration tasks using our
irace software (http://iridia.ulb.ac.be/irace), which implements the iterated racing procedure for automatic algorithm configuration. We will provide a practical step-by-step guide on using irace for the typical algorithm configuration scenario.

NEW Cloudy distributed evolutionary computation

Cloud computing has emerged as one of the dominant frameworks for performing large-scale computation. However, having a grid, cluster or money to pay for vast amounts of cloud resources is great, but the need to do science and the high performance attached to it is not always in sync with what is provided by your friendly science funding agency. At the same time, there are nowadays many resources connected to the Internet which you can tap when free or when they are offered to you voluntarily.

In this tutorial we will, first, make a general review of volunteer/citizen grid and cloud computing resources. Then we will make a brief introduction to the JavaScript language and how it can be leveraged for programming the cloud, and which is the language used in all browsers, and explain how to create, very simply, a client-server application that uses free or low-cost cloud resources to create a fully distributed evolutionary computing system.

We will also explain which evolutionary computing paradigms are better suited to this kind of environment, introducing pool-based evolutionary algorithms and a very simple implementation; we will also show what is the state of the art in that area and how researchers, so far, have dealt with this problem and what kind of application areas we could we use.

NEW 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 cryptography 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 evaluate 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 will 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 out of the focus of 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 for Feature Selection and Feature Construction

In data mining and machine learning, many real-world problems such as bio-data classification and biomarker detection, image analysis, text mining often involve a large number of features/attributes. However, not all the features are essential since many of them are redundant or even irrelevant, and the useful features are typically not equally important. Using all the features for classification or other data mining tasks typically does not produce good results due to the big dimensionality and the large search space. This problem can be solved by feature selection to select a small subset of original (relevant) features or feature construction to create a smaller set of high-level features using the original low-level features.

Feature selection and construction are very challenging tasks due to the large search space and feature interaction problems. Exhaustive search for the best feature subset of a given dataset is practically impossible in most situations. A variety of heuristic search techniques have been applied to feature selection and construction, but most of the existing methods still suffer from stagnation in local optima and/or high computational cost. Due to the global search potential and heuristic guidelines, evolutionary computation techniques such as genetic algorithms, genetic programming, particle swarm optimisation, ant colony optimisation, differential evolution and evolutionary multi-objective optimisation have been recently used for feature selection and construction for dimensionality reduction, and achieved great success. Many of these methods only select/construct a small number of important features, produce higher accuracy, and generated small models that are easy to understand/interpret and efficient to run on unseen data. Evolutionary computation techniques have now become an important means for handle big dimensionality and feature selection and construction.

The tutorial will introduce the general framework within which evolutionary feature selection and construction 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 bio-data classification and biomarker detection, image analysis and object recognition and pattern classification, symbolic regression, network security and intrusion detection, and text mining. EC techniques to be covered will include genetic algorithms, genetic programming, particle swarm optimisation, differential evolution, ant colony optimisation, artificial bee colony optimisation, and evolutionary multi-objective optimisation. We will show how such evolutionary computation techniques can be effectively applied to feature selection/construction and dimensionality reduction and provide promising results.

Evolutionary Computation in Games

In recent years, the field of Computational Intelligence and Games (CIG) has enjoyed rapid progress and a sharp rise in popularity. In this field, algorithms from across the computational intelligence spectrum are tested on benchmarks based on e.g. board games and video games, and new CI-based solutions are developed for problems in game development and game design. This tutorial will give an overview of key research challenges and methods of choice in CIG. The tutorial is divided in two parts, where the second part builds on methods and results introduced in the first part. Level: introductory. No particular background is assumed beyond basic knowledge of computational intelligence methods and an interest in games.

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.

Medical Applications of Evolutionary Computation

The application of genetic and evolutionary computation to problems in medicine has increased rapidly over the past five years, but there are specific issues and challenges that distinguish it from other real-world applications. Obtaining reliable and coherent patient data, establishing the clinical need and demonstrating value in the results obtained are all aspects that require careful and detailed consideration.

My research uses genetic programming (a representation of Cartesian Genetic Programming) in the diagnosis and monitoring of Parkinson's disease, Alzheimer's disease and other neurodegenerative conditions. It is also being used in the early detection of breast cancer through automated assessment of mammograms. I currently have multiple clinical studies in progress in the UK (Leeds General Infirmary), USA (UCSF), UAE (Dubai Rashid Hospital), Australia (Monash Medical Center) and Singapore (National Neuroscience Institute). The technology is protected through 3 patent applications and a spinout company marketing 4 medical devices.

The tutorial considers the following topics:

1. Introduction to medical applications of genetic and evolutional computation and how these differ from other real-world applications
2. Overview of past work in the from a medical and evolutional computation point of view
3. Three case examples of medical applications:
   i. diagnosis and monitoring of Parkinson's disease
   ii. detection of beast cancer from mammograms
   iii. cancer screening using Raman spectroscopy
4. Practical advice on how to get started working on medical applications, including existing medical databases and conducting new medical studies, commercialization and protecting intellectual property.
5. Summary, further reading and links