Takeover Time

Takeover time is the number of generations it takes for a single best individual in the initial population to colonize the whole population with copies of itself under the effects of selection only [GD91]. The takeover time is usually used as an approach to characterize the selection pressure of an EA. Shorter takeover times mean a stronger selection.

As an exapmle, we plot in figures 1 and 2 the takeover times for some synchronous (Fig.1) and asynchronous cEAs (Fig.2). For that, only the selection operator is active (binary tournament). Nor mutation neither crossover are applied during the evolution. Initially, only one optimal individual is placed in a random location of the grid, and it is let being selected and copied until it takes over all the grid positions. The axes of the graphics represent the proportion of the best individual in the population (X axis), and the number of generations or time steps (Y axis).  Figure 1. Growth curves of the best individual for two cEAs with different neighborhood and population shapes, but similar ratio values. The graph represents the proportion of population consisting of best individual as a function of time Figure 2. Takeover times with tournament selection using a L5 neighborhood in populations of 1024 individuals with different grid shapes. Mean values over 100 runs. The graph represents the proportion of population consisting of best individual as a function of time. Horizontal axis is in logarithmic scale

Theoretically, only a little work has been made in the literature in this research line in cEAs. The first approach for determining a model for the growth curve (the proportion of the best individual in the population along the time in a cEA) was proposed by Sarma and De Jong (1997). In that work, they proposed a simple quantitative model for cellular EAs based in the logistic family of curves already known to work for panmictic EAs [GD91]. In summary, the proposed equation is: where a is a growth coefficient and P(t) is the proportion of the best individual in the population at time step t. This model threw accurate results for synchronous updates of square shaped cellular EAs.

As it can be guessed from Figures 1 and 2, it is difficult (maybe not possible) to adjust the takeover of algorithms using populations with non-square ratios and/or asynchronous policies with a low error. In the case of asynchronous cEAs, improved models have been proposed by Alba, Giacobini and Tomassini not following a logistic curve. In [GTT03] the authors present quantitative models for the takeover time in cellular evolutionary algorithms structured as a ring with nearest neighbor interactions only. These models are based on simple difference probabilistic equations, and the gap between the real behavior of the algorithm and the model is large in some cases. In a latter studies [GAT03] [GATT04], Alba, Giacobini, Tettamanzi and Tomassini extended those models to synchronous and asynchronous cEAs using a 2-D (square) population.