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, which invokes the genetic operators sequence where each operator will be detalized later. You may consider the genetic operators like the abstract black-box functions are used in genetic algorithm. 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 with a population of decisions. We addtto store the actual population while the genetic operators execute. Take a look,oldis the sum oft and new where new is equal t before it’s feeded the genetic operators. After then,operator_selection( old ) is used to return a new population of decisions.

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 is simple and readable. Actually, this code reflects the skeleton of genetic algorithm. We generate the decisions list (3) and push it to operator_roulette(6) and the obtained list go to operator_crossingove(7) and operator_mutation(8). Mentioned operations repeated while epochs aren’t finished (4).

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 *