Skip to content

Genetic Algorithm From Scratch With Using Python

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

I suggest to code the function calling sequence (genetic operators) and after then each function will be detalized. So, you may imagine that selection, crossingover and mutation are abstract black-box functions always to be used in this algorithm. Below, you can see simple code with the black-box functions inside the loop with epochs. Ok, what else can you notice? Yes, there are some variables such as t,new,old. Each variable is a list with the decisions, where t – actial list to be used for calculating the best decisions by genetic operators, new– the list after finishing the loop and old is sum oft and new. Take a look, the oldlist uses in operator_selection( old ), and selects the best decisions from new and current list.

new = []
old = []
t = init_population()
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 )

I hope this code slice is simple and readable. Indeed, if you read the previous post, you remember this code reflects the skeleton of genetic algorithm. Firstly, it generates the random list and push it to operator_roulette(6) after then the handled list go to operator_crossingove(7) to accumalate the useful property and finaly operator_mutation (8) is triggered to random change of decision for the random search of the best decision. Secondly, it’s needed to join two list newand t to take into account all solutions found for operator_selection, which skips only best decisions are maximum or minimum of fitness-function. Mentioned operations are repeated while epochs aren’t finished (4). The init_population is assigned to tand randomly creates list of decisions (3).

Now, let’s define concrete task and apply skeleton for it. Probably, everybody wrote a simple code to be printed string such as ‘Hello world!’, why not write ‘Hello world!’ with using the genetic algorithm? We have template such as ‘Hello world!’ which may be used for design of fitness-function. In this case, the score is amount of matches with template (‘Hello world!’) for each letter from a sentence is labeled as founded_string(4-7). Therefore, the score with the greatest amount of matches is optimal for our task. Since we defined the fitness function, we need calculate the total score for each sentence inside a list (12-13). In this way, the chromosomes are a set of sentences in the list.

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

It’s important to define the start point for algorithm via init_population. This function has the trick. You can see on line 6, the random genes are created by np.random.randint(31, 123). The interval between 31 and 123 contains a char code, which is converted to a letter in the loop (6). After then, founded sentence (new_chromosome) feeds to fitness_function to initialize at least good start point for searching the best decisions (9-10). At 12 line, the length of new_chromosome compares to the variable is labaled count_chromosomes.

def init_population ( 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 

And when init_populationcreated a set of chromosomes (in our case, sentences), it’s feeded to the roulette operator. There are two main features ( creating the sectors and modeling the roulette). Let’s start with creating the roulette sectors (15-19). The roulette circle is divided into the chromosomes according the fitness function values. For this reason, it’s added the parameter prev_score with contribution of each chromosome (19). And the roulette sector is calculated as tuple with point of the start sector (prev_score) and termination of the sector((score/sum_scores)+prev_score) at 17 line. For modeling the roulette added 21-24 lines of code. For this reason, we create some randoms according to length of chromosomes rotation_roulette at 9 line, and we use its in loop for modeling the roulette. If mentioned random value falls into sector, which presents as the tuple with start and terminate of sector (23), cromosome for this sector is selected (24). Finally, 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

After the operator roulette we will invoke the next genetic operator - operator_crossingover. The key idea is to share with each other genes (sentences) (7-14). In this reason, we use the standard feature in python such as slices with ':' operator. Firstly, a chromosomes list is used At 11 line we invoke a random value to be crossover point labaled as 'crossing'. and use by dividing at 12 and 14 lines

def operator_crossingover ( chromosomes ):
    
    len_chr   = len( population )
    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

Be First to Comment

Leave a Reply

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