An Analysis on Crossovers for Real Number Chromosomes in an Infinite Population Size

1 Introduction

A lot of experimental and theoretical researches on Evo­ lutionary Algorithms (EA) have been recently reported. In the theoretical results, most of them are ones for EAs using bit strings as chromosomes, in particular, the Simple Genetic Algorithms (SGA). These are based on the theory of Finite Markov Chain [Dawid, 1994; Davis and Principe, 1993; Nix and Vose, 1992; Rudolph, 1994] because the SGA uses bit strings with a constant length. However, the state spaces of EAs using real num­ ber chromosomes are infinite and uncountable sets and there are difficulties different from the SGA to investigate the time evolution. .

Rudolph derived the conditions for the convergence m EAs with general state spaces and a finite population size using the concept of Markov Kernel [Rudolph, 1996]. In this result, however, the selection and mutation affects the convergence and the effect of the crossover is not considered.

On the other hand, Qi and Palmieri derived the prop­ erties of the genetic operations including a uniform crossover in EAs with an infinite population size [Qi and Palmieri, 1994a; 1994b]. In these results, the changes of the population density in the infinite population size through the genetic operations are the main object. In this paper, we also focus our attention on the change of the population density through crossovers.

In the case of EAs using discrete value chromosomes, Booker theoretically showed the properties of crossovers based on the recombination distribution inspired by Geiringer's result, a kind of the probability at which schemata is generated by crossovers [Booke~, 1992]. Our analysis in the case of EAs using real number chromo­ somes is based on the relation between the population densities before and after crossovers, and the change of the mean values and covariances on loci. For this purpose, we have given a framework of the descrip­ tion for the change of the distribution of the popula­ tion through crossover, called Linear Crossover [Nomura, 1997]. The previous version of this framework did not include one-point, multi- point, or uniform crossover. In this paper, we extend this framework to the one which includes various crossovers which have been proposed, one-point, multi-point crossovers, uniform crossover, average crossover [Davis, 1990], the Unfair Average Crossover we have proposed [Nomura and Miyoshi, 1995; 1996], and the R 3 operator [Radcliffe, 1991]. We verify the properties of these crossovers based on the results.

2 General Framework for Description of Crossovers

2.1 Basic Formulation

In EAs with real value chromosome, each individual is represented as a vector in the Euclid space Rm. Given two parents X and Y ( E Rm), we assume that crossovers produce two offsprings X' and Y' from the parents.

In this paper, we consider the crossover represented in the following form:

Here, (a , b)= (a1 , . .. , am, b1 , ... , bm) is a stochastic vari­ able on R 2 m whose distribution function is s(a, b). More­ over, we assume the following condition:

The form in (1) is represented by the following linear transformation on R 2 m:

(2) represents that the production of the offsprings by (a, b) is done at the same probability as that by (b, a) and the probability density of a is the same as that of b. (3) represents that the linear transformation on R 2 m in (4) has the inverse transformation if s(a, b) has a positive value.

Now, It is easily shown that the following statements for C;(a, b) and F(a, b) are obtained:

2.2 Representation of Various Crossovers based on the Framework

We can represent one-point, uniform crossover, the av­ erage crossover, the unfair average crossover, and the IP operator using the above framework in the following way.

One-point Crossover

One-point crossover produces two offsprings from a pair of parents by randomly selecting a point on the chromo­ somes and replacing the former and latter half of each parent from the point at a probability r. Thus, we rep­ resent it in the following form:

Thus, s(a, b) in this case is represented in the following form:

Uniform Crossover

Uniform crossover produces two offsprings from a pair of parents by uniformly replacing the elements on each lo­ cus of the parents at a probability r. Thus, we represent it in the following form:

Thus, s(a, b) in this case is represented in the following form:

Average Crossover

The average crossover produces one offspring from a pair of parents by averaging the elements on each locus of the parents at probability r [Davis, 1990]. By assuming that another offspring is produced as a copy one of the parents, we represent it in the following way:

Thus, s(a, b) in this case is represented in the following form:

Unfair Average Crossover

The Unfair Average Crossover [Nomura and Miyoshi, 1995; 1996] produces two offspring from a pair of par­ ents at probability r by the following way:

Here, a is a constant and j is randomly selected among {0, 1, ... , m } . Thus, we represent it in the following form:

Thus, s(a, b) in this case is represented in the following form: ·

R 3 Operator

The R 3 operator produces offsprings from a pair of the parents by picking any point in the hypercuboid includ­ ing the parents at probability r [Radcliffe, 1991]. By assuming that one offspring is produced as a copy one of the parents and another is produced as the above way, we represent it in the following way:

Thus, s(a, b) in this case is represented in the following form:

