Evol - Evolution search optimisation

local EV = require 'Math.Evol' xb, sm, fb, lf = evol(xb, sm, function, constrain, tm) -- or xb, sm = select_evol(xb, sm, choose_best, constrain)

-- not yet implemented: -- 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.

*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 secondsThe 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,*choices*the number of choices*select_evol*generatesThe 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*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.

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,local function minimise(x) -- objective function, to be minimised local sum = 0.0 for k,v in ipairs(x) do sum = sum + v*v; end -- 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,local function constrain(x) -- force values into acceptable range if x[1] > 1.0 then x[1]=1.0 -- it's a probability elseif x[1] < 0.0 then x[1]=0.0 end local cost = 3.45*x[2] + 4.56*x[3] + 5.67*x[4] if cost > 1000.0 than -- enforce 1000 dollars maximum cost x[1] = x[2] * 1000/cost x[2] = x[3] * 1000/cost x[3] = x[4] * 1000/cost end if x[5] < 0.0 then x[5] = 0.0; end -- it's a population density x[6] = math.floor(x[6] + 0.5) -- it's an integer return x end xbref, smref, fb, lf = EV.evol(xb, sm, minimise, constrain)

*choose_best*({ a, b, c ... })-
This function whose reference is passed to

*select_evol*must accept a list of arrays; the first must be the current array of values, and the others are 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 (1, 2, 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,local function choose_best(choices) io.write("Array 1 is "..table.concat(choices[1]," ").."\n") io.write("Array 2 is "..table.concat(choices[2]," ").."\n") local preference = 0 + choose('Do you prefer 1 or 2 ?','1','2') local continue = confirm('Continue ?') return preference, continue end xb, sm, fb, lf = EV.select_evol(xb, sm, choose_best);

*choose_best_text*( text1, text2, text3 ... );-
This function which 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 (1, 2, 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.

EV.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 EV.ec. The absolute convergence test is suppressed if EV.ec is undefined.

EV.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 EV.ed multiplied by the absolute value of the objective function. The relative convergence test is suppressed if EV.ed is undefined.

These interact with two other small numbers EV.ea and EV.eb, which are the minimum allowable step-sizes, absolute and relative respectively.

These number are set within Evol as follows:

EV.ea = 0.00000000000001; -- absolute stepsize EV.eb = 0.000000001; -- relative stepsize EV.ec = 0.0000000000000001; -- absolute error EV.ed = 0.00000000001; -- relative error

You can change those settings before invoking the evol subroutine, e.g.:

EV.Evol.ea = 0.00000000000099; -- absolute stepsize EV.Evol.eb = 0.000000042; -- relative stepsize EV.Evol.ec = nil -- disable absolute-error-criterion EV.Evol.ec = 0.0000000000000031; -- absolute error EV.Evol.ed = 0.00000000067; -- relative error

The most robust criterion is the maximum-cpu-time parameter *tm*

This module is available as a LuaRock in
luarocks.org/modules/peterbillam/

so you should be able to install it with the command:

` `

**luarocks install math-evol**

Or:

```
luarocks install
http://www.pjb.com.au/comp/lua/math-evol-1.13-0.rockspec
```

The test script is in www.pjb.com.au/comp/lua/test_ev.lua

This module is the translation into *Lua* of
the *Perl* CPAN module Math::Evol,
and comes in its `./lua`

subdirectory.
The calling-interfaces are identical in both versions.

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 modernised,
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 Amoeba which implements the Simplex strategy of Nelder and Mead; another good algorithm is that of Davidon, Fletcher, Powell and Stewart, 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: