gaw.n

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

This box labelled axis value is used in combination with the mouse cursor
to read values from any of the graphs described above.
When the mouse cursor is moved over the plot area of any graph, it changes to
a cross hair and causes the Axis Value box to display the coordinate values
of the corresponding graph at the point indicated by the cross hair.

.(b
.sp 15
.ce
.uh "Figure 1 - Example Screen Display"
.)b

.sh 2 "Menu Commands"

.lp
The program is controlled entirely through use of a mouse.
General commands such as starting and stopping the algorithm are invoked
through a menu.
The target function is input by drawing the function on a graph using the
mouse cursor, and algorithm and program control variables can be altered
by clicking the mouse over the up and down arrows to the left of each value.

.lp
This section describes each menu command.
Program control variables are explained in the following section.

.lp
The functions of the command menu shown in the top left of the screen are
as follows:


.ip "\fIRedraw\fR"
Redraws the whole screen.

.ip "\fIStart Alg/Stop Alg\fR"
Start/pause algorithm operation.
Note that an algorithm can only be run if it the algorithm chapter is
showing the corresponding algorithm page.
No algorithm can run while the chapter is displaying the page relating to
general program control variables.

.ip "\fIStep Alg\fR"
No function.
Currently unimplemented.

.ip "\fIReset Alg\fR"
Resets algorithm ready for a run.
See the relevant appendix for details of reseting an algorithm.

.ip "\fIPlot Data\fR"
Plots currently selected data (see description of "Plot data" variable
later), on the output plot.
This displays the selected variable against time for the duration of the
current algorithm run.

.ip "\fIPlot Targ\fR"
Re-plot the target function.
After redrawing the entire screen the target function graph is cleared.
This command allows the current target function to be redrawn, but note
that it will have no effect until a function has been entered using
the "Enter Targ" command described next.

.ip "\fIEnter Targ\fR"
Enter or re-enter target function.
After executing this command, the mouse cursor is moved to the target function
graph allowing a target function to be drawn.
Clicking with the left mouse button plots a point for the function, and
clicking with the right deletes a point.
You should draw a function which spans the full width of the x axis from
left to right and uses as few points as possible.
Functions with many points slow down the algorithms.
When you are happy with the function, press both left and right mouse
buttons together.

.ip "\fIQuit\fR"
Exit the program.

.ip "\fITest\fR"
Tests my jump-up menus (no function).
Play by all means, but this has nothing to do with the Workbench program.

.sh 2 "Program Control Variables"

.lp
The program control variables are shown on the page labelled "General
Program Control Variables".
The meaning of each program control variable explained below.
(Algorithm control variables are explained in appendix A.)

.lp
Program control variable meanings:

.ip "\fIPlot data\fR"
This variable is used to determine the source of data for plotting on the
graph entitled "Output Plot".
The selections available include values (but not all values) of output
variables from those displayed in the "Output Variables" box.

.ip "\fIO/P Plot X-max\fR"
This variable sets scale of the output plot X axis by fixing the maximum
x value that can be displayed.

.ip "\fIO/P Plot Y-max\fR"
This variable sets scale of the output plot Y axis by fixing the maximum
y value that can be displayed.

.ip "\fIPlot period\fR"
This variable determines the frequency with which the population distribution
histogram is updated.
A value of 1 causes an update for every iteration (or generation) of the
algorithm.
A value of 2 causes update every other iteration, 3 every third and so on.

.ip "\fIRandom # seed\fR"
This value is used to seed the program's random number generator each time
the algorithm is reset from the command menu.

.sh 1 "Bibliography"

.lp
This section lists some sources of information about genetic algorithms.

.lp
A brief and very general introduction to genetic algorithms is given in
appendix D which contains a copy of an article from The Guardian
newspaper.

.lp
The following text is a comprehensive textbook of genetic algorithm
theory and applications up to the year 1989.

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

.lp
Users wishing to experiment with genetic algorithms in their own programs
may be interested in a package called GENESIS.
This is a set of very useful subroutines written in C and built into a tool
for experimenting with different "flavours" of algorithm.
GENESIS is far more flexible than the Workbench but is not interactive and
has no graphical output built in.
As an integrated tool, GENESIS will run on most Unix systems, but the genetic
algorithm subroutines are easily ported to any system with a standard C
compiler.
GENESIS can be obtained from its author:

.(l
John J. Grefenstette,
Navy Center for Applied Research in Artificial Intelligence,
Naval Research Laboratory, Washington, D.C. 20375-5000.
USA.
.)l

.lp
The author of the Workbench program is happy to correspond with users
interested in learning more about genetic algorithms, or who wish to discuss
their relevance to a particular kind of problem.
He can be reached by writing to the following address:

.(l
Mark Hughes,
256 Milton Road,
Cambridge,
CB4 1LQ.
UK.

Internet: [e-mail]
.)l
.bp
.lp
.sh 1 "Appendix A - Workbench Algorithms"

.lp
This appendix describes the implementation of the genetic algorithm and
operators used in the Workbench program.

.sh 2 "Solving Problems with a Genetic Algorithm"

.lp
A genetic algorithm evolves solutions to a problem through natural selection,
breeding and genetic variation.
This involves generating a population of solutions, measuring their suitability
or fitness, selecting the better solutions for breeding which produces a
new population.
The process is repeated and gradually the population evolves towards the
solution.

.lp
In the genetic algorithm Workbench, the problem is to find the value of x for
which the target function has a maximum value of f(x).
Each individual in the population represents a solution to this problem in
the form of a candidate value for x.
The suitability or fitness of the individual is simply taken by calculating
the value of f(x) for the individual.
This leads to an individual whose value of x corresponds to a high value of f(x)
being fitter, and consequently being given a greater chance of breeding, than
an individual whose value of x corresponds to a lower value of f(x).

.sh 2 "Genotype Coding"

.lp
In the same way that the genetic information of animals is coded as a string
(of DNA), the genetic information of each individual, i.e. its value of x, is
also coded as a string.
In this case as a string of zeros or ones which can be interpreted as a
simple binary code.
The choice of a string representation is deliberate because it allows
processes which act on strings of DNA during natural evolution
to be implemented by the computer version of the genetic algorithm.

.lp
The string coding of each individual is known as its genotype in biological
terminology, while its interpretation, i.e. its value of x, is referred to
as its phenotype.

.sh 2 "Genetic Algorithm Implementation"

.lp
The genetic algorithm implemented by this program boils down to the following
steps.
(Note that a number of new terms, shown in italics, are introduced during 
the following steps without full explanation.
These terms refer to operations that are explained subsequently.)

.np
Generate an initial population of organisms.
The random number generator is seeded with the value of "Random # seed" (see
section 3.5), and a new population of organisms is generated each with a
different random genotype.
This happens whenever the "Reset Alg" command is invoked from the main menu.
The command also resets the generation counter to 0 and clears the output
variables which are updated during each algorithm run.
The number of organisms generated depends on the value of the \fIpopulation\fR
input variable.

.np
Calculate and scale new fitnesses.
Each new individual's fitness is calculated by reading a value of f(x)
from the target function at the individual's value of x.
If selected, \fIfitness scaling\fR is now done.

.np
Select individuals for breeding.
A subset of the population is selected for breeding.

.np
Breed to produce new population.
The set of breeders are taken in random pairs and mated to produce pairs of
new organisms, the progeny.

.np
Disperse progeny into the population.
The new progeny are inserted into the population, displacing existing
individuals.

.lp
After the last step, the algorithm begins again at step 2, starting the next
generation.

.sh 2 "Summary of Algorithm Input Variables"

.lp
Each input variable to the simple genetic algorithm is summarised below.

.sh 3 "Population"

.lp
This input variable determines the number of individuals in the population.
That is, the number of candidate solutions being manipulated by the
algorithm at any time.
Too small a population and there will be little opportunity for genetic
variation, too large and the algorithm will reduce to a random search.

.lp
For the problem posed in the Workbench, populations as low as 5 to 10 can
be quite effective but in more complex problems where there are many more
possible solutions larger populations are required.
However, even for very complex problems, populations rarely exceed a few
hundred individuals.

.lp
One of the reasons why surprisingly small populations can be effective is the
intrinsic tolerance of noise exhibited by the genetic algorithm which arises
out of the repeated sampling of small chunks of the genetic material (so
called schemata) over a number of generations.

.lp
There is a discussion of the issues in selecting suitable population sizes
in Goldberg 1988.

.sh 3 "Fitness Scaling"

.lp
Fitness scaling occurs between the production of new individuals in the
population and the use of their fitness values for selection.
It is a method of adjusting the probability distribution which
determines the likelihood of an individual being selected for breeding.
It is usually used to emphasise the relatively small differences in relative
fitness when a population begins to converge.
Without it, the rate of convergence will slow down as diversity decreases and
most individuals in the population have similar fitnesses.

.lp
The kind of fitness scaling employed depends on the value of the corresponding
input variable which has one of the following values.

.ip \fINone\fR
No scaling.
An individual's scaled fitness value is the same as its unscaled value.

.ip \fILinear\fR
Each individual's scaled fitness f' is calculated from its unscaled fitness f
according to the formula

.(l
f' = a.f + b
.)l