Summary of Tutorial- Evolutionary Computation- A Unified Approach (by Kenneth De Jong)

This tutorial was conducted by Kenneth De Jong on 8th July, 2020 during GECCO, 2020.

Evolutionary computation (EC) gets its inspiration from biological evolution. A initial population of candidate solutions is generated and evolved subjected to mutation and natural selection with the hope to increase the fitness. The specific fitness function determines the value of fitness. Thus this approach is based on global optimisation. This is in contrast with the Neural Networks, trained with Stochastic Gradient Descent (SGD), which is prone to getting stuck in local minima.

Evolutionary computation has its historical roots starting from 1950’s. Lawrence J. Fogel proposed the idea of Evolutionary Programming (EP) during 1960’s, while John H. Holland gave the term Genetic Algorithms (GAs) during 1960’s. Holland’s groundbreaking book on Genetic Algorithms titled “Adaptation in Natural and Artificial Systems” was published in 1975. During 2000’s a variety of evolutionary algorithms came in use. The common feature across various algorithms is the Darwinian-like evolutionary processes to solve difficult computational problems.

The core elements of an Evolutionary Algorithm are the following:

A population of “individuals”

A notion of “fitness”

A birth/death cycle biased by fitness

A notion of “inheritance”

However, there are various design decisions which affect the performance of the model. For example, a design choice to make is what should be the population size. It depends on the fitness landscape, which is not known.Related question is what should be the offspring population size in the population. Do the offsprings replace the entire population thus there is no overlapping generation? Thus resulting in non-overlapping generation. Or, there is overlapping generation, offsprings and their parent make the entire population. The selection pressure is high in overlapping generation as compared to non-overlapping one. The various selection strategies, such as Truncation, Tournament and Ranking, Fitness proportional and Uniform selection have different computational implications. The selection pressure decreases from Truncation towards Uniform selection in that order.

Reproduction strategies influence preservation of useful features and introduction of variety and novelty in the population. The strategy can be based on single parent cloning and mutation or multi-parents recombination and mutation. If fitness covariance between parents and offsprings is positive, then the reproduction strategy is beneficial.

A crucial design choice is to appropriately balance between exploration and exploitation. Reproduction expands the scope of the search thus leading to more exploration while selection pressure reduces the scope of the search by limiting the search to the promising areas.

The performance of the algorithm is affected by representation techniques. The genotypic representation requires minimum domain knowledge and are portable. While, the phenotypic representation leverages domain knowledge, uses problem specific encodings, but lacks portability.

Thus, evolutionary computation is a parallel and adaptive search process with useful global search heuristics. It can be very general or problem specific. There is a strong sense of fitness “optimisation”.

An interesting application area is related to testing autonomous vehicle controller.The robustness demanded from such systems requires testing under varying conditions. This scenario search space can be generated by evolutionary algorithms where the fitness function is related to the difficulty the scenario creates for the controller.