EMAS in multi-modal optimisation
The goal of evolutionary multi-modal optimisation techniques (niching techniques) is to find all (or most) local maxima of the fitness function in a feasible solution set.
In classical evolutionary algorithms, forming and stable maintaining subpopulations (species) are achieved by applying niching techniques like allopatric speciation based on the restricted application of selection and/or recombination mechanisms. Alternatively in sympatric speciation new species evolve while inhabiting the same geographic region. It is modelled in evolutionary algorithms by techniques based on the modification of the parent selection mechanism like fitness sharing, or techniques based on the modification of the mechanism of selecting individuals for a new generation like deterministic crowding. Ideally, each of the species should be placed within one of the basins of attraction of local maxima, which in practice might be difficult to achieve.
Although co-evolutionary techniques and sexual selection mechanism promote the population diversity, they were not widely used as a basis for constructing niching techniques. These techniques were a point of reference for the model of co-evolutionary multi-agent system (CoEMAS).
Co-evolutionary multi-agent systems
As in the case of classical evolutionary algorithms, basic EMAS-based systems, without any special mechanisms that promote useful population diversity are unable to solve multi-modal optimisation problems because they are not able to form species located within basins of attraction of many different local optima. They would rather locate only one solution, however, population diversity would be much higher than in the case of classical evolutionary algorithm.
The basic idea behind the CoEMAS model is to introduce the possibility of co-evolution of species and co-evolution of sexes (sexual selection) within EMAS. In the exemplary systems presented in the next sections, co-evolutionary interactions between species and sexual selection are used in order to construct niching techniques in evolutionary multi-agent system and to promote useful population diversity.
In the co-evolutionary multi-agent system with co-evolving species (nCoEMAS) there exist two different types of computational agents. They will be called ‘niches’ and ‘individuals’ (big agents and small agents in the figure below). Individuals ‘live’ within niches; they can search for a suitable agent-niche and migrate into it. They can even ‘create’ new agent-niche when they are not able to find a suitable niche and migrate into it. The main goal of the mechanism of migrating between and creating new niches is to split the population of agents-individuals into such subpopulations (species) so that each of them would be located within a distinct basin of attraction of local maxima.
Mating is restricted only to agents-individuals located within the same agent-niche. Reproduction, as in the case of basic EMAS model, is initiated by an agent that has enough resources to reproduce. The agent initiating a reproduction process searches for other ready for reproduction partners from the same niche and chooses one of them. Two children are generated and each offspring receives some amount of resources from each of their parents.
Agents-niches can migrate within an environment, but only when they have enough resources, because each migration costs some amount of resources which is returned to the environment. Two agents-niches can merge with each other: merging takes place when centers of gravity of sub-populations, which belong to two different niches, are located within the basin of attraction of the same local optima. The system is applied to multi-modal optimisation problems, therefore, the goal is to localize most of basins of attraction of local maxima.
Resources circulate between an environment and agents. The whole amount of resources within the system is constant so the number of agents cannot grow infinitely. Environment gives equal amount of resources to each agent-niche, and then they redistribute resources among agents-individuals proportionally to their fitness.
Multi-agent system with sexual selection (sCoEMAS) utilizes co-evolution of sexes and sexual selection in order to obtain the effect of speciation. In sCoEMAS there exist two sexes: female and male.
Reproduction process is initiated by a female agent when it has enough resources to reproduce. Generally, female agents use more resources than male agents during the reproduction process and that is why they reproduce less frequently than male agents. Therefore, there are always more male agents ready for reproduction than female agents and female agents choose partners from several ready for reproduction male agents. A female agent located within an evolutionary island searches for a partner in such a way that it chooses one ready for reproduction male agent from the same island. The partner is chosen on the basis of genotype similarity. The more similar two agents from opposite sex are, the more probable is that the female agent will choose the male agent. Reproduction takes place when a pair composed of agents of the opposite sex is formed. Such a pair of agents is formed permanently for several steps of the algorithm because of difficulties and costs involved in searching for a partner. The offspring (two children) is generated with the use of mutation and recombination operators and receives some of the resources from parents: more from the female agent and less from the male one.
Agents can migrate within an environment but it costs some amount of resources. Similar to nCoEMAS, in sCoEMAS the whole amount of resources present within it is constant and the environment distributes resources between agents proportionally to their fitness.