genesis.doc

王小平《遗传算法——理论、应用与软件实现》随书光盘

int length;      /* length of bit string                         */
double vect[];   /* floating point representation                */
int genes;       /* number of elements in vect                   */
{
	register int i;
	double sum;

	sum = 0.0;
	for (i = 0; i < length; i++)
		sum += (str[i] == '0');

	return (sum);
}

/************************************************ end of file ****/
.ft
.DE
.DS C
Figure 3: An evaluation function for counting 0's.
.DE

These and other commonly used test functions are provided in
the test.fns directory.


.ne 10
4. INSTALLING GENESIS

GENESIS should run on most machines with a C compiler.  This version has
run successfully on both Sun workstations and IBM PC's (using Turbo C). 
This section will address these systems.  The code has been designed to
be portable, but minor changes may be necessary for other systems. 

It is advisable to create a new directory, say /usr/yourname/genesis,
and copy the files from the distribution diskette into this directory. 
The distribution also includes a subdirectory called test.fns with some
sample evaluation functions. 

1) In the file "define.h", set exactly one of the compiler constants
UNIX or TURBOC to 1, as appropriate for your system.  Use UNIX for 32
bit UNIX compatible systems; use TURBOC for Turbo C on DOS machines. 

2) Copy either "makefile.unx" or makefile.dos" to Makefile, as appropriate.

3) To compile the system, use the make(I) command:

.ft CW
   % make install
.ft

This should compile the programs "setup", "report" and an executable
"ga.exe" on DOS or a random archive library "ga.a" under UNIX. 


.ne 10
5. RUNNING THE PROGRAMS

Before running the GA, execute the "setup" program, which prompts you
for a number of input parameters.  All of this information is stored in
files for future use, so you may only need to run "setup" once.  A
<return> response to any prompt gets the default value shown in
brackets.  The prompts are as follows:

-- the suffix for file names []:

If a string is entered, say "foo", then the files for this run will have
names like "in.foo", "out.foo", "log.foo", etc.  Otherwise, the file
names are "in", "out", "log", etc. 

-- Floating point representation [y]:

Unless this is declined, the user will be asked the specify the

-- number of genes:

Each gene will take on a range of floating point values, with a
user-defined granularity and output format.  The user will be asked to
specify for each gene: its minimum value; its maximum value; the
number of values (must be a positive power of 2); the desired output
format for this gene (using printf format, e.g., %7.2f).  The user may
also specify a repetition count, meaning that there a number of genes
with the same range, granularity, and output format.  When all genes
have been specified, the information is stored in the "template" file,
and Setup prompts for:

-- the number of experiments [1]:

This is the number of independent optimizations of the same function.

-- the number of trials per experiment [1000]:

-- the population size [50]:

-- the length of the structures in bits [30]:

If the "f" option is selected, this number will computed automatically from the
information collected above.

-- the crossover rate [0.60]:

-- the mutation rate [0.001]:

-- the generation gap [1.0]:

The generation gap indicates the fraction of the population which is
replaced in each generation. 

-- the scaling window [5]:

When minimizing a numerical function with a GA, it is common to define
the performance value u(x) of a structure x as u(x) = f_max - f(x),
where f_max is the maximum value that f(x) can assume in the given
search space.  This transformation guarantees that the performance u(x)
is positive, regardless of the characteristics of f(x).  Often, f_max is
not available a priori, in which case we may define u(x) = f(x_max) -
f(x), where f(x_max) is the maximum value of any structure evaluated so
far.  Either definition of u(x) has the unfortunate effect of making
good values of x hard to distinguish.  For example, suppose f_max = 100. 
After several generations, the current population might contain only
structures x for which 5 < f(x) < 10.  At this point, no structure in
the population has a performance which deviates much from the average. 
This reduces the selection pressure toward the better structures, and
the search stagnates.  One solution is to define a new parameter F_max
with a value of, say, 15, and rate each structure against this standard. 
For example, if f(xi) = 5 and f(xj) = 10, then u(xi) = F_max - f(xi) =
10, and u(xj) = F_max - f(xj) = 5; the performance of xi now appears to
be twice as good as the performance of xj.  The scaling window W allows
the user to control how often the baseline performance is updated.  If W
> 0 then the system sets F_max to the greatest value of f(x) which has
occurred in the last W generations.  A value of W = 0 indicates an
infinite window (i.e.  u(x) = f(x_max) -f(x)). 

-- the number of trials between data collections [100]:

-- how many of the best structures should be saved [10]:

-- how many consecutive generations are permitted without any
evaluations occurring [2]:

-- the number of generations between dumps [0]:

0 indicates no dumps will occur.

-- the number of dumps that should be saved [0]:

-- the options (see below) [cefgl]:

-- the seed for the random number generator [123456789]:

--  Rank_Min [0.75]:

This is the minimum expected number of offspring for ranking (used only
if option "R" is set).  The Ranking selection algorithm used here is a
linear mapping under which the worst structure is assigned Rank_Min
offspring and the best is assigned (2 - Rank_Min). 

Setup then echoes the input file, and exits.  The setup program should
be run at least once for each new evaluation function, but after that,
it may be more convenient to simply edit the input file to make minor
changes to the parameters.


