Neural Network Driven Evolution
Let's look at the environment: particles of “food” and agents can exist in it. Using sensors, agents can obtain information about the environment. If the agent is close enough to a particle of food, then it is considered to be “eaten” and disappears, and at the same moment a new particle of food appears in a random place in the environment. The task of a group of agents is to collect food. Efficiency is considered based on the total amount of food collected.
Let's simulate a competitive environment to automatically search for the optimal behavior of a group of agents. We will construct an agent behavior algorithm in the form of a neural network.
To simulate a competitive environment, you can use the genetic algorithm and conduct tournaments: all agents are assigned a neural network of a certain configuration (the “brain”) and after a certain period of time the number of eaten food particles is fixed. Those neural networks are won, under whose control agents were able to collect more food - on their basis a new population of neural networks is formed, etc.
Of course, there are specialized algorithms for training neural networks, but I used the genetic algorithm, because:
The medium is characterized by size (width and height), as well as the number of agents and particles of food. The environment is closed - agents cannot go beyond it.
Food particles are characterized by coordinates (x, y).
Each agent is characterized by a position (x, y) and a direction vector.
Agent sensors receive the following indicators from the environment: a signal about the presence of food nearby, a distance to a food particle, the cosine of the angle between the direction vector of the agent and the vector directed to food, a signal about the presence of other agents nearby (and, accordingly, the distance and cosine of the angle between the direction of our agent and vector directed to another agent). The agent’s ability to receive information about the environment is limited by the “scope” - roughly speaking, the agent can only see ahead of itself.
The agent interacts with the environment by changing its own position and direction. That is, the indicators of sensors are fed to the input of the neural network, and the value of the angle by which it is necessary to turn, as well as the value of the value by which the agent's speed should be changed, are read out.
For convenience, a neural network can be transformed into a linear form. For this, it is enough to write all the parameters of a neural network into a one-dimensional array. The parameters include the weights of the bonds, as well as the type and parameters of the transition functions of neurons. The operations of crossing and mutation of linear chromosomes are quite simple.
We will observe the agents in an environment with dimensions of 600 x 400, but to speed up the calculations, tournament competitions are held in an environment with more compact parameters: the dimensions of the environment are 200 x 200, the number of agents is 10, the number of food particles is 5. A
neural network of the optimal configuration is enough quickly. In the video, you can observe how the behavior of agents changes as a result of tournament selections (if you look at YouTube, the image will look a little clearer):
Here are the neural network configuration files that I used in the demo videos.
The emulator is equipped with a simple graphical interface. By clicking the left mouse button, you can add food, and by clicking the right button - new agents.
The architecture of the main components of the application is as follows: The
genetic algorithm is executed in a separate thread, and upon its completion, a new configuration of the neural network is established for all agents, which entails a change in the behavior of the agents on the screen. The configuration of the neural network can be saved - the xml format is quite convenient for this.
The use of a genetic algorithm for training a small neural network was successful.
When working on such a small task, you get a lot of pleasure: it is very interesting to observe the evolution and collective behavior of artificial creatures.
Let's simulate a competitive environment to automatically search for the optimal behavior of a group of agents. We will construct an agent behavior algorithm in the form of a neural network.
To simulate a competitive environment, you can use the genetic algorithm and conduct tournaments: all agents are assigned a neural network of a certain configuration (the “brain”) and after a certain period of time the number of eaten food particles is fixed. Those neural networks are won, under whose control agents were able to collect more food - on their basis a new population of neural networks is formed, etc.
Of course, there are specialized algorithms for training neural networks, but I used the genetic algorithm, because:
- I didn’t want to limit myself to the specific topology of the neural network (if more objectively, this is due to the lack of theoretical prerequisites as to which network topology and number of neurons are best used in this case)
- I wanted to test the possibility of using a genetic algorithm for training a neural network
- reused the implementation of the genetic algorithm that he created to solve another problem
Let's look at the details of our model
The medium is characterized by size (width and height), as well as the number of agents and particles of food. The environment is closed - agents cannot go beyond it.
Food particles are characterized by coordinates (x, y).
Each agent is characterized by a position (x, y) and a direction vector.
Agent sensors receive the following indicators from the environment: a signal about the presence of food nearby, a distance to a food particle, the cosine of the angle between the direction vector of the agent and the vector directed to food, a signal about the presence of other agents nearby (and, accordingly, the distance and cosine of the angle between the direction of our agent and vector directed to another agent). The agent’s ability to receive information about the environment is limited by the “scope” - roughly speaking, the agent can only see ahead of itself.
The agent interacts with the environment by changing its own position and direction. That is, the indicators of sensors are fed to the input of the neural network, and the value of the angle by which it is necessary to turn, as well as the value of the value by which the agent's speed should be changed, are read out.
Genetic operations on a neural network
For convenience, a neural network can be transformed into a linear form. For this, it is enough to write all the parameters of a neural network into a one-dimensional array. The parameters include the weights of the bonds, as well as the type and parameters of the transition functions of neurons. The operations of crossing and mutation of linear chromosomes are quite simple.
Model in action
We will observe the agents in an environment with dimensions of 600 x 400, but to speed up the calculations, tournament competitions are held in an environment with more compact parameters: the dimensions of the environment are 200 x 200, the number of agents is 10, the number of food particles is 5. A
neural network of the optimal configuration is enough quickly. In the video, you can observe how the behavior of agents changes as a result of tournament selections (if you look at YouTube, the image will look a little clearer):
Interesting observations
- The environment can be complicated by allowing particles of food to move. It is interesting that the neural networks obtained for an environment with static food particles show good results in an environment where food can move (at the end of the video I demonstrated moving food particles).
- The environment in which the agents operate is partially observable (agents can only see in front of themselves, and cannot see the position of all environmental objects at the same time).
Also, the environment is non-deterministic (food particles can appear in random places and move in different directions).
But as a result of the “evolution”, quite often, such configurations of neural networks are formed that during the movement to the target “force” the agent to “turn around” (this can also be seen in the video). This behavior is effective because there is always the possibility that while the agent is approaching the target, some other agent may eat this particle of food, or a new piece of food will appear on the way to the target, which can be eaten faster.
To summarize, those neural networks that help fight environmental restrictions are more effective.
- Generally speaking, observing the behavior of agents, sometimes one gets the impression that they behave quite “naturally” - like a group of some bugs or fish.
I implemented the ability to save the configuration of a neural network to a file, and the following video is a demonstration of the various behavioral strategies that I observed:
If you want to experiment
- You must have the Java runtime installed
- Emulator can be downloaded from here.
- Emulator Zapuk:
java -jar simulator.jar
Here are the neural network configuration files that I used in the demo videos.
The emulator is equipped with a simple graphical interface. By clicking the left mouse button, you can add food, and by clicking the right button - new agents.
Technical details
The architecture of the main components of the application is as follows: The
genetic algorithm is executed in a separate thread, and upon its completion, a new configuration of the neural network is established for all agents, which entails a change in the behavior of the agents on the screen. The configuration of the neural network can be saved - the xml format is quite convenient for this.
Instead of a conclusion
The use of a genetic algorithm for training a small neural network was successful.
When working on such a small task, you get a lot of pleasure: it is very interesting to observe the evolution and collective behavior of artificial creatures.
References
- In this, you can read about the agent-based approach to creating intelligent systems, about various environmental options and decision-making strategies:
Stuart J. Russell, Peter Norvig, Artificial Intelligence: A Modern Approach (available in translation) - Github project sources
- Generic implementation of the genetic algorithm - source