Natural genetic algorithm or evidence of the evolution of living organisms in C ++

Introduction

Models of natural computing are widely used in modern science. The area of ​​their application is very extensive, they are used to solve problems of modeling, artificial intelligence, pattern recognition, control.

One of the most common methods of natural computation is genetic algorithms. To better understand how these algorithms are designed and how they work, it was decided to reproduce one of these algorithms - the genetic one. In order to apply a method to solve specific problems, this method must be mastered. Therefore, the genetic algorithm considered in this paper does not solve any specific problem. The main ones are at the same time the process and the result of the work on creating a program for modeling and visualizing the work of the genetic algorithm. The programmer's experience is important.
The program models the behavior of a population of the most primitive living organisms. This program is unlikely to have any practical application, but it vividly illustrates the principle of operation of genetic algorithms.

Simulation of the genetic algorithm, in which natural selection is determined by environmental conditions

Modeling is a method of scientific knowledge of the objective world through the construction and study of models.
')
Visualization is one of the most convenient ways for people to present information. It is more convenient for a person to perceive information if it is represented graphically, and not as a large array of meaningless numbers, therefore an important part of the work is a graphical representation of the algorithm.

Before using any method, it must be studied and tested first on a relatively simple task, possibly several times. For a programmer, such a study is writing specific programs.

A C ++ programming language has been chosen for work, since this language is a powerful, time-tested programming language. C ++ is widespread among programmers. For visualization used open graphic library OpenGL.

Goal and tasks

The purpose of the work is to write a program for modeling the work and visualization of a genetic algorithm, in which natural selection is determined depending on environmental conditions.
Tasks

1. To analyze the sources of information.
2. Learn basic concepts related to genetic algorithms.
3. Create a biological species of primitive living organisms.
4. Create a system of interaction of organisms with each other.
5. Organize the life cycle (the birth of new organisms, life expectancy, reproduction and death).
6. Create a driving force of evolution.
7. Organize predator-prey relationships.
8. In conclusion, you need to implement the collection of statistical data on the population.

Creating a view

The program is written in the C ++ programming language using the open graphic library OpenGL.
To represent the species, the Bio class was created, which includes the coordinates, speed, lifetime and other parameters of a primitive living organism.

Bio Fields

public: Code_bio code; //  float x,y,dx,dy; //   bool life; //   float w,h; //  int num; //   int lifetime; //  float range; //   

The Bio class provides a constructor (for creating class objects).

 Bio(void) { life=1; // w=20; //   h=20; num=rand()%10000; range=200; //srand(time(0)); //  x=rand()%(winW-(int)w); y=rand()%(winH-(int)h); //srand(time(0)); dx=rand()%8-4; //  dy=rand()%8-4; lifetime=0; } 

In addition to the constructor, you must create a function set (int a, int b), with which you can manually set the coordinates of the object being created.

 void set(int a,int b){ x=a; y=b; life=true; dx=rand()%8-4; dy=rand()%8-4; } 

To simulate a random movement, we introduce the turn () function, which will rotate an object at a random angle to the left or right at each instant of time.

 inline void turn(float vect, int deg) { if((dx!=0)||(dy!=0)) { float grad; if((dx>=0)&&(dy<0)) { dy=-dy; grad=atan(dx/dy)*180/pi; grad+=deg; dx=sin(grad*pi/180)*vect; dy=cos(grad*pi/180)*vect; dy=-dy; } if((dx>=0)&&(dy>=0)) { grad=atan(dx/dy)*180/pi; grad=90-grad; grad+=deg; grad=90-grad; dx=sin(grad*pi/180)*vect; dy=cos(grad*pi/180)*vect; } if((dx<0)&&(dy<=0)) { dy=-dy; dx=-dx; grad=atan(dx/dy)*180/pi; grad=90-grad; grad+=deg; grad=90-grad; dx=sin(grad*pi/180)*vect; dy=cos(grad*pi/180)*vect; dy=-dy; dx=-dx; } if((dx<0)&&(dy>=0)) { dx=-dx; grad=atan(dx/dy)*180/pi; grad+=deg; dx=sin(grad*pi/180)*vect; dy=cos(grad*pi/180)*vect; dx=-dx; } } } 

To handle the collision of an object with the edges of the screen, the collx () and colly () functions are needed.

 inline void collx() { if(xw/2<0) { x=winW-w/2; } if(x+w/2>winW) { x=w/2; } } inline void colly() { if(yh/2<0) { y=h/2; dy=-dy; } if(y+h/2>winH) { y=winH-h/2; dy=-dy; } } }; 

