Skip to content

Genetic Algorithm From Scratch With Using Python

In the previous post, we considered the basic elements for understanding the genetic algorithm and main components such as fitness-function, selection, crossingover, and mutation. We are ready to develop canonical genetic algorithm from scratch with using my favorite program language – Python! Let’s start!

The Skeleton for Genetic algorithm

We defined the basic scheme for GA. Therefore we can sketch out the “black-box” functions (selection, crossingover, and mutation) . Below, the pseudocode with the “black-box” functions are placed inside a loop with the iterations labaled epoch. At the same time, we have defined the variables t, new, old. Each variable is a list of decisions (or population).

Take a look,oldis the sum oft and new where new is equal to t. After then,operator_selection( old ) will return a new chromosomes of decisions for next ireration.

new = []
old = []
t = init_GA()
for epoch in range(0, epochs):
    new = t 
    t = operator_roulette( t )
    t = operator_crossingover( t )
    t = operator_mutation( t )
    old = t+new
    t = operator_selection( old )

Firstly, we create the random decisions (3) and send to operator_roulette(6). The obtained decision goes to operator_crossingove(7) after then tooperator_mutation(8). Mentioned operations repeated while epochs aren’t finished (4).

Now, let’s define the task and apply the skeleton for it. Probably, everybody wrote a simple code to be printed a string such as ‘Hello world!’. Let’s do it with GA.

For this reason, we have to define a fitness-function. In our case, the fitness-function is the number of matches a letter with the position of the letter from template ‘Hello world!’.

Moreover, you should know that the letter such as space to be included too. Now, we can code it using a loop has a comparison iteration of the letter position(4-7). Finally, we need to calculate the total score for each chromosome because GA uses a set of chromosomes(12-13).

def fitness_function ( found_string, template='Hello world!' ):
    score = 0
    count = 0
    for letter in template:
        if letter == found_string[count]:
            score += 1
        count = count+1
    return score
  
def calculate_score ( chromosomes ):
    sum_score = 0
    for chromosome in chromosomes:
        sum_score+=fitness_function ( chromosome )
    return sum_score

Let’s describe the main function –init_GA. This function has a trick. You can see on line 6, the random genes are created by np.random.randint(31, 123). The interval between 31 and 123 represents code of letter, which is converted to the letter (7). That’s all and we can define operator Roulette.

def init_GA (len_chromosome, count_chromosomes = 4):
    sum_scores = 0
    new_chromosomes = []
    while True:
        new_chromosome = ''
        for gene in range(0, len_chromosome):
            new_chromosome+=chr( np.random.randint(31, 123) )
        
        if fitness_function(new_chromosome):
            new_chromosomes.append(new_chromosome)
        
        if count_chromosomes == len(new_chromosomes):
            break
    return new_chromosomes 

If you run this code, you would see the result like this:

['p/+L+Opx7odI', ',zlNs&.V/o<)', ',8H\\>/drr+dY', '-LD^Y *)XBWV']

The random string is a chomosome and a letter is a gene. Finally, our target is to transform eiher string to ‘Hello world!’.

Operator Roulette

Model of roulette has two basic ideas:

  • creating the sectors;
  • imitation of rotation.

Let’s start with creating the roulette sectors (15-19). A roulette circle will be divided into the sectors include chromosomes with the fitness function values (12). At the same time, we add the parameter prev_score for calculating the sum of previous sectors (19).

The imitation of rotation is presented at 21-14 lines. Firstly, it will be created a number of rotations and the random value (from zero to one) for each rotation at 9 line. After then, we should evaluate the random value by the roulette sector 23-24 and selected chromosomes return in main program context.

def operator_roulette ( chromosomes=[] ):
    
    rotation_roulette    = []
    selected_chromosomes = []
    score_chromosomes    = []
    
    sum_scores = calculate_score ( chromosomes )
    prev_score  = 0
    rotation_roulette = np.random.randint( 1, 10, size=len(chromosomes) )/10.0
    
    for chromosome in chromosomes:
        score_chromosomes.append( fitness_function( chromosome ) )
    
    roulette_sector = []
    for chromosome, score in zip( chromosomes, score_chromosomes ):
        roulette_sector.append( 
          ( np.round(prev_score, 2), np.round((score/sum_scores)+prev_score, 2) ) 
        )
        prev_score += np.float( score/sum_scores )
   
    for chromosome, score_chromosome in zip( chromosomes, roulette_sector ):
        for selected_sector in rotation_roulette:
            if score_chromosome[0] < selected_sector <= score_chromosome[1]:
                selected_chromosomes.append(chromosome)

    return selected_chromosomes

You should note that operator roulette will select the number of chromosome to be equale the number of roulette rotate.

Crossingover

Crossingover helps to use the useful properties of chromosomes by its splitting. The key idea is to divide the chromosomes into two slices (3-4). Each slice will randomly divide into a set of genes for crossbreeding (11).

def operator_crossingover ( chromosomes ):
    
    len_chr   = len( chromosomes )
    slice_chr = int( len_chr/2 )
    new_population = []

    for husband, wife in zip( chromosomes[ :slice_chr],
                             chromosomes[slice_chr:len_chr] ):
        children1 = []
        children2 = []
        crossing  = np.random.randint(1, len(husband))
        children1 = husband[ :crossing]+wife[crossing: ]
        new_chromosomes.append(children1)
        children2 = wife[ :crossing]+husband[crossing: ] 
        new_chromosomes.append(children2)
    return new_chromosomes

Mutation

Mutation is simplest operator in code. In this case, we get a single chromosome inside a loop and change one gene (letter). For this reason, we create a random value and check it. If value less than or equal to 30 percente (mutation propability), the gene will be changed.

def operator_mutation ( chromosomes ):
    new_chromosomes=[]
    for chromosome in chromosomes:
        if np.random.randint( 0,  100 ) <= 30:
            len_cromosome = len(chromosome) 
            crossing      = np.random.randint( 0,  len_cromosome )
            mutation_gen  = chr( np.random.randint(31, 123) )
            if crossing:
                chromosome =chromosome[ :crossing-1]+mutation_gen+\
                chromosome[crossing:len_cromosome]
            else:
                chromosome = mutation_gen+\
                chromosome[crossing+1:len_cromosome]       
            new_chromosomes.append( chromosome )     
        else:
            new_chromosomes.append( chromosome )
    return new_chromosomes

You can change the mutation propability. It will increase the degree of variability chromosomes.

Selection

Mutation is simplest operator in code. In this case, we get a single chromosome inside a loop and change one gene (letter). For this reason, we create a random value and check it. If value less than or equal to 30 percente (mutation propability), the curreant gene will be changed.

def operator_selection( chromosomes ):
    result          = []
    new_chromosomes = []
    score           = 0
    for chromosome in chromosomes:
        score = objective_function( chromosome ) 
        new_chromosomes.append((score, chromosome))
    new_chromosomes = sorted( new_chromosomes, reverse=True )    
    for key, val in new_chromosomes:
        result.append(val)    
    return result[ :int(len(chromosomes)/2)]

Be First to Comment

Leave a Reply

Your email address will not be published. Required fields are marked *