EMAS algorithm - ParaPhraseAGH/erlang-emas GitHub Wiki
Evolutionary Multi-Agent System (EMAS) is a computational paradigm proposed by prof. Krzysztof Cetnarowicz and developed at AGH University of Science and Technology in Kraków, Poland. EMAS is an even mix of an evolutionary algorithm and multi-agent system. It is built around the concept that the evolution process takes place in a multi-agent environment, where individuals mate, die, reproduce etc.
The algorithm is designed to work without keeping any global knowledge. Agents are autonomous and capable of making their own decisions concerning their future activities. This feature makes the algorithm more scalable and enables easy parallelisation. It also makes the program often asynchronous, because each agent operates and evolves in his own pace.
Inheritance and selection, which are the two main components of evolutionary algorithms, are implemented by the phenomena of death and reproduction. Best agents in a population are preserved and allowed to produce offspring, while the worst are permanently removed from the environment. This forces the population to evolve and improves general fitness over time.
More detailed and thoroughgoing description of the algorithm can be found on the website of the Age project.
Agent
In order to understand the EMAS algorithm, one first has to familiarise with the concept of an agent. In our implementation agents consist of three things:
- solution
- fitness
- energy
Solution is the genotype of an agent. It represents a single answer to the problem being solved and is the basis for computing fitness. Solution is the attribute which is inherited throughout reproductions and undergoes mutations during the process of evolution. It is the fundamental component of an agent, provides a basis for other elements and remains constant throughout the whole algorithm execution.
The second attribute is fitness, which is a number representing the quality of the solution. Better solutions have better fitness value and are more likely to be chosen for reproduction. The value itself is computed directly from the solution attribute after the agent's creation. Fitness is naturally also constant during the program execution.
The last attribute is responsible for the emergence of selective pressure. Due to the lack of global knowledge and autonomy of agents, it is impossible to evaluate all agents at the same time and evolution process runs asynchronously between them. In such a situation selection mechanisms known from classical evolutionary computation cannot be used, and there is a need for a different approach to this matter.
This is the reason for introducing energy. This attribute can be described as a state of an agent and is responsible for differencing bad solutions from the good ones. During the agent interactions they can lose or gain energy depending on the quality of their solutions. "Good" agents are more likely to gather large quantities of energy at the expense of their peers with worse solutions, although the total amount of energy in the system is constant.
Because the agents in EMAS are completely autonomous, they make decisions concerning their behaviour single-handedly based on their energy level. If the number exceeds a certain threshold, they decide to reproduce and when it reaches zero the agent dies. We can represent the general agent behaviour with this fragment of code:
behaviour(Agent) when Agent#agent.energy == 0 ->
death
behaviour(Agent) when Agent#agent.energy > reproductionThreshold() ->
reproduction
behaviour(Agent) ->
fight
Agent interactions
There are three possible actions an agent can undertake (excluding migration):
- death
- reproduction
- fight
Death is an equivalent of removing an agent from the population. It usually means either terminating the agent's process or deleting an object from a data structure.
Reproduction is the process of creating new agents. It needs either one or two parents to occur, and results in one or two newborn agents respectively. As previously stated, solution and fitness attributes are constant during the lifespan of an agent, so parents are returned unchanged with the exception of a decrease in energy level. This drop is required to provide children with some amount of initial energy necessary to avoid death in the next generation (what would certainly happen if the agent was born with energy = 0). Solutions of newborns are computed by randomly mixing their parents' genotypes and afterwards their fitness can be computed.
Fighting is an action responsible for exchanging the energy. Thanks to it, better agents can drain energy from their peers with worse solutions, thereby creating a selective pressure on the environment. The action is nothing more than a fitness comparison and an energy transfer as a result. It is a very fast way for comparing different solutions and rewarding better ones.
As one can see, no energy is lost or generated during the interactions. Its overall amount is constant during the whole program execution, which can be helpful in e.g. testing or debugging.
Evolution process
Although the evolution process is nominally asynchronous, we can apply a certain scheme to the behaviour of the population which is shown below.
- Tag
- Group
- Work (Fight/Reproduce/Death)
- Shuffle
First step of the algorithm is to decide what action should the agents undertake. As previously stated, there is no global knowledge of the population and the decisions are based purely on agents' states and chance. All actors are "tagged" with the interaction that they are planning to perform, which is necessary for the next step of the algorithm.
Afterwards agents are divided into three groups for each different action. Depending on the implementation model it can be done differently, but the intention is to enable them to interact with each other, because agents themselves do not have any knowledge about their peers and their plans.
Subsequently, all the actions are carried out. These interactions are completely independent, and can be parallelised if necessary. Although it should be noted that the complexity of computations between them may vary very significantly. The death of agents, for instance, is usually very fast, while reproduction can be computationally particularly demanding.
Finally new agents are gathered and the population needs to be shuffled. This process is performed in order to reduce the probability of agents interacting with the same peers during consecutive program iterations. It would have a disadvantageous influence on the variety of developed solutions and may result in miscellaneous patterns in the program behaviour.
This concludes the algorithm iteration and creates a new generation of agents. The whole process is repeated infinitely causing the population to evolve and may be stopped on demand after a certain time, a fixed number of cycles or when the program hits the desired fitness value.
Population and islands
Population is simply a collection of agents. Its initial size is parameterised and varies during program execution. All the interactions between agents happen strictly inside the population just as in most evolutionary algorithms. During a single program execution we can create several different populations called islands, evolving independently at the same time. It is similar to evaluating the algorithm several times one after another and choosing the best answer, although we can significantly improve the overall score by the synergy of all these simultaneous executions.
By design, all populations explore different parts of the search space. Through introducing migration between different islands, we are able to export some solutions from one group to another, which has a positive effect on overall performance. Good solutions developed in one population can be introduced to another and mixed with the local "species". That way we may create agents combining properties from both islands, possibly having better value of fitness than their parents. "Bad" agents emigrating between populations are quickly discarded by the evolution process causing no harm whatsoever.