Genetic Algorithms as Global Random Search Methods: An Alternative Perspective

Genetic Algorithms as Global Random Search Methods: An Alternative Perspective Charles C. Peck & Atam P. Dhawan Summary By: Ilan Shacham

Overview

This article attempts to describe a mathematical method of describing Genetic Algorithms, and use this method for better describing the behavior of these algorithms, and predicting their outcome. Through this method the authors prove that under certain constraints weak convergence of an algorithm can be proven. The article also reviews important topics in Genetic Algorithm planning and construction, and makes suggestions for designing better Genetic Algorithms.

The Canonical Genetic Algorithm

1. Initialize a population of Chromosomes (binary strings)

2. Evaluate each chromosome in the population by applying the objective function to its corresponding candidate solution.

3. Create new chromosomes by applying a fitness scaling technique to the chromosome evaluations, and recombining fit parent encodings.

4. Delete members of the population to make room for the new ones.

5. Evaluate each new chromosome as in step 2, and insert it into the population.

6. If the stopping criterion has been satisfied, stop and return the chromosome with best fitness, otherwise continue with step 3.

Criteria for evaluating Genetic Algorithm Analyses

1. The theory should be well grounded in the procedural elements and the generating mechanisms of genetic algorithms. These include the process of selection, recombination, fitness evaluation, and population management.

2. The theory should have explanatory and predictive power.

3. The theory should be robust with respect to algorithmic variations.

The Schema Theory

* Genetic algorithms work in the space of schemata, as opposed to the space of strings.

* A schema includes all the strings with certain common string elements.

* A schema’s order is the number of fixed string elements in it.

* Each binary string implicitly searches/samples 2^l samples.

Suitability of the schema theory

1. The allocation of trials to schema is certainly well grounded to the procedural elements.

2. The schema theory has led to useful, verifiable predictions, but is unable to explain how genetic algorithms systematically generate improved candidate solutions.

3. The schema theory is not robust with respect to algorithmic variations.

Alternative analyses of Genetic Algorithms

* Most of the analyses in the literature have made simplifying assumptions, or have not been dependent on the distinguishing characteristics of genetic algorithms.

* Vose and Liepins(1991) - Markov chain analysis, infinite population.

* Nix and Vose (1992) - similar applied to finite size population.

* Vose (1993) - GA-surface, geometric interpretation of genetic search.

Suitability of these analyses

1. The construction and operation of the population transition operators is well grounded in the procedural elements and generating mechanisms of genetic algorithms.

2. because the representations are exact, any phenomena observed of genetic algorithms will be explainable within its contexts.

3. Markov chain representations may be generated for nearly any algorithmic variant. Derived properties must be proved for each variant.

Global Random Search Methods

A global random search method should find an optimal solution to the following type of problem (Zhigljavsky 1991) :

for find
or or both.

A global minimization method is a procedure for constructing a sequence {x_k} of points in X that converges to a point at which the global minimizor, f^*, is attained or approximated. This definition is also true for the reverse problem (finding a global maximizor).

Formal Scheme of Global random Search

1. Set k=1, choose a probability distribution P₁ on X.

2. Sample N_k times the distribution P_k to obtain the points x₁^(k),..., x_Nk^(k)

At each of these points evaluate f, possibly with random noise.

3. Using a fixed, algorithm-dependent rule, construct the probability distribution P_k+1 on X.

4. If the stopping criterion is satisfied, then stop; otherwise, set k=k+1 and continue with step 2.

Methods of Generation

1. New samples of f should most often be obtained in the vicinity of previous, high-performance samples.

2. The number of new samples in the vicinity of a previous sample must depend on the observed value of f at that sample.

3. The Breadth of the sampling distribution around the previous samplings should decrease as the global optimizer is approached.

Genetic Algorithms as Global Random Search Methods

1. Set k=1, choose a probability distribution P₁ on A.

2. Sample N_k times the distribution P_k to obtain the points a₁^(k),..., a_Nk^(k)

At each of these points evaluate f, the fitness function, possibly with random noise.

3. Construct the probability distribution P_k+1 on A, according to the parent selection scheme, and crossover ,mutation and deletion rules.

4. If the stopping criterion is satisfied, then stop; otherwise, set k=k+1 and continue with step 2.

Genetic algorithm Behavior

1. The number of times a previous sample is chosen for constructing a transition probability, Q_k, is dependent on the function evaluated at that point.

2. The similarities between previous samples should be exploited in the construction of the transition probabilities.

3. often enough, the objective or fitness function behaves similarly on similar samples.

Candidate Solution Encoding - Why Not Strings?

1. The problem-specific structure of X is typically much better understood then the distribution of candidate solutions across A.

2. The recombination operators, Q_k, may be customized to exploit knowledge of the structure and similarities of the candidate solutions.

3. The behavior of the genetic algorithm will be better understood.

4. Only the recombination operators are problem dependent, the remainder of the algorithm is unchanged.

5. Mathematical analysis is easier due to the elimination of the mapping.

Issues in Genetic Algorithm design

Selection

How to select candidates for crossover and mutation?

The Most common method is Proportional selection.

Auxiliary functions are constructed for fitness scaling or ranking.

Variance reduction techniques, such as the Stochastic Universal Sampling (SUS) selection method, don’t allow the extinction of high performance samples.

Management of the Population

sizing and initialization

* The complexity of the phenospace and the characteristics of the objective function should be considered in the sizing of the population.

* stratified initialization - divide the sampling region into m equal sized sub-regions, and get l samples (uniformly) from each sub-region (for a total of N=lm samples).

sequentiality

In sequential algorithms sampling distributions are updated more frequently, such as after each sample, instead of after a full generation, making it possible to exploit information sooner after it is acquired.

This increases selection noise and genetic growth, and it's efficiency is very dependent on the deletion method.

deletion

Deletion methods used in Genetic Algorithms include WIFO - Worst-in-first-out, FIFO - First-in-first-out, and uniform deletion.

Methods that do not use fitness evaluations, such as uniform and FIFO deletion are preferred when the objective function is evaluated with favorable noise.

Convergence

example:

In this example the function F6 has two local maxima - a thin lobed global maximum and a wide lobed local maximum. The problem is to get the search to converge on the global maximum. This was tried twice, with the same algorithm, for alpha's of 0.22 and 0.23 (which have a very similiar graph) and these were the results:

As it can be seen in figure 10, one converged to the sub-optimal peak, and the other to the optimal peak. This means that it is very important to try and guarantee convergence to the global maximum.

In the article it is shown that by limiting the search width according to a predefined schedule, it is possible to guarantee weak convergence.

Conclusions

In this paper the theory of global random search methods is applied to genetic algorithms.

It is concluded that the construction and evolution of the sampling distributions P_k+1 is the preferred basis for understanding genetic algorithm behavior, The authors show that by implying certain constrictions on the genetic algorithm - limiting the search width according to a predefined schedule, it is possible to guarantee weak convergence.

An overview of Genetic Algorithm design issues is given, it is recommended that candidate similarities be exploited directly.

Future Work

* find better ways to exploit similarity in the phenospace.

* develop a fully adaptive method that is provably convergent.

* reduce selection sampling variance in sequential methods.

My personal conclusions

* The paper presents a very interesting approach to analyzing genetic algorithms.

* A review of research in the field of genetic algorithm design is given, and suggestions for designing better genetic algorithms are given.

* Not enough is said about the connection between the conclusions and the analysis.