### GAc-1.0 README file

    /************************************************************
    ;                                                           *
    ;  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.