SECTION 16.3 GLOBAL OPTIMIZATION BY GENETIC ALGORITHM (GENALG)
Genetic algorithms start by generating a set of random feasible solutions. The best of these solutions are permitted to "mate" and produce offspring and mutations are occasionally introduced. The worst solutions in every generation are discarded and the process continues until either an iteration limit is reached or convergence takes place. See R. L. Haupt and S. E. Haupt, Practical Genetic Algorithms, Wiley, 1998 and D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, 1989.
Suitable parameters for the algorithm should be determined by experimentation, since good values are problem dependent. This implementation is a continuous parameter (thus not a binary encoded) version of genetic algorithms.
In the MAIN program you must include
COMMON/GENALG2/NC,INITGEN,IPAIR,IMATE,KTERL,IMUTE,
* ITEST,IHOWMAN
COMMON/GENALG3/YMUTE,ALPH1,BET1,BACC,PM4,SHRINK1,EXPAND
COMMON/BPRINT/IPT,NFILE,NDIG,NPUNCH,JPT,MFILE
CALL DFLT
OPEN (UNIT=nfile,file='filename')
where NFILE is initialized by DFLT to 8 and will be the output file.
The call to GENALG is
CALL GENALG(MX,NP,NIPOP,NPOP,NGOOD,XL,XH,CC,PP,CPP,
* MATES,X,POP,U,FVAL,FUNC,ITERC,IER,IVAL,NCONT)
where
MX = 1 to maximize, = 2 to minimize
NP = the number of parameters
NIPOP = the initial population (a power of 2; 128 is
often suitable)
NPOP = the "working size" of the population (a power of 2, 64
is often suitable)
NGOOD = the subpopulation that is permitted to mate (a power
of 2; 32 is often suitable)
XL = a DOUBLE PRECISION vector dimensioned XL(NP)
containing the lower bounds of the search area
XH = a DOUBLE PRECISION vector dimensioned XH(NP)
containing the upper bounds of the search area
CC,PP,CPP = DOUBLE PRECISION work arrays, each dimensioned
NP, i.e., CC(NP), PP(NP), CPP(NP)
MATES = a work array dimensioned MATES(2,NGOOD/2)
X = a DOUBLE PRECISION work array dimensioned X(NP)
POP = an INTEGER array dimensioned POP(NIPOP,NP) containing
the initial and subsequent populations; after
convergence POP(1,.) contains the parameter values
for the best solution
U = DOUBLE PRECISION work array dimensioned U((NIPOP,NP)
FVAL = DOUBLE PRECISION array which will contain the function
values corresponding to the population members; after
convergence, FVAL(1) contains the best function value
FUNC = the name of the function subroutine to be minimized or
maximized; must be declared in an EXTERNAL statement
in the MAIN program. See Section 1.1 for the conventions
concerning FUNC subroutines.
ITERC = the iteration (generation) count
IVAL = the number of function evaluations
IER = error return; =-1 iteration limit exceeded, =-3 input
error, =-5 continual straying into a forbidden region
NCONT = an integer value which causes the computations to be
repeated if > 1. The repetition is as follows: after
the first "pass" has converged, the best parameter
values (in POP(1,.)) are retained, the feasible search
area is shrunk (except in directions in which the
optimum value is near the original boundary, in which
case the search area is expanded in that direction), a
new set of NIPOP-1 points are generated and the
algorithm resumes. See also SHRINK1 and EXPAND below.
A value of NCONT > 1 is useful to refine the location
of a local optimum, but may hurt the chances of
finding a global optimum.
IHOWMAN = the number of consecutive generations (iterations)
in which either the optimal function value or the mean
function value is allowed to remain unchanged without
terminationg the computations; must be <=9.
(Default=5)
The following parameters, communicated to GENALG through labelled COMMON, are also important.
COMMON/GENALG2/NC,INITGEN,IPAIR,IMATE,KTERL,IMUTE,
* ITEST,IHOWMAN
where
NC = 1 should not be altered; this is a provision for
future modifications
INITGEN = 2 initial population is generated randomly;
3 no initial population is generated; user is
responsible for filling the NIPOP rows of POP;
4 one half of the population is generated randomly;
from the ith row of POP (i=1,nipop/2) the remaining
rows are generated by POP(nipop/2+i,j)=XH(j)-POP(i,j)
(Default=2)
IPAIR = 1 parents are selected for pairing as follows: the
lowest-cost parent mates with the second-lowest
cost parent, the third-lowest with the
fourth-lowest, and so on;
= 2 pairing by rank-weighting (See Haupt and Haupt,
p. 39);
= 3 pairing by cost weighting (See Haupt and Haupt,
pp. 39-40) (default=3);
= 4 random pairing
IMATE = 1 each parent pair creates four potential offspring
which differ in that for two the ic-th parameter of
the offspring being a (BET1,1-BET1) and a
(1-BET1,BET1) convex combination of the parents and
for another two a (1+ALPH1,-ALPH1) and a (-ALPH1,
ALPH1) combination, with the best two selected;
= 2 each parent produces three potential offspring,
the first of which is for the ic-th parameter
a (u,1-u) combination of the parents (where u
is a U(0,1) deviate), and the remaining two as
immediately above, with the best two chosen;
KTERL = iteration limit (default=99)
IMUTE = 1 mutation rate remains constant;
= 2 mutation rate decays 10% each generation;
= 3 mutation is given by POP(I,.)*(1.5-u) where
u is distributed as U(0,1);
ITEST = 1 if testing for convergence should be based on the
optimal value achieved in a population (default=1);
= 2 if testing should be based on the mean value of the
population (this latter is likely to give a better
optimum, but may take a great deal more
computation);
IHOWMAN = the number of consecutive generations (iterations)
in which either the optimal function value or the mean
function value is allowed to remain unchanged without
terminationg the computations; must be <=9.
(default=5)
COMMON/GENALG3/YMUTE,ALPH1,BET1,BACC,PM4,SHRINK1,EXPAND
YMUTE = DOUBLE PRECISION constant defining the mutation rate;
the number of mutations in a population will be
(NPOP+NGOOD)*NP*YMUTE. The required number of
individuals in the population will be chosen at random
(except the best element in the population will not
be subject to mutation) and then two randomly
chosen city pairs will be exchanged (default=0.06)
BACC = DOUBLE PRECISION required relative accuracy (default=
0.001)
ALPH1 = extrapolation factor for mating (see IMATE above)
(default =0.1)
BET1 = convex combination factor for mating (see (IMATE
above (default = 0.5)
PM4 = used internally; user should not alter this
SHRINK1 = Shrinkage factor for region of exploration in
successive passes. XL and XH for each parameter are
reset as XL = XL + SHRINK1*(POP(1,.)-XL) and
XH = XH + SHRINK1*(POP(1,.)-XH) (default=0.95)
EXPAND = Expansion factor for region of exploration in
successive passes. XL and XH for each parameter are
reset as XL = XL - EXPAND*(XH-XL) and
XH = XH + EXPAND*(XH-XL) (default=0.05)