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!

Skeleton for Genetic algorithm

I suggest to code genetic algorithm, which invokes the “black-box” functions. 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;tto be stored 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. Firstly, we generate the decisions list at random (3) and push it to operator_roulette(6) and the obtained list go 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 genetic algorithm.

We should 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 like a loop with comparison of each input letter with the position of letter from template ‘Hello world!’ (4-7). If you recall, genetic algorithm use the chromosomes (in math languages vectors) so we need calculate the total score for each fitness-function (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

It’s important to define the start point for algorithm via init_population. 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 a letter(7). After then, new_chromosome push to new_chromosomes. At 12 line, the length of new_chromosome is compared to 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 

Operator 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

Crossingover.

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