Evolutionary Algorithm — Selections Explained
Understand what goes on, with visualization and code
The Travelling Salesman Problem (TSP) is a well-known np-hard problem, that has obvious practical applications in real life. For example, this is useful if one is planning a trip around Europe and estimates the point-to-point travel time between sites.
With just a mere 30 cities, there would be over 10³⁰ possible permutations. To solve TSP with 30 cities by brute force is not feasible (The number of grains of sand on Earth is ‘only’ 10¹⁹).
By the end of this article, solving such problems with Evolutionary Algorithm (EA) will be easy for you. You will be able to get the following result yourself.
More importantly, you will understand what exactly goes on behind the scenes, and how each component (specifically the various types of mutations) contribute to the solution.
1. Value Proposition
Many guides incorrectly use the words Genetic Algorithm (GA) and Evolutionary Algorithm (EA) interchangeably.
GA, in its canonical form, involves the following elements [1]:
1. Representation — bit strings
2a. Parent selection — proportional to fitness
2b. Recombination — one-point crossover
3. Mutation — bit flip
4. Survival selection — next generation
GA is a subset of EA.
In this guide, we cover aspects of EA that are not discussed in GA. In particular, we will focus on aspects pertaining to permutation representation, explaining with intuitive visualizations and code.
2. Definitions
Before moving further, we need to be clear on the use of terminologies [2].
Phenotypes
The solutions within the original problem context. These are to be interpreted ‘as is’ without any decoding; and are agnostic to how the solutions are even derived.
Genotypes
The encodings that represent the phenotype. This may be a string of bits, integers, or even floats. A deterministic mapping converts each genotype into the corresponding phenotype.
Fitness
A measure from some function that serves as the basis for selection. It allows us to compare between two genotypes (and hence two solutions) and define which is ‘better’.
Population
Collection of individual genotypes, typically of a constant size. Through iterations, members of the population change through the process of recombination, mutation, and survivor selection.
Recombination
A binary variation, where two offspring are created from two parent genotypes, blending their attributes in the process.
Mutation
A unary variation performed on a single genotype. The change is random, and it serves to maintain diversity in the population.
Survivor Selection
The process of determining which individuals (as represented by their genotype) will remain in the population for the next generation. The objective is to retain the most promising selections, with diversity maintained to foster potential future improvements.
3. Outline
EA follows the following framework.
3.1 — Initialization; Representation
Before even talking about any sort of math or code, we need to frame the problem and formulate the genotype such that it maps to the solution space appropriately.
EA goes beyond binary and permutation representations, but we will not delve further here.
The population will then be initialized with random copies of the appropriate genotype.
3.1.1 (Why not) Binary Representation
Using bits to represent the genotype is a natural choice, as this reflects reality. Human, as well as other organisms, has DNA as its genetic material. We can think of a DNA sequence as a string of 1’s and 0’s, in place of ‘A-T’ and ‘C-G’.
Binary representation works beautifully when the inherent problem involves binary decisions — the perfect example is a knapsack problem, where each bit indicates whether or not that corresponding item is selected.
Even though everything can be represented in bits, it is not appropriate to use bits for representing solutions to non-binary problems.
Get James Koh, PhD’s stories in your inbox
Join Medium for free to get updates from this writer.
Mutation is supposed to change the solution with equal probabilities, and ensure that the ensuing solution is valid. Changing a number 7 (0111) to 8 (1000) requires four bit flips, while changing it to 3 (0011) or 5 (0101) or 6 (0110) requires only one bit flip — the odds are different. Using Gray coding [3] is insufficient to resolve this discrepancy in Hamming distance, and insisting on such representation will lead to the evolution process being skewed.
Furthermore, adjustments may be required after recombination and/or mutation, if a binary representation is used to represent a permutation. This is because each index much occur exactly once, and the resulting genotype might correspond to an invalid phenotype.
3.1.2 Permutation Representation
This brings us to using permutations as the genotype. Apart from TSP, this is also applicable to problems requiring us to select a sequence. It could be a sequence of place to visit, a sequence of tasks to complete, assigning matches, or the placement of inventory in a warehouse.
Having the genotype as a sequence of indices is ideal here, because we can be assured of a valid phenotype after variations. For example, if there are 12 cities to choose from, the genotype can be [9,2,6,1,7,8,11,0,4,3,10,5]. We will see that there are multiple ways to perform variations while ensuring that each integer appears exactly once.
We can begin with the following outline to generate a population. (For conciseness, I am excluding the importing of libraries as those are trivial.)
class Evolutionary:
def __init__(self, task):
self.task = task
def generate_genome(self, length):
genome = np.arange(length)
np.random.shuffle(genome)
return genome
def generate_population(self, size, genome_length):
population = [self.generate_genome(genome_length) for _ in range(size)]
return population3.2 — Parent selection
In EA, the process of parent selection, variation, and survival selection happens iteratively to ensure that the population as a whole improves across generations.
If any of the three steps is not implemented correctly, the whole algorithm can fall apart.
Parent selection, as one of the three pillars, is important because offspring are variants of their parents. Recall that each individual is actually a genotype, which is a representation of a candidate solution.
When we combine two parents, and apply recombination (Section 3.3.1) to obtain new genotypes, what really happens is that aspects of two solutions are blended together, resulting in new candidate solutions. While it is not a guarantee that parents of higher fitness lead to better offspring, the odds will be in our favor.
Nonetheless, we need to strike a balance between exploration and exploitation, just like in reinforcement learning. It is a bad idea to select the two fittest parents 100% of the time, because the lack of diversity would hinder us from finding the optimal solution [4].
3.2.1 Roulette wheel for Parent selection
The hypothetical roulette wheel has its area directly proportional to the fitness of each individual. Each area depicts the probability of selecting each respective individual as a parent.
A caveat is that the fitness values should be positive. Try the following yourself, and it speaks louder than a thousand words.
population=['A', 'B', 'C', 'D', 'E']
weights = [-.1, -.2, -.3, -.3, 1]
for _ in range(100):
x = random.choices(
population=population, weights=weights, k=2
)
print(x)You will see that all negative weights have zero chance of being selected, and that a highly negative weight would be no different from a slightly negative weight. That’s not what we want in EA, because a somewhat poor solution should be significantly preferred over an extremely bad one.
In TPS, one common way of representing the fitness is by negating the distance between cities (You will see the code in Section 4.1). In this case, we need to normalize the fitness such that they are positive. This could be done by subtracting from the minimum (ie. most negative) fitness, add then adding some small epsilon to that even the worse solution has a non-zero chance of being selected.
This choice of baseline is actually more important than it looks, and does require some discretion on the part of the data scientist. Consider the following:
How fitness is defined is of relevance. In the case above, it certainly makes a difference whether a fitness of 100 was already ‘guaranteed’ and built-in, or whether individual A earned it and was effectively a worthy contender of the others.
3.2.2 Tournament for Parent selection
Another popular approach is that of tournament selection. This approach is used to ensure that the fittest parents do not end up dominating most of the time.
Here, what happens is that a small subset of the population is randomly selected, and the fittest individual among this group gets chosen. In the example below (where the circle size represents each individual’s respective fitness), the purple individual will be selected as the parent for this particular run.
The helps in maintaining diversity, which is an important aspect as mentioned at the beginning of Section 3.2. Had roulette wheel selection been used, the chances of this purple individual being selected would be pretty low.
In code, tournament selection or roulette wheel for parent selection can be implemented as follows:
class Evolutionary:
def selection(self, population, fitness_func, method='tournament'):
if method == 'tournament':
k = min(5, int(0.02*len(population)))
sub_population1 = random.choices(
population=population, k=k
)
sub_population2 = random.choices(
population=population, k=k
)
return (
sorted(sub_population1, key=fitness_func, reverse=True)[0],
sorted(sub_population2, key=fitness_func, reverse=True)[0]
)
else: # roulette wheel
min_fitness = min([fitness_func(gene) for gene in population])
selected = random.choices(
population=population,
weights=[fitness_func(gene)+eps-min_fitness for gene in population],
k=2
)
return tuple(selected)I’ve set the size of the sub-population to be 5, or 2% of the population, whichever is lower. You are, of course, free to change this number. The smaller these hyperparameters, the more exploration (and less exploitation) is performed.
To Be Continued
In this article, you’ve learnt about the different components that make up EA, with the rationale for different approaches for parent selection being explored.
That’s quite many new things to absorb in a single article. It’s already a 8 minutes read-time, and there’s plenty more important concepts in EA that needs to be discussed. To keep the learning palatable, that’s it for this article.
In the next article, Evolutionary Algorithm — Mutations Explained, you will learn about recombination, mutation and survival selection. Recombination in permutation-based genotype is not as trivial as crossovers, but explanations will be supported with intuition, visualization and code such that it can be clearly understood even without prior experience. We will then put all the code together, and solve the TSP.
References
[1] D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning (1989), Addison-Wesley
[2] A. E. Eiben and J. E. Smith, Introduction to evolutionary computing (2015), Springer-Verlag Berlin Heidelberg
[3] C. Faloutsos, Multiattribute hashing using gray codes (1986), In Proceedings of the 1986 ACM SIGMOD international conference on Management of data
[4] F. Vafaee, G. Turán, P. C. Nelson, and T. Y. Berger-Wolf, Balancing the exploration and exploitation in an adaptive diversity guided genetic algorithm (2014), In 2014 IEEE Congress on Evolutionary Computation
