Population Model (evolutionary Algorithm)

The population model of an evolutionary algorithm (EA) describes the structural properties of its population to which its members are subject. A population is the set of all proposed solutions of an EA considered in one iteration, which are also called ''individuals'' according to the biological role model. The individuals of a population can generate further individuals as offspring with the help of the genetic operators of the procedure.

The simplest and widely used population model in EAs is the ''global'' or ''panmictic model'', which corresponds to an unstructured population. It allows each individual to choose any other individual of the population as a partner for the production of offspring by crossover, whereby the details of the selection are irrelevant as long as the fitness of the individuals plays a significant role. Due to global mate selection, the genetic information of even slightly better individuals can prevail in a population after a few generations ( iteration of an EA), provided that no better other offspring have emerged in this phase. If the solution found in this way is not the optimum sought, that is called ''premature convergence''. This effect can be observed more often in panmictic populations.

In nature global mating pools are rarely found. What prevails is a certain and limited isolation due to spatial distance. The resulting local neighbourhoods initially evolve independently and mutants have a higher chance of persisting over several generations. As a result, genotypic diversity in the gene pool is preserved longer than in a panmictic population.

It is therefore obvious to divide the previously global population by substructures. Two basic models were introduced for this purpose, the ''island models'', which are based on a division of the population into fixed subpopulations that exchange individuals from time to time, and the ''neighbourhood models'', which assign individuals to overlapping neighbourhoods, also known as ''cellular genetic'' or ''evolutionary algorithms'' (cGA or cEA). The associated division of the population also suggests a corresponding parallelization of the procedure. For this reason, the topic of population models is also frequently discussed in the literature in connection with the parallelization of EAs.

Island models

In the island model, also called the ''migration model'' or ''coarse grained model'', evolution takes place in strictly divided subpopulations. These can be organised panmictically, but do not have to be. From time to time an exchange of individuals takes place, which is called ''migration''. The time between an exchange is called an ''epoch'' and its end can be triggered by various criteria: E.g. after a given time or given number of completed generations, or after the occurrence of stagnation. Stagnation can be detected, for example, by the fact that no fitness improvement has occurred in the island for a given number of generations. Island models introduce a variety of new strategy parameters:
* Number of subpopulations
* Size of the subpopulations
* Neighbourhood relations between islands: they determine which islands are considered neighbouring and can thus exchange individuals, see picture of a simple unidirectional ring (black arrows) and its extension by additional bidirectional neighbourhood relations (additional green arrows)
*Criteria for the termination of an epoch, synchronous or asynchronous migration
* Migration rate: number or proportion of individuals involved in migration.
* Migrant selection: There are many alternatives for this. E.g. the best individuals can replace the worst or randomly selected ones. Depending on the migration rate, this can affect one or more individuals at a time.

With these parameters, the selection pressure can be influenced to a considerable extent. For example, it increases with the interconnectedness of the islands and decreases with the number of subpopulations or the epoch length.

Neighbourhood models or cellular evolutionary algorithms

The neighbourhood model, also called ''diffusion model'' or ''fine grained model'', defines a topological neighbouhood relation between the individuals of a population that is independent of their phenotypic properties. The fundamental idea of this model is to provide the EA population with a special structure defined as a connected graph, in which each vertex is an individual that communicates with its nearest neighbours. Particularly, individuals are conceptually set in a toroidal mesh, and are only allowed to recombine with close individuals. This leads to a kind of locality known as ''isolation by distance''. The set of potential mates of an individual is called its neighbourhood or ''deme''. The adjacent figure illustrates that by showing two slightly overlapping neighbourhoods of two individuals marked yellow, through which genetic information can spread between the two demes. It is known that in this kind of algorithm, similar individuals tend to cluster and create '' niches'' that are independent of the deme boundaries and, in particular, can be larger than a deme. There is no clear borderline between adjacent groups, and close niches could be easily colonized by competitive ones and maybe merge solution contents during this process. Simultaneously, farther niches can be affected more slowly. EAs with this type of population are also well known as ''cellular EAs'' (cEA) or ''cellular genetic algorithms'' (cGA).

