Last updated February 28, 2024
In AI Mysteries

Genetic Algorithms Made Easy With EasyGA

Share

Published on July 15, 2021

by Yugesh Verma

Genetic algorithms(GA) are a rapidly growing area of artificial intelligence and machine learning. They are based on natural selection and genetics. Genetic algorithms are adaptive heuristic algorithms; as such, they represent an intelligent utilization of random search to solve optimization problems. The idea of GA is given by John Holland which follows the principle “Survival of the fittest ” by Charles Darwin about evolution. In computer science, we can say that algorithms performing well or adapting in nature will stay in evolution. Let’s consider we are having a problem, and there are many solutions for this problem, and from this solution space, we need to find an optimized solution. The algorithm will look into all the solutions. Suppose a combined solution can be the best solution. In that case, the algorithm will extract those solutions. By combining them, it will make a child solution. Next time, the generated child solution will be combined with another solution to give their child a solution. This will always help us to improve the results. This is why we say it is focused on optimization. More formally, we can say here we are not finding the solution; we already have the solution; we are finding the best-optimized solution by reproducing from a given solution space.

GA is commonly used to generate sustainable solutions of optimization or search problems; It is just like finding the best solution from a huge set of available solutions. To find the best solution, some steps are followed by the algorithms. The flowchart below can better explain the steps.

Here in the above flowchart, the lines showing the solutions; let’s start a discussion on blocks of the above flowchart.

Initial population – this is just a space of solutions for a given problem. The larger the population, the result will be much better. For example, in travelling between two points, there can be many ways available, and some have huge traffic but the shortest distance, and some have low traffic and huge distance. So all ways can be considered as the initial population.

Converge (if yes) – we have the best solution in this case, and we can proceed with that solution. The genetic algorithm will automatically choose the solution and stop working.

Converge (if not) – if the solution is not the best-optimized solution, the algorithm will send the solution to reproduce a new solution from it.

Evaluate the fitness – whatever inputs we are providing, the best output should come. So in the evaluation, it checks for the best-fit inputs. For example, we have a search engine, and we are searching for how to make a genetic algorithm, and by mistake, we typed “how to take a genetic algorithm”. So it is the job of our search engine to consider “take” as “make”. To do this, search engines will seek the best fit from the available solution.

In the set of solutions, it can have many words like take, cake. So to create “make” algorithm will give some fitness value to “take” and “cake”, and that can be measured.

Select mate – It is the process of selecting a solution with a high fitness value. There will be many words in the above case, selecting the more relevant word for making the best-optimized solution.

Crossover – there are various methods to do a crossover. It is a method to generate a new population. As we have discussed, the higher the population, the better the result. So here, the crossover is a technique to increase the population size. For example, we have the words abcde and efghi, in one method of crossover, what it suggests is to swap the keyword by randomly selected place in the word to make a new population. In the picture below we can see the swap between de and hi from the words.

Mutation – Generating a new population mutation is nothing but ensuring that the new population is better than the old available population.

These all processes get repeated until the solution does not come under the selection.

For more information about genetic algorithms, we can refer to this article.

What if we don’t have much knowledge to build a genetic algorithm and are required to use it. A python package called EasyGA came to save us from this difficult situation. Next, in this article, we are going to discuss the basics of EasyGA.

EasyGA

As the name suggests, EasyGA is a package to implement genetic algorithms easily. It is a well-designed package to work with GA. It also allows users to customize its feature according to their requirements.

Code Implementation of EasyGA

The following code implementation is in reference to the official implementation. Let’s start with the installation of the EasyGA using google colab.

Input:

!pip3 install EasyGA

We can use the above pip3 install command to install the EasyGA python package.

Let’s look at some basic examples of evolving a generic algorithm to get more knowledge about the package.

Importing the library

Input:

import EasyGA as EGA

Creating an object of a genetic algorithm.

ega = EGA.GA()

Evolving the genetic algorithm until the termination of it to make the population.

ega.evolve()

Extracting information about the algorithm.

Input:

 ega.print_generation()
 ega.print_population()
 ega.print_best_chromosome()
 ega.print_worst_chromosome()

