A grouping genetic algorithm for joint stratification and sample allocation designs
Section 2. Classical vs grouping genetic algorithms

• Previous
• Next

In this section we discuss “classical” and “grouping” GAs, and explain why the latter are more appropriate for our problem.

2.1  Classical genetic algorithms

GAs are a nature-inspired class of optimisation algorithms, modelled on the ability of organisms to solve the complex problem of adaptation to life on Earth. The variables of an optimisation problem are called genes and their values alleles. A candidate solution is a list of alleles called a chromosome. A set of chromosomes is usually called a population, so to avoid confusion with the target population we shall use chromosome population when referring to GAs. The objective function (which is maximised by convention) is called the chromosome’s fitness. The search for fit chromosomes (solutions with high objective) uses two genetic operators: small random changes called mutation, equivalent to small local moves in a hill-climbing algorithm; and large changes called crossover in which the genes of two parent chromosomes are recombined. One well-known recombination operator is single-point crossover: choose two parent chromosomes with alleles

$$a_1\mathrm{,}\dots \mathrm{,}{a}_N{b}_1\mathrm{,}\dots \mathrm{,}{b}_N,$$

select a random integer $i$ (the crossover point) such that $1\le i\mathrm{<mo><</mo>}N,$ and generate two new offspring chromosomes

$$a_1\mathrm{,}\dots \mathrm{,}{a}_i\mathrm{,}{b}_{i+1}\mathrm{,}\dots \mathrm{,}{b}_N{b}_1\mathrm{,}\dots \mathrm{,}{b}_i\mathrm{,}{a}_{i+1}\mathrm{,}\dots \mathrm{,}{a}_N.$$

These might be further subjected to random mutation, in which a few alleles are changed, before placing them back into the chromosome population. There are a variety of methods for selecting parents and replacing existing chromosomes. In generational GAs the entire chromosome population is replaced by offspring, and parents are often selected randomly but with a bias toward fitter chromosomes; while in steady-state GAs only one offspring is generated in each GA iteration, and usually replaces the least-fit chromosome in the chromosome population. GAs often give more robust results than search algorithms based on hill-climbing, because of their use of recombination. They have found many applications since their introduction in 1975 by John Holland.

The original GA which is represented in the $R$ (R Core Team, 2015) package SamplingStrata (Barcaroli, 2014), is an elitist generational GA in which the atomic strata $L$ are considered to be elements of a set (or genes) for a standard crossover strategy. In each iteration the best solutions (the elite) are carried over to the next generation. Each gene represents a variable in the problem. We refer to this as a classical GA because a classical problem representation and genetic operators are used, as described below.

Dividing atomic strata into disjoint groups is an example of a grouping problem, related to cutting, packing and partitioning problems. The motivation for our work is that classical GAs are known to perform poorly on grouping problems. The reason is that the chromosomal representation of a grouping contains a great deal of symmetry (or redundancy): permuting the group names yields an equivalent grouping, so each grouping has multiple representations. Symmetry has a damaging effect on GAs because recombining similar parent groupings might yield a very different offspring grouping, violating the basic GA principle that parents should tend to produce offspring with similar fitness. In extreme cases, a classical GA might perform even worse than a completely random search. We provide two examples to illustrate the problem.

To illustrate the problem with symmetry in our first example the parents represent the same grouping in different ways. Note that to increase readability, letters A - F are used as alleles instead of integers in the presentation here. Consider the following two chromosomes:

which both represent the grouping $\left\{\left\{1\right\},\left\{2\right\},\left\{3\right\},\left\{4\right\},\left\{5\right\},\left\{6\right\}\right\}.$ Now suppose we apply single-point crossover to obtain two new offspring chromosomes from these parents. Arbitrarily choosing the center of the chromosomes as the crossover point, we obtain offspring:

