gaw.n

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

Syswerda, G. (1989). \fIUniform Crossover in Genetic Algorithms.\fR
Proceedings of the Third International Conference on Genetic Algorithms.
Morgan Kaufman.
.bp
.lp
.sh 1 "Appendix B - A Typical Session Using the Workbench"

.lp
This appendix describes a typical session using the genetic algorithm
Workbench.

.lp
To run the Workbench program you require an IBM compatible personal computer
with EGA display and Microsoft compatible mouse.
To start the program, make sure your mouse driver is loaded, your display
is in EGA mode and type

.(l
gaw
.)l

.lp
followed by pressing the <ENTER> key.
The program does not have any command line parameters.
(See also section 3.2, "Running the Program".)

.lp
Check that the program display is similar to that of figure 1 shown earlier
in the manual.
If you think something is wrong, refer to \fIproblems, appendix C\fI which describes
possible problems and their solution.

.lp
Typical use involves the following steps.

.ip 1
Click on "Enter Targ" in the menu and enter a function extending from
leftmost to rightmost points on the graph.
(Note that clicking the left mouse button sets a point, clicking the right
deletes a point, and pressing both together ends input of the function).
You should enter a function starting from the graph origin (bottom left), and
finishing at the bottom right of the graph.
To end entry of the function, press left and right mouse buttons 
simultaneously.
If you go wrong, click on "Enter Targ" and try again.

.ip 2
Click on "Reset Alg" to initialise the genetic algorithm.
Notice the histogram of population distribution in the bottom left hand corner
is redrawn, along with the output variables in the box at the bottom right
corner of the screen.

.ip 3
Click on "Start Alg" which causes the algorithm to run.
Note that the menu option changes its name to "Stop Alg", and so clicking on
it again will pause the algorithm.

.lp
While running, a count of generations is maintained in the "Output Variables"
box, along with several other algorithm variables.
Every so often, the histogram is updated as the population
attempts to converge on the value of x which corresponds to the highest
peak in the target function input earlier.

.lp
At any time, a plot of average fitness against time can be produced by
clicking on "Plot Data".
The algorithm can be paused/re-started by clicking on "Stop Alg" 
and "Start Alg".
New target functions can be provided, as described earlier, and the algorithm
allowed to run with the current population distribution or with a
new distribution by clicking on "Reset Alg".

.lp
While the algorithm is paused, various program variables can be changed by
clicking the mouse button while the cursor is hovering over the \fIup\fR
and \fIdown\fR arrows next to values displayed in the large box spanning
the top of the screen.
Pressing and holding the mouse button enables variables to be changed
quickly.

.lp
Note that the large box spanning the top of the screen contains two pages, only
one of which is displayed at a time.
These can be thumbed through by clicking on the arrows at the very top right
of the display, immediately to the right of the copyright message.
The first page is called "Simple Genetic Algorithm" which allows algorithm
variables to be adjusted.
The second page, called "General Program Control Variables", allows selection
of different data for plotting on the output graph, changes to the scale
of output graph axes and so on.

.lp
Note that the algorithm will only run while the "Simple Genetic Algorithm"
page is selected.
Alternative algorithms, simulated annealing for example, will be implemented
by providing additional pages of algorithm variables.
.bp
.lp
.sh 1 "Appendix C - Problems and How to Fix Them"

.lp
This appendix is intended to help sort out problems encountered when
trying to run the genetic algorithm Workbench program.

.lp
If you are unable to fix any problems using the list of potential problems
and solutions which follow, it is wise to take the following steps before
giving up in despair:

.np
Prevent installation of any unnecessary resident programs such as pop-up
utilities, disk caches or command line editors.
These are often installed by commands in your autoexec.bat file and could
be the source of your problem.

.np
Prevent installation of any unnecessary device drivers.
These are usually installed by commands in your config.sys file such
as "device=filename".

.lp
The only resident program or device driver that you will need installed is
your mouse driver which may be installed by either of the above methods
depending on the software supplied with your mouse.

.uh "Problem: Display is squashed"

.lp
The top third of the screen is blank, but everything is displayed correctly
in the lower two thirds of the screen.
The mouse cursor may also be missing.

.lp
Your display adapter is in the wrong mode, possibly VGA mode.
Refer to your display adapter manual for details of how to set it into
EGA mode.

.uh "Problem: Display corrupt or blank"

.lp
Your display adapter is probably in the wrong mode.
Refer to your display adapter manual for details of how to set it into
EGA mode.

.uh "Problem: No mouse cursor"

.lp
The mouse cursor is not visible but it is possible to highlight options in
the command menu by moving the invisible cursor towards the menu and "circling"
with the mouse.

.lp
This probably indicates a problem with your mouse driver.
It may not be compatible with this mode of your display adapter.
Note that the Workbench program operates in \fIgraphics\fR mode, and so this problem
may occur even if you have used your mouse with the display in EGA \fIcharacter\fR
mode (which would display a block mouse cursor).
.bp
.lp
.sh 1 "Appendix D - General Introduction to Genetic Algorithms"

