probopt - Man Page

Probabilistic optimisation methods

Synopsis

package require Tcl  8.6

package require TclOO

package require math::probopt  1

::math::probopt::pso function bounds args

::math::probopt::sce function bounds args

::math::probopt::diffev function bounds args

::math::probopt::lipoMax function bounds args

::math::probopt::adaLipoMax function bounds args

Description

The purpose of the math::probopt package is to provide various optimisation algorithms that are based on probabilistic techniques. The results of these algorithms may therefore vary from one run to the next. The algorithms are all well-known and well described and proponents generally claim they are efficient and reliable.

As most of these algorithms have one or more tunable parameters or even variations, the interface to each accepts options to set these parameters or the select the variation. These take the form of key-value pairs, for instance, -iterations 100.

This manual does not offer any recommendations with regards to these algorithms, nor does it provide much in the way of guidelines for the parameters. For this we refer to online articles on the algorithms in question.

A few notes, however:

The collection consists of the following algorithms:

The various procedures have a uniform interface:

   set result [::math::probopt::algorithm function bounds args]

The arguments have the following meaning:

The result of the various optimisation procedures is a dictionary containing at least the following elements:

Details on the Algorithms

The algorithms in the package are the following:

::math::probopt::pso function bounds args

The "particle swarm optimisation" algorithm uses the idea that the candidate optimum points should swarm around the best point found so far, with variations to allow for improvements.

It recognises the following options:

  • -swarmsize number: Number of particles to consider (default: 50)
  • -vweight    value: Weight for the current "velocity" (0-1, default: 0.5)
  • -pweight    value: Weight for the individual particle's best position (0-1, default: 0.3)
  • -gweight    value: Weight for the "best" overall position as per particle (0-1, default: 0.3)
  • -type       local/global: Type of optimisation
  • -neighbours number: Size of the neighbourhood (default: 5, used if "local")
  • -iterations number: Maximum number of iterations
  • -tolerance  value: Absolute minimal improvement for minimum value
::math::probopt::sce function bounds args

The "shuffled complex evolution" algorithm is an extension of the Nelder-Mead algorithm that uses multiple complexes and reorganises these complexes to find the "global" optimum.

It recognises the following options:

  • -complexes           number: Number of particles to consider (default: 2)
  • -mincomplexes        number: Minimum number of complexes (default: 2; not currently used)
  • -newpoints           number: Number of new points to be generated (default: 1)
  • -shuffle             number: Number of iterations after which to reshuffle the complexes (if set to 0, the default, a number will be calculated from the number of dimensions)
  • -pointspercomplex    number: Number of points per complex (if set to 0, the default, a number will be calculated from the number of dimensions)
  • -pointspersubcomplex number: Number of points per subcomplex (used to select the best points in each complex; if set to 0, the default, a number will be calculated from the number of dimensions)
  • -iterations          number: Maximum number of iterations (default: 100)
  • -maxevaluations      number: Maximum number of function evaluations (when this number is reached the iteration is broken off. Default: 1000 million)
  • -abstolerance        value: Absolute minimal improvement for minimum value (default: 0.0)
  • -reltolerance        value: Relative minimal improvement for minimum value (default: 0.001)
::math::probopt::diffev function bounds args

The "differential evolution" algorithm uses a number of initial points that are then updated using randomly selected points. It is more or less akin to genetic algorithms. It is controlled by two parameters, factor and lambda, where the first determines the update via random points and the second the update with the best point found sofar.

It recognises the following options:

  • -iterations          number: Maximum number of iterations (default: 100)
  • -number              number: Number of point to work with (if set to 0, the default, it is calculated from the number of dimensions)
  • -factor              value: Weight of randomly selected points in the updating (0-1, default: 0.6)
  • -lambda              value: Weight of the best point found so far in the updating (0-1, default: 0.0)
  • -crossover           value: Fraction of new points to be considered for replacing the old ones (0-1, default: 0.5)
  • -maxevaluations      number: Maximum number of function evaluations (when this number is reached the iteration is broken off. Default: 1000 million)
  • -abstolerance        value: Absolute minimal improvement for minimum value (default: 0.0)
  • -reltolerance        value: Relative minimal improvement for minimum value (default: 0.001)
::math::probopt::lipoMax function bounds args

The "Lipschitz optimisation" algorithm uses the "Lipschitz" property of the given function to find a maximum in the given bounding box. There are two variants, lipoMax assumes a fixed estimate for the Lipschitz parameter.

It recognises the following options:

  • -iterations          number: Number of iterations (equals the actual number of function evaluations, default: 100)
  • -lipschitz           value: Estimate of the Lipschitz parameter (default: 10.0)
::math::probopt::adaLipoMax function bounds args

The "adaptive Lipschitz optimisation" algorithm uses the "Lipschitz" property of the given function to find a maximum in the given bounding box. The adaptive variant actually uses two phases to find a suitable estimate for the Lipschitz parameter. This is controlled by the "Bernoulli" parameter.

When you specify a large number of iterations, the algorithm may take a very long time to complete as it is trying to improve on the Lipschitz parameter and the chances of hitting a better estimate diminish fast.

It recognises the following options:

  • -iterations          number: Number of iterations (equals the actual number of function evaluations, default: 100)
  • -bernoulli           value: Parameter for random decisions (exploration versus exploitation, default: 0.1)

References

The various algorithms have been described in on-line publications. Here are a few:

Keywords

mathematics, optimisation, probabilistic calculations

Category

Mathematics

Info

tcllib Tcl Math Library