which both represent the completely unrelated grouping $\{\left\{1,6\right\},\left\{2,5\right\},\left\{3,4\right\}\}:$ no groups at all are passed from the parents to the offspring. Hence the offspring and parent fitnesses can be completely unrelated to each other, which reduces the GA to near-random search. As another example, consider the following two classical chromosomes:

which in turn represent the different groupings $\left\{\left\{1\right\},\left\{3,6\right\},\left\{2,5\right\},\left\{4\right\}\right\}$ and $\left\{\left\{5,6\right\},\left\{1,4\right\},\left\{2,3\right\}\right\}.$ Using the same crossover strategy we obtain offspring:

representing the groupings $\left\{\left\{1,5,6\right\},\left\{3\right\},\left\{4\right\},\left\{2\right\}\right\}$ and $\left\{\left\{6\right\},\left\{1\right\},\left\{5\right\},\left\{2,3,4\right\}\right\}.$ Note that these offspring have very little in common with their parents, as the only preserved groups are $\left\{1\right\}$ and $\left\{4\right\}.$

2.2  Grouping genetic algorithms

The symmetry problem can be tackled by designing more complex genetic representations and operators (Galinier and Hao, 1999) or by clustering techniques (Pelikan and Goldberg, 2000). The risk of clustering is that genetic diversity may be lost if the clusters are too tight, leading to search stagnation (Prügel-Bennett, 2004). Instead we follow the former approach by designing a GGA (Falkenauer, 1998), which have been shown to perform far better than classical GAs on grouping problems.

GGAs are designed specifically to solve grouping problems and have found many applications, including WiFi network deployment (Agustín-Blas, Salcedo-Sanz, Vidales, Urueta and Portilla-Figueras, 2011), wireless network design (Brown and Vroblefski, 2004), steel plate cutting (Hung, Sumichrast and Brown, 2003), production plant layout (De Lit, Falkenauer and Delchambre, 2000) and social network analysis (James, Brown and Ragsdale, 2010). They may use the same heuristics as other GAs (parent selection, offspring replacement, etc.) but they use different genetic encoding and operators: that is, how they map a problem to chromosomes and how they perform recombination and mutation. We shall illustrate these differences on the above examples.

GGAs represent a grouping as an ordered list of subsets, omitting empty sets. The parents in the second example of Section 2.1 might be represented in this way:

$$\langle \left\{1\right\},\left\{3,6\right\},\left\{2,5\right\},\left\{4\right\}\rangle \langle \left\{5,6\right\},\left\{1,4\right\},\left\{2,3\right\}\rangle .$$

GGA mutation is simple: an item is moved from one group to another. However, the GGA recombination operator is more complicated. Choose a crossing section in each parent, for example $\langle \left\{1\right\},\left\{3,6\right\}\rangle$ from the $1^{\text{st}}$ parent and $\langle \left\{1,4\right\}\rangle$ from the $2^{\text{nd}}$ parent. Then inject the $1^{\text{st}}$ crossing section into the $2^{\text{nd}}$ parent at a random point, and vice-versa:

$$\langle \left\{1\right\},\left\{3,6\right\},\underset{\_}{\left\{1,4\right\}},\left\{2,5\right\},\left\{4\right\}\rangle \langle \left\{5,6\right\},\left\{1,4\right\},\underset{\_}{\left\{1\right\}},\underset{\_}{\left\{3,6\right\}},\left\{2,3\right\}\rangle .$$

Next remove any repeated objects that were already in the receiving parent:

$$\langle \varnothing ,\left\{3,6\right\},\left\{1,4\right\},\left\{2,5\right\},\varnothing \rangle \langle \left\{5\right\},\left\{4\right\},\left\{1\right\},\left\{3,6\right\},\left\{2\right\}\rangle .$$

Finally remove any empty sets:

$$\langle \left\{3,6\right\},\left\{1,4\right\},\left\{2,5\right\}\rangle \langle \left\{5\right\},\left\{4\right\},\left\{1\right\},\left\{3,6\right\},\left\{2\right\}\rangle .$$

