Capabilities and Enhancements relative to the Simple Genetic Algorithm (SGA)
LAST UPDATED: August 4, 1996.
GALOPPS is a flexible, generic GA, in 'C'. It was based upon Goldberg's
Simple Genetic Algorithm (SGA)
architecture, in order to make it easier for users to learn to use and extend.
All performance-critical code has been rewritten from the SGA-C
implementation used as a starting point (after some bug fixes). It
has been extended to provide island parallelism in three types of
architectures, ranging from a single PC simulating parallel
subpopulations, through multiple processes on a workstation, to
multiple computers on a PC network or workstation network, each of
which can "handle" one or many interacting subpopulations. It's been
tested under DOS, Windows, NeXTStep, SunOS, Solaris, HP-UX, Metrowerks
CodeWarrior (on Macintosh) and a few
other systems. An 84-page User's Guide (building on Goldberg's SGA
exposition) is provided. NEW: A PVM port of GALOPPS3.01 for running
many processors from a single master control point (PVM GALOPPS 3.1)
GALOPPS extends the SGA capabilities several fold:
For additional capabilities, see also
NEW FEATURES of Release 3.2.
- 5 selection methods: roulette wheel, stochastic remainder
sampling, tournament selection, stochastic universal sampling,
- Random or superuniform initialization of "ordinary" (non-permutation)
binary or non-binary chromosomes; random initialization of permutation-based
chromosomes; or user-supplied initialization of arbitrary types of chromosomes.
- Binary or non-binary alphabetic fields on value-based chromosomes,
including different user-definable field sizes.
- 3 crossovers for value-based representations: 1-pt, 2-pt, and uniform,
all of which operate at field boundaries if a non-binary alphabet is used.
- 4 crossovers for order-based reps: PMX, order-based, uniform
order-based, and cycle.
- 4 mutations: fast bitwise, multiple-field, swap and random sublist
- Fitness scaling: linear scaling, Boltzmann scaling, sigma truncation,
window scaling, ranking.
- (optional) Automatic control of selection pressure, using Boltzmann
scaling with automatic control of beta, coupled with Stochastic Universal
- (optional) DeJong-style crowding replacement with (optional) incest-
reduction option for mating restriction (negative assortative mating bias),
which follows the selection of
candidates for mating for an entire generation by a pairing for crossover
biased by use of the furthest mate (Hamming distance) among several sampled
- Other replacement strategy options: child-replaces-parent (from
SGA) or child-replaces-random.
- Elitism is optional.
- Convergence: "lost," "converged," "percent converged," & other
- Performance measures: on-line and off-line (local and global
across subpopulations), plus current local best, best ever, global
- (optional) Inversion operation on entire subpopulations, with
migration among them automatically handled, even if fields are of
- Allows user to define multiple (different) representations in
subpopulations, with migration among them (by user-supplied migration
"conversion" code unless difference is only in order of loci on
chromosome, which is handled automatically by GALOPPS).
- Provides a "beta" implementation of Emanuel Falkenauer's Grouping
Genetic Algorithm (GGA) representation and operators, implemented by Brian
Zulawinski, which provides tools for efficient solution of a variety of
"grouping-type" combinatorial problems (including a bin packing example
included, various assignment problems, partitioning problems, etc.).
Useful for approximating solutions to many NP-complete problems.
- Uses "SGA philosophy" of one template file for the user to
modify, but enriched with MANY additional user callbacks, for added
flexibility, extensibility. All but definition of objective function
may be ignored if not needed.
- All runs are restartable or seedable from automatic checkpoint
- Output easily suppressed to one of 3 reduced levels, including
user-callback-driven outputs. Input is from file or keyboard, and
files allow optional keywords to permit automatic diagnosis of missing
- Communication topology for parallel runs is easily specified in a
single "master" file, using either a detailed specification or a
"cloned" sample communication pattern. May be defined graphically using
new Graphical User Interface.
Released in February, 1997: A 2-level GA (DAGA2) in which
first-level GA subpopulations compete under control of a second-level GA,
solving difficult problems with no more (and maybe fewer) evaluations than
one-level GA's (and compatible with GALOPPS3.2's input and application files).
For more information
on GALOPPS, contact
GALOPPS, Erik Goodman