# FreeBSD Manual Pages

Evol(3) User Contributed Perl Documentation Evol(3)NAMEMath::Evol - Evolution search optimisationSYNOPSISuse 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 );DESCRIPTIONThis 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 scriptps_evolwhich uses that is included for human-judgement-based fine-tuning of drawings in PostScript. Version 1.13SUBROUTINESevol(\@xb, \@sm, \&minimise, \&constrain, $tm); Where the arguments are:@xbthe initial values of variables,@smthe initial values of step sizes, _minimisethe function to be minimised, _constraina function constraining the values,$tmthe max allowable cpu time in seconds The step sizes and the caller-supplied functions _functionand _constrainare discussed below. The default value of$tmis 10 seconds.evolreturns a list of four things:\@xbthe best values of the variables,\@smthe final values of step sizes,$fbthe best value of objective function,$lfa success parameter$lfis 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:@xbthe initial values of variables,@smthe initial values of step sizes, _choose_bestthe function allowing the user to select the best, _constraina function constraining the values,$nchoicesthe number of choicesselect_evolgenerates The step sizes and the caller-supplied functions _choose_bestand _constrainare discussed below.$nchoicesis 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$nchoicesis 1, giving the user the choice between the current best and 1 alternative.select_evolreturns a list of two things:\@xbthe best values of the variables, and\@smthe final values of step sizestext_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 isevolstepand the previous number on the same line is taken as the value to be varied. The function reference\_choose_best_textis discussed below.$nchoicesgets passed bytext_evoldirectly toselect_evol. _text_evolreturns the optimised $text. _text_evolis 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 calledps_evolfor 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.STEP SIZESThe caller must supply initial values for the step sizes. Following the work of Rechenberg and of Schwefel,evolwill 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.CALLER-SUPPLIED SUBROUTINESminimise( @x );evolminimises 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 subroutineconstrain(@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 toselect_evolmust 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, andchoose_bestmust then return($preference,$continue)where$preferenceis 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 isselect_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 totext_evolmust 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_textmust return($preference,$continue)where$preferenceis 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 istext_evol's only convergence criterion. As an example, see the script calledps_evolfor fine-tuning A4 PostScript drawings which is included with this package.CONVERGENCE CRITERIA$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 $tmLUAIn the "lua/" subdirectory of the install directory there isEvol.lua, which is an exact translation of this Perl code into Lua. The function names and arguments are unchanged, except thattext_evolis 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)AUTHORPeter J Billam, www.pjb.com.au/comp/contact.htmlCREDITSThe strategy of adjusting the step-size to give a success rate of 0.2 comes from the work of I. Rechenberg in hisOptimisationofTechnicalSystemsinAccordancewiththePrinciplesofBiologicalEvolution(Problemata Series, Vol. 15, Verlag Fromman-Holzboog, Stuttgart 1973). The code ofevolis based on the Fortran version inNumericalOptimisationofComputerModelsby Hans-Paul Schwefel, Wiley 1981, pp 104-117, 330-337, translated into english by M.W. Finnis fromNumerischeOptimierungvonComputer-ModellenmittelsderEvolutionsstrategie(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.SEE ALSOThe 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). perl v5.32.1 2017-06-13 Evol(3)

NAME | SYNOPSIS | DESCRIPTION | SUBROUTINES | STEP SIZES | CALLER-SUPPLIED SUBROUTINES | CONVERGENCE CRITERIA | LUA | AUTHOR | CREDITS | SEE ALSO

Want to link to this manual page? Use this URL:

<https://www.freebsd.org/cgi/man.cgi?query=Math::Evol&sektion=3&manpath=FreeBSD+13.1-RELEASE+and+Ports>