Genetic Algorithms & Artificial Neural Networks

The following was extracted from:

Genetic Algorithms and Artificial Neural Networks

A talk presented to the Fort Worth, Texas chapter of the Association for Computing Machinery, Spring 1988

What is a genetic algorithm?

A genetic algorithm is an iterative search technique premised on the principles of natural selection.
A genetic algorithm is an implementation of a search technique which locates local maxima. Is it a state-space search or does it search surfaces? It does both.

What use is a genetic algorithm?

In searching a large state-space, multi-modal state-space, or n-dimensional surface, a genetic algorithm may offer significant benefits over more typical search or optimization techniques (linear programming, heuristic, depth-first, breadth- first, praxis, DFP [De Jong, 80]). Of course, 'boy-with-a- hammer' syndrome should be avoided.

Genetic algorithm components

a goal condition or function
a group of candidate structures (bit-maps, messages, weights, etc.)
an evaluation function which measures how well the candidates achieve the goal condition or function
reproduction function (takes current candidates and reproduces them with some amount of variance)

Genetic Algorithm Sequence of Events

repeat
until satisfied

where 'satisfied' indicates that the goal condition has been met, or that some failure condition is triggered, or never. 'Repeat forever' would be useful for adaptive systems.

Why does this work?

competition for system resources
heritability of variance

How does this work? Example [from Smith, 88]:

State goal condition as finding binary string of length 5 with (4) 1's

Randomly generate L5 strings (length five), population size of 5

00010 (eval: 1)
10001 (eval: 2)
10000 (eval: 1)
01011 (eval: 3)
10010 (eval: 2)

Population evaluation average: 1.8

To find next generation, reproduce from this candidate population with modification. Modification method is defined as 'crossover', as in sexual reproduction.

Modification methods thus far proposed for GA's:

crossover - interchanges strings at random point
inversion - generates new schemata by flipping substring
mutation - point mutation

Reproductive function semi-randomly selects pairs of candidate strings for production of new candidates. A random number is generated and applied to a selectionist distribution of candidate strings.

Selectionist distribution:

1 00010 (eval: 1)
2 10001 (eval: 2)
3 10001 (repeat since fitness is higher)
4 10000 (eval: 1)
5 01011 (eval: 3)
6 01011 (repeat)
7 01011 (repeat)
8 10010 (eval: 2)
9 10010 (repeat)

Select pairs (indices from selectionist distribution):
1 & 4 Then crossover point: 1
4 & 5 4
9 & 7 3
8 & 6 1
7 & 5 1

Result from :
1+4:1 = 00000 (eval: 0)
4+5:4 = 10001 (eval: 2)
9+7:3 = 10011 (eval: 3)
8+6:1 = 11011 (eval: 4)
7+5:1 = 01011 (eval: 3)
New population evaluation average: 2.4

The goal condition has now been satisfied, and the procedure ends.

How well do GA's work?

Given candidates which are binary strings:
Population size N
Number of generations G
We sample NG points out of 2^l where l is binary string length

So what?

This can be done with random search methods
But GA's develop a pool of genes
Search is for 'schemas' which are 'blocks' or 'alleles' (portions of the binary string which tend to be reproduced as a unit)
2^l schemas per individual
N*2^l schemas per population

[Smith, 88]

What applications can this be put to?

Accomplished:

adaptive systems design
adaptive control
finite automata specification
optimization problems (TSP [Brady, 85])

Projected:

parameter specification for neural networks

Problems:

How to specify a 'genetic' pattern for the application in mind?
Does it converge faster than learning procedures?

The example brought up by Smith was that of specifying weights in a back-propagation ANN. The question was raised as to whether the GA would show any advantage over just going ahead and doing the typical training. Since training involves the solving of sets of differential equations for each weight in the network, repeated over multiple training iterations, it is expected that GA's would produce significant time benefits. The GA does not require intensive computation, so more time could be spent in the evaluation phase. The GA would be more space-intensive, however, in order to maintain a 'population' of candidate weights for the back-propagation ANN.

Miscellaneous:

The foremost researcher using GA's is really interested in 'classifier' systems, which incorporate GA's in formulating new classifiers. [Holland, 86]

Most classifier work seems to be done with binary string representation. Since this is what digital computers run off of, it has been noted that a classifier system is theoretically capable of forming any program which can be specified.

Another point of view is offered by Dress, who applies 'Darwinian' techniques to learning in artificial neural network models. Strictly speaking, his method is not Darwinian, but the issues he raises concerning 'programmer omniscience' are valid and need to be addressed [Dress, 87].

Random musings:

The area of GA research seems to have quickly lost track of the biological origin of the concepts used. For example, this quote from Holland:

