gaw.n

较好的一种新的关于遗传算法的源程序

.ip
where a and b are chosen so that the mean scaled fitness is equal to the
mean unscaled fitness of the population, and so that the maximum scaled
fitness is a given multiple of the maximum unscaled fitness.
The multiple is typically two.

.lp
Several methods of fitness scaling are discussed in Goldberg 1989.

.sh 3 "Breeder Selection"

.lp
Breeder selection involves choosing a number of individuals according to
(scaled) fitness which will be used for breeding.

.lp
The number chosen depends on the number of new individuals required, which
is the product of the current population size and the \fIgeneration gap.\fR
The latter is an input variable between 0 and 1 which represents the
proportion of the current population replaced during each generation.

.lp
The method of selecting the individuals depends on the value of the
input variable \fIbreeder selection:\fR

.ip "\fIRoulette\fR"
This method is so named because of its similarity to spinning a roulette wheel.
In effect, an imaginary roulette wheel is marked out with one slot per
individual in the population, but the slots are of differing sizes giving
some individuals a better chance of being selected for breeding than others.
By making the slot size proportional to the (scaled) fitness of each
individual, the fitter individuals have a correspondingly better chance of
being selected and passing on their characteristics.

.ip
The imaginary wheel is spun once for each individual required, one individual
being selected per spin.
This allows some individuals to be selected more than once and others not
to be selected at all.

.ip "\fIExpected Value\fR"
There is a potential problem with roulette wheel selection because it is
a stochastic process.
In other words, its random element allows some individuals to be selected
more often than their fitness deserves (and others to be selected less often).
Expected value selection reduces this stochastic error by ensuring that
no individual can be selected more than one more time than it deserves.
(Obviously some stochastic error must remain because the number of times
and individual is selected must be an integer whereas its "selection merit"
is a real number).

.lp
Both \fIgeneration gap\fR and several kinds of \fIbreeder selection\fR are
discussed in Goldberg 1989.

.sh 3 "Generation Gap"

.lp
The \fIgeneration gap\fR input variable determines the proportion of
each the population replaced during each generation.
See breeder selection above.

.sh 3 "Mates Selection"

.lp
Following selection of a pool of individuals for breeding, pairs are
taken from this pool and bred to produce a pool of progeny.
The input variable \fImates selection\fR determines how these pairs are
chosen.
Currently only one method is supported:

.ip "\fIRandom\fR"
Each individual chosen for mating from the breeding pool is selected
at random and is immediately removed from the pool to prevent it
being selected again.

.lp
In this implementation all individuals are identical and so purely random
selection of a mate is always valid.
However, more complicated schemes are feasible where mating is restricted
in some way, perhaps to simulate the formation of niche populations or
species.
This is discussed further in Goldberg 1989 (p188-197).
See also section 5.4.9 which describes dispersal by crowding.

.sh 3 "Mating"

.lp
Having selected a pair of individuals for mating, they are mated to produce
new individuals which are collected in a pool of progeny.
The method used is determined by the value of the \fImating\fR input
variable, but this currently only supports one method:

.ip "\fISimple\fR"
Simple mating produces two progeny from two parents as follows.
First a copy of each parent is taken and \fIcrossover\fR is
applied to produce two individuals each of which receives some genetic
material from both parents.
Finally, \fImutation\fR is applied to each individual which may introduce
a random change to the genetic material.

.lp
Crossover and mutation are described in the following sections.

.lp
Currently only simple mating is supported, but many variations can be
envisaged, for example incorporating other genetic operators than crossover
and mutation.
These operators are copied directly from natural processes and their are
many other such operators, both natural and man made, that can be tried.

.sh 3 "Crossover"

.lp
As mentioned earlier, each individual represents a candidate solution to
the problem in the form of a string of zeros and ones.
Crossover is a process which takes two such strings and exchanges portions of
the strings to produce two new strings, each of which incorporates information
from both the initial strings.
Many variations of the crossover operator have been experimented with.
The following are available according to the value of the \fIcrossover\fR
input variable:

.ip "\fISingle Point\fR"
A point is chosen at random from the first to the last but one binary digit
of one of the strings.
The digits following this point are exchanged between the two strings.
For example, given the two initial strings and a crossover point indicated
by the '^'.

.TS
center tab(!) ;
c c c c c c c .
0!1!0!0!0!0!0
1!0!1!1!0!1!0
 ! !^
.TE

.ip
the following new strings would be produced.

.TS
center tab(!) ;
c c c c c c c .
0!1!0!1!0!1!0
1!0!1!0!0!0!0
 ! !^
.TE

.ip "\fITwo Point\fR"
Two point crossover is similar except that two distinct points are chosen,
again randomly, and the segment between the two points is exchanged.
The operator works in such a way that single point crossover is a legal
special case of two point crossover.
This is the case if either of the two points is at the extremes of the
string.

