In local selection every individual resides inside a constrained environment called the local neighbourhood. Individuals interact only with individuals inside this region. The neighbourhood is defined by the structure in which the population is distributed. The neighbourhood can be seen as the group of potential mating partners.
Fig 3: Linear neighbourhood: full and half ring
The first step is the selection of the first half of the mating population uniform at random (or using one of the other mentioned selection algorithms, for example, stochastic universal sampling or truncation selection). Now a local neighbourhood is defined for every selected individual. Inside this neighbourhood the mating partner is selected (best of all, fitness proportional or uniform at random).
Fig 4: Two-dimensional neighbourhood: full and half cross
The structure of the neighbourhood can be:
The distance between possible neighbours together with the structure determines the size of the neighbourhood. Table 1 gives examples for the size of the neighbourhood concerning the given structures and different distance values.
Fig 5: Two-dimensional neighbourhood: full and half star
Between individuals of a population an 'isolation by distance' exist. The smaller the neighbourhood, the bigger is the isolation distance. However, because of overlapping neighbourhood, propagation of new variants takes place. This assures the exchange of information between all individuals.
Tab. 1: Number of neighbours for local selection
The size of the neighbourhood determines the speed of propagation of information between the individuals of a population, thus, deciding between quick propagation or maintaining a high diversity/variability in the population. A higher variability is often desired, thus, preventing problems such as premature convergence to a local minimum. Similar results were drawn from simulations in [25]. Local selection in a small neighbourhood performed better than local selection in a bigger neighbourhood. Nevertheless, the interconnection of the whole population must still be provided. Two-dimensional neighbourhood with structure half star using a distance of 1 is recommended for local selection. However, if the population is bigger (>100 individuals) a greater distance and/or a two-dimensional neighbour should be used.