Evolutionary Algorithm — Mutations Explained
Illustrations with code implementation, applied to TSP as an example
This is a continuation of Evolutionary Algorithm — Selections Explained.
If you are reading to gain a high-level understanding of recombination and mutations in premutation-based representation, this article will be self-sufficient as a standalone.
However, to understand the full details of every step of the process, it will be helpful to first read the linked article above before continuing here.
Together with the code snippets from the previous article, you will be able to solve the famous Travelling Salesman Problem (TSP) on your personal computer. More importantly, you will appreciate everything that goes on behind the scenes.
Getting to the same page
In the first part, I gave an outline of the Evolutionary Algorithm framework as follows:
After looking at a couple of terminologies used in EA, we dug into the details of initializing the appropriate genotype (in Section 3.1, for <1>) as well as roulette wheel and tournament selection (in Section 3.2, for <2>).
We shall continue with Section 3.3 now.
3.3 — Variation
Variations can be unary (involving a single genotype) or binary (involving two genotypes). The objective is to end up with new genotype(s) which will, hopefully, have a higher fitness than its predecessor(s).
Statistics help us realize this hope. Simply by chance, some genotype would be better, while others would be worse. By working hand-in-hand with parent selection (section 3.2) and survival selection (section 3.4), the ‘successes’ count for much more than ‘failures’.
In sections 3.3.1 and 3.3.2, we focus on variations made to permutation-based genotypes.
Technically, the recombination process can involve more than two parents, but more is not necessarily better [1], and the scope of this article is kept at two parents.
3.3.1 — Recombination
This involves two parent genotypes.
Unlike binary representations, which can recombine using single-point or n-points crossover, it is less straightforward for permutation representations.
Suppose we have a permutation from 0 to 5 inclusive, from two parents (one in red, the other in pink). A crossover would result in duplicates of some indices, and the absence of others. This cannot be a solution to the TSP.
What we do, instead, is to apply the partial map crossover.
In the example below, the first offspring [0, 1, 3, 5, 2, 4] is obtained from the left portion of the first (red) parent, retained as-in, combined with yet-to-be-used indices from the second (pink) parent, with the relative order maintained. This gives us [0, 1] (from the red) and [3, 5, 2, 4] (from the pink) added together.
The motivation is as follows:
- The red parent [0, 1, 4, 3, 5, 2] already has a good (or at least decent) fitness, hence it was selected as a parent.
- It is possible that keeping a portion of its genotype, and shuffling the remaining, can lead to an improvement.
- We exploit the knowledge that the pink parent [3, 5, 1, 2, 0, 4] also has a good fitness — It visited 3, before 5, before 2, before 4.
- Rather than randomly shuffling the tail end of the red parent randomly, we scramble it to follow the order of visit by the pink parent.
The same is true when the two parents are switched. Hence, two offspring are obtained.
Get James Koh, PhD’s stories in your inbox
Join Medium for free to get updates from this writer.
Note that the cutoff could happen anywhere along the genotype with equal probability. If the cutoff was performed exclusively at the middle, we lose the opportunity for a diverse set of offspring in the subsequent generation. No one can say for certain that the first half is ideal and should be kept — it could well be just the first quarter, or perhaps the first three-quarters. Hence, all options should be kept on the table, and the work is left to statistics.
3.3.2 — Mutation
Still in the ‘Variation’ aspects of Evolutionary Algorithms, we move on to changes which are applicable to individual genotypes.
If a genotype comprises a permutation sequence, the changes to be applied has to involve some sort of re-ordering. It is not feasible to perform a bit flip, or to increase/decrease a single number.
One approach is to randomly select a number (for example, ‘2’) and shift it to the beginning or the end of the sequence. Another approach is to randomly select two numbers and exchange their positions with each other.
The idea here is to make minimal changes to a single genotype, with the hope of making an already good solution even better. Such variations would be especially helpful in scenarios where the solution is very good for most parts except for a point that is out of place.
Here’s the code for sections 3.3.1 (Recombination) and 3.3.2 (Mutation).
class Evolutionary:
def __init__(self, task):
self.task = task
def partial_map_crossover(self, parent1, parent2):
n = len(parent1)
point = random.randint(0, n-1)
child1 = list(parent1[0:point])
for j in parent2:
if (j in child1) == False:
child1.append(j)
child2 = list(parent2[0:point])
for j in parent1:
if (j in child2) == False:
child2.append(j)
return child1, child2
def run_evolution(self, population_size, generation_limit=5000, fitness_limit=1e99, crossover='single', verbose=True):
## ... define population ...
best_fitness_seen = -1e9
for i in tqdm(range(generation_limit)):
population = sorted(
population, key=lambda genome: self.task.fitness(genome), reverse=True
)
fitness = self.task.fitness(population[0])
if verbose and (fitness > best_fitness_seen):
best_fitness_seen = fitness
self.task.visualize(population[0], save_id=i)
if fitness >= fitness_limit:
break
## ... elitism; keep best individuals and variants of them ...
for j in range((population_size - n_keep)//2):
parents = self.selection(
population, self.task.fitness,
method='tournament'
)
if random.random() < 0.9:
offspring_a, offspring_b = self.partial_map_crossover(parents[0], parents[1])
else:
offspring_a, offspring_b = parents[0], parents[1]
if random.random() < 0.9:
offspring_a = self.swop(offspring_a)
offspring_b = self.swop(offspring_b)
next_generation += [offspring_a, offspring_b]
population = next_generation
best_genome = population[0]
return best_genome
def selection(self, ...):
## tournament or roulette wheel, or combination
def shift_to_end(self, genome, num=1):
new_genome = deepcopy(genome)
for _ in range(num):
a = random.sample(range(len(genome)), k=1)[0]
ref = deepcopy(new_genome[a])
if random.random() < 0.5:
new_genome[1:a+1] = new_genome[:a]
new_genome[0] = ref # bring to first
else:
new_genome[a:-1] = new_genome[a+1:]
new_genome[-1] = ref # bring to last
return new_genome
def swop(self, genome, num=1):
new_genome = deepcopy(genome)
for _ in range(num):
a, b = random.sample(range(len(genome)), k=2)
new_genome[a], new_genome[b] = genome[b], genome[a]
return new_genome3.4 — Survival selection
After discussing extensively on parent selection and variation, let’s move on to the third pillar of EA, which involves selecting which individuals in the population make it to the next population.
The first approach is to put all parents and offspring together, and select the fittest individuals to populate the next generation. The issue here is that we are ‘diluting’ the evolution effects. After going through all the trouble of creating offspring from parent selection + recombination + mutation, a substantial portion of those ends up being discarded. There’s some elements of ‘two steps forward and one step back’ in this.
The second approach is to (somewhat) mimic nature. All parents will ‘die’ and disappear from the population, and the next generation is entirely populated by the offspring. The problem here is that the best offspring is not necessarily better than the best parent — and removing all parents may cause us to be further away from the ideal solution.
As such, the middle ground is usually taken. We select the best individual(s) from the parents. We also mutate copies of them, with the hope that some perturbations further improve the solution. Then, we generate just enough offspring to full up the remaining places of the next population, without discarding any.
Specifically, in the ##... elitism; keep best individuals and variants of them ... component in section 3.3, we can do something like the following:
next_generation = population[:n_top] # keep the n_top fittest individuals
for _ in range(n_perturb):
# select a candidate from population[:n_top]
if np.random.random() < p_shift:
candidate = self.shift_to_end(candidate)
if np.random.random() < p_swop:
candidate = self.swop(candidate)
next_generation += [candidate]
n_keep = n_top + n_perturb3.5 — Termination
Perhaps your company has tasked you to apply EA and solve an industry problem, within a given budget. Or, perhaps you know the optimal objective value (but not the solution which gives that).
In such cases, you may want to perform early termination once the results are good enough.
If there’s no specific number to look for, and we are uncertain about what is ‘good enough’ in the first place, one approach is to stop the iteration after the improvement across a certain number of generations is smaller than some threshold.
If resources are not an issue, then you should be concerned about terminating too early rather than too late. It doesn’t hurt to go on with additional iterations, and run the evolution for more generations. Like in deep learning, we would keep the solution corresponding to the best iteration, and not the last iteration.
4. Getting The Results
4.1 Representing the TSP
Let’s build a class for the Travelling Salesman problem, to streamline the implementation process.
class Salesman:
def __init__(self, num_cities, x_lim, y_lim, read_from_txt=None):
if read_from_txt:
self.city_locations = []
f = open(read_from_txt)
for i, line in enumerate(f.readlines()):
if i==num_cities:
break
node_val = line.split()
self.city_locations.append(
(float(node_val[-2]), float(node_val[-1]))
)
self.num_cities = len(self.city_locations)
self.x_lim = np.max(np.array(self.city_locations)[:,0])
self.y_lim = np.max(np.array(self.city_locations)[:,1])
else: # generate randomly
self.num_cities = num_cities
self.x_lim = x_lim
self.y_lim = y_lim
x_loc = np.random.uniform(0, x_lim, size=num_cities)
y_loc = np.random.uniform(0, y_lim, size=num_cities)
self.city_locations = [
(x,y) for x,y in zip(x_loc,y_loc)
]
self.distances = self.calculate_distances()
def calculate_distances(self):
distances = np.zeros((self.num_cities, self.num_cities))
for i in range(self.num_cities):
for j in range(i + 1, self.num_cities):
dist = np.sqrt((self.city_locations[i][0] - self.city_locations[j][0]) ** 2 + (self.city_locations[i][1] - self.city_locations[j][1]) ** 2)
distances[i][j] = distances[j][i] = dist
return distances
def fitness(self, solution):
total_distance = 0
for i in range(self.num_cities - 1):
total_distance += self.distances[solution[i]][solution[i+1]]
fitness = -total_distance
return fitness
def visualize(self, solution, save_id=None):
n = len(solution)
assert n == len(self.city_locations), 'The solution must correspond to all cities'
for i, (x,y) in enumerate(self.city_locations):
plt.plot(x, y, "ro")
plt.annotate(i, (x, y))
ordered_cities = [self.city_locations[idx] for idx in solution]
x_coord = [x for (x,y) in ordered_cities]
y_coord = [y for (x,y) in ordered_cities]
distance = -self.fitness(solution)
plt.plot(x_coord, y_coord, "gray")
plt.title("Connected cities (%.1f) according to solution" % distance)
if save_id is not None:
filename = "results/plot_%03d.png" % save_id
plt.savefig(filename, bbox_inches='tight')
plt.close()
else:
plt.show()4.2 Train and observe
Putting together the code snippets above into a single Evolutionary class, the following can then be applied to find a solution to the TSP.
salesman = Salesman(
num_cities=30, x_lim=100, y_lim=100, read_from_txt='city_locations.txt'
)
evo = Evolutionary(salesman)
best_genome = evo.run_evolution(
population_size=200, generation_limit=1000, crossover='pmx', verbose=True
)
salesman.visualize(best_genome)If you’ve saved the intermediate results, you can simply put the screenshot images together to form a gif using my code which I shared here.
Congratulations! You now have the knowledge to solve an np-hard problem using evolutionary algorithm.
Conclusion
In this article, you learnt what makes Evolutionary Algorithm ticks, and how each component functions. Apart from the high level concepts, we dived deeply into the implementations, supported by visualization, codes, and tangible numbers.
References
[1] A. E. Eiben, P. E. Raue, and Z. Ruttkay, Genetic algorithms with multi-parent recombination (1994), In International conference on parallel problem solving from nature