3 Change of Distribution of Population through Crossovers

In this paper, we assume that the population of the G A consists of infinite individuals. Then, the statistical state of the population is represented by the population den­ sity [Qi and Palmieri, 1994b]. In this section, we describe the change of the distribution of the population through the crossover in (1) using the population density.

3.1 Description of Population Density

Now, let q(x) be the population density before a crossover, and p(x) be the population density after the crossover. Moreover, let pxy(x, y) be the density of the parents for the crossover, and Px·y·(x ,y) be the density of the offsprings for the crossover. Because the two parents are selected independently, we obtain . pxy(x,y) = q(x)q(y) . Moreover, p(x) is derived from the joint probability density PX'Y' (x, y) in the following way:

Moreover, we assume that (a , b) and (X, Y) are statis­ tically independent on each other. Then, for any mea­ surable set M on R 2 m , we obtain the following equation from (3) , (4) and the independence between (a, b) and (X,Y) :

In the above equation, we used the variable transforma­ tion (x , y)-+ (x, y)F(a, b) . Thus, we obtain the following relation between PXY and PX'Y':

Thus, we obtain the following equation from (19) and

This <@QUation represents the change of the density through the crossover.

Now, we consider the mean value of a function of the chromosomes f : Rm -+ R on the population density p(x) . From (21), this value is represented in the following equation:

In the above equation, we used the variable transforma­ tion (x , y) -+ (x, y)F(a, b)- 1 .

3.2 Changes of Moments

Based on the above result , we can calculate the change of the mean value of each coordinate and the covariance be­ tween the coordinates on the population density through the crossover.

Substituting x; for g(x) in (22), we obtain the follow­ ing equation which represents the change of the mean value:

that is, the following theorem was proved:

Theorem 1 The mean value on the population density is not changed through the crossover described in ( 1).

Next, we calculate the change of the covariance. We note that for the covariance between functions f and g on a probability density r, V (f, g, r), is described as the following way:

First, we obtain the following equation which repre­ sents the change of the mean value of x;xi , in the same way as the above:

Thus, from (23) and (24), we obtain the following equa­ tion which represents the change of the covariance:

that is, the following theorem was proved:

Theorem 2 For any i and j E {1 , . .. ,m} , the covari­ ance between the i - th and j - th coordinates on the pop­ ulation density after the crossover described in ( 1) is the product of that before the crossover and the constant PC;j = E(2a;a1 - a; - a1, s) + 1.

The values PC;j represent a diversification property of the crossover.

3.3 Application for Some Crossovers

We apply the results in the previous section to the crossovers described in section 2.2 and verify the prop­ erties of them.

From (9)- (18) , we obtain the following result for each crossover method:

One-point Crossover:

Thus, 1 - r $ PC;j $ 1. In particular, PC;; = 1 and PC;1 < 1 if i # j and r > 0.

Uniform Crossover:

If i # j,

Thus, ~ $ PC;1 $ 1. In particular, PCij < 1 if O<r<l.

If i = j,

Average Crossover:

Unfair Average Crossover:

In particular, PC;; = 1 + 2ro 2 .

3.4 Discussion

We can derive the following discussion from the above results.

In the cases of one-point and uniform crossovers, the correlations between the different coordinates in the pop­ ulation decrease through the crossovers and the devia­ tions do not change. Although these results are the ones on only the second order moments, they support the re­ sult which Qi and Palmieri derived [Qi and Palmieri, 1994b], that is, a kind of extension of Geiringer's results in the case of discrete values [Booker, 1992] to the case of real values.

The average crossover makes not only the correlations between the different coordinates but also the deviation in the population decrease.

In the case of the unfair average crossover, the correla­ tions between the different coordinates in the population change dependent on the distance between the coordi­ nate. In particular, it makes the deviation increase and has a diversification property. The W also operator has the same property, although it does not change the corre­ lations between the different coordinates. Thus, the un­ fair average crossover and the W operator are expected to have a high capacity of exploration in combination with the cohesion property of the selection toward the global maximum fitness values [Qi and Palmieri, 1994a] .

4 Conclusion

We investigated the change of the population density through the crossovers. As results, it was shown that the crossovers included by our framework does not change the mean values of the population density, and it propor­ tionally changes the covariances dependent on the prob­ ability of the crossover operations.

As future problems, we must investigate the time evo­ lution of the population density through the selection, crossover, and mutation. Furthermore, we must investi­ gate the change of the fitness in the population through the time, and clarify the convergence properties and the conditions for the convergence in the crossover.

Acknowledgment

The author would like to thank Dr. Katsunori Shimo­ hara at ATR Human Information Processing Research Laboratories for support.