#!/bin/sh
# This is a shell archive (produced by shar 3.49)
# To extract the files from this archive, save it to a file, remove
# everything above the "!/bin/sh" line above, and type "sh file_name".
#
# made 07/11/1992 19:00 UTC by schraudo@beowulf
# Source directory /a/gremlin/spare/rik/GA
#
# existing files will NOT be overwritten unless -c is specified
#
# This shar contains:
# length  mode       name
# ------ ---------- ------------------------------------------
#   9547 -r--r--r-- README
#  52175 -r--r--r-- GAucsd.doc
#   3905 -r-xr-xr-x etc/ga
#   1469 -r-xr-xr-x etc/gx
#   1345 -r--r--r-- etc/dispatch
#   9658 -r--r--r-- etc/wrapper
#    667 -r--r--r-- usr/GAhosts
#    584 -r--r--r-- usr/sample.in
#   1674 -r--r--r-- usr/f1_ga.c
#    362 -r--r--r-- usr/f1.c
#    275 -r--r--r-- usr/f2.c
#    327 -r--r--r-- usr/f3.c
#    480 -r--r--r-- usr/f4.c
#    724 -r--r--r-- usr/f5.c
#   3452 -rw-r--r-- src/Makefile
#   3977 -rw-r--r-- src/define.h
#   3804 -r--r--r-- src/format.h
#   8509 -r--r--r-- src/global.h
#   5378 -r--r--r-- src/best.c
#   2202 -r--r--r-- src/checkpt.c
#   1598 -r--r--r-- src/converge.c
#   4483 -r--r--r-- src/cross.c
#   2137 -r--r--r-- src/decode.c
#   1674 -r--r--r-- src/done.c
#   3020 -r--r--r-- src/dpe.c
#   2064 -r--r--r-- src/elitist.c
#   2013 -r--r--r-- src/encode.c
#   1229 -r--r--r-- src/error.c
#   1708 -r--r--r-- src/evaluate.c
#   1726 -r--r--r-- src/gap.c
#   2847 -r--r--r-- src/generate.c
#   4285 -r--r--r-- src/init.c
#   5809 -r--r--r-- src/input.c
#   8052 -r--r--r-- src/inset.c
#   2247 -r--r--r-- src/main.c
#   4237 -r--r--r-- src/measure.c
#   2130 -r--r--r-- src/mutate.c
#   2054 -r--r--r-- src/random.c
#   5704 -r--r--r-- src/report.c
#   2652 -r--r--r-- src/restart.c
#   3096 -r--r--r-- src/schema.c
#   2576 -r--r--r-- src/select.c
#   1721 -r--r--r-- src/setflag.c
#
# ============= README ==============
if test -f 'README' -a X"$1" != X"-c"; then
	echo 'x - skipping README (File already exists)'
else
echo 'x - extracting README (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'README' &&
___________________________________________________________________
-------------------------------------------------------------------
X     Name: GAucsd  Date: 920707  Version: 1.4  Patchlevel: 0
-------------------------------------------------------------------
<<<<<<<<<<<<<<<<<<                             >>>>>>>>>>>>>>>>>>>>
<<<<<<<<<<<<<<<<<< DO NOT EDIT ABOVE THIS LINE >>>>>>>>>>>>>>>>>>>>
X
X
Congratulations - it looks as if you have successfully unpacked the
source files for GAucsd 1.4 into this directory.  Instructions  for
the installation and use of the system are in the ``User's Guide to
GAucsd 1.4'' in the file GAucsd.doc.  A PostScript version  can  be
obtained  -- along with other related material -- via anonymous ftp
from cs.ucsd.edu (132.239.51.3), directory pub/GAucsd.
X
GAucsd has been developed in a Unix environment, but should be easy
to port to any platform that has a C compiler, and the make and awk
utilities.  A Unix 'sh' compatible command shell is helpful but not
necessary -- see the User's Guide for details.
X
NOTE: The installation procedure has changed significantly from the
previous version.  Even if you are familiar with GAucsd, you should
take a quick look at the installation section in the User's Guide.
X
Share and enjoy!
X
- Nici Schraudolph.                        San Diego, 7th July 1992
X
X
Changes since 1.2:
=================
X
Many thanks to those who spotted problems -- they are noted below
next to "their" bug.
X
1) Bug Fixes
------------
X
- random generator does not get stuck in a loop anymore; a patch
X  for this was distributed back in '91  (Peter J.B. Hancock)
X
- five missing values in second row of 'a' array in f5.c are now
X  supplied  (Bruce Rosen)
X
- avg and var arrays in report.c are now dynamically allocated
X  to prevent overflow  (Richard E. Gillilan)
X
- the wrapper and Ctoi() can now handle very long genes, including
X  those longer than the machine's integer size  (John C. Schultz)
X
- a missing external declaration for _eval() has been supplied in
X  best.c  (Sabih Gerez)
X
- simultaneous use of the subdirectory and remote execution features
X  in non-shared file space works now; min and cpt file names are still
X  not treated quite right though
X
X
2) Portability
--------------
X
Special thanks to Daniele Montanari for sharing his experiences in
porting GAucsd to DOS, and thus facilitating many improvements.
X
- all filenames are now DOS-friendly; e.g. "init.foo" --> "foo.ini"
X
- the use of popen() and pclose() in setup.c has been eliminated
X
- problems with GNU's gawk and "picky" C compilers have been resolved
X
- the two makefiles have been merged to simplify customization; the
X  merged file now uses macros to achieve high portability
X
- to reduce the frequent name clashes between GAucsd utilities and other
X  software, "ex" and "go" have mutated into "gx" and "ga" while "setup"
X  has metamorphosed to "inset"
X
- more support for heterogenous environments: library and utilities
X  are now compiled into machine-specific subdirectories
X
- the cryptic and Unix-specific "make dir" installation step has been
X  replaced with the "GAUCSD" environment variable  (Dave Demers)
X
X
3) Other Changes
----------------
X
- structured source tree with src, usr, bin & etc subdirectories
X
- the default population size suggested by "inset" is now a little
X  more reasonable (the usual disclaimers still apply though!)
X
- by popular request, crossover rate is now entered in "inset" on
X  a per-individual basis again, with a dynamically computed default
X
- the obsolete "clean" shell script has been thrown out
X
- define.h now uses <limits.h> to get machine constants (Norman Barth)
X
- global.h and extern.h have been collapsed into a single file to
X  improve code consistency
X
X
Changes since 1.1:
=================
X
1) Incompatibilities
--------------------
X
- the "ckpt" file format has changed;
X
- the Unpack() function used by low-level evaluation functions no longer
X  has a "length" parameter;
X
- due to a new feature (see 4) below) low-level evaluation functions may
X  be called with a negative "length" parameter.  The minimum action re-
X  quired to maintain compatibility is to insert "if (length < 0) return;"
X  at the start of your old "eval()" or "_eval()" functions.
X
Note that the 1.2ucsd "wrapper" takes these changes into account; your old
high-level evaluation functions can therefore be used without modification.
X
2) Bug Fixes
------------
X
- the non-portable bzero() function is no longer used;
- a bug causing the very first bit to always mutate has been fixed;
- problems with fully converged populations have been dealt with;
- sigma scaling no longer causes a small inadvertent generation gap;
- flawed genotype comparisons in cross.c and elitist.c have been fixed;
- bugs in the schema performance calculations have been corrected;
- restarts don't cause extraneous lines in the "out" file anymore;
- "go" no longer removes old out files (this has mangled restarts).
X
3) Refinements
--------------
X
- floats are printed out with more precision in various places;
- there's more validity checking when reading "in" & "ckpt" files;
- the experiment counter now starts at one, not zero ("ckpt" file);
X
- there is no more "length" argument to Unpack() since this function
X  produces garbage unless "length" is invariant;
X
- the min file may now contain duplicate genotypes if they cause differing
X  entries due to DPE, anti-aliassing ('A') or stochastic evaluation ('a');
X
- the source for the "random()" number generator has been included in the
X  distribution, eliminating the need to compile with "#ifdef genrand" on
X  non-BSD systems;
X
- since an immediate abort of the simulation may leave the data files in a
X  corrupt state, a third level of urgency - quit after current generation -
X  has been added to the signal handler.  INT (^C) signals are now caught as
X  well as TERM (kill) signals.
X
4) New Feature
--------------
X
The "min" files now also contain "phenotypes" (ie. the decoded parameters
to the fitness function) along with the encoded genome; this greatly aids
the interpretation of the file.  To make use of this feature, low-level
"eval()" or "_eval()" functions must return a string describing the most
recently evaluated phenotype when called with a negative "length" para-
meter.  This can be achieved by making the variables holding the phenotype
static - see file "f1-ga.c" for an example.  For high-level evaluation
functions the "wrapper" provides phenotype descriptions automatically.
X
X
X
Changes since 1.0:
=================
X
1) Bug Fixes
------------
- "go" can now handle remote execution when "l" flag is not set;
- fussy shells no longer complain about missing )'s in "go";
- the non-portable cbrt() library function is no longer used;
- a bug in the fitness scaling algorithm has been fixed.
X
2) New Features
---------------
- subdirectory structure for data files;
- re-editing of "in" files;
- application-specific parameters;
- sigma scaling;
- stochastic decoding for continuous search spaces ('A');
- super-uniform population initialization ('u');
- Dynamic Parameter Encoding (DPE).
X
X
Changes from GENESIS 4.5 to GAucsd 1.0:
======================================
X
1) Bug Fixes
------------
John Grefenstette's published 4.5 bug fixes:
- changed random seeds from int to unsigned int;
- corrected cross.c, line 81 to use i instead of temp;
- correct crossover if crossing points are within same byte.
X
Problems with machine-dependent data formats:
- get char and int sizes from <values.h>;
- modified use of bitmasks to allow for differing char sizes;
- corrected built-in Rand() to allow for differing int sizes;
- changed a number of variables from int to long.
X
Other sundry bugs:
- cross.c starts diff after Xing segment at xbyte2 + 1;
- prevented computation of log(0.0) in calculation of Mu_next;
- "go" without suffix reports to file "report", not "report.";
- "clean" stays quiet when it can't find optional files;
- made user input fields in setup.c longer (30 characters);
- repaired signal bell to ring when experiment terminates.
X
2) Code Improvements (Consistency & Efficiency)
-----------------------------------------------
- collapsed IN_FORMAT and OUT_FORMAT to single constant;
- introduced symbolic constant for checkpoint file format;
- genes are no longer unpacked for mutation;
- use random() generator, saving its entire state in dumps;
- diff outside Xing segment is computed more efficiently in cross.c;
- modified Makefile to better reflect dependencies.
X
3) Improved User Interface
--------------------------
- eval file name is default file suffix;
- "clean" exits on "" (instead of "q");
- maintain and start several named simulation queues for "ex";
- user notification upon completion of queue execution;
- better diagnostics from "report" in case of irregularities;
- crossover rates greater than 1.0 possible;
- setting "Max Gens w/o Eval" to 0 disables this feature;
- zero report interval reports on initial and final generations only;
- "G=..." line in go, ex and UserMakefile generated automatically;
- eval function may use packed gene directly for added speed;
- kill signals are caught for orderly termination.
X
4) Major Departures from 4.5
----------------------------
- MUTATION macro always flips one bit by default;
- dynamically computed default values in "setup";
- C_rate is entered on a per-bit basis;
- new termination criteria (Bias and Conv thresholds);
- wrapper for eval functions automates genotype decoding;
- ex/go can distribute simulations to remote machines.
SHAR_EOF
chmod 0444 README ||
echo 'restore of README failed'
Wc_c="`wc -c < 'README'`"
test 9547 -eq "$Wc_c" ||
	echo 'README: original size 9547, current size' "$Wc_c"
fi
# ============= GAucsd.doc ==============
if test -f 'GAucsd.doc' -a X"$1" != X"-c"; then
	echo 'x - skipping GAucsd.doc (File already exists)'
