1 INTRODUCTION

One of the benefits of using an evolutionary algorithm is that it opens up the possibility of using a crossover operator. In early Genetic Algorithms single-point or two-point crossover were used to recombine pairs of strings [1-3]. Later multi-point crossover [4] and uniform crossover [5-7] were studied. A short controversy raged over which of these operators was best. Of course, this will depend on the problem being treated. Indeed, for many problems it is necessary to design a problem specific crossover operator [8]. Nevertheless, an important practical issue is to identify characteristics of crossover which allow for a more rational choice of crossover operator.

In this paper we study one such aspect of crossover, namely how efficiently it mixes the solutions. This is a problem independent aspect of crossover, which tells us about how quickly the population will explore the space of solutions. To study this we consider a problem which can be viewed as generalized card shuffle. We start with a pack of cards consisting of N suits with L cards in each suit. The pack is divided into N hands sorted according to their suit. The hands are then shuffled by pairing them and swapping cards using a uniform, single-point or multi-point crossover strategy. We study how the hands become shuffled over time. In the language of Genetic Algorithms the hands correspond to strings or chromosomes, the cards to genes, while the suits correspond to different alleles.

We define an order parameter to measure the degree of mixing within the population. As the strings become mixed the order parameter decays to the value of a totally mixed population. We define the mixing rate to be the asymptotic rate at which the order parameter decays. The mixing rates for single-point, two-point and uniform crossover are calculated analytically. As one might expect, uniform crossover mixes faster than multipoint crossover which mixes faster than single-point crossover, however, the difference in the rate between uniform and single-point crossover, is more dramatic than one might naively expect. This does not, of course, imply that uniform crossover is always best. Another important factor in choosing a crossover operator is its average cost due to the disruption it causes. A measure of this cost might be the average loss in fitness caused by crossover (this ‘interface energy’ was computed, for example, in [9], 10] for one particular problem). For problems where the spatial position of the loci have a meaning, uniform crossover may be too disruptive, whereas single-point crossover may produce only a small change in the fitness. However, this cost will depend on the problem being considered. In contrast, mixing of the allele between strings is problem independent.

On completing this paper, a different approach to the same problem was brought to my attention. This approach by Rabani, Rabinovich and Sinclair [11] considered crossover to be a special case of a quadratic dynamical system (QDS)—a generalization of a Markov chain to a process depending on combining two members of a population. In contrast to Markov chains there is no known procedure for solving a QDS. The authors, however, develop tight bounds on the convergence times for the probability distribution of a subclass of QDS to its equilibrium distribution. They use this result to obtain mixing rates for different crossover operators. Rabani et al.’s approach is extremely powerful, but has a different character to the approach taken here. In this paper, we consider the evolution of a single statistical property of the population, namely a measure of the degree of shuffling. By concentrating on this simple quantity the problem simplifies considerably. For example, we can quite easily obtain an exact expression for the evolution of this quantity for uniform crossover in a finite population at each generation. This is a more detailed, although less general result than that obtained by Rabani et al. The two approaches have different strengths. Rabani et al. approach gives a rigorous mathematical framework. Obtaining useful results from such a framework is notoriously hard. The fact that they succeed in finding such a result is very impressive. The tack taken in this paper, which I would not pretend to be of comparable significance to Rabani et al.’s general result, is to find a statistical quantity for which we can compute the dynamics. This approach, though often only approximate, allows complex systems to be modelled which are beyond the scope of a rigorous framework—modelling of more complex systems is discussed in the final section of this paper.

4 DISCUSSION

We have obtained analytic expressions for the mixing rate for uniform, single-point and two-point crossover. In figure 2 the analytic expressions are plotted for a population size and string length of 100. The curve for uniform crossover is exact. Those for singlepoint and two-point crossover are approximate, but for these parameters the theory and simulations differ by less than 5 × 10^− 4.

