A genetic algorithm searches for a target by evolving a population of candidate solutions. Each candidate is a genome with a fitness score. Rather than changing one candidate alone, the algorithm selects parents, combines their genomes, mutates the resulting offspring, and evaluates the new population. section 9.5
For a target string, the search loop is:
- Initialize a population of random strings with the same length as the target. section 9.5
- Score each string against the target. Fitness is defined as 1/loss, where loss measures distance between corresponding ASCII string characters. section 9.5
- Choose two parents using probabilities ranked by fitness. Pick a random crossover index to produce two children, then randomly change characters according to the mutation rate. section 9.5
- Add offspring to the new population and repeat until the fittest string matches the target or the fixed iteration limit is reached. section 9.5
Evolving “Genome”
Start with randomly initialized letter sequences and set “Genome” as the target. Repeated fitness scoring, crossover, and mutation can produce the exact target sequence. This small search problem makes each operation visible, though genetic algorithms can take a long time to converge on other problems. section 9.5 section 9.6
Listing 9.6 Genetic algorithm implmentation
import numpy as np
import string
class GeneticAlgorithm():
def __init__(self, target_string, population_size, mutation_rate):
self.target = target_string
self.population_size = population_size
self.mutation_rate = mutation_rate
self.letters = [" "] + list(string.ascii_letters)
def initialize(self): #1
self.population = []
for _ in range(self.population_size):
individual = "".join(np.random.choice(self.letters,
size=len(self.target)))
self.population.append(individual)
def calculate_fitness(self): #2
population_fitness = []
for individual in self.population:
loss = 0 #3
for i in range(len(individual)):
letter_i1 = self.letters.index(individual[i])
letter_i2 = self.letters.index(self.target[i])
loss += abs(letter_i1 - letter_i2)
fitness = 1 / (loss + 1e-6)
population_fitness.append(fitness)
return population_fitness
def mutate(self, individual): #4
individual = list(individual)
for j in range(len(individual)):
if np.random.random() < self.mutation_rate:
individual[j] = np.random.choice(self.letters)
return "".join(individual)
def crossover(self, parent1, parent2): #5
cross_i = np.random.randint(0, len(parent1))
child1 = parent1[:cross_i] + parent2[cross_i:]
child2 = parent2[:cross_i] + parent1[cross_i:]
return child1, child2
def run(self, iterations):
self.initialize()
for epoch in range(iterations):
population_fitness = self.calculate_fitness()
fittest_individual =
self.population[np.argmax(population_fitness)]
highest_fitness = max(population_fitness)
if fittest_individual == self.target:
break
parent_probabilities = [fitness / sum(population_fitness) for
fitness in population_fitness] #6
new_population = [] #7
for i in np.arange(0, self.population_size, 2):
parent1, parent2 = np.random.choice(self.population,
size=2, p=parent_probabilities, replace=False) #8
child1, child2 = self.crossover(parent1, parent2) #9
new_population += [self.mutate(child1), self.mutate(child2)] #10
print("iter %d, closest candidate: %s, fitness: %.4f" %(epoch,
fittest_individual, highest_fitness))
self.population = new_population
print("iter %d, final candidate: %s" %(epoch, fittest_individual))
if __name__ == "__main__":
target_string = "Genome"
population_size = 50
mutation_rate = 0.1
ga = GeneticAlgorithm(target_string, population_size, mutation_rate)
ga.run(iterations = 1000)
The Python listing organizes the from-scratch implementation around initialization, fitness calculation, mutation, crossover, and the run loop. section 9.5
The same population-based search idea can be considered for other candidate designs, including neural network architecture search. Choosing an effective problem is itself a useful exercise: identify what a genome represents, how to score it, and what crossover and mutation would change. section 9.6 section 9.7 section 9.5