.ne 6
Running GENESIS under UNIX

The UNIX Makefile produces a random archive called ga.a that can be
linked to the user's evaluation function.  Suppose the new evaluation
function is in file f7.c.  Then the following command will create an
executable called "ga.f7":

.ft CW
   % make f=f7 ga.f7
.ft

To make things easier, a shell script called "go" is provided.  This
command takes two arguments: the first is the root name of the source
file containing the evaluation function; the second is an optional file
suffix (as discussed under setup above).  The command:

.ft CW
   % go f7 x1
.ft

will compile the user's evaluation function, link it with the GENESIS
random archive, run the program using the in.x1 (and template.x1) input
files, and produce a report in file rep.x1.  The report is discussed
below. 

GENESIS was designed to encourage experiments with genetic algorithms. 
It is relatively easy for the user to create variations of GENESIS. 
Suppose for example that you wish to test a new crossover operator. 
Simply create a file called, say, "mycross.c" which contains a function
called "crossover()".  This file should "#include extern.h", in order to
access global variables (see cross.c).  Now, modify the Makefile so that
the loader gets your function instead of the crossover provided, i.e.,

.ft CW
   cc $(CFLAGS) -o ga.$f $f.o mycross.o ga.a -lm -lcurses -ltermlib
.ft

No recompilation of GENESIS itself is necessary.

In order to facilitate such experimentation, most of the important
variables in GENESIS are global.  All global identifiers in GENESIS
begin with a capital letter, to minimize conflicts with user-defined
global identifiers. 


.ne 6
Running GENESIS under DOS

The DOS version of GENESIS assumes a more rudimentary MAKE facility.  To
change the objective function, edit eval.c to compute the desired
evaluation, and recompile with the command:

   C:> MAKE

Execute the program by running GA.EXE:

   C:> GA

with an optional command line argument.  This approach can also be used
to change other functions in GENESIS.  There is also a file GO.BAT
provided that will compile, run and generate a report. 


.ne 6
6. FILES

"ckpt" - a checkpoint file containing a snapshot of important variables,
and the current population.  This file is produced if either the "d"
option is set or both the number of saved dumps and the dump interval
are positive.  This file is necessary for the restart option "r" to
work.  It is also sometimes interesting in its own right. 

"dump.<n>" - intermediate checkpoint files produced when the number of
saved dumps is greater than 1 and the dump interval is positive.  "ckpt"
is always identical to the latest dump. 

"in" - contains input parameters and initial random number seeds.  This
file is required. 

"init" - contains structures to be included in the initial population. 
This is useful if you have heuristics for selecting plausible starting
structures.  This file is read iff the option "i" is set. 

"log" - logs the dates of starts and restarts.  This file is produced if
the "l" option is set. 

"log.error" - logs error messages that precede aborting the program.
Check here first when problems occur.

"min" - contains the best structures found by the GA.  The number of
elements in "min" is indicated by the response to the "save how many"
prompt during setup.  If the number of experiments is greater than one,
the best structures are stored in "min.n" during experiment number n. 
This file is produced if the number of saved structures is positive. 

"out"- contains data describing the performance of the GA.  This file is
produced if option "c" is set. 

"rep" - summarizes the performance of the algorithm.  This file is
produced by the report program from the "out" file. 

"schema" - logs a history of a single schema.  This file is required for
the "s" option. 

"template" - describes the floating point representation, defined during
interaction with the setup program.  This file is required for the "f"
option.  This file probably should not be edited by hand, unless all
changes are properly reflected in the Length line of the "in" file.

If you gave a non-null response, say "foo", to the first prompt from
"setup", then all of the above files (except "dump" and "log.error")
will have the given extension, e.g., "in.foo", "out.foo", etc. 


.ne 6
7. OPTIONS

GENESIS allows a number of options which control the kinds of output
produced, as well as certain strategies employed during the search. 
Each option is associated with a single character.  The options are
indicated by responding to the "options" prompt with a string containing
the appropriate characters.  If no options are desired, respond to the
prompt by typing ".".  Options may be indicated in any order.  All
options may be invoked independently, except as noted below.

"a": evaluate all structures in each generation.  This may be useful
when evaluating a noisy function, since it allows the GA to sample a
given structure several times.  If this option is not selected then
structures which are identical to parents are not evaluated. 

"b": at the end of the experiments, write the average best value (taken
over all experiments) to the standard output. 

"c": collect statistics concerning the convergence of the algorithm. 
These statistics are written to the "out" file, after every "report
interval" trials.  The intervals are approximate, since statistics are
collected only at the end of a generation.  Option "c" implies option
"C".  Option "c" is expensive relative to option "C". 

"C": collect statistics concerning the performance of the algorithm. 
These statistics are written to the "out" file, after every "report
interval" trials.  The intervals are approximate, since statistics are
collected only at the end of a generation.  This information is also
printed on the screen under the "D" and "I" options. 

"d": dump the current population to "ckpt" file AFTER EACH EVALUATION. 
WARNING: This may considerably slow down the program.  This may be
useful when each evaluation represents a significant amount of
computation. 

"D": display mode.  Performance statistics are printed to the screen
after each generation. 

"e": use the "elitist" selection strategy.  The elitist strategy
stipulates that the best performing structure always survives intact