These are the offspring. Clearly, both offspring have much in common with both parents, as 5 of the 7 parent groups survive in the offspring: $\left\{1\right\},$ $\left\{4\right\},$ $\left\{1,4\right\},$ $\left\{2,5\right\}$ and $\left\{3,6\right\}.$ In the first example of Section 2.1 it is easily verified that both offspring represent the same grouping as the parents, as one would expect. This property of the GGA injection-based recombination makes it much more likely that offspring have similar fitness to parents, which in turn helps the GGA to iteratively improve the chromosome population.

It might be noticed that the GGA problem representation still contains symmetry: any grouping still has multiple representations, obtained by permuting the subsets in the ordered list. But the genetic operators are almost independent of this ordering so it is almost irrelevant. The only effect of the ordering is to limit the set of possible injections: in the second example of Section 2.1 we cannot inject a non-existent crossing section for example such as $\langle \left\{1\right\},\left\{4\right\}\rangle$ from parent 1 because those two groups are not adjacent. This limit is removed by an additional genetic operator called inversion which selects a section of the chromosome and reverses it. For example

$$\langle \left\{1\right\},\left\{2\right\},\underset{\_}{\left\{3,6\right\}},\underset{\_}{\left\{4\right\}},\underset{\_}{\left\{5\right\}}\rangle \to \langle \left\{1\right\},\left\{2\right\},\underset{\_}{\left\{5\right\}},\underset{\_}{\left\{4\right\}},\underset{\_}{\left\{3,6\right\}}\rangle .$$

This does not change the grouping represented by the chromosome, but reordering the groups in the chromosome makes all injections possible.

Injection, mutation and inversion are the common operators used in GGAs, but there is no canonical algorithm. Instead GGAs tend to be tailored for specific applications, and in principle any GA can be adapted to grouping problems by using grouping operators. In Section 2.3 we design a GGA for our problem.

2.2.1  Note on implementation

For the sake of clarity the descriptions in Section 2.2 omit implementation details, for example the fact that GGA chromosomes are usually implemented in two parts (or sometimes more). The first part uses a classical representation as above, while the second part lists the nonempty groups as a permutation. Injection occurs on the second parts of parent chromosomes and some renaming of groups is necessary.

Typically we decide in advance the number of iterations which we wish to run the algorithm for. This should be enough to give the GGA a chance to converge on the optimum solution after the mutation and inversion probabilities have been applied. If, however, the optimum solution is known beforehand the algorithm can be set to stop at this point.

The number of iterations is usually decided with experience of using the GGA on similar target and auxiliary variables for similar datasets, or with the existing dataset and target and auxiliary variables. It may require a number of experiments using the GGA (or GA) before the number of iterations needed to reach convergence can be estimated. In fact there is a possibility that either the GGA or GA would appear to have reached convergence after a set number of iterations, but instead have become trapped in a local minimum. It may be useful to increase the number of iterations and try alternative mutation probabilities in order to be certain that it has converged on a global minimum.

This implies a number of trial runs before finally deciding the parameters under which to run the algorithms. Therefore the fact the GGA has been shown to attain convergence quicker than the GA is likely to compound the improvement in total processing time. In the experiments described below we keep the number of iterations small as we want to demonstrate the ability of the GGA to converge on a solution within that number of iterations.

We use either the mutation settings specified in the examples provided by (Ballin and Barcaroli, 2013) or the default mutation settings in (Barcaroli, 2014). We apply grouping genetic operators and inversion to the GA designed by (Ballin and Barcaroli, 2013): it is the grouping genetic operators that make it a GGA. Thus we compare the performance between the different GA and GGA genetic operators rather than experiment with parameters such as varying the number of iterations, chromosome population size, mutation probability, or elitism rate.