else
echo 'x - extracting GAucsd.doc (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'GAucsd.doc' &&
X
X
X
X
X                         _A_ _U_s_e_r_'_s_ _G_u_i_d_e_ _t_o_ _G_A_u_c_s_d_ _1_._4 (*)
X
X
X
X                              Nicol N. Schraudolph
X                                nici@cs.ucsd.edu
X                   Computer Science & Engineering Department
X                      University of California, San Diego
X                            La Jolla, CA 92093-0114
X
X                              John J. Grefenstette
X                             gref@aic.nrl.navy.mil
X         Navy Center for Applied Research in Artificial Intelligence
X                           Naval Research Laboratory
X                           Washington, DC 20375-5000
X
X
X                                  July 7, 1992
X
X
X
X                                    _A_b_s_t_r_a_c_t
X
X
X     This document describes the GAucsd system for function
X     optimization based on genetic search techniques.  Genetic
X     algorithms appear to hold a lot of promise as general purpose
X     adaptive search procedures.  However, the authors disclaim any
X     warranties of fitness for a particular problem.  The purpose of
X     making this system available is to encourage the experimental use
X     of genetic algorithms on realistic optimization problems, and
X     thereby to identify the strengths and weaknesses of genetic
X     algorithms.
X
X     GAucsd was developed by Nicol Schraudolph at the University of
X     California, San Diego; it is based on Genesis 4.5, a genetic
X     algorithm package written by John J. Grefenstette.  GAucsd and
X     related materials are available via anonymous ftp from cs.ucsd.edu
X     (132.239.51.3) in the pub/GAucsd directory or via electronic mail
X     from the first author, who welcomes bug reports, comments and
X     suggestions, and maintains a mailing list of users to announce
X     patches and new releases.
________________________________
X (*) Hardcopies of this document can be obtained by requesting technical
report CS92-249 from Technical Reports, CSE Department, UC San Diego, La
Jolla, CA 92093-0114.  There is a charge of 5 US$ for this service.
X
X
X
X                                        1
X
X
X
X
_1_ _ _I_n_t_r_o_d_u_c_t_i_o_n
X
X
This document describes the GAucsd software package written to promote the
study of genetic algorithms for function minimization.  Since genetic
algorithms are task-independent optimizers, the user must provide only an
evaluation function which returns a value when given a particular point in
the search space.  GAucsd was written in C under the Unix(1) operating system,
but should be portable to many platforms.
X
The remainder of this section gives a general overview of genetic algorithms
(GAs); for an in-depth introduction see [8].  Details on porting,
installing, and running GAucsd are provided in subsequent sections.
X
GAs are iterative procedures which maintain a population P of n candidate
solutions to an objective function f:
X
X
X                            P(t) = {x1(t); x2(t); ... xn(t)}
X
X
Each structure xi in population P(t) at time t is simply a binary string of
length l.  Generally, each xi represents a vector of parameters to the
function f(x), but the semantics associated with the vector is unknown to
the GA. During each iteration step, called a generation, the current
population is evaluated, and, on the basis of that evaluation, a new
population of candidate solutions is formed.  A general sketch of this
procedure --- known as generational GA --- is shown in Figure 1.
X
X
X
X                 t <- 0;
X                 initialize P(t);
X                 evaluate P(t);
X                 while (not finished) do
X                 begin
X                         t <- t + 1;
X                         select P(t) from P(t - 1);
X                         operate on P(t);
X                         evaluate P(t);
X                 end;
X
X
X
X                 Figure 1:  A Generational Genetic Algorithm.
X
X
The initial population P(0) is usually chosen at random.  Alternately, the
initial population may contain heuristically chosen initial points.  In
either case, the initial population should contain a wide variety of
structures.  Each structure in P(0) is then evaluated.  For example, if we
are trying to minimize a function f, evaluation might consist of computing
and storing {f(x1); ... f(xn)}.
________________________________
X  (1) Unix is a trademark of Bell Laboratories
X
X
X
X                                        2
X
X
X
X
The structures of the population P(t + 1) are chosen from the population P(t)
by a randomized selection procedure that ensures that the expected number of
times a structure is chosen is proportional to that structure's performance,
relative to the rest of the population.  That is, if xj has twice the
average performance of all the structures in P(t), then it is expected to
appear twice in population P(t + 1).  At the end of the selection procedure,
population P(t + 1) contains exact duplicates of the selected structures in
population P(t).
X
In order to search other points in the search space, some variation is
introduced into the new population by means of idealized genetic operators.
The most important operator is called crossover.  Under the crossover
operator, two structures in the new population exchange portions of their
binary representation.  This can be implemented by choosing a point at
random, called the crossover point, and exchanging the segments to the right
of this point.  For example, let
X
X
X                       x1 = 100:01010 and x2 = 010:10100;
X
X
and suppose that the crossover point has been chosen as indicated.  The
resulting structures would be
X
X
X                       y1 = 100:10100 and y2 = 010:01010.
X
X
Crossover serves two complementary search functions.  First, it provides new
points for further testing of the schemata already present in the
population.  In the above example, both x1 and y1 are representatives of the
schema 100#####, where the # means "don't care".  Thus, by evaluating y1,
the GA gathers further information about this schema.  Second, crossover
introduces representatives of new schemata into the population.  In the
above example, y2 is a representative of the schema #1001###, which is not
represented by either parent.  If this schema represents a high-performance
area of the search space, the evaluation of y2 will lead to further
exploration in this part of the search space.
X
Termination may be triggered by finding an acceptable approximate solution
to f(x), by fixing the total number of evaluations, or some other
application-dependent criterion.
X
The basic concepts of GAs were developed by John Holland [9] and his
students [2, 4, 7, 10].  Theoretical considerations concerning the
allocation of trials to schemata [4, 9] show that genetic techniques provide
a near-optimal heuristic for information gathering in complex search spaces.
A number of experimental studies [2, 3, 4] have shown that GAs exhibit
impressive efficiency in practice.  While classical gradient search
X
X
X
X                                        3
X
X
X
X
techniques are more efficient for problems which satisfy tight constraints
(e.g., continuity, low dimensionality, unimodality, etc.), GAs consistently
outperform both gradient techniques and various forms of random search on
more difficult (and more common) problems, such as optimizations involving
discontinuous, noisy, high-dimensional, and multimodal objective functions.
GAs have been applied to various domains, including numerical function
optimization [2, 3], adaptive control system design [5], and artificial
intelligence task domains [12].
X
X
X
_2_ _ _I_n_s_t_a_l_l_i_n_g_ _t_h_e_ _S_y_s_t_e_m
X
X
This section explains if and how GAucsd can be ported to various computing
platforms.  It assumes that you have successfully obtained and unpacked the
GAucsd source distribution into a designated directory.  You will see four
subdirectories there:  src contains source code for the GAucsd library and
utilities, usr has various templates for files users have to write, etc
contains a few sh and awk scripts, and bin is where the compiled binaries
will be installed.
X
If you want to run GAucsd on multiple platforms, follow the instructions
below for each type of machine in succession.  Since this version of GAucsd
uses machine-dependent subdirectories for binaries, you can compile for
multiple target platforms from a single copy of the source distribution on a
shared file system.
X
X
X
2.1  Requirements
X
X
GAucsd has been developed in a Unix environment, but should be easy to port
to any platform that has a C compiler and the make and awk utilities.  GNU
versions of cc, make and awk are available as source distributions and also
as binaries free of charge for a variety of machines.
X
Note that since make and awk are called as such from deep within the GAucsd
package, they must be available as commands by that name.  Thus if you are
using GNU's gawk for instance, you must define awk as a link or alias for
gawk on all target platforms.  Also make sure that make and awk are both in
your command search path.
X
GAucsd uses the names inset, report, and (on Unix systems) ga & gx for its
own commands; if one of these clashes with some other command on your
system, you have to take steps to resolve the name conflict.  The gx command
available on Unix platforms uses "mail $USER" to notify users of completed
experiments; if this won't work on the target machine, modify the mailing
address in file etc/gx accordingly, or remove the mail command altogether.
X
X
X
X                                        4
X
X
X
X
2.2  Customizing the Makefile
X
X
The top portion of the file src/Makefile needs to be customized for each
target platform.  For many platforms this will be the only modification
necessary; on most Unix systems the supplied makefile will work without any
changes.  On each successful installation, a copy of the makefile will be
saved along with the binaries.
X
Since binaries are installed in machine-dependent subdirectories, the
makefile needs the variable MACH set to a directory name that is unique to
each target platform.  The default is set to the output of the mach command,
which on many Unix systems returns the machine type.  If some of your target
platforms do not have a mach command, you may consider writing one, although
often it will be easier to just manually set MACH to a suitable name for
each target platform.
X
Next, you should set CFLAGS to whatever compiler flags you wish to set on
this particular platform.  In particular, you should add -DNOGAGX to CFLAGS
for platforms where you can't (or don't want to) use the ga and gx utilities
for distributed computing, which work only in certain types of Unix
environment.
X
Further macros that may need to be customized deal with the command shell's
behavior, file naming conventions, file handling and compilation commands on
the target platform; all of these are documented in the makefile itself.
X
X
X
2.3  Building GAucsd
X
X
Define the environment variable GAUCSD to be the full pathname to the
directory you unpacked the GAucsd source distribution in.  From there,
change into the src subdirectory and type "make all".  If all goes well,
type "make install", then "make clean".  If you get errors due to missing
include files, check the top section of file define.h for details on how
to work around these problems.  Finally, communicate to users where you
have installed GAucsd so that they can set the GAUCSD variable in their
environment.
X
X
X
_3_ _ _M_a_j_o_r_ _P_r_o_c_e_d_u_r_e_s
X
X
This section gives a more detailed description of the genetic algorithm
implemented in the GAucsd library.
X
X
X
X                                        5
X
X
X
X
3.1  Initialization
X
X
File init.c contains the initialization procedure, whose primary
responsibility is to set up the initial population.  If you wish to seed the
initial population with heuristically chosen structures, put the structures
in the ini file (see Section 11) and use the i option (see Section 10).  The
rest of the initial population is filled with random structures, or by a
reduced-variance technique for super-uniform initialization if the u option
is used.
X
X
X
3.2  Generation
X
X
As previously mentioned, one generation (see generate.c) comprises the
following steps:  selection, mutation, crossover, evaluation, and some data
collection procedures.
X
X
X
3.3  Selection
X
X
Selection is the process of choosing structures for the next generation from
the structures in the current generation.  The selection procedure (see file
select.c) is a stochastic procedure that guarantees that the number of
offspring of any structure is bounded by the floor and the ceiling of the
(real-valued) expected number of offspring.  This procedure is based on an
algorithm by James Baker.  The idea is to allocate to each structure a
portion of a spinning wheel proportional to the structure's relative
fitness.  A single spin of the wheel assigns the number of offspring to all
structures.  This algorithm is compared to other selection methods in [1].
The selection pointers are then randomly shuffled, and the selected
structures are copied into the new population.
X
X
X
3.4  Mutation
X
X
After the new population has been selected, mutation is applied to each
structure in the new population (see mutate.c).  Each position is given a
chance M_rate of undergoing mutation.  This is implemented by computing an
interarrival interval between mutations, assuming a mutation rate of M_rate.
The mutation macro in define.h determines what happens if mutation does
occur; the default action is to flip the bit value for that position.  The
mutated structure is then marked for evaluation.
X
X
X
3.5  Crossover
X
X
Crossover (see cross.c) exchanges alleles among C_rate * Popsize adjacent
X
X
X                                        6
X
X
X
X
pairs of structures in the new population.  Note that a C_rate greater than
1.0 will cause some structures to undergo several crossovers.  Crossover
might be implemented in a variety of ways, but there are theoretical
advantages treating the structures as rings, choosing two crossover points,
and exchanging the sections between these points [4].  The segments between
the crossover points are exchanged, provided that the parents differ
somewhere outside of the crossed segment.  If, after crossover, the
offspring are different from the parents, then the offspring replace the
parents, and are marked for evaluation.
X
X
X
_4_ _ _F_i_t_n_e_s_s_ _S_c_a_l_i_n_g
X
X
When minimizing a numerical function with a GA, it is common to define the
performance value u(x) --- the expected number of offspring --- of a
structure x as u(x) = F - f(x), where F is a large baseline function value.
Negative values of u(x) can either be zeroed or avoided altogether by
setting F to fmax , the maximum value that f(x) can assume in the given
search space.  Often fmax is not available a priori, in which case we may
use F = f(xmax), the maximum value of any structure evaluated so far.
X
Either choice of F has the unfortunate effect of making good values of x
hard to distinguish.  For example, suppose fmax = 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
selective pressure towards better structures, and the search stagnates.  One
solution is to update the baseline to, say, F = 15, and rate each structure
against this new standard.
X
The problem is then to automate the baseline update in a manner that keeps
the amount of selective pressure under control.  GAucsd provides two
alternative fitness scaling algorithms for this task:  window scaling and
sigma scaling.
X
Window scaling allows the user to control how aggressively the baseline is
updated via the scaling window size W.  If W > 0, the system sets F 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. F = f(xmax).  Note that
this method is overly attentive to individuals in that a single "lethal"
genotype can all but eliminate selective pressure for W  generations.
X
Sigma scaling (studied by Forrest [6]) achieves more robust performance by
setting F to the average population fitness plus a certain multiple, the
sigma scaling factor s, of the standard deviation of population fitness;
structures worse than F are assigned zero performance.  Note that for a
structure x with f(x) one standard deviation better than the population
average, u(x) = (s + 1)/s; sigma scaling thus provides very direct control
over the selection pressure.  Values for s between 1 and 5 are commonly used
in practice.
X
X
X
X                                        7
X
X
X
X
_5_ _ _D_y_n_a_m_i_c_ _P_a_r_a_m_e_t_e_r_ _E_n_c_o_d_i_n_g
X
X
When encoding real-valued parameters of the evaluation function on a binary
genotype there is a conflict between the desire to keep the genes short for
good convergence and the need to know the result with a certain precision.
An appropriate --- but cumbersome --- reaction when faced with this dilemma
would be to first run an experiment with short genes to quickly obtain a
low-precision result, then repeating it with ever-increasing precision while
keeping the genotype short by restricting the search to the previously
identified solution region.
X
Dynamic Parameter Encoding (DPE) [11] implements this strategy of iterative
refinement by gathering convergence statistics of the top two bits of each
parameter.  Whenever the population is found to be converged on one of three
subregions of the search interval for a parameter, DPE invokes a zoom
operator that alters the interpretation of the gene in question such that
the search proceeds with doubled precision, but restricted to the target
subinterval.  In order to minimize its disruptiveness the zoom operator
preserves most of the phenotype population by modifying the genotypes to
match the new interpretation.
X
The DPE algorithm logs its zoom activity in the dpe file (see Section 11).
Since the zoom operation is irreversible it has to be applied conservatively
in order to avoid premature convergence; to this end DPE smoothes its
convergence statistics through exponential historic averaging.  The time
constant of this filtering process is an important characteristic of the
algorithm:  the smaller its value, the bolder DPE becomes, accenting the
risks and benefits associated with fast convergence.
X
Note that although DPE often facilitates a radical reduction of gene length,
there is a point beyond which the function to be optimized will no longer be
sampled with enough resolution to yield useful results.  In particular if
the basin of attraction around the optimum is small, a low-resolution search
might miss it altogether.  Of the five test functions provided in the
$GAUCSD/usr subdirectory for instance, four can be solved with DPE using as
little as three bits per parameter, but the multimodal function f5 requires
twice as much.
X
The DPE algorithm is activated by selecting a non-zero smoothing time
constant in the inset program; it may be selectively disabled for certain
parameters via a b or g flag in the GAeval comment line (see Section 7).
Since DPE is based on strong assumptions about the interpretation of the
genome it is meant to be used in conjunction with a high-level evaluation
function as facilitated by the wrapper described below.
X
This quick overview was intended to encourage experiments with the DPE
algorithm; many aspects have been somewhat glossed over.  For a more
detailed discussion please refer to [11].
X
X
X
X                                        8
X
X
X
X
X
_6_ _ _E_v_a_l_u_a_t_i_o_n_ _P_r_o_c_e_d_u_r_e
X
X
To use GAucsd, the user must write an evaluation procedure.  There are three
levels of abstraction at which such a procedure may be written.  At the
lowest level a function called _eval() receives a pointer to the genome and
its length in bit as input and returns a double precision value.  It must be
declared as
X
X
X         double _eval(genome, length)
X         char genome[];
X         int length;
X
X
The interpretation of the genome is entirely up to the user, thus allowing
great flexibility and efficiency.  However, the packed form of the genotype
can be awkward to deal with if the parameters are not aligned with byte
boundaries.  Therefore an evaluation function eval() may be declared instead
which receives an unpacked genotype:
X
X
X         double eval(buff, length)
X         char buff[];
X         int length;
X
X
where buff is a character array containing (integer) zeroes and ones, and
length indicates the length of the array buff.  This form of evaluation
function was used in the original Genesis software and is assisted by some
functions which facilitate its interpretation.  One is called Ctoi():
X
X
X         double Ctoi(buf, length)
X         char buf[];
X         int length;
X
X
and takes two arguments, a pointer to a char array and a length indicator.
Ctoi() returns the value computed by interpreting the buffer as an unsigned
binary string with the indicated length.  If the A option is used, Ctoi()
will add a random fractional part to the value in order to avoid aliasing
effects that might otherwise compromise the search of continuous spaces (see
Section 10).
X
Gray codes are often used to represent integers in genetic algorithms.  They
have the property that adjacent integer values differ at exactly one bit
position; their use avoids the unfortunate effects of Hamming cliffs in
which adjacent values, say 31 and 32, differ in every position of their
fixed point binary representations (01111 and 10000, respectively).
X
X
X
X                                        9
X
X
X
X
/******************************************  file f1.c  ****/
X
X
double _eval(genome, length)
char genome[];
int length;
{
X    register int i;
X    char buff[30];
X    char outbuf[10];
X    double sum = 0.0;
X
X
X    /* phenotype description, must be static */
X    static double x[3];
X
X
X    /* return previous phenotype on request  */
X    if (length < 0)
X         sprintf(genome, ""n%lf %lf %lf", x[0], x[1], x[2]);
X    else
X    {
X         /* GAlength 30 */
X         if (length != 30) Error("length error in eval");
X
X
X         /* unpack the genotype */
X         Unpack(genome, buff);
X
X
X         for (i = 0; i < 3; i++)
X         {
X             /*  convert next 10 bits to an integer  */
X             Degray(&buff[i*10], outbuf, 10);
X             x[i] = Ctoi(outbuf, 10);
X
X
X             /*  scale x to the range [-5.12, 5.11]  */
X             x[i] = (x[i] - 512.0) / 100.0;
X
X
X             /*  accumulate sum of squares of x's  */
X             sum += x[i]*x[i];
X         }
X    }
X    return(sum);
}
X
X
******************************************* end of file ****/
X
X
X                  Figure 2:  A Low-level Evaluation Function.
X
X
X
X                                       10
X
X
X
X
Functions which translate between Gray code and fixed point representations
are provided:
X
X
X         Gray(inbuf, outbuf, length)
X         char *inbuf, *outbuf;
X         register int length;
X
X
X         Degray(inbuf, outbuf, length)
X         char *inbuf, *outbuf;
X         register int length;
X
X
In the function Gray(), inbuf contains the fixed point integer, one bit per
char, while outbuf gets the Gray coded version, one bit per char.  In
Degray(), inbuf contains the Gray code integer and outbuf gets the
corresponding fixed point integer.
X
A procedure Error() is provided which writes an error message to both the
file errors and the standard error output (stderr), and then terminates the
program.  Functions for re-encoding, packing and unpacking genomes are also
provided --- see the files encode.c and decode.c in $GAUCSD/src for details.
X
Figure 2 shows a low-level evaluation function which makes use of these
GAucsd procedures.  Note how a call to the evaluation function with negative
length parameter is used by GAucsd to ask for a phenotypic description of
the most recently evaluated structure.  This description is provided
automatically if you use the wrapper (see Section 7) and will be printed in
the min file (see Section 11).
X
A comment of the form /* GAlength l */ (as shown in Figure 2) is recognized
by the inset program and used to set the default value of the "Genome
Length" parameter.  It may safely be omitted but is provided automatically
by the wrapper.
X
It is often desirable to pass parameters to the evaluation function that
might vary from experiment to experiment but should not be subjected to the
GA search.  GAucsd uses a method similar to that of passing C command line
arguments to make such application-specific parameters, entered via the
inset program, accessible through the declarations:
X
X
X         extern int   GArgc;
X         extern char *GArgv[];
X
X
which, again, the wrapper provides for you.  Note that each of the GArgc
string parameters in GArgv[] may contain blank spaces but not '\0' or '\n'.
X
If you are writing evaluation functions as shown in this section, GAucsd
leaves the interpretation of the genome entirely up to you.  While this
X
X
X
X                                       11
X
X
X
X
affords great flexibility, it also means that the DPE technique --- which
assumes a known layout of gray-coded parameters on the genome --- cannot be
used unless additional information about this layout is provided.  This can
be done by declaring and initializing the global variables GAgenes, GAposn,
GAbase and GAfact in the evaluation file.  For further details, consult the
sample file f1_ga.c in $GAUCSD/usr.
X
X
X
_7_ _ _T_h_e_ _W_r_a_p_p_e_r
X
X
GAucsd includes an awk script called wrapper which provides a higher level
of abstraction:  by supplying the code for decoding and printing the
evaluation function parameters automatically, it allows the direct use of
most C functions as evaluation functions.  The only restrictions are:
X
X
X   o the function must not be called _eval();
X
X   o it must return a scalar type or a pointer to such a type;
X
X   o all its parameters must be simple C types as described below, or
X     pointers to such types (this allows for passing arrays by reference).
X
X
The wrapper gets invoked from the inset program and constructs from
<name>.c the file <name>_ga.c which includes a function _eval(gene, length)
interfacing your evaluation function to the GAucsd system.  In order
to do its job the wrapper needs a comment line (occurring after the first
declaration of your evaluation function) in <name>.c which looks as
follows:
X
X
X         /* GAeval <fn> <field1> <field2> ...  */
X
X
where <fn> is the name of your evaluation function, possibly prefixed with
an asterisk for indirect return values.  It is followed by one or more
fields, where each field specifies a parameter to the evaluation function.
White space delimits fields and hence may not occur within fields.  The
format of an individual field is (in this order):
X
X
X  1. an integer indicating the number of bits to be used for representing
X     this parameter on the genotype.  This must be between 1 and the number
X     of bits of an "int" on your machine to make sense.
X
X  2. (optional) a colon followed by a number r specifying the range of the
X     parameter.  This means that the parameter will range from -r (or zero
X     if unsigned --- see below) inclusive to +r exclusive.  If omitted, the
X     range is determined directly from the number of bits used to represent
X     the parameter.  A second number s, separated by a colon, may be
X
X
X
X                                       12
X
X
X
X
X     specified, forcing a range from r inclusive to s exclusive.  Both r and
X     s may contain a decimal point and a sign, but no exponent, and s must
X     be strictly greater than r.
X
X  3. a character string containing in any order, in upper or lower case:
X
X        o exactly one of c, s, i, l, f or d, specifying the parameter type as
X          char, short, int, long, float or double respectively;
X
X        o (optional) a b or g indicating that the parameter is to be encoded
X          in binary or Gray code, respectively.  Either character causes the
X          parameter to be left alone by the DPE algorithm which relies on the
X          default Gray coding for its operation.
X
X        o (optional) a u indicating that the parameter is unsigned.  For
X          float or double parameters the type will not change, but the
X          default range will be from zero to r instead of -r to r (see
X          above).
X
X  4. (optional) an integer n indicating replication:  the parameter is a
X     pointer to an array of n values of the same format.  Values of 1
X     (simple indirection) or 0 (same as no n at all) for n are allowed.
X
X
Space for parameters on the genotype is allocated from the left in order of
the fields.  Figure 3 demonstrates how the evaluation function of Figure 2
is greatly simplified when the wrapper is used.  The function shown is the
first of a suite of five test functions that have been used extensively in
the GA community since their introduction by De Jong [4]; all five can be
found in the $GAUCSD/usr subdirectory.
X
If awk is not available on your system, you will not be able to use the
wrapper.  You can emulate its operation manually by writing your low-level
evaluation function in a file ending with _ga.c and including the additional
data the wrapper normally provides.  Please refer to the sample wrapper
output file f1_ga.c in $GAUCSD/usr for further details.
X
X
X
_8_ _ _S_e_t_t_i_n_g_ _u_p_ _E_x_p_e_r_i_m_e_n_t_s
X
X
In order to use GAucsd, you must set the variable GAUCSD in your
environment to the full pathname of the directory where GAucsd was
installed on your system.  You also have to add the directory where the
GAucsd binaries for your system are located --- a subdirectory of
$GAUCSD/bin whose name reflects the machine type --- to your command
search path.  On Unix systems, the directory $GAUCSD/etc should be added
to the command search path as well.  You may want to put the commands that
achieve this into a file that gets executed automatically whenever you use
the system, such as .cshrc under Unix or AUTOEXEC.BAT under DOS.
X
X
X
X                                       13
X
X
X
X
/****************************************  file f1.c  ****/
X
X
double f1(x)
register double *x;
{
X    register int i;
X    register double sum;
X
X
X    /*  accumulate sum of squares of x's  */
X    for (sum = 0.0, i = 0; i < 3; i++)
X         sum += x[i]*x[i];
X    return (sum);
}
X
X
/* GAeval f1 10:5.12d3 */
X
X
/**************************************** end of file ****/
X
X
X            Figure 3:  Same Evaluation Function using the Wrapper.
X
X
X
The easiest way to write an evaluation function for GAucsd to optimize is to
copy one of the examples provided in $GAUCSD/usr and use it as a template.
Once you have the desired evaluation function in your current directory, run
the inset program to construct an in file.  As inset prompts for various GA
parameters, hitting return in response results in the default value shown in
brackets being used.  Many defaults (indicated with a * below) are computed
on the fly by inset from previously entered data.
X
It is important to keep in mind that while these "dynamic defaults" are a
nice feature, the heuristics employed by no means guarantee a good, nor
indeed even adequate setting of GA parameters.  The research on how to find
good values for them is still in its infancy, and as of today there are no
strong results that could replace the intuitive exploration of this
parameter space by the experimenter.
X
The parameters set via inset are:
X
X
X   o Evaluation File Name [f1]:
X
X     At this point make is called to preprocess, compile and link the
X     appropriate files.  If the wrapper aborts with an error, examine the
X     _ga.c file for diagnostics.
X
X   o Name of Experiment [*]:
X
X     The basename for all files associated with this experiment (see
X     Section 11); it defaults to the name of the evaluation file.  If an in
X
X
X
X                                       14
X
X
X
X
X  file with the chosen basename exists already, it will be read at this
X  point and used as default for subsequent prompts.  If the existing in
X  file is read-only, you will be asked to provide an alternative basename
X  for writing --- thus inset may be used to re-edit existing in files, or
X  to make modified copies from a read-only master file.  If there is no
X  appropriate in file, inset will create it and try to guess reasonable
X  defaults as described above.
X
o Genome Length [*]:
X
X  If there is a comment of the form /* GAlength l */ --- as produced
X  automatically by the wrapper --- in the evaluation file, the default
X  length suggested will be l.
X
o Population Size [*]:
X
X  The number of structures in the population.
X
o Trials per Run [*]:
X
X  The maximum number of function evaluations in each GA run.  When they
X  are computationally expensive, trials are a better indicator of
X  processing time than the number of generations.
X
o Number of Runs [1]:
X
X  The number of independent optimizations of the same function in this
X  experiment; multiple runs can increase the chance of finding a good
X  solution.
X
o Crossing Rate (per individual) [*]:
X
X  The expected number of two-point crossovers for each structure.
X
o Mutation Rate [*]:
X
X  The expected number of mutations for each bit in the population.
X
o Generation Gap [1.0]:
X
X  The generation gap is the percentage of the population which is
X  replaced in each generation.  Note that GAucsd operates very
X  inefficiently for small generation gaps.
X
o Windowsize [-1]:
X
X  The size of the scaling window (see Section 4).  Zero indicates
X  infinite size, and any negative value indicates sigma scaling.
X
o Sigma Scaling Factor [2.0]:
X
X  Used only when sigma scaling is chosen.
X
X
X
X                                    15
X
X
X
X
X   o DPE Time Constant [0]:
X
X     This is the time constant (in generations) with which the DPE algorithm
X     smoothes its convergence statistics through exponential historic
X     averaging in order to avoid premature convergence.  A value of zero
X     switches DPE off altogether.
X
X   o Convergence Threshold [*]:
X
X     The percentage of the population that needs to have the same value in a
X     given allele for it to be considered converged.  Since it is used as
X     the trigger threshold for the zoom operator, this is an important
X     parameter for DPE. The default value follows an analysis in [11].
X
X   o Max Alleles to Converge [*]:
X
X   o Maximum Bias [0.99]:
X
X   o Max Gens w/o Evaluation [2]:
X
X
The three parameters above allow termination of a run when a certain bias is
reached, a certain number of alleles have converged, or a certain number of
generations has passed without creating a new genome.  If any of these
conditions is met, the remainder of the run will be "faked" by reprinting
the current statistics an appropriate number of times; this simplifies
post-processing of GAucsd data e.g. into graphs.  The bias check can be
disabled with a value of 1.0 or greater, the other two with a value of zero.
X
X
X   o Report Interval [*]:
X
X     The number of evaluations between data collections; zero indicates
X     collections at the start and end of each run only.
X
X   o Structures Saved [*]:
X
X     How many of the best structures should be saved to the min file.
X
X   o Dump Interval [*]:
X
X     The number of generations between data dumps to the cpt file; zero
X     indicates that no dumps will be made.
X
X   o Dumps Saved [1]:
X
X     The number of dump files that should be kept.  One means that only the
X     current dump file is kept; zero indicates that no dumps will be made.
X
X   o Options [Aclu]:
X
X     Used to set a variety of options; see Section 10 for details.
X
X
X
X                                       16
X
X
X
X
X   o Random Seed [*]:
X
X     The seed value for the random number generator used by GAucsd.  Its
X     control allows exact replication of experiments; the default is derived
X     from the system clock.
X
X
At this point inset writes all settings out to the in file and prompts for
any application-specific arguments (cf. Section 6).  Hitting return will
obtain the default read previously from the in file, or exit the loop when
no default exists.
X
If GAucsd was compiled with the -DNOGAGX flag on your system, inset then
prints the command that will start the experiment and exit.  On some Unix
systems, however, it will prompt with "queue []:".  Hitting return in reply
will start the program via ga in background mode; any other response will
queue it in the named file for collective --- possibly distributed ---
execution of a set of experiments via gx (see Section 9).
X
X
X
_9_ _ _R_u_n_n_i_n_g_ _E_x_p_e_r_i_m_e_n_t_s
X
X
9.1  Direct Execution
X
X
A GAucsd program compiled from, say, evaluation file "f1.c" may be run
directly on an experiment named "foo" by typing "f1 foo".  On systems
supporting Unix-style signal handling, you can terminate the experiment
prematurely by sending it INT or TERM signals, which can be generated
by pressing key combinations such as CTRL-C. The first such signal causes
the experiment to conclude after the current run while the second forces a
cpt dump and exit after the current generation.  The third signal causes
immediate termination; in this case all progress since the last cpt dump
will be lost.
X
X
X
9.2  The Report Utility
X
X
If the c or C option is active, the experiment will append a line of data to
the out file every "Report Interval" trials.  To summarize the mean and
variance of these measurements over all runs, use the report utility:
typing "report foo" for instance will summarize data file foo.out.
X
The summary contains a copy of the in file, followed by the means and
variances of measurements such as online performance, offline performance,
the average performance of the current population, and the current best
value.  Online performance is the mean of all evaluations; offline
performance is the mean of all current best evaluations --- see [5].
X
If option c is active, three measures of convergence are also printed:
"Conv" is the number of positions which have converged at least to the
X
X
X
X                                       17
X
X
X
X
chosen threshold, "Lost" is the number of those which have converged 100%
(i.e. the entire population has the same value), and "Bias" indicates the
average percentage of the most prominent value in each position.  For
instance, a bias of 0.75 means that on average each position has converged
to either 75% zeroes or 75% ones.
X
X
X
9.3  Remote Execution via ga
X
X
On Unix systems, the command ga f1 foo & will run the same experiment as f1
foo, but at low priority and in the background.  ga also calls the report
program if appropriate, and can be used to execute GAucsd experiments
remotely, provided you have the necessary permissions in your .rhosts file
on the remote machine:  the command
X
X
X         ga f1 foo neuromancer smith /usr/ga &
X
X
for instance will recompile f1 on host neuromancer in the directory /usr/ga.
It will then copy foo.in (also foo.ini, foo.out and foo.sma if applicable)
into the remote directory, run the program there (using login name smith),
then copy any resulting data files back into your local directory and
produce a report if appropriate.
X
For binary compatible hosts the directory may be omitted, causing the
executable program to be run directly in /tmp on the remote host.  This
eliminates the compilation time and does not require GAucsd to be installed
on the remote host.  In this mode the login name defaults to $USER if
omitted.  If the remote machine has direct access to the local directory
through a shared file system, specify the remote host's path to it as
directory argument:  ga can exploit this special case to avoid the overhead
of copying files between the hosts.
X
X
X
9.4  Distributed Execution via gx
X
X
On Unix systems, you can execute entire sets of experiments sequentially or
in parallel on a network of machines.  This is done by accumulating
experiments in one or several queue files (see Section 8) whose names are
then given as arguments to the gx script.  When all experiments have been
completed, gx will notify you via write or --- if that fails --- mail.
X
gx distributes experiments to remote hosts specified in the GAhosts in the
local directory, your home directory or $GAucsd/usr.  Each entry in the
GAhosts file consists of a load factor (how many programs will be sent to
that host) followed by the remote execution arguments to ga as described
above --- see the sample GAhosts file in $GAucsd/usr for details.  Any
remaining experiments (after the GAhosts file has been exhausted) are
executed locally.
X
X
X
X                                       18
X
X
X
X
_1_0_ _ _O_p_t_i_o_n_s
X
X
GAucsd 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 in inset 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.
X
X
a --- evaluate all structures in each generation.  This may be useful when
X     evaluating a noisy function, since it allows the GA to sample a given
X     structure several times.  If this option is not selected then
X     structures which are identical to parents are not evaluated.
X
A --- causes Ctoi() to add a random fractional part to its conversion
X     results in order to avoid aliasing problems that might otherwise occur
X     when searching continuous spaces, due to the quantized nature of the
X     genetic encoding.  Since this option makes Ctoi() stochastic, A
X     automatically implies a.
X
b --- at the end of the experiment, write the average best value (over all
X     runs) to the standard output.
X
c --- collect statistics concerning the convergence of the algorithm.  These
X     statistics are written to the out file every "Report Interval"
X     trials.  The intervals are approximate, since statistics are collected
X     only at the end of a generation.  Option c implies C but is
X     computationally more expensive.
X
C --- collect statistics concerning the performance of the algorithm.  These
X     statistics are written to the out file every "Report Interval"
X     trials.  The intervals are approximate, since statistics are collected
X     only at the end of a generation.
X
d --- dump the current population to cpt file after each evaluation.  This
X     may considerably slow down the program, and is only useful when each
X     evaluation represents a large amount of computation.
X
e --- use the elitist selection strategy.  The elitist strategy stipulates
X     that the best performing structure always survives intact from one
X     generation to the next.  In the absence of this strategy, it is
X     possible that the best structure disappears due to crossover or
X     mutation.
X
X
X
X                                       19
X
X
X
X
i --- read structures from the ini file into the initial population.  If the
X     file contains fewer structures than the population needs, the remaining
X     structures will be initialized randomly, or super-uniformly if the u
X     option is used.
X
l --- log activity (such as starts and restarts) in the log file.  Some
X     error messages also end up in the log file.
X
L --- dump the last generation to the cpt file.  This allows the user to
X     extend the experiment at a later time, using the r option.
X
o --- at the end of the experiment, write the average online performance to
X     the standard output.  Online performance is the average of all
X     evaluations.
X
O --- at the end of the experiment, write the average offline performance to
X     the standard output.  Offline performance is the average of the "best
X     value so far" over the course of the run.
X
r --- restart a previously interrupted execution.  In this case, the cpt
X     file is read back in, and the GA takes up where it left off.
X
s --- trace the history of one schema.  This options requires that a sma
X     file exists in which the first line contains a string which has the
X     length of one structure and which contains only the characters '0',
X     '1', and '#' (and no blanks).  The system will append one line to the
X     schema file after each generation describing the performance
X     characteristics of the indicated schema (number of representatives,
X     relative fitness, etc.).
X
t --- trace each major function call; only useful for debugging purposes.
X     Tracing statements are written to the standard output.
X
u --- create a super-uniform initial population in which all schemata up to
X     a certain defining length (limited by the population size) are equally
X     represented.  In crossover-dominated GAs (i.e. those with low mutation
X     rate) this eliminates the risk of pathological initial populations in
X     which an important low-order schema just happens to be missing, and has
X     to be created by an unlikely mutation event.  The u option uses a
X     reduced-variance stochastic algorithm which produces a population with
X     no local, but large global correlations.  Crossover is very effective
X     in destroying such long-range correlations, but this option should not
X     be used in mutation-dominated GAs with very low crossover rates.
X
X
X
X                                       20
X
X
X
X
_1_1_ _ _F_i_l_e_s
X
X
For any the file names listed below, you may create a subdirectory in which
these files are collected.  The output of an experiment with name "foo",
for instance, will be in the file foo in the subdirectory out if that
exists, in the file foo.out in the current directory otherwise.  There is
also a file "errors" in which GAucsd error messages are collected.
X
X
cpt --- a checkpoint file containing a snapshot of important variables, and
X     the current population.  This file is produced if the d option is set,
X     the second termination signal is received, or both the number of saved
X     dumps and the dump interval are positive.  This file is necessary for
X     the restart option r to work, but can also be interesting in its own
X     right.
X
dpe --- this file, produced when the DPE algorithm is used, logs the
X     activity of the zoom operator.  For each zoom one line is appended,
X     containing generation and trial number, the index of the zoomed
X     parameter (starting at zero), the endpoints of its new search interval,
X     and its new precision.
X
in --- contains all input parameters.  This file is required.
X
ini --- contains structures which will be included in the initial
X     population.  This is useful if you have heuristics for selecting
X     plausible starting structures.  This file is read if the i option is
X     set.
X
log --- logs the dates of starts and restarts; produced if the l option is
X     set.
X
min --- contains the best structures found by the GA. Each paragraph of the
X     min file displays a binary structure, its evaluation, and the
X     generation and trial counters at the time of the first occurrence of
X     this structure, followed by a phenotypic description of the structure
X     as provided by the evaluation function.  The number of elements in min
X     is indicated by the response to inset's "Structures Saved" prompt.
X     If the number of runs is greater than one, the best structures are
X     stored in min.n during run number n.
X
out --- if the c or C option is set, a line of data describing the
X     performance of the GA is appended to this file every "Report
X     Interval" trials.  From left to right, the data columns are:
X     generations, trials, lost and converged alleles, bias, and online,
X     offline, best and average performance.
X
X
X
X                                       21
X
X
X
X
rep --- produced by ga (via the report program) from the out file, this file
X     summarizes the performance of the GA. It consists of a copy of the in
X     file followed by the mean and variance of the out file data averaged
X     over all runs.
X
sma --- logs a history of a single schema.  This file is required for the s
X     option; its first line must contain the schema in question and is read
X     at the start of the experiment.  A line of data describing the schema's
X     performance is then appended each generation (cf. option s).
X
X
X
_1_2_ _ _M_a_k_i_n_g_ _M_o_d_i_f_i_c_a_t_i_o_n_s
X
X
GAucsd was designed to encourage experiments with genetic algorithms.  It is
relatively easy for the user to create variations of GAucsd.  Suppose for
example that you wish to test a new crossover operator.  Simply copy the
file $GAUCSD/src/cross.c into your own directory and modify it as desired.
X
Now copy the GAucsd Makefile from the appropriate subdirectory of
$GAUCSD/bin into your directory and add "cross.o" (or "CROSS.OBJ" under
DOS) to the LOBJS macro at its top.  Now when you run inset, or compile your
experiment manually, the loader will include your crossover function instead
of the one provided in the GAucsd library.  Recompilation of the library is
thus not necessary.
X
In order to facilitate such experimentation, most of the important variables
in GAucsd are global.  All global identifiers in $GAUCSD/src/global.h begin
with a capital letter to minimize conflict with user-defined identifiers.
X
X
X
Acknowledgments
X
X
John Grefenstette wishes to thank the early users of Genesis for their
suggestions and comments, especially Ray Ford, Jeremy Norton and Mike
Fitzpatrick.  Nicol Schraudolph is indebted to John Grefenstette for
providing with the Genesis package such a useful basis for modifications,
and a User's Guide that forms the backbone of this manual.  Special thanks
go to all the users of GAucsd, who with countless bug reports and
suggestions have been vital in shaping this package.  Further suggestions
and comments are welcome.
X
X
X
X                                       22
X
X
X
X
References
X
X
X [1] James E. Baker.  Reducing bias and inefficiency in the selection
X     algorithm.  In John J. Grefenstette, editor, Proc. 2nd Int. Conf.
X     Genetic Algorithms and their Applications, pages 14--21, Hillsdale, NJ,
X     1987. Lawrence Erlbaum Associates.
X
X [2] A. D. Bethke.  Genetic Algorithms as Function Optimizers.  PhD thesis,
X     Dept. of Computer and Comm. Sciences, Univ. of Michigan, Ann Arbor, MI,
X     1981.
X
X [3] A. Brindle.  Genetic Algorithms for Function Optimization.  PhD thesis,
X     Computer Science Dept., Univ. of Alberta, 1981.
X
X [4] Kenneth A. De Jong.  An Analysis of the Behavior of a Class of Genetic
X     Adaptive Systems.  PhD thesis, Dept. of Computer and Comm. Sciences,
X     Univ. of Michigan, Ann Arbor, MI, 1975.  Univ. Microfilms No. 76-9381.
X
X [5] Kenneth A. De Jong.  Adaptive system design:  a genetic approach.  IEEE
X     Trans. Systems, Man, and Cybernetics, SMC-10(9):566--574, 1980.
X
X [6] Stephanie Forrest.  Documentation for prisoner's dilemma and norms
X     programs that use the genetic algorithm.  Technical report, Univ. of
X     Michigan, Ann Arbor, MI, 1985.
X
X [7] D. R. Frantz.  Non-linearities in Genetic Adaptive Search.  PhD thesis,
X     Dept. of Computer and Comm. Sciences, Univ. of Michigan, Ann Arbor, MI,
X     1972.
X
X [8] David E. Goldberg.  Genetic Algorithms in Search, Optimization & Machine
X     Learning.  Addison-Wesley, Reading, MA, 1989.
X
X [9] John H. Holland.  Adaptation in Natural and Artificial Systems.  The
X     Univ. of Michigan Press, Ann Arbor, MI, 1975.
X
[10] R. B. Hollstien.  Artificial Genetic Adaptation in Computer Control
X     Systems.  PhD thesis, Dept. of Computer and Comm. Sciences, Univ. of
X     Michigan, Ann Arbor, MI, 1971.
X
[11] Nicol N. Schraudolph and Richard K. Belew.  Dynamic parameter encoding
X     for genetic algorithms.  Machine Learning, 9:9--21, 1992.
X
[12] S. F. Smith.  Flexible learning of problem solving heuristics through
X     adaptive search.  In Proc. 8th Int. Joint Conf. Artif. Intelligence
X     (IJCAI), August 1983.
X
X
X
X                                       23
SHAR_EOF
chmod 0444 GAucsd.doc ||
echo 'restore of GAucsd.doc failed'
Wc_c="`wc -c < 'GAucsd.doc'`"
test 52175 -eq "$Wc_c" ||
	echo 'GAucsd.doc: original size 52175, current size' "$Wc_c"
fi
# ============= etc/ga ==============
if test ! -d 'etc'; then
    echo 'x - creating directory etc'
    mkdir 'etc'
fi
if test -f 'etc/ga' -a X"$1" != X"-c"; then
	echo 'x - skipping etc/ga (File already exists)'
else
echo 'x - extracting etc/ga (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'etc/ga' &&
#!/bin/sh
X
###############################################################
#                                                             #
#   Copyright (c) 1989 Nicol N. Schraudolph                   #
#   Computer Science & Engineering, C-014                     #
#   University of California, San Diego                       #
#   La Jolla, CA 92093-0114                                   #
#                                                             #
#   Permission is hereby granted to copy all or any part of   #
#   this program for free distribution.   The author's name   #
#   and this copyright notice must be included in any copy.   #
#                                                             #
###############################################################
X
#
#  file:    ga
#
#  author:  Nicol N. Schraudolph
#
#  created: August 1989
#
#  purpose: Bourne shell script for GAucsd simulation startup
#
X
trap "" 21	# shell bug fix: ignore background tty reads
nice=/bin/nice	# or whatever path your remote nice has
X
# set up file names
if test -d in
then in=in/${2-in}
else in=${2+$2.}in
fi
if test -d out
then out=out/${2-out}
else out=${2+$2.}out
fi
if test -d ini
then init=ini/${2-ini}
else init=${2+$2.}ini
fi
if test -d sma
then sma=sma/${2-sma}
else sma=${2+$2.}sma
fi
if test -d rep
then rep=rep/${2-rep}
else rep=${2+$2.}rep
fi
if test -d cpt
then cpt=cpt
else cpt=\.
fi
if test -d min
then min=min
else min=\.
fi
if grep -s '^ *Options = [a-zA-Z]*l' $in
then
X	if test -d log
X	then log=log/${2-log}
X	else log=${2+$2.}log
X	fi
else
X	log=/dev/null
fi
X
touch $out
if test $3z = z   # no host name: execute locally
then
X	nice -10 $1 $2
else
X	if test $4z = z
X	then me=$USER
X	else me=$4
X	fi
X	if test $5z = z   # binary compatible: run directly in /tmp
X	then
X		rsh -l $me $3 "mkdir /tmp/$$" 2> e$$ && \
X		rcp $1 $me@$3:/tmp/$$ 2>> e$$ && \
X		rcp $in $me@$3:/tmp/$$/$2.in 2>> e$$ && \
X		rcp $out $me@$3:/tmp/$$/$2.out 2>> e$$ && \
X		(rcp $init $me@$3:/tmp/$$/$2.ini 2> /dev/null || true) && \
X		(rcp $sma $me@$3:/tmp/$$/$2.sma 2> /dev/null || true) && \
X		echo running on $3: >> $log && \
X		(rsh -l $me $3 "cd /tmp/$$ && ($nice -15 $1 $2 l; cat $2.log \
X			|| echo Error: couldn\'t start $1 && date \
X			&& echo ''; rm -f $1 $2.in $2.ini $2.log)" >> $log 2>> e$$
X		rcp -p $me@$3:/tmp/$$/$2.out $out 2> /dev/null
X		rcp -p $me@$3:/tmp/$$/$2.dpe $dpe 2> /dev/null
X		rcp -p $me@$3:/tmp/$$/$2.min\* $min 2> /dev/null
X		rcp -p $me@$3:/tmp/$$/$2.cpt\* $cpt 2> /dev/null
X		rcp -p $me@$3:/tmp/$$/$2.sma $sma 2> /dev/null
X		rsh -l $me $3 "rm -rf /tmp/$$" 2>> e$$)
X	else
X		rsh -l $me $3 "touch $5/t$$" 2> e$$ && \
X		if test -f t$$
X		then            # shared file space: don't copy files
X			rm -f t$$
X			rsh -l $me $3 "cd $5; $nice -15 $1 $2"
X		else
X			eva=`echo $1 | sed -e 's/^ga\.//'`
X			rcp -p $eva.c $me@$3:$5/$eva.c 2> e$$ && \
X			rcp $in $me@$3:$5/$2.in 2>> e$$ && \
X			rcp $out $me@$3:$5/$2.out 2>> e$$ && \
X			(rcp $init $me@$3:$5/$2.ini 2> /dev/null || true) && \
X			(rcp $sma $me@$3:$5/$2.sma 2> /dev/null || true) && \
X			echo running on $3: >> $log && \
X			(rsh -l $me $3 "cd $5 && rm -f t$$ && \
X				($nice -5 make -f" \`which Makefile\` "GAeval=$eva && \
X				($nice -15 $1 $2 l; cat $2.log && rm $2.in $2.log || \
X				echo Error: couldn\'t start $1 && date && echo ''; \
X				rm -f $2.ini) || echo Error: couldn\'t make $1 && date \
X				&& echo '')" >> $log 2>> e$$
X			rcp -p $me@$3:$5/$2.out $out 2> /dev/null
X			rcp -p $me@$3:$5/$2.dpe $dpe 2> /dev/null
X			rcp -p $me@$3:$5/$2.min\* $min 2> /dev/null
X			rcp -p $me@$3:$5/$2.cpt\* $cpt 2> /dev/null
X			rcp -p $me@$3:$5/$2.sma $sma 2> /dev/null)
X		fi
X	fi
X	if test -s e$$   # collect errors, if any
X	then
X		echo running on $3: > f$$
X		cat e$$ >> f$$
X		date >> f$$
X		echo "" >> f$$
X		cat f$$ >> errors
X	fi
X	rm -f e$$ f$$
fi
if test -s $out   # prepare report
then
X	echo This is $rep for $1 > $rep
X	date >> $rep
X	report $2 >> $rep
fi
X
SHAR_EOF
chmod 0555 etc/ga ||
echo 'restore of etc/ga failed'
Wc_c="`wc -c < 'etc/ga'`"
test 3905 -eq "$Wc_c" ||
	echo 'etc/ga: original size 3905, current size' "$Wc_c"
fi
# ============= etc/gx ==============
if test -f 'etc/gx' -a X"$1" != X"-c"; then
	echo 'x - skipping etc/gx (File already exists)'
else
echo 'x - extracting etc/gx (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'etc/gx' &&
#!/bin/sh
X
###############################################################
#                                                             #
#   Copyright (c) 1989 Nicol N. Schraudolph                   #
#   Computer Science & Engineering, C-014                     #
#   University of California, San Diego                       #
#   La Jolla, CA 92093-0114                                   #
#                                                             #
#   Permission is hereby granted to copy all or any part of   #
#   this program for free distribution.   The author's name   #
#   and this copyright notice must be included in any copy.   #
#                                                             #
###############################################################
X
#
#  file:    gx
#
#  author:  Nicol N. Schraudolph
#
#  created: August 1989
#
#  purpose: Bourne shell script for running simulation queues
#
X
qtmp=/tmp/gx$$
export qtmp
if test -f GAhosts
then f="GAhosts $*"
elif test -f $HOME/GAhosts
then f="$HOME/GAhosts $*"
elif test -f $GAUCSD/usr/GAhosts
then f="$GAUCSD/usr/GAhosts $*"
else f="$*"
fi
echo "# The following GAucsd simulations initiated by you" > $qtmp
echo "# on" `date` "have terminated:" >> $qtmp
echo "" >> $qtmp
cat $f | awk -f $GAUCSD/etc/dispatch >> $qtmp
echo "" >> $qtmp
echo "wait  # end of simulations" >> $qtmp
(nice -5 sh < $qtmp;
X write $USER < $qtmp || mail -s "your GAucsd simulations" $USER < $qtmp;
X rm $qtmp) &
X
SHAR_EOF
chmod 0555 etc/gx ||
echo 'restore of etc/gx failed'
Wc_c="`wc -c < 'etc/gx'`"
test 1469 -eq "$Wc_c" ||
	echo 'etc/gx: original size 1469, current size' "$Wc_c"
fi
# ============= etc/dispatch ==============
if test -f 'etc/dispatch' -a X"$1" != X"-c"; then
	echo 'x - skipping etc/dispatch (File already exists)'
else
echo 'x - extracting etc/dispatch (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'etc/dispatch' &&
X
###############################################################
#                                                             #
#   Copyright (c) 1989 Nicol N. Schraudolph                   #
#   Computer Science & Engineering, C-014                     #
#   University of California, San Diego                       #
#   La Jolla, CA 92093-0114                                   #
#                                                             #
#   Permission is hereby granted to copy all or any part of   #
#   this program for free distribution.   The author's name   #
#   and this copyright notice must be included in any copy.   #
#                                                             #
###############################################################
X
#
#  file:    dispatch
#
#  author:  Nicol N. Schraudolph
#
#  created: August 1989
#
#  purpose: awk script for dispatching GENESIS simulation queues
#
X
BEGIN \
{
X	i = 0;
X	j = 0;
}
X
# skip comment lines
/^[	 ]*#/ \
{
X	next;
}
X
# read lines from GAhosts
/^[	 ]*[1-9]/ \
{
X	cap[i] = $1;
X	host[i] = $2;
X	login[i] = $3;
X	dir[i] = $4;
X	i++;
}
X 
# read execution queue
/^[	 ]*ga[ 	]+/ \
{
X	for (k = 0; k < i; k++)
X	{
X		if (j >= i) j = 0;
X		if (cap[j])
X		{
X			printf "\tga ";
X			print $2, $3, host[j], login[j], dir[j], $4;
X			cap[j++]--;
X			next;
X		}
X		else j++;
X	}
X	print $0;
}
X
SHAR_EOF
chmod 0444 etc/dispatch ||
echo 'restore of etc/dispatch failed'
Wc_c="`wc -c < 'etc/dispatch'`"
test 1345 -eq "$Wc_c" ||
	echo 'etc/dispatch: original size 1345, current size' "$Wc_c"
fi
# ============= etc/wrapper ==============
if test -f 'etc/wrapper' -a X"$1" != X"-c"; then
	echo 'x - skipping etc/wrapper (File already exists)'
else
echo 'x - extracting etc/wrapper (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'etc/wrapper' &&
X
###############################################################
#                                                             #
#   Copyright (c) 1989 Nicol N. Schraudolph                   #
#   Computer Science & Engineering, C-014                     #
#   University of California, San Diego                       #
#   La Jolla, CA 92093-0114                                   #
#                                                             #
#   Permission is hereby granted to copy all or any part of   #
#   this program for free distribution.   The author's name   #
#   and this copyright notice must be included in any copy.   #
#                                                             #
###############################################################
X
#
#  file:    wrapper
#
#  author:  Nicol N. Schraudolph
#
#  created: August 1989
#
#  purpose: awk script for processing GENESIS eval functions
#
X
BEGIN \
{
printf "\n/* evaluation file for GENESIS 1.4ucsd GA simulator */\n";
printf "/* produced by \"wrapper\" awk(1) script from \"%s\" */\n", FILENAME;
printf "\nextern int   GArgc;   /* number of application-specific arguments */";
printf "\nextern char *GArgv[]; /* vector of application-specific arguments */";
printf "\nextern double Ctoi(); /* double returned to facilitate 'A' option */";
printf "\n\n";
}
X
# reproduce input file on output:
#
{print $0}
X
# is an _eval() function already present?
#
/^[ \t]*_eval[ \t]*\(/ {found = 1}
/^[ \t]*double[ \t][ \t]*_eval[ \t]*\(/ {found = 1}
X
# are gene descriptor variables already supplied?
#
/GAgenes/ {DPE = 1}
X
# now look for GAeval entries:
#
/^[ \t]*\/\*[ \t][ \t]*GAeval[ \t]/ \
{
X	if (len > 0 || $3 == "_eval" || NF < 5)
X	{
X		print "/* ^^illegal GAeval entry: ignored */";
X		continue;
X	}
X	found = 1;      # we have a promising GAeval line to look at
X	num_real = 0;
X	for (i = 4; $i != "*/"; i++)    # for each descriptor field:
X	{
X		# read first number: field width in bits
X		#
X		for (j = 1; (c = substr($i, j, 1)) ~ /[0-9]/; j++)
X			width[i-3] = 10*width[i-3] + c;
X		if (!width[i-3])
X		{
X			printf "/* ^^can't find width of field \"%s\" */\n", $i;
X			exit 3;
X		}
X
X		# look for field type description
X		#
X		if ($i ~ /[cC]/) type[i-3] = "char";
X		else if ($i ~ /[sS]/) type[i-3] = "short";
X		else if ($i ~ /[iI]/) type[i-3] = "int";
X		else if ($i ~ /[lL]/) type[i-3] = "long";
X		else if ($i ~ /[fF]/) type[i-3] = "float";
X		else if ($i ~ /[dD]/) type[i-3] = "double";
X		else
X		{
X			printf "/* ^^can't find type of field \"%s\" */\n", $i;
X			exit 2;
X		}
X		if ($i ~ /[uU]/ && $i !~ /[fdFD]/)
X			type[i-3] = "unsigned " type[i-3];
X
X		# read up to first colon: is there a range field?
X		#
X		for (j = 1; j < length($i); j++)
X			if (substr($i, j, 1) == ":") break;
X
X		if (j < length($i))     # yes: read a float into hi[]
X		{
X			hi[i-3] = dot = 0;
X			if ((c = substr($i, ++j, 1)) == "-")
X			{
X				div = -1.0;     # float is negative
X				j++;
X			}
X			else div = 1.0;
X			if (c == "+") j++;  # ignore leading '+'
X
X			for (; (c = substr($i, j, 1)) ~ /[\.0-9]/; j++)
X			{
X				if (c == ".")   # found the decimal point
X				{
X					if (dot)
X					{
X						printf "/* ^^too many '.' in field \"%s\" */\n", $i;
X						exit 4;
X					}
X					else dot = 1;
X				}
X				else            # read one digit
X				{
X					hi[i-3] = 10*hi[i-3] + c;
X					if (dot) div *= 10.0;
X				}
X			}
X			hi[i-3] /= div;     # adjust for decimal point
X
X			# same for second range field, if there is any:
X			#
X			if (substr($i, j, 1) == ":")
X			{
X				lo[i-3] = hi[i-3];
X				hi[i-3] = dot = 0;
X				if ((c = substr($i, ++j, 1)) == "-")
X				{
X					div = -1.0;     # float is negative
X					j++;
X				}
X				else div = 1.0;
X				if (c == "+") j++;  # ignore leading '+'
X
X				for (; (c = substr($i, j, 1)) ~ /[\.0-9]/; j++)
X				{
X					if (c == ".")   # found the decimal point
X					{
X						if (dot)
X						{
X							printf "/* ^^too many '.' in field \"%s\" */\n", $i;
X							exit 4;
X						}
X						else dot = 1;
X					}
X					else            # read one digit
X					{
X						hi[i-3] = 10*hi[i-3] + c;
X						if (dot) div *= 10.0;
X					}
X				}
X				hi[i-3] /= div;     # adjust for decimal point
X			}
X			else if ($i !~ /[uU]/) lo[i-3] = -hi[i-3];
X			#
X			# no second range field: make range symmetric if signed
X		}
X
X		# now read replicator, if any:
X		#
X		k = 1;
X		for (j = length($i); (c = substr($i, j, 1)) ~ /[0-9]/; j--)
X		{
X			num[i-3] += k*c;
X			k *= 10;
X		}
X		if (num[i-3]) any_num = 1;
X
X		# look for 'b' and 'g' switches:
X		#
X		dpe[i-3] = 0;
X		if ($i ~ /[bB]/) gray[i-3] = 0;
X		else
X		{
X			gray[i-3] = 1;
X			if (width[i-3] > maxw) maxw = width[i-3];
X			if ($i !~ /[gG]/ && width[i-3] >= 2) dpe[i-3] = 1;
X		}
X
X		# convert range boundaries into (base,scale) notation:
X		#
X		excess = 1;
X		for (j = 1; j < width[i-3]; j++) excess *= 2;
X		if (hi[i-3] == 0 && lo[i-3] == 0)
X		{
X			hi[i-3] = 1;
X			if ($i !~ /[uU]/) lo[i-3] = -excess;
X		}
X		else hi[i-3] = (hi[i-3] - lo[i-3])/(2*excess);
X
X		# construct gene descriptor variables:
X		#
X		for (j = 0; j < num[i-3] || j == 0; j++)
X		{
X			len += width[i-3];
X			start[num_real] = len;
X			if (!dpe[i-3]) start[num_real] = -start[num_real];
X			scale[num_real] = hi[i-3];
X			base[num_real++] = lo[i-3];
X		}
X	}
X
X	# now let's do some outputting:
X	#
X	if (!DPE)   # print gene descriptor variables, nicely formatted
X	{
X		printf "\nint GAgenes = %d;  /* the number of genes */\n", num_real;
X		print "\n/* locates the end of each gene; negate to inhibit DPE */";
X		printf "int GAposn[%d] = {", num_real;
X		for (i = 1; i < num_real; i++)
X		{
X			printf "%3d, ", start[i-1];
X			if (!(i % 10)) printf "\n                  ";
X		}
X		printf "%3d};\n", start[num_real-1];
X		print "\n/* multiplication factors (see _eval() below) */";
X		printf "double GAfact[%d] = {", num_real;
X		for (i = 1; i < num_real; i++)
X		{
X			printf "%.5e, ", scale[i-1];
X			if (!(i % 4)) printf "\n                     ";
X		}
X		printf "%.5e};\n", scale[num_real-1];
X		print "\n/* displacement terms (see _eval() below) */";
X		printf "double GAbase[%d] = {", num_real;
X		for (i = 1; i < num_real; i++)
X		{
X			printf "%.5e, ", base[i-1];
X			if (!(i % 4)) printf "\n                     ";
X		}
X		printf "%.5e};\n", base[num_real-1];
X		DPE = 1;
X	}
X	else print "\n/* using user-supplied GA globals in good faith */";
X
X	# print the appropriate _eval() function:
X	#
X	print "\n/* user's evaluation function needs unpacking and decoding */";
X	print "double _eval(genome, length)";
X	print "\tchar *genome;";
X	print "\tint length;\n{";
X	for (i = 1; type[i] != ""; i++)
X	{
X		printf "\tstatic %s p%d", type[i], i;   # variables to hold the genes
X		if (num[i] && width[i]) printf "[%d]", num[i];
X		print ";";
X	}
X	if (maxw) printf "\tchar tmp[%d];\n", maxw; # a char buffer for Degray()
X	if (any_num) print "\tregister int i;";     # loop counter for replication
X	print "\textern   char *Buff;";             # global buffer for Unpack()
X	print "\tregister char *buff;";             # a pointer to the above
X	print "\tregister double *f = GAfact;";
X	print "\tregister double *b = GAbase;";     # pointers for fast scaling
X
X	# report last phenotype if length is negative:
X	#
X	print "\n\tif (length < 0)\t/* report previous phenotype */\n\t{";
X	printf "\t\tsprintf(genome, \"\\n";
X	for (i = 1; type[i] != ""; i++)     # construct the formatting string
X		for (j = 0; j == 0 || j < num[i]; j++)
X		{
X			printf "%%%d", width[i];
X			if (type[i] ~ /long/) printf "l";
X			if (type[i] ~ /float/ || type[i] ~ /double/) printf "g ";
X			else if (type[i] ~ /unsigned/) printf "u ";
X			else printf "d ";
X		}
X	printf "\"";
X	j = i;
X	for (i = 1; type[i] != ""; i++)     # print gene vars in nice format
X	{
X		if (num[i])
X			for (j = 0; j < num[i]; j++)
X			{
X				if (j%6 == 0) printf ",\n\t\t\t";
X				else printf ", ";
X				printf "p%d[%d]", i, j;
X			}
X		else
X		{
X			if (j >= 6)
X			{
X				printf ",\n\t\t\t";
X				j = -4;
X			}
X			else printf ", ";
X			printf "p%d", i;
X			j++;
X		}
X	}
X	print ");\n\t\treturn((double) 0.0);\n\t}";
X
X	# back to the decoding business:
X	#
X	printf "\t/*  GAlength %d  */\n", len;
X	printf "\tif (length < %d)\n", len;
X	printf "\t\tError(%clength error in eval%c);\n", 34, 34;
X	print "\n\tUnpack(genome, buff = Buff);";
X
X	for (i = 1; type[i] != ""; i++)     # for each descriptor:
X	{
X		if (num[i])     # start a loop for replication
X		{
X			printf "\tfor (i = 0; i < %d; ", num[i];
X			printf "i++, buff += %d)\n\t", width[i];
X			if (gray[i]) printf "{\n\t";
X		}
X		if (gray[i])    # call Degray() if necessary
X		{
X			printf "\tDegray";
X			printf "(buff, tmp, %d);\n", width[i];
X			if (num[i]) printf "\t";
X		}
X		printf "\tp%d", i;      # now decode the gene
X		if (num[i]) printf "[i]";
X		printf " = (%s) (Ctoi(", type[i];
X		if (gray[i]) printf "tmp";
X		else printf "buff";
X		printf ", %d) * *f++ + *b++);\n", width[i];
X		if (gray[i] && num[i]) print "\t}"
X		if (!num[i] && type[i+1] != "")
X			printf "\tbuff += %d;\n", width[i];
X	}
X
X	# invoke user's eval function with decoded genes:
X	#
X	printf "\treturn((double) %s(", $3;
X	for (i = 1; type[i] != ""; i++)
X	{
X		if (!comma) comma = 1;
X		else printf ", ";
X		printf "p%d", i;
X	}
X	print "));\n}";
}
X
END \
{
X	if (!found)     # must be old-fashioned eval() function:
X	{
X		print "\n/* user's eval() function needs unpacking only */";
X		print "double _eval(genome, length)\n\tchar *genome;";
X		print "\tint length;\n{\n\textern char *Buff;\n";
X		print "\tif (length > 0)\n\t{"; 
X		print "\t\tUnpack(genome, Buff, length);";
X		print "\t\tgenome = Buff;\n\t}"; 
X		print "\treturn(eval(genome, length));\n}";
X	}
X	if (!DPE)       # no data for parameter descriptor variables:
X	{
X		print "\n/* inserting dummy GA globals - DPE won't work */";
X		print "int GAgenes = 0, *GAposn;";
X		print "double  *GAfact, *GAbase;";
X	}
}
X
SHAR_EOF
chmod 0444 etc/wrapper ||
echo 'restore of etc/wrapper failed'
Wc_c="`wc -c < 'etc/wrapper'`"
test 9658 -eq "$Wc_c" ||
	echo 'etc/wrapper: original size 9658, current size' "$Wc_c"
fi
# ============= usr/GAhosts ==============
if test ! -d 'usr'; then
    echo 'x - creating directory usr'
    mkdir 'usr'
fi
if test -f 'usr/GAhosts' -a X"$1" != X"-c"; then
	echo 'x - skipping usr/GAhosts (File already exists)'
else
echo 'x - extracting usr/GAhosts (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'usr/GAhosts' &&
X
# GAhosts - the host table used by GAucsd to distribute simulations.
# The base table in $GAUCSD/usr can be overridden by a user-specific
# table "~/GAhosts" which in turn yields to "GAhosts" in the current
# directory.  Each entry should have the format:
#
# <load factor> <host name> [<login> [<directory>]]
# eg. "1 neuromancer smith /data/GAucsd"
#
# For binary compatible hosts the directory may coincide with the
# current directory through disk sharing (in which case redundant
# copies will be avoided) or even be omitted (in which  case  the
# executable  will be run in /tmp).  If the login is also omitted
# it will default to $USER.  Add entries below:
X
SHAR_EOF
chmod 0444 usr/GAhosts ||
echo 'restore of usr/GAhosts failed'
Wc_c="`wc -c < 'usr/GAhosts'`"
test 667 -eq "$Wc_c" ||
	echo 'usr/GAhosts: original size 667, current size' "$Wc_c"
fi
# ============= usr/sample.in ==============
if test -f 'usr/sample.in' -a X"$1" != X"-c"; then
	echo 'x - skipping usr/sample.in (File already exists)'
else
echo 'x - extracting usr/sample.in (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'usr/sample.in' &&
X
X      Experiments = 5
X     Total Trials = 2000
X  Population Size = 50
X Structure Length = 30
X   Crossover Rate = 0.500000
X    Mutation Rate = 0.005000
X   Generation Gap = 1.000000
X   Scaling Window = -1
X  Report Interval = 200
X Structures Saved = 10
Max Gens w/o Eval = 2
X    Dump Interval = 10
X      Dumps Saved = 1
X          Options = Aclu
X      Random Seed = 3436473682
X     Maximum Bias = 0.990000
X  Max Convergence = 30
X   Conv Threshold = 0.750000
DPE Time Constant = 20
X    Sigma Scaling = 2.000000
--
This is GArgv[0]...
...and this GArgv[1].
You can have up to 50 of these.
SHAR_EOF
chmod 0444 usr/sample.in ||
echo 'restore of usr/sample.in failed'
Wc_c="`wc -c < 'usr/sample.in'`"
test 584 -eq "$Wc_c" ||
	echo 'usr/sample.in: original size 584, current size' "$Wc_c"
fi
# ============= usr/f1_ga.c ==============
if test -f 'usr/f1_ga.c' -a X"$1" != X"-c"; then
	echo 'x - skipping usr/f1_ga.c (File already exists)'
else
echo 'x - extracting usr/f1_ga.c (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'usr/f1_ga.c' &&
X
/* evaluation file for GENESIS 1.4ucsd GA simulator */
/* produced by "wrapper" awk(1) script from "f1.c" */
X
extern int   GArgc;   /* number of application-specific arguments */
extern char *GArgv[]; /* vector of application-specific arguments */
extern double Ctoi(); /* double returned to facilitate 'A' option */
X
/************************************************  file f1.c  ****/
X
double f1(x)
register double *x;
{
X	register int i;
X	register double sum;
X
X	for (sum = 0.0, i = 0; i < 3; i++)
X	{
X		/*  accumulate sum of squares of x's  */
X		sum += x[i]*x[i];
X	}
X	return (sum);
}
X
/* GAeval f1 10:5.12d3 */
X
int GAgenes = 3; /* the number of genes */
X
/* locates the end of each gene; negate to inhibit DPE */
int GAposn[3] = {10, 20, 30};
X
/* multiplication factors (see _eval() below) */
double GAfact[3] = {0.010000, 0.010000, 0.010000};
X
/* displacement terms (see _eval() below) */
double GAbase[3] = {-5.120000, -5.120000, -5.120000};
X
/* user's evaluation function needs unpacking and decoding */
double _eval(genome, length)
X	char *genome;
X	int length;
{
X	static double p1[3];
X	char tmp[10];
X	register int i;
X	extern   char *Buff;
X	register char *buff;
X	register double *f = GAfact;
X	register double *b = GAbase;
X
X	if (length < 0)	/* report previous phenotype */
X	{
X		sprintf(genome, "\n%10g %10g %10g ",
X			p1[0], p1[1], p1[2]);
X		return;
X	}
X	/*  GAlength 30  */
X	if (length < 30)
X		Error("length error in eval");
X
X	Unpack(genome, buff = Buff);
X	for (i = 0; i < 3; i++, buff += 10)
X	{
X		Degray(buff, tmp, 10);
X		p1[i] = (double) (Ctoi(tmp, 10) * *f++ + *b++);
X	}
X	return((double) f1(p1));
}
X
/************************************************ end of file ****/
SHAR_EOF
chmod 0444 usr/f1_ga.c ||
echo 'restore of usr/f1_ga.c failed'
Wc_c="`wc -c < 'usr/f1_ga.c'`"
test 1674 -eq "$Wc_c" ||
	echo 'usr/f1_ga.c: original size 1674, current size' "$Wc_c"
fi
# ============= usr/f1.c ==============
if test -f 'usr/f1.c' -a X"$1" != X"-c"; then
	echo 'x - skipping usr/f1.c (File already exists)'
else
echo 'x - extracting usr/f1.c (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'usr/f1.c' &&
/************************************************  file f1.c  ****/
X
double f1(x)
register double *x;
{
X	register int i;
X	register double sum;
X
X	for (sum = 0.0, i = 0; i < 3; i++)
X	{
X		/*  accumulate sum of squares of x's  */
X		sum += x[i]*x[i];
X	}
X	return (sum);
}
X
/* GAeval f1 10:5.12d3 */
X
/************************************************ end of file ****/
SHAR_EOF
chmod 0444 usr/f1.c ||
echo 'restore of usr/f1.c failed'
Wc_c="`wc -c < 'usr/f1.c'`"
test 362 -eq "$Wc_c" ||
	echo 'usr/f1.c: original size 362, current size' "$Wc_c"
fi
# ============= usr/f2.c ==============
if test -f 'usr/f2.c' -a X"$1" != X"-c"; then
	echo 'x - skipping usr/f2.c (File already exists)'
else
echo 'x - extracting usr/f2.c (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'usr/f2.c' &&
X
/************************************************  file f2.c  ****/
X
X
X
double f2(x)
register double *x;
{
X	double ans;
X
X	ans = (x[0]*x[0] - x[1]);
X	ans *= ans;
X	ans = 100.0*ans + (1.0 - x[0])*(1.0 - x[0]);
X	return (ans);
}
X
/* GAeval f2 12:2.048bd2 */
X
/** end of file **/
X
SHAR_EOF
chmod 0444 usr/f2.c ||
echo 'restore of usr/f2.c failed'
Wc_c="`wc -c < 'usr/f2.c'`"
test 275 -eq "$Wc_c" ||
	echo 'usr/f2.c: original size 275, current size' "$Wc_c"
fi
# ============= usr/f3.c ==============
if test -f 'usr/f3.c' -a X"$1" != X"-c"; then
	echo 'x - skipping usr/f3.c (File already exists)'
else
echo 'x - extracting usr/f3.c (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'usr/f3.c' &&
X
/************************************************  file f3.c  ****/
X
X
X
double f3(x)
register double *x;
{
X	register int k[5];
X	register int i;
X	double ans;
X
X	ans = 0;
X	for (i=0; i<5; i++)
X	{
X		k[i] = x[i];
X		if (k[i]>x[i]) k[i] -= 1;
X		ans += k[i];
X	}
X	return (ans + 30.0);
}
X
/* GAeval f3 10:5.12bd5 */
X
/** end of file **/
X
SHAR_EOF
chmod 0444 usr/f3.c ||
echo 'restore of usr/f3.c failed'
Wc_c="`wc -c < 'usr/f3.c'`"
test 327 -eq "$Wc_c" ||
	echo 'usr/f3.c: original size 327, current size' "$Wc_c"
fi
# ============= usr/f4.c ==============
if test -f 'usr/f4.c' -a X"$1" != X"-c"; then
	echo 'x - skipping usr/f4.c (File already exists)'
else
echo 'x - extracting usr/f4.c (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'usr/f4.c' &&
X
/************************************************  file f4.c  ****/
X
double f4(x)
register double *x;
{
X	extern double Rand();
X	register int i;
X	register int k;
X	double ans;
X	double prod;
X
X	ans = 0.0;
X	for (i = 0; i < 30; i++)
X	{
X		for (prod = 1.0, k = 0; k < 4; k++)
X			prod *= x[i];
X		ans += (i + 1)*prod;
X	}
X
X	/* now add Gaussian noise */
X	prod = -6.0;
X	for (i = 0; i < 12; i++) prod += Rand();
X
X	ans += prod;
X	return(ans);
}
X
/* GAeval f4 8:1.28bd30 */
X
/** end of file **/
X
SHAR_EOF
chmod 0444 usr/f4.c ||
echo 'restore of usr/f4.c failed'
Wc_c="`wc -c < 'usr/f4.c'`"
test 480 -eq "$Wc_c" ||
	echo 'usr/f4.c: original size 480, current size' "$Wc_c"
fi
# ============= usr/f5.c ==============
if test -f 'usr/f5.c' -a X"$1" != X"-c"; then
	echo 'x - skipping usr/f5.c (File already exists)'
else
echo 'x - extracting usr/f5.c (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'usr/f5.c' &&
X
/************************************************  file f5.c  ****/
X
X
static int a[2][25] = {
X	{ -32, -16, 0, 16, 32, -32, -16, 0, 16, 32, -32, -16, 0, 16, 32,
X	  -32, -16, 0, 16, 32, -32, -16, 0, 16, 32 },
X	{ -32, -32, -32, -32, -32, -16, -16, -16, -16, -16, 
X	   0, 0, 0, 0, 0, 16, 16, 16, 16, 16, 32, 32, 32, 32, 32 }
X	};
X
X
double f5(x)
register double *x;
{
X	register int i, j;
X	register int n;
X	double ans;
X	double fj; 
X	double prod;
X	double diff;
X
X	ans = 0.002;
X	for (j=0; j<25; j++)
X	{
X		fj = j+1;
X		for (i=0; i<2; i++)
X		{
X			diff = x[i] - a[i][j];
X			for ( prod=1, n=0; n<6; n++)
X				prod *= diff;
X			fj += prod;
X		}
X		ans += 1.0 / fj;
X	}
X	return (1.0 / ans);
}
X
/* GAeval f5 17:65.536bd2 */
X
/** end of file **/
X
SHAR_EOF
chmod 0444 usr/f5.c ||
echo 'restore of usr/f5.c failed'
Wc_c="`wc -c < 'usr/f5.c'`"
test 724 -eq "$Wc_c" ||
	echo 'usr/f5.c: original size 724, current size' "$Wc_c"
fi
# ============= src/Makefile ==============
if test ! -d 'src'; then
    echo 'x - creating directory src'
    mkdir 'src'
fi
if test -f 'src/Makefile' -a X"$1" != X"-c"; then
	echo 'x - skipping src/Makefile (File already exists)'
else
echo 'x - extracting src/Makefile (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'src/Makefile' &&
X
###############################################################
#                                                             #
#   Copyright (c) 1992 Nicol N. Schraudolph                   #
#   Computer Science & Engineering, C-014                     #
#   University of California, San Diego                       #
#   La Jolla, CA 92093-0114                                   #
#                                                             #
#   Permission is hereby granted to copy all or any part of   #
#   this program for free distribution.   The author's name   #
#   and this copyright notice must be included in any copy.   #
#                                                             #
###############################################################
X
# Local object files you wish to include:
#
LOBJS =
X
############################
# CUSTOMIZE SECTION BELOW  #
# FOR EACH TARGET PLATFORM #
############################
X
# MACH must uniquely identify target platform:
#
MACH = `mach`
X
# CFLAGS are the flags given to the C compiler
# (add -DNOGAGX if you're not using ga and gx):
#
CFLAGS = -O
X
# DQ should be set to a double quote that will
# survive the command shell, i.e. it should be
# escaped if it is a special shell character:
#
DQ = \"
X
# DS should be set to your directory separator:
#
DS = /
X
# file naming conventions:
#
OBJ = .o   # suffix for object files
LIB = .a   # suffix for libraries
EXE =      # suffix for executables
X
# file handling commands:
#
RM = rm -f # command to delete a file
MD = mkdir # command to create a new directory
CP = cp    # command to copy a file to a directory
X
# compilation commands:
#
CC = cc    # the C compiler
AR = ar r  # the archiver/librarian
X
X
##########################
# DO NOT EDIT BELOW HERE #
##########################
X
# GAeval should be set from command line
#
GAeval = GAeval
X
$(GAeval)$(EXE): $(GAeval)_ga$(OBJ)
X	$(CC) $(CFLAGS) -o $(GAeval)$(EXE) $(GAeval)_ga$(OBJ) $(LOBJS) $(GAUCSD)$(DS)bin$(DS)$(MACH)$(DS)ga$(LIB) -lm
X
$(GAeval)_ga.c: $(GAeval).c $(GAUCSD)$(DS)etc$(DS)wrapper
X	awk -f $(GAUCSD)$(DS)etc$(DS)wrapper $(GAeval).c > $(GAeval)_ga.c
X
X
OBJS = best$(OBJ) checkpt$(OBJ) converge$(OBJ) cross$(OBJ) decode$(OBJ) \
X	done$(OBJ) dpe$(OBJ) elitist$(OBJ) encode$(OBJ) error$(OBJ) \
X	evaluate$(OBJ) gap$(OBJ) generate$(OBJ) init$(OBJ) input$(OBJ) \
X	main$(OBJ) measure$(OBJ) mutate$(OBJ) random$(OBJ) restart$(OBJ) \
X	schema$(OBJ) select$(OBJ) setflag$(OBJ)
X
HDRS = Makefile define.h global.h format.h
X
DFLAGS = -DDS=$(DQ)$(DS)$(DQ) \
X	-DMF=$(DQ)$(GAUCSD)$(DS)bin$(DS)$(MACH)$(DS)Makefile$(DQ)
X
all : ga$(LIB) inset$(EXE) report$(EXE)
X
ga$(LIB) : $(OBJS)
X	-$(RM) ga$(LIB)
X	$(AR) ga$(LIB) $(OBJS)
X
$(OBJS) : $(HDRS)
X
main$(OBJ) : main.c
X	$(CC) $(CFLAGS) $(DFLAGS) -c main.c
X
inset$(EXE) : inset.c random$(OBJ) $(HDRS)
X	$(CC) $(CFLAGS) $(DFLAGS) -o inset$(EXE) inset.c random$(OBJ) -lm
X
report$(EXE) : report.c error$(OBJ) $(HDRS)
X	$(CC) $(CFLAGS) $(DFLAGS) -o report$(EXE) report.c error$(OBJ)
X
install : ga$(LIB) report$(EXE) inset$(EXE)
X	-$(MD) $(GAUCSD)$(DS)bin
X	-$(MD) $(GAUCSD)$(DS)bin$(DS)$(MACH)
X	$(CP) ga$(LIB) $(GAUCSD)$(DS)bin$(DS)$(MACH)
X	-ranlib $(GAUCSD)$(DS)bin$(DS)$(MACH)$(DS)ga$(LIB)
X	$(CP) inset$(EXE) $(GAUCSD)$(DS)bin$(DS)$(MACH)
X	$(CP) report$(EXE) $(GAUCSD)$(DS)bin$(DS)$(MACH)
X	$(CP) Makefile $(GAUCSD)$(DS)bin$(DS)$(MACH)
X
clean :
X	-$(RM) *$(OBJ)
X	-$(RM) ga$(LIB)
X	-$(RM) inset$(EXE)
X	-$(RM) report$(EXE)
X
.c$(OBJ) :
X	$(CC) $(CFLAGS) -c $<
X
SHAR_EOF
chmod 0644 src/Makefile ||
echo 'restore of src/Makefile failed'
Wc_c="`wc -c < 'src/Makefile'`"
test 3452 -eq "$Wc_c" ||
	echo 'src/Makefile: original size 3452, current size' "$Wc_c"
fi
# ============= src/define.h ==============
if test -f 'src/define.h' -a X"$1" != X"-c"; then
	echo 'x - skipping src/define.h (File already exists)'
else
echo 'x - extracting src/define.h (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'src/define.h' &&
/*************************************************************/
/*                                                           */
/*  Copyright (c) 1986                                       */
/*  John J. Grefenstette                                     */
/*  Navy Center for Applied Research in AI                   */
/*  Naval Research Laboratory                                */
/*                                                           */
/*  Permission is hereby granted to copy all or any part of  */
/*  this program for free distribution.   The author's name  */
/*  and this copyright notice must be included in any copy.  */
/*                                                           */
/*************************************************************/
X
/*
X *  file:	define.h
X *
X *  author:	John J. Grefenstette
X *
X *  created:	1981 
X *
X *  purpose:	global definitions for genesis
X */
X
/**************************************************************/
/*****  SYSTEM-DEPENDENT DEFINITIONS (edit if necessary)  *****/
/**************************************************************/
X
#include <limits.h>
/*
X * If your system doesn't have <limits.h>, you need to #define
X * the following machine constants here by hand:
X *
X *     CHAR_BIT - the number of bits in a byte
X *      INT_MAX - the largest signed integer
X *     LONG_MAX - the largest signed long int
X */
X
#include <signal.h>
/*
X * If your system doesn't have <signal.h>, you won't be able to
X * interrupt running experiments in a controlled manner and must
X * #define the symbol NOSIGNAL here.
X */
X
#include <sys/types.h>
/*
X * If your system doesn't have <sys/types.h>, comment out this
X * line and try again - things may just work without this file.
X * If they do not, follow the same instructions as given for a
X * missing <sys/stat.h> below.
X */
X
#include <sys/stat.h>
/*
X * If your system doesn't have <sys/stat.h>, you cannot use the
X * subdirectory feature and must #define the symbol NOSTAT here.
X * Also, "inset" won't recognize a local Makefile -- you'll have
X * to compile such experiments manually with "make GAeval=...".
X */
X
#ifdef UTILITY
#include <string.h>
/*
X * If your system doesn't have <string.h>, try using <strings.h>
X * instead.  If you don't have that either, you won't be able to
X * compile the inset utility.  To run an experiment named "foo",
X * you will have to compile it with
X *
X *         make -f $GAUCSD/bin/$MACH/Makefile GAeval=foo
X *
X * Then use $GAUCSD/usr/sample.in as template to create "foo.in".
X */
#endif
X
X
/*************************************/
/*****  end of system-dependency *****/
/*************************************/
X
/* fitness ratio 'r' closest to 1.0 that DPE can handle */
#define FIT_RATIO 0.99
X
/* This is what happens when a mutation occurs */
#define MUTATION(Gene,Mask) (Gene ^= Mask)
X
/* maximum number of application-specific arguments */
#define MAXGARG 50
X
X
/***********************************/
/*****  DO NOT EDIT BELOW HERE *****/
/***********************************/
X
/* define various constants and bitmasks */
#define BIT(X)  ((1 << (CHAR_BIT - 1)) >> (X))
#define PRE(X)  ((~0 << CHAR_BIT) >> (X))
#define POST(X) (~PRE(X))
X
/* each member of the population has this form */
typedef struct {
X	char *Gene;
X	double Perf;
X	int Needs_evaluation;
} STRUCTURE;
X
/* the best structures are saved in the following record */
typedef struct {
X	char *Gene;
X	char *Phene;
X	double Perf;
X	int Gen;
X	long Trials;
} BESTSTRUCT;
X
/* print a debugging message */
#define Trace(s)  if (Traceflag) \
X		{ printf(s); printf("\n"); fflush(stdout);}
X
X
/****************************************************************/
/* Rand() returns a pseudo-random double value between 0 and 1; */
/* Randint(L,H) produces an integer between L and H inclusive.  */
/****************************************************************/
X
#define RAND_DEG 31 	/* size of state array */
X
#define Randint(low,high) ((int)(low + (high-low+1) * Rand()))
X
/** end of file **/
X
SHAR_EOF
chmod 0644 src/define.h ||
echo 'restore of src/define.h failed'
Wc_c="`wc -c < 'src/define.h'`"
test 3977 -eq "$Wc_c" ||
	echo 'src/define.h: original size 3977, current size' "$Wc_c"
fi
# ============= src/format.h ==============
if test -f 'src/format.h' -a X"$1" != X"-c"; then
	echo 'x - skipping src/format.h (File already exists)'
else
echo 'x - extracting src/format.h (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'src/format.h' &&
/*************************************************************/
/*                                                           */
/*  Copyright (c) 1986                                       */
/*  John J. Grefenstette                                     */
/*  Navy Center for Applied Research in AI                   */
/*  Naval Research Laboratory                                */
/*                                                           */
/*  Permission is hereby granted to copy all or any part of  */
/*  this program for free distribution.   The author's name  */
/*  and this copyright notice must be included in any copy.  */
/*                                                           */
/*************************************************************/
X 
X
/*
X *  file:	format.h
X *
X *  author:	John J. Grefenstette
X *
X *  created:	1981
X *
X *  purpose:	specify the formats for the input and output files
X */
X 
X
/* FORMAT is the format for both reading and printing the input	*/
/* parameters; IN_VARS and OUT_VARS are the corresponding vars	*/
X
#define N_FORM 15	/* number of variables in FORMAT */
X
#define FORMAT "\n\
X      Experiments = %d\n\
X     Total Trials = %ld\n\
X  Population Size = %d\n\
X Structure Length = %d\n\
X   Crossover Rate = %lf\n\
X    Mutation Rate = %lf\n\
X   Generation Gap = %lf\n\
X   Scaling Window = %d\n\
X  Report Interval = %d\n\
X Structures Saved = %d\n\
Max Gens w/o Eval = %d\n\
X    Dump Interval = %d\n\
X      Dumps Saved = %d\n\
X          Options = %s\n\
X      Random Seed = %u\n"
X
#define IN_VARS &Totalexperiments, &Totaltrials, &Popsize, &Length, \
X	&C_rate, &M_rate, &Gapsize, &Windowsize, &Interval, &Savesize, \
X	&Maxspin, &Dump_freq, &Num_dumps, Options, &Seed
X
#define OUT_VARS Totalexperiments, Totaltrials, Popsize, Length, \
X	C_rate, M_rate, Gapsize, Windowsize, Interval, Savesize, \
X	Maxspin, Dump_freq, Num_dumps, Options, Seed
X
/* FORM_2 is the format for reading and printing optional input	*/
/* parameters; IN_2 and OUT_2 are the corresponding variables	*/
X
#define FORM_2 "\
X     Maximum Bias = %lf\n\
X  Max Convergence = %d\n\
X   Conv Threshold = %lf\n\
DPE Time Constant = %d\n\
X    Sigma Scaling = %lf\n"
X
#define IN_2  &Maxbias, &Maxconv, &Convlev, &DPEfreq, &Sigfact
#define OUT_2  Maxbias,  Maxconv,  Convlev,  DPEfreq,  Sigfact
X
/* separator for application-specific arguments */
#define GARGSEP "--\n"
X
X
/* FORM_CKPT is the format used for both reading and printing	*/
/* checkpoint data; IN_CKPT and OUT_CKPT are the matching vars	*/
X
#define N_CKPT 15	/* number of variables in FORM_CKPT */
X
#define FORM_CKPT "\
X  Experiment %d\n\
X   Totonline %le\n\
X  Totoffline %le\n\
X         Gen %d\n\
X       Onsum %le\n\
X      Offsum %le\n\
X      Trials %ld\n\
X     Plateau %ld\n\
X        Best %le\n\
X       Worst %le\n\
X        Spin %d\n\
X   Curr_dump %d\n\
X     Mu_next %ld\n\
X    Lastzoom %d\n\
X   Next Seed %u\n"
X
#define IN_CKPT &Experiment, &Totonline, &Totoffline, &Gen, \
X	&Onsum, &Offsum, &Trials, &Plateau, &Best, &Worst, &Spin, \
X	&Curr_dump, &Mu_next, &Lastzoom, &Seed
X
#define OUT_CKPT Experiment, Totonline, Totoffline, Gen, \
X	Onsum, Offsum, Trials, Plateau, Best, Worst, Spin, \
X	Curr_dump, Mu_next, Lastzoom, Seed
X
X
X
/* OUT_F2 is the format for the data produced by 'Measure' to	*/
/* be used by 'report'; OUT_V2 describes the corresponding vars	*/
X
#define OUT_F2 "%4d %5ld %3d %3d %5.3f % .5e % .5e % e % e\n"
X
#define OUT_V2 Gen, Trials, Lost, Conv, Bias, \
X	Online, Offline, Best, Ave_current_perf
X
X
/*	LINE_FIN is the input format of each line of the outfile	*/
/*	used by the report program; LINE_VIN are the matching vars	*/
X
#define LINE_FIN "%lf %lf %lf %lf %lf %lf %lf %lf %lf"
X
#define LINE_VIN  &line[0], &line[1], &line[2], &line[3], \
X	&line[4], &line[5], &line[6], &line[7], &line[8]
X
X 
/** end of file **/
SHAR_EOF
chmod 0444 src/format.h ||
echo 'restore of src/format.h failed'
Wc_c="`wc -c < 'src/format.h'`"
test 3804 -eq "$Wc_c" ||
	echo 'src/format.h: original size 3804, current size' "$Wc_c"
fi
# ============= src/global.h ==============
if test -f 'src/global.h' -a X"$1" != X"-c"; then
	echo 'x - skipping src/global.h (File already exists)'
else
echo 'x - extracting src/global.h (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'src/global.h' &&
/*************************************************************/
/*                                                           */
/*  Copyright (c) 1986                                       */
/*  John J. Grefenstette                                     */
/*  Navy Center for Applied Research in AI                   */
/*  Naval Research Laboratory                                */
/*                                                           */
/*  Permission is hereby granted to copy all or any part of  */
/*  this program for free distribution.   The author's name  */
/*  and this copyright notice must be included in any copy.  */
/*                                                           */
/*************************************************************/
X 
X
/*
X *  file:   global.h
X *
X *  author: John J. Grefenstette
X *
X *  created:    1981
X *
X *  purpose:    global variables for genesis.
X *
X *  modified:   07 may 90  added name_file()  - Nici.
X *              12 jun 92  folded in extern.h - Nici.
X */
X
#include <stdio.h>
#include <math.h>
X
#include "define.h"
#include "format.h"
X
#ifdef  EXTERN
#define GLOBAL(T,N,V) extern T N
#define GARRAY(T,N,I) extern T N[]
#else
#define GLOBAL(T,N,V) T N = V
#define GARRAY(T,N,I) T N[I]
#endif
X
extern char *calloc();
extern char *malloc();
extern double  Rand();
X
/* The Input file specifies these parameters */
GLOBAL(int,    Totalexperiments, 1);     /* number of experiments   */
GLOBAL(long,   Totaltrials,   5000L);    /* trials per experiment   */
GLOBAL(int,    Popsize,         50);     /* population size         */
GLOBAL(int,    Length,          30);     /* bit length of structure */
GLOBAL(double, C_rate,           0.6);   /* crossover rate          */
GLOBAL(double, M_rate,           0.005); /* mutation rate           */
GLOBAL(double, Convlev,          0.95);  /* convergence threshold   */
GLOBAL(double, Gapsize,          1.0);   /* fraction of pop replaced per gen */
GLOBAL(int,    Windowsize,      -1);     /* used to update worst performance */
GLOBAL(int,    Interval,       500);     /* trials between statistic reports */
GLOBAL(int,    DPEfreq,          0);     /* DPE smoothing time constant     */
GLOBAL(int,    Savesize,         1);     /* number of structures in minfile */
GLOBAL(int,    Maxspin,          2);     /* max gens without evaluations    */
GLOBAL(double, Maxbias,          0.99);  /* maximum bias to reach           */
GLOBAL(int,    Maxconv,          0);     /* maximum alleles to converge     */
GLOBAL(double, Sigfact,          2.0);   /* sigma scaling factor            */
GLOBAL(int,    Dump_freq,        0);     /* gens between checkpointing      */
GLOBAL(int,    Num_dumps,        1);     /* number of checkpoint files kept */
GLOBAL(char,   Options[20],   "Aclu");   /* option flags                    */
GLOBAL(unsigned int, Seed, 123456789);   /* seed for random numbers         */
X
#ifndef UTILITY   /* skip the rest if this is for inset.c or report.c */
X
/* File names */
GARRAY(char, Bestfile,   40);   /* file of best structures  */
GARRAY(char, Ckptfile,   40);   /* name of check point file */
GLOBAL(int,  Curr_dump,   0);   /* suffix of last dumpfile  */
GARRAY(char, Dumpfile,   40);   /* current dumpfile name    */
GARRAY(char, Initfile,   40);   /* file of initial genomes  */
GARRAY(char, Infile,     40);   /* input file               */
GARRAY(char, Logfile,    40);   /* logs starts and restarts */
GARRAY(char, Minfile,    40);   /* file prefix of bestfile  */
GARRAY(char, Outfile,    40);   /* output file              */
GARRAY(char, Schemafile, 40);   /* schema history record    */
GARRAY(char, DPEfile,    40);   /* record of DPE parameters */
X
GLOBAL(char,       *Buff,    NULL); /* buffer for unpacked gene */
GLOBAL(STRUCTURE,  *Old,     NULL); /* pointer to population    */
GLOBAL(STRUCTURE,  *New,     NULL); /* pointer to population    */
GLOBAL(BESTSTRUCT, *Bestset, NULL); /* set of best structures   */
X
/* data collection and loop control variables */
GLOBAL(int,     Best_guy,   0);     /* index of best_current_perf       */
GLOBAL(int,     Bestsize,   0);     /* number of currently saved structures */
GLOBAL(int,     Bytes,      0);     /* byte-length of packed structures */
GLOBAL(int,     Full,       0);     /* number of full bytes in genome */
GLOBAL(int,     Slop,       0);     /* number of bits in last byte */
GLOBAL(int,     Conv,       0);     /* number of partially coverged genes   */
GLOBAL(int,     Experiment, 0);     /* experiment counter       */
GLOBAL(int,     Gen,        0);     /* generation counter       */
GLOBAL(long,    Mu_next,    0L);    /* next mutated position    */
GLOBAL(long,    Trials,     0L);    /* trial counter            */
GLOBAL(long,    Plateau,    0L);    /* counter for next output  */
GLOBAL(double,  Offline,    0.0);   /* offline performance      */
GLOBAL(double,  Online,     0.0);   /* online performance       */
GLOBAL(double,  Offsum,     0.0);   /* accumulator for offline performance  */
GLOBAL(double,  Onsum,      0.0);   /* accumulator for online performance   */
GLOBAL(double,  Best,       0.0);   /* best performance seen so far     */
GLOBAL(double,  Bias,       0.0);   /* ave. domination of alleles       */
GLOBAL(int,     Spin,       0);     /* number of gens since eval occurred   */
GLOBAL(int,     Lost,       0);     /* number of totally coverged positions */
GLOBAL(int,     Phenesize,  0);     /* max length of phenotype descriptions */
GLOBAL(int,     Lastzoom,   0);     /* last generation a DPE zoom occurred  */
GLOBAL(int,     Sigcount,   0);     /* counter for termination signals */
GLOBAL(char,    Doneflag,   0);     /* set when termination conditions hold */
GLOBAL(double,  Totbest,    0.0);   /* total for best           */
GLOBAL(double,  Totoffline, 0.0);   /* total for offline        */
GLOBAL(double,  Totonline,  0.0);   /* total for online         */
GLOBAL(double, *DPEhist,    NULL);  /* pointer to DPE history   */
GLOBAL(double, *Window,     NULL);  /* circular queue of recent worsts  */
GLOBAL(double, *Scale,      NULL);  /* loads DPEscale for each experiment */
GLOBAL(double, *Basis,      NULL);  /* loads DPEbasis for each experiment */
GLOBAL(double,  Worst,      0.0);   /* worst performance seen so far    */
GLOBAL(double,  Ave_current_perf,   0.0);  /* avg perf in current gen   */
GLOBAL(double,  Best_current_perf,  0.0);  /* best perf in current gen  */
GLOBAL(double,  Worst_current_perf, 0.0);  /* worst perf in current gen */
GLOBAL(double,  Few,        0.0);   /* replaces former FEW constant */
X
GARRAY(int,  Pre, CHAR_BIT);  /*   left bit mask */
GARRAY(int, Post, CHAR_BIT);  /*  right bit mask */
GARRAY(int,  Bit, CHAR_BIT);  /* single bit mask */
X
/* application-specific arguments */
GLOBAL(int,   GArgc, 0);
GARRAY(char, *GArgv, MAXGARG);
X
extern int    GAgenes,  GAposn[];
extern double GAfact[], GAbase[];
X
/* flags set according to the Options string */
GLOBAL(char, Allflag,     0);  /* evaluate all structures      */
GLOBAL(char, Aliasflag,   0);  /* avoid aliassing in Ctoi()    */
GLOBAL(char, Bestflag,    0);  /* print final best value       */
GLOBAL(char, Collectflag, 0);  /* performance data in outfile  */
GLOBAL(char, Convflag,    0);  /* convergence data in outfile  */
GLOBAL(char, Dumpflag,    0);  /* dump after each evaluation   */
GLOBAL(char, Eliteflag,   0);  /* elitist selection strategy   */
GLOBAL(char, Initflag,    0);  /* read initial structures      */
GLOBAL(char, Lastflag,    0);  /* dump the last generation     */
GLOBAL(char, Logflag,     0);  /* log starts and restarts      */
GLOBAL(char, Offlnflag,   0);  /* print final offline measure  */
GLOBAL(char, Onlnflag,    0);  /* print final online measure   */
GLOBAL(char, Restartflag, 0);  /* restart from last checkpoint */
GLOBAL(char, Schemflag,   0);  /* trace history of a schema    */
GLOBAL(char, Traceflag,   0);  /* trace program execution      */
GLOBAL(char, Uniflag,     0);  /* super-uniform initialization */
X
#endif  /* !UTILITY */
X
#ifndef EXTERN
X
/* procedure for setting up GAucsd file names: */
X
name_file(name, ext, base)
char *name, *ext, *base;
{
X    if (base) if (*base)
X    {
X		sprintf(name, "%s.%s", base, ext);
X
#ifndef NOSTAT
X		{
X			struct stat buf[1];
X
X			/* if subdir exists, use it */
X			if (!stat(ext, buf))
X				if ((buf->st_mode & S_IFDIR) == S_IFDIR)
X					sprintf(name, "%s%s%s", ext, DS, base);
X		}
#endif  /* !NOSTAT */
X    }
X    else strcpy(name, ext);
}
X
#endif  /* !EXTERN */
X
/*** end of file ***/
X
SHAR_EOF
chmod 0444 src/global.h ||
echo 'restore of src/global.h failed'
Wc_c="`wc -c < 'src/global.h'`"
test 8509 -eq "$Wc_c" ||
	echo 'src/global.h: original size 8509, current size' "$Wc_c"
fi
# ============= src/best.c ==============
if test -f 'src/best.c' -a X"$1" != X"-c"; then
	echo 'x - skipping src/best.c (File already exists)'
else
echo 'x - extracting src/best.c (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'src/best.c' &&
/*************************************************************/
/*                                                           */
/*  Copyright (c) 1986                                       */
/*  John J. Grefenstette                                     */
/*  Navy Center for Applied Research in AI                   */
/*  Naval Research Laboratory                                */
/*                                                           */
/*  Permission is hereby granted to copy all or any part of  */
/*  this program for free distribution.   The author's name  */
/*  and this copyright notice must be included in any copy.  */
/*                                                           */
/*************************************************************/
X
/*
X *  file:	best.c
X *
X *  author:	John J. Grefenstette
X *
X *  created:	1983
X *
X *  purpose:	input and output of best structures
X *
X *  modified:	15 apr 86
X *		16 dec 86: don't print Bestsize to minfile in Printbest()
X *      02 nov 90: store phenotypes, allow duplicates when -a
X */
X
#define   EXTERN
#include "global.h"
X
extern void Pack();
extern void Unpack();
extern double _eval();
X
static double max;	/* maximum (worst) performance in the Bestset */
static int maxptr;	/* pointer to structure with perf = max */
X
X
Savebest(i)
register int i;
{
X	/*  Save the ith structure in current population  */
X	/*  if it is one of the Savesize best seen so far */
X
X	register int j;		/* loop control var */
X	register int k;
X
X	int found;
X	if (Bestsize < Savesize)
X	{
X		if (!Allflag)
X		{
X			/* Bestsize is the number saved so far, so  		*/
X			/* there are still empty slots in the Bestset.		*/
X			/* Check if an identical structure is already there	*/
X
X			for (j = 0; j < Bestsize; j++)
X			{
X				for (k = 0, found = 1; (k < Bytes) && found; k++)
X					found = (New[i].Gene[k] == Bestset[j].Gene[k]);
X				if (found && Bestset[j].Gen > Lastzoom) return;
X			}
X		}
X
X		/* insert ith structure */
X		for (k = 0; k < Bytes; k++)
X			Bestset[Bestsize].Gene[k] = New[i].Gene[k];
X
X		/* obtain the phenotype, if available */
X		*(Bestset[Bestsize].Phene) = '\0';
X		_eval(Bestset[Bestsize].Phene, -Phenesize);
X
X		Bestset[Bestsize].Perf = New[i].Perf;
X		Bestset[Bestsize].Gen = Gen;
X		Bestset[Bestsize].Trials = Trials;
X		Bestsize++;
X
X		if (Bestsize == Savesize)
X		{
X			/* find worst element in Bestset */
X			max = Bestset[0].Perf;
X			maxptr = 0;
X			for (j = 1; j < Savesize; j++)
X			{
X				if (max < Bestset[j].Perf)
X				{
X					max = Bestset[j].Perf;
X					maxptr = j;
X				}
X			}
X		}
X	}
X	else if (New[i].Perf < max) 	/* then save New[i] */
X	{
X		if (!Allflag)   	/* unless its already there */
X		{
X			for (j = 0; j < Bestsize; j++)
X			{
X				for (k = 0, found = 1; (k < Bytes) && found; k++)
X					found = (New[i].Gene[k] == Bestset[j].Gene[k]);
X				if (found && Bestset[j].Gen > Lastzoom) return;
X			}
X		}
X
X		/* overwrite the worst one */
X		for (k = 0; k < Bytes; k++)
X			Bestset[maxptr].Gene[k] = New[i].Gene[k];
X
X		/* obtain the phenotype, if available */
X		*(Bestset[maxptr].Phene) = '\0';
X		_eval(Bestset[maxptr].Phene, -Phenesize);
X
X		Bestset[maxptr].Perf = New[i].Perf;
X		Bestset[maxptr].Gen = Gen;
X		Bestset[maxptr].Trials = Trials;
X
X		/* find worst element in Bestset */
X		max = Bestset[0].Perf;
X		maxptr = 0;
X		for (j = 1; j < Savesize; j++)
X		{
X			if (max < Bestset[j].Perf)
X			{
X				max = Bestset[j].Perf;
X				maxptr = j;
X			}
X		}
X	}
}
X
X
Printbest()
{
X	/*	Write the Best structures out to the Bestfile.	*/
X
X	register int i;
X	register int j;
X	register int k;
X	register int posn;
X	FILE *fp, *fopen();
X
X	Trace("Printbest entered");
X
X	fp = fopen(Bestfile, "w");
X	for (i = 0; i < Bestsize; i++)
X	{
X		Unpack(Bestset[i].Gene, Buff);
X		for (j = k = posn = 0; j < Length; j++)
X		{
X			if (GAgenes)
X			{
X				if (j == posn)
X				{
X					if (j) fprintf(fp, " ");
X					posn = GAposn[k++];
X					if (posn < 0) posn = -posn;
X				}
X			}
X			fprintf(fp, "%1d", Buff[j]);
X		}
X
X		fprintf(fp, "  %11.4e ", Bestset[i].Perf);
X		fprintf(fp, "%4d %4ld ", Bestset[i].Gen, Bestset[i].Trials);
X		fprintf(fp, "%s\n\n",    Bestset[i].Phene);
X	}
X
X	fclose(fp);
X
X	Trace("Printbest completed");
}
X
X
Readbest()
{
X	/*   Read the Best structures in from the Bestfile    */
X	/*   (during a Restart)                               */
X
X	int i, j, k;
X	char *s;
X	FILE *fp, *fopen();
X	static char *dummy = ".";
X
X	if (Savesize)
X	{
X		Trace("Readbest entered");
X
X		fp = fopen(Bestfile, "r");
X		if (fp == NULL) 
X		{
X			Bestsize = 0;
X			return;
X		}
X
X		for (Bestsize = 0; (fscanf(fp, "%1d", &k) != EOF); Bestsize++)
X		{
X			Buff[0] = k;
X			for (j = 1; j < Length; j++)
X			{
X				fscanf(fp, "%1d", &k);
X				Buff[j] = k;
X			}
X			Pack(Buff, Bestset[Bestsize].Gene);
X
X			fscanf(fp, " %lf", &Bestset[Bestsize].Perf);
X			fscanf(fp, " %d ", &Bestset[Bestsize].Gen);
X			fscanf(fp, " %ld", &Bestset[Bestsize].Trials);
X
X			/* read phenotype description, if any */
X			s = dummy;
X			for (k = -1; k < Phenesize && *s != '\n'; k += strlen(s))
X				s = fgets(Bestset[Bestsize].Phene+k, Phenesize+1-k, fp);
X
X			if (k < Phenesize) Bestset[Bestsize].Phene[k-2] = '\0';
X			else Error("Phenotype description too long");
X		}
X		fclose(fp);
X
X		/* find worst element in Bestset */
X		max = Bestset[0].Perf;
X		maxptr = 0;
X		for (i = 1; i < Bestsize; i++)
X		{
X			if (max < Bestset[i].Perf)
X			{
X				max = Bestset[i].Perf;
X				maxptr = i;
X			}
X		}
X
X		Trace("Readbest completed");
X	}
}
X
/**** end of file ****/
X
SHAR_EOF
chmod 0444 src/best.c ||
echo 'restore of src/best.c failed'
Wc_c="`wc -c < 'src/best.c'`"
test 5378 -eq "$Wc_c" ||
	echo 'src/best.c: original size 5378, current size' "$Wc_c"
fi
# ============= src/checkpt.c ==============
if test -f 'src/checkpt.c' -a X"$1" != X"-c"; then
	echo 'x - skipping src/checkpt.c (File already exists)'
else
echo 'x - extracting src/checkpt.c (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'src/checkpt.c' &&
/*************************************************************/
/*                                                           */
/*  Copyright (c) 1986                                       */
/*  John J. Grefenstette                                     */
/*  Navy Center for Applied Research in AI                   */
/*  Naval Research Laboratory                                */
/*                                                           */
/*  Permission is hereby granted to copy all or any part of  */
/*  this program for free distribution.   The author's name  */
/*  and this copyright notice must be included in any copy.  */
/*                                                           */
/*************************************************************/
X
/*
X *  file:	checkpt.c
X *
X *  author:	John J. Grefenstette
X *
X *  created:	1982
X *
X *  purpose:	save global variables in a file for later restart
X *
X *  modified:	18 apr 86
X *
X */
X
#define   EXTERN
#include "global.h"
X
extern void Printbest();
extern void Unpack();
extern int  Getptr();
extern long Rstate[];
X
X
Checkpoint(ckptfile)
char ckptfile[];
{
X	FILE *fp, *fopen();
X	int i,j;
X
X	Trace("Checkpoint entered");
X
X	fp = fopen(ckptfile, "w");
X	fprintf(fp, FORM_CKPT, OUT_CKPT);
X
X	if (Windowsize > 0)
X	{
X		fprintf(fp, "\nWindow");
X		for (i = 0; i < Windowsize; i++)
X		{
X			if (!(i%4)) fprintf(fp, "\n");
X			fprintf(fp, "%.8le\t", Window[i]);
X		}
X		fprintf(fp,"\n");
X	}
X
X	fprintf(fp, "\nRandom State");
X	for (i = 0; i < RAND_DEG; i++)
X	{
X		if (!(i%4)) fprintf(fp, "\n");
X		fprintf(fp, "0x%08lx\t", Rstate[i]);
X	}
X	fprintf(fp, "%d\n", Getptr());
X
X	if (DPEfreq)
X	{
X		fprintf(fp, "\nDPE State");
X		for (i = 0; i < GAgenes; i++)
X			fprintf(fp, "\n%.8le\t%.8le\t%.8le\t%.8le",
X				GAfact[i], GAbase[i], DPEhist[2*i], DPEhist[2*i+1]);
X		fprintf(fp,"\n");
X	}
X
X	fprintf(fp, "\nPopulation\n");
X	for (i = 0; i < Popsize; i++)
X	{
X		Unpack(New[i].Gene, Buff);
X		for (j = 0; j < Length; j++)
X			fprintf(fp, "%1d", Buff[j]);
X		fprintf(fp, " %.12le ", New[i].Perf);
X		fprintf(fp, "%1d\n", New[i].Needs_evaluation);
X	}
X	fclose(fp);
X
X	/*  save the best structures */
X	if (Savesize) Printbest();
X
X	Trace("Checkpoint completed");
}
X
/** end of file **/
X
SHAR_EOF
chmod 0444 src/checkpt.c ||
echo 'restore of src/checkpt.c failed'
Wc_c="`wc -c < 'src/checkpt.c'`"
test 2202 -eq "$Wc_c" ||
	echo 'src/checkpt.c: original size 2202, current size' "$Wc_c"
fi
# ============= src/converge.c ==============
if test -f 'src/converge.c' -a X"$1" != X"-c"; then
	echo 'x - skipping src/converge.c (File already exists)'
else
echo 'x - extracting src/converge.c (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'src/converge.c' &&
/*************************************************************/
/*                                                           */
/*  Copyright (c) 1986                                       */
/*  John J. Grefenstette                                     */
/*  Navy Center for Applied Research in AI                   */
/*  Naval Research Laboratory                                */
/*                                                           */
/*  Permission is hereby granted to copy all or any part of  */
/*  this program for free distribution.   The author's name  */
/*  and this copyright notice must be included in any copy.  */
/*                                                           */
/*************************************************************/
X
/*
X *  file:	converge.c
X *
X *  author:	John J. Grefenstette
X *
X *  created:	1982
X *
X *  purpose:	measure system convergence
X *
X *  modified:	7 feb 86
X *
X *		13 nov 86: leave structures packed.
X */
X
#define   EXTERN
#include "global.h"
X
Converge()
{
X	
X	register int i,j;
X	register int ones;
X	int focus;
X	int bit;
X	FILE *fp, *fopen();
X
X	Trace("Converge entered");
X
X	Bias = 0.0;
X	Lost = Conv = 0;
X	if (!Convflag) return;
X
X	for (j = 0; j < Length; j++)
X	{
X		focus = j / CHAR_BIT;
X		bit = j % CHAR_BIT;
X		ones = 0;
X		for (i = 0; i < Popsize; i++)
X			ones += ((New[i].Gene[focus] & Bit[bit]) != 0);
X		Lost += (ones == 0) || (ones == Popsize);
X		Conv += (ones <= Few) || (ones >= Popsize - Few);
X		Bias += (ones > Popsize/2) ? ones : (Popsize - ones);
X	}
X	Bias /= Popsize*Length;
X
X	Trace("Converge completed");
}
X
/*** end of file ***/
SHAR_EOF
chmod 0444 src/converge.c ||
echo 'restore of src/converge.c failed'
Wc_c="`wc -c < 'src/converge.c'`"
test 1598 -eq "$Wc_c" ||
	echo 'src/converge.c: original size 1598, current size' "$Wc_c"
fi
# ============= src/cross.c ==============
if test -f 'src/cross.c' -a X"$1" != X"-c"; then
	echo 'x - skipping src/cross.c (File already exists)'
else
echo 'x - extracting src/cross.c (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'src/cross.c' &&
/*************************************************************/
/*                                                           */
/*  Copyright (c) 1986                                       */
/*  John J. Grefenstette                                     */
/*  Navy Center for Applied Research in AI                   */
/*  Naval Research Laboratory                                */
/*                                                           */
/*  Permission is hereby granted to copy all or any part of  */
/*  this program for free distribution.   The author's name  */
/*  and this copyright notice must be included in any copy.  */
/*                                                           */
/*************************************************************/
X
/*
X *  file:	cross.c
X *
X *  author:	John J. Grefenstette
X *
X *  created:	1981
X *
X *  purpose:	perform two-point crossover on entire population
X *
X *  modified:	8 apr 86
X *
X *		13 nov 86:  perform crossover on packed structures.
X *
X *              4 august 87: add second crossover point
X *
X *              11 july 89: fix bug when xbyte1 == xbyte2 
X *                   (bug found by Jon Richardson.)
X *
X *		7 august 89: allow C_rate > 1.0   - Nici.
X */
X
#define   EXTERN
#include "global.h"
X
Crossover()
{
X	static int firstflag = 1;
X	static int last;	/* last element to undergo Crossover */
X
X	register int mom, dad;	/* participants in the crossover */
X	register int xpoint1;	/* first crossover point w.r.t. structure */
X	register int xpoint2;	/* second crossover point w.r.t. structure */
X	register int xbyte1;	/* first crossed byte */
X	register int xbit1; 	/* first crossed bit in xbyte1 */
X	register int xbyte2;	/* last crossed byte */
X	register int xbit2; 	/* last crossed bit in xbyte2 */
X	register int i;     	/* loop control variable */
X	register char temp; 	/* used for swapping alleles */
X
X	int diff;    	/* set if parents differ from offspring */
X	int count = 0;	/* loop counter for crossovers */
X	char *kid1;  	/* pointers to the offspring */
X	char *kid2;
X
X	Trace("Crossover entered");
X
X	if (firstflag)
X	{
X		last = C_rate*Popsize;
X		firstflag = 0;
X	}
X
X	while (count < last)
X	{
X		mom = count++ % Popsize;
X		dad = count++ % Popsize;
X
X		/* kids start as identical copies of parents */
X		kid1 = New[mom].Gene;
X		kid2 = New[dad].Gene;
X
X		/* choose two Crossover points */
X		xpoint1 = Randint(0, Length);
X		xpoint2 = Randint(0, Length - 1);
X
X		/* guarantee that xpoint1 < xpoint2 */
X		if (xpoint2 >= xpoint1) xpoint2++;
X		else
X		{
X			i = xpoint1;
X			xpoint1 = xpoint2;
X			xpoint2 = i;
X		}
X
X		xbyte1 = xpoint1 / CHAR_BIT;
X		xbit1  = xpoint1 % CHAR_BIT;
X		xbyte2 = xpoint2 / CHAR_BIT;
X		xbit2  = xpoint2 % CHAR_BIT;
X
X		/* do parents differ outside cross segment? */
X		for (diff = i = 0; !diff && i < xbyte1; i++)
X			diff = (kid1[i] != kid2[i]);
X		for (i = xbyte2 + 1; !diff && i < Full; i++)
X			diff = (kid1[i] != kid2[i]);
X		if (!diff)
X		{
X			diff = ((kid1[xbyte1] & Pre[xbit1]) !=
X				(kid2[xbyte1] & Pre[xbit1]));
X			if (xbyte2 < Full)
X				diff += ((kid1[xbyte2] & Post[xbit2]) !=
X					 (kid2[xbyte2] & Post[xbit2]));
X			if (Slop)
X				diff += ((kid1[Full] & Pre[Slop]) !=
X					 (kid2[Full] & Pre[Slop]));
X		}
X
X		if (diff)	/* they do */
X		{
X			/* perform crossover */
X			temp = kid1[xbyte1];
X			kid1[xbyte1] = (kid1[xbyte1] & Pre[xbit1]) |
X				(kid2[xbyte1] & Post[xbit1]);
X
X			kid2[xbyte1] = (kid2[xbyte1] & Pre[xbit1]) |
X				(temp & Post[xbit1]);
X
X			diff = ((kid1[xbyte1] & Post[xbit1]) !=
X				(kid2[xbyte1] & Post[xbit1]));
X
X			for (i = xbyte1 + 1; i < xbyte2; i++)
X			{
X				temp = kid1[i];
X				kid1[i] = kid2[i];
X				kid2[i] = temp;
X				diff += (kid1[i] != kid2[i]);
X			}
X
X			if (xbyte1 < xbyte2)
X			{
X				temp = kid1[xbyte2];
X				kid1[xbyte2] = (kid1[xbyte2] & Post[xbit2]) |
X					(kid2[xbyte2] & Pre[xbit2]);
X
X				kid2[xbyte2] = (kid2[xbyte2] & Post[xbit2]) |
X					(temp & Pre[xbit2]);
X
X				diff += ((kid1[xbyte2] & Pre[xbit2]) !=
X					 (kid2[xbyte2] & Pre[xbit2]));
X			}
X			else
X			{
X				temp = kid1[xbyte2];
X				kid1[xbyte2] = (kid1[xbyte2] & Pre[xbit2]) |
X					(kid2[xbyte2] & Post[xbit2]);
X
X				kid2[xbyte2] = (kid2[xbyte2] & Pre[xbit2]) |
X					(temp & Post[xbit2]);
X
X				diff = ((kid1[xbyte2] & Post[xbit1] & Pre[xbit2]) !=
X					(kid2[xbyte2] & Post[xbit1] & Pre[xbit2]));
X
X			}
X
X			if (diff)	/* kids differ from parents */
X			{
X				/* set evaluation flags */
X				New[mom].Needs_evaluation = 1;
X				New[dad].Needs_evaluation = 1;
X			}
X		}
X	}
X	Trace("Crossover completed");
}
X
/** end of file **/
X
SHAR_EOF
chmod 0444 src/cross.c ||
echo 'restore of src/cross.c failed'
Wc_c="`wc -c < 'src/cross.c'`"
test 4483 -eq "$Wc_c" ||
	echo 'src/cross.c: original size 4483, current size' "$Wc_c"
fi
# ============= src/decode.c ==============
if test -f 'src/decode.c' -a X"$1" != X"-c"; then
	echo 'x - skipping src/decode.c (File already exists)'
else
echo 'x - extracting src/decode.c (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'src/decode.c' &&
/*************************************************************/
/*                                                           */
/*  Copyright (c) 1986                                       */
/*  John J. Grefenstette                                     */
/*  Navy Center for Applied Research in AI                   */
/*  Naval Research Laboratory                                */
/*                                                           */
/*  Permission is hereby granted to copy all or any part of  */
/*  this program for free distribution.   The author's name  */
/*  and this copyright notice must be included in any copy.  */
/*                                                           */
/*************************************************************/
X
/*
X *  file:	decode.c
X *
X *  author:	John J. Grefenstette
X *
X *  created:	1990 (functions date back to 1981)
X *
X *  purpose:	functions to decode genotypes into phenotypes
X *
X */
X
#define   EXTERN
#include "global.h"
X
X
Unpack(binbuf, charbuf)
/*
X * convert left-justified packed genotypes to unpacked form
X */
register char *binbuf;		/* packed array		*/
register char *charbuf;		/* unpacked form	*/
{
X	register i, j;
X
X	for (i = 0; i < Full; i++, binbuf++)
X		for (j = 0; j < CHAR_BIT; j++)
X			*charbuf++ = ((*binbuf & Bit[j]) != 0);
X
X	if (Slop)
X		for (j = 0; j < Slop; j++)
X			*charbuf++ = ((*binbuf & Bit[j]) != 0);
}
X
X
Degray(inbuf, outbuf, length)
/*
X * translate unpacked genes from reflected Gray code to binary
X */
char *inbuf, *outbuf;
register int length;
{
X	register int i;
X	register int last;
X
X	last = 0;
X	for (i = 0; i < length; i++)
X	{
X		if (inbuf[i])  outbuf[i] = !last;
X		else outbuf[i] = last;
X		last = outbuf[i];
X	}
}
X
X
double Ctoi(buf, length)
/*
X * decode binary integer from char array into real value
X * 'buf' must be unpacked (contain only \000 and \001's)
X */
register char *buf;
register int length;
{
X	register int i;
X	register double answer = 0.0;
X	extern char Aliasflag;
X	extern double Rand();
X
X	for (i = 0; i < length; i++)
X	{
X		answer *= 2.0;
X		answer += *buf++;
X	}
X	if (Aliasflag) answer += Rand();
X	return(answer);
}
X
/*** end of file ***/
SHAR_EOF
chmod 0444 src/decode.c ||
echo 'restore of src/decode.c failed'
Wc_c="`wc -c < 'src/decode.c'`"
test 2137 -eq "$Wc_c" ||
	echo 'src/decode.c: original size 2137, current size' "$Wc_c"
fi
# ============= src/done.c ==============
if test -f 'src/done.c' -a X"$1" != X"-c"; then
	echo 'x - skipping src/done.c (File already exists)'
else
echo 'x - extracting src/done.c (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'src/done.c' &&
X
/*************************************************************/
/*                                                           */
/*  Copyright (c) 1989                                       */
/*  Nicol N. Schraudolph                                     */
/*  Computer Science & Engineering, C-014                    */
/*  University of California, San Diego                      */
/*                                                           */
/*  Permission is hereby granted to copy all or any part of  */
/*  this program for free distribution.   The author's name  */
/*  and this copyright notice must be included in any copy.  */
/*                                                           */
/*************************************************************/
X
/*
X *  file:   	done.c
X *
X *  author: 	Nicol N. Schraudolph
X *
X *  created:	August 1989
X *
X *  purpose:	provide for orderly termination on interrupt
X *
X */
X
#ifndef NOSIGNAL
X
#define   EXTERN
#include "global.h"
X
/* #define void int	*/	/* for confused compilers */
X
extern void Killer();
void (*Catcher)() = Killer;
X
void Killer(sig, code, scp, addr)
int sig, code;
char *scp, *addr;
{
X	if (Sigcount == 2)
X	{
X		printf("third signal: immediate abort, might leave a mess\n");
X		Error("killed by triple signal");
X	}
X	else if (Sigcount == 1)
X	{
X		printf("second signal: dump & quit after current generation\n");
X		Sigcount = 2;
X		signal(SIGINT,  Catcher);
X		signal(SIGTERM, Catcher);
X	}
X	else
X	{
X		printf("first signal: conclusion after current run\n");
X		Totalexperiments = Experiment;
X		Sigcount = 1;
X		signal(SIGINT,  Catcher);
X		signal(SIGTERM, Catcher);
X	}
}
X
#endif  /* !NOSIGNAL */
X
/* end of file */
SHAR_EOF
chmod 0444 src/done.c ||
echo 'restore of src/done.c failed'
Wc_c="`wc -c < 'src/done.c'`"
test 1674 -eq "$Wc_c" ||
	echo 'src/done.c: original size 1674, current size' "$Wc_c"
fi
# ============= src/dpe.c ==============
if test -f 'src/dpe.c' -a X"$1" != X"-c"; then
	echo 'x - skipping src/dpe.c (File already exists)'
else
echo 'x - extracting src/dpe.c (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'src/dpe.c' &&
/*************************************************************/
/*                                                           */
/*  Copyright (c) 1989                                       */
/*  Nicol N. Schraudolph                                     */
/*  Computer Science & Engineering, C-014                    */
/*  University of California, San Diego                      */
/*                                                           */
/*  Permission is hereby granted to copy all or any part of  */
/*  this program for free distribution.   The author's name  */
/*  and this copyright notice must be included in any copy.  */
/*                                                           */
/*************************************************************/
X
/*
X *  file:   	dpe.c
X *
X *  author: 	Nicol N. Schraudolph
X *
X *  created:	November 1989
X *
X *  purpose:	implement Dynamic Parameter Encoding
X *
X */
X
#define   EXTERN
#include "global.h"
X
X
DPE()
{
X	
X	register int i,j;
X	register int one, two;
X	register int bit1, bit2;
X	register int focus1, focus2;
X	int zoom, active, posn;
X	double range;
X	FILE *fp, *fopen();
X
X	Trace("DPE entered");
X	posn = 0;
X
X	for (j = 0; j < GAgenes; j++)
X	{
X		if (GAposn[j] < 1)
X		{
X			posn = -GAposn[j];
X			continue;
X		}
X
X		bit1 = posn % CHAR_BIT;
X		focus1 = posn / CHAR_BIT;
X		posn++;
X		bit2 = posn % CHAR_BIT;
X		focus2 = posn / CHAR_BIT;
X
X		one = two = 0;
X		for (i = 0; i < Popsize; i++)
X		{
X			if (New[i].Gene[focus1] & Bit[bit1]) one++;
X			if (!(New[i].Gene[focus2] & Bit[bit2])) two++;
X		}
X
X		DPEhist[2*j] *= 1.0 - 1.0/DPEfreq;
X		DPEhist[2*j] += one/(double)DPEfreq;
X		one = DPEhist[2*j];
X		DPEhist[2*j+1] *= 1.0 - 1.0/DPEfreq;
X		DPEhist[2*j+1] += two/(double)DPEfreq;
X		two = DPEhist[2*j+1];
X
X		zoom = 0;
X		if (one < Few) zoom = 1;
X		else
X		{
X			one = Popsize - one + 1;
X			if (one < Few) zoom = 3;
X			else one = Few;
X		}
X		if (two < one)
X		{
X			zoom = 2;
X			bit1 = bit2;
X			focus1 = focus2;
X		}
X
X		range = 1.0;
X		for (i = 0; i <= GAposn[j] - posn; i++) range *= 2.0;
X		range *= GAfact[j];
X		posn = GAposn[j];
X
X		if (zoom)
X		{
X			Lastzoom = Gen;
X			DPEhist[2*j] = DPEhist[2*j+1] = 0.5*Popsize;
X			range /= 2.0;
X			GAfact[j] /= 2.0;
X			GAbase[j] += (zoom - 1)*(range/2.0);
X			bit2 = (posn - 1) % CHAR_BIT;
X			focus2 = (posn - 1) / CHAR_BIT;
X
X			for (i = 0; i < Popsize; i++)
X			{
X				one = focus1;
X				two = New[i].Gene[one] & Pre[bit1];
X				two |= (New[i].Gene[one] << 1) & Post[bit1];
X				if (zoom > 1) two ^= Bit[bit1];
X
X				while (one < focus2)
X				{
X					if (New[i].Gene[one+1] & Pre[1]) two ^= 1;
X					New[i].Gene[one++] = two;
X					two = New[i].Gene[one] << 1;
X				}
X				New[i].Gene[one] &= Post[bit2];
X				New[i].Gene[one] |= two & Pre[bit2];
X
X				if (Rand() < 0.5) New[i].Gene[one] ^= Bit[bit2];
X				New[i].Needs_evaluation = 1;
X			}
X
X			fp = fopen(DPEfile, "a");
X			fprintf(fp, "%4d %7ld %3d   % le", Gen, Trials, j, GAbase[j]);
X			fprintf(fp, " % le   %le\n", GAbase[j] + range, GAfact[j]);
X			fclose(fp);
X		}
X	}
X	Trace("DPE completed");
}
X
/*** end of file ***/
SHAR_EOF
chmod 0444 src/dpe.c ||
echo 'restore of src/dpe.c failed'
Wc_c="`wc -c < 'src/dpe.c'`"
test 3020 -eq "$Wc_c" ||
	echo 'src/dpe.c: original size 3020, current size' "$Wc_c"
fi
# ============= src/elitist.c ==============
if test -f 'src/elitist.c' -a X"$1" != X"-c"; then
	echo 'x - skipping src/elitist.c (File already exists)'
else
echo 'x - extracting src/elitist.c (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'src/elitist.c' &&
/*************************************************************/
/*                                                           */
/*  Copyright (c) 1986                                       */
/*  John J. Grefenstette                                     */
/*  Navy Center for Applied Research in AI                   */
/*  Naval Research Laboratory                                */
/*                                                           */
/*  Permission is hereby granted to copy all or any part of  */
/*  this program for free distribution.   The author's name  */
/*  and this copyright notice must be included in any copy.  */
/*                                                           */
/*************************************************************/
X
/*
X *  file:	elitist.c
X *
X *  author:	John J. Grefenstette
X *
X *  created:	1982
X *
X *  purpose:	The elitist policy stipulates that the best individual
X *		always survives into the new generation.  The elite
X *		individual is placed in the last position in New pop,
X *		and is not changed through crossover or mutation.
X *
X *  modified:	24 mar 86
X */
X
#define   EXTERN
#include "global.h"
X
X
Elitist()
{
X	register int i;		/* loop control variables */
X	register int k;
X	register int found;	 /* set if elite is found */
X
X
X	Trace("Elitist entered");
X
X	/* is anybody in current population identical  */
X	/* to the best guy in the previous generation? */
X
X	for (i = 0, found = 0; i < Popsize && !found; i++)
X	{
X		for (k = 0, found = 1; found && (k < Full); k++)
X			found = (New[i].Gene[k] == Old[Best_guy].Gene[k]);
X		if (found && Slop)
X			found = ((New[i].Gene[k] & Pre[Slop]) ==
X				 (Old[Best_guy].Gene[k] & Pre[Slop]));
X	}
X
X	if (!found) 	/* elite was not present */
X	{
X		/* replace last guy with the elite one */
X		for (k = 0; k < Bytes; k++)
X			New[Popsize-1].Gene[k] = Old[Best_guy].Gene[k];
X		New[Popsize-1].Perf = Old[Best_guy].Perf;
X		New[Popsize-1].Needs_evaluation = 0;
X		if (Traceflag)
X			printf("perf: %e\n", New[Popsize-1].Perf);
X	}
X
X	Trace("Elitist completed");
}
X
/*** end of file ***/
SHAR_EOF
chmod 0444 src/elitist.c ||
echo 'restore of src/elitist.c failed'
Wc_c="`wc -c < 'src/elitist.c'`"
test 2064 -eq "$Wc_c" ||
	echo 'src/elitist.c: original size 2064, current size' "$Wc_c"
fi
# ============= src/encode.c ==============
if test -f 'src/encode.c' -a X"$1" != X"-c"; then
	echo 'x - skipping src/encode.c (File already exists)'
else
echo 'x - extracting src/encode.c (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'src/encode.c' &&
/*************************************************************/
/*                                                           */
/*  Copyright (c) 1986                                       */
/*  John J. Grefenstette                                     */
/*  Navy Center for Applied Research in AI                   */
/*  Naval Research Laboratory                                */
/*                                                           */
/*  Permission is hereby granted to copy all or any part of  */
/*  this program for free distribution.   The author's name  */
/*  and this copyright notice must be included in any copy.  */
/*                                                           */
/*************************************************************/
X
/*
X *  file:	encode.c
X *
X *  author:	John J. Grefenstette
X *
X *  created:	1990 (functions date back to 1981)
X *
X *  purpose:	functions to encode phenotypes into genotypes
X *
X */
X
#define   EXTERN
#include "global.h"
X
X
Itoc(n, outbuf, length)
/*
X * convert integer n into unpacked, binary coded char array
X */
register int n;
register char *outbuf;
int length;
{
X	register int i;
X
X	for (i = length - 1; i >= 0; i--)
X	{
X		outbuf[i] = (n & 1);
X		n >>= 1;
X	}
}
X
X
Gray(inbuf, outbuf, length)
/*
X * translate unpacked genes from binary to reflected Gray code
X */
char *inbuf, *outbuf;
register int length;
{
X	register int i;
X	register int last;
X
X	last = 0;
X	for (i = 0; i < length; i++)
X	{
X		outbuf[i] = (inbuf[i] != last);
X		last = inbuf[i];
X	}
}
X
X
X
Pack(charbuf, binbuf)
/*
X * convert unpacked genotype into left-justified packed form
X */
register char *charbuf;		/* unpacked array, one bit per char	*/
register char *binbuf;		/* packed representation of charbuf	*/
{
X	register i, j;
X
X	for (i = 0; i < Full; i++, binbuf++)
X	{
X		*binbuf = '\0';
X		for (j = 0; j < CHAR_BIT; j++)
X			if (*charbuf++)  *binbuf |= Bit[j];
X	}
X
X	if (Slop)
X	{
X		*binbuf = '\0';
X		for (j = 0; j < Slop; j++)
X			if (*charbuf++)  *binbuf |= Bit[j];
X	}
}
X
/*** end of file ***/
SHAR_EOF
chmod 0444 src/encode.c ||
echo 'restore of src/encode.c failed'
Wc_c="`wc -c < 'src/encode.c'`"
test 2013 -eq "$Wc_c" ||
	echo 'src/encode.c: original size 2013, current size' "$Wc_c"
fi
# ============= src/error.c ==============
if test -f 'src/error.c' -a X"$1" != X"-c"; then
	echo 'x - skipping src/error.c (File already exists)'
else
echo 'x - extracting src/error.c (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'src/error.c' &&
/*************************************************************/
/*                                                           */
/*  Copyright (c) 1986                                       */
/*  John J. Grefenstette                                     */
/*  Navy Center for Applied Research in AI                   */
/*  Naval Research Laboratory                                */
/*                                                           */
/*  Permission is hereby granted to copy all or any part of  */
/*  this program for free distribution.   The author's name  */
/*  and this copyright notice must be included in any copy.  */
/*                                                           */
/*************************************************************/
X
/*
X *  file:	error.c
X *
X *  author:	John J. Grefenstette
X *
X *  created:	apr 84
X *
X *  purpose:	print message in error log file and abort.
X *
X *  modified:	7 feb 86
X */
X
#include <stdio.h>
X
Error(s)
char *s;
{
X	FILE *fopen(), *fp;
X	long clock;
X	long time();
X	char *ctime();
X
X	fp = fopen("errors", "a");
X	fprintf(fp, "%s\n", s);
X	time(&clock);
X	fprintf(fp, "%s\n", ctime(&clock));
X	fclose(fp);
X	fprintf(stderr, "%s\n", s);
X	
X	exit(1);
}
X
/*** end of file ***/
X
SHAR_EOF
chmod 0444 src/error.c ||
echo 'restore of src/error.c failed'
Wc_c="`wc -c < 'src/error.c'`"
test 1229 -eq "$Wc_c" ||
	echo 'src/error.c: original size 1229, current size' "$Wc_c"
fi
# ============= src/evaluate.c ==============
if test -f 'src/evaluate.c' -a X"$1" != X"-c"; then
	echo 'x - skipping src/evaluate.c (File already exists)'
else
echo 'x - extracting src/evaluate.c (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'src/evaluate.c' &&
/*************************************************************/
/*                                                           */
/*  Copyright (c) 1986                                       */
/*  John J. Grefenstette                                     */
/*  Navy Center for Applied Research in AI                   */
/*  Naval Research Laboratory                                */
/*                                                           */
/*  Permission is hereby granted to copy all or any part of  */
/*  this program for free distribution.   The author's name  */
/*  and this copyright notice must be included in any copy.  */
/*                                                           */
/*************************************************************/
X
/*
X *  file:	evaluate.c
X *
X *  author:	John J. Grefenstette
X *
X *  created:	1981
X *
X *  purpose:	evaluate the current population by
X *		calling the user-defined function "eval"
X *
X *  modified:	13 feb 86
X *
X *		28 Aug 89: call _eval() with packed gene  - Nici.
X */
X
#define   EXTERN
#include "global.h"
X
extern double _eval(); 
extern void Checkpoint();
extern void Savebest();
X
Evaluate()
{
X	register double performance;
X	register int i;
X
X	Trace("Evaluate entered");
X
X	for (i = 0; i < Popsize; i++)
X	{
X		if (New[i].Needs_evaluation)
X		{
X			New[i].Perf = _eval(New[i].Gene, Length);
X			performance = New[i].Perf;
X			New[i].Needs_evaluation = 0;
X			Trials++;
X			Spin = 0;   /* we're making progress */
X			if (Savesize) Savebest(i);
X
X			if (performance < Best || Trials == 1) Best = performance;
X			Onsum += performance;
X			Offsum += Best;
X
X			if (Dumpflag) Checkpoint(Ckptfile);
X		}
X	}
X	Trace("Evaluate completed");
}
X
/** end of file **/
X
SHAR_EOF
chmod 0444 src/evaluate.c ||
echo 'restore of src/evaluate.c failed'
Wc_c="`wc -c < 'src/evaluate.c'`"
test 1708 -eq "$Wc_c" ||
	echo 'src/evaluate.c: original size 1708, current size' "$Wc_c"
fi
# ============= src/gap.c ==============
if test -f 'src/gap.c' -a X"$1" != X"-c"; then
	echo 'x - skipping src/gap.c (File already exists)'
else
echo 'x - extracting src/gap.c (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'src/gap.c' &&
/*************************************************************/
/*                                                           */
/*  Copyright (c) 1986                                       */
/*  John J. Grefenstette                                     */
/*  Navy Center for Applied Research in AI                   */
/*  Naval Research Laboratory                                */
/*                                                           */
/*  Permission is hereby granted to copy all or any part of  */
/*  this program for free distribution.   The author's name  */
/*  and this copyright notice must be included in any copy.  */
/*                                                           */
/*************************************************************/
X
/*
X *  file:	gap.c
X *
X *  author:	John J. Grefenstette
X *
X *  created:	1981
X *
X *  purpose:	If the population gap is less than 1.0,
X *		choose survivors from old population	
X *		uniformly, without replacement.	
X *
X *  modified:	7 feb 86
X */
X
#define   EXTERN
#include "global.h"
X
X
Gap(sample)
int sample[];
{
X	static firstflag = 1;
X	static int *samp2;
X	int i,j;		
X	int temp;
X
X	if (firstflag)
X	{
X		samp2 = (int *) calloc((unsigned) Popsize, sizeof(int));
X		firstflag = 0;
X	}
X
X	/* randomly shuffle the new structures */
X	for (i=0; i<Popsize; i++)
X	{
X		j = Randint(i,Popsize-1);
X		temp = sample[j];
X		sample[j] = sample[i];
X		sample[i] = temp;
X	}
X
X	/* construct a uniform shuffle */
X	for (j=0; j<Popsize; j++) samp2[j]=j;
X	for (j=0; j<Popsize; j++)
X	{
X		i = Randint(j, Popsize-1);
X		temp = samp2[i];
X		samp2[i] = samp2[j];
X		samp2[j] = temp;
X	}
X
X	/* now choose survivors */
X	for (i=Gapsize*Popsize; i<Popsize; i++)
X		sample[i] = samp2[i];
}
X
/* end of file */
SHAR_EOF
chmod 0444 src/gap.c ||
echo 'restore of src/gap.c failed'
Wc_c="`wc -c < 'src/gap.c'`"
test 1726 -eq "$Wc_c" ||
	echo 'src/gap.c: original size 1726, current size' "$Wc_c"
fi
# ============= src/generate.c ==============
if test -f 'src/generate.c' -a X"$1" != X"-c"; then
	echo 'x - skipping src/generate.c (File already exists)'
else
echo 'x - extracting src/generate.c (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'src/generate.c' &&
/*************************************************************/
/*                                                           */
/*  Copyright (c) 1986                                       */
/*  John J. Grefenstette                                     */
/*  Navy Center for Applied Research in AI                   */
/*  Naval Research Laboratory                                */
/*                                                           */
/*  Permission is hereby granted to copy all or any part of  */
/*  this program for free distribution.   The author's name  */
/*  and this copyright notice must be included in any copy.  */
/*                                                           */
/*************************************************************/
X
/*
X *  file:	generate.c
X *
X *  author:	John J. Grefenstette
X *
X *  created:	1981
X *
X *  purpose:	One generation consists of
X *			(1) forming a new population of structures.
X *			(2) evaluating the population.
X *			(3) gathering performance statistics.
X *
X *  modified:	7 feb 86
X *
X *		2 dec 86: Measure() now calls Converge().
X */
X
#define   EXTERN
#include "global.h"
X
extern void Checkpoint();
extern void Crossover();
extern void Elitist();
extern void Evaluate();
extern void Initialize();
extern void Mutate();
extern void Printbest();
extern void Restart();
extern void Select();
extern void DPE();
X
X
Generate()
{
X	STRUCTURE *temp;	/* for swapping population pointers	*/
X	register int i;		/* for marking structures		*/
X
X	if (Traceflag) printf("                    Gen %d\n",Gen);
X	Trace("Generate entered");
X
X	/* create a new population */
X
X	if (Restartflag)	/* restart - read "ckpt" file */
X		Restart();
X	else if (Gen == 0)	/* this is a fresh run */
X	{
X		Initialize();	/* form an initial population */
X		Spin++;	
X	}
X	else
X		/* form a new population from the */
X		/* old one via genetic operators  */
X	{
X		Select();
X		Mutate();
X		Crossover();
X		if (Eliteflag) Elitist();
X
X		/* perform DPE if appropriate */
X		if (DPEfreq) DPE();
X
X		if (Allflag)	/* mark structures for evaluation */
X			for (i = 0; i < Popsize; i++) New[i].Needs_evaluation = 1;
X
X		Spin++;
X	}
X
X	/* evaluate the newly formed population */
X	Evaluate();
X
X	/* gather performance statistics */
X	Measure();
X
X	/* exit with dump after two signals */
X	if (Sigcount == 2) Doneflag = Lastflag = 1;
X
X	/* checkpoint if appropriate */
X	if (Num_dumps && Dump_freq && Gen % Dump_freq == 0)
X	{
X		if (Num_dumps > 1)
X		{
X			sprintf(Dumpfile, "%s.%03d", Ckptfile, Curr_dump);
X			Curr_dump = (Curr_dump + 1) % Num_dumps;
X			Checkpoint(Dumpfile);
X		}
X		Checkpoint(Ckptfile);
X	}
X	else if (Doneflag)
X	{
X		if (Lastflag) Checkpoint(Ckptfile);
X		else if (Savesize) Printbest();
X	}
X
X	/* prepare for next generation */
X	temp = Old;
X	Old = New;
X	New = temp;
X	Gen++;
X	Restartflag = 0;
X
X	Trace("Generate completed");
}
X
/*  end of file */
SHAR_EOF
chmod 0444 src/generate.c ||
echo 'restore of src/generate.c failed'
Wc_c="`wc -c < 'src/generate.c'`"
test 2847 -eq "$Wc_c" ||
	echo 'src/generate.c: original size 2847, current size' "$Wc_c"
fi
# ============= src/init.c ==============
if test -f 'src/init.c' -a X"$1" != X"-c"; then
	echo 'x - skipping src/init.c (File already exists)'
else
echo 'x - extracting src/init.c (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'src/init.c' &&
/*************************************************************/
/*                                                           */
/*  Copyright (c) 1986                                       */
/*  John J. Grefenstette                                     */
/*  Navy Center for Applied Research in AI                   */
/*  Naval Research Laboratory                                */
/*                                                           */
/*  Permission is hereby granted to copy all or any part of  */
/*  this program for free distribution.   The author's name  */
/*  and this copyright notice must be included in any copy.  */
/*                                                           */
/*************************************************************/
X
/*
X *  file:	init.c
X *
X *  author:	John J. Grefenstette
X *
X *  created:	1981
X *
X *  purpose:	create an initial population of structures,
X *		and initalize some performance variables.
X *		This is called at the start of each run.
X *
X *  modified:	7 feb 86
X *
X */
X
#define   EXTERN
#include "global.h"
X
extern void Generate();
extern void Pack();
X
X
Initialize()
{
X	FILE *fp, *fopen();
X	register int i, j;
X	register int k;
X	register int num;
X	int shift, byte;
X	int nc, *counters;
X	int x;
X	double r;
X
X	Trace("Initialize entered");
X
X	if (Totalexperiments > 1)
X		sprintf(Bestfile, "%s.%03d", Minfile, Experiment);
X
X	/* prepare for new run */
X
X	/* NOTE: Srand() automatically advances Seed for next run */
X	Srand(&Seed);
X
X	Sigcount = 0;
X	Doneflag = 0;
X	Curr_dump = 0;
X	Bestsize = 0;
X	Trials = Gen = 0;
X	Lost = Conv = 0;
X	Plateau = 0;
X	Spin = 0;
X	Lastzoom = -1;
X	Onsum = Offsum = 0.0;
X	for (i = 0; i < Windowsize; i++) Window[i] = 0.0;
X	for (i = 0; i < 2*GAgenes; i++)  DPEhist[i] = 0.5*Popsize;
X
X	/* set up initial population */
X
X	i = 0;		/* current structure */
X
X	if (Initflag)		/* get some structures from Initfile */
X	{
X		if ((fp = fopen(Initfile, "r")) == NULL)
X		{
X			char msg[40];
X			sprintf(msg, "Init: can't open %s", Initfile);
X			Error(msg);
X		}
X
X		/* get the number of structures in Initfile */
X		k = 0;
X		while (fscanf(fp, "%1d", &x) != EOF) k++;
X		fclose(fp);
X		if (k % Length != 0) 
X		{
X			char msg[40];
X			sprintf( msg, "Init: bad format in %s", Initfile);
X			Error(msg);
X		}
X
X		/* num = number of structures to be read from file */
X		num = k/Length < Popsize ? k/Length : Popsize;
X
X		if ((fp = fopen(Initfile, "r")) == NULL)
X		{
X			char msg[40];
X			sprintf(msg, "Init: can't open %s", Initfile);
X			Error(msg);
X		}
X		for (i = 0; i < num; i++)
X		{
X			for (j = 0; j < Length; j++)
X			{
X				fscanf(fp,"%1d", &x);
X				Buff[j] = x;
X			}
X			Pack(Buff, New[i].Gene);
X			New[i].Needs_evaluation = 1;
X		}
X		fclose(fp);
X	}
X
X	/* restore DPE to original search space */
X	if (Experiment > 1)
X	{
X		for (j = 0; j < GAgenes; j++)
X		{
X			GAfact[j] = Scale[j];
X			GAbase[j] = Basis[j];
X		}
X	}
X
X	if (Uniflag)	/* super-uniform initialization */
X	{
X		/* find out how many individuals to work on */
X		x = 0;
X		for (num = 1; num <= Popsize - i; num *= 2) x++;
X		num /= 2;
X		num--;
X		x--;
X
X		/* allocate and initialize counters */
X		nc = Length/x;
X		if (Length%x) nc++;
X		counters = (int *) calloc((unsigned) nc, sizeof(int));
X		for (k = 0; k < nc; k++) counters[k] = Randint(0, num);
X
X		for (j = 0; j <= num; i++, j++) 	/* for each individual */
X		{
X			for (k = 0; k < Bytes; k++) New[i].Gene[k] = 0;
X
X			k = byte = 0;
X			shift = CHAR_BIT - x;
X
X			while (k < nc && byte < Bytes)	/* scan through genome */
X			{
X				/* splice counter into byte */
X				if (shift > 0)
X				{
X					New[i].Gene[byte] |=	/* next counter */
X						(char)((counters[k++]++ & num) << shift);
X					shift -= x;
X				}
X				else
X				{
X					New[i].Gene[byte++] |=	   /* next byte */
X						(char)((counters[k] & num) >> -shift);
X					shift += CHAR_BIT;
X				}
X			}
X			if (k < nc) counters[k]++;
X			New[i].Needs_evaluation = 1;
X		}
X		free(counters);
X	}
X
X	for (; i < Popsize; i++)   /* initialize remainder randomly */ 
X	{
X		for (j = 0; j < Bytes; j++)
X			New[i].Gene[j] = Randint(0, Post[0]);
X		New[i].Needs_evaluation = 1;
X
X	}
X
X	/* find first location to mutate */
X	if (M_rate > 0.0 && M_rate < 1.0)
X	{
X		while ((r = Rand()) == 0.0);
X		Mu_next = (long) ceil(log(r) / log(1.0 - M_rate))/2;
X	}
X	else Mu_next = 0;
X
X	Trace("Initialize completed");
}
X
/** end of file **/
X
SHAR_EOF
chmod 0444 src/init.c ||
echo 'restore of src/init.c failed'
Wc_c="`wc -c < 'src/init.c'`"
test 4285 -eq "$Wc_c" ||
	echo 'src/init.c: original size 4285, current size' "$Wc_c"
fi
# ============= src/input.c ==============
if test -f 'src/input.c' -a X"$1" != X"-c"; then
	echo 'x - skipping src/input.c (File already exists)'
else
echo 'x - extracting src/input.c (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'src/input.c' &&
/*************************************************************/
/*                                                           */
/*  Copyright (c) 1986                                       */
/*  John J. Grefenstette                                     */
/*  Navy Center for Applied Research in AI                   */
/*  Naval Research Laboratory                                */
/*                                                           */
/*  Permission is hereby granted to copy all or any part of  */
/*  this program for free distribution.   The author's name  */
/*  and this copyright notice must be included in any copy.  */
/*                                                           */
/*************************************************************/
X
/*
X *  file:	input.c
X *
X *  author:	John J. Grefenstette
X *
X *  created:	1981
X *
X *  purpose:	Set up filenames and read the input file, and
X *		initialize variables for this run.
X *
X *		See init.c for the initialization of variables for each run.
X *
X *  modified:	26 jun 86
X *              23 may 90   added application-specific arguments  - Nici.
X */
X
#define   EXTERN
#include "global.h"
X
extern void Setflag();
X
Input(argc,argv)
int argc;
char *argv[];
{
X	FILE *fopen(), *fp;
X
X	int i;
X	char msg[80];
X	long clock;
X	long time();
X	char *ctime();
X	char *arg1 = 0;
X
X
X	/* set up file names */
X
X	if (argc >= 2) arg1 = argv[1];
X
X	name_file(Infile,    "in",  arg1);   
X	name_file(Outfile,   "out", arg1); 
X	name_file(Ckptfile,  "cpt", arg1); 
X	name_file(Minfile,   "min", arg1); 
X	name_file(Logfile,   "log", arg1);
X	name_file(Initfile,  "ini", arg1);
X	name_file(Schemafile,"sma", arg1);
X	name_file(DPEfile,   "dpe", arg1);
X
X	strcpy(Bestfile, Minfile);
X
X
X	/* read in the Input parameters from the in file */
X
X	if ((fp = fopen(Infile, "r")) == NULL)
X	{
X		sprintf(msg, "Input: can't open %s", Infile);
X		Error(msg);
X	}
X	if (fscanf(fp, " This is %s for %s ", msg, msg)) fgets(msg, 80, fp);
X	if (fscanf(fp, FORMAT, IN_VARS) < N_FORM)
X	{
X		sprintf(msg, "Input: garbled input file %s", Infile);
X		Error(msg);
X	}
X	fscanf(fp, FORM_2, IN_2);
X
X	if (!Interval) Interval = Totaltrials;
X	if (!Maxspin) Maxspin = INT_MAX;
X	if (!Maxconv) Maxconv = Length + 1;
X	Few = (int)((1.0 - Convlev)*Popsize);
X	Experiment = 1;
X
X	/* read application-specific arguments, if any */
X	GArgc = 0;
X	if (fgets(msg, 80, fp)) if (!strcmp(msg, GARGSEP))
X		while (fgets(msg, 80, fp))
X		{
X			i = strlen(msg);
X			if (msg[i - 1] == '\n') msg[i - 1] = '\0';
X			if (!*msg) break;
X			if (GArgc >= MAXGARG)
X			{
X				sprintf(msg,
X					"more than %d application-specific arguments", MAXGARG);
X				Error(msg);
X			}
X			GArgv[GArgc] = (char *) malloc(strlen(msg) + 1);
X			strcpy(GArgv[GArgc++], msg);
X		}
X	fclose(fp);
X
X	/* Bytes is the size of each packed chromosome */
X	Full = Length / CHAR_BIT;
X	Slop = Length % CHAR_BIT;
X	Bytes = Full;
X	if (Slop) Bytes++;
X
X	/* set up all the bit masks */
X	for (i = 0; i < CHAR_BIT; i++)
X	{
X		 Pre[i] = PRE(i);
X		Post[i] = POST(i);
X		 Bit[i] = BIT(i);
X	}
X
X	/* allocate storage for variable sized structures */
X
X	/* population arrays */
X	Old = (STRUCTURE *) calloc((unsigned) Popsize, sizeof(STRUCTURE));
X	New = (STRUCTURE *) calloc((unsigned) Popsize, sizeof(STRUCTURE));
X
X	/* the following request avoids excessive swapping  */
X	/* in the following loop                            */
X	Buff = malloc((unsigned) 2*Popsize*(Bytes+4));
X	free(Buff);
X
X	for (i = 0; i < Popsize; i++)
X	{
X		Old[i].Gene = malloc((unsigned) Bytes);
X		New[i].Gene = malloc((unsigned) Bytes);
X	}
X
X	/* used to compute moving value for Worst */
X	if (Windowsize > 0)
X		Window = (double *) calloc((unsigned) Windowsize, sizeof(double));
X
X	/* used to save DPE history */
X	if (GAgenes) DPEhist = (double *) calloc(2*GAgenes, sizeof(double));
X
X	/* used to re-initialize DPEscale and DPEbasis for each run */
X	if (Totalexperiments > 1)
X	{
X		Scale = (double *) calloc(GAgenes, sizeof(double));
X		Basis = (double *) calloc(GAgenes, sizeof(double));
X		for (i = 0; i < GAgenes; i++)
X		{
X			Scale[i] = GAfact[i];
X			Basis[i] = GAbase[i];
X		}
X	}
X
X	/* used to save best structures */
X	if (Savesize) Bestset = (BESTSTRUCT *)
X		calloc((unsigned) Savesize, sizeof(BESTSTRUCT));
X	Phenesize = 8*GAgenes + Length + 85;
X
X	/* the following request avoids excessive swapping  */
X	/* in the following loop                            */
X	Buff = malloc((unsigned) Savesize*(Bytes+Phenesize+8));
X	free(Buff);
X
X	for (i = 0; i < Savesize; i++)
X	{
X		Bestset[i].Gene = malloc((unsigned) Bytes);
X		Bestset[i].Phene = malloc((unsigned) Phenesize);
X		Bestset[i].Phene++;
X	}
X	Phenesize -= 2; 	/* room for first & last char */
X
X	/* buffer for accessing alleles */
X	Buff = malloc((unsigned) Length);
X
X	/* activate the Options */
X	for (i = 0; Options[i] != '\0'; i++) Setflag(Options[i]);
X
X	/* echo Input params */
X	if (Traceflag) printf(FORMAT, OUT_VARS);
X
X	/* enable setting of Logflag from command line (used in "ga") */
X	if (argc >= 3) if (*argv[2] == 'l') Logflag = 1;
X
X	/* scratch the output file (unless this is a restart) */
X	if (!Restartflag)
X	{
X		if ((fp = fopen(Outfile, "w")) == NULL)
X		{
X			sprintf(msg, "Input: can't open %s", Outfile);
X			Error(msg);
X		}
X		fclose(fp);
X		if (DPEfreq) if ((fp = fopen(DPEfile, "w")) == NULL)
X		{
X			sprintf(msg, "Input: can't open %s", DPEfile);
X			Error(msg);
X		}
X		fclose(fp);
X	}
X
X	/* log this activation */
X	if (Logflag)
X	{
X		if ((fp = fopen(Logfile, "a")) == NULL)
X		{
X			sprintf(msg,"Input: can't open %s", Logfile);
X			Error(msg);
X		}
X		fprintf(fp, "%s ", argv[0]);
X		if (Restartflag) fprintf(fp, "re");
X		time(&clock);
X		fprintf(fp, "started  %s", ctime(&clock));
X		fclose(fp);
X	}
X
#ifndef NOSIGNAL
X	{
X		extern void (*Catcher)();
X
X		/* set custom signal catcher */
X		signal(SIGINT,  Catcher);
X		signal(SIGTERM, Catcher);
X	}
#endif  /* !NOSIGNAL */
X
}
X
/** end of file **/
X
SHAR_EOF
chmod 0444 src/input.c ||
echo 'restore of src/input.c failed'
Wc_c="`wc -c < 'src/input.c'`"
test 5809 -eq "$Wc_c" ||
	echo 'src/input.c: original size 5809, current size' "$Wc_c"
fi
# ============= src/inset.c ==============
if test -f 'src/inset.c' -a X"$1" != X"-c"; then
	echo 'x - skipping src/inset.c (File already exists)'
else
echo 'x - extracting src/inset.c (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'src/inset.c' &&
/*************************************************************/
/*                                                           */
/*  Copyright (c) 1986                                       */
/*  John J. Grefenstette                                     */
/*  Navy Center for Applied Research in AI                   */
/*  Naval Research Laboratory                                */
/*                                                           */
/*  Permission is hereby granted to copy all or any part of  */
/*  this program for free distribution.   The author's name  */
/*  and this copyright notice must be included in any copy.  */
/*                                                           */
/*************************************************************/
X
/*
X *  file:	inset.c (formerly setup.c)
X *
X *  author:	John J. Grefenstette
X *
X *  created:	1983
X *
X *  purpose:	create an input file for GAucsd.
X *		Default values for input parameters are provided
X *		when the user gives a null response to a prompt.
X *
X *  modified:	feb. 1986
X *              08/24/89: get input parameters from global.h - Nici.
X */
X
#define UTILITY
X
#include "global.h"
#include "format.h"
X
#define  LIMIT 30	/* max. length of user input field */
#define  DIGITS 2	/* significant digits for rounding */
X
#define SETPAR(Prompt, Format, Var) \
X	{	printf(Prompt); printf(" ["); printf(Format, Var); \
X		printf("]: "); fflush(stdout); \
X		sscanf(gets(s), Format, &Var); }
X
#define ROUND(X) \
X	if ((X) > 1e-30) \
X	{	double _dIgS; _dIgS = floor(DIGITS-log((double)X)/log(10.0)); \
X		_dIgS = exp(_dIgS*log(10.0)); \
X		X = ((long)(_dIgS*X + 0.5))/_dIgS; }
X
main()
{
X	extern double Rand();
X	char s[LIMIT];
X	char base[LIMIT];
X	char ga[LIMIT+3];
X	char infile[LIMIT+3];
X	char cmd[128];
X	char eos = '\0';
X	char *garg[MAXGARG];
X	FILE *fp, *fopen();
X	int preset = 0;
X	int status;
X	double tmp;
X
X	printf("\nEvaluation File Name [f1]: "); 
X	fgetstr(ga, LIMIT);
X	if (strlen(ga) == 0) strcpy(ga, "f1");
#ifndef NOSTAT
X	if (!stat("Makefile", NULL) || !stat("makefile", NULL))
X		sprintf(cmd, "make GAeval=%s", ga);
X	else
#endif
X	sprintf(cmd, "make -f %s GAeval=%s", MF, ga);
X	status = system(cmd);
X	if (status)
X	{
X		printf("Setup aborted.\n\n");
X		exit(1);
X	}
X
X	sprintf(base, "ga%06d.tmp", ((int) time(0))%1000000);
X	sprintf(cmd, "awk \"/\\/\\*[ \t][ \t]*GAlength[ \t][ \t]*[0-9][0-9]*[ \t]/ {print \\$3}\" %s_ga.c > %s", ga, base);
X	printf("Checking for GAlength entry in %s_ga.c\n", ga);
X
X	if (system(cmd))
X	{
X		printf("Warning: unable to locate GAlength entry;");
X		printf(" error in command\n    %s\n", cmd);
X	}
X	else
X	{
X		fp = (FILE *) fopen(base, "r");
X
X		if (fgets(cmd, 80, fp))
X		{
X			if (!sscanf(cmd, "%d", &Length))
X				printf("Warning: ignoring bad GAlength entry\n    %s\n", cmd);
X			else if (fscanf(fp, "%*s") != EOF)
X				printf("Warning: ignoring extraneous GAlength entries.\n");
X		}
X		else printf("Warning: no GAlength entry found.\n");
X
X		fclose(fp);
X		unlink(base);
X	}
X
X	printf("\nName of Experiment [%s]: ", ga);
X	fgetstr(base, LIMIT);
X	if (strlen(base) == 0) strcpy(base, ga);
X	name_file(infile, "in", base);   
X
X	for (status = 0; status < MAXGARG; status++)
X		garg[status] = &eos;
X	if ((fp = fopen(infile, "r")) != NULL)
X	{
X		preset = fscanf(fp, FORMAT, IN_VARS);
X		if (preset == N_FORM)
X		{
X			preset += fscanf(fp, FORM_2, IN_2);
X			if (preset < N_FORM) preset = N_FORM;
X		}
X		else if (preset < 0) preset = 0;
X
X		status = 0;
X		if (fgets(cmd, 100, fp))
X			if (!strcmp(cmd, GARGSEP))
X				while (fgets(cmd, 100, fp))
X				{
X					garg[status] = (char *) malloc(strlen(cmd));
X					cmd[strlen(cmd) - 1] = '\0';
X					strcpy(garg[status++], cmd);
X				}
X		fclose(fp);
X		preset += status;
X		printf("Using %d defaults from %s\n\n", preset, infile);
X	}
X	else printf("Creating file %s\n\n", infile);
X
X	while ((fp = fopen(infile, "a")) == NULL)
X	{
X		printf("Can't open %s for writing\n", infile);
X		printf("Please provide alternative name: ");
X		*base = '\0';
X		fgetstr(base, LIMIT);
X		if (strlen(base) == 0)
X		{
X			printf("Setup aborted.\n\n");
X			exit(1);
X		}
X		name_file(infile, "in", base);   
X		printf("\n");
X	}
X	fclose(fp);	/* this was just a test */
X
X	SETPAR("Genome Length", "%d", Length);
X
X	if (preset < 3)
X	{
X	/* Default shatters schemata in sqrt(Length)
X	 * generations at the given crossover rate.
X	 */
X		tmp = pow((double)2.0, sqrt((double)Length)/(2.0*C_rate));
X		if (tmp > 32499.0) Popsize = 32500;
X		else
X		{
X			Popsize = (int) tmp;
X			if (Popsize < 3) Popsize = 3;
X			else ROUND(Popsize);
X		}
X	}
X	SETPAR("Population Size", "%d", Popsize);
X
X	if (preset < 2)
X	{
X		/* Default is square of revised shatter time.
X		 */
X        tmp = Length / (2.8854*C_rate*log((double)Popsize));
X		Totaltrials = (int) Popsize*tmp*tmp;
X		ROUND(Totaltrials);
X	}
X	SETPAR("Trials per Run", "%ld", Totaltrials);
X
X	SETPAR("Number of Runs", "%d", Totalexperiments);
X
X	if (preset < 5)
X	{
X    /* Default shatters schemata in square root of
X     * running time at the given population size.
X     */
X        C_rate = (Length / sqrt(Totaltrials/(double)Popsize))
X               / (2.8854*log((double)Popsize));
X		ROUND(C_rate);
X	}
X	SETPAR("Crossover Rate (per individual)", "%lf", C_rate);
X
X	if (preset < 6)
X	{
X		/* Default uses empirical relationship found by
X		 * Schaffer et al. in ICGA-3; no theoretic support
X		 * but seems to work well in practice.
X		 */
X		M_rate = 0.5*sqrt(2.72/Length)/Popsize;
X		ROUND(M_rate);
X	}
X	SETPAR("Mutation Rate", "%lf", M_rate);
X
X	SETPAR("Generation Gap", "%lf", Gapsize);
X
X	SETPAR("Windowsize (hit return for sigma scaling)", "%d", Windowsize);
X	if (Windowsize < 0)
X		SETPAR("Sigma Scaling Factor", "%lf", Sigfact);
X
X	SETPAR("DPE Time Constant", "%d", DPEfreq);
X
X	if (preset < 18)
X	{
X		/* Default based on DPE analysis by Schraudolph
X		 */
X		tmp = (1.0 - FIT_RATIO) + M_rate*(FIT_RATIO + 1.0);
X		Convlev = tmp - sqrt(tmp*tmp - M_rate*(4.0 - 4.0*FIT_RATIO));
X		Convlev /= 2.0 - 2.0*FIT_RATIO;
X		Convlev = 1.0 - Convlev;
X		ROUND(Convlev);
X	}
X	SETPAR("Convergence Threshold", "%lf", Convlev);
X
X	if (preset < 17) Maxconv = Length;
X	SETPAR("Max Alleles to Converge", "%d", Maxconv);
X
X	SETPAR("Maximum Bias", "%lf", Maxbias);
X	SETPAR("Max Gens w/o Evaluation", "%d", Maxspin);
X
X	if (preset < 9)
X	{
X		Interval = exp(log((double) Totaltrials)/3.0) + 0.5;
X		Interval *= Interval;
X		ROUND(Interval);
X	}
X	SETPAR("Report Interval", "%d", Interval);
X
X	if (preset < 10)
X		Savesize = (int)((1.0 - Convlev)*Popsize);
X	SETPAR("Structures Saved", "%d", Savesize);
X
X	if (preset < 12)
X	{
X		Dump_freq = (Interval*Totalexperiments)/Popsize;
X		ROUND(Dump_freq);
X	}
X	SETPAR("Dump Interval", "%d", Dump_freq);
X	if (Dump_freq)
X		SETPAR("Dumps Saved", "%d", Num_dumps);
X
X	printf("Options [%s]: ", Options);
X	fflush(stdout);
X	sscanf(gets(s), "%s", Options);
X
X	if (preset < 15)
X	{
X		Seed = (unsigned int) time(0);
X		Srand(&Seed);
X	}
X	SETPAR("Random Seed", "%u", Seed);
X
X	printf("\nWriting new settings to %s\n", infile);
X	fp = fopen(infile, "w");
X	fprintf(fp, FORMAT, OUT_VARS);
X	fprintf(fp, FORM_2, OUT_2);
X
X	printf("\nApplication-specific Arguments:\n");
X	for (status = 0; status < MAXGARG; status++)
X	{
X		printf("%2d [%s]: ", status, garg[status]);
X		if (!status) fprintf(fp, GARGSEP);
X		if (!*gets(s))
X		{
X			if (!*garg[status]) break;
X			else fprintf(fp, "%s\n", garg[status]);
X		}
X		else fprintf(fp, "%s\n", s);
X	}
X	fclose(fp);
X
#ifdef NOGAGX
X	printf("\nRun experiment with: %s %s\n", ga, base);
#else
X	printf("\nqueue []: ");
X	fgetstr(s, LIMIT);
X	if (strlen(s) == 0)
X	{
X		sprintf(cmd, "(ga %s %s; echo ) &", ga, base);
X		system(cmd);
X		printf("ga command executed\n");
X	}
X	else
X	{
X		if ((fp = fopen(s, "a")) == NULL)
X		{
X			printf("Error: can't open %s\n", s);
X			printf("Setup aborted.\n\n");
X			exit(1);
X		}
X		else
X		{
X			fprintf(fp, "        ga %s %s &\n", ga, base);
X			fclose(fp);
X		}
X		printf("ga command queued on %s\n", s);
X	}
#endif   /* NOGAGX */
X	printf("Setup done.\n\n");
}
X
X
X
fgetstr(s, n) 
char *s;
int n;
{
X	register int c;
X	while (--n > 0 && (c = getchar()) != EOF)
X		if ( c != '\n' )
X			*s++ = c;
X		else
X			break;
X	*s = '\0';
X	return;
}
X
/*** end of file ***/
SHAR_EOF
chmod 0444 src/inset.c ||
echo 'restore of src/inset.c failed'
Wc_c="`wc -c < 'src/inset.c'`"
test 8052 -eq "$Wc_c" ||
	echo 'src/inset.c: original size 8052, current size' "$Wc_c"
fi
# ============= src/main.c ==============
if test -f 'src/main.c' -a X"$1" != X"-c"; then
	echo 'x - skipping src/main.c (File already exists)'
else
echo 'x - extracting src/main.c (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'src/main.c' &&
/*************************************************************/
/*                                                           */
/*  Copyright (c) 1986                                       */
/*  John J. Grefenstette                                     */
/*  Navy Center for Applied Research in AI                   */
/*  Naval Research Laboratory                                */
/*                                                           */
/*  Permission is hereby granted to copy all or any part of  */
/*  this program for free distribution.   The author's name  */
/*  and this copyright notice must be included in any copy.  */
/*                                                           */
/*************************************************************/
X
/*
X *  file:	main.c
X *
X *  author:	John J. Grefenstette
X *
X *  created:	1981
X *
X *  purpose:	main program for genesis.
X *
X *  modified:	28 mar 86
X */
X
#include "global.h"
X
extern void Input();
extern void Generate();
X
X
main(argc,argv)
int argc;
char *argv[];
{
X	FILE *fp, *fopen();
X	long clock;
X	long time();
X	char *ctime();
X
X	/* see input.c for the use of command line args */
X	Input(argc,argv);
X
X	do		/* one run */
X	{
X		if (Traceflag) 
X		{
X			if (Restartflag) printf("Restart\n");
X			else printf("Run #%d\n", Experiment); 
X		}
X
X		do	/* see generate.c for main GA loop */
X		    {
X			Generate();
X		}  
X		while (!Doneflag);
X
X		if (Traceflag)
X			printf("Online %e   Offline %e    Best %e\n",
X			Online, Offline, Best);
X
X		/* accumulate performance measurements */
X		Totonline += Online;
X		Totoffline += Offline;
X		Totbest += Best;
X
X		/* get ready for next run */
X		Experiment++;
X		Gen = 0;
X
X	} 
X	while (Experiment <= Totalexperiments);
X
X	/* compute and print final performance measures */
X
X	Totonline /= Totalexperiments;
X	Totoffline /= Totalexperiments;
X	Totbest /= Totalexperiments;
X	if (Onlnflag)
X		printf("%e\n", Totonline);
X	if (Offlnflag)
X		printf("%e\n", Totoffline);
X	if (Bestflag)
X		printf("%e\n", Totbest);
X	if (Logflag)
X	{
X		fp = fopen(Logfile, "a");
X		fprintf(fp, "Online %e    ", Totonline);
X		fprintf(fp, "Offline %e   ", Totoffline);
X		fprintf(fp, "Best %e\n", Totbest);
X		time(&clock);
X		fprintf(fp, "%s\n", ctime(&clock));
X		fclose(fp);
X	}
}
X
/** end of file **/
SHAR_EOF
chmod 0444 src/main.c ||
echo 'restore of src/main.c failed'
Wc_c="`wc -c < 'src/main.c'`"
test 2247 -eq "$Wc_c" ||
	echo 'src/main.c: original size 2247, current size' "$Wc_c"
fi
# ============= src/measure.c ==============
if test -f 'src/measure.c' -a X"$1" != X"-c"; then
	echo 'x - skipping src/measure.c (File already exists)'
else
echo 'x - extracting src/measure.c (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'src/measure.c' &&
/*************************************************************/
/*                                                           */
/*  Copyright (c) 1986                                       */
/*  John J. Grefenstette                                     */
/*  Navy Center for Applied Research in AI                   */
/*  Naval Research Laboratory                                */
/*                                                           */
/*  Permission is hereby granted to copy all or any part of  */
/*  this program for free distribution.   The author's name  */
/*  and this copyright notice must be included in any copy.  */
/*                                                           */
/*************************************************************/
X
/*
X *  file:	measure.c
X *
X *  author:	John J. Grefenstette
X *
X *  created:	1981
X *
X *  purpose:	calculate performance measures and append them
X *		to the output file.
X *
X *  modified:	26 mar 86
X *
X *		2 dec 86: call Converge() right before output,
X *		and fake remainder of output if terminating
X */
X
#define   EXTERN
#include "global.h"
X
extern void Converge();
extern void Schema();
X
Measure()
{
X	double New_worst();
X	extern double sqrt();
X	FILE *fp, *f2, *fopen();
X	register int i;
X	register int w;
X	register double performance;
X	register double sigma;
X
X	Trace("Measure entered");
X	for (i = 0; i < Popsize; i++)
X	{
X		/* update current statistics */
X		performance = New[i].Perf;
X		if (i > 0)
X		{
X			Ave_current_perf += performance;
X			sigma += performance*performance;
X			if (performance < Best_current_perf)
X			{
X				Best_current_perf = performance;
X				Best_guy = i;
X			}
X			if (performance > Worst_current_perf)
X				Worst_current_perf = performance;
X		}
X		else
X		{
X			Ave_current_perf = performance;
X			sigma = performance*performance;
X			Best_current_perf = performance;
X			Best_guy = 0;
X			Worst_current_perf = performance;
X		}
X
X	}
X	Ave_current_perf /= Popsize;
X
X	/* update Worst */
X	if (Windowsize < 0) 	/* sigma scaling */
X	{
X		sigma -= Popsize*Ave_current_perf*Ave_current_perf;
X		sigma /= Popsize - 1;
X
X		/* hack to fix numerical problems */
X		if (sigma < 0.0) sigma = 0.0;
X
X		sigma = sqrt(sigma);
X		Worst = New_worst(Ave_current_perf + Sigfact*sigma);
X	}
X	else if (Windowsize > 0) 	/* window scaling */
X	{
X		/* Worst = worst in last (Windowsize) generations */
X		w = Gen % Windowsize;
X		Window[w] = New_worst(Worst_current_perf);
X		Worst = Window[0];
X		for (i = 1; i < Windowsize; i++)
X			if (Window[i] > Worst) Worst = Window[i];
X	}
X	else if (Worst < Worst_current_perf)
X		Worst = New_worst(Worst_current_perf);
X
X	/* update overall performance measures */
X	Online = Onsum / Trials;
X	Offline = Offsum / Trials;
X
X	if (Traceflag)
X	{
X		printf("     Gen %d     Trials %ld\n",Gen,Trials);
X		if (Onlnflag) printf("     Online %e\n", Online);
X		if (Offlnflag) printf("     Offline %e\n", Offline);
X	}
X
X	if (Interval && Collectflag)
X	{
X		if (Trials >= Plateau)
X		{
X			Doneflag = (Plateau >= Totaltrials);
X			/* add measures to the output file */
X			Converge();
X			fp = fopen(Outfile, "a");
X			fprintf(fp, OUT_F2, OUT_V2);
X
X			if (Bias >= Maxbias || Conv >= Maxconv || Spin >= Maxspin)
X			{
X				long temp = Plateau;
X
X				if (Logflag)
X				{
X					f2 = fopen(Logfile, "a");
X					fprintf(f2, "Experiment %1d: ", Experiment);
X					if (Bias >= Maxbias)
X						fprintf(f2, "BIASED (%0.2lf) ", Maxbias);
X					if (Spin >= Maxspin)
X						fprintf(f2, "SPINNING (%d) ", Maxspin);
X					if (Conv >= Maxconv)
X						fprintf(f2, "CONVERGED (%d) ", Maxconv);
X					fprintf(f2, "at Gen %1d, ", Gen);
X					fprintf(f2, "after %1ld Trials\n", Trials);
X					fclose(f2);
X				}
X				while (temp < Totaltrials)
X				{
X					temp += Interval;
X					Gen += (Interval/Popsize) ? (Interval/Popsize) : 1;
X					fprintf(fp, OUT_F2, OUT_V2);
X				}
X				Trials = temp;
X				Doneflag = 1;
X			}
X
X			fclose(fp);
X			Plateau = (Trials/Interval)*Interval + Interval;
X		}
X	}
X	else Doneflag = (Trials >= Totaltrials);
X
X	if (Schemflag) Schema();
X
X	Trace("Measure completed");
}
X
#define epsilon 1.0e-4
X
double New_worst(bad)
double bad; 	/* correct for numerical instabilities */
{
X	if (bad == 0.0) return(epsilon);
X
X	if (bad > 0.0) return(bad*(1.0 + epsilon));
X
X	return(bad*(1.0 - epsilon));
}
X
/** end of file **/
X
SHAR_EOF
chmod 0444 src/measure.c ||
echo 'restore of src/measure.c failed'
Wc_c="`wc -c < 'src/measure.c'`"
test 4237 -eq "$Wc_c" ||
	echo 'src/measure.c: original size 4237, current size' "$Wc_c"
fi
# ============= src/mutate.c ==============
if test -f 'src/mutate.c' -a X"$1" != X"-c"; then
	echo 'x - skipping src/mutate.c (File already exists)'
else
echo 'x - extracting src/mutate.c (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'src/mutate.c' &&
/*************************************************************/
/*                                                           */
/*  Copyright (c) 1986                                       */
/*  John J. Grefenstette                                     */
/*  Navy Center for Applied Research in AI                   */
/*  Naval Research Laboratory                                */
/*                                                           */
/*  Permission is hereby granted to copy all or any part of  */
/*  this program for free distribution.   The author's name  */
/*  and this copyright notice must be included in any copy.  */
/*                                                           */
/*************************************************************/
X
/*
X *  file:	mutate.c
X *
X *  author:	John J. Grefenstette
X *
X *  created:	1981
X *
X *  purpose:	Perform mutation on the current population.
X *
X *	The global variable Mu_next indicates the position of
X *	next mutation, treating the entire population as a linear
X *	array of positions.  
X *
X *  modified:	7 feb 98
X */
X
#define   EXTERN
#include "global.h"
X
X
Mutate()
{
X	static long bits;	/* number of bits per pop */
X	register int i;		/* index of the Mutated structure */
X	register int j;		/* position within the structure */
X	register int k;		/* position within Mutated byte */
X	register double r;	/* current random number */
X	static int firstflag = 1;
X
X	Trace("Mutate entered");
X
X	if (firstflag)
X	  {
X	    bits = Popsize*Length;
X	    firstflag = 0;
X	  }
X
X	if (M_rate > 0.0)
X	{
X		while (Mu_next<bits)
X		{
X			i = Mu_next/ Length;	/* Mutated structure */
X			j = Mu_next % Length;	/* Mutated position */
X			k = j % CHAR_BIT;   	/* Mutated bit  */
X			j /= CHAR_BIT;      	/* Mutated byte */
X
X			MUTATION(New[i].Gene[j], Bit[k]);
X			New[i].Needs_evaluation = 1;
X
X			/* update next mutation location */
X			if (M_rate < 1.0)
X			{
X				while ((r = Rand()) == 0.0);
X				Mu_next += ceil (log(r) / log(1.0 - M_rate));
X			}
X			else
X				Mu_next += 1L;
X		}
X
X		/* adjust Mu_next for next Generation */
X		Mu_next -= bits;
X
X	}
X
X	Trace("Mutate completed");
}
X
X
/** end of file **/
X
SHAR_EOF
chmod 0444 src/mutate.c ||
echo 'restore of src/mutate.c failed'
Wc_c="`wc -c < 'src/mutate.c'`"
test 2130 -eq "$Wc_c" ||
	echo 'src/mutate.c: original size 2130, current size' "$Wc_c"
fi
# ============= src/random.c ==============
if test -f 'src/random.c' -a X"$1" != X"-c"; then
	echo 'x - skipping src/random.c (File already exists)'
else
echo 'x - extracting src/random.c (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'src/random.c' &&
X
/*
X * Copyright (c) 1987 Regents of the University of California.
X * All rights reserved.
X *
X * Redistribution and use in source and binary forms are permitted
X * provided that the above copyright notice and this paragraph are
X * duplicated in all such forms and that any documentation,
X * advertising materials, and other materials related to such
X * distribution and use acknowledge that the software was developed
X * by the University of California, Berkeley.  The name of the
X * University may not be used to endorse or promote products derived
X * from this software without specific prior written permission.
X * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
X * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
X * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
X */
X
#include "define.h"
X
long Rstate[RAND_DEG] = {   0x9a319039,
X	0x32d9c024, 0x9b663182, 0x5da1f342, 0xde3b81e0, 0xdf0a6fb5,
X	0xf103bc02, 0x48f340fb, 0x7449e56b, 0xbeb1dbb0, 0xab5c5918,
X	0x946554fd, 0x8c2e680f, 0xeb3d799f, 0xb11ee0b7, 0x2d436b86,
X	0xda672e2a, 0x1588ca88, 0xe369735d, 0x904f35f7, 0xd7158fd6,
X	0x6fa6f051, 0x616e6b96, 0xac94efdc, 0x36413f93, 0xc622c298,
X	0xf5a42ab8, 0x8a88d77b, 0xf5ad9d0e, 0x8999220b, 0x27fb47b9
};
X
static long *fptr = &Rstate[3];
static long *rptr = &Rstate[0];
static long *end_ptr = &Rstate[RAND_DEG];
X
int Getptr()
{
X	return(fptr - &Rstate[0]);
}
X
Setptr(p) int p;
{
X	fptr = &Rstate[p];
X	rptr = fptr - 3;
X	if (rptr < &Rstate[0]) rptr += RAND_DEG;
}
X
Srand(x) unsigned int *x;
{
X	register int i;
X	double Rand();
X
X	Rstate[0] = (long) *x;
X	for (i = 1; i < RAND_DEG; i++)
X		Rstate[i] = 1103515245 * Rstate[i - 1] + 12345;
X	*x = (unsigned int) (1103515245 * Rstate[RAND_DEG - 1] + 12345);
X
X	fptr = &Rstate[3];
X	rptr = &Rstate[0];
X
X	for (i = 0; i < 10*RAND_DEG; i++) (void) Rand();
}
X
double Rand()
{
X	long i;
X	
X	*fptr += *rptr;
X	i = (*fptr >> 1) & LONG_MAX;
X	if (++fptr >= end_ptr)
X	{
X		fptr = &Rstate[0];
X		++rptr;
X	}
X	else
X		if (++rptr >= end_ptr) rptr = &Rstate[0];
X	return(i/(LONG_MAX + 1.0));
}
X
SHAR_EOF
chmod 0444 src/random.c ||
echo 'restore of src/random.c failed'
Wc_c="`wc -c < 'src/random.c'`"
test 2054 -eq "$Wc_c" ||
	echo 'src/random.c: original size 2054, current size' "$Wc_c"
fi
# ============= src/report.c ==============
if test -f 'src/report.c' -a X"$1" != X"-c"; then
	echo 'x - skipping src/report.c (File already exists)'
else
echo 'x - extracting src/report.c (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'src/report.c' &&
/*************************************************************/
/*                                                           */
/*  Copyright (c) 1986                                       */
/*  John J. Grefenstette                                     */
/*  Navy Center for Applied Research in AI                   */
/*  Naval Research Laboratory                                */
/*                                                           */
/*  Permission is hereby granted to copy all or any part of  */
/*  this program for free distribution.   The author's name  */
/*  and this copyright notice must be included in any copy.  */
/*                                                           */
/*************************************************************/
X
/*
X *  file:	report.c
X *
X *  author:	John J. Grefenstette
X *
X *  created:	sep 1981
X *
X *  purpose:	generate a report summarizing the mean
X *		and variance of a number of performance
X *		measures of a GA run.
X *
X *  modified:	5 aug 86
X */
X
#define   UTILITY
#include "global.h"
X
extern void Error();
X
#define COLUMNS 9
X
double *avg, *a, *var, *v;
double line[COLUMNS];
X
X
main(argc, argv)
int argc;
char *argv[];
{
X	register int row, col, i;
X	double oldgens;		/* previous Generation count */
X	double tmp;
X	int cutoff = 0;		/* was data truncated? see below */
X	int droplast = 0;	/* was last run incomplete? */
X	char Outfile[40];	/* output file produced by Genetic alg */
X	char Infile[40];	/* Input file for Genetic alg. */
X	char msg[80];   	/* message string */
X	char *arg1 = 0;  	/* points to file suffix, if any */
X	int lines;		/* number of lines in Report */
X	int eof;		/* true when Outfile is exhausted */
X	int expn;		/* number of runs */
X
X	FILE *fp, *fopen();
X
X	/* set up the file names */
X	if (argc >= 2) arg1 = argv[1];
X	name_file(Infile,  "in",  arg1);   
X	name_file(Outfile, "out", arg1);   
X
X	/* read the parameters from the Infile */
X	if ((fp = fopen(Infile, "r")) == NULL)
X	{
X		sprintf(msg, "Report: can't open %s", Infile);
X		Error(msg);
X	}
X	fscanf(fp, FORMAT, IN_VARS);
X	printf(FORMAT, OUT_VARS);
X	fscanf(fp, FORM_2, IN_2);
X	printf(FORM_2, OUT_2);
X	while (fgets(msg, 80, fp)) fputs(msg, stdout);
X	fclose(fp);
X
X	/* For the purpose of computing the means and the variances, */
X	/* the number of lines is taken to be the minimum number of */
X	/* lines produced by any run.  If any data is        */
X	/* discarded, the flag cutoff is set, so that a warning     */
X	/* may be printed.                                          */
X
X	row = Totaltrials/Interval + 2;
X	a = avg = (double *) calloc(row, COLUMNS * sizeof(double));
X	v = var = (double *) calloc(row, COLUMNS * sizeof(double));
X
X	/* get the Outfile */
X	if ((fp = fopen(Outfile, "r")) == NULL)
X	{
X		sprintf(msg, "Report: can't open %s", Outfile);
X		Error(msg);
X	}
X
X	lines = 0;
X	oldgens = -1.0;
X
X	/* read in a line */
X	if (fscanf(fp, LINE_FIN, LINE_VIN) == EOF)
X	{
X		sprintf(msg, "Report: unexpected EOF on %s", Outfile);
X		Error(msg);
X	}
X
X	eof = 0;
X	for (expn = 0; (!eof); expn++)
X	{
X		row = 0;
X
X		/* oldgens > line[0] indicates the start of a new run. */
X		while ( !(eof) && (oldgens <= line[0]))
X		{
X			/* if oldgens = line[0], then this line repeats the */
X			/* previous line (this sometimes happens after Restarts) */
X			/* The current line is ignored in this case.        */
X			if (oldgens < line[0])
X			{
X				/* record the values */
X				for (col = 0; col < COLUMNS; col++)
X				{
X					*a++ += line[col];
X					*v++ += line[col] * line[col];
X				}
X				row++;
X			}
X			oldgens = line[0];
X
X			/* read in a line */
X			eof = (fscanf(fp, LINE_FIN, LINE_VIN) == EOF);
X		}
X
X		oldgens = -1.0;
X		if (expn)
X		{
X			if (row > lines) cutoff = 1;
X			else if (row < lines)
X			{
X				lines = row;
X				if (eof) droplast = 1;
X				else cutoff = 1;
X			}
X		}
X		else lines = row;
X
X		a = avg;
X		v = var;
X	}
X	fclose(fp);
X
X	/* compute the mean and variance */
X	for (row = 0; row < lines; row++)
X	{
X		for (col = 0; col < COLUMNS; col++)
X		{
X			if (expn > 1)
X			{
X				tmp = *a * *a;
X				tmp /= expn;
X				*v -= tmp;
X				*v++ /= expn - 1;
X			}
X			*a++ /= expn;
X		}
X	}
X
X	/* print the mean values */
X	printf("\nMEAN\n");
X	printf("Gens Trials Lost ");
X	printf("Conv  Bias     Online      ");
X	printf("Offline       Best        Average\n");
X	a = avg;
X	for (i = 0; i < lines; i++)
X	{
X		printf("%4.0lf ",    *a++);
X		printf("%6.0lf ",    *a++);
X		printf("%3.0lf ",    *a++);
X		printf("%4.0lf  ",   *a++);
X		printf("%5.3lf ",    *a++);
X		printf("% 11.5le ",  *a++);
X		printf("% 11.5le ",  *a++);
X		printf("% 11.5le ",  *a++);
X		printf("% 11.5le\n", *a++);
X	}
X
X	/* print the variance */
X	if (expn > 1)
X	{
X		printf("\nVARIANCE\n");
X		printf("Gens Trials Lost ");
X		printf("Conv  Bias     Online      ");
X		printf("Offline       Best        Average\n");
X		v = var;
X		for (i = 0; i < lines; i++)
X		{
X			printf("%4d ",  (int) *v++);
X			printf("%6d ",  (int) *v++);
X			printf("%3d ",  (int) *v++);
X			printf("%4d  ", (int) *v++);
X			printf("%5.3lf ",     *v++);
X			printf("% 11.5le ",   *v++);
X			printf("% 11.5le ",   *v++);
X			printf("% 11.5le ",   *v++);
X			printf("% 11.5le\n",  *v++);
X		}
X	}
X
X	/* print any warnings */
X	if (expn != Totalexperiments)
X	{
X		printf("\nNOTE: found data for %d runs, ", expn);
X		printf("not %d as specified above.", Totalexperiments);
X	}
X	if (droplast)
X	{
X		printf("\nNOTE: incomplete last run caused ");
X		printf("truncation of data; consider removing\n");
X		printf("      the offending lines from file ");
X		printf("'%s' and re-running report.", Outfile);
X	}
X	if (cutoff)
X	{
X		printf("\nWARNING: ignored extraneous data reported ");
X		printf("by some runs;\n         please check ");
X		printf("validity of data file '%s'.", Outfile);
X	}
X	printf("\n");
}
X
/*** end of file ***/
X
SHAR_EOF
chmod 0444 src/report.c ||
echo 'restore of src/report.c failed'
Wc_c="`wc -c < 'src/report.c'`"
test 5704 -eq "$Wc_c" ||
	echo 'src/report.c: original size 5704, current size' "$Wc_c"
fi
# ============= src/restart.c ==============
if test -f 'src/restart.c' -a X"$1" != X"-c"; then
	echo 'x - skipping src/restart.c (File already exists)'
else
echo 'x - extracting src/restart.c (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'src/restart.c' &&
/*************************************************************/
/*                                                           */
/*  Copyright (c) 1986                                       */
/*  John J. Grefenstette                                     */
/*  Navy Center for Applied Research in AI                   */
/*  Naval Research Laboratory                                */
/*                                                           */
/*  Permission is hereby granted to copy all or any part of  */
/*  this program for free distribution.   The author's name  */
/*  and this copyright notice must be included in any copy.  */
/*                                                           */
/*************************************************************/
X
/*
X *  file:	restart.c
X *
X *  author:	John J. Grefenstette
X *
X *  created:	1982
X *
X *  purpose:	restart an interupted GA run.
X *
X *  modified:	13 feb 86
X *
X */
X
#define   EXTERN
#include "global.h"
X
extern void Readbest();
extern void Setptr();
extern long Rstate[];
X
X
Restart()
{
X	FILE *fp, *fopen();
X	int i,j;
X	int k;
X	char msg[40];
X
X	Trace("Restart entered");
X
X	fp = fopen(Ckptfile, "r");
X	if (fp == NULL) 
X	{
X		sprintf(msg, "Restart: can't open %s", Ckptfile);
X		Error(msg);
X	}
X
X	if (fscanf(fp, FORM_CKPT, IN_CKPT) < N_CKPT)
X	{
X		sprintf(msg,"Restart: garbled file %s (globals)", Ckptfile);
X		Error(msg);
X	}
X
X	fscanf(fp, " Window ");
X	for (i = 0; i < Windowsize; i++)
X		if (fscanf(fp, " %lf ", &Window[i]) < 1)
X		{
X			sprintf(msg,"Restart: garbled file %s (Window)", Ckptfile);
X			Error(msg);
X		}
X
X	fscanf(fp, " Random State ");
X	for (i = 0; i < RAND_DEG; i++)
X		if (fscanf(fp, " 0x%lx ", &Rstate[i]) < 1)
X		{
X			sprintf(msg,"Restart: garbled file %s (Random State)", Ckptfile);
X			Error(msg);
X		}
X	fscanf(fp, " %d ", &i);
X	Setptr(i);
X
X	fscanf(fp, " DPE State ");
X	for (i = 0; i < GAgenes; i++)
X		if (fscanf(fp, " %lf %lf %lf %lf ",
X			&GAfact[i], &GAbase[i], &DPEhist[2*i], &DPEhist[2*i+1]) < 4)
X			if (DPEfreq)
X			{
X				sprintf(msg,"Restart: garbled file %s (DPE State)", Ckptfile);
X				Error(msg);
X			}
X
X	fscanf(fp, " Population ");
X	for (i = 0; i < Popsize; i++)
X	{
X		for (j = 0; j < Length; j++)
X		{
X			fscanf(fp,"%1d", &k);
X			Buff[j] = k;
X		}
X		Pack(Buff, New[i].Gene);
X		fscanf(fp, " %lf ", &New[i].Perf);
X		if (fscanf(fp, " %d ", &New[i].Needs_evaluation) < 1)
X		{
X			sprintf(msg,"Restart: %s garbled (line %d of Population)",
X				Ckptfile, i + 1);
X			Error(msg);
X		}
X	}
X	fclose(fp);
X
X	if (Totalexperiments > 1)
X		sprintf(Bestfile, "%s.%03d", Minfile, Experiment);
X
X	Readbest();
X	Doneflag = (Trials >= Totaltrials);
X
X	Trace("Restart completed");
}
X
/** end of file **/
X
SHAR_EOF
chmod 0444 src/restart.c ||
echo 'restore of src/restart.c failed'
Wc_c="`wc -c < 'src/restart.c'`"
test 2652 -eq "$Wc_c" ||
	echo 'src/restart.c: original size 2652, current size' "$Wc_c"
fi
# ============= src/schema.c ==============
if test -f 'src/schema.c' -a X"$1" != X"-c"; then
	echo 'x - skipping src/schema.c (File already exists)'
else
echo 'x - extracting src/schema.c (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'src/schema.c' &&
/*************************************************************/
/*                                                           */
/*  Copyright (c) 1986                                       */
/*  John J. Grefenstette                                     */
/*  Navy Center for Applied Research in AI                   */
/*  Naval Research Laboratory                                */
/*                                                           */
/*  Permission is hereby granted to copy all or any part of  */
/*  this program for free distribution.   The author's name  */
/*  and this copyright notice must be included in any copy.  */
/*                                                           */
/*************************************************************/
X
/*
X *  file:	schema.c
X *
X *  author:	John J. Grefenstette
X *
X *  created:	3 feb 86
X *
X *  purpose:	measure the current allocation of trials to a schema
X *		and record the results in Schemafile.
X *
X *  modified:	13 feb 86
X *
X */
X
#define   EXTERN
#include "global.h"
X
extern void Unpack();
X
Schema()
{
X	FILE *fopen();
X	static FILE *fp;
X	static char *S;
X	static int firstflag = 1;
X	static int firstcount = 1;
X	static int lastcount;
X
X	int i, j, ok;
X	int count = 0;
X	double expected = 0.0;
X	double perf = 0.0;
X	double sum = 0.0;
X	char msg[40], tmp;
X
X
X	Trace("Schema entered");
X
X	if (firstflag)
X	{
X	/*  initialize schema S from schemafile */
X		S = malloc((unsigned) Length);
X		if ((fp = fopen(Schemafile, "r")) == NULL)
X		{
X			sprintf(msg, "Schema: can't open %s", Schemafile);
X			Error(msg);
X		}
X		for (i = 0; i < Length; i++)
X		{
X			fscanf(fp, "%c", &tmp);
X			if (tmp == '0')      S[i] = 0;
X			else if (tmp == '1') S[i] = 1;
X			else                 S[i] = '#';
X		}
X		fclose(fp);
X		if ((fp = fopen(Schemafile, "w")) == NULL)
X		{
X			sprintf(msg, "Schema: can't open %s", Schemafile);
X			Error(msg);
X		}
X		for (i = 0; i < Length; i++)
X		{
X			if (S[i] == '#') fprintf(fp, "#");
X			else if (S[i])   fprintf(fp, "1");
X			else             fprintf(fp, "0");
X		}
X		fprintf(fp, "\n");
X		fprintf(fp, " Gen  Count  Incr  Expct  ");
X		fprintf(fp, "Schema Ave    Pop. Ave\n");
X		firstflag = 0;
X	}
X
X	/* record count and expected offspring of S in current pop */
X	for (i = 0; i < Popsize; i++)
X	{
X		Unpack(New[i].Gene, Buff);
X		for (ok = 1, j = 0; ok && (j < Length); j++)
X		{
X			ok = (S[j] == '#') || (S[j] == Buff[j]);
X		}
X		if (New[i].Perf < Worst)
X		{
X			sum += Worst - New[i].Perf;
X			if (ok)
X			{
X				count++;
X				perf += New[i].Perf;
X			}
X		}
X		else if (ok)
X		{
X			count++;
X			perf += New[i].Perf;
X			expected += Worst - New[i].Perf;
X		}
X	}
X
X	if (firstcount && count)
X	{
X		lastcount = count;
X		firstcount = 0;
X	}
X	if (count)
X	{
X		expected = Worst*count - perf - expected;
X		expected *= Popsize;
X		expected /= sum;
X		perf /= count;
X
X		fprintf(fp, "%4d  %4d ", Gen, count);
X		fprintf(fp, " %5.3f ", ((double)count)/lastcount);
X		lastcount = count;
X		fprintf(fp, " %5.3f ", expected);
X		fprintf(fp, " %10.3e ", perf);
X		fprintf(fp, " %10.3e ", Ave_current_perf);
X		fprintf(fp, "\n");
X	}
X
X	Trace("Schema completed");
}
X
/***  end of file ***/
SHAR_EOF
chmod 0444 src/schema.c ||
echo 'restore of src/schema.c failed'
Wc_c="`wc -c < 'src/schema.c'`"
test 3096 -eq "$Wc_c" ||
	echo 'src/schema.c: original size 3096, current size' "$Wc_c"
fi
# ============= src/select.c ==============
if test -f 'src/select.c' -a X"$1" != X"-c"; then
	echo 'x - skipping src/select.c (File already exists)'
else
echo 'x - extracting src/select.c (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'src/select.c' &&
/*************************************************************/
/*                                                           */
/*  Copyright (c) 1986                                       */
/*  John J. Grefenstette                                     */
/*  Navy Center for Applied Research in AI                   */
/*  Naval Research Laboratory                                */
/*                                                           */
/*  Permission is hereby granted to copy all or any part of  */
/*  this program for free distribution.   The author's name  */
/*  and this copyright notice must be included in any copy.  */
/*                                                           */
/*************************************************************/
X
/*
X *  file:	select.c
X *
X *  author:	John J. Grefenstette (algorithm by James E. Baker)
X *
X *  created:	4 august 1987
X *
X *  purpose:	choose a new population via Baker's selection.
X */
X
#define   EXTERN
#include "global.h"
X
X
Select()
{
X	extern Gap();
X
X	static firstflag = 1;
X	static int *sample;	/* pointers to Selected structures	*/
X	double expected;	/* expected number of offspring		*/
X	double factor;		/* normalizer for expected value        */
X	double ptr;		/* determines fractional selection	*/
X	double sum;             /* control fro selection loop           */
X	int i, j, k, temp;	/* loop control				*/
X
X	Trace("Select entered");
X
X	if (firstflag)
X	{
X		sample = (int *) calloc((unsigned) Popsize, sizeof(int));
X		firstflag = 0;
X	}
X
X	/* denominator for selection probabilities */
X	for (sum = i = j = 0; i < Popsize; i++)
X		if (Old[i].Perf < Worst)
X		{
X			sum += Old[i].Perf;
X			j++;
X		}
X
X	factor = Popsize/(Worst*j - sum);
X
X	k = 0;		/* index of next Selected structure */
X	ptr = Rand();   /* spin the wheel one time */
X
X	for (sum = i = 0; i < Popsize; i++)
X	{
X		if (Old[i].Perf < Worst)
X			expected = (Worst - Old[i].Perf) * factor;
X		else expected = 0.0;
X
X		for (sum += expected; sum > ptr; ptr++)
X			sample[k++] = i;
X	}
X	if (k != Popsize) Error("Select: internal scaling error");
X
X	if (Gapsize < 1.0) Gap(sample); 	/* Generation Gap */ 
X	
X
X	/* randomly shuffle pointers to new structures */
X	for (i = 0; i < Popsize; i++)
X	{
X		j = Randint(i, Popsize-1);
X		temp = sample[j];
X		sample[j] = sample[i];
X		sample[i] = temp;
X	}
X
X	/* finally, form the new population */
X	for (i = 0; i < Popsize; i++)
X	{
X		k = sample[i];
X		for (j = 0; j < Bytes; j++)
X			New[i].Gene[j] = Old[k].Gene[j];
X
X		New[i].Perf = Old[k].Perf;
X		New[i].Needs_evaluation = 0;
X	}
X
X	Trace("Select completed");
}
X
X
/*** end of file ***/
X
SHAR_EOF
chmod 0444 src/select.c ||
echo 'restore of src/select.c failed'
Wc_c="`wc -c < 'src/select.c'`"
test 2576 -eq "$Wc_c" ||
	echo 'src/select.c: original size 2576, current size' "$Wc_c"
fi
# ============= src/setflag.c ==============
if test -f 'src/setflag.c' -a X"$1" != X"-c"; then
	echo 'x - skipping src/setflag.c (File already exists)'
else
echo 'x - extracting src/setflag.c (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'src/setflag.c' &&
/*************************************************************/
/*                                                           */
/*  Copyright (c) 1986                                       */
/*  John J. Grefenstette                                     */
/*  Navy Center for Applied Research in AI                   */
/*  Naval Research Laboratory                                */
/*                                                           */
/*  Permission is hereby granted to copy all or any part of  */
/*  this program for free distribution.   The author's name  */
/*  and this copyright notice must be included in any copy.  */
/*                                                           */
/*************************************************************/
X
/*
X *  file:	setflag.c
X *
X *  author:	John J. Grefenstette
X *
X *  created:	apr 84
X *
X *  purpose:	set the option flags according to option string
X *		in input file.
X *
X *  modified:	28 mar 86
X */
X
#define   EXTERN
#include "global.h"
X
X
Setflag(c)
char c;
{
X	switch (c) {
X	case 'a' :
X		Allflag = 1;
X		break;
X	case 'A' :
X		Allflag = 1;
X		Aliasflag = 1;
X		break;
X	case 'b' : 
X		Bestflag = 1; 
X		break;
X	case 'c' : 
X		Collectflag = 1; 
X		Convflag = 1;
X		break;
X	case 'C' : 
X		Collectflag = 1; 
X		break;
X	case 'd' : 
X		Dumpflag = 1; 
X		break;
X	case 'e' :
X		Eliteflag = 1;
X		break;
X	case 'i' :
X		Initflag = 1;
X		break;
X	case 'l' :
X		Logflag = 1;
X		break;
X	case 'L' :
X		Lastflag = 1;
X		break;
X	case 'o' : 
X		Onlnflag = 1; 
X		break;
X	case 'O' :
X		Offlnflag = 1;
X		break;
X	case 'r' : 
X		Restartflag = 1; 
X		break;
X	case 's' : 
X		Schemflag = 1; 
X		break;
X	case 't' : 
X		Traceflag = 1; 
X		break;
X	case 'u' : 
X		Uniflag = 1; 
X		break;
X	}
}
X
/*** end of file ***/
X
SHAR_EOF
chmod 0444 src/setflag.c ||
echo 'restore of src/setflag.c failed'
Wc_c="`wc -c < 'src/setflag.c'`"
test 1721 -eq "$Wc_c" ||
	echo 'src/setflag.c: original size 1721, current size' "$Wc_c"
fi
exit 0