genesis.doc

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

.nr PO 1i
.LP
.ND
.DS C
.ps +4
.vs +4
A User's Guide to GENESIS
Version 5.0

.vs
.ps
JOHN J. GREFENSTETTE
October 1990

.DE
.FS
Copyright \(co 1990 by John J. Grefenstette
.FE
ABSTRACT

This document describes the GENESIS system for function optimization
based on genetic search techniques.  Genetic algorithms appear to hold a
lot of promise as general purpose adaptive search procedures.  However,
the author disclaims any warranties of fitness for any particular
problem.  The purpose of making this system available is to encourage
the experimental use of genetic algorithms on realistic optimization
problems, and thereby to identify the strengths and weaknesses of
genetic algorithms.  Comments and bug reports are also welcome. 


1. INTRODUCTION

This document describes the GENEtic Search Implementation System
(GENESIS Version 5.0).  This system was 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.  The system is written in the language C.
Details concerning the interface between the user-written function and
GENESIS are explained below.  Makefiles are provided to ease the
construction of genetic algorithms for the user's application.

This version offers several enhancements over previous versions that
should make the system much more user friendly.  The major improvement
is a user-level representation that allows the user to think about the
genetic structures as vectors of real numbers, rather than bit strings. 
This level of representation should make the application of GENESIS to
new problems easier than ever.  A number of new options have been added,
including: a display mode that includes an interactive user interface,
the option to maximize or minimize the objective function, the choice of
rank-based or proportional selection algorithm, and an option to use a
Gray code as a transparent lower level representation. 

The remainder of this section provides a general overview of genetic
algorithms (GA's).  For more detailed discussions, see [5,7].  GA's are
iterative procedures which maintain a "population" of candidate
solutions to the objective function f(x):

.DS C
P(t) = <x1(t), x2(t), ... , xN(t)>
.DE

Each structure xi in population P 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 the
procedure appears in Figure 1. 

.DS B

procedure \fIGA\fP
begin
	t = 0;
	\fIinitialize\fP P(t);
	\fIevaluate\fP structures in P(t);
	while termination condition not satisfied do
	begin
		t = t + 1;
		\fIselect\fP P(t) from P(t-1);
		\fIrecombine\fP structures in P(t);
		\fIevaluate\fP structures in P(t);
	end
 end.
.DE
.DS C
Figure 1.  A Genetic Algorithm
.DE

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). 

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 xj 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). 

In order to search other points in the search space, some variation is
introduced into the new population by means of idealized "genetic
recombination operators." The most important recombination operator is
called "crossover".  Under the crossover operator, two structures in the
new population exchange portions of their binary representations.  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

   x1 = 100:01010, and

   x2 = 010:10100.

and suppose that the crossover point has been chosen as indicated.  The
resulting structures would be

  y1 = 100:10100    and

  y2 = 010:01010.

Crossover serves two complementary search functions.  First, it provides
new points for further testing within the schemas 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 schemas
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. 

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. 

The basic concepts of GA's were developed by Holland [7] and his
students [2,4,6,8].  Theoretical considerations concerning the
allocation of trials to schemas [4,7] show that genetic techniques
provide a highly efficient heuristic for information gathering in
complex search spaces.  A number of experimental studies [2,3,4] have
shown that GA's exhibit impressive efficiency in practice.  While
classical gradient search techniques are more efficient for problems
which satisfy tight constraints (e.g., continuity, low dimensionality,
unimodality, etc.), GA's 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.  GA's have
been applied to various domains, including numerical function
optimization [2,3], adaptive control system design [5], and artificial
intelligence task domains [9].  The next section discusses each of the
major modules of this implementation in greater detail. 


2. MAJOR PROCEDURES

This section describes some of the more important procedures in the
GENESIS system.  For full details, see the actual source code. 

Representation

GENESIS has three levels of representation for the structures it is
evolving.  The lowest level, or "packed" representation, is used to
maximize both space and time efficiency in manipulating structures.  In
general, this level of representation is transparent to the user.  The
next level, or "string" representation, represents structures as
null-terminated arrays of chars.  For example, the structure 00110011
would be represented by the string "00110011".  This level is provided
for users who wish to provide an arbitrary interpretation on the genetic
structures, for example, non-numeric concepts.  The third level, or
"floating point" representation, will be the appropriate level for many
numeric optimization problems.  At this level, the user can think about
the genetic structures as vectors of real numbers.  The user specifies
the floating representation by interacting with the "setup" program (see
below).  For each parameter, or "gene", the user specifies its range,
its number of values, and its output format.  The system then
automatically lays out the string representation, and translates between
the user-level genes and the lower representation levels.

In the following sections, the major modules are described in more
detail.  The descriptions will be given at the string level
representation, although in some cases, the actual operations take place
at the packed level. 

Initialization

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 a file called "init" (or "init.foo" if you are using
file extensions (see below)), and use the "i" option (see "Options"). 
The rest of the initial population is filled with random structures.  If
the "f" option is in effect ("floating point representation"), the
structures in the init file must be specified as real numbers;
otherwise, the init file must contain strings, one per line. 

.ne 6
Generation

As previously mentioned, one generation (see "generate.c") comprises the
following steps: selection, mutation, crossover, evaluation, and some
data collection procedures. 

.ne 6
Selection

Selection is the process of choosing structures for the next generation
from the structures in the current generation.  The default 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 by 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 determines the number of offspring assigned to every structure. 
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. 

If the "R" option is in effect, selection is based on a Ranking
algorithm: the probability of selecting a structure is proportional to
its index in the population, where the index of the best structure is
Popsize-1, and the index of the worst structure is 0.  Ranking helps
prevent premature convergence by preventing "super" individuals from
taking over the population within a few generations.  However, ranking
often produces slower improvement than proportional selection. 

.ne 6
Mutation

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.  If mutation does occur, a random value is
chosen from {0,1} for that position.  If the mutated structure differs
from the original structure, the structure is marked for evaluation. 

.ne 6
Crossover

Crossover (see "cross.c") exchanges alleles among adjacent pairs of the
first (C_rate*Popsize) structures in the new population.  (Recall that
the population is randomly shuffled in the selection procedure.)
Crossover can be implemented in a variety of ways, but there are
theoretical advantages to 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. 


.ne 10
3. EVALUATION PROCEDURE

To use GENESIS, the user must write an evaluation procedure, which takes
one structure as input and returns a double precision value.  The
procedure must be declared in the user's file as follows:

.DS
.ft CW
double eval(str, length, vect, genes)
char str[];
int length;
double vect[];
int genes;
.ft
.DE

where "str" is string representation of the structure, "length" is the
length of "str", "vect" is the floating point representation (if option
"f" is set), and "genes" is the length of "vect".  The body of the
evaluation function is of course application dependent.  Figure 2 shows
a sample evaluation function.

.DS L
.ft CW
/************************************************  file f1.c  ****/

double eval(str, length, vect, genes)
char str[];      /* string representation                        */
int length;      /* length of bit string                         */
double vect[];   /* floating point representation                */
int genes;       /* number of elements in vect                   */
{
	register int i;
	double sum;

	sum = 0.0;
	for (i = 0; i < genes; i++)
		sum += vect[i] * vect[i];

	return (sum);
}

/************************************************ end of file ****/
.ft
.DE
.DS C
Figure 2: An evaluation function for a parabola.
.DE

Figure 3 shows an evaluation function that counts the number of 0's
in the string representation.

.DS L
.ft CW
/************************************************  file f6.c  ****/

double eval(str, length, vect, genes)
char str[];      /* string representation                        */