Evolutionary Algorithms, Genetic Programming, and Learning
Evolutionary algorithms are a family of search algorithms inspired by the process of (Darwinian) evolution in Nature. Common to all the different family members is the notion of solving problems by evolving an initially random population of candidate solutions, through the application of operators inspired by natural genetics and natural selection, such that in time fitter (that is, better) solutions to the problem emerge.
The field, whose origins can be traced back to the 1950s and 1960s, has come into its own over the past two decades, proving successful in solving numerous problems from highly diverse domains including (to mention but a few): optimization, automatic programming, electronic-circuit design, telecommunications, networks, finance, economics, image analysis, signal processing, music, and art.
Interestingly, researchers — including myself — have found that evolutionary algorithms can be combined with machine learning and deep learning in beneficial ways. More about that in a bit.
Here’s what a basic evolutionary algorithm looks like:
- produce an initial population of individuals, these latter being candidate solutions to the problem at hand
- evaluate the fitness of each individual in accordance with the problem whose solution is sought
- while termination condition not met do - select fitter individuals for reproduction - recombine (crossover) individuals - mutate individuals - evaluate fitness of modified individuals
Let’s take stock of the main ingredients of an evolutionary algorithm:
Genome (chromosome). Evolutionary algorithms are inherently population-based. An individual in the population is known as a genome, or chromosome. It can take on many forms, including bitstrings, real-valued vectors, character-based encodings, computer programs, and more. Designing a representation that suits the problem at hand is critical to the success of an evolutionary algorithm.
Fitness, or fitness function. A measure of the quality of a candidate solution in the population. Defining this function well is also critical to the success of an evolutionary algorithm.
Generation. A single iteration of the while loop above.
Selection. The operator by which an evolutionary algorithm selects (usually probabilistically) higher-fitness individuals to contribute genetic (well, “genetic”) material to the next generation.
Crossover. One of the two main genetic operators, wherein two (or more) candidate solutions (parents) are combined in some pre-defined manner to form offspring.
Mutation. The second main genetic operator, wherein one candidate solution is randomly altered.
Time for a simple example. Let’s consider a population of 4 individuals, which are bitstrings (genomes) of length 10. The fitness value equals the number of 1s in the bitstring. In actual applications, population size and genome length are larger, of course.
Fitness computation in this case is extremely simple: just count the number of 1s in an individual. For real-world problems we often have to perform some heavy-duty computing to get the fitness values.
The initial random population might look like this (fitness values are in parentheses): 0000011011 (4), 1110111101 (8), 0010000010 (2), 0011010000 (3).
Selection might then choose as parent pairs: 1110111101 (8) with 0011010000 (3), and 0000011011 (4) with 1110111101 (8). Note how some individuals get selected more than others, while some maybe not at all — selection is probabilistic, and it depends on fitness. The higher the fitness, the higher the probability of getting selected as a parent.
The crossover operator swaps random chunks amongst a pair of parents, followed by the mutation operator, which randomly flips a small number of bits.
Once we’ve done selection-crossover-mutation, we’ve got ourselves a new generation. It might look like this in our case: 1111010000 (5), 0010101101 (5), 0000011011 (4), 1110111111 (9). Yup, a bit of this parent, a bit of that parent, a bit of alterations, and voilà — an improved solution, with fitness 9 (whereas before the best was 8).
What now? Just keep cycling through the generations — selection-crossover-mutation-fitness — until you’ve got a good-enough solution. Maybe even the optimal one.
Genetic Programming. Now let’s makes things more interesting. Why evolve simple bitstrings? One of the main sub-domains within evolutionary algorithms is called genetic programming, which focuses on the use of more-sophisticated representations. Traditionally, these have been computational trees, but over the years many other representations have been proposed.
A computational tree looks like this:
I evolved this tree through genetic programming, and it actually computes (recursively) the equivalent mathematical expression: x⁴ + x³ + x² + x + 1. Sometimes evolution churns out more-complicated trees, such as:
Machine Learning and Deep Learning. One of the main advantages of evolutionary algorithms, as I and others have discovered in past years, is how well they “play” with machine learning and deep learning — if used judiciously.
For example, in a machine learning setting I designed a number of evolutionary-based classifiers, which were competitive with XGBoost, LightGBM, and a deep neural network. Here’s the full paper.
In a deep learning setting, we used a so-called coevolutionary algorithm, wherein multiple populations evolve in tandem, to evolve activation functions for deep networks. Rather than use standard ReLU, sigmoid, or such, we plugged evolved activation functions into deep networks and showed that their performance increased. Here’s the full paper.
Within the field of adversarial deep learning, researchers investigate the vulnerability of deep models to attacks, both trying to improve model defenses and to design novel attacks. Small changes in input images, undetectable to us, can cause networks to err.
In one work we used evolution to generate physically plausible adversarial patches, which are performant and appear realistic — without the use of gradients. We made use of GAN (generative adversarial network) generators. Given a pretrained generator, we sought an input latent vector, corresponding to a generated image, that leads the object detector to err. We leveraged the latent space’s (relatively) small dimension, approximating the gradients using an Evolution Strategy algorithm, repeatedly updating the input latent vector by querying the target object detector until an appropriate adversarial patch was discovered.
Below witness my talented grad student, Raz Lapid, standing beside his better half, showing how the evolved patch (printed, that is, physical) hides him from the deep learning model (no bounding box). The full paper is here.
You’re welcome to peruse my website for more details and full papers.
How hard is it to get started with evolutionary algorithms? Well, I’d begin with one of the many excellent packages out there. Unabashedly, I’d like to recommend the project I’ve initiated — along with my wonderful collaborators and grad students — EC-KitY:
We have multiple goals in mind for this project, and thus EC-KitY is:
- A comprehensive toolkit for running evolutionary algorithms;
- Written in Python;
- Can work with or without scikit-learn, that is, it supports both sklearn and non-sklearn modes;
- Designed with modern software engineering in mind;
- Designed to support all popular evolutionary algorithm paradigms.
You can run an evolutionary algorithm with just 3 lines of code:
algo = SimpleEvolution(Subpopulation(SymbolicRegressionEvaluator()))
algo.evolve()
print(f'algo.execute(x=2,y=3,z=4): {algo.execute(x=2, y=3, z=4)}')And EC-KitY is also compatible with scikit-learn, as you can see in this code snippet:
X, y = make_regression(n_samples=100, n_features=3)
terminal_set = create_terminal_set(X)
algo = SimpleEvolution(Subpopulation(creators=FullCreator(terminal_set=terminal_set),
evaluator=RegressionEvaluator()))
regressor = SKRegressor(algo)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)
regressor.fit(X_train, y_train)
print('MAE on test set:', mean_absolute_error(y_test, regressor.predict(X_test)))Let me end with a famous quote by Charles Darwin — the closing lines of Origin of Species:
There is grandeur in this view of life, with its several powers, having been originally breathed into a few forms or into one; and that, whilst this planet has gone cycling on according to the fixed law of gravity, from so simple a beginning endless forms most beautiful and most wonderful have been, and are being, evolved.