A commonly used structure for arranging the individuals of a population is a 2D toroidal grid, although the number of dimensions can be easily extended (to 3D) or reduced (to 1D, e.g. a ring, see the figure on the right). The neighbourhood of a particular individual in the grid is defined in terms of the '' Manhattan distance'' from it to others in the population. In the basic algorithm, all the neighbourhoods have the same size and identical shapes. The two most commonly used neighbourhoods for two dimesional cEAs are L5 and C9, see the figure on the left. Here, ''L'' stands for ''Linear'' while ''C'' stands for ''Compact''. Each deme represents a panmictic subpopulation within which mate selection and the acceptance of offspring takes place by replacing the parent. The rules for the acceptance of offspring are local in nature and based on the neighbourhood: for example, it can be specified that the best offspring must be better than the parent being replaced or, less strictly, only better than the worst individual in the deme. The first rule is ''elitist'' and creates a higher selective pressure than the second non-elitist rule. In ''elitist EAs'', the best individual of a population always survives. In this respect, they deviate from the biological model.

The overlap of the neighbourhoods causes a mostly slow spread of genetic information across the neighbourhood boundaries, hence the name ''diffusion model''. A better offspring now needs more generations than in panmixy to spread in the population. This promotes the emergence of local niches and their local evolution, thus preserving genotypic diversity over a longer period of time. The result is a better and dynamic balance between breadth and depth search adapted to the search space during a run. Depth search takes place in the niches and breadth search in the niche boundaries and through the evolution of the different niches of the whole population. For the same neighbourhood size, the spread of genetic information is larger for elongated figures like L9 than for a block like C9, and again significantly larger than for a ring. This means that ring neighbourhoods are well suited for achieving high quality results, even if this requires comparatively long run times. On the other hand, if one is primarily interested in fast and good, but possibly suboptimal results, 2D topologies are more suitable.

Comparison

When applying both population models to genetic algorithms, evolutionary strategy and other EAs, the splitting of a total population into subpopulations usually reduces the risk of premature convergence and leads to better results overall more reliably and faster than would be expected with panmictic EAs.

Island models have the disadvantage compared to neighbourhood models that they introduce a large number of new strategy parameters. Despite the existing studies on this topic in the literature, a certain risk of unfavourable settings remains for the user. With neighbourhood models, on the other hand, only the size of the neighbourhood has to be specified and, in the case of the two-dimensional model, the choice of the neighbourhood figure is added.

Parallelism

Since both population models imply population partitioning, they are well suited as a basis for parallelizing an EA. This applies even more to cellular EAs, since they rely only on locally available information about the members of their respective demes. Thus, in the extreme case, an independent execution thread can be assigned to each individual, so that the entire cEA can run on a parallel hardware platform. The island model also supports parallelization, e.g. by assigning a processor to each island. If the subpopulations of the islands are organized panmictically, all evaluations of the descendants of a generation can be parallelized additionally. In real-world applications the evaluations are usually by far the most time-consuming part. Of course, it is also possible to design the island sub-populations as cEAs, so that the statements made before about parallelizing cEAs apply. In this way, hierarchical population structures with the appropriate parallelizations can be created. Not only comparatively expensive computer clusters but also inexpensive graphics cards (GPUs) can be used for parallelization.

However, it is important to stress that cEAs, or EAs with a population distributed across islands, represent a search model that differs in many ways from traditional EAs. Moreover, they can run on both sequential and parallel platforms, which highlights the fact that model and implementation are two different concepts.

Bibliography

* Erick Cantú-Paz (2001): ''Efficient and Accurate Parallel Genetic Algorithms'' (PhD thesis, University of Illinois, Urbana-Champaign, USA). Springer, New York, NY.
* Martina Gorges-Schleuter (1990): ''Genetic Algorithms and Population Structures - A Massively Parallel Algorithm.'' PhD thesis, Universität Dortmund, Fakultät für Informatik, Germany.
* Enrique Alba, Bernabé Dorronsoro (2008):
Cellular Genetic Algorithms
'. Springer, New York, NY.
* Dirk Sudholt (2015):
Parallel Evolutionary Algorithms
'. In Janusz Kacprzyk, Witold Pedrycz (eds.): Parallel Evolutionary Algorithms. Springer, Berlin, Heidelberg, pp. 929–959
* Gabriel Luque, Enrique Alba (2011):
Parallel Genetic Algorithms
'. Springer, Berlin Heidelberg. {{doi, 10.1007/978-3-642-22084-5

See also

* Cellular automaton
* Dual-phase evolution
* Evolutionary algorithm
* Metaheuristic

References

Evolutionary algorithms