A new restart rule is proposed for genetic algorithms (GAs) with multiple restarts. This rule is based on the Schnabel census method, originally developed for statistical estimation of the animal population size. It is assumed that during a number of latest iterations, the population of a GA was in the stationary distribution and the Schnabel census method is applicable for estimating the quantity of di erent solutions that can be visited with a positive probability. The rule is to restart a GA as soon as the maximum likelihood estimate reaches the number of di erent solutions observed at the last iterations. We demonstrate how the new restart rule can be incorporated into a GA with non-binary representation for the Set Cover Problem. Computational experiments on benchmarks from OR-Library show a signi cant advantage of the GA with the new restarting rule over the original GA. On the unicost instances, the new restarting rule also turned out to be in advantage to restarting the GA as soon as the current iteration number becomes twice the iteration number when the best incumbent was found.
Genetic algorithms (GAs) are randomized search heuristics based on biological analogy of selective breeding in nature, originating from the work of J. Holland and applicable to a wide range of optimization problems. The basic components of a GA are a population of individuals and random operators that are introduced to model mutation and crossover in nature. An individual is a pair of genotype g and phenotype x(g) corresponding to a search point in the space of solutions D to a given optimization problem. Here g is a xed length string of symbols (called genes) from some alphabet A. The function x(g) maps g to its phenotype ? This research is supported by the Russian Science Foundation grant 17-18-01536.
Copyright c by the paper's authors. Copying permitted for private and academic purposes.
In: S. Belim et al. (eds.): OPTA-SCL 2018, Omsk, Russia, published at http://ceur-ws.org x(g) 2 D, thus de ning a representation of solutions in GA. The search in GAs is guided by the values of the tness function (g) = (f (x(g))) on the genotypes of the current population t on iteration t. Here f : D ! R is the objective function of a problem, and : R ! R may be an identical mapping or a monotone function, chosen appropriately to intensify the search. The genotypes of the initial population are randomly generated according to some a priori de ned probability distribution.
In this paper, a new restart rule is proposed for the GAs. The rule is based
on the Schnabel Census method, originally developed for statistical estimation
of size of animal populations [
We show how the new restart rule can be incorporated into a GA with
NonBinary Representation (NBGA) [
The Schnabel Census method as a means of estimation of the number of
unvisited solutions [
One of the methods developed in biometrics for statistical estimation of size
of animal populations is the Schnabel Census method [
Let r be a parameter that de nes the length of a historical period that is considered for statistical analysis. Given some value of a parameter r, the new restart rule assumes that during the r latest iterations, the GA population was at a stationary distribution and all tentative solutions produced on these iterations may be treated analogously to sampled animals in the Schnabel Census method. The Schnabel Census method is applied here to estimate the number of di erent solutions that may be visited with positive probability if the current distribution of o spring remains unchanged.
In the sequel, we assume that in the latest r iterations of a GA we have a sample of r independent o spring solutions and the random variable K is the number of distinct solutions among them. In addition we make a simplifying assumption that all solutions that may be generated in the stationary distribution have equal probabilities. The rule consists in restarting the GA as soon as the estimate ^ML becomes equal to k. The value of parameter r is chosen adaptively during the GA execution. The rationale behind this rule is that once the equality ^ML = k is satis ed, most likely there are no more non-visited solutions in the area where the GA population spent the latest r iterations. In such a case it is more appropriate to restart the GA rather than to wait till the population distribution will signi cantly change. 3
In This Section, We Describe the Ga Application Which is Used for testing the new restart rule. The Set Cover Problem (SCP) can be stated as follows. Consider a set M = f1; : : : ; mg and the subsets Mj M, where j 2 N = f1; :::; ng. A subset J N is a cover of M if Sj2J Mj = M. For each Mj , a positive cost cj is assigned. The SCP is to nd a cover of minimum summary cost.
The SCP may be formulated as an integer linear programming problem: minfcx : Ax e; x 2 f0; 1gng; (1) where c is an n-vector of costs, e is the m-vector of 1s, A = (aij ) is an m n matrix of 0s and 1s, where aij = 1, i i 2 Mj . Using this formulation one can regard SCP as a problem of optimal covering all rows of A by a subset of columns.
In this paper, we use the same GA for the Set Covering Problem as proposed
in our earlier work [
The NBGA was tested on OR-Library benchmark problem sets 4-6, A-H, and two sets of combinatorial problems CLR and Stein. The sets 4-6 and A-H consist of problems with randomly generated costs cj from 1,...,100, while CLR and Stein consist of unicost problems, i.e. here cj = 1 for all j. We compared three modes of GA execution.
{ Mode (i): single run without restarts. { Mode (ii): restarting the GA as soon as the current iteration number becomes twice the iteration number when the best incumbent was found. This rule was used successfully by di erent authors for restarting random hill-climbing and genetic algorithms. { Mode (iii): restarting the GA using the new rule proposed in Section 2. The historic period used for statistical analysis was chosen as r latest iterations of the GA, where value r is chosen adaptively as follows: Whenever the best found solution is improved, r is set to be the population size. If the best incumbent was not improved during the latest 2r iterations, we double the value of r. Here we reset r to the population size, assuming that whenever the best incumbent is improved, the population reaches a new unexplored area and we should reduce the length of the historic period for analysis. If the best incumbent is not improved long enough, our rule extends the historic period. In order to reduce the CPU cost, the termination condition is checked only at those iterations when the value of r is updated. Fig 1 illustrates a typical behavior of parameter r; together with the number of di erent o spring solutions k and the maximum likelihood estimate ^ML over a single GA run, until the termination condition was satis ed.
In our experiments, N = 30 trials of GA in each of the three modes were carried out. The population size was 100 and the total budget of GA iterations over all runs was equal to 10 000. A single experiment with the given budget we call a trial. Let := P3k0=1 f3k0ff 100%, where fk is the cost of solution found in k-th trial and f is the optimal cost. In what follows, Fbst will denote the frequency of obtaining a solution with the best known cost from the literature, estimated by 30 trials. The statistically signi cant di erence at level p 0:05 between the frequencies of nding optimal solutions is reported below.
For all non-unicost problems, we set the mutation probability pm = 0:1. Comparing the GA results in modes (i) and (iii), among 37 instances, where these two modes yield di erent frequencies Fbst, mode (iii) has a higher value Fbst in 31 cases and in 16 out of these 31 cases the di erence is statistically signi cant. Mode (i) has a statistically signi cant advantage over mode (iii) only on a single instance. Numbers of instances where mode (i) or mode (iii) had a higher frequency of nding optima are shown in Fig. 2 (denoted \>freq"). This gure also shows the numbers of instances where these modes had statistically signi cant advantage (denoted \p < 0:05").
Modes (ii) and (iii) show di erent frequencies Fbst on 28 instances. On 16 of these instances mode (iii) has a higher value Fbst than mode (ii) and in 5 out of these 16 cases the di erence is statistically signi cant. Mode (ii) has a statistically signi cant advantage over mode (iii) only on a single instance. In terms of percentage of deviation , averaged over all instances of series 4-6, A,C,D and E,F,G,H, mode (iii) gives the least error.
The three modes of running the GA were also tested on two series of
unicost SCP instances CLR and Stein. Again we use the population size of 100
individuals and the total budget of GA iterations, equal to 10 000 in each trial.
The mutation probability pm is set to 0:01 for all instances. On the unicost
instances, restart mode (iii) shows better or equal results compared to the other
two modes, except for a single instance CLR.13. On CLR.13, the best known
solution is found only in mode (i) and it took more than 4000 iterations. Mode (iii)
was irrelevant on this instance, which is probably due to a negative bias of the
maximum likelihood estimate ^ML (see [
For genetic algorithms, a new restart rule is proposed using the Schnabel Census Method, originally developed to estimate the number of animals in a population. Performance of the new restart rule is shown on a GA with a non-binary representation of solutions for the set cover problem. Computational experiments show a signi cant advantage of the GA with the new restart rule over the GA without restarting and the GA restarting as soon as the current iteration number becomes twice the number of the current iteration. The new restart rule also demonstrated the most stable behavior compared to the other two GA modes.
Applying Schnabel Census in this research is an attempt to further bene t from the convergence between computer science and biology. That interface had been crucial for evolutionary computation to emerge, but was scarcely maintained systematically afterwards. As the present research shows, developing this transdisciplinary integration can be productive.
This appendix contains a description of the NBGA [
Denote the set of columns that cover the row i by Ni = fj 2 N : aij = 1g. The NBGA is based on a non-binary representation where the genotype consists of m genes g(1); g(2); : : : ; g(m), such that g(i) 2 Ni, i = 1; 2; : : : ; m. In this representation x( ) maps a genotype g to the phenotype x(g), where ones correspond to the columns present in genes of g. Obviously, it is a feasible solution. For local improvements we use greedy heuristics that nd approximate solutions to a corresponding reduced version Pg of the given SCP. Problem Pg has a matrix that consists of the columns of A represented in genes of g.
An improved genotype is added to the population only if there are no individuals with the same phenotype in it yet. Genotypes of 0 are generated independently and each gene g(i) is uniformly distributed over Ni:
Consider the population on iteration t as a vector of genotypes of its individuals t = (g1; g2; : : : ; gs). Then the tness function on iteration t is t(g) = cx(gl(t)) cx(g); where l(t) is the index of the individual of the largest cover cost in t:
The selection operator in our GA implements the proportional selection scheme, where the probability to choose the k-th individual is p(gk) = t(gk)
s X l=1
! 1 t(gl)
The operators of crossover, mutation and the local improvement procedures Prime, Greedy and Dual Greedy will be described in what follows.
We use an optimized crossover operator, the LP-crossover, designed for SCP. The goal of this operator is to nd the best possible combination of the genes of parent genotypes gu and gv, if it is possible without extensive computations. Consider a problem of optimal crossover Poc, which is a reduced version of the initial SCP but with the covering subsets restricted by the set of indices N 0 = fj : x(gu)j = 1g [ fj : x(gv)j = 1g.
First, in LP-crossover a trivial reduction is applied to Poc. Denote
S = fi 2 M : jNi \ N 0j = 1g: Then each row i 2 S may be covered by a single column j(i) in Poc. We call Q = fj : j = j(i); i 2 Sg a set of xed columns. For each i 2 S Mj , one of j2Q the columns that cover the gene g(i) in Q is assigned. We refer to these genes as xed too. As a result of the reduction we obtain a new subproblem Pr, that consists of the rows and columns that were not xed during this procedure.
Second, we solve the linear relaxation of Pr, i.e. an LP problem where the Boolean constraints are replaced with the conditions xj 0 for all j. If the obtained solution x0 turns out to be integer, then it is used to complete the genotype g by an assignment of the non- xed genes that corresponds to x0. To avoid time-consuming computations we do not solve Pr if the number of rows in Pr exceeds a threshold (we use = 150). If this is the case or if the number of simplex iterations exceeds its limit (equal to 300 in our experiments), or if the solution x0 is fractional, then LP-crossover returns an unchanged genotype gu.
The mutation operator works as follows: Suppose, i-th gene is to be mutated, then the probability to assign a column j 2 Ni to g(i) is pi(j) = 1 cj
X k2Ni ck 1 ! 1 :
We use three greedy-type heuristics to exclude redundant columns from a
solution. The most simple heuristic Prime starts with a given cover and discards
the columns in decreasing order of indices. A column is discarded only if the
remaining solution is still a cover. The second heuristic is the well-known Greedy
algorithm [
The Dual Greedy Algorithm 1. Set Ni0 := Ni \ N 0 for all i = 1; :::; m, M0 := M; J 0 := N 0; J := ;. 2. While J 6
0 = ; do 2.1. If there is i 2 M0 such that jNi0j = 1, then
using the j 2 Ni0, set J := J [ fjg; M0 := M0n(Mj \ M0).
Otherwise choose j 2 J 0 such that
cj ck jMj\M0j jMk\M0j for all k 2 J 0: 2.2. Set J 0 := J 0nfjg, Ni0 := Ni0nfjg for all i 2 Mj .
In Step 1.2 of NBGA we use the Prime algorithm, while Greedy and Dual Greedy are used in Step 2.4 of NBGA (both heuristics are called and the best of the two obtained solutions is accepted to construct a new genotype g0).
Before solving the non-unicost problems (where cj have di erent values) we
apply a core-re ning reduction which is similar to the approach used in [