genesis.doc

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

from one generation to the next.  In the absence of this strategy, it is
possible that the best structure disappears, thanks to crossover or
mutation. 

"f": use the floating point representation specified in the template
file.  If set, structure in the init file (option "i") must be specified
in floating point, structures in the min file will be printed in
floating point, and the ckpt file will also show the interpreted genes
(in addition to the string representation).

"g": use Gray code.  A Gray code is sometimes useful in representing
integers in genetic algorithms.  Gray codes have the property that
adjacent integer values differ at exactly one bit position.  The use of
Gray codes avoid 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).  This
option has no effect unless option "f" is also set. 

"i": read structures into the initial population.  The initial
population will be read from the "init" file.  If the file contains
fewer structures than the population needs, the remaining structures
will be initialized randomly.  Note: it is good practice to allow at
least some randomness in the initial population. 

"I": interactive mode.  Display mode is enabled, and statistics are
printed to the screen after each generation.  In addition, the user is
prompted for command to control the operation of the genetic algorithm. 

"l": log activity (starts and restarts) in the "log" file.  Some error
messages also end up in the "log" file. 

"L": dump the last generation to the "ckpt" file.  This allows the user
to restart the experiment at a later time, using option "r". 

"M": maximize the evaluation function.  The default is to minimize the
evaluation function. 

"o": at the end of the experiments, write the average online performance
measure to the standard output.  Online performance is the average of
all evaluations during the experiment. 

"O": at the end of the experiments, write the average Offline
performance measure to the standard output.  Offline performance is the
average of the best current values. 

"r": restart a previously interrupted execution.  In this case, the
"ckpt" file is read back in, and the GA takes up where it left off. 

"R": Rank based selection.

"s": trace the history of one schema.  This option requires that a file
named "schema" exists in which the first line contains a string which has
the length of one structure and which contains only the characters "0",
"1", and "#" (and no blanks).  The system will append one line to the
schema file after each generation describing the performance
characteristics of the indicated schema (number of representatives,
relative fitness, etc.).  The lines are also printed on screen under "D"
and "I" options. 

"t": trace each major function call.  (FOR DEBUGGING.) Tracing
statements are written to the standard output. 


.ne 6
8. THE REPORT

If the "c" or "C" option is selected, a report describing the
performance of the GA can be produced by the "report" program.  Run
"report" with the same command line argument used for running the GA. 
For example:

.ft CW
   % ga.foo foo
.ft

.ft CW
   % report foo > rep.foo
.ft

The report summarizes the mean, variance and range of several
measurements, including 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 the current best evaluations.  See [5].  If
option "c" is selected, three additional measures concerning the
convergence of the GA are printed: "Conv" indicates the number of
positions in which at least 95% of the population has the same value. 
"Lost" indicates the number of positions in which 100% of the population
has the same value.  "Bias" indicates the average percentage of the most
prominent value in each position.  That is, a bias of 0.75 means that,
on average, each position has converged to 75% 0's or 75% 1's.  The
minimum bias is 0.50. 


.ne 6
9. EXAMPLE

Figure 2 shows an example of a user-defined evaluation for the following
problem:

Min f(x) =  sum [(xi)^2], where  -5.12 <= xi <= 5.11, i=1,2,3.

Each xi is represented by 10 bits, so that the structure length is 30,
and the granularity for each xi is 0.01.  The minimum occurs at the
origin.  (Of course, this problem does not require the full power of
genetic algorithms and can be more appropriately solved using classical
optimization techniques.)

.na
.nf
.ft CW
   % setup
.ft

.ft CW
   File suffix []: ex1
   Floating point representation [y]:
   genes: 3
   gene 0:
   min: -5.12
   max: 5.11
   values (must be a power of 2): 1024
   format: %7.2f
   repetition: 3

   Experiment [1]:
   Trials [1000]:
   Pop Size [50]:
   Length [30]:
   Crossover Rate [0.6]:
   Mutation Rate [0.001]:
   Generation Gap [1.0]:
   Windowsize [5]:
   Report Interval [100]: 200
   Structures Saved [10]: 5
   Max Gens w/o Eval [2]:
   Dump Interval [0]:
   Dumps Saved [0]:
   Options [cefgl]: acefgL
   Random Seed: [123456789]:
   Rank Min [0.75]:
.ft

The input file "in.ex1" is created and echoed to the terminal:

.ft CW
       Experiments = 1
      Total Trials = 1000
   Population Size = 50
  Structure Length = 30
    Crossover Rate = 0.6
     Mutation Rate = 0.001
    Generation Gap = 1.0
    Scaling Window = 5
   Report Interval = 200
  Structures Saved = 5
 Max Gens w/o Eval = 2
     Dump Interval = 0
       Dumps Saved = 0
           Options = acefgL
       Random Seed = 123456789
          Rank Min = 0.75