.ip "\fIUniform\fR"
Uniform crossover passes along the length of the strings and chooses to take
each bit from either one parent or the other according to some specified
probability.
The origin of each bit is independent of all the other bits and in this
implementation has an equal chance of being taken from either parent.
This produces more mixing of bits than the former operators.

.lp
The effect of crossover, whatever its form, is to produce new individuals
which contain genetic material from two parents.
No new material is introduced, and so there is a limit to the genotypes that
can be produced throughout crossover alone.

.lp
Several such operators including single point and two point crossover
are described in Goldberg 1989.
Uniform crossover is described (and compared with several other crossover
operators) in Syswerda 1989.

.sh 3 "Mutation Probability"

.lp
Mutation involves the chance introduction of a change to any particular
bit of an individual's string.
Each bit is considered in turn, and is flipped from a zero to a one (or vice
versa) with probability determined by the value of the \fImutation 
probability\fR input variable.

.lp
Mutation can result in new genetic material being introduced into the 
population, since it can produce values that were not present in either
parent, or indeed in the entire population.

.lp
Typical mutation rates are of the order one in a hundred to one in a thousand
bits.
Much higher rates tend to disrupt the action of crossover, preventing
convergence and leading to a more random type of search.

.sh 3 "Dispersal"

.lp
Dispersal is the method by which progeny are placed into the existing
population, which requires some existing individuals to be deleted.
This is done by the method indicated by the value of the \fIdispersal\fR
input variable:

.ip "\fIRandom\fR"
Individuals are chosen at random from the existing population to be replaced by
progeny until all progeny have been inserted.
Measures are taken to ensure that progeny inserted by the current dispersal
are not displaced by the insertion of other progeny.

.ip "Crowding"
Crowding is a mechanism used to prevent premature convergence of the algorithm.
The chance of an individual being displaced is made to depend on the degree 
of similarity between it and the new individual that is replacing it.
When a new individual is ready to be placed into the existing population,
it is compared (bit for bit) with a given number of individuals chosen
at random from the existing population.
The one most like the new individual is chosen to be replaced.
The number of individuals chosen for comparison is determined by the value
of the \fIcrowding factor\fR input variable.

.ip
Dispersal by crowding is so called because it simulates competition for
scarce resources by individuals which are genetically similar and so
encourages the formation of niche populations.
Mate selection, described in section 5.4.5 is another method that can
be used to encourage the formation of niche populations.
These and other methods are discussed further in Goldberg 1989 (p188-197).

.sh 3 "Crowding Factor"

.lp
The \fIcrowding factor\fR input variable determines the number of individuals
that are compared with each new individual during during dispersal by
crowding (see above).
A crowding factor of 1 would prevent crowding from working and be equivalent
to random dispersal.

.sh 3 "Elitism"

.lp
Elitism is a feature that is active dependent on the value (on or off) of
the \fIelitism\fR input variable.

.lp
When active, elitism ensures that the best, or fittest, individual cannot
be lost from the population through dispersal.
A copy of the fittest individual in each generation is kept and is
re-introduced into the population if, after dispersal, no individual in
the new population is at least as fit.

.lp
When elitism acts to re-introduce a lost individual it must choose an
individual to be replaced.
For details of how this is done, see the section entitled "Sacrifice Selection"
below.

.lp
Elitism is discussed in Goldberg 1989.

.sh 3 "Sacrifice Selection"

.lp
The method by which an individual is selected for replacement due to the
operation of elitism (see above) is determined by the value of the input
variable \fIsacrifice selection\fR as follows:

.ip "\fIRandom\fR"
The individual to be replaced is chosen randomly.

.ip "\fIWeakest\fR"
The weakest (i.e. least fit) individual is chosen.

.sh 2 "Output variables"

.lp
With each generation the display of output variables is updated.
Each variable is explained below:

.ip "\fIGeneration\fR"
The number of generations (iterations of the genetic algorithm) completed
so far.

.ip "\fIOptimum Fitness\fR"
The maximum value of the function f(x).

.ip "\fICurrent Best Fitness\fR"
The highest value of f(x) for any individual in the current population.

.ip "\fIAverage Fitness\fR"
The average value of f(x) for all individuals in the current population.

.lp
Note that the above fitness values relate to unscaled fitnesses.

.ip "\fIOptimum x\fR"
The value of x which corresponds the the maximum value of f(x) of the
target function.

.ip "\fICurrent Best x\fR"
The x of the individual in the population which has the highest value for f(x).

.ip "\fIAverage x\fR"
The average of all x values in the current population.

.sh 2 "References"

.ip "Goldberg 1988"
Goldberg, D. E. (1988). \fISizing Populations for Serial and Parallel
Genetic Algorithms.\fR TCGA report no. 88005. University of Alabama.

.ip "Goldberg 1989"
Goldberg, D. E. (1989). \fIGenetic Algorithms in Search Optimization & Machine
Learning.\fR Addison-Wesley.

.ip "Syswerda 1989"