A simple optimization goal is defined first, and the genetic algorithm is then implemented in a straightforward manner.
The goal is to produce chromosomes that contain
seven lucky numbers(7) and then to form a genome composed of seven such chromosomes, as shown below:
GENE_COUNT = 7
CHROMOSOME_COUNT = 7
GENERATION_LIMIT = 777
# The goal genome is configured 7 x 7 matrix and each gene is `7`
goal_genome => [[7, 7, 7, 7, 7, 7, 7],
[7, 7, 7, 7, 7, 7, 7],
[7, 7, 7, 7, 7, 7, 7],
[7, 7, 7, 7, 7, 7, 7],
[7, 7, 7, 7, 7, 7, 7],
[7, 7, 7, 7, 7, 7, 7],
[7, 7, 7, 7, 7, 7, 7]]
# This is the way to create the genome
def generate_genome(self):
genome = []
for _ in range(self.GENOME_COUNT):
chromosome = []
for _ in range(self.GENE_COUNT):
gene = random.randint(0, 9)
chromosome.append(gene)
genome.append(chromosome)
return genome
The method for creating the genome is shown above.
A
fitness function is now required to evaluate each genome in every generation. It can be computed by subtracting the lucky numbers from each gene and summing the scores across all chromosomes.
For example, consider a chromosome containing the following numbers:
[1, 7, 6, 5, 9, 3, 2].
The fitness of each gene is evaluated by computing the difference between each number generated by the
generate_genome function and
7 and converting it into an absolute value.
In this example, the fitness of each gene is as follows:
[1, 7, 6, 5, 9, 3, 2] => [6, 0, 1, 2, 2, 4, 5]
If all fitness values are
0, the evolution is terminated before the maximum generation number is reached.
Make each gene into the dominant factor
Next, a process is required to select parent chromosomes and to
crossover the selected chromosomes.
The selection of chromosomes is based on the sum of fitness values; the closer this sum is to 0, the better the chromosome.
Several crossover methods exist, but uniform crossover is used here.
Uniform crossover proceeds as follows.
The uniform crossover method randomly selects one of the parent chromosomes to
mask the genes of that parent chromosome and assigns the masked gene to the child chromosome.
A more detailed description of uniform crossover is available
here, and its implementation is shown below.
def reproduction_genome(self, parent_chromosome, child_chromosome, best_parents_indices):
for i in range(self.GENOME_COUNT):
for j in range(self.GENE_COUNT):
if random.random() < self.MUTATION_RATE:
mutated_gene = random.randint(0, 9)
child_chromosome[i][j] = mutated_gene
else:
idx = random.randint(0, 1)
selected_parent = best_parents_indices[idx]
crossoverd_gene = parent_chromosome[selected_parent][j]
child_chromosome[i][j] = crossoverd_gene
Finally, the processes described above are iterated until the goal is met.
In this example, the desired result is obtained before reaching the maximum generation (777), because a simple objective was set.
Evaluating fitness in each generation
The traveling salesman problem (also called the traveling salesperson problem or
TSP) is one of the well-known problems in computer science.
The problem is to visit all cities exactly once and to find the order that minimizes the total distance of the route returning to the original starting point.
In this problem, a number of
cities and their
coordinates are received as input.
Traveling salesman problem
From the left, Coordinates of cities · The shortest distance of visit
Given the coordinates of the cities, the genome is the order in which the cities are visited.
The first and last entries in the visit sequence must be the same origin point.
For example, given 20 cities and an origin (0), the genome can be created as follows:
[0, 12, 10, 17, 14, 3, 11, 5, 19, 16, 8, 7, 1, 9, 15, 4, 6, 13, 2, 18, 0].
The fitness of the genome is determined by the sum of the visiting distances in the current order (indices), computed through the formula for
calculating the distance between two points.
If the city coordinates are given as follows and the genome is in the sequence shown above, the fitness is computed as shown in the figure below.
city_coordinates = [[217, 314], [328, 294], [394, 269], [272, 337], [485, 210],
[328, 371], [418, 340], [299, 353], [247, 230], [158, 377],
[139, 285], [153, 389], [100, 364], [395, 286], [247, 349],
[236, 227], [422, 370], [207, 279], [356, 232], [312, 350]]
genome = [0, 12, 10, 17, 14, 3, 11, 5, 19, 16, 8, 7, 1, 9, 15, 4, 6, 13, 2, 18, 0]
def evaluate_distance(self, city_1, city_2):
x1, y1 = city_1
x2, y2 = city_2
distance = math.sqrt((x2-x1)**2 + (y2-y1)**2)
return distance
distances = [127.24, 88.1, 68.26, 80.62, 27.73, 129.87, 175.92, 26.4, 111.8, 224.11,
133.54, 65.74, 189.18, 169.07, 249.58, 146.25, 58.69, 17.03, 53.94, 161.38]
fitness = sum(distances)
For this problem, the
order one crossover method is used among the available crossover methods.
First, a portion of the
parent_1 genome is randomly sliced and assigned to the
offspring genome.
The remaining genes are then taken from the
parent_2 genome to complete the offspring genome.
A mutation function that changes the city visit order with a random probability can also be added.
Please refer to the
github link for the code related to order one crossover and mutation.
Conception of the order one crossover
Finally, a threshold value is set. It is used to remove a genome from the population if its fitness is lower than the threshold that was set.
population = [[0, 12, 10, 17, 14, 3, 11, 5, 19, 16, 8, 7, 1, 9, 15, 4, 13, 2, 18, 0]
[0, 1, 3, 17, 14, 10, 11, 5, 4, 16, 8, 7, 12, 9, 15, 19, 18, 13, 2, 6, 0]
.
.
.
[0, 17, 1, 12, 15, 3, 6, 7, 19, 16, 8, 5, 10, 9, 14, 4, 11, 13, 18, 2, 0]]
if fitness > self.weakness_threshold:
population.remove(genome)
The image below compares the cases with a threshold and without a threshold.
Applying a threshold finds the shortest path in an earlier generation than the version without it.
Calculate minimum distance
From the left, With threshold, Without threshold