The mutation probability can be selected in advance by the user. Typically, the probability of mutation should be such that it increases the chance of the GGA leaving a local minimum, but not disrupt the natural evolution of chromosomes from one generation to the next. On the other hand we have fixed the inversion probability at 0.01, because this is enough to maintain diversity.

The size of the chromosome population can be decided by trial and error. It is advisable to consider the evaluation time of each chromosome when setting the size: if there are too many chromosomes in the set, it might take an extra long time to move from one iteration to the next, and we found that the bethel.r algorithm (i.e., the Bethel-Chromy evaluation algorithm in (Barcaroli, 2014)) takes several seconds to evaluate even one chromosome for the larger datasets we used in this paper (we discuss this further in Section 4).

For further details on the implementation of GGAs (e.g., elitism rate) we refer the reader to papers such as (Falkenauer, 1998).

2.3  Application to the joint stratification and sample allocation problem

As mentioned above our GGA is based on the GA described in (Ballin and Barcaroli, 2013) and represented in $R$ in the SamplingStrata package (Barcaroli, 2014), but with grouping operators and chromosomes instead of the classical versions. This change is the only novelty of our algorithm (except for the optimisation described in Section 4) but its effect on performance is large. We inserted the GGA into a modified version of the function called rbga.r from the genalg R package (Willighagen, 2005). It is designed to work with the other functions in SamplingStrata, and is applied to the joint stratification and optimum sample size problem. The GGA is summarised in Figure 2.1.

Following the problem statement in (Ballin and Barcaroli, 2013) we summarise the cost function as follows:

$$C\left(n_1\mathrm{,}\dots \mathrm{,}{n}_H\right)\mathrm{<mo>=</mo>}{C}_0+{\displaystyle \sum _{h\mathrm{<mo>=</mo>\; 1}}^H{C}_h{n}_h},$$

where $C_0$ is the fixed cost and $C_h$ is the average cost of interviewing one unit in stratum $h$ and $n_h$ is the number of units, or sample, allocated to stratum $h.$ In our analysis $C_0$ is set to 0, and $C_h$ is set to 1. The expectation of the estimator of the $“g^{\text{th}}”$ population total is:

$$E\left({\widehat{T}}_g\right)\mathrm{<mo>=</mo>}{\displaystyle \sum _{h\mathrm{<mo>=</mo>\; 1}}^H{N}_h{\overline{Y}}_{h\mathrm{,}g}}\left(g\mathrm{<mo>=</mo>\; 1,}\dots \mathrm{,}G\right),$$

where ${\overline{Y}}_{h\mathrm{,}g}$ is the mean of the $G$ different target variables $Y$ in each stratum $h.$ The variance of the estimator is given by:

$$\text{VAR}\left({\widehat{T}}_g\right)\mathrm{<mo>=</mo>}{\displaystyle \sum _{h\mathrm{<mo>=</mo>\; 1}}^H{N}_h^2}\left(1-\frac{n_h}{N_h}\right)\frac{S_{h\mathrm{,}g}^2}{n_h}\left(g\mathrm{<mo>=</mo>\; 1,}\dots \mathrm{,}G\right).(2.1)$$

The upper limit of variance or precision $U_g$ is expressed as a coefficient of variation $\text{CV}$ for each ${\widehat{T}}_g:$

$$\text{CV}\left({\widehat{T}}_g\right)\mathrm{<mo>=</mo>}\frac{\sqrt{\text{VAR}\left({\widehat{T}}_g\right)}}{E\left({\widehat{T}}_g\right)}\le U_g.(2.2)$$

The problem can be summarised as follows:

$$\begin{array}{ll}\min n\hfill & ={\displaystyle \sum _{h\mathrm{<mo>=</mo>\; 1}}^H{n}_h}\hfill \\ \text{CV}\left({\widehat{T}}_g\right)\hfill & \le U_g.\hfill \end{array}$$

• Previous
• Article main page
• Next