Main

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

• Introduction
• EMAS
• iEMAS
• NN optimization
• Papers

Generally speaking immunological algorithms, which are based on immune system of vertebrates, are similar to evolutionary algorithms. There is also a population, which is transformed by the means of mutation. Main difference consists in introducing certain similarity measure, or similarity function and using it in order to affect the transformations of populations. As an example, negative selection algorithm will be presented, which may be used to detect and remove intruders (appropriately defined) from the system. Pseudo code of this algorithm is as follows:

1. Generate random detectors.
2. Present self (good individuals) to the (immature) detectors, if any of the detector matches the individual (by the means of similarity function) it is removed from the system.
3. Remaining detector are considered mature and may be used to detect non-self (bad) indviduals.

For more information about classical immunological algorithms see TW:HP2002, WIERZ2001.

Computation of fitness function value is one of the most common and crucial task in evolutionary algorithms, and usually it is very simple and straightforward. E.g. considering optimization of multi-modal, multi-dimensional function, one can absolutely neglect the computation cost of the fitness function value. However, there exist number of problems, which may be solved by the means of evolution, at the same time using very complex fitness function, e.g.:

• evolution of neural-network architecture (fitness function call consists in performing the full training of the network),
• evolution of theorem prover's parameters (fitness function call consists in performing whole algorithm of theorem proving),
• reverse problems (fitness function call usually consists in performing complex simulation). When solving these or similar problems, evolutionary mechanisms such as selection could use special techniques, in order to decrease the cost of multiple calls of fitness function, e.g. by intelligent getting rid of certain individuals.

iEMAS being the merge of evolutionary (EMAS) and immunological (negative selection inspiration) is aimed at increasing the performance of evolutionary optimization, especially when fitness computation is very time-consuming. The idea of iEMAS is based on the fact, that bad phenotypes come from bad genotypes, so there may exist an alorithm, which when appropriately applied, could remove "bad" genotypes, before even fitness is computed. Thus, the creation of "bad" phenotypes may be hindered. Following this paradigm, a new group of agents is introduced into EMAS. They play the roles of lymphocytes (or T-Cells) and remove "bad" agents from the population in the following way:

• Lymphocyte is created when agent is removed from the system. This lympocyte contains the genotype of the recently removed agent (this genotype may be mutated, moreover, there may be several agents created instead of only one).
• Newly created lymphocyte is now considered immature. During certain time period (negative selection period) the lymphocyte tries to match neighboring agents (the neighbors in the simplest case may be chosen randomly from the current subpopulation) and if it succeeds and the matched agent had high energy level, the lymphocyte is considered "bad" and is removed from the system.
• After passing negative selection period the lymphocyte may match any agent in the subpopulation and interact with it, i.e. it may cause death of matched agent, or penalize it by removing some of its energy.
• The lymphocyte that matched an agent is rewarded by increasing its energy, however, during every step of systems work, energy of every lymphocyte is decreased. Lymphocytes are removed from the system when their energy falls below zero.