Main

• AgE project home page
• Evolutionary multi-agent systems
• Computing environment (PL)

• Introduction
• EMAS
• iEMAS
• NN optimization
• Papers

Classical evolutionary algorithms are conducted in following (or similar) way:

1. Initialize the population
2. Compute fitness
3. Select mating pool from the population
4. Choose randomly parents and produce offspring
5. Mutate the offspring creating the new population
6. Return to 2.

One should notice following lacks of classical approach to evolution BacHamSch:TEC97:

• there's no possibility of dynamically changing environmental conditions,
• consideration of many criteria is difficult,
• there's need for global knowledge (in order to perform selection, crossover and mutation)
• there exists generational synchronisation (whole population is changed at once),
• no different species and co-evolution,
• no evolving genotype-fenotype mapping. At least some of these shortcomings may be avoided utilizing the idea of decentralized evolutionary computation, which may be realized as an evolutionary multi-agent system (EMAS).

Following neodarwinian paradigms, two main components of the process of evolution are inheritance (with random changes of genetic information by means of mutation and recombination) and selection. They are realized by the phenomena of death and reproduction, which may be easily modeled as actions executed by agents:

• action of death results in the elimination of the agent from the system,
• action of reproduction is simply the production of a new agent from its parent(s).

One should also notice, that there is no need for global evaluation, every agent may evaluate itself whenever it wants, so the fitness computation may be perceived somewhat inversed.

Inheritance is to be accomplished by an appropriate definition of reproduction, which is similar to classical evolutionary algorithms. The set of parameters describing core properties of the agent (genotype) is inherited from its parent(s) - with the use of mutation and recombination. Besides, the agent may possess some knowledge acquired during its life, which is not inherited. Both the inherited and acquired information determines the behavior of the agent in the system (phenotype).

Selection is the most important and most difficult element of the model of evolution employed in EMAS. This is due to an assumed lack of global knowledge (which makes it impossible to evaluate all individuals at the same time) and autonomy of agents (which causes that reproduction is achieved asynchronously). In such a situation selection mechanisms known from classical evolutionary computation cannot be used. The proposed principle of selection corresponds to its natural prototype and is based on the existence of non-renewable resource, called '''life energy'''. The energy is gained and lost when the agent executes actions in the environment. Increase in energy is a reward for ''good'' behavior of the agent, decrease - a penalty for ''bad'' behavior (which behavior is considered ''good'' or ''bad'' depends on the particular problem to be solved). At the same time the level of energy determines actions the agent is able to execute. In particular, low energy level should increase possibility of death and high energy level should increase possibility of reproduction. Agents should change its energy based on some kind of local-bound algorithm, which may consist in evaluation of their fitness and exchange certain portions of their energy during encounters with neighbors.

A more precise description of this model and its advantages may be found in CetDorNaw:ICMAS96, DorDobNaw:IAI2001, Dor:SOFSEM2002. In short, EMAS should enable the following:

• local selection allows for an intensive exploration of the search space, which is similar to parallel evolutionary algorithms,
• the way phenotype (behaviour of the agent) is developed from genotype (inherited information) depends on its interaction with the environment,
• self-adaptation of the population size is possible when appropriate selection mechanisms are used.

In EMAS, explicitly defined living space facilitates an implementation in a distributed computational environment. The population of individuals may be easily decomposed into subpopulations connected by the means of predefined topology. Thus, genetic material may be exchanged among the subpopulations (similar to classical niching technique - allopatric speciation). Subpopulations may be assigned and run independently on remote nodes. Classical peer to peer computing, clustering or grid approaches may be further adapted.

For more informations about parallel evolutionary algorithms see CAPA:1995