Although at the first step, the crossover strategies appear comparable for single-point, two-point and uniform crossover with a = 1/2, the shuffling rate continues to reduce rapidly for uniform crossover, but slows down very considerably for single-point and two-point crossover. Two-point crossover shuffles at twice the rate of single-point crossover. In fact, if we rescaled the time so that one generation of two-point crossover equals two generations of single-point crossover the two curves for Q(t) lie almost on top of each other. Multi-point crossover, in which n-points are chosen at random and where every other region is taken from the second parent, will extrapolate between the two-point and uniform crossover curves.

For uniform crossover the mixing rate is 1 – 2a (l − a) (ignoring finite population corrections). This is maximized when the bias, a, is set to 1/2. For a  1/2 the mixing rate will be much reduced and the initially reduction in the order parameter will be much slower than that for single-point or two-point crossover. However, provided a  1/L the asymptotic mixing rate will be much faster for the biased uniform crossover than single or two-point crossover. Thus after a long enough period biased uniform crossover will achieve a better mixing than its rivals. This is illustrated in figure 2 where we have also plotted Q(t) for uniform crossover with a = 1/10.

One referee of this paper asked the pertinent question, so what? The answer to this is that modelling has both short and long term objectives. The short term objective is to find an accurate description of the system being studied. The much bolder long term objective is to obtain an understanding of the important features that determine the efficiency of the search performed by a Genetic Algorithm, with the hope of creating a principled approach to designing GAs. This is an accumulative process which can be achieved by understanding the detailed behaviour of simple systems. In this paper we identified a measure of the degree of mixing which allowed us to compute the mixing rates. The result that uniform crossover is faster than two-point crossover which in turn is faster than single-point crossover is, of course, not surprising. A result which was more unexpected (at least, for the author) was that uniform crossover even with a very strong bias towards one parent still has a much faster asymptotic mixing rate than single-point crossover. The mixing rates are important as they provide a measure for how fast crossover causes the population to decorrelate from its initial state. The shorter the decorrelation time the faster the exploration of the search space. Asymptotically single-point crossover is no faster than a mutation of one allele per generation (they both require touching each loci, which takes of order L log(L) trials), while uniform crossover is dramatically faster, taking $\mathcal{O}$(Iog(L)) steps. These results agree with Rabani et al., although we have also calculated how the degree of mixing changes for intermediate times.

To understand what crossover does in a GA, however, necessitates the modelling of the interaction of crossover with the other operators such as selection and mutation. This is part of the long term objective of modelling, of which this paper is only a small contribution. A statistical mechanics analysis of GAs has been carried out for various simple problems (e.g. [9, 10, 12-21]), which use statistical properties of the population to model the system dynamics. However, these studied did not treat the problem of spatial correlations that arise when using single or multi-point crossover. Recently the author has completed a paper treating the dynamics of a GA with two-point crossover [22]. The additional spatial correlations considerably complicate the analysis—not because of the difficulty of modelling crossover (which can be done exactly), but because of the difficulty in estimating the effect of selection on the spatial correlations produced by crossover. This paper uncovers a small part of the story of crossover. It shows how the amount of mixing caused by crossover evolves over generations. How important this is to the larger picture only time will tell.

APPENDIX: TOTALLY MIXED STATE

The overlap parameters $M_{\alpha }^{\mu }\left(t\right)=L{m}_{\alpha }^{\mu }\left(t\right)$ define a partitioning of the L alleles in string μ amongst the N initial strings. Total mixing corresponds to a random partitioning so that the probability of the overlaps being (M₁^μ, M₂^μ, …, M_N^μ) is given by the multinomial distribution

$\frac{1}{N^L}\frac{L!}{M_1^{\mu }!M_2^{\mu }!\cdots M_N^{\mu }!}\left[{\displaystyle \sum _{\alpha =1}^N{M}_{\alpha }^{\mu }=L}\right]\text{.}$

To find averages over a multinomial probability distribution we note that the multinomial coefficients appear in the following expansion

