Math::Evol - Evolution search optimisation
use Math::Evol;
($xbref,$smref,$fb,$lf) = evol(\@xb,\@sm,\&function,\&constrain,$tm);
# or
($xbref, $smref) = select_evol(\@xb,\@sm,\&choose_best,\&constrain);
# or
$new_text = text_evol($text, \&choose_best_text, $nchoices );
This module implements the evolution search strategy. Derivatives of the
objective function are not required. Constraints can be incorporated. The
caller must supply initial values for the variables and for the initial step
sizes.
This evolution strategy is a random strategy, and as such is particularly robust
and will cope well with large numbers of variables, or rugged objective
funtions.
Evol.pm works either automatically (evol) with an objective function to be
minimised, or interactively (select_evol) with a (suitably patient) human who
at each step will choose the better of two possibilities. Another subroutine
(text_evol) allows the evolution of numeric parameters in a text file, the
parameters to be varied being identified in the text by means of special
comments. A script
ps_evol which uses that is included for
human-judgement-based fine-tuning of drawings in PostScript.
Version 1.13
- evol(\@xb, \@sm, \&minimise, \&constrain, $tm);
- Where the arguments are:
@xb the initial values of variables,
@sm the initial values of step sizes,
&minimise the function to be minimised,
&constrain a function constraining the values,
$tm the max allowable cpu time in seconds
The step sizes and the caller-supplied functions &function and
&constrain are discussed below. The default value of
$tm is 10 seconds.
evol returns a list of four things:
\@xb the best values of the variables,
\@sm the final values of step sizes,
$fb the best value of objective function,
$lf a success parameter
$lf is set false if the search ran out of cpu time
before converging. For more control over the convergence criteria, see the
CONVERGENCE CRITERIA section below.
- select_evol(\@xb, \@sm, \&choose_best, \&constrain,
$nchoices);
- Where the arguments are:
@xb the initial values of variables,
@sm the initial values of step sizes,
&choose_best the function allowing the user to select the best,
&constrain a function constraining the values,
$nchoices the number of choices select_evol
generates
The step sizes and the caller-supplied functions &choose_best and
&constrain are discussed below. $nchoices
is the number of alternative choices which will be offered to the user, in
addition to the current best array of values. The default value of
$nchoices is 1, giving the user the choice between
the current best and 1 alternative.
select_evol returns a list of two things:
\@xb the best values of the variables, and
\@sm the final values of step sizes
- text_evol( $text, \&choose_best_text, $nchoices );
- The $text is assumed to contain some numeric parameters to be varied,
marked out by magic comments which also supply initial step sizes for
them, and optionally also maxima and minima. For example:
$x = -2.3456; # evol step .1
/x 3.4567 def % evol step .2
/gray_sky .87 def % evol step 0.05 min 0.0 max 1.0
The magic bit of the comment is evol step and the previous number on
the same line is taken as the value to be varied. The function reference
\&choose_best_text is discussed below.
$nchoices gets passed by text_evol directly to
select_evol.
&text_evol returns the optimised $text.
&text_evol is intended for fine-tuning of PostScript, or files
specifying GUI's, or HTML layout, or StyleSheets, or MIDI, where the value
judgement must be made by a human being. As an example, a script called
ps_evol for fine-tuning A4 PostScript drawings is included with
this package; it uses $nchoices = 8 and puts the nine alternatives onto
one A4 page which the user can then view with Ghostview in order to select
the best one.
The caller must supply initial values for the step sizes. Following the work of
Rechenberg and of Schwefel,
evol will adjust these step-sizes as it
proceeds to give a success rate of about 0.2, but since the ratios between the
step-sizes remain constant, it helps convergence to supply sensible values.
A good rule of thumb is the expected distance of the value from its optimum
divided by the square root of the number of variables. Larger step sizes
increase the chance of discovering a global optimum rather than an inferior
local optimum, at the cost of course of slower convergence.
- minimise( @x );
- evol minimises an objective funtion; that function accepts a list
of values and returns a numerical scalar result. For example,
sub minimise { # objective function, to be minimised
my $sum; foreach (@_) { $sum += $_*$_; } # sigma x**2
return $sum;
}
($xbref, $smref, $fb, $lf) = evol (\@xb, \@sm, \&minimise);
- constrain( @x );
- You may also supply a subroutine constrain(@x) which forces the
variables to have acceptable values. If you do not wish to constrain the
values, just pass 0 instead. constrain(@x) should return the list
of the acceptable values. For example,
sub constrain { # force values into acceptable range
if ($_[0]>1.0) { $_[0]=1.0; # it's a probability
} elsif ($_[0]<0.0) { $_[0]=0.0;
}
my $cost = 3.45*$_[1] + 4.56*$_[2] + 5.67*$_[3];
if ($cost > 1000.0) { # enforce 1000 dollars maximum cost
$_[1]*=1000/$cost; $_[2]*=1000/$cost; $_[3]*=1000/$cost;
}
if ($_[4]<0.0) { $_[4]=0.0; } # it's a population density
$_[5] = int ($_[5] + 0.5); # it's an integer
return @_;
}
($xbref,$smref,$fb,$lf) = evol (\@xb,\@sm,\&minimise,\&constrain);
- choose_best( \@a, \@b, \@c ... );
- This function whose reference is passed to select_evol must accept
a list of array_refs; the first ref refers to the current array of values,
and the others refer to alternative arrays of values. The user should then
judge which of the arrays is best, and choose_best must then return
($preference, $continue) where
$preference is the index of the preferred array_ref
(0, 1, etc). The other argument ($continue) is set false if the
user thinks the optimal result has been arrived at; this is
select_evol's only convergence criterion. For example,
use Term::Clui;
sub choose_best { my ($aref, $bref) = @_;
inform("Array 0 is @$aref");
inform("Array 1 is @$bref");
my $preference = 0 + choose('Do you prefer 0 or 1 ?','0','1');
my $continue = confirm('Continue ?');
return ($preference, $continue);
}
($xbref, $smref, $fb, $lf) = select_evol(\@xb, \@sm, \&choose_best);
- choose_best_text( $text1, $text2, $text3 ... );
- This function whose reference is passed to text_evol must accept a
list of text strings; the first will contain the current values while the
others contain alternative values. The user should then judge which of the
strings produces the best result. choose_best_text must return
($preference, $continue) where
$preference is the index of the preferred string (0,
1, etc). The other argument ($continue) is set false if the user
thinks the optimal result has been arrived at; this is text_evol's
only convergence criterion.
As an example, see the script called ps_evol for fine-tuning A4
PostScript drawings which is included with this package.
$ec (>0.0) is the convergence test, absolute. The search is terminated if the
distance between the best and worst values of the objective function within
the last 25 trials is less than or equal to $ec. The absolute convergence test
is suppressed if $ec is undefined.
$ed (>0.0) is the convergence test, relative. The search is terminated if the
difference between the best and worst values of the objective function within
the last 25 trials is less than or equal to $ed multiplied by the absolute
value of the objective function. The relative convergence test is suppressed
if $ed is undefined.
These interact with two other small numbers $ea and $eb, which are the minimum
allowable step-sizes, absolute and relative respectively.
These number are set within Math::Evol as follows:
$ea = 0.00000000000001; # absolute stepsize
$eb = 0.000000001; # relative stepsize
$ec = 0.0000000000000001; # absolute error
$ed = 0.00000000001; # relative error
You can change those settings before invoking the evol subroutine, e.g.:
$Math::Evol::ea = 0.00000000000099; # absolute stepsize
$Math::Evol::eb = 0.000000042; # relative stepsize
undef $Math::Evol::ec; # disable absolute-error-criterion
$Math::Evol::ec = 0.0000000000000031; # absolute error
$Math::Evol::ed = 0.00000000067; # relative error
The most robust criterion is the maximum-cpu-time parameter $tm
In the "lua/" subdirectory of the install directory there is
Evol.lua, which is an exact translation of this Perl code into Lua. The
function names and arguments are unchanged, except that
text_evol is
not yet implemented. Brief Synopsis:
local M = require 'Evol'
local function minimise(x) -- returns a number to be minimised
local sum = 1.0
for k,v in pairs(x) do sum = sum + v * v end
return sum
end
local function constrain(x)
if x[1] > 1.0 then x[1] = 1.0 -- it's a greyscale value
elseif x[1] < 0.0 then x[1] = 0.0
end
return x
end
local function choose_best(arglist)
local preference = 1; local i_arg
for i_arg=1,#arglist do
local x = arglist[i_arg]
if that_suits_me() then preference = i_arg; break end
end
local continue = true or false
return preference, continue
end
M.ed = 0.00000000067 -- relative error
local x = {3.456, 1.234, -2.345, 4.567} -- starting values
local sm = {.8, .4, .6, 1.2} -- starting step-sizes
local tm = 5.0 -- max time in seconds
-- and now...
xb,sm,fb,lf = M.evol(xb, sm, minimise, constrain, tm)
-- or
xb,sm = M.select_evol(xb, sm, choose_best, constrain)
-- not yet implemented :
-- new_text = M.text_evol(text, choose_best_text, nchoices)
Peter J Billam, www.pjb.com.au/comp/contact.html
The strategy of adjusting the step-size to give a success rate of 0.2 comes from
the work of I. Rechenberg in his
Optimisation of Technical Systems in
Accordance with the Principles of Biological Evolution (Problemata
Series, Vol. 15, Verlag Fromman-Holzboog, Stuttgart 1973).
The code of
evol is based on the Fortran version in
Numerical
Optimisation of Computer Models by Hans-Paul Schwefel, Wiley 1981, pp
104-117, 330-337, translated into english by M.W. Finnis from
Numerische
Optimierung von Computer-Modellen mittels der Evolutionsstrategie
(Interdiscipliniary Systems Research, Vol. 26), Birkhaeuser Verlag, Basel
1977. The calling interface has been greatly Perlised, and the constraining of
values has been much simplified.
The deterministic optimistation strategies can offer faster convergence on
smaller problems (say 50 or 60 variables or less) with fairly smooth
functions; see John A.R. Williams CPAN module Math::Amoeba which implements
the Simplex strategy of Nelder and Mead; another good algorithm is that of
Davidon, Fletcher, Powell and Stewart, currently unimplemented in Perl, see
Algorithm 46 and notes, in Comp J. 13, 1 (Feb 1970), pp 111-113; Comp J. 14, 1
(Feb 1971), p 106 and Comp J. 14, 2 (May 1971), pp 214-215. See also
http://www.pjb.com.au/,
perl(1).