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 of
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
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 for each letter from a sentence is labeled as
founded_string(4-7). Therefore, 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 convers to a letter in the loop (7). After then, founded sentence (
new_chromosome) feeds to
fitness_function to initialize at least good start point for searching the best decisions (9-10).
def init_population ( len_chromosome, count_chromosomes ): 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
The roulette operator is presented as the function handles a list of sentences (chromosomes).
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 ) ) history_obj_func.append( round( sum( score_chromosomes )/len( chromosomes ), 2 ) ) 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 < selected_sector <= score_chromosome: selected_chromosomes.append(chromosome) return selected_chromosomes