.ft

The file "template.ex1" is created:

.ft CW
   genes: 3

   gene 0
   min: -5.12
   max: 5.11
   values: 1024
   format: %7.2f

   gene 1
   min: -5.12
   max: 5.11
   values: 1024
   format: %7.2f

   gene 2
   min: -5.12
   max: 5.11
   values: 1024
   format: %7.2f
.ft

Now execute the shell script:

.ft CW
  % go f1 ex1
.ft

This executes the commands:

.ft CW
  make f=f1 ga.f1
  ga.f1 exp1
  report f1 > rep.ex1
.ft

.fi
.ad
The program ga.f1 executes.  The raw output data is sent to file
"out.ex1", and the values of the global variables, including the final
population, are sent to "ckpt.ex1." The report generator produces file
"rep.ex1":

.DS L
.ft CW
rep.ex1 for ga.f1
Tue Oct  9 23:10:25 EDT 1990
 
      Experiments = 1
     Total Trials = 1000
  Population Size = 50
 Structure Length = 30
   Crossover Rate = 0.600
    Mutation Rate = 0.001
   Generation Gap = 1.000
   Scaling Window = 5
  Report Interval = 200
 Structures Saved = 5
Max Gens w/o Eval = 2
    Dump Interval = 0
      Dumps Saved = 0
          Options = acefgL
      Random Seed = 123456789
         Rank Min = 0.750

MEAN
Gens  Trials  Lost  Conv   Bias    Online    Offline      Best     Average
   0      50     0     0  0.569  2.622e+01  5.271e+00  2.795e+00  2.622e+01
   3     200     0     0  0.617  1.951e+01  2.859e+00  7.049e-01  1.518e+01
   7     400     0     0  0.690  1.467e+01  1.633e+00  3.097e-01  7.546e+00
  11     600     1     2  0.723  1.146e+01  1.185e+00  2.485e-01  3.514e+00
  15     800     2     5  0.742  9.329e+00  9.362e-01  1.861e-01  2.665e+00
  19    1000     3     5  0.753  7.860e+00  7.837e-01  1.202e-01  1.791e+00
.ft
.DE

The 5 best structures are saved in file "min.ex1":

.ft CW
   % cat min.ex1
.ft

.DS
.ft CW
  -0.29   0.19   0.00   1.2020e-01    19   972
   0.36   0.14   0.17   1.7810e-01    18   921
  -0.30  -0.31   0.00   1.8610e-01    12   617
   0.32   0.29   0.00   1.8650e-01    18   902
  -0.29   0.30   0.00   1.7410e-01    18   923
.ft
.DE 

Each line of the minfile displays one structure, its evaluation, and the
generation and trial counters at the time of the first occurrence of
this structure. 

If it is desired to continue this experiment, edit the input file
"in.ex1" to increase the total number of trials and to add "r" to the
options.  Then issue the command:

.ft CW
   % go f1 ex1
.ft



ACKNOWLEDGMENTS

The author wishes to thank the many users of GENESIS for their
suggestions and comments.  Further suggestions and comments are
solicited.  Of course, the responsibility for any remaining errors is
mine. 


REFERENCES

1. James E. Baker, "Reducing bias and inefficiency in the selection
algorithm," in Genetic Algorithms and Their Applications: Proc. 2nd
Intl. Conf., ed. J. J. Grefenstette, pp. 14-21, LEA, Cambridge,
MA, July 1987. 

2. A. D. Bethke, Genetic algorithms as function optimizers, Ph. D. 
Thesis, Dept. Computer and Communication Sciences, Univ. of Michigan,
1981. 

3. A. Brindle, Genetic algorithms for function optimization, Ph. D. 
Thesis, Computer Science Dept., Univ. of Alberta, 1981. 

4. K. A. DeJong, Analysis of the behavior of a class of genetic
adaptive systems, Ph. D. Thesis, Dept. Computer and Communication
Sciences, Univ. of Michigan, 1975. 

5. K. A. DeJong, "Adaptive system design: a genetic approach," IEEE
Trans. Syst., Man, and Cyber., vol. SMC-10, no. 9, pp. 566-574,
Sept. 1980. 

6. D. R. Frantz, Non-linearities in genetic adaptive search, Ph. D. 
Thesis, Dept. Computer and Communication Sciences, Univ. of Michigan,
1972. 

7. J. H. Holland, Adaptation in Natural and Artificial Systems, Univ. 
Michigan Press, Ann Arbor, 1975. 

8. R. B. Hollstien, Artificial genetic adaptation in computer control
systems, Ph. D. Thesis, Dept. Computer and Communication Sciences,
Univ. of Michigan, 1971. 

9. S. F. Smith, "Flexible learning of problem solving heuristics
through adaptive search," Proc. 8th Intl. J. Conf. Artif. Intel. 
(IJCAI), Aug. 1983.