Adaptive Genetic Algorithm with Mutation and Crossover Matrices

1 Introduction

The notion of mutation matrix is used in the development of adaptive genetic algorithm so that the selection process does not require any external input parameter. Numerical examples on knapsack problems indicate that this new adaptive genetic algorithm, called MOGA (mutation only genetic algorithm) is superior to many traditional methods [Ma and Szeto, 2004; Szeto and Zhang, 2005; Zhang and Szeto, 2005]. The idea behind MOGA is that mutation probability is a function of time, fitness ranking of the chromosome, and locus. The dependence is automatically determined by the statistics of the locus and the fitness ranking of the chromosome at the given time. The traditional genetic algorithm is a special case of MOGA in which all the mutation probabilities are fixed. In this paper, we extend the basic idea behind MOGA to include the crossover process. Section 2 reviews the MOGA

formalismwithout crossover. Section 3 focuses on the implementation of the crossover matrix. A brief explanation of the test problem - Ising spin glass is given in section 4, and the test results on Ising spin glass are discussed in section 5.

2 MutationMatrix

Traditional genetic algorithm can be considered as a special case of the mutation only genetic algorithm (MOGA). For a population of NP chromosomes, each encoded by L locus, can be arranged into a population matrix A with NP rows and L columns. Each element of the matrix A has a probability p (0 < p < 1) to undergo mutation. These mutation probabilities Mij (i = 1, ..., NP ; j = 1, ..., L) form a mutation matrix M: Mij is the mutation probability of Aij . In matrix A, each row is one chromosome. The rows are listed in decreasing order of the fitness: fi ≥ fj if i < j .

In traditional genetic algorithm, the best N1 = c1 × NP chromosomes survive (0 < c1 < 1). These survivors produce N2 = c2 × NP children to replace the less fit ones through crossover and/or mutation (0 < c2 < 1 - c1). The remaining N3 = (1c1 - c2)× NP unfit chromosomes are replaced by the same number of randomly generated candidates in order to ensure population diversity. Thus the traditional genetic algorithm can be described by a mutation matrix which has Mij = 0 for the first N1 rows; Mij = m(0 < m < 1) for the next N2 rows; Mij = 1 for all remaining rows. In traditional genetic algorithm, we must input three time independent parameters: c1, c2 and m.

MOGA makes use of the information of the fitness ranking and loci statistics to determine Mij dynamically. It outperforms traditional genetic algorithm in terms of both speed and quality of solution. In this formalism, the mutation matrix is nearly the same as the population matrix A, but with the loci arranged according to the standard deviation σ(j) for the allele distribution. If there are V allele values possible for the locus, (in ordinary binary string representation of genetic algorithm, the possible value of an allele is either 0 or 1, so V = 2), then we define the standard deviation σ(j) for the allele distribution as:

where

Here, C(f(i)) is the fitness cumulative probability of chromosome i, which, as well as fitness, can be considered as an informative measure of chromosome i. High fitness cumulative probability indicates high informative measure. The allele standard deviation σ(j) for each loci can also be regarded as an informative measure. A locus which has a smaller allele standard deviation contains more useful information than the other loci.

At the beginning of the algorithm, chromosomes are randomly generated. Alleles are randomly distributed. Thus the allele standard deviation is not so informative. After generations of evolution, chromosomes acquire higher fitness, good chromosome structures emerge. Then more chromosomes evolve to acquire the good structures. Therefore, a locus with high structural information has a small allele standard deviation.

The presence of the factor of C(f(i)) ∑NP i=1 C(f(i)) in the allele

standard deviation is to take account of the informative usefulness of each chromosome. Loci in chromosomes with high fitness generally are more informative than those in chromosomes with low fitness. With this factor, the allele standard deviation more appropriately reflect the amount of information contained in a particular locus. Our cumulative probability C(f(i)) is defined by

N(g) is the number of chromosomes with fitness value g. Note that C(f) is a non-decreasing function of f where C(fmax) = 1 and ( 1 NP ≤ C(f) ≤ 1).

Therefore, the mutation matrix can be viewed as an arrangement of genes based on the informative measures: the fitness cumulative probability C(f(i)) and the standard deviation σ(j) for the allele distribution. The higher the row is, the more useful information the loci in this row contains. Similarly, the closer to the right side the locus is, the more information it contains. Our mutation is to make use of these two informative measures through the mutation matrix.

In each generation, rows (i.e. chromosomes) in the mutation matrix were first selected for mutation based on the fitness cumulative probability. The probability α(i) to choose the ith row for mutation is defined as,

Therefore, a chromosome with higher fitness has a lower probability to participate in mutation, or in other words, it has higher ability to survive. As the chromosomes are kept in a decreasing order of the fitness: fi ≥ fj if i < j, in the matrix A; α(i) is a non-decreasing function of the row index (chromosome index) i. Thus, α(i) is higher for less fit rows (chromosome). The fittest chromosome, i.e. the first row of the population matrix A, α(i) = 0. It is, hence, never selected for mutation. The worst chromosome, i.e. the last row of A, will mutate with a probability close to unity for large enough NP : α(NP ) = 1 - 1 NP ≈ 1, e.g. α(NP ) = 0.95 for NP = 20.

Next, we employ the fitness cumulative probability again to determine the number Nmg of loci to undergo mutation for the selected chromosomes, each with L loci. Stating the formula for Nmg,

