Loading [Contrib]/a11y/accessibility-menu.js
Back
Close

Genetic Algorithms

Sablier
117.5K views

Algorithm

Algorithm overview

  1. Create the base population We create a random initial population. Each individual is is defined by its genetic material. We create a new individual with the previously declared create_chromosome(size) function.
  2. Evaluation Each individual is scored on its fitting to the problem. This is done in the beginning of the selection.
  3. Selection Each individual has a chance to be retained proportional to the way it fits the problem. We only keep the selected individuals returned by the selection(population) function.
  4. Crossover / reproduction Random couples are formed in the selected population. Each couple produces a new individual. The number of individuals in the population can either be constant or vary over time.

On each reproduction :

  • Crossover The genetic material of a child is a combination of the parents' (generally 50% of each parent's genetic material). Once the parents have been chosen the ``crossover(parent1, parent2)` function allows the creation of the child.
  • Mutation Probability : from 0.1% to 1% Each child have a chance to have a randomly modified gene thanks to the mutation(chromosome) function.

Finally, the is_answer(chromosome) function checks if the individual is solution to the problem (100% score). If there is no solution, we go to the next generation (phase 2).

Recap

The goal of this exercise is to find the secret sentence using a genetic algorithm and the tools we created earlier.

Genetic algorithm
Create your playground on Tech.io
This playground was created on Tech.io, our hands-on, knowledge-sharing platform for developers.
Go to tech.io
import random
import sys
from answer import is_answer, get_mean_score
# You can redefine these functions with the ones you wrote previously.
# Another implementation is provided here.
from encoding import create_chromosome
from tools import selection, crossover, mutation
def create_population(pop_size, chrom_size):
# use the previously defined create_chromosome(size) function
# TODO: create the base population
chrom = create_chromosome(chrom_size)
return ???
def generation(population):
# selection
# use the selection(population) function created on exercise 2
select = selection(population)
# reproduction
# As long as we need individuals in the new population, fill it with children
children = []
# TODO: implement the reproduction
while len(children) < ???:
## crossover
parent1 = ??? # randomly selected
parent2 = ??? # randomly selected
# use the crossover(parent1, parent2) function created on exercise 2
child = crossover(parent1, parent2)
## mutation
# use the mutation(child) function created on exercise 2
child = mutation(child)
children.append(child)
# return the new generation
return select + children
def algorithm():
chrom_size = int(input())
population_size = ???
# create the base population
population = create_population(population_size, chrom_size)
answers = []
# while a solution has not been found :
while not answers:
## create the next generation
# TODO: create the next generation using the generation(population) function
population = ???
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
codingame x discord
Join the CodinGame community on Discord to chat about puzzle contributions, challenges, streams, blog articles - all that good stuff!
JOIN US ON DISCORD
Online Participants