Output:

 Current Generation : 100
 Chromosome - 0 [5][5][5][5][5][5][5][5][5][5] / Fitness = 10
 Chromosome - 1 [5][5][5][5][5][5][5][5][5][5] / Fitness = 10
 Chromosome - 2 [5][5][5][5][5][5][5][5][5][5] / Fitness = 10
 Chromosome - 3 [5][5][5][5][5][5][5][5][5][5] / Fitness = 10
 Chromosome - 4 [5][5][5][5][5][5][5][5][5][5] / Fitness = 10
 Chromosome - 5 [5][5][5][5][5][5][5][5][5][5] / Fitness = 10
 Chromosome - 6 [5][5][5][5][5][5][5][5][5][5] / Fitness = 10
 Chromosome - 7 [5][5][5][5][5][5][5][5][5][5] / Fitness = 10
 Chromosome - 8 [5][5][5][5][5][2][5][5][5][5] / Fitness = 9
 Chromosome - 9 [5][5][5][2][5][5][5][5][5][5] / Fitness = 9
 Best Chromosome : [5][5][5][5][5][5][5][5][5][5]
 Best Fitness    : 10
 Worst Chromosome : [5][5][5][2][5][5][5][5][5][5]
 Worst Fitness    : 9

Here we can see how our algorithm evolved in terms of population and best and worst chromosomes and how many generations are there in the algorithm.

Let’s look at an example to get a clear picture of the package. In this example, we will generate passwords, see the best and worst chromosomes, and visualise the algorithm’s evolution.

Evolving an algorithm for password matching.

Input:

 import EasyGA
 import random
 ega = EasyGA.GA()
 password = input("Please enter a word: \n")
 # Basic Attributes
 ega.chromosome_length = len(password)
 ega.fitness_goal = len(password)
 # Size Attributes
 ega.population_size = 50
 ega.generation_goal = 10000
 # User defined fitness
 def password_fitness(chromosome):
     return sum(1 for gene, letter
         in zip(chromosome, password)
         if gene.value == letter
     )
 ega.fitness_function_impl = password_fitness
 # What the genes will look like.
 ega.gene_impl = lambda: random.choice(["A","a","B","b","C","c","D","d","E","e",
                                       "F","f","G","g","H","h","I","i","J","j",
                                       "K","k","L","l","M","m","N","n","O","o",
                                       "P","p","Q","q","R","r","S","s","T","t",
                                       "U","u","V","v","W","w","X","x","Y","y",
                                       "Z","z"," "])
 # Evolve the genetic algorithm
 ega.evolve()

Output:

 Please enter a word: 
 analytics india  magazine

Let’s check for the attributes of the algorithm.

Input :

 ega.print_generation()
 ega.print_population()
 ega.print_best_chromosome()
 ega.print_worst_chromosome()
 # Show graph of progress
 ega.graph.highest_value_chromosome()
 ega.graph.show()

