Genetic Algorithms

Sablier
18.6K views

Open Source Your Knowledge, Become a Contributor

Technology knowledge has to be shared and made accessible for free. Join the movement.

Create Content

Tools

Genetic algorithms base themselves on natural selection, meaning the reproductive advantage of an individual that fits better in said environment. They make use of tools inspired by biology allowing the specie to evolve through generations.

Selection

This tool resemble the natural selection.

The giraffes able to eat high leaves are better at surviving

Each individual gets a fitting score, depending on the given problem. In this step, we will select individuals in order to create the next generation. This selection can be done that way:

  • A well fitted individual (high fitting score) has good chances at being selected
  • The lower the fitting score, the lower the chances at being selected

The first thing to do is to create a fitting function. It will score each individual. The function generally returns a floating number between 0 (bad score) and 1 (good score).

In this exercise, you will implement the fitting function. We will simply compare the chromosome with the solution.

Fitting function
1
2
3
4
5
6
7
8
9
from answer import get_answer
def get_score(chrom):
key = get_answer()
# TODO: implement the scoring function
# * compare the chromosome with the solution (how many character are in the correct position?)
return 0
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Once the fitting function has been defined, we can apply a selection on our population. The goal is to keep the best fitted individuals.

An example of selection function would be:

  • Select the best 30% individuals
  • Randomly select 20% of the rest

If only the best ones were to be kept (elitism), the risk is to head towards a local extremum without having the possibility to explore other potentially rewarding ways.

In the next exercise, we will implement the selection function.

Chromosomes selection
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import random
from answer import get_score
def score(chrom):
# floating number between 0 and 1. The better the chromosome, the closer to 1
# We coded the get_score(chrom) in the previous exercise
return get_score(chrom)
def selection(chromosomes_list):
GRADED_RETAIN_PERCENT = 0.3 # percentage of retained best fitting individuals
NONGRADED_RETAIN_PERCENT = 0.2 # percentage of retained remaining individuals (randomly selected)
# TODO: implement the selection function
# * Sort individuals by their fitting score
# * Select the best individuals
# * Randomly select other individuals
return []
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Genetic operators

These tools will directly impact the genetic material of a new individual.

Crossover / reproduction

We now need to fill our population with a new generation. In order to create this generation, we will make individuals reproduce. During this step, the parents will be exchanging their genetic material to produce a child Genetic recombination

Crossover of two chromosomes

A solution is to take each parent 50% of their genetic material, making the crossover in the middle of the chromosome. For instance if the parents are ABCDEFGH and 1345678, the child will be ABCD5678. There is no change in the genes' places.

There are other types of crossovers. One can take 70% of the genetic material of a parent and 30% of the other. Or we could do the crossover on multiple locations.

Two-points crossover

Chromosome crossover
1
2
3
4
5
6
7
def crossover(parent1, parent2):
# TODO: implement the crossover function
# * Select half of the parent genetic material
# * child = half_parent1 + half_parent2
# * Return the new chromosome
# * Genes should not be moved
return ""
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Mutation

In order to create new genetic material, some individuals will mutate. A gene will randomly be mutated.

Gene mutation

Mutation
1
2
3
4
5
6
7
8
9
10
import random
from answer import alphabet
def get_letter():
return random.choice(alphabet)
def mutation(chrom):
# TODO: implement the mutation function
# * Random gene mutation : a character is replaced
return chrom
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Open Source Your Knowledge: become a Contributor and help others learn. Create New Content