NEW FEATURES of Release 3.2
LAST UPDATED: February 20, 1997.
Release 3.2 includes many new capabilities and improvements.
Directions for revising the app file for users of earlier GALOPPS releases
are in file "changes.txt" in subdirectory docs.
Major new features of Release 3.2 include:
DELETED GRAPHICAL USER INTERFACE (optional):
An optional new GRAPHICAL USER INTERFACE (GUI) for GALOPPS was written in
Tcl/Tk, for use on Unix systems,
for form-based generation of input files and graphical plotting of program
output (fitness, convergence measures, etc.). However, its author departed
before it was fully debugged, and it has been pulled from the distribution.
A new JAVA-based GUI is now under development.
ARBITRARY-SIZED FIELDS, PRESERVED UNDER CROSSOVER AND MUTATION:
Allows user to define "fields" of different sizes (and lengths), so that
discrete variables of differing cardinalities can easily be used in
the new GALOPPS Release 3.2. The DIFFERENCE is this:
IN THE PAST, in order to represent integer or floating point variables
(i.e., not binary choices), the user could specify either:
a binary or "bit string" encoding (alpha_size = 2),
and then break it up into different-sized fields, using functions like
int2ithruj() to put a set of bits into an integer "index" and
indextofloat() to generate a set of discrete real values between
some lower and upper limits. However, in that case, crossover and
mutation operated on the BIT level. That is, crossover in the middle
of a field effectively performed a MUTATION at the same time (changing
the value of the field at each crossover point), and the mutation
operator generated ALL possible bit strings, so discretizations were
practically confined to powers of two, unless the user "packed" and
"unpacked" the bit string.
an "alpha_size" > 2, which put fields of cardinality alpha_size onto the
chromosome and preserved them under crossover and allowed only legal
values to be created by mutation, but ALL FIELDS WERE OF SAME
NOW: the user can also enter "1" as the alpha_size, which indicates that
the actual size of each field is set in user-defined function
app_set_field_sizes(), in the user's appxxxxx.c file. There, a global
array, field_sizes, can be set (MUST be set if alpha_size is entered
< 2). The system then preserves these fields appropriately, crossing
over only between fields, mutating only to legal values, etc. Even if
the user employs INVERSION, GALOPPS tracks the rearrangements of the
fields in each subpopulation, and automatically transforms the fields
to the "standard" order used in the fitness (objective) function objfunc()
before passing the individual to the fitness function for evaluation or
before moving the individual to another subpopulation during migration.
When inversion is in use, these transformations or remappings occur
automatically, without user intervention.
BOLTZMANN SCALING of fitnesses:
In addition to linear scaling, window scaling, and sigma-truncation, the
user may now elect Boltzmann scaling of .init_fitnesses (raw fitnesses) to
generate the (scaled) .fitness values actually used by the selection
routines. This may be used "manually" (by specifying:
autocontrol_selection = n
beta = (desired non-negative value for Boltzmann scaling).
As with all scaling operations in GALOPPS, this puts the SCALED fitness
value into the .fitness fields, and leaves the UNSCALED values in the
.init_fitness fields. All selection methods in GALOPPS use the SCALED
fitnesses (and if no scaling is done, .fitness values are set automatically
to the raw .init_fitness values), just as in Goldberg's Simple Genetic
Boltzmann Scaling and AUTOCONTROL_SELECTION:
Alternatively, GALOPPS Release 3.2 allows the user to elect
"autocontrol_selection". The user must then specify (or use the
automatic default for) beta_s_tilde. The automatic default is based
on the work of Shapiro and Pruegel-Bennett, and is determined by using
a recommended point on the graph of the ratio of the std. deviation of
fitnesses (across one generation) versus beta_s. The value of
beta_s_tilde is obtained by multiplying beta_s by sqrt(2 * log popsize).
From beta_s_tilde, beta is defined as:
beta_s_tilde / sqrt (std. dev. of scaled fitnesses).
Beta, calculated in this way, tends to keep selection pressure roughly
constant as the fitness distribution changes. If the suggested default
for beta_s_tilde is accepted, Shapiro and Pruegel-Bennett suggest that
it may tend to maximize the gain in mean fitness subject to not sharply
decreasing the diversity of the population. Thus, if
autocontrol_selection is y(es), GALOPPS calculates beta_s_tilde (based
on popsize) once, and then rescales beta from it at each generation,
using the current std. deviation of the scaled fitness distribution
(after any migrants have entered the population).
If autocontrol_selection is chosen, the selection function in suselect.c
must be compiled in. That is Stochastic Universal Sampling, which then
acts on the "optimally" Boltzmann-scaled values to sample the population
quite accurately according to the Boltzmann-scaled probabilities.
MULTIPLE LOCUS MUTATION OPERATOR:
Single-bit or single-locus mutation operators, applied at rates low enough
NOT to interfere with beneficial crossover, selection, etc., CANNOT easily
overcome even relatively simple deceptive problems, because no single-locus
change can produce a beneficial effect, but multiple-locus mutations are
very rare. Therefore, a Multiple Locus Mutation operator is introduced
to GALOPPS. (Non-single-locus mutation operators are commonly used in
evolution strategies, for example, which do not (classically) use
crossover, so must perform all of their exploration by using much
The multiple-locus mutation operator provided here (in multimut.c) is only
for value-based (not permutation-type) problems. It uses two probability
1) the probability (per chromosome) that a mutation occurs on the
2) the expected number of adjacent loci randomly mutated (from a random
starting point, and treating the chromosome as circular). This
number is a Poisson-distributed random variable with expected value
avg_mut_width. The user must set avg_mut_width in function
app_set_options(), if user wants to use multimut.c. However, the
mutation operator does not flip ALL loci in that range to new
values -- it sets them at random, so that some may retain their
former values, but any combination of them up to the width determined
for the current mutation may be changed.
GGA (Grouping Genetic Algorithm) Representation and Operators Added
A beta version of Emanuel Falkenauer's Grouping Genetic Algorithm, with an
example demonstrating its use for bin packing, has been added. This
implementation, by Brian Zulawinski, provides crossover and mutation operators
for the GGA representation, usable for approximating solutions to many
NP-complete problems, including bin packing, various types of assignment,
partitioning, etc. It is not yet extensively documented, but has been used
for solving makespan problems as well as bin packing.
SMALL "TWEAKS" to improve output:
Release 3.2 has many small, incremental improvements in the
output of the program -- for example, more thorough printing of all of the
options selected by the user in app_set_options, printing of int version of
chromosome when printstrings == y and chromosome is not binary, printing
of migrants when quiet == 0, etc.
GALOPPS, Erik Goodman