Genitor Code Structure

1 Introduction

Genetic algorithms have been applied to a wide variety of optimization problems. However, it is possible to utilize many of the basic steps of the algorithm with little or no change, regardless of the application. With this in mind, the Genitor code has been software engineered to maximize code reuse across applications. Thus the developer of applications which are optimized by a genetic algorithm can concentrate more effort on application specific concerns.

1.1 Fundamental Functional Modules

The Genitor code is broken apart into functional modules. The following lists Genitor’s Fundamental Functional Modules. Section 2 describes the function calls available to utilize each fundamental functional module.

• Execution Parameter Manipulation – Process command line arguments.

– Set execution parameters.

• Genetic Pool Management – Allocate data structures for the genetic pool.

– Initialize the genetic pool.

– Sort the genetic pool by fitness.

– Insert offspring into the sorted genetic pool.

• Selection – Select two parents for genetic recombination.

– Bias functions for use in selection.

• Search Status – Compute average population fitness.

– Output status information.

– Save current status.

• Signal Handling – Recieve and process user-generated interrupts/signals.

• Utilities – Copy one gene to another.

1.2 Data Type Independence

The genetic algorithm may be applied to a number of applications; this inherently means that the algorithm must be able to manipulate a number of different data types. Therefore, the software engineering of the Genitor code includes methodologies for using the fundamental functional modules such that they are virtually data type independent. Section 3 describes these methodologies in detail.

1.3 Genetic Operators

Additionally, code modules for several genetic operators are included with the Genitor package. The basic crossover operator provided is Reduced Surrogate Crossover [ref]. At this point, this operator is standard within the genetic algorthim research community.

The choice of operator can be a very problem specific issue, and thus the development of new genetic operators is a significant research issue. A special Adaptive Mutation operator [ref] is included with the Genitor package. Also included with this package is the Edge Recombination Operator [ref] developed at Colorado State University for use with the classic Traveling Salesman Problem.

The genetic operator modules provided are discussed in detail in Section 4.

1.4 Examples Provided

Finally, several example main() driver functions are included with the Genitor package. These main() functions iteratively invoke the fundamental functionalities of a genetic algorithm and provide examples of usage protocols. Section 5 presents the sample problems included with the Genitor package.

2 Fundamental Functional Modules

2.1 Execution Parameter Manipulation

ga params.c, ga params.h The file ‘ga params.c’ respresents the functional module for manipulating genetic algorithm execution parameters. These subroutines can directly set the values of Genitor’s global variables, as are defined and declared in ga global.h, ga global extern.h

There is a global variable for each essential execution parameter of the genetic algorithm. The ‘ga global.h’ file contains the definition of Genitor’s global variables. It should be #included in Genitor’s main() driver procedure file, which you will write yourself ^{1}.

The header file ‘ga global extern.h’ contains extern declarations for these variables is available for inclusion in other files which require access.

By default, access to these global variables is restricted to the Execution Parameter Manipulation functional module (which initializes most of the global variables) and to the Signal Handling functional module (since calls to signal handling routines are invoked automatically and cannot be passed parameters directly). ^{2} All other functional modules are passed values via subroutine calls. The intent is to encourage modular programming and reduce dependence on global variables.

Genitor execution parameters may be manipulated with the following functions:

• Parse a Genitor command line.^{3}

       parse_command_line (argc, argv)
       int                 argc;   /*number command line args*/
       char               *argv[]; /*command line tags and values*/

• Parse a Genitor configuration file.^{4}

      int
      parse_config_file (filename)
      char               filename[];

• Set a Genitor execution parameter.

      int
      set_parameter (tag, value)
      char           tag;     /*each param has associated one char tag*/
      char           value[];

• Print the Genitor execution parameters.

1Your driver procedure must set the values of those global variables which are not set in this module. See section 5 Examples Provided for sample implementations

2In fact, the Execution Parameter Manipulation and Signal Handling modules depend on the naming of these globals and thus changing the names is NOT recommended.

3See the Genitor Command Line Options section for detailed requirements about command line format.

4See the Genitor Command Line Options section for detailed requirements about configuration file format.

void
print_params (fileptr)
FILE         *fileptr;  /*direct output to this file pointer*/

• Display a command line usage message.

void
usage();

2.2 Genetic Pool Management

ga pool.c, ga pool.h A genetic pool structure (POOL, POOLPTR) has three basic components:

1. a size variable (int) indicating the number of genes in the pool.

