Skip site navigation (1)Skip section navigation (2)

FreeBSD Manual Pages

  
 
  

home | help
Evol(3)		      User Contributed Perl Documentation	       Evol(3)

NAME
       Math::Evol - Evolution search optimisation

SYNOPSIS
	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 );

DESCRIPTION
       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

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

STEP SIZES
       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.

CALLER-SUPPLIED	SUBROUTINES
       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.

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 $tm

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

AUTHOR
       Peter J Billam, www.pjb.com.au/comp/contact.html

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

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

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>

home | help