.lp
The following is an article which appeared in the Guardian newspaper on 14
September 1989.

.sz +2
.uh "Why Nature Knows Best About Design"
.sz -2

.ip
\fIEngineers now need a helping hand from Nature in order to solve their
problems.
Mark Hughes reports.\fR

.lp
All life on earth, including its most intricate
and ingenious features is the product of a genetic algorithm, known more
commonly as evolution.
However, genetic algorithms need not be confined to nature.
They can be used to help solve many design and optimisation problems.
Computer implementations of genetic algorithms are being used to tackle
difficult problems in fields as far ranging as turbine blade design,
automatic integrated circuit layout, and even in the training of neural
networks.

.lp 
All living things carry a kind of "blue-print" for their construction
in the DNA of each living cell.
Over a period of time, changes (e.g. mutations) occur to the DNA giving rise
to organisms which are more likely to survive, and so have a greater chance
of passing their improved characteristics on to future generations.
Of course, not all changes will be beneficial, but those which are not
tend to die out.
This is evolution.
It is analogous to engineers making design changes in order to
improve their company's product and so gain a competitive
advantage or increase profitability.
The genetic algorithm is the mechanism invented by nature for trying out 
alterations to DNA.

.lp
In the past, evolution has been perceived as a slow and hap-hazard process,
relying on random mutations, and thus unsuitable for use in
engineering.
This perception caused problems to scientists trying to explain the rapid rate
of evolution evident from the fossil record, and has been shown to be false.
Although scientists have been aware of genetic operators other than
random mutation for some time, it was not until the 1970s that a
mathematical analysis revealed their importance (Holland 1975). 
Holland showed that nature's genetic algorithm was highly efficient
at search and optimisation, and in no sense hap-hazard.

.lp
In engineering, computer simulations of genetic algorithms can be used to
evolve better designs for a variety of systems.
The computer is used to maintain a population of competing designs
each with its own computer representation of DNA (usually a binary string).
Here, instead of determining animal characteristics such as size, number
of limbs and eye colour, the "DNA" is decoded to produce design characteristics
such as lengths, angles, equations or rules.
At each generation, the better (cf. fitter) designs are chosen to
reproduce, and operators borrowed from nature are used to make changes
to their "DNA" in the search for improvements. 
The designs are then tested by decoding the "DNA", and over several
generations the population evolves and improves the criteria chosen by
the engineer. 

.lp
The freedom to select fitness criteria allows genetic algorithms to
be applied in many fields.
For example, you may wish to evolve rules for trading in financial markets,
improve the aerodynamics of a vehicle, or simply solve an abstract
mathematical function.
But why use a genetic algorithm, when in the last case for example, there
are plenty of established methods for solving mathematical functions?

.lp
The reason is that existing methods are fine so long as the problem is not 
too complex.
A genetic algorithm allows extremely difficult functions to
be solved efficiently - even the design of a living organism.

.lp
In engineering terms, the strengths of genetic algorithms can be
summarised by their abilities to cope with a variety of very difficult
problems, to work without prior knowledge about the function being
optimised, to optimise "noisy" functions, and to do without secondary
information such as gradients.
In plain language they can cope with the difficulties represented by real-life 
problems which are generally insoluble by other methods.

.lp
A recent and most impressive testament to the fact that genetic algorithms
are now coming of age has been provided by General Electric in the USA who
used the technique to design an improved gas turbine blade.
Their computer model indicates efficiency improvements of 2% for the design,
a significant saving in this field, and they are currently spending around
$1m verifying the prediction.
If this succeeds they will spend $70m re-tooling their production line to
produce the new type of blade.

.lp 
Applications in addition to those mentioned already include gas
pipeline management, medical image registration, adaptive filter design
and mechanical structure optimisation.
But engineering is not the only area to benefit.
Genetic algorithms have been used to generate rules for financial trading
systems, to classify forensic evidence, and to identify insurance risks.

.lp
A lack of computer power has been a factor limiting the usefulness of genetic
algorithms as they sometimes require large amounts of computation, particularly
if complex computer models are involved.
But this is no longer such a problem because computing power has become
relatively cheap.
Even very difficult problems can now be solved because of the efficiency
with which genetic algorithms can be implemented on today's parallel 
computer architectures.

.lp
Engineering problems are getting so complex that man's intuitive approach
to design is becoming too primitive.
Genetic algorithms are one of the tools that engineers are using to
make up for their short-comings.

.lp
\fIReference: Holland J. H. (1975). 
Adaptation in Natural and Artificial Systems.
Univ. of Michigan Press: Ann Arbor, MI.\fR
.bp
.lp
.sh 1 "Appendix E - Main Command Menu"

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

.TS
center tab(!) ;
cb cb
l l .
Option!Function
Redraw!Redraws the whole screen
Start Alg/Stop Alg!Start/pause algorithm operation
Step Alg!No function
Reset Alg!Generate initial random population
Plot Data!Plot graph of average or best fitness
Plot Targ!Re-plot the target function
Enter Targ!Enter or re-enter target function
Quit!Exit the program
Test!Tests my jump-up menus (no function)
.TE