${\left({\displaystyle \sum _{\alpha =1}^N{x}_{\alpha }}\right)}^L={\displaystyle \sum _{\left\{M_{\alpha }\right\}}L!}\left({\displaystyle \prod _{\alpha =1}^N\frac{x_{\alpha }^{M_{\alpha }}}{M_{\alpha }!}}\right)\left[{\displaystyle \sum _{\alpha =1}^N{M}_{\alpha }=L}\right]$

where the sum is over all integer values of the M_α’s. We can use equation (24) to compute averages over the multinomial distribution using the observation

$\begin{array}{l}{\left.〈M_{\alpha }〉=\frac{1}{N^L}\frac{\partial }{\partial x_{\alpha }}{\displaystyle \sum _{\left\{M_{\alpha }\right\}}L!}\left({\displaystyle \prod _{\alpha =1}^N\frac{x_{\alpha }^{M_{\alpha }}}{M_{\alpha }!}}\right)\left[{\displaystyle \sum _{\alpha =1}^N{M}_{\alpha }=L}\right]\right|}_{x_{\alpha }=1}\\ \begin{array}{ccc}\hfill \hfill & \hfill \hfill & \hfill =\frac{\partial }{\partial x_{\alpha }}\frac{{\left({\displaystyle {\sum }_{\alpha =1}^N{x}_{\alpha }}\right)}^L}{N^L}=\frac{L{\left({\displaystyle {\sum }_{\alpha =1}^{N}1}\right)}^{L-1}}{N^L}=\frac{L}{N}\hfill \end{array}\end{array}$

Similarly

$\begin{array}{l}{\left.〈M_{\alpha }\left(M_{\alpha }-1\right)〉=\frac{{\partial }^2}{\partial x_{\alpha }^2}\frac{{\left({\displaystyle {\sum }_{\alpha =1}^N{x}_{\alpha }}\right)}^L}{N^L}\right|}_{x_{\alpha }=1}\\ \begin{array}{ccccc}\hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill =\frac{L\left(L-1\right){\left({\displaystyle {\sum }_{\alpha =1}^{N}1}\right)}^{L-2}}{N^L}=\frac{L\left(L-1\right)}{N^2}\text{.}\hfill \end{array}\end{array}$

From the definition (8) and assuming totally shuffling

$Q\left(\infty \right)=\frac{N}{L^2}〈{\left(M_{\alpha }^{\mu }\right)}^2〉=\frac{N+L-1}{NL}$

APPENDIX: STATISTICS OF BLOCK SIZES

We need to calculate 〈(x_n^μ(t))²〉 and 〈x_n^μ(t) x_m^μ(t)〉. We first abstract this problem. We consider a string with L sites which is split into R regions where the position of each region boundary is independently chosen. We then ask what is the probability distribution for the sizes of the regions? For this calculation we can drop the superscript μ and the time index as these are irrelevant. Thus the length of a region we denote by x_n. Our single constraint is

${\displaystyle \sum _{n=1}^R{x}_n=L}\text{.}$

We can write the probability of a partitioning x = (x₁, x₂,…, x_R) as

$\begin{array}{cc}\hfill p\left(\mathrm{x}\right)=\frac{1}{Z}{\mathrm{e}}^{-{\displaystyle {\sum }_n{x}_n}}\left[{\displaystyle \sum _{n=1}^R{x}_n=L}\right],\hfill & \hfill Z=\underset{\left\{x\right\}}{\mathrm{T}\mathrm{r}}{\mathrm{e}}^{-{\displaystyle {\sum }_n{x}_n}}\left[{\displaystyle \sum _{n=1}^R{x}_n=L}\right]\hfill \end{array}$

where we have used the shorthand

$\underset{\left\{\mathrm{x}\right\}}{\mathrm{T}\mathrm{r}}\equiv {\displaystyle \sum _{x_1=1}^{\infty }{\displaystyle \sum _{x_2=1}^{\infty }\cdots {\displaystyle \sum _{x_R=1}^{\infty }}}}$

