Lab 4: Genetic Algorithm

Lab learning outcomes

After completing this lab, the students are able to implement genetic algorithm to solve an optimisation problem.

Genetic algorithm

Consider the following problem:

Problem

You are given a sheet of paper with width w and height h. Your task is to cut the paper into squares of equal size. The aim of the task is to have as many squares as possible, and to have the area of each square as large as possible.

An optimisation problem can always be phrased in the form of

to optimise ... such that it maximises/minimises ...

In this problem, what is the parameter to be optimised and what are the parameters to be maximised or minimised?
Let x denotes the length of the sides of a square. We need a fitness function such that higher fitness corresponds to larger number of squares and large area. If the number of squares (that can be cut out) is zero, or the area of the square is zero, the fitness will be zero. Consider the fitness function of number of squares * area of a single square.

feature encoding

population initialisation

selection as parents

crossover

mutation

offspring (next generation population)

repeat from fitnexx calculation until termination

Feature encoding

In this problem as we only have one feature, i.e. the side length of the square, each chromosome consists of the value of the side length of the square. We will encode the chromosome in the form of Gray code.
numpy provides the function of binary_repr to convert a decimal value to its corresponding binary code.
The Python built-in function int can be used to convert back from the binary string to its integer value.

Population initialisation

A population is randomly generated according to the defined population size.
Create a function to generate randomly a population of size pop_size with each value lies between the range of pop_min to pop_max.
```
def generatePopulation(pop_size, pop_min, pop_max):
  # this function generate the first generation randomly based on the population size and the range of the value of each chromosome
  ...
  return population
```
This function and all the functions created after this should be placed before the if __name__ == "__main__": code block.
[Optional testing] You can test the function by changing the __main__ code block to
```
if __name__ == "__main__":
  print(generatePopulation(8, 0, 10))
```
The printed output should be a series of 8 chromosomes displayed as decimal values.

Fitness calculation

The fitness function was designed at the beginning of this section. Define a function that takes the input of a chromosome (as decimal value) and returns the fitness of the chromosome.
```
def calculateFitness(value):
  # this function calculates the fitness of a chromosome from the decimal value of the chromosome
  ...
  return fitness
```
2. [Optional] Test the function with
```
if __name__ == "__main__":
  print(calculateFitness(5))
```
The printed output should be the fitness of a chromosome of value 5, which would be a decimal value larger than zero.

Selection as parents

From the list of the chromosomes, we will select the chromosome pairs as parents. As we will be using one-point crossover, each pair of parents will produce exactly two offsprings. Therefore for population size of pop_size, we need pop_size/2 pairs of parents.
Define a function that takes the inputs of the current population and the total number of chromosomes in current population, and returns the chromosome pairs which will act as parents. The selection process is performed with the roulette wheel selection. The same chromosome can be selected more than once.
```
def selectParents(chromosomes, pop_size):
  ...
  return parent_pairs
```

[Optional] Test the function with

if __name__ == "__main__":
  print(selectParents([13, 8, 14, 7], 6))

The printed output should be 3 parent pairs, for example,

[[13, 8], [8, 14], [13, 7]]

Crossover

Define a function that takes a parent pair and returns a pair of offspring after performing one-point crossover.

def crossover(parents):
  # this function takes a parent pair and perform one-point crossover to produce a pair of offspring
  ...
  return offsprings

[Optional] Test the function with
```
if __name__ == "__main__":
  print(crossover([13, 9]))
```
The printed output should be a pair of offsprings, for example,
```
[10, 14]
```
13 is 1011 and 9 is 1101 in Gray code, the offsprings 10 is 1111 and 14 is 1001 in Gray code.

Mutation

Each gene in all chromosomes has the same mutation probability p_mutation.
Define a function that takes a chromosome and the mutation probability p_mutation as the inputs, and returns the mutated chromosome.
```
def mutate(chromosome, p_mutation):
  # this function mutates each gene of a chromosome based on the mutation probability
  ...
  return mutated
```
3. [Optional] Test the function with
```
if __name__ == "__main__":
  print(mutate(15, 0.1))
```
The printed output should be the mutated or unmutated chromosome, for example, 14.

15 is 1000 and 14 is 1001 in Gray code. In the example output, the last bit is mutated.

Repeat until termination

The common termination criteria are the maximum number of iterations and the distance among the fitnesses of the chromosomes of the latest population.

Define a function that calculates one metric to measure the distance among the fitnesses of the chromosomes, i.e. how far the fitnesses of all the chromosomes are from each other.

def findOverallDistance(chromosomes):
  # this function takes the input of the current population and returns the overall distance among fitnesses of all chromosomes
  ...
  return overall_distance

[Optional] Test the function with
```
if __name__ == "__main__":
  print(findOverallDistance([13, 11, 14, 7]))
```
The printed output should be a decimal value that represents the overall distance of fitnesses.

Combining all functions

The functions we have created can be combined with the following code snippet to execute the genetic algorithm to solve the problem defined at the beginning of this section. Consider the width and the height of the sheet of paper to be 20cm and 15cm.

if __name__ == "__main__":
  # main function
  ## parameter definition
  pop_size = 10
  pop_min = 1 #1cm
  pop_max = 10 #10cm
  curr_iter = 0
  max_iter = 100
  min_overalldistance = 0.5
  p_mutation = 0.05
  ## initialise population
  population = []
  population.append(generatePopulation(pop_size, pop_min, pop_max))
  while (curr_iter < max_iter and findOverallDistance(population[-1]) > min_overalldistance):
    curr_iter += 1
    ## select parent pairs
    parents = selectParents(population[-1], len(population[-1]))
    ## perform crossover
    offsprings = []
    for p in parents:
      new_offsprings = crossover(p)
      for o in new_offsprings:
        offsprings.append(o)
    ## perform mutation
    mutated = [mutate(offspring, p_mutation) for offspring in offsprings]
    ## update current population
    population.append(mutated)

Task: Consider a different fitness function than the one defined here. How does it change the outcome of the algorithm?

Report

Submit a report detailing the process, results, graphs, and your observations.