Genetic Algorithm Optimization in Python

Jan 05, 2023 16 min read Updated on May 28, 2023

Genetic algorithms is a subclass of evolutionary computing and works by searching through a large set of potential solutions to find the best one based on some measurement of fitness (as in survival of the fittest). As in biology, diversification in solutions is introduced via different selection methods, crossover, and mutation.

A binary genetic algorithm (BGA) is one type of genetic algorithm that is effective at working with both continuous and discrete variables, as well as optimizing for many decision variables at once.

Python and `tabulate`

(optional but makes tables pretty).

```
import random
import math
# https://pypi.org/project/tabulate/
from tabulate import tabulate
```

```
random.seed(1234)
```

Helper function to print table using `tabulate`

.

```
def print_table(population):
print(tabulate(population, headers=['n', 'encoding', 'decoded x, y', 'cost'], floatfmt=".3f", tablefmt="simple"), end="\n\n")
```

In BGA, decision variables are represented as binary chromosomes and each gene in the chromosome is encoded using a certain number of bits, `M_BITS`

. Variables encoded for selection, crossover, and mutation, and then decoded for fitness evaluation using the cost function `f`

.

A population `N_POP`

is a group of chromosomes, where each chromosome represent a potential solution to the optimization problem.

The function for encoding a decimal number into its binary representation.

```
def encode(x, x_low, x_high, m):
decimal = round((x - x_low) / ((x_high - x_low) / (2 ** m - 1)))
binary = []
while decimal >= 1:
if decimal % 2 == 1:
binary.append(1)
else:
binary.append(0)
decimal = math.floor(decimal / 2)
while len(binary) < 4:
binary.append(0)
return list(reversed(binary))
```

```
assert encode(9, -10, 14, 5) == [1, 1, 0, 0, 1]
```

The variables `x_low`

and `x_high`

represent lower and upper bounds of the range for `x`

. The variable `m`

is the number of bits used to encode genes (note that `m`

is also referred to as `M_BITS`

).

The function for decoding a binary representation into its decimal number is `x = x_low + B * ((x_high - x_low) / ((2 ** m) - 1))`

, where `B`

is binary value to convert into decimal.

```
def decode(B, x_low, x_high, m):
return x_low + int((''.join(map(str, B))), 2) * ((x_high - x_low) / ((2 ** m) - 1))
```

```
assert int(decode([1, 1, 0, 0, 1], -10, 14, 5)) == 9
```

The initial population is generated arbitrarily. The chromosomes are decoded and evaluated using the cost function and appended to a cost table, which is sorted in ascending order (lower cost is better).

```
def generate_population(n_pop, x_range, y_range, m_bits):
pop_lst = []
for i in range(n_pop):
x = random.randint(x_range[0], x_range[1])
y = random.randint(y_range[0], y_range[1])
# encoded values
x_encoded = encode(x, x_range[0], x_range[1], m_bits)
y_encoded = encode(y, y_range[0], y_range[1], m_bits)
# decoded values
x_decoded = round(decode(x_encoded, x_range[0], x_range[1], m_bits), 2)
y_decoded = round(decode(y_encoded, y_range[0], y_range[1], m_bits), 2)
# determine initial cost
cost = round(f(x_decoded, y_decoded), 2)
# append to list
pop_lst.append([i, x_encoded + y_encoded, [x_decoded, y_decoded], cost])
# sort on cost
pop_lst.sort(key = lambda x: x[3])
# update index
for i in range(len(pop_lst)):
pop_lst[i][0] = i
return pop_lst
```

Below is an example population.

```
example_population = generate_population(
n_pop=6,
x_range=[5, 20],
y_range=[-5, 15],
m_bits=4
)
print_table(example_population)
# n encoding decoded x, y cost
# --- ------------------------ -------------- -------
# 0 [0, 0, 0, 0, 0, 0, 1, 0] [5.0, -2.33] 55.820
# 1 [0, 0, 1, 1, 1, 0, 0, 0] [8.0, 5.67] 57.320
# 2 [0, 0, 0, 0, 0, 0, 0, 0] [5.0, -5.0] 62.500
# 3 [0, 0, 0, 1, 0, 0, 1, 0] [6.0, -2.33] 66.990
# 4 [0, 1, 1, 1, 0, 0, 0, 0] [12.0, -5.0] 150.000
# 5 [1, 1, 1, 0, 0, 0, 1, 0] [19.0, -2.33] 212.130
```

Offsprings are generated using double-point crossover (there are other methods).