2. a string length variable (int) indicating the number of chromosomes (i.e. bits of data) per gene.

3. a data pointer (GENEPTR) indicating the location of current population of genes. Each gene (GENE) has two components:

(a) a worth variable (float) indicating the relative “fitness” or “goodness” of an individual gene.

(b) a string of data (GENE DATA, GENE DATAPTR).

This functional module provides methods for manipulating and managing the genetic pool.

• Manage memory for genetic pool.

GENEPTR
get_gene(string_length)
int      string_length;
POOLPTR
get_pool(string_length, pool_size)
int      string_length, pool_size;
void
free_gene(gene)
GENEPTR   gene;
void
free_pool(pool, start_pt)
POOLPTR   pool;
int       start_pt;

Note that free pool() includes a start pt parameter which allows you to specify the location in the genetic pool at which to begin freeing genes. Specifying a 0 will free all genes and deallocate the pool structure itself. Specifying a non-zero number N will free all genes from N to the pool size and set the pool size variable of the pool structure to N. This feature is included to assist in dynamic population sizing; it allows you to decrease the population size with little effort. However, if you wish to increase the population size, you should do the following:

1. allocate a new, larger pool of size M

2. copy the existing, smaller pool of size N into the first N slots of the new pool

3. free the smaller pool

4. initialize slots N through M in the new pool (see below).

• Initialize the genetic pool.

The genes may be randomly generated or input from a disk file, or some combination of both. The start pt and stop pt variables of each initialization routine allow you to directly control the contents of genetic pool data structure during initialization. Regardless, after initialization, the pool data array must be continguously initialized from 0 to the population size(-1).

The init pool() function provides the simplest form of pool initialization. If seed file is NULL, random init pool() is called to randomly initialize the genetic pool from start pt to stop pt. Thus, to randomly initialize the entire genetic pool, set start pt to 0 and stop pt to the population size. If seed file has a value, seed pool() is called to read initialization data from the indicated disk file. If the seed file does not contain enough data to fill the genetic pool from start pt to stop pt, init pool() calls random init pool() to complete the initialization.

All three initialization functions return the number of genes initialized. random init pool() and seed pool() may also be called directly if desired.

 int
 init_pool (seed_file, pool, start_pt, stop_pt, eval_fun)
 char      *seed_file;
 POOLPTR    pool;
 int        start_pt, stop_pt;
 float     (*eval_fun)();
 int
 random_init_pool(pool, start_pt, stop_pt, eval_fun)
 POOLPTR          pool;
 int              start_pt, stop_pt;
 float           (*eval_fun)();
 int
 seed_pool(fp, pool, start_pt, stop_pt, eval_fun)
 FILE     *fp
 POOLPTR   pool;
 int       start_pt, stop_pt;
 float    (*eval_fun)();

• Sort genetic pool according to fitness. The sort routine assumes a minimization problem, thus the most fit individuals have the lowest worth value. If your application requires the opposite sorting procedure (i.e. you want high values to be considered good and low values bad), the suggested method is to have the evaluation function negate its value before return.

void
sort_pool(pool)
POOLPTR   pool;

• Insert individuals into sorted genetic pool.

void
insert_gene(gene, pool)
GENE        gene;
POOLPTR     pool;

2.3 Selection

ga selection.c, ga selection.h This functional module provides the capability to choose individuals from the genetic pool for reproduction.

• Selection functions.

void
get_parents (mom, dad, pool, bias_fun, bias_num);
GENEPTR      mom, dad;
POOLPTR      pool;
int         (*bias_fun)();
float        bias;

• Bias functions.

int
linear (max, bias_num);

2.4 Search Status

ga status.c, ga status.h The file ‘ga status.c’ contains the functional module which manages displaying genetic algorithm execution status. There are subroutines to perform the following services:

• Compute average fitness of genetic pool.

float
avg_pool(pool)
POOLPTR  pool;

• Print the best, worst, average, and mean individuals in the population.

void
show_progress (fileptr, pool, current_generation)
FILE          *fileptr; /*direct output to this fileptr*/
POOLPTR        pool;
int            current_generation;

• Print the contents of genetic pool, beginning at start pt for count.

void
print_pool(fp, pool, start_pt, count)
FILE      *fp;
POOLPTR    pool;
int        start_pt,
count;

• Save the current state of an experiment for later restart. Two files will be created: a configuration file (.config) with the current settings of Genitor’s execution parameters and a pool file (.pool) with the population data.