(p(x) is not a multinomial distribution as there are no combinatorial factors preferring equi-paxtitioning.) In the definition of p(x) we have included the term

${\mathrm{e}}^{-{\displaystyle \sum _n{X}_n}}$

which is a constant in light of the Kronecker delta, however, it will act as a regularization term in what follows.

Our aim is to find

$〈x_n^2〉=\underset{\left\{x\right\}}{\mathrm{T}\mathrm{r}}{x}_n^{2}p\left(\mathrm{x}\right)\text{.}$

We can replace the Kronecker delta with its integral representation

$\left[{\displaystyle \sum _{n=1}^R{x}_n=L}\right]={\displaystyle {\int }_{-\mathrm{\pi }}^{\mathrm{\pi }}{\mathrm{e}}^{i\mathrm{\lambda }\left({\displaystyle {\sum }_{n=1}^{\mathrm{R}}{\mathrm{x}}_n-L}\right)}\frac{\mathrm{d}\mathrm{\lambda }}{2\mathrm{\pi }}}\text{.}$

Giving

$〈x_n^2〉=\frac{1}{Z}{\displaystyle {\int }_{-\mathrm{\pi }}^{\mathrm{\pi }}{\mathrm{e}}^{i\mathrm{\lambda }L}\underset{\left\{x\right\}}{\mathrm{T}\mathrm{r}}{x}_n^2{\mathrm{e}}^{-\left(i\mathrm{\lambda }+1\right){\displaystyle {\sum }_{n=1}^R{x}_n}}\frac{\mathrm{d}\mathrm{\lambda }}{2\mathrm{\pi }}\text{.}}$

We can perform the sums (notice the regularization term ensures that sums converge) to give

$\begin{array}{l}〈x_n^2〉=\frac{1}{Z}{\displaystyle {\int }_{-\mathrm{\pi }}^{\mathrm{\pi }}{\mathrm{e}}^{i\mathrm{\lambda }L}}\left(\frac{2{\mathrm{e}}^{2i\mathrm{\lambda }+2}}{{\left({\mathrm{e}}^{i\mathrm{\lambda }+1}-1\right)}^{R+2}}-\frac{{\mathrm{e}}^{i\mathrm{\lambda }+1}}{{\left({\mathrm{e}}^{i\mathrm{\lambda }+1}-1\right)}^{R+1}}\right)\frac{\mathrm{d}\mathrm{\lambda }}{2\mathrm{\pi }}\\ \begin{array}{cc}\hfill \hfill & \hfill =\hfill \end{array}\frac{1}{Z}{\displaystyle {\int }_{-\mathrm{\pi }}^{\mathrm{\pi }}{\mathrm{e}}^{i\mathrm{\lambda }L}}\left(\frac{2}{R\left(R+1\right)}\left(-D_{\mathrm{\lambda }}^2+{\mathrm{iD}}_{\mathrm{\lambda }}\right)-\frac{\mathrm{i}}{\mathrm{R}}{\mathrm{D}}_{\mathrm{\lambda }}\right)\frac{1}{{\left({\mathrm{e}}^{i\mathrm{\lambda }+1}-1\right)}^R}\frac{\mathrm{d}\mathrm{\lambda }}{2\mathrm{\pi }}\end{array}$

where $D_{\mathrm{\lambda }}=\partial /\partial \mathrm{\lambda }$. We can integrate by parts so that the remaining integral cancels with the normalization factor Z. We thus obtain

$〈x_n^2〉=\frac{L\left(2L-R+1\right)}{R\left(R+1\right)}$

We can calculate (x_n x_m) in a similar way. However it is easier to observe that

$L^2={\left({\displaystyle \sum _n{x}_n}\right)}^2={\displaystyle \sum _n{x}_n^2}+{\displaystyle \sum _{n\ne m}{x}_n{x}_m}$

Thus

$〈x_n{x}_m〉=\frac{L-〈x_n^2〉}{L-1}\text{.}$