'Rather surprisingly, and contrary to common wisdom in genetics, it can be shown that the crossover operator (the major source of recombination) is the primary contributor of improved rules.'

I can assure you that 'common wisdom' in genetics does not disagree with Holland's statement. The principle of 'hybrid vigor' has been noted and understood for some time.

Genetic algorithms provide a search method which offers the promise of fast convergence on a solution state. Usually, this is accomplished in a semi-random manner, so that intermediate states may not be observed. Thus, GA's are not applicable for replacing min-max game trees or other forms of search in which the change from previous state to current state must be incremental.

Background:

Genetic algorithms are premised on the principles of natural selection in biology. In searching for a solution state, a 'population' of candidate states are generated, evaluated, selected, and reproduced with modification to produce the next candidate population.

(BA == Biological analogue)
Structures and modules needed:

candidate data structures (BA = organisms)
representation structure (BA = set of chromosomes)
evaluation function (BA = environment)
selection mechanism (BA = [too many to list])
reproduction mechanism (BA = genetics)

In biology, the sequence of events works like this:

The organism has a set of structures which help determine its internal organization and capabilities. These are the genes, which in combination with environmental factors during development specify the formation of structures and connections. At maturity, the organism will have expressed a suite of characteristics which enable it to survive in its environment and propagate itself. The mode of reproduction which produces the most variance in the resulting offspring is sexual reproduction, which mixes genes from separate individuals to form the resulting offspring. Asexual reproduction is subject to variation only through external disturbances, such as radiation induced mutation or viral transcription, which produce variations that are small or relatively infrequent.

Various expressed characteristics of an organism may make it less successful than other organisms of the same species, where success is defined as 'differential reproductive success', in other words, the organism leaves more related offspring than those which do not demonstrate the same degree of adaptation. The next generation of organisms then proceed through the same processes.

The expressed characteristics of the organism are not necessarily the same characteristics as those coded for in the genes of the organism. The actual set of gene information is referred to as the genotype, while the expressed characteristics of the organism is referred to as the phenotype. The difference between code and expression can be a result of both the environmental factors and the interaction between genes on a pair of chromosomes.

Why genetic algorithms? Why, for that matter, neural networks? Both of these active research fields are premised on aspects of biological phenomena. Consider the complex problems which living systems must contend with in order to survive. The highly diverse fauna currently living gives some idea of the range of possible solutions to these problems. However, that is not the entire picture. Consider the currently extant number of species to be a small subset of instances in a far larger solution space.

The existing species can be thought of as representing 'splotches' on the surface of an expanding hypersphere. By no means do they represent the entire range of possible solutions. These species are postulated to have arisen by the process of natural selection.

Natural selection provides a mechanism for the identification and propagation of appropriate adaptation to specific and complex problems. Basically, natural selection can be described cursorily in the following manner. Several conditions are postulated.

a population of candidate entities
within this population, there is variation
some of these variations are heritable
the individuals of the population are capable of reproduction, either by themselves or in conjunction with other individuals
the individuals within the population are constrained by the environment
stresses in the environment may prove debilitating or fatal to the individual
limitations on resources provided by the environment will prevent the unrestricted propagation of individuals of the population
limitations induce competition between individuals of the population for resources
individuals compete for basic resources:
elements or compounds necessary for basic processes of metabolism
elements, compounds, or structures which provide food
other individuals for the purpose of reproduction ( in sexual reproduction )
a mechanism for the introduction of variation exists
within the context of DNA or RNA based heritability, point mutations may occur through the action of radiation of suitable energy (gamma ray, X-ray, UV light). For asexually reproducing species, this will be one of the major sources of variation.

With these postulated requirements, natural selection proceeds.

the variation in individuals will lead to differences in the success of individuals, where success is defined to be differential reproductive success.
heritable traits which confer differential success will tend to become more highly represented in the population
heritable traits which are maladaptive will tend to become less well represented in the population

Notice that the selection process is not considered to 'favor' adaptive characteristics, rather, relatively maladaptive or nonadaptive traits are 'selected' against. Thus, natural selection can be considered to include a normalization procedure.

The variation which is present in the population is generally assumed to arise at random. The selection process, however, is not random, but is premised on relative functionality with reference to the absolute constraints of the environment.

References:

Brady, RM. 1985. Optimization strategies gleaned from biological evolution. Nature 317(6040):804-806.

Dejong, K. 1980. Adaptive system design - a genetic approach. IEEE Syst. M. 10(9):566-574.

Dress, WB. 1987. Darwinian optimization of synthetic neural systems. IEEE Proc. ICNN Vol. 4:769-776.

Holland, JH. 1986. A mathematical framework for studying learning in classifier systems. Physica 22D(1-3):307-317.

Smith, D. 1988. Genetic algorithms, a speech presented to the Metroplex Institute for Neural Dynamics.