GALCO

GENETIC ALGORITHMS WITH LIMITED CONVERGENCE

Introduction
The main goal of the proposed algorithm called the genetic algorithm with limited convergence (GALCO) is to maintain the fruitful diversity of the evolved population during the whole run and so to preserve a GA from getting stuck in local optima. To achieve this a concept of imposing limits on the convergence of the population is adopted.

The algorithm inherits most of the features from the standard GA working on a binary representation. In fact it is a type of the incremental GA where only one crossover operation is performed in each generation cycle (the step from the old to the new population). As such it uses a standard se- lection strategy to choose the parents, a classical crossover operator (2-point crossover is used here, as commented further) for generating new chromo- somes, and special rule for inserting of the offspring chromosomes into the population. What makes the GALCO unique is just the way the convergence of the population is maintained within specified boundaries.

There is a limit imposed on the maximum convergence of every position of the representation. Let us denote the vector of genes at the i-th position of the chromosome over the whole population as the i-th column of the population. Then the limit is expressed as a symmetric integer interval [PopSize/2-C, PopSize/2+C], where PopSize is the population size. The parameter C denotes the convergence rate. Its value is the input parameter to the algorithm and can be chosen from the range 0 to PopSize=2. Strictly speaking 2xC defines the maximal allowed difference of the frequency of ones and zeros in every column of the population. So the ratio of ones and zeros must be 1 : 1 during the whole run in the case of C = 0. This is the principal condition of the algorithm. To keep the condition valid during the whole run a special insertion rule for incorporating offspring into the population has been used.

--------------------------------------------------------------------------------
Step 1      Generate initial population of size PopSize
Step 2      Choose parents
Step 3      Create offspring using the 2-point crossover
Step 4      Insert the offspring into the population according to the following rule
               if (max(child1,child2) > max(parent1,parent2))
               then replace both parents with the children
               else{
                     find(current_worst)
                     replace_with_mask(child1, current_worst)
                     find(current_worst)
                     replace_with_mask(child2, current_worst)
               }
Step 5      if (not finished) then go to Step 2
--------------------------------------------------------------------------------
A functional schema of the GALCO algorithm

The functional scheme of GALCO is shown in Figure above. First an initial population of chromosomes is generated. It is made sure that the distribution of ones and zeros does not violates the convergence constraint at any position of the chromosome. Typically, the evolution starts from maximally diverse population i.e. every column of the population consist of an equal number PopSize/2 of ones and zeros regardless of the chosen convergence range.

The body of the algorithm is through the steps 2-5, which realizes the generational cycle of the incremental GA. In step 2 a pair of parental chromosomes is chosen according to the used selection strategy (a tournament selection is used here). Then the parents are crossed over using the 2-point crossover to yield two new chromosomes. Note that there is no crossover rate parameter needed since the parents always undergo this operation. There is no explicit mutation operator used in the algorithm neither.

The most important action of the algorithm comes in step 4. Here the offspring is inserted to the population according to the insertion rule, which follows two main objectives:
   (i) to use as much of the genetic material of the newly generated individuals as possible and
   (ii) not to violate the maximal allowed convergence rate.

In practice this is implemented so that both children replace their parents iff at least one of the children has better fitness than both parents. Otherwise the children replace the worst individuals of the current population using the replace-with-mask operator described below.

The effect of replacing the parents with both offspring in the "then branch of the rule" is such that the distributions of ones and zeros do not change in any column of the population. This is obvious since the genetic material of parents and their children is invariant through the application of the crossover operation. Thus it is ensured that if the old population does comply with the desired convergence range the new population must comply with the convergence range as well.

Slightly more complicated situation arises when the children are both of rather poor quality, the "else branch of the rule". Replacing the parents with their offspring irrespectively of the offspring quality would cause problems with a slow convergence to the optimal solution. Note that the case the parents produce fitter offspring is much less frequent than the opposite case i.e. that both offspring are worse than the better parent. So the breeding phase (crossover plus replacement of parents) would be in most cases counterproductive. The evolution should not be restricted only to those rather singular moments when the parents breed something better than they are. Some reasonable way to use the newly generated chromosomes whatever good they are might be very useful since it would considerably increase the rate of sampling of the search space.

The trade-off between exploration power and exploitation ability of the algorithm is accomplished by placing the generated offspring into the population using the replace-with-mask operator. The operation should be seen as a merging of two chromosomes rather than an inserting of a new one in the population. The least fit chromosomes are chosen as replacements in order to reduce the loss of quality. The operator works so that it traverses the chromosome of the replacement individual and replaces its i-th gene with a corresponding gene of the child's chromosome if and only if such a change is legal. So the bit is replaced if this does not make the frequency of ones and zeros of the corresponding column of the population to exceed the allowed convergence range. Otherwise the original gene of the replacement retains in the population.

Apparently the greater the convergence rate is the more of the offspring's genes are used in the early phase of the run and vice versa.

Experimental results

Mean convergence curves obtained with the optimal convergence rate C, convergence rate C=1 and C=0 on the 200-bit problem composed of 4-bit deceptive building blocks.

Comparison of the convergence characteristics of GALCO and Standard Iterational GA (SIGA) on the deceptive problem.

The final distribution of 100 solutions after 500000 fitness function evaluations achieved on a multimodal problem.

Conclusions
   - An efficient approach for preserving population diversity - the population is explicitly prevented from becoming too homogenous by simply imposing limits on its convergence.
   - A specific replacement strategy is used to keep the desired distribution of ones and zeros during the whole run.
   - The best performance of the algorithm was achieved with rather low convergence rate (C << PopSize/2).
   - Due to its replacement-recombinative component the algorithm is able to go on to generate new sample points of the search space even after the global optimum has been found.
   - Representatives of various optima can co-exist in the population during the evolution.
   - It does not require any tuning of the mutation or crossover probabilities.

Publications:

1)	Kubalik, J., Rothkrantz, L.J.M., Lazansky, J.: Genetic Algorithms with Limited Convergence. In Information Processing with Evolutionary Algorithms: From Industrial Applications to Academic Speculations. New York: Springer, 2005, p. 233-254. ISBN 1-85233-866-0.

top

back to my research page