void
dump_status (pool, basename)
POOLPTR      pool;
char         basename[]; /*basename of files in which to save state*/

Additionally, the Search Status module contains the following convenience routines:

• Pause execution (until input is received).

void
pause_it();

• Print a warning message to stderr.

void
warning(message)
char    message[];

• Print an (optional) message to stderr and exit the program with a -1. If the input message is non-NULL it is printed to stderr. The standard message “FATAL ERROR: Exiting.” is always printed immediately before exit.

void
fatal_error(message)
char       *message;

ga xdr.c, ga xdr.h Finally, Genitor provides a binary data format for population data disk files using the “External Data Representation” (XDR) standard. The XDR standard is most frequently used in conjunction with the RPC utility, but need not be and, indeed, is useful outside the domain of RPC procedures. XDR was designed to work across different languages, operating systems, and machine architectures. Thus, an XDR format binary file may be written on one machine, say a VAX running VMS, and read on another machine, say a SUN Sparc running Unix. Even when machine portability is not an issue, XDR is still a good choice because its protocols are standardized and reliable.

In practice, you will probably only want to use the XDR format when your application is dealing with floating point data. When you use floating point data, XDR can provide significant disk space savings. However, for other data types (character or integer) you are better off remaining with the normal ascii file format, as the overhead of XDR’s machine independent format actually makes files of this type larger than their ascii counterparts.

int
print_xdr (fp, pool)
FILE      *fp;
POOLPTR    pool;
int
read_xdr (fp, pool)
FILE     *fp;
POOLPTR   pool;

2.5 Signal Handling

ga signals.c, ga signals.h This functional module module provides signal handling capabilites during algorithm execution. The subroutine ‘setup signal’ may be called at the beginning of the main() driver routine to install signal handlers as appropriate. The file ‘ga signals.c’ is the suggested location for signal handling subroutines as well. The following signal handling routine is already provided:

• ga dump interrupt() This subroutine will print the current execution status to the screen and dump the current state of the genetic algorithm execution to file(s). ^{5}

2.6 Utilities

ga copy.c, ga copy.h This functional module provides a data translation and copying utility independent of data type.

 void
 gene_copy (gene1, gene2, string_length)
 GENEPTR    gene1, gene2;
 int        string_length;

5See show progress and dump status subroutines in Search Status section above.

3 Different Data Types

gene.h The Genitor algorithm may be applied to a number of problems, which inherently means that the algorithm must be able to manipulate a number of different data types. The Genitor code is designed to manipulated genes of various data types:

• Character This is generally used for the traditional binary encodings.

• Integer This might be used for a problem requiring a symbolic encoding, such as the Traveling Salesman Problem.

• Floating point This can be used for symbolic problems as well. For example this data reprensentation is well-suited to neural network weight optimization problems.

You may use essentially the same code and the same function calls regardless of the data type due to the centralization of type-specific information found in the header file ‘gene.h’. All references to Genitor’s population data type are made using the typedefs contained in ‘gene.h’. Thus, you should include ‘gene.h’ in any file which will reference Genitor’s population data and use the standard typedefs to do so. In other words, to refer to:

• the data type to be manipulated: use GENE DATA and GENE DATAPTR.

• a gene structure containing a string of data and a worth: use GENE and GENEPTR.

• a pool structure containing a population of genes, a population size, and a data string length: use POOL and POOLPTR.

The file ‘gene.h’ has three sections, one for each of the three data types enumerated above. Each section typedefs GENE DATA to the desired data type. Additionally, each section contains a few macros to insert data type specific methods and syntaxes at compile time. In particular, the INIT() macro is used to call the appropriate random initialization routines for each data type.^{6} Additionally, the input and output of data must be data type specific, and so three macros (GENE DATA IN FORMAT, GENE DATA OUT FORMAT(), and XDR DATA) ^{7} are defined for this purpose.

Since only one data type is active at a given time, the sections of the gene.h file are bracked by #ifdefs. The appropriate constant (BIN DATA, CHAR DATA, or FLOAT DATA) should be defined on the command line at compilation time (i.e. cc file.c -DCHAR DATA)

6INIT() is used by random init pool() in the file ga pool.c.

7GENE DATA IN FORMAT is used by seed pool() in the file ga pool.c. GENE DATA OUT FORMAT() is used by print pool() in the file ga status.c. XDR DATA is used by xdr GENE() in the file ga xdr.c.

4 Genetic Operators:

4.1 Reduce Surrogate Crossover

ga red surrog.c, ga red surrog.h Reduced Surrogate Crossover is a refined form of simple crossover. Simple crossover begins with choosing two points at which to break each of two genetic strings. Next, fragments from each string are used to build a third string, thus forming a new string (a child) which contains information from each of the initial two (parent) strings. Reduced Surrogate crossover uses this same idea, but enhances the simple algorithm by insuring that the exchanged information is unique to each parent (exchanging identical information is a waste of time). The Reduced Surrogate operator implementation provided with the Genitor package returns the number of (bit positions) differences between the two parent strings as the function value. This return value can be useful in triggering mutation based on population diversity.

  int
  red_surrogate_cross (mom_string, dad_string, string_length);
  GENE_DATA            mom_string[], dad_string[];
  int                  string_length;

4.2 Adaptive Mutation

ga mutate.c, ga mutate.h Adaptive mutation bases the amount of disruption to a given string on two factors: the relative similarity of its two parent strings, and a mutation rate. The more similar the two parent strings, the more likely mutation is to occur. The actual mutation which occurs is the product of this similarity and a fractional mutation rate. Thus, if the mutation rate is .20 and the parents of a particular string where identical, approximately 20% of the string will be mutated. Or, if the parents contained 50% unique information, only about 10% of the string will be mutated.

  void
  adaptive_mutate (gene_string, string_length, diffs, mutate_rate);
  GENE_DATA        gene_string[];
  int              string_length;
  int              diffs;
  float            mutate_rate;

4.3 Edge Recombination

ga tsp.c, ga tsp.h The Traveling Salesman Problem (TSP) is defined as follows: given a finite list of points and information about the distances between each possible pair of points, find the shortest circuit which visits every point exactly once. The TSP is a classic schedule optimization exercise, and methodologies which can be successfully applied to it are often of use in many types of scheduling problems.

The Edge Recombination operator invented at Colorado State University has had significant success in solving TSPs. The novelty and success of CSU’s operator is due to the fact that the operator focuses on manipulating the edges between points rather than the points themselves. Classically, genetic algorithms have worked by recombining the explicit data string representations of individual genes. For example, in function optimization, genetic recombination involves exchanging parameter settings which are positionally, explicitly encoded in the gene data strings. However, in a TSP, every string encodes the same explicit data (the list of cities to be visited). Further, the real information lies in the position of each data element in the string relative to other data elements (as opposed to the absolute positioning of the function optimization example, in which relative position is of little or no importance.)

The foundation of the Edge Recombination operator’s implementation is an edge table. Every time recombination takes place, an edge table representing the edges of two parent genes is created. A new gene is generated by selecting edges from this edge table, such that the new gene is constructed of interspersed edges from each parent.

The following section lists the functions which implement the Edge Recombination operator. These functions assume that each point in the circuit is represented symbolically by an integer. Thus, a 30 “city” tour will have city number 1, number 2, and so on. This integer naming scheme lends itself easily to an implementation based on array indexing. Before examining the Edge Recombination functions provided, a brief description of the edge table data structure is in order:

The edge table is an array of EDGE NODE structures. The array is indexed by city; for example the EDGE NODE for city 3 is found at edge table[3]. Each EDGE NODE enumerates the cities to which it has edges. Thus, if parent A is 52314 parent B is 41253, the EDGE NODE at edge table[3] will have references ^{8} to cities 2, 1, 5, and 4 since the edges containing 3 in the parents are 23, 31, 53, and 34. Likewise, the EDGE NODEs at edge table[2], [1], [5], and [4] will include a reference to city 3. A new gene is constructed by moving through the connections represented in the edge table, removing cities from the edge table as they are visited.

 EDGE_NODE *
 get_edge_table (num_points)
 int             num_points;
 free_edge_table (edge_table);
 EDGE_NODE        edge_table[];
 float
 build_edge_table (mom_string, dad_string, num_points, edge_table)
 GENE_DATA         mom_string[], dad_string[];
 int               num_points;
 EDGE_NODE         edge_table[];
 GENEPTR
 build_tour (edge_table, child_string, num_points)
 EDGE_NODE   edge_table[];
 GENE_DATA   child_string[];
 int         num_points;

8Actually, each EDGE NODE has an array of 4 elements to store connecting cities. Also, note that all 4 elements may not be used: often parents share edges and thus a particular EDGE NODE may only reference 2 or 3 other cities.

5 Examples

12