```
def generate_offsprings(population, crossover):
n = 0
offsprings_lst = []
while n < len(population):
offsprings_lst.append(population[n][1][0:crossover[0]] + population[n + 1][1][crossover[0]:crossover[1]] + population[n][1][crossover[1]:])
offsprings_lst.append(population[n + 1][1][0:crossover[0]] + population[n][1][crossover[0]:crossover[1]] + population[n + 1][1][crossover[1]:])
# pair-wise
n += 2
return offsprings_lst
```

Basically, select two parent chromosomes from the population and choose two points within them as crossover points (at random or otherwise). Split the chromosomes at these points to create four segments. The first and fourth segments are swapped between the two parent chromosomes to create two new offsprings.

Mutation works by introducing small random changes to the chromosomes. Mutations allows the algorithm to explore a wider range of potential solutions and avoids getting stuck in local optima.

```
def mutate(offsprings, mu, m_bits):
nbits = round(mu * (len(offsprings) * m_bits * 2))
for i in range(nbits):
offspring = random.randint(0, len(offsprings) - 1)
bit = random.randint(0, m_bits * 2 - 1)
# flip bits
if offsprings[offspring][bit] == 1:
offsprings[offspring][bit] = 0
else:
offsprings[offspring][bit] = 1
return offsprings
```

The parameter `mu`

(also referred to as `MUTATE_RATE`

) is the mutation rate and is used with `M_BITS`

to decide how many bits to flip. The bits are flipped at random.

The population is updated by replacing some or all of the existing chromosomes with the new offsprings. The number of chromosomes that are kept from the previous population is determined by the `keep`

parameter (also referred to as `N_KEEP`

).

```
def update_population(current_population, offsprings, keep, x_range, y_range, m_bits):
offsprings_lst = []
for i in range(len(offsprings)):
# decoded values
x_decoded = round(decode(offsprings[i][:4], x_range[0], x_range[1], m_bits), 2)
y_decoded = round(decode(offsprings[i][4:], y_range[0], y_range[1], m_bits), 2)
# determine initial cost
cost = round(f(x_decoded, y_decoded), 2)
# append to list
offsprings_lst.append([i, offsprings[i], [x_decoded, y_decoded], cost])
# sort on cost
offsprings_lst.sort(key = lambda x: x[3])
# update index
for i in range(len(offsprings_lst)):
offsprings_lst[i][0] = i
# discard current population
current_population[keep:] = offsprings_lst[:keep]
# sort on cost
current_population.sort(key = lambda x: x[3])
# update index
for i in range(len(current_population)):
current_population[i][0] = i
return current_population
```

The offsprings are evaluated using the cost function and sorted based on their fitness. The `N_KEEP`

fittest offsprings then replace the same number of least fit chromosomes in the previous population.

Below is the configuration variables used in this example.

```
M_BITS = 4
N_POP = 4
N_KEEP = 2
MUTATE_RATE = 0.1
# max number of generations (for sanity check)
MAX_GEN = 10000
# crossover
crossover = [3, 6]
```

The cost function is `f(x, y) = -x * ((y / 2) - 10)`

, x-range is `[10, 20]`

, and y-range is `[-5, 7]`

.

```
# cost function
def f(x, y): return -x * ((y / 2) - 10)
# range
x_range = [10, 20]
y_range = [-5, 7]
```

The initial population.

```
current_population = generate_population(N_POP, x_range, y_range, M_BITS)
print_table(current_population)
# n encoding decoded x, y cost
# --- ------------------------ -------------- -------
# 0 [1, 0, 0, 0, 1, 1, 0, 0] [15.33, 4.6] 118.040
# 1 [0, 0, 1, 1, 0, 0, 0, 1] [12.0, -4.2] 145.200
# 2 [1, 1, 1, 0, 1, 0, 0, 1] [19.33, 2.2] 172.040
# 3 [1, 1, 1, 0, 1, 0, 0, 1] [19.33, 2.2] 172.040
```

The final population.

```
for i in range(MAX_GEN):
# generate offsprings
offsprings = generate_offsprings(current_population, crossover)
# mutate
offsprings = mutate(offsprings, MUTATE_RATE, M_BITS)
# update population
current_population = update_population(
current_population,
offsprings,
N_KEEP,
x_range,
y_range,
M_BITS
)
print_table(current_population)
# n encoding decoded x, y cost
# --- ------------------------ -------------- ------
# 0 [0, 0, 0, 0, 1, 1, 1, 1] [10.0, 7.0] 65.000
# 1 [0, 0, 0, 0, 1, 1, 1, 1] [10.0, 7.0] 65.000
# 2 [0, 0, 0, 0, 1, 1, 1, 1] [10.0, 7.0] 65.000
# 3 [0, 0, 0, 0, 1, 1, 1, 1] [10.0, 7.0] 65.000
```

Updated on May 27, 2023 Changelog