|
1. INTRODUCTION
Background
An algorithm is any procedure that uses data and modifies it according to a step-by-step set calculation procedure. Every program you have ever written, is an example of an
algorithm. Genetic Algorithms are programs that stimulate the logic of Darwinian selection, if you understand how populations accumulate differences over time due to the environmental conditions acting as a
selective breeding mechanism, then you understand GAs. Put in another way, understanding a GA means understanding the simple, iterative process that underpin evolutionary change. The issue, of course, is how
best to get that "selection procedure" translated into a program procedure applicable to your problem.
John Holland, the pioneer of Genetic Algorithms defines the evolutionary nature of the algorithm as follows:
- Start with an initial population that is randomly generated, but contains the variability parameters characteristic to the population.
- The fitness of each individual in the population is assessed according to the fitness function.
- The probability of each individual to survive is proportional to the fitness.
- The individuals of the next generation are selected on probability and through a genetic transformation process of mutation and
crossover ensuring that the solution is not localized within the solution environment.
GAs, are suited to solve problems that are not vulnerable to attack by brute force methods because the sheer number of potential
solutions defies the possibility of testing them all. Such problems are typically multi-constrained, that is the solution must be a balance of
conflicting or synergistic properties. When considering a problem with multiple dependencies you are normally forced to admit the
possibility of isomeric solutions i.e. solutions that give the same result using different processing routes. So for some problems there is no
such thing as the "best solution" but instead you are looking for members of a fuzzy set of solutions that can be defined as "good enough".
Some problems have a "Best" solution but it is lost in a vast result space. Brute force techniques can and do work in situations like this,
that's' why machines can now beat chess masters, but the problem with any brute force method is its almost complete lack of scalability. If
you manage to build a computer large enough to solve for a reasonably constrained problem, then adding just one more constraint will
probably require another 10 similar computers to deal with additional calculations. Add another row of squares to a chessboard and the
number of possible moves expands dramatically. One of the great strengths of check all the possible solutions. This means that increasing
the number of possible solutions has little impact on the run time of a GA – the logic has already sacrificed absolute confidence in the result for the ability to get any sort of workable result at all.
Typically you will notice that GAs use bit-strings to represent the state of an object model. Manipulations of the values of these bit-strings
can be translated back into changes to the associated objects' instance-data. Once freed by this abstraction into bit-strings the GA-coder
can apply biologically analogous processes such as Mutation, Crossover and Replication to the bit-strings, which can then be translated
back to the objects themselves. In this way the GA-coder can evolve the instance-state of the components within an object model.
Many people believe random mutation is the engine of evolution but this is not strictly true. Although mutation does provide populations
with a steady trickle of novelty in unexpected places the real engine of evolution is Useful Variation. Variation stems from mutation but
only useful variation is amplified and preserved. This amplification rests on the GAs ability to select members of the population with high
fitness values (or their children) and use them to replace members with low fitness values. Selective breeding and selective replacement act
together to steadily ratchet the mean population fitness remorselessly upwards. Only those members that are good enough, according to the definition of "fit", can survive to breed.
Selection pressure and random mutation may get you to a solution but this is not a GA (it is called a "random walk"). Vital to a GAs
amazing efficiency at searching through huge result spaces is the ability to exchange sequences between different, pre-tested (they are still
alive) solutions. Generating variety through sequence swapping ensures that you less likely to lose beneficial groups of bits through sheer
bad luck but instead give them a chance to recombine in novel ways. The biological term for this safe shuffling is "Crossover".
The final fundamental component of a GA is its Fitness Test. This is usually a simple set of calculations that consumes an object's current
state, and assigns to the object a Fitness Value based on that state. Each member of the population must be presented for a Fitness re
-evaluation whenever any of the Fitness-Implicated properties change their value.
Now that we know that a GA is a search procedure based on the mechanics of natural selection and natural genetics and that this
technique is geared to handle complex multi objective problems that has a large solution space, a brief overview of the functioning of a GA will be provided.
Goldberg indicated that a GA differ from the traditional search methods in the following ways:
- GAs work with coding of the parameter set, not the parameters themselves.
- Search for population of points, not a single point.
- GAs use objective functions (payoff) information not derivatives or other auxiliary knowledge to determine the fitness of the solution.
- GAs use probabilistic transition rules not deterministic rules.
- Goldberg provide the following examples to illustrate the working of a genetic algorithm.
Below are some screen captures of the GANEO program which was developed for network optimization (Input and Results screens)
2. SYSTEM REQUIREMENTS
GAWUP
runs on any personal computer, but requires Windows 95/98/ME/ZP, Windows N.T 4.0, or 2000. The program takes up approximately 10 MB of hard disk space and a pointing device (mouse) is a helpful tool.
3. THE PACKAGE
GAWUP is distributed on a CD which contains all the files and libraries necessary to install and run the program, GAWUP. The entire package can also be downloaded from the link below.
4. INSTALLING THE PROGRAM
You install GAWUP using the program setup.exe
. The Setup program installs the software, sample applications and the help files.
To install GAWUP:
- insert the distribution CD in the CD-drive
- type "d:setup.exe" (if "d" is the CD drive) or use the windows explorer to start the setup.exe program on the CD.
- Follow the setup instruction on the screen.
The installation program automatically creates a program group called GAWUP
. This program group will be listed under the Programs menu, which is under the Start
menu. The installation program creates the directory specified by the user and then copies the necessary files to this directory.
The following files should be in the selected directory:
|
GAWUP.exe
|
GANEO\Projects & Data\New York Tunnel pipes.pip
|
|
GAWUP.hlp
|
GANEO\Projects & Data\Hanoi Example.gan
|
|
GAPOP.hlp
|
GANEO\Projects & Data\Hanoi Example.inp
|
|
GANEO.hlp
|
GANEO\Projects & Data\Hanoi pipes.pip
|
|
Epanet.dll
|
GANEO\temp.inp
|
|
Readme.txt
|
GANEO\temp.out
|
|
St6unst.log
|
GAPOP\Projects & Data\Example 1 (Gravitation system).gap
|
|
GANEO\Projects & Data\New York Tunnel Example.gan
|
GAPOP\Projects & Data\Example 2 (Pumping system).gap
|
|
GANEO\Projects & Data\New York Tunnel Example (SI).inp
|
Report\WRC Report no 1144-01-01.pdf
|
The installation program will install all the necessary files in their correct locations and will create shortcut items under the Windows Startup menu.
Future updates will be made available on the internet web site or can be send to you via e-mail. Please visit the website regularly to keep
your version up to date. All the files listed above will be updated when running the "patch" file (update file)
For best results set the display properties to High Color (16 bit) and at least a screen area 800 x 600 pixels.
5. REGISTRATION
Genetic Algorithm Water Utility Programs
once installed can be used for 15 trial uses. If the user would like to become a registered user, a password is available from the Department of Civil and Biosystems Engineering at no cost
. The benefit of registering is that regular updates of the program and information on the latest products available will be distributed to all the registered users.
Please print the registration form and fax it to the number below. Registering can also be done by telephone or e-mail. The developers will
provide the password which must be entered to register the program. If registering by phone please remember to provide the "System serial number" generated by the program.
Department of Civil and Biosystems Engineering
Contact person for registration: Mr Marco van Dijk
Tel: 012 420 3176
Fax: 012 362 5218
E-mail: software@sinotechcc.co.za
Remember to keep the password provided by the Department of Civil and Biosystems Engineering for future reference. It may be
required to re-enter the password if the program is updated in the future. Updates will be send to all registered users and will be made available on the internet web site.
6. DISCLAIMER
The software program was developed for the convenience of its users. Although every reasonable effort has been made to ensure that the
program is accurate and reliable neither the Water Research Commission nor the program developers, University of Pretoria accept any
liability of any kind for any results, interpretation thereof or any use made of the results obtained with this program. All users of this program do so entirely at their own risk.
7. SOFTWARE DOWNLOADS
The latest version available is version 1.0.1 (March 2005):
Date: 15 March 2005
License: Shareware
Size: 5.1 MB
GAWUP - version 1.0.1
The latest version of EPANET can also be downloaded by clicking on the links below:
EPANET
EPANET user manual
EPANET toolkit
8. UPDATES/PATCHES
The first version released was version 1.0.1 (March 2005)
No updates since then.
Return to top of page
|