/************************************************************
;                                                           *
;  William M. Spears					    *
;  Navy Center for Applied Research in AI                   *
;  Naval Research Laboratory                                *
;                                                           *
;  This software is the property of the Department of the   *
;  Navy. Permission is hereby granted to copy all or any    *
;  part of this program for free distribution, however      *
;  this header is required on all copies.		    *
;							    *
;************************************************************/

Date: 9106.12

Summary:

	The enclosed C code contains functions useful for
	experimentation in Genetic Algorithms. The system is
	called GAC.

	There is no guarantee that the code will do what you
	expect or that it is error free. It is simply meant
	to provide a useful way to learn and experiment about
	some of the finer details of GA implementation.

	The implementation is a "standard" GA, similar to
	Grefenstette's work. Baker's SUS selection algorithm
	is employed, n-point crossover is maintained at 60%,
	and mutation is very low. Selection is based on 
	proportional fitness. This GA uses generations.
	It is also important to note that this GA maximizes.

	A note on crossover is in order. This version of GAC
	allows for n-point crossover, where n is less than
	the length of an individual (although there is no 
	check for that). It is also possible to run uniform
	crossover (see discussion below).

	GAC will display run-time information as it executes.
	GAC also has the ability to output this information into
	files. These statistics include	best behavior, online/
	offline measurements, convergence, and the number of
	reevaluations per generation. At this time the code is
	commented out. The user can simply remove a few comment
	symbols to use this facility. See run.c and geval.c for
	details.
	
	There is no ranking, adaptive operators, etc. We intend
	to explore these issues in future work.


The Evaluation Function:

	In order to use this code, the C function "myeval"
	must be defined. This is essentially the function that
	describes the space to be searched. Myeval must be defined
	in a file named "myeval.c". Myeval takes one
	argument, namely the index of the individual to be evaluated.
	This individual is stored in an array c[][].
	As an example, I could create a separate file with this function:


	#include "header.h"

	/* One Max Problem */

	double myeval (i)
	int i;
	{
	   int j, temp;
	  
	   temp = 0;
	   solution = length;
	   for (j = 1; j <= length; j++) {
	     if (c[i][j] == 1) temp++;
	   }
	   return((double)temp);
	}


	See "myeval.c" for a complete example. It is assumed
	that myeval will always return a quantity that is
	greater than (or equal to) 0.0. Also, if all the
	individuals in a given generation return 0.0, problems
	will arise.

Termination:

	The GA will terminate when the function "termination" (in
	term.c) returns true. This needs to be defined for any
	application of the GA. 

	The GA will start itself over if it hasn't terminated and
	has lost diversity.

	An example termination function is:

	int termination () { return(best == solution); }

	if you know what the solution should be. A good place to
	define the variable solution is in the myeval function
	(see above). If you don't know the solution, a possible
	termination function would be:

	int termination () { return(evals >= 100000);}

To Compile the Code:

	In the Unix world, a Makefile is provided. An executable
	called "gac" will be created.

	There is no dynamic allocation in GAC, and the maximum
	individual length (MAX_BITS) and maximum population size
	(MAX_POP) are set at compile time in header.h. The user
	can modify these if need be.

To Run the Code:

	GAC is called in the following manner:

	gac population-size bit-length number-of-crossover-points
	    number-of-experiments log-file

	Example:

	gac 100 30 2 5 mylog

	This calls GAC with 100 individuals in the population. Each
	individual has 30 bits. The 2 refers to the number of crossover
	points. In this case it will run 2-point crossover. GAC will
	interpret a 0 as a request for uniform crossover. 5 experiments
	are run (in order to average the results). When the solution is
	found, the solution and the number of evaluations is dumped to mylog.