"Hello world!" Using genetic algorithms

Nowadays, genetic algorithms are becoming increasingly popular. They are used to solve a variety of tasks. Somewhere they work more efficiently than others, somewhere a programmer just decided to show off ...

So what is a genetic algorithm? If you believe Wikipedia, the genetic algorithm is a heuristic search algorithm used to solve optimization and modeling problems by randomly selecting, combining and varying the desired parameters using mechanisms resembling biological evolution. It is a type of evolutionary computation. A distinctive feature of the genetic algorithm is the emphasis on the use of the "crossing" operator, which performs the operation of recombination of candidate solutions, whose role is similar to the role of crossing in living nature.

Those. genetic algorithm works like our evolution with you. Initially, the initial populations are created, then they interbreed with each other (with the possible emergence of mutations). Populations that survived the natural selection process are checked for satisfaction of specified criteria. If they satisfy - everyone is happy, if not - they cross again and so on until final victory.
')
You can see how this all looks in the following image:




As an example, I will give an algorithm that creates the string “Hello world!”

This genetic algorithm has the following parameters:

Population size:	2048
Mutations (%):	25
Elitism (%):	ten

Source

 #include <iostream> // for cout, etc.
 #include <vector> // for class vector
 #include <string> // for string class
 #include <algorithm> // for the sorting algorithm
 #include <time.h> // for random variables
 #include <math.h> // for abs ()

 #define GA_POPSIZE 2048 // Population Size
 #define GA_MAXITER 16384 // maximum number of iterations
 #define GA_ELITRATE 0.10f // Elitism
 #define GA_MUTATIONRATE 0.25f // mutations
 #define GA_MUTATION RAND_MAX * GA_MUTATIONRATE
 #define GA_TARGET std :: string ("Hello world!")

 using namespace std;				

 struct ga_struct 
 {
	 string str;  // line
	 unsigned int fitness;  // suitability
 };

 typedef vector <ga_struct> ga_vector;  // to be short

 void init_population (ga_vector & population,
					  ga_vector & buffer) 
 {
	 int tsize = GA_TARGET.size ();

	 for (int i = 0; i <GA_POPSIZE; i ++) {
		 ga_struct citizen;
		
		 citizen.fitness = 0;
		 citizen.str.erase ();

		 for (int j = 0; j <tsize; j ++)
			 citizen.str + = (rand ()% 90) + 32;

		 population.push_back (citizen);
	 }

	 buffer.resize (GA_POPSIZE);
 }

 void calc_fitness (ga_vector & population)
 {
	 string target = GA_TARGET;
	 int tsize = target.size ();
	 unsigned int fitness;

	 for (int i = 0; i <GA_POPSIZE; i ++) {
		 fitness = 0;
		 for (int j = 0; j <tsize; j ++) {
			 fitness + = abs (int (population [i] .str [j] - target [j]));
		 }
		
		 population [i] .fitness = fitness;
	 }
 }

 bool fitness_sort (ga_struct x, ga_struct y) 
 {return (x.fitness <y.fitness);  }

 inline void sort_by_fitness (ga_vector & population)
 {sort (population.begin (), population.end (), fitness_sort);  }

 void elitism (ga_vector & population, 
				 ga_vector & buffer, int esize)
 {
	 for (int i = 0; i <esize; i ++) {
		 buffer [i] .str = population [i] .str;
		 buffer [i] .fitness = population [i]. fitness;
	 }
 }

 void mutate (ga_struct & member)
 {
	 int tsize = GA_TARGET.size ();
	 int ipos = rand ()% tsize;
	 int delta = (rand ()% 90) + 32; 

	 member.str [ipos] = ((member.str [ipos] + delta)% 122);
 }

 void mate (ga_vector & population, ga_vector & buffer)
 {
	 int esize = GA_POPSIZE * GA_ELITRATE;
	 int tsize = GA_TARGET.size (), spos, i1, i2;

	 elitism (population, buffer, esize);

	 // Mate the rest
	 for (int i = esize; i <GA_POPSIZE; i ++) {
		 i1 = rand ()% (GA_POPSIZE / 2);
		 i2 = rand ()% (GA_POPSIZE / 2);
		 spos = rand ()% tsize;

		 buffer [i] .str = population [i1] .str.substr (0, spos) + 
			             population [i2] .str.substr (spos, esize - spos);

		 if (rand () <GA_MUTATION) mutate (buffer [i]);
	 }
 }

 inline void print_best (ga_vector & gav)
 {cout << "Best:" << gav [0] .str << "(" << gav [0]. fitness << ")" << endl;  }

 inline void swap (ga_vector * & population,
				  ga_vector * & buffer)
 {ga_vector * temp = population;  population = buffer;  buffer = temp;  }

 int main ()
 {
	 srand (unsigned (time (NULL)));

	 ga_vector pop_alpha, pop_beta;
	 ga_vector * population, * buffer;

	 init_population (pop_alpha, pop_beta);
	 population = & pop_alpha;
	 buffer = & pop_beta;

	 for (int i = 0; i <GA_MAXITER; i ++) {
		 calc_fitness (* population);  // calculate suitability
		 sort_by_fitness (* population);  // sort the population
		 print_best (* population);  // display the best population

		 if ((* population) [0] .fitness == 0) break;

		 mate (* population, * buffer);  // mating populations
		 swap (population, buffer);  // clear buffers
	 }

	 return 0;
 }

