GALOPPS 3.2

GENERAL DESCRIPTION

Capabilities and Enhancements relative to the Simple Genetic Algorithm (SGA)

LAST UPDATED: August 4, 1996.

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:

• 5 selection methods: roulette wheel, stochastic remainder sampling, tournament selection, stochastic universal sampling, linear-ranking-then-SUS.
• 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 scramble.
• 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 Sampling.
• (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 candidate parents.
• Other replacement strategy options: child-replaces-parent (from SGA) or child-replaces-random.
• Elitism is optional.
• Convergence: "lost," "converged," "percent converged," & other measures.
• Performance measures: on-line and off-line (local and global across subpopulations), plus current local best, best ever, global best ever.
• (optional) Inversion operation on entire subpopulations, with migration among them automatically handled, even if fields are of different lengths.
• 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 files.
• 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 parameters, etc.
• 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 Erik Goodman