It is obvious that Nmg is also a function of the row index i, or in GA language, the fitness. If a selected chromosome has a high fitness, it has fewer loci to undergo mutation. If a selected chromosome has a low fitness, it has more loci to mutate. Finally, we mutate the Nmg leftmost loci located in the selected rows in the mutation matrix, i.e. the Nmg least informative loci of each chromosome. In this way, most of the informative loci remain and guide the evolution process to the next generation, while most of the less informative loci mutate until they contain more information.

3 Crossover Based on Hamming Distance

With the implementation of the mutation matrix, the crossover is operated implicitly on the population. The implicit crossover deploys the chromosome fitness ranking and the loci statistics in search of solution. Besides these two kinds of information, the Hamming distance can also be used to search the solution. Through the introduction of a crossover matrix, two different explicit crossover methods which employ the information of the Hamming distance are implemented and compared.

The distance matrix H is a square NP × NP matrix with matrix element Hii′ defined by a distance measure between the i-th chromosome, represented by -→Ri which is the i-th row vector of the population matrix A, and the i'-th chromosome -→Ri′ : Hii′ = D(-→R i, -→Ri′). In this paper, we have two different measures for H. The first one is called long Hamming distance crossover (LHDC) in which Hii′ = H L ii′ = Dii′ , where Dii′ is equal to the number of different alleles in these two rows. The second measure is called short Hamming distance crossover (SHDC), with Hii′ = H S ii′ = L - Dii′ . We see that in LHDC, the smaller the distance between two chromosomes i and i' is, the more similar they are. While in SHDC, it is just the opposite: smaller distance indicates low similarity. Note that the matrix H is a symmetric matrix. The diagonal entries of H are zero in LHDC, but equal L in SHDC.

After defining the matrix H, we have to select two chromosomes for crossover. The probabilities to choose the two chromosomes are different, but they are both related to H. One probability is just the fitness cumulative probability, and we call it the first crossover probability PCI(i).

A chromosome, which we call the first chromosome, is first chosen with this first crossover probability. As the row index in H is also the row index in A, chromosome represented by smaller H row index has higher probability to be selected for crossover. Then, the second chromosome is selected with another probability called the second crossover probability. The second crossover probability depends on the chromosome already chosen. If chromosome i (i.e. chromosome with H row index i), is the first chromosome, then the second crossover probability PCII(i′ ) to choose chromosome i' as the second chromosome is:

If the first and the second chromosome are the same, the second one is chosen again until they are both different. Both LHDC and SHDC are single-point crossovers with the crossing points chosen randomly once in a generation. In each generation, a total of NP chromosomes are selected to participate in the crossover. There is no limitation on the number of times a chromosome can take part in crossover in one generation. Later, the fittest NP chromosomes are selected to form a new generation from the pool of NP original chromosomes and the NP children chromosomes produced by crossover.

In each generation, we first carry out crossover and then mutation. At the end of crossover, i.e. when the fittest NP chromosomes are selected, as well as at the end of the mutation, we update the fitness and cumulative fitness probability for all the chromosomes in the population.

4 Application: One-Dimensional Ising Spin Glass

The algorithm is applied to find the minimum energy of a 1D periodic Ising model consisting of Nloci spins (Nloci = 10, 11, 15, 20, 25 and 30). Each spin can be either up or down, represented by '1', or '-1' respectively. The interaction energy between a pair of neighbouring Ising spin is randomly generated in the range [-1,1]. The problem is to find the minimum of the energy

for a given set of interaction energy . For each value of Nloci, two different sets of interaction energy were generated. For each set of interaction energy, the exact minimum energy Emin was first computed by exhaustive search over 2Nloci spin configurations. The program is then executed 400 times with a fixed population size of NP = 20 chromosomes. Each execution is regarded as one sample. An execution stops when an acceptable solution is found or the maximum allowed generations NMA = 250000 is reached. An acceptable solution is a candidate solution which is within 1% tolerance of the exact minimum energy Emin. When no solution can be found within NMA generations in an execution, the execution is considered as a failure sample.

5 Results

We have compared the efficiency of three adaptive genetic algorithms (MOGA, LHDC and SHDC) on the spin glass problem. Table 1 summarizes the average generation to reach solution and the number of failure. Both GAs with crossover, LHDC and SHDC, outperform MOGA in terms of average generation and number of successful searches. Moreover LHDC gives the best performance.

The two GAs with crossover is better due to the information exchange between chromosomes. In LHDC, fit chromosome is selected and crossover with a very different chromosome to generate two new chromosomes. This expands the exploration space and minimizes the chance of premature convergence. In SHDC, fit chromosome is selected and crossover with a similar one. This exploits the local search process and speeds up convergence. The results suggest that a second crossover probability emphasizing the exploration of search space is better for the Ising-spin-glass-like problem (i.e. knapsack-type problem)[Kellerer et al., 2004].

6 Conclusion

Three different ways to implement the adaptive genetic algorithm are tested and compared using the one-dimensional Ising model for spin glass as the testing problem. The results show that LHDC is best and that all three methods are parameter-free. Since MOGA outperforms other algorithms, including dynamic programming [Kellerer et al., 2004; Simoes and Costa, 2001; 1999], for solving the knapsack problem, our test shows the superiority of LHDC in this kind of search problem. This work also provides a matrix formulation of parameter free adaptive genetic algorithm with both mutation and crossover.

Acknowledgments

N.L.Law and K.Y. Szeto acknowledge interesting discussion from C.W. Ma. K.Y. Szeto acknowledges the support of RGC grant 603203.