Just want to give a few comments on the code. First, we cheated when we set the fixed row sizes in the genetic algorithm, which are equal to the size of the required row. This is done to provide a better understanding of the code. Secondly, the STL class vector is used to store data - this is done in order to simplify sorting. Finally, the program uses two arrays to store populations — one for the current, the second as a buffer for the next generation. In each generation, points are rounded to the whole to speed up the calculations.

Determination of suitability
Let's take a look at the function of determining the suitability of a population:
void calc_fitness(ga_vector &population)
{
string target = GA_TARGET;
int tsize = target.size();
unsigned int fitness;

for (int i=0; i<GA_POPSIZE; i++) {
fitness = 0;
for (int j=0; j<tsize; j++) {
fitness += abs(int(population[i].str[j] - target[j]));
}

population[i].fitness = fitness;
}
}


In principle, each member of the population is simply recruited and compared with that in the target line. The differences between the characters are added up and the accumulated amount is used as a value of suitability (so the smaller it is, the better).

Result
When executed, the program displays the best population on the screen and its suitability (the number in brackets).
Best: IQQte=Ygqem# (152)
Best: Crmt`!qrya+6 (148)
Best: 8ufxp+Rigfm* (140)
Best: b`hpf"woljh[ (120)
Best: b`hpf"woljh4 (81)
Best: b`hpf"woljh" (63)
Best: Kdoit!wnsk_! (24)
Best: Kdoit!wnsk_! (24)
Best: Idoit!wnsk_! (22)
Best: Idoit!wnsk_! (22)
Best: Idoit!wnsk_! (22)
Best: Idoit!wnsk_! (22)
Best: Ifknm!vkrlf? (17)
Best: Ifknm!vkrlf? (17)
Best: Gfnio!wnskd$ (14)
Best: Ffnjo!wnskd$ (14)
Best: Hflio!wnskd$ (11)
Best: Hflio!wnskd$ (11)
Best: Kflkn wosld" (8)
Best: Ifmmo workd" (6)
Best: Hfljo wosld" (5)
Best: Hflmo workd" (4)
Best: Hflmo workd" (4)
Best: Hflmo workd" (4)
Best: Iflmo world! (3)
Best: Iflmo world! (3)
Best: Hflmo world! (2)
Best: Hflmo world! (2)
Best: Hflko world! (2)
Best: Hflko world! (2)
Best: Hdllo world! (1)
Best: Hfllo world! (1)
Best: Hfllo world! (1)
Best: Helko world! (1)
Best: Hfllo world! (1)
Best: Hfllo world! (1)
Best: Hfllo world! (1)
Best: Hello world! (0)


Conclusion
I hope this small program is able to demonstrate how a simple genetic algorithm can be used to solve a problem. This algorithm is not the most efficient, although using STL should help a little. The algorithm was tested in Visual Studio.

Application example
To test a trading robot on a range of parameters, it is possible to “pass” a range not in cycles (as it is now in all programs), but using genetic algorithms. And time is reduced by 9-12 times. #

Original article in English.
What is a genetic algorithm?