Analysis of selection noise in genetic algorithms

Soft Computing (2025) 29:3757–3773 https://doi.org/10.1007/s00500-025-10652-6 FOUNDATION, ALGEBRAIC, AND ANALYTICAL METHODS IN SOFT COMPUTING Analysis of selection noise in genetic algorithms Nataliya M. Gulayeva1,2 ·Joaquín Borrego-Díaz2·Fernando Sancho-Caparrini2 Accepted: 18 January 2025 / Published online: 17 May 2025 © The Author(s) 2025 Abstract Selection is often considered as a fundamental force in the evolutionary process. Genetic drift, or selection noise, is an important characteristic of selection methods. It has a direct effect on the performance of genetic algorithms. In this paper, a brief review of methods to analyze genetic drift is given, and known estimations of selection noise of various selection schemes used in genetic algorithms are presented. After that, genetic drift of widely used proportional, ranking, and tournament selection schemes is thoroughly studied. To this end, two new measures for selection noise analysis are proposed, namely the noise takeover time and pure reproduction rate. Using these measures, the effect of population size, chromosome length, and selection scheme parameters on genetic drift is analyzed. Also, selection schemes known as being selection pressure equivalent are tested for selection noise equivalence. Both theoretical and experimental approaches are used for the analysis. The results obtained are presented in tabular form. Wherever possible, it is indicated whether the obtained results are identical or different from the results of previous studies. Since no comprehensive study of selection noise has been conducted previously, this indication concerns only some of the results. Although our results differ at some points from those presented earlier, they are consistent on both measures. Keywords Genetic algorithm ·Genetic drift ·Selection noise ·Proportional selection ·Tournament selection ·Ranking selection 1 Introduction Genetic drift, also called genetic sampling error, is a wellknown phenomenon in population genetics, referring to changes in the gene pool that take place strictly by chance; drift happens faster in small populations than in larger ones (Masel 2011). Genetic drift phenomenon is observed in genetic algorithms due to the stochastic nature of selection operators. In a finite size population, a random selection among individuals of equal fitness leads to a disproportion between the expected and actual number of copies of an individual in the mating pool; in other words, random selection adds noise to the expected number of copies of an individual. BNataliya M. Gulayeva gulayev[email protected] 1Department of Informatics, National University of Kyiv-Mohyla Academy, Kyiv, Ukraine 2Departamento de Ciencias de la Computación e Inteligencia Artificial, Universidad de Sevilla, E.T.S. Ingeniería Informática, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain This explains why, in genetic algorithms, genetic drift is also referred to as selection noise. At low selection pressure, genetic drift can lead to a loss of population diversity and, consequently, to premature convergence of the algorithm, since operation of the algorithm is virtually independent of fitness of individuals. Reducing selection noise is one of the population diversification techniques aiming at preventing premature convergence of genetic algorithms (Hill and O’Riordan 2016). On the other hand, evolutionary algorithms may benefit from the stochasticity in selection process (Branke and Schmidt 2003; Carvalho and Nolfi 2023; Hancock 1997). Therefore, an important task is not to eliminate selection noise but to control its level. To provide mechanisms of such control, we need to understand how various parameters of genetic algorithms affect selection noise. Since selection noise is primarily a property of selection scheme, a tool to estimate selection noise regarding selection scheme parameters as well as genetic algorithm parameters is needed, and estimation of selection noise for various parameter combinations should be done. 123 3758 N. M. Gulayeva et al. In this paper, we introduce two measures to estimate selection noise property of selection schemes. Using these measures, we study the effect of population size, chromosome length, and selection scheme parameters on genetic drift of various proportional, ranking, and tournament selection schemes. We also compare selection noise of selection schemes known as being selection pressure equivalent. We summarize obtained results in tabular form. Wherever possible, we indicate whether our results coincide with the results of previous works or differ from them. This indication applies only to some of our results, since no comprehensive study of selection noise has been conducted previously. The rest of this paper is organized as follows. Section 2 provides a brief review of methods used to study selection noise and results obtained earlier for various selection schemes. Section 3describes the most widely used selection schemes, presents known theoretical results on their selection pressure equivalence, introduces the noise takeover time and pure reproduction rate measures to be used for selection noise analysis, and provides theoretical estimates of the pure reproduction rate values for described selection schemes. Section 4 describes the experimental conditions and parameters whose effect on selection noise is studied. Section 5provides and discusses results obtained for various selection schemes, with the selection pressure equivalent schemes considered separately. Finally, Section 6concludes the paper. 2 Related work Formal criteria to evaluate disproportion between the expected and actual number of copies of an individual in the mating pool were proposed in (Baker 1987; Brindle 1980). To introduce them, let us note that any selection scheme can be considered as a two-step procedure (Brindle 1980; Schell and Wegenkittl 2001). In the first step, the selection probabilities P=(p1,...,pN),pi∈[0,1],N i=1pi=1, are calculated for all individuals i,1 ≤i≤N, of the current population. In the second step, a sampling algorithm, often called a sampling strategy, draws Nindividuals from the current population to the mating pool. Let eibe the expected number of copies of the i-th individual in the mating pool, and let oi be the actual number of its copies. Then ei=N∗pi, expectation E[oi]=ei, and N i=1ei=N i=1oi=N. Thus, oiis an estimator for ei, and selection noise can be measured in terms of the vector (o1,...,oN)distribution characteristics, namely: •bias is the average absolute difference between the actual and expected number of copies of an individual in the mating pool (Brindle 1980); •variance of number of copies of an individual in the mating pool (Brindle 1980); •spread is the range of possible number of copies of an individual in the mating pool (Baker 1987). Following Brindle (1980), bias and variance are measures to estimate accuracy; following Baker (1987), bias indicates accuracy and spread indicates precision. Criteria above were used in (Baker 1987; Brindle 1980)to evaluate the genetic drift of proportional selection schemes. In particular, it was shown that the most popular proportional selection schemes, roulette-wheel selection (RWS) and stochastic universal selection (SUS), both have zero bias, SUS has the minimum spread (from eito ei), and RWS has the maximum spread (from 0 to N). In addition, Baker (1987) used an empirical approach to evaluate bias of proportional selection schemes. He conducted runs of a genetic algorithm using the selection scheme under analyzes and no other genetic operators; the bias factor (the ratio of the actual number of copies of an individual in the mating pool to its expected value) and fertility factor (the percentage of individuals in a population that were selected into the mating pool) were calculated at each iteration of the algorithm. Schell and Wegenkittl (2001) proposed the following noise estimation method based on calculation of the chisquare Goodness-of-Fit statistic. Let all individuals are grouped into dmutually disjoint classes C1,C2,...,Cd.Let Ej=i∈Cjeidenotes the overall expectation in each class, and Oj=i∈Cjoidenotes the overall observation in each class. Then the chi-square statistic χ=d j=1 (Oj−Ej)2 Ejcan be used as a measure for accuracy, with the higher value of χmeaning lower accuracy. It is shown theoretically and empirically that χ≈0 for SUS and χ≈E[χ2 d−1]=d−1 for RWS (Schell and Wegenkittl 2001). To evaluate other selection schemes, a sequence of independent replications of vector (o1,...,oN)is generated. After that, sample expectation and variance are calculated as approximations for the bias and variance criteria. The empirical distribution function is also calculated and compared with theoretical chi-square distribution of a benchmark selection scheme that uses the same probability distribution. SUS and RWS are commonly used as benchmark selection schemes since they are often referred to as extreme sampling schemes with high and low sampling accuracy, respectively. Based on the technique above, it is shown in (Schell and Wegenkittl 2001) that binary tournament selection with replacement is almost perfectly resembled by RWS using the same probability distribution and has lower accuracy in comparison with SUS using the same probability distribution; binary tournament selection with partial replacement provides significantly smaller bias and spread in comparison with RWS using the same probability distribution but has lower accuracy in comparison with SUS using the same probability distribution; the accuracy of binary probability 123 Analysis of selection noise… 3759 tournament selection with partial replacement, p>0.5, does not depend on pand cannot be distinguished from RWS using the same probability distribution. The chi-square statistic was also used to evaluate genetic drift of mixed size tournament selection scheme (msTS) (Huber and Schell 2002) and of several recently proposed selection schemes such as stairwise selection (SWS) (Haq et al 2019), split rank selection (SRS) (Hussain and Muhammad 2020), split-based selection (SBS) (Hussain and Cheema 2020), fitness-based selection (FBS) (Naqvi and Shad 2022), and round-robin based tournament selection (RRTS) (Hussain et al 2022). Rogers and Prügel-Bennett (1999) proposed an analytical estimation of genetic drift in terms of reduce in population fitness variance after one generation. They introduced the rate of genetic drift measure as the ratio of the expectation of fitness variance in a given generation to the fitness variance in the previous generation. The rate is computed assuming the action of selection operator only: to avoid the effect of selection pressure, fitness value is not taken into account in the selection process. It is shown that the rate of genetic drift depends on the population size and selection scheme only, and equations for tournament selection schemes used in generational and generation gap genetic algorithms are derived. Hill and O’Riordan (2016) analyzed genetic drift empirically by comparing the average and the best fitness of a population (on-line and off-line, respectively). Analysis in (Hill and O’Riordan 2016) was performed for SUS, stochastic remainder selection (SRS), and their scaled versions (linear scaling, window scaling, sigma truncation, and Boltzmann scaling) using a four-bit changing deceptive function; no statistically significant differences (Wilcoxon signed rank test) among these methods were revealed. Another approach for empirical analysis of selection noise of selection schemes is to use a flat surface for evolutionary process being under the action of selection operator only. Mahfoud (1996) used this approach to demonstrate differences in selection noise between RWS and SUS in terms of time needed for the population to become homogeneous. In (Chisari and Amadio 2018), to compare genetic drift of RWS, SUS, and binary tournament selection schemes, genetic algorithm runs on a flat landscape are depicted on graphs with “number of generation” and “standard deviation” axes; these graphs visualize the population loss of diversity on the phenotype level. In (Hancock 1994), a function with greater range of fitness values is used, and it is shown graphically that for SUS compared to RWS the number of best individuals in the population grows faster while the fitness of the worst individual remains lower during algorithm execution. Unfortunately, no statistical analysis is provided in the mentioned studies. Genetic drift analysis can also be done by calculating Markov chain transition matrices and finding the time required for the system to reach a homogeneous population (Holland 1992). However, results obtained in this manner are approximations and are difficult to generalize, as Petrowski and Ben Hamida (2016) state. In (Wiles et al 2001) it is argued that tracking the progress of genetic algorithm towards population homogeneity could provide valuable information about genetic drift; the average fitness of the population when an allele becomes homogeneous is proposed as a quantitative measure of diversity. With this approach, several proportional and tournament selection schemes were analyzed empirically using a needle in a haystack problem. Based on the calculations averaged over 10 trials, authors conclude that deterministic and probabilistic binary tournament selection schemes have the highest genetic drift, RWS with sigma truncation and elitist deterministic tournament selection schemes have the lowest genetic drift, and RWS and roulette with ranking (stochastic binary tournament) are characterized by slightly higher genetic drift compared to the lowest one. The conclusion seems surprising since RWS is usually referred to as a scheme with the highest genetic drift. A possible explanation is that the results in (Wiles et al 2001) are obtained on a single parameter set, calculations are averaged over 10 trials only, and no statistical analysis is performed. Also, a crossover operator is used whose effect on selection noise remains an open question. From the above we see that there exist different approaches to study genetic drift of selection schemes, both analytical and empirical ones. However, genetic drift of only some selection schemes has been evaluated analytically. Empirical analysis of genetic drift has been conducted for several popular selection schemes, but statistical analysis of obtained results has not always been performed. We still know little about the effects of various parameters on genetic drift and how selection schemes differ in selection noise while this information could shed light on parameter tuning in genetic algorithms (Gibbs et al 2008; Huber and Schell 2002). 3 Materials and methods 3.1 Selection schemes to be analyzed In this paper, we analyze selection noise of the most popular selection schemes widely used in generational genetic algorithms. These are SUS, RWS, and these schemes using fitness scaling techniques such as linear scaling, power low scaling, and sigma truncation; linear and exponential ranking selection schemes based on SUS and RWS; deterministic and probabilistic tournament selection schemes with and without replacement. Recall that in a generational genetic algorithm the entire population of size Nis replaced during each generation: Nindividuals are selected to the mating pool by use of 123 3760 N. M. Gulayeva et al. a selection scheme, and these individuals produce Nchildren that replace entirely the population of parents. To avoid ambiguity, we briefly describe the above mentioned selection schemes below. We also present theoretical results on selection pressure equivalence for these schemes. 3.1.1 Description of selection schemes In the RWS scheme, the probability piof an individual Xito be selected into the mating pool is proportional to its fitness f(Xi):pi=f(Xi) N j=1f(Xj). To implement, a segment of length pion a segment of unit length is assigned to each individual Xi. Then, a random number 0 <ξ≤1 is generated, and the individual corresponding to the segment containing generated value is selected into the mating pool. This procedure is repeated Ntimes. The SUS scheme uses the same probability distribution as the RWS, but a segment of length Nis divided into N segments of length N∗pi, a random number 0 <ξ≤1is generated only once, and Nindividuals that correspond to the segments containing points of the form ξ+i,0≤i≤N−1, are selected into the mating pool. When a fitness scaling technique is used, RWS and SUS deal with fitness values scaled according to the applied scaling method. In particular, in linear scaling, fscaled(X)= a∗f(X)+b, where coefficients aand bmay be chosen in a number of ways. In sigma truncation, fscaled(X)= f(X)−(f−c∗σ), where fis the mean fitness of the population, σis the standard fitness deviation in the population, and cis a small integer constant. The power low scaling changes fitness values as fscaled(X)=fk(X), where kis a small constant. When fscaled(X)≤0, we put fscaled(X)=d, where dis a small constant. Suppose that individuals are sorted by their fitness values, and ranks are assigned to the individuals such that rank zero is assigned to the least fit individual and rank N−1 is assigned to the fittest one. In a ranking selection scheme, RWS or SUS is used as a sampling strategy. However, the probability pi of an individual Xito be drawn into the mating pool is no longer proportional to its fitness, but depends on its rank, i.e., the relative position of the individual in the sorted list. In linear ranking scheme, pi=(2−β) N+2rank(Xi)∗(β−1) N∗(N−1), where βis a constant, 1 <β≤2. In exponential ranking scheme, pi=c−1 cN−1∗cN−rank(Xi)−1, where cis a constant, 0 <c<1. Hereinafter, the linear ranking scheme with RWS sampling strategy is denoted by LinRank_RWS, and the linear ranking scheme with SUS sampling strategy is denoted by LinRank_SUS. The exponential ranking schemes with RWS and SUS sampling strategies are denoted by ExpRank_RWS and ExpRank_SUS, respectively. Note that in ranking selection schemes, different probabilities are assigned to individuals with the same fitness. Therefore, the population should be shuffled at each iteration of the algorithm to avoid randomly favoring any genotypes. In tournament selection schemes, the probabilities of individuals to be selected into the mating pool are not explicitly assigned. Instead, a group of tindividuals is randomly selected from the population, and the fittest individual is inserted into the mating pool. The procedure is repeated Ntimes. The fittest individual can be selected deterministically or with a probability p,0.5<p<1.0; in the latter case binary tournaments are usually used. There are also tournaments with replacement, when all tournament participants are returned back to the population, and without replacement, when tournament participants are withdrawn from the population. In the latter case, the population is copied ttimes and each copy is used to select individuals until it is exhausted. Another way of implementation is to join tcopies of the population into the one of size t∗N. This approach is used in (Schell and Wegenkittl 2001) and called the tournament with partial replacement selection scheme. In the sequel, we refer to the deterministic tournament selection scheme as TournDet_With if selection is made with replacement, TournDet_Without if selection is made without replacement, and TournDet_Part if selection is made with partial replacement. Similarly, the notations TournProb_With,TournProb_Without, and TournProb_Part are used for the probabilistic tournament selection schemes. 3.1.2 Selection pressure equivalence In this subsection, we describe selection schemes known as being selection pressure equivalent, i.e., schemes that provide the same probability distributions. First of all, these are ranking selection schemes with different sampling strategies (SUS or RWS) and tournament selection schemes with, without, and with partial replacement. Note that tournament selection schemes with different replacement strategies actually provide different probability distributions, but this difference is usually considered to be negligible (Schell and Wegenkittl 2001). It is shown in (Bäck 1996;Julstrom1999) that deterministic tournament selection with replacement and exponential ranking selection schemes associate approximately the same probabilities with chromosomes in a population when c≈1−1 Nt (1) It is stated in (Blickle and Thiele 1996; Goldberg and Deb 1991;Julstrom1999) that individual’s selection probabilities are the same for deterministic tournament selection without replacement, t=2, and linear ranking selection, β=2. Also, it is known from (Julstrom 1999) that the distribution of probabilistic tournament selection without replacement is 123 Analysis of selection noise… 3761 equivalent to that of linear ranking selection when β=2p(2) Combining the statements above we also get the selection pressure equivalence for linear ranking and exponential ranking schemes when β=2 and c≈1−1 N2 (3) 3.2 Proposed selection noise estimation measures Now let us introduce measures to be used for selection noise estimation. These measures are inspired by the biological genetic drift counterpart. Similar to the takeover time criterion τused to evaluate selection pressure (Grefenstette 1997), we introduce the noise takeover time criterion to evaluate selection noise. The noise takeover time, denoted by η, is the number of generations needed for a population to become homogeneous on a flat fitness function when the evolutionary process is driven by selection operator only. Obviously, ηdiffers for different starting points. Therefore, the same initial populations should be used to analyze the effect of scheme parameters on selection noise or compare selection schemes with respect to genetic drift. In the following, we also use the notation ηi to denote the noise takeover time for populations of size Ni. The lower the selection noise, the larger η, and vice versa. For selection schemes with very low selection noise, ηcan be very large. Moreover, for some selection schemes the population will never become homogeneous on a flat fitness landscape, so η→∞. This means that an appropriate budget for maximum number of iterations should be predefined to estimate ηexperimentally. This budget dependence is a limitation for the use of the criterion. In addition to the noise takeover time, we introduce the pure reproduction rate PRR measure defined as the fraction of individuals selected into the mating pool when evolutionary process is driven by selection operator only and effect of selection pressure is excluded. Note that similar measures were used earlier for selection pressure analysis. For example, Baker (1989) introduced the reproduction rate RR measure as the percentage of individuals in a population that were selected into the mating pool; in his earlier papers, the percent involvement (Baker 1985) or fertility factor (Baker 1987) terms were used instead. In (Blickle and Thiele 1996), the loss of diversity LD measure was defined as the proportion of individuals that were not selected to reproduce. From the definitions it follows that RR =100 ∗(1−LD). Baker (1989)usedRR as a dynamic convergence measure. Blickle and Thiele (1996)viewedLD as a function of selection intensity. We propose to compute PRR on a flat fitness landscape to quantify the selection noise of selection schemes. Note that PRR ≤1, and the less noisy the selection scheme, the larger PRR. 3.3 Methods of analysis In this subsection, we describe the empirical approach used in the paper to estimate the noise takeover time and pure reproduction rate values. Then we give theoretical estimates of the proposed measures for the schemes described in Subsection 3.1.1. 3.3.1 Empirical approach We use the following empirical approach to study genetic drift. We conduct multiple runs of genetic algorithm with a selection scheme under analysis; no other genetic operator is used, thus, the population of children matches the mating pool. Runs are conducted on a flat fitness function, hence, the effect of selection pressure is eliminated. Algorithm stops when population becomes homogeneous or when allocated time resources are spent. For each run, the number of iterations performed by the algorithm and PRR average over generations are saved. Afterwards, the minimum, maximum, average, and standard deviation of number of iterations and of PRR average are calculated for the runs when the algorithm stops under the population homogeneity condition. In the sequel, we denote by AvgNI the average number of iterations and by AvgPRR the average PRR average over runs. Also, the notation AvgNI(N)is used for AvgNI computed for populations of size N. 3.3.2 Theoretical estimations By construction, fitness scaling techniques accentuate small differences in objective values by mapping fitness values to an interval. On a flat objective function, these techniques do not change the probability distribution of individuals to be selected into the mating pool. Thus, RWS and SUS with fitness scaling have the same selection noise, i.e., the same noise takeover time and pure reproduction rate, as RWS and SUS without scaling, respectively. Also, on a flat fitness landscape, determining the fittest individual among a group of individuals is stochastic for any tournament selection scheme. Thus, probabilistic tournament selection schemes with different values of pshould have the same noise takeover time and pure reproduction rate as the appropriate binary deterministic tournament selection schemes. With a flat fitness function, the expected number of copies of the i-th individual in the mating pool for proportional selection schemes is given by ei=N∗pi=N∗1 N=1. Recall that SUS is known as a scheme with the highest sampling accuracy: it has zero bias and minimum spread that ranges 123 3762 N. M. Gulayeva et al. from eito ei, i.e., from 1 to 1. Therefore, we estimate PRR =1 for SUS and its scaled versions. Also, on a flat fitness landscape no convergence of genetic algorithms using SUS or its scaled versions is expected, i.e., η→∞. We have no theoretical estimates of ηfor other selection schemes. Theoretical estimates of PRR are given below. For RWS, selection of an individual on a flat fitness landscape can be considered as a Bernoulli trial with probability of success 1 N. Therefore, the probability of an individual not to be selected into the mating pool is determined by binomial distribution and is equal to N 0∗1 N0∗1−1 NN= N−1 NN, where N 0is the binomial coefficient. Thus, for RWS and its scaled versions we get PRR =1−N−1 NN (4) Eq. 4can also be obtained by calculating the probability of an individual to be selected into the mating pool at least once. In this case, we get sum of terms of the geometric sequence: PRR =1 N+1 N∗1−1 N1 +1 N∗1−1 N2 + +···+ 1 N∗1−1 NN = = 1 N∗1−1 NN−1 1−1 N−1=1−N−1 NN Eq. 4is valid for tournament selection schemes with replacement since on a flat fitness function the probability of success equals t N∗1 t=1 Nfor all individuals. This result differs from that of Blickle and Thiele (1996), where non-flat fitness landscapes are considered. Recall that number of successful draws without replacement from a finite population is modeled by Hypergeometric(M,K,m) distribution, where Mis the population size, K is the number of objects with a specified feature, and mis the number of draws from the population. Let N=k∗t+i, where k=N t. For tournament selection schemes without replacement, kdifferent individuals are drawn without replacement from each of tcopies of the population. Hence, on a flat fitness landscape the probability of an individual to be selected into the mating pool is described by the Hypergeometric(N,1,k) distribution. In our implementation, the remaining iindividuals needed to fill the mating pool are drawn without replacement from another copy of the population, and the probability of an individual to be selected into the mating pool is described by the Hypergeometric(N,1,i) distribution. From the above it follows that the probability of an individual not to be selected into the mating pool is equal to the probability of being selected zero times from all population copies and is equal to (1 0)∗(N−1 k) (N k)t ∗(1 0)∗(N−1 i) (N i)=N−k Nt∗N−i N. Thus, for TournDet_Without we get PRR =1−N−k Nt ∗N−i N(5) where k=N t,i=N−k∗t. Note that when i=0, we get N=k∗t, and N−k Nt∗N−i N=k∗t−k k∗tt∗N−0 N=t−1 tt. Therefore, we get PRR =1−t−1 tt (6) for TournDet_Without when N tis an integer. For tournament selection schemes with partial replacement, Nindividuals are drawn without replacement from t joined copies of the population of size N. Therefore, the probability of an individual to be selected into the mating pool is described by the Hypergeometric(N∗t,t,N) distribution, and for TournDet_Part we obtain PRR =1−t 0∗t∗N−t N t∗N N= =1− t−1  i=0 (t−1)∗N−i t∗N−i (7) Binary tournaments are the most widely used in theoretical and practical research, see (Chisari and Amadio 2018; Schell and Wegenkittl 2001; Wiles et al 2001). Therefore, values of PRR at t=2 are of particular interest to us. From Eq. 4it follows that PRR tends to 0.63 as Nincreases. The value does not depend on tand is valid for binary TournDet_With and TournProb_With. For binary tournaments without and with partial replacement, the PRR tends to 0.75 as Nincreases. Indeed, from Eq. 5we get for binary TournDet_Without and TournProb_Without PRR =0.75 (8) when Nis even, and PRR =0.75 −N2−N−1 4N3(9) when Nis odd. From Eq. 7we get for binary TournDet_Part and TournProb_Part PRR =1−N−1 4N−2(10) 123 Analysis of selection noise… 3763 For ranking selection schemes, the probabilities of individuals to be selected into the mating pool depend on the rank only, thus, estimates obtained earlier for RR or LD should also be valid under a flat fitness function. Using results from (Blickle and Thiele 1996), we get for LinRank_SUS PRR =1−β−1 4(11) and for ExpRank_SUS PRR =1−1−ln α−1 αln α ln α−α α−1(12) where α=cN. Values of PRR for LinRank_RWS and ExpRank_RWS should be smaller and bounded from above by Eq. 4. 4 Experiments In this paper, experiments are conducted under the following conditions. As a flat fitness landscape, the function FCONST(X)= 100 defined on binary strings of fixed length is used. Initial population of size Nis generated randomly; each gene is set to 1 with the probability 0.5 or to 0 with the same probability. The algorithm stops when the population becomes homogeneous (that is, all strings representing individuals in the population become identical) or after 100000 iterations. For each parameter set, a series of 100 runs of genetic algorithm using the selection scheme under analysis is performed. To avoid randomly assigning a better starting point to any algorithm, i-th runs of the compared algorithms are performed using the same initial population, i=1,...,100. Criteria mentioned in Subsection 3.3.1 are computed over runs to estimate the noise takeover time and pure reproduction rate values. We have conducted two stages of experiments. First, we study the effect of various parameters on genetic drift of the selection schemes under analysis. Secondly, we test selection schemes that provide the same probability distributions (the same selection pressure, see Subsection 3.1.2)tohavethe same selection noise. At the first stage, the following parameters are considered: •population size N; •chromosome length l; •parameters specific for selection schemes. The reasons to choose the above parameters are as follows. It is shown analytically in (Rogers and Prügel-Bennett 1999) that the rate of genetic drift depends on the population size: the larger N, the smaller the genetic drift, hence, the larger the value of η. It is also well known that in nature genetic drift happens faster in small populations than in larger ones (Masel 2011). The diversity of chromosomes of the initial population affects the noise takeover time η: the greater the chromosomal diversity of the initial population, the larger the value of η. Chromosomal diversity depends on the initialization method and length of chromosomes. Indeed, when 2l<N, the population will contain identical chromosomes regardless of the initialization method used. To study the effect of initial population diversity we use different values of l. We use chromosome length values such that the possible number of different chromosomes is equal to 2, is about 30% of the population size, and is greater than the population size. Finally, parameters specific for selection schemes such as t and pin tournament selection schemes or βand cin ranking selection schemes are usually referred to as parameters affecting selection pressure (Bäck 1996; Baker 1985; Blickle and Thiele 1995,1996; Goldberg and Deb 1991; Huber and Schell 2002;Julstrom1999; Julstrom and Robinson 2000), whereas their effect on genetic drift is an open question. All experiments at the first stage are conducted using the following parameter values: •N=100,N=200,N=400; •l=1,l=log(0.32N), l=10,l=100; •values of parameters specific for selection schemes are given in Table 1. In the sequel, we refer to this set of parameter values as the ParamSuite 1. If necessary, ParamSuite 1 is extended to refine the analyzed dependencies; the extensions are listed additionally for each particular case. It is noted in Subsection 3.3.2 that RWS and SUS with fitness scaling have the same selection noise as RWS and SUS without scaling, respectively. Nevertheless, we conduct additional runs for RWS and SUS with fitness scaling to get more data for analysis and ensure the consistency of results obtained for proportional selection schemes. Similarly, we conduct additional runs for probabilistic tournament selection schemes with different values of p, although on a flat fitness landscape the probabilistic tournament selection schemes have the same selection noise as the appropriate deterministic tournament selection schemes, see Subsection 3.3.2. For the second stage of experiments, the ParamSuite 2 set of parameter values is used: •N=100,N=200,N=300,N=400; •l=1,l=10,l=100; •values of parameters specific for selection schemes are given in Table 2. 123 3764 N. M. Gulayeva et al. Table 1 Values of parameters specific for selection schemes (ParamSuite 1) Scheme Parameter values SUS/RWS with linear scaling a=1,b=1; a=1,b=−1; a=2,b=1; a=2,b=−1 SUS/RWS with sigma truncation c=1; c=2; c=3; c=4; c=5 SUS/RWS with power low scaling k=1.005; k=1.01; k=1.05; k=1.1; k=1.5; k=2 LinRank_SUS/_RWS β=2; β=1.8; β=1.6; β=1.2 ExpRank_SUS/_RWS c=0.809; c=0.9; c=0.945; c=0.955; c=0.979; c=0.996 TournDet_With/_Without/_Part t=2; t=3; t=4; t=5; t=6; t=7; t=8; t=9; t=10; t=20 TournProb_With/_Without/_Part p=0.9; p=0.8; p=0.75; p=0.7; p=0.6 Table 2 Values of parameters specific for selection schemes with the same selection pressure (ParamSuite 2) Scheme 1 Scheme 2 Parameter values LinRank_SUS LinRank_RWS β=2; β=1.8; β=1.6; β=1.5; β=1.4; β=1.2 ExpRank_SUS ExpRank_RWS c=0.9950; c=0.9933; c=0.9925; c=0.9900; c=0.9876; c=0.9867; c=0.9851; c=0.9834; c=0.9826; c=0.9802; c=0.9801; c=0.9777; c=0.9769; c=0.9753; c=0.9752; c=0.9736; c=0.9704; c=0.9703; c=0.9672; c=0.9655; c=0.9607; c=0.9606; c=0.9559; c=0.9512; c=0.9511; c=0.9510; c=0.9415; c=0.9354; c=0.9321; c=0.9227; c=0.9135; c=0.9046; c=0.9044; c=0.8179 TournDet_Without TournDet_Part tfrom Table 1 TournProb_Without TournProb_Part pfrom Table 1 TournDet_Without/_Part TournDet_With tfrom Table 1 TournProb_Without/_Part TournProb_With pfrom Table 1 TournDet_With/_Without/_Part ExpRank_SUS/_RWS tfrom Table 1 cis calculated for each t,Nby Eq. 1 TournDet_With/_Without/_Part LinRank_SUS/_RWS t=2 β=2 LinRank_SUS ExpRank_SUS β=2 cis calculated for each Nby Eq. 3 LinRank_RWS ExpRank_RWS β=2 cis calculated for each Nby Eq. 3 TournProb_With/_Without/_Part LinRank_SUS/_RWS pfrom Table 2 βis calculated by Eq. 2 Parameter values for the second stage of experiments are chosen with regard to the results obtained in the first stage, and the data obtained in the first stage are reused where possible. To evaluate the effect of selection scheme specific parameters, ANOVA is used. Cochran’s C test is used to verify the equality of variances condition required for ANOVA to be applied. In case of strong differences in variances, the Kruskal-Wallis H test (by ranks) is additionally used. However, both the H test and ANOVA gave similar results in all the cases. To evaluate the effect of other parameters, two-sample t-tests are performed for two series of runs, each using the same parameter values except for the one under analysis. 123 Analysis of selection noise… 3765 Table 3 Effect of population size N: test results for RWS, l=100 N1AvgNI,N2AvgNI,p-value N=N1N=N2 100 205.35 200 393.72 8.38 ∗10−13 100 205.35 400 817.53 1.26 ∗10−23 200 393.72 400 817.53 2.55 ∗10−12 Also, t-tests are used to compare selection noise of selection schemes with the same selection pressure and in some cases to clarify the effect of scheme specific parameters. We use α=0.01 significance level in our analysis. 5 Results and discussion 5.1 Effect of parameters on selection noise In this subsection, we analyse the effect of population size, chromosome length, and selection scheme parameters on genetic drift of various proportional (Subsection 5.1.1), ranking (Subsection 5.1.2), and tournament (Subsection 5.1.3) selection schemes. Subsection 5.1.4 summarizes obtained results and compares them with those obtained in earlier studies. 5.1.1 Proportional selection schemes All runs of SUS and its scaled versions were stopped after execution of 100000 iterations; AvgPRR =1. This experimental result is consistent with our theoretical estimates, see Subsection 3.3.2. To analyze the effect of population size Non ηfor RWS and RWS with scaling, two-sample t-tests are performed for series of runs, each series in a pair differs only in N; pairs with N=100 and N=200, N=200 and N=400, and N=100 and N=400 are compared. In all our experiments, values of AvgNI differ for different N. Table 3illustrates the results obtained for RWS, l=100. The experiments have also shown that AvgNI grows proportionally to the population size growth. To confirm, we used two-sample t-tests for AvgNI(Nj)∗Ni Njand AvgNI(Ni)values. Thus, we conclude that Ni Nj ≈ηi ηj (13) To analyze the effect of chromosome length lon ηfor RWS and RWS with scaling, two-sample t-tests are performed for series of runs using the same parameter sets but different chromosome lengths. Our experiments revealed statistically Table 4 Effect of chromosome length l:testresultsforRWS,N=100 l1AvgNI,l2AvgNI,p-value l=l1l=l2 1 129.56 5 188.95 2.81 ∗10−05 1 129.56 10 174.67 1.14 ∗10−03 1 129.56 100 205.35 1.01 ∗10−06 5 188.95 10 174.67 0.275 5 188.95 100 205.35 0.258 10 174.67 100 205.35 0.033 significant difference in AvgNI only for pairs with l=1 and l≥log(0.32N), i.e., when numbers of different chromosomes in initial populations differ significantly. Table 4 shows the results obtained for RWS, N=100. Experimentally obtained values of AvgPRR correspond to the values from Eq. 4and are about 0.63 for all N. 5.1.2 Ranking selection schemes To examine the effect of chromosome length lon η,twosample t-tests are performed for series of runs using the same parameter sets but different chromosome lengths. For all ranking selection schemes, the effect of lon ηis confirmed for pairs with l=1 and l≥log(0.32N)and is not confirmed for pairs where both l≥log(0.32N). For linear ranking selection schemes LinRank_SUS and LinRank_RWS, the effect of population size Non ηwith the growth of ηin proportion to the growth of N,seeEq.13,is confirmed by two-sample t-tests performed for series of runs using the same parameter sets but different values of N. For exponential ranking selection schemes ExpRank_SUS and ExpRank_RWS, the effect of population size Non ηwas not clear from the analysis of runs based on ParamSuite 1. Therefore, additional series of runs were conducted using the extended set of parameter values, namely: •N=40,N=80,N=100,N=200,N=300,N= 400; •l=10,l=100; •34 different values of parameter cgiven in Table 2. As before, two-sample t-tests were performed for different series of runs. Parameter values for these series differed in the population size only, and pairs Niand Njsuch that Ni Nj≥2 were used for the analysis. Experiments have shown that for ExpRank_RWS the value of AvgNI increases with increasing N, and this increase is more significant for larger values of c. Namely, for Ni> Njit is true that AvgNI(Ni)>AvgNI(Nj)for larger values of c, and either AvgNI(Ni)>AvgNI(Nj)or the 123 3772 N. M. Gulayeva et al. island algorithm could have different selection noise and/or selection pressure. Providing procedures to control selection noise and find the pressure-noise balance for various computational models and problem types is a subject for future research. Acknowledgements The authors thank the anonymous reviewers for their comments and suggestions that helped us improve the paper. Funding Funding for open access publishing: Universidad de Sevilla/ CBUA This work is funded by University of Seville plan to aid Ukraine and by Grant PID2023-147198NB-I00 funded by MICIU/AEI/ 10.13039/501100011033 (Agencia Estatal de Investigación), Spain, and by FEDER, UE. Data Availability The datasets generated and analysed during the current study are available from the corresponding author on reasonable request. Declarations Conflict of interest The authors have no relevant financial or nonfinancial interests to disclose. Ethical approval Ethical approval is not required for this type of study. Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecomm ons.org/licenses/by/4.0/. References Bäck T (1996) Evolutionary Algorithms in Theory and Practice: Evolution Strategies, evolutionary programming, genetic algorithms. Oxford University Press Inc, New York, USA, Genetic Algorithms Baker JE (1985) Adaptive selection methods for genetic algorithms. In: Greffenstette JJ (ed) Proceedings of the 1st International Conference on Genetic Algorithms and Their Applications. Lawrence Erlbaum Associates Inc., Hillsdale, NJ, pp 101–111 Baker JE (1987) Reducing bias and inefficiency in the selection algorithm. In: Greffenstette JJ (ed) Genetic algorithms and their applications: Proceedings of the 2nd International Conference on Genetic Algorithms. Lawrence Erlbaum Associates Inc., Hillsdale, NJ, pp 14–21 Baker JE (1989) An analysis of the effects of selection in genetic algorithms. PhD thesis, Graduate School of Vanderbilt University, Nashville, TN Blickle T, Thiele L (1995) A mathematical analysis of tournament selection. In: Eshelman LJ (ed) Proceedings of the 6th International Conference on Genetic Algorithms. Morgan Kaufmann, San Mateo, CA, pp 9–16 Blickle T, Thiele L (1996) A comparison of selection schemes used in evolutionary algorithms. Evolutionary Computation 4(4):361– 394. https://doi.org/10.1162/evco.1996.4.4.361 Branke J, Schmidt C (2003) Selection in the presence of noise. In: Cantú-Paz E, Foster JA, Deb K et al (eds) Genetic and Evolutionary Computation - GECCO 2003, vol 2723. Lecture Notes in Computer Science. Springer, Berlin, Heidelberg, pp 766–777 Brindle AF (1980) Genetic algorithms for function optimization. PhD thesis, University of Alberta, Edmonton, Canada Carvalho JT, Nolfi S (2024) The role of morphological variation in evolutionary robotics: Maximizing performance and robustness. Evol Comput 32(2):125–142. https://doi.org/10.1162/evco_a_00336 Chisari C, Amadio C (2018) Tosca: a tool for optimisation in structural and civil engineering analyses. International Journal of Advanced Structural Engineering 10:401–419. https://doi.org/10. 1007/s40091-018-0205-1 Gibbs MS, Dandy GC, Maier HR (2008) A genetic algorithm calibration method based on convergence due to genetic drift. Information Sciences 178(14):2857–2869. https://doi.org/10.1016/j.ins.2008. 03.012 Goldberg DE, Deb K (1991) A comparative analysis of selection schemes used in genetic algorithms. In: Rawlins GJ (ed) Foundations of Genetic Algorithms. Morgan Kaufmann, San Mateo, CA, p 69–93, https://doi.org/10.1016/B978-0-08-050684-5.50008-2 Grefenstette J (1997) Proportional selection and sampling algorithms. In: Bäck T, Fogel DB, Michalewicz Z (eds) Handbook of Evolutionary Computation. Institute of Physics Publishing and Oxford University Press, Bristol and New York, p C2.2:1–C2.2:7 Hancock PJB (1994) An empirical comparison of selection methods in evolutionary algorithms. In: Fogarty TC (ed) AISB Workshop on Evolutionary Computing, vol 865. Lecture Notes in Computer Science. Springer, Berlin, pp 80–94 Hancock PJB (1997) A comparison of selection mechanisms. In: Bäck T, Fogel DB, Michalewicz Z (eds) Handbook of Evolutionary Computation. Institute of Physics Publishing and Oxford University Press, Bristol and New York, p C2.8:1–C2.8:11 Haq Eu, Ahmad I, Hussain A et al (2019) A novel selection approach for genetic algorithms for global optimization of multimodal continuous functions. Computational Intelligence and Neuroscience 2019. https://doi.org/10.1155/2019/8640218 Hill S, O’Riordan C (2016) Diversifying techniques & neutrality in genetic algorithms. In: Merelo J, Melício F, Cadenas JM, et al (eds) Proceedings of the 8th International Joint Conference on Computational Intelligence (IJCCI 2016) - ECTA, INSTICC, vol 3. SciTePress, pp 140–147, https://doi.org/10.5220/ 0006036201400147 Holland JH (1992) Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. University of Michigan Press, Ann Arbor, MI, https://doi.org/10.7551/mitpress/1090.001.0001 Huber R, Schell T (2002) Mixed size tournament selection. Soft Computing 6:449–455. https://doi.org/10.1007/S00500-001-0160-8 Hussain A, Cheema SA (2020) A new selection operator for genetic algorithms that balances between premature convergence and population diversity. Croatian Operational Research Review 11:107– 119. https://doi.org/10.17535/crorr.2020.0009 Hussain A, Muhammad YS (2020) Trade-off between exploration and exploitation with genetic algorithm using a novel selection operator. Complex & Intelligent Systems 6:1–14. https://doi.org/10. 1007/s40747-019-0102-7 Hussain A, Riaz S, Amjad M et al (2022) Genetic algorithm with a new round-robin based tournament selection: Statistical properties analysis. PLOS ONE 17(9):e0274456. https://doi.org/10. 1371/journal.pone.0274456 Julstrom BA (1999) It’s all the same to me: revisiting rank-based probabilities and tournaments. In: Proceedings of the 1999 Congress on 123 Analysis of selection noise… 3773 Evolutionary Computation - CEC99 (Cat. No. 99TH8406), vol 2. IEEE Press, Piscataway, NJ, pp 1501–1505, https://doi.org/10. 1109/CEC.1999.782661 Julstrom BA, Robinson DH (2000) Simulating exponential normalization with weighted k-tournaments. In: Proceedings of the 2000 Congress on Evolutionary Computation. CEC00 (Cat. No.00TH8512), vol 1. IEEE Press, Piscataway, NJ, pp 227–231, https://doi.org/10.1109/CEC.2000.870299 Mahfoud SW (1996) Niching methods for genetic algorithms. PhD thesis, University of Illinois at Urbana-Champaign, Urbana, USA, uMI Order No. GAX95-43663 Masel J (2011) Genetic drift. Current Biology 21(20):R837–R838. https://doi.org/10.1016/j.cub.2011.08.007 Naqvi FB, Shad MY (2022) A new fitness-based selection operator for genetic algorithms to maintain the equilibrium of selection pressure and population diversity. Croat Oper Res Rev (CRORR) 13(1):113–130. https://doi.org/10.17535/crorr.2022.0008 Petrowski A, Ben Hamida S (2016) Evolutionary algorithms. In: Siarry P (ed) Metaheuristics. Springer International Publishing, Cham, p 115–178, https://doi.org/10.1007/978-3-319-45403-0_6 Rogers A, Prügel-Bennett A (1999) Genetic drift in genetic algorithm selection schemes. IEEE Transactions on Evolutionary Computation 3(4):298–303. https://doi.org/10.1109/4235.797972 Schell T, Wegenkittl S (2001) Looking beyond selection probabilities: Adaptation of the χ2measure for the performance analysis of selection methods in GAs. Evolutionary Computation 9(2):243– 256. https://doi.org/10.1162/106365601750190424 Wiles J, Schulz R, Bolland S et al (2001) Selection procedures for module discovery: exploring evolutionary algorithms for cognitive science. In: Moore JD, Stenning K (eds) Proceedings of the 23rd Annual Conference of the Cognitive Science Society (CogSci 2001). Lawrence Erlbaum Associates, Mahwah, New Jersey, pp 1124–1129 Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. 123