Now we need only the main function Draw (), which will change the state of the object and draw it.

 void Bio::Draw() { if(life) { if(dx==0)dx=rand()%30/10+1; if(dy==0)dy=rand()%30/10+1; // float min=range; bool ok=0; float x2,y2; list<Predator>::iterator i=preds.begin(); for(;i!=preds.end();i++) { if(sqrt( (xi->x)*(xi->x)+(yi->y)*(yi->y) )<min) { min=sqrt( (xi->x)*(xi->x)+(yi->y)*(yi->y) ); ok=1; x2=i->x; y2=i->y; } } if(ok) { runaway(code.maxspeed,x2,y2); turn(code.maxspeed,(rand()%(2*(int)code.maxturn+1)*10)/10-(int)code.maxturn); } else turn((rand()%(int)(code.maxspeed-code.minspeed+1)*10)/10+code.minspeed, (rand()%(2*(int)code.maxturn+1)*10)/10-(int)code.maxturn); x+=dx; collx(); y+=dy; colly(); // if(1) { glBindTexture(GL_TEXTURE_2D,bio_tex[0]); glBegin(GL_QUADS); glTexCoord2f(0,1); glVertex2f(xw/2,yh/2); glTexCoord2f(1,1); glVertex2f(x+w/2,yh/2); glTexCoord2f(1,0); glVertex2f(x+w/2,y+h/2); glTexCoord2f(0,0); glVertex2f(xw/2,y+h/2); glEnd(); } // makechild(); //.  lifetime++; if(lifetime>code.maxltime) life=0; // w=lifetime/40+20; h=lifetime/40+20; } } 

At the creation of the species ends. Now the question arises about the storage of all these organisms (after all, there will be a large number of them). Their number will also constantly change as a result of the life cycle. A dynamic list array is well suited for storing them.

 list<Bio> bios; 

Life cycle

As a result, the first task is completed. Next you need to organize the life cycle of the population and the interaction of organisms with each other. Since the program must simulate the behavior of the most primitive organisms, their relationships will be the simplest. When two individuals collide, they will die, and their children will appear in random coordinates (from 1 to 3). Given the computing resources of a regular computer, the program will be able to process up to 200 organisms at a normal speed. This number is not sufficient for the existence of a stable population, so that the number of organisms does not become too large or too small a condition is introduced - if the population size is less than 50, more children are born (from 1 to 4), if the number is more than 50, reproduction will be slower.

In order for the genetic algorithm to work, each individual of the population must have its own genetic code. For this, a separate code structure has been created in the program. Each organism of the population has its own copy of this structure. A cross-breeding function is also needed, which will accept the genetic codes of the parents and return the baby’s code. These primitive creatures in the code have only the minimum and maximum speeds, the maximum lifespan and the maximum angle of rotation.

 struct Code_bio { int maxltime; float minspeed,maxspeed; int maxturn; }; inline Code_bio childcode(Code_bio c1, Code_bio c2) { // Code_bio c; c.maxltime=(c1.maxltime+c2.maxltime)/2; c.minspeed=(c1.minspeed+c2.minspeed)/2; c.maxspeed=(c1.maxspeed+c2.maxspeed)/2; c.maxturn=(c1.maxturn+c2.maxturn)/2; // c.maxltime+=c.maxltime/100*((rand()%(maxltime_mut*2+1))-maxltime_mut); c.maxspeed+=c.maxspeed/100*((rand()%(maxspeed_mut*2+1))-maxspeed_mut); c.minspeed+=c.minspeed/100*((rand()%(minspeed_mut*2+1))-minspeed_mut); c.maxturn+=c.maxturn/100*(rand()%(maxturn_mut*2+1)-maxturn_mut); return c; } 

In the Bio class you now need to add a breeding function. This feature will detect the collision of organisms, kill them and create offspring.

 void Bio::makechild() { list<Bio>::iterator i=bios.begin(); for(;i!=bios.end();i++) { if(num!=i->num) { if((lifetime>200)&&(i->lifetime>200)) if(sqrt((xi->x)*(xi->x))+((yi->y)*(yi->y))<w+i->w) { life=0; i->life=0; int c; if(bios.size()<50) c=rand()%4+1; else c=rand()%3+1; for(int j=0;j<c;j++) { Bio b; b.code=childcode(code,i->code); bios.push_back(b); } } } } } 

In the drawing function, you also need to make a change: add reproduction. All objects are drawn in the timer function with an interval of 20 ms. In the same function, the program deletes all dead individuals (whose value of life is false).

 list<Bio>::iterator i=bios.begin(); for(;i!=bios.end();i++) i->Draw(); bios.remove_if([](Bio b) {return (b.life==0);}); //  

Predator

Since the genetic algorithm still has to solve some problem, you need to set this task to it. In this case, the task will be to find the most fit organism. The population will be improved all the time as a result of evolution. Each next generation will be better adapted to environmental conditions. It is necessary to create a driving factor of evolution, which will select the most adapted individuals. This factor will be a predator.

Predators, as well as victims, can be many. The predator class from the Bio class will differ only in that the predators will not be able to breed and die. Their number will always be fixed throughout the program.

Predator Class Fields

 public: float x,y,dx,dy,speed; bool life; float w,h; int num; int lifetime; float range; float hungry; 

The default constructor and the set () function for manual creation.

 Predator(void) { life=1; w=100; h=100; num=rand()%10000; range=250; speed=10.2; hungry=0;//1*1000/20; //srand(time(0)); x=rand()%(winW-(int)w); y=rand()%(winH-(int)h); //srand(time(0)); dx=rand()%8-4; dy=rand()%8-4; lifetime=0; } void set(int a,int b) { x=a; y=b; life=true; dx=rand()%8-4; dy=rand()%8-4; } 

In the free time from eating the predator will make a random movement. Its turn () function for changing directions is no different from the similar method of class Bio. In order for the predator to catch up with the prey, it needs the aim () function, which will accept the coordinates of the victim and the speed with which it must be caught up.

 inline void aim(float vect, float x2, float y2) { dx=((x2-x)*vect)/sqrt( (x-x2)*(x-x2)+(y-y2)*(y-y2) ); dy=((y2-y)*vect)/sqrt( (x-x2)*(x-x2)+(y-y2)*(y-y2) ); } 

In the main function Draw (), if a predator is hungry, he will look through his surroundings, find the nearest victim and chase after it. If he is not hungry, he will randomly move around the screen.

 inline void Draw() { if(life) { if(dx==0)dx=rand()%30/10+1; if(dy==0)dy=rand()%30/10+1; //  bool ok=0; float x2,y2; if(hungry<=0) { float min=range; list<Bio>::iterator i=bios.begin(); for(;i!=bios.end();i++) { if(sqrt( (xi->x)*(xi->x)+(yi->y)*(yi->y) )<w/2+i->w/2-10) { i->life=0; hungry=0.01*1000/20; } else if(sqrt( (xi->x)*(xi->x)+(yi->y)*(yi->y) )<min) { min=sqrt( (xi->x)*(xi->x)+(yi->y)*(yi->y) ); ok=1; x2=i->x; y2=i->y; } } } if(ok) aim(speed,x2,y2); else turn(6,(rand()%(2*15+1)*10)/10-15); x+=dx; collx(); y+=dy; colly(); // if(view) { glBindTexture(GL_TEXTURE_2D,pred_tex[0]); glBegin(GL_QUADS); glTexCoord2f(0,1); glVertex2f(xw/2,yh/2); glTexCoord2f(1,1); glVertex2f(x+w/2,yh/2); glTexCoord2f(1,0); glVertex2f(x+w/2,y+h/2); glTexCoord2f(0,0); glVertex2f(xw/2,y+h/2); glEnd(); } //.  // // hungry--; } } 

It remains only to create a dynamic array of predators.

 list<Predator> preds; 

Predator-Prey Relationship

In order for the relationship between the predator and the victim to work properly, you need to teach the victim to run away from the predator. Otherwise, the predator will simply eat the prey and no evolution will occur. To do this, add the runaway () method to the Bio class. It is similar to the method of pursuit by the predator of the victim, only directs the object in the opposite direction.

 inline void runaway(float vect, float x2, float y2) { dx=((x-x2)*vect)/sqrt( (x-x2)*(x-x2)+(y-y2)*(y-y2) ); dy=((y-y2)*vect)/sqrt( (x-x2)*(x-x2)+(y-y2)*(y-y2) ); } 

Now we need to finally modify the Draw function of the Bio class. In addition to the simple chaotic movement, it is necessary to add the detection of a predator and escape from it.

 if(dx==0)dx=rand()%30/10+1; if(dy==0)dy=rand()%30/10+1; // float min=range; bool ok=0; float x2,y2; list<Predator>::iterator i=preds.begin(); for(;i!=preds.end();i++) { if(sqrt( (xi->x)*(xi->x)+(yi->y)*(yi->y) )<min) { min=sqrt( (xi->x)*(xi->x)+(yi->y)*(yi->y) ); ok=1; x2=i->x; y2=i->y; } } if(ok) runaway(code.maxspeed,x2,y2); else turn((rand()%(int)(code.maxspeed-code.minspeed+1)*10)/10+code.minspeed, (rand()%(2*code.maxturn+1)*10)/10-code.maxturn); 

The likelihood of a prey catching a fast prey is less than the likelihood of catching a slow one. As a result, fast individuals will be better adapted to environmental conditions, and an increase in the average population rate will gradually be observed.

Principle of evolution

For evolution to work, it was necessary to add a few more important points. When the predator begins to pursue the prey, the prey runs away from it in the opposite direction. If the speed of the prey is much less than the speed of the predator, then evolution will not occur, because then with minor evolutionary changes in its speed, the predator will still catch up and eat the prey. If the speed of the victim is greater than the speed of the predator, it will not be able to catch up with it, unless it drives into the corner. Only one option remains: the speed of the prey should be approximately equal to the speed of the predator. Then, even with the smallest evolutionary change in the speed of the victim, it will have a significant advantage over the others. A predator will be less likely to catch up with such a prey.

When the program creates an initial population, it sets all individuals the same genotypes, which show the same maximum and minimum speeds. All parameters of the genotypes of offspring are calculated as the arithmetic average of the parameters of the parents. For example, the child’s maximum speed will be the average of the average speeds of the parents. If the genetic algorithm is launched exactly this way, evolution will not work. All genotypes will simply be averaged and become the same. Even if the initial population is created with different genotypes, there will be no evolution anyway. In addition to natural selection and the driving factor for the evolution of a tedious mutation. All you need is to calculate it by plus / minus 10% after calculating the arithmetic average. Then, some individuals as a result of crossing will be born faster, and some - more slowly, and evolution will work.

During operation, the program once every 10 seconds records in four files the general population indicators: abundance, average, minimum and maximum speeds. Using this data, it will be possible to see the result of the genetic algorithm and draw a conclusion about the evolution of the population.

Fragment of data collected:

Min. Number Speed ​​max Speed, Wed. speed:
45.00 1,01842 9,83393 5,42617
54.00 1,01048 10,214 5.61252
53.00 1.00726 10.4374 5.72231
51.00 0.932109 10.1463 5.53921
48.00 0.93236 10.6849 5.80864
45.00 0.908688 11.0295 5.96907
46.00 0.888795 11.1242 6.0065
51.00 0.894669 11.1927 6.04366
48.00 0.933062 11.679 6.30601
52.00 0.92753 11.9278 6.42764
54.00 0.899226 12.3086 6.6039
51.00 0.875113 12.52 6.69756
43.00 0.902515 12.84 6.87124

Based on these data, the construction of the graph is performed:



The graph shows that as a result of evolution, the average maximum speed of all organisms increased 10 times. This is really a huge leap in the evolution of organisms. From this graph, we can also conclude that the average minimum velocity of all organisms has not changed. This is due to the peculiarities of the movement of creatures. At a time when they do not run away from a predator, they simply run around the screen in random directions. Moreover, their speed is also subject to random change. It takes a random value between their minimum possible speed, embedded in the genotype, and the maximum possible speed, also embedded in the genotype. But when these organisms run away from the enemy, they run at their highest possible speed. That is why the driving factor of evolution, which makes the selection of the most adapted individuals, changes only their maximum possible speeds, as the graph shows.

Results and conclusions

1. Created an artificial biological species for the genetic algorithm.
2. Created a system of interaction of organisms with each other.
3. Organized life cycle (the birth of new organisms, life expectancy, reproduction and death).
4. A predator has been created as a driving factor for evolution.
5. The interaction of predator and prey is organized.
6. An example of statistical data was collected, which clearly demonstrates the operation of the algorithm and proves the evolution of the created population.

At the bottom left is a predator.

Conclusion

The created program meets all stated requirements. At first glance, it does not perform any specific socially useful task, but it clearly demonstrates the principle of operation of the genetic algorithm. The algorithm implemented in this program is quite simple, but without understanding how it works, it is impossible to create a more complex genetic algorithm.

Literature

1. N. Ershov. Natural Models of Parallel Computations [Electronic resource] URL: naturalmodels.blogspot.ru (circulation date 05/10/14 ).
2. R. Laforé “Object-Oriented Programming in C ++”, 4th edition, 2011.
3. B. I. Pakhomov "C / C ++ and MS Visual C ++ 2012".