GALOPPS 3.2

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.
  OR
  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 CARDINALITY.

  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 and 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 Algorithm.
• 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 "smarter" mutation.) The multiple-locus mutation operator provided here (in multimut.c) is only for value-based (not permutation-type) problems. It uses two probability distributions: 1) the probability (per chromosome) that a mutation occurs on the chromosome, and 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.