Natural genetic algorithm or evidence of the evolution of living organisms in C ++
Introduction
Natural computing models are widely used in modern science. The scope 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 computing is genetic algorithms. To better understand how these algorithms are structured and how they work, it was decided to reproduce one of such algorithms - genetic. 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 both the process and the result of creating a program for modeling and visualizing the work of the genetic algorithm. The programmer experience gained is important.
The program models the behavior of the population of the most primitive living organisms. This program is unlikely to have any practical application, but it clearly illustrates the principle of genetic algorithms.
Modeling the operation of a 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 a person to present information. It is more convenient for a person to perceive information if it is represented graphically, and not in the form of a large array of meaningless numbers, therefore, an important part of the work is the 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.
The C ++ programming language was chosen for work, since this language is a powerful, time-tested programming language. C ++ is widespread among programmers. For visualization, the OpenGL open graphics library is used.
Goal and tasks
The purpose of the work is to write a program for modeling work and visualizing a genetic algorithm in which natural selection is determined depending on environmental conditions.
Tasks
- To analyze the sources of information.
- Learn basic concepts related to genetic algorithms
- Create a biological species of primitive living organisms.
- Create a system of interaction of organisms with each other.
- Organize the life cycle (the birth of new organisms, life expectancy, reproduction and death).
- Create a driving factor in evolution.
- Establish a predator-prey relationship.
- In conclusion, you need to implement the collection of statistical data on the population.
Create view
The program is written in the C ++ programming language using the OpenGL open graphics library.
To represent the biological species, the Bio class was created, which includes the coordinates, speed, lifetime and other parameters of a primitive living organism.
Bio Class 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, it is necessary to create a set (int a, int b) function, with which you can manually set the coordinates of the created object.
void set(int a,int b){
x=a;
y=b;
life=true;
dx=rand()%8-4;
dy=rand()%8-4;
}
To simulate random movement, we introduce the turn () function, which will rotate the object at a random angle to the left or right at any 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;
}
}
}
The collx () and colly () functions are needed to handle the collision of an object with the edges of the screen.
inline void collx()
{
if(x-w/2<0)
{
x=winW-w/2;
}
if(x+w/2>winW)
{
x=w/2;
}
}
inline void colly()
{
if(y-h/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::iterator i=preds.begin();
for(;i!=preds.end();i++)
{
if(sqrt( (x-i->x)*(x-i->x)+(y-i->y)*(y-i->y) )x)*(x-i->x)+(y-i->y)*(y-i->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(x-w/2,y-h/2);
glTexCoord2f(1,1); glVertex2f(x+w/2,y-h/2);
glTexCoord2f(1,0); glVertex2f(x+w/2,y+h/2);
glTexCoord2f(0,0); glVertex2f(x-w/2,y+h/2);
glEnd();
}
//ДЕТИ
makechild();
//ПРОД. ЖИЗНИ
lifetime++;
if(lifetime>code.maxltime)
life=0;
//РОСТ
w=lifetime/40+20;
h=lifetime/40+20;
}
}
This ends the creation of the view. Now the question arises about the storage of all these organisms (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 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 should 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 conventional computer, the program will be able to process up to 200 organisms with normal speed. This amount is not enough for a stable population to exist, so that the number of organisms does not become too large or too small, the condition is introduced - if the population 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 in 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 instance of this structure. A crossover function is also needed that will accept the parental genetic codes and return the baby's code. For these primitive creatures, the code contains only the minimum and maximum speeds, maximum life expectancy and 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 now you need to add the reproduction function. This function will detect collisions of organisms, kill them and create offspring.
void Bio::makechild()
{
list::iterator i=bios.begin();
for(;i!=bios.end();i++)
{
if(num!=i->num)
{
if((lifetime>200)&&(i->lifetime>200))
if(sqrt((x-i->x)*(x-i->x))+((y-i->y)*(y-i->y))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;jcode);
bios.push_back(b);
}
}
}
}
}
In the rendering 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 life value is false).
list::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 it this task. In this case, the task will be to find the most adapted organism. The population will continue to improve 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, like 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;
Default constructor and 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 his free time, the predator will make a random movement. Its turn () function for changing direction is no different from a similar method of the Bio class. In order for the predator to catch up with the prey, he needs the aim () function, which will take the coordinates of the prey and the speed with which it needs to catch 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 Draw () function, if the predator is hungry, it will look at its environment, find the nearest prey and chase after it. If he is not hungry, he will accidentally 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::iterator i=bios.begin();
for(;i!=bios.end();i++)
{
if(sqrt( (x-i->x)*(x-i->x)+(y-i->y)*(y-i->y) )w/2-10)
{
i->life=0;
hungry=0.01*1000/20;
}
else
if(sqrt( (x-i->x)*(x-i->x)+(y-i->y)*(y-i->y) )x)*(x-i->x)+(y-i->y)*(y-i->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(x-w/2,y-h/2);
glTexCoord2f(1,1); glVertex2f(x+w/2,y-h/2);
glTexCoord2f(1,0); glVertex2f(x+w/2,y+h/2);
glTexCoord2f(0,0); glVertex2f(x-w/2,y+h/2);
glEnd();
}
//ПРОД. ЖИЗНИ
//РОСТ
//ГОЛОД
hungry--;
}
}
It remains only to create a dynamic array of predators.
list preds;
Predator-Prey Relationship
In order for the relationship between the predator and the prey to work correctly, you need to teach the prey to escape 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 a predator of a 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 a simple chaotic movement, it is necessary to add the detection of a predator and flight 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::iterator i=preds.begin();
for(;i!=preds.end();i++)
{
if(sqrt( (x-i->x)*(x-i->x)+(y-i->y)*(y-i->y) )x)*(x-i->x)+(y-i->y)*(y-i->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 predator’s likelihood of catching a quick prey is less than the probability of catching a slow prey. As a result of this, fast individuals will be better adapted to environmental conditions, and an increase in the average population speed will gradually be observed.
The principle of evolution
In order for evolution to work, it was necessary to introduce several more important points. When a predator begins to pursue a prey, the prey runs away from him in the opposite direction. If the victim’s speed is much lower 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 victim. If the speed of the victim is greater than the speed of the predator, he will not be able to catch up with it, unless it is driven into a 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 victim’s speed, she will have a significant advantage over the others. A predator will have less chance of catching such a prey.
When a program creates an initial population, it sets all individuals the same genotypes, which indicate the same maximum and minimum speeds. All parameters of the progeny genotypes are calculated as the arithmetic mean of the parameters of the parents. For example, the maximum speed of the child will be the arithmetic average of the average speeds of the parents. If the genetic algorithm is run this way, evolution will not work. All genotypes simply average and become the same. Even if you create an initial population with different genotypes, there will still be no evolution. In addition to natural selection and a driving factor for evolution, a mutation is tedious. All that is needed is, after calculating the arithmetic mean, change it to plus / minus 10%. Then some individuals as a result of crossing will be born faster, and some - slower,
During operation, the program writes the total population indicators in four files every 10 seconds: size, average, minimum and maximum speeds. Using these data, it will be possible to see the result of the genetic algorithm and make a conclusion about the evolution of the population.
Fragment of the collected data:
Number, Min. Speed Max Speed, Avg. 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 graph is constructed:
The graph shows that as a result of evolution, the average maximum speed of all organisms increased 10 times. This is truly a colossal leap in the evolution of organisms. From this graph, we can also conclude that the average minimum speed of all organisms has not changed. This is due to the characteristics of the movement of creatures. While they are not running away from a predator, they are simply running around the screen in random directions. However, their speed is also subject to random changes. 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 flee from the enemy, they flee at their highest possible speed. That is why the driving factor in evolution, which selects the fittest individuals,
Results and Conclusions
- An artificial biological species was created for the operation of the genetic algorithm.
- A system of interaction of organisms with each other has been created.
- The life cycle is organized (the birth of new organisms, life expectancy, reproduction and death).
- A predator has been created as a driving factor in evolution.
- The interaction of a predator and a prey is organized.
- An example of statistical data is 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 the stated requirements. At first glance, it does not perform any specific socially useful task, but it clearly demonstrates the principle 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. Ershov N. M. Natural models of parallel computing [Electronic resource] URL: naturalmodels.blogspot.ru (accessed 05/10/14).
2. R. Laforet “Object-oriented programming in C ++”, 4th edition, 2011.
3. B. I. Pakhomov “C / C ++ and MS Visual C ++ 2012”.