Output:

 Current Generation : 1467
 Chromosome - 0 [a][n][a][l][y][t][i][c][s][ ][i][n][d][i][a][ ][ ][m][a][g][a][z][i][n][e] / Fitness = 25
 Chromosome - 1 [a][n][a][l][y][t][i][c][s][ ][i][n][d][i][g][ ][ ][m][a][g][a][z][i][n][e] / Fitness = 24
 Chromosome - 2 [a][n][a][l][y][t][i][c][s][ ][i][n][d][i][g][ ][ ][m][a][g][a][z][i][n][e] / Fitness = 24
 Chromosome - 3 [a][n][a][l][y][t][i][c][s][ ][i][n][d][i][g][ ][ ][m][a][g][a][z][i][n][e] / Fitness = 24
 Chromosome - 4 [a][n][a][l][y][t][i][c][s][ ][i][n][d][i][g][ ][ ][m][a][g][a][z][i][n][e] / Fitness = 24
 Chromosome - 5 [a][n][a][l][y][t][i][c][s][ ][i][n][d][i][g][ ][ ][m][a][g][a][z][i][n][e] / Fitness = 24
 Chromosome - 6 [a][n][a][l][y][t][i][c][s][ ][i][n][d][i][g][ ][ ][m][a][g][a][z][i][n][e] / Fitness = 24
 Chromosome - 7 [a][n][a][l][y][t][i][c][s][ ][i][n][d][i][t][ ][ ][m][a][g][a][z][i][n][e] / Fitness = 24
 Chromosome - 8 [a][n][a][l][y][t][i][c][s][ ][i][n][d][i][g][ ][ ][m][a][g][a][z][i][n][e] / Fitness = 24
 Chromosome - 9 [a][n][a][l][y][t][i][c][s][ ][i][n][d][i][g][ ][ ][m][a][g][a][z][i][n][e] / Fitness = 24
 Chromosome - 10 [a][n][a][l][y][t][i][c][s][ ][i][n][d][i][g][ ][ ][m][a][g][a][z][i][n][e] / Fitness = 24
 Chromosome - 11 [a][n][a][l][y][t][i][c][s][ ][i][n][d][i][g][ ][ ][m][a][g][a][z][i][n][e] / Fitness = 24
 Chromosome - 12 [a][n][a][l][y][t][i][c][s][ ][i][n][d][i][g][ ][ ][m][a][g][a][z][i][n][e] / Fitness = 24
 Chromosome - 13 [a][n][a][l][y][t][i][c][s][ ][i][n][d][i][g][ ][ ][m][a][g][a][z][i][n][e] / Fitness = 24
 Chromosome - 14 [a][n][a][l][y][t][i][c][s][ ][i][n][d][i][g][ ][ ][m][a][g][a][z][i][n][e] / Fitness = 24
 Chromosome - 15 [a][n][a][l][y][t][i][c][s][ ][i][n][d][i][g][ ][ ][m][a][g][a][z][i][n][e] / Fitness = 24
 Chromosome - 16 [a][n][a][l][y][t][i][c][s][ ][i][n][d][i][g][ ][ ][m][a][g][a][z][i][n][e] / Fitness = 24
 Chromosome - 17 [a][n][a][l][y][t][i][c][s][ ][i][n][d][i][a][ ][ ][m][a][g][e][z][P][n][e] / Fitness = 23
 Chromosome - 18 [a][n][a][l][y][t][i][c][s][ ][i][n][d][i][M][ ][ ][m][a][g][l][z][i][n][e] / Fitness = 23
 Chromosome - 19 [a][n][a][l][y][t][i][c][s][ ][i][n][d][i][g][ ][ ][m][e][g][a][z][i][n][e] / Fitness = 23
 Chromosome - 20 [a][n][a][l][y][t][i][c][s][ ][i][n][d][i][a][ ][ ][m][a][g][e][z][P][n][e] / Fitness = 23
 Chromosome - 21 [C][n][a][l][y][t][i][f][s][ ][i][n][d][i][g][ ][ ][m][a][g][a][z][i][n][e] / Fitness = 22
 Chromosome - 22 [a][n][a][l][y][t][i][c][s][i][i][n][d][i][d][ ][ ][m][a][g][ ][z][i][n][e] / Fitness = 22
 Chromosome - 23 [a][n][a][l][y][t][i][c][s][ ][i][n][d][i][g][ ][ ][m][a][K][z][z][i][n][e] / Fitness = 22
 Chromosome - 24 [a][n][a][l][y][t][i][c][s][ ][i][n][d][i][g][ ][ ][m][a][g][a][M][c][n][e] / Fitness = 22
 Chromosome - 25 [a][n][a][l][y][t][i][c][s][ ][i][n][d][i][g][ ][ ][m][a][g][e][z][P][n][e] / Fitness = 22
 Chromosome - 26 [a][n][a][l][y][t][i][c][s][ ][K][n][d][i][g][ ][ ][k][a][g][H][z][i][n][e] / Fitness = 21
 Chromosome - 27 [a][n][a][l][y][t][r][c][s][ ][i][n][d][I][g][ ][z][m][a][g][a][z][i][n][e] / Fitness = 21
 Chromosome - 28 [a][n][a][l][C][t][g][c][s][ ][O][n][d][i][g][ ][ ][m][a][g][a][z][i][n][e] / Fitness = 21
 Chromosome - 29 [a][n][a][l][y][t][i][c][s][r][i][n][d][i][g][ ][ ][m][a][U][c][z][i][n][e] / Fitness = 21
 Chromosome - 30 [a][n][a][l][s][t][i][c][s][ ][i][n][d][i][g][ ][ ][m][a][u][a][z][i][U][e] / Fitness = 21
 Chromosome - 31 [a][n][a][l][y][P][i][c][s][Z][i][n][d][T][g][ ][ ][m][a][g][a][z][i][n][e] / Fitness = 21
 Chromosome - 32 [a][n][a][l][y][t][i][K][k][ ][i][n][d][i][g][ ][ ][m][Q][g][a][z][i][n][e] / Fitness = 21
 Chromosome - 33 [a][n][a][p][y][t][i][c][s][ ][i][n][d][O][g][ ][ ][m][a][g][a][z][T][n][e] / Fitness = 21
 Chromosome - 34 [a][ ][a][l][y][t][i][c][s][ ][i][n][F][i][g][b][ ][m][a][g][a][z][i][n][e] / Fitness = 21
 Chromosome - 35 [a][n][a][l][y][t][i][K][k][ ][i][n][d][i][g][ ][ ][m][Q][g][a][z][i][n][e] / Fitness = 21
 Chromosome - 36 [a][n][a][l][y][Q][i][c][s][ ][i][D][d][i][M][ ][ ][m][a][g][l][z][i][n][e] / Fitness = 21
 Chromosome - 37 [a][n][a][l][y][t][i][K][k][ ][i][n][d][i][g][ ][ ][m][Q][g][a][z][i][n][e] / Fitness = 21
 Chromosome - 38 [a][n][a][l][y][t][o][c][s][ ][i][n][d][i][t][ ][J][m][R][g][B][z][i][n][e] / Fitness = 20
 Chromosome - 39 [a][n][a][l][y][t][z][c][s][ ][t][n][d][i][M][ ][ ][m][a][g][l][L][i][n][e] / Fitness = 20
 Chromosome - 40 [a][n][a][l][y][ ][i][c][s][ ][i][n][k][J][g][ ][ ][m][a][g][a][z][i][n][C] / Fitness = 20
 Chromosome - 41 [a][n][a][l][f][t][i][c][s][ ][i][n][d][i][J][ ][ ][ ][a][g][a][z][x][h][e] / Fitness = 20
 Chromosome - 42 [a][n][a][l][y][t][i][c][s][ ][i][n][d][i][g][ ][ ][m][a][K][z][M][c][n][e] / Fitness = 20
 Chromosome - 43 [a][n][a][l][y][t][i][c][s][ ][i][n][d][i][g][ ][ ][m][a][K][z][M][c][n][e] / Fitness = 20
 Chromosome - 44 [R][n][a][l][y][t][h][c][F][ ][i][n][d][i][t][f][ ][m][a][g][a][z][L][n][e] / Fitness = 19
 Chromosome - 45 [a][n][a][l][y][t][d][c][s][I][y][ ][g][i][g][ ][ ][ ][a][g][a][z][i][n][e] / Fitness = 18
 Chromosome - 46 [s][n][a][l][y][t][i][c][y][ ][j][d][d][i][g][ ][P][h][a][g][a][z][i][n][e] / Fitness = 18
 Chromosome - 47 [a][n][a][l][y][Q][i][c][U][ ][i][D][d][i][M][b][b][m][a][g][l][z][i][n][e] / Fitness = 18
 Chromosome - 48 [a][n][a][R][J][t][i][c][b][ ][i][n][d][i][g][ ][ ][m][a][g][e][z][y][Z][e] / Fitness = 18
 Chromosome - 49 [a][n][a][l][y][t][i][K][k][ ][Y][n][d][i][g][ ][ ][m][Q][g][a][q][y][n][e] / Fitness = 18
 Best Chromosome : [a][n][a][l][y][t][i][c][s][ ][i][n][d][i][a][ ][ ][m][a][g][a][z][i][n][e]
 Best Fitness    : 25
 Worst Chromosome : [a][n][a][l][y][t][i][K][k][ ][Y][n][d][i][g][ ][ ][m][Q][g][a][q][y][n][e]
 Worst Fitness    : 18

Here in the above, we can see some of the population with their fitness value and the best fit and the worst fit chromosome and a historical graph between generation and fitness.

Here we have seen that in comparison to the old genetic algorithms, this package has made many things easier to perform. It is efficient and easy to use. Also, in some cases, we don’t need to be worried about the deep knowledge of genetic algorithms With a basic knowledge of them we can use this easily in less lines of code. This package has provided most of the things related to genetic algorithms under one roof and made it easy to use all of them.