NAG FL Interface
e05saf (bnd_pso)
Note: this routine uses optional parameters to define choices in the problem specification and in the details of the algorithm. If you wish to use default
settings for all of the optional parameters, you need only read Sections 1 to 10 of this document. If, however, you wish to reset some or all of the settings please refer to Section 11 for a detailed description of the algorithm and to Section 12 for a detailed description of the specification of the optional parameters.
1
Purpose
e05saf is designed to search for the global minimum or maximum of an arbitrary function, using Particle Swarm Optimization (PSO). Derivatives are not required, although these may be used by an accompanying local minimization routine if desired.
e05saf is essentially identical to
e05sbf, but with a simpler interface and with various optional parameters removed; otherwise most arguments are identical. In particular,
e05saf does not handle general constraints.
2
Specification
Fortran Interface
Subroutine e05saf ( |
ndim, npar, xb, fb, bl, bu, objfun, monmod, iopts, opts, iuser, ruser, itt, inform, ifail) |
Integer, Intent (In) |
:: |
ndim, npar |
Integer, Intent (Inout) |
:: |
iopts(*), iuser(*), ifail |
Integer, Intent (Out) |
:: |
itt(6), inform |
Real (Kind=nag_wp), Intent (In) |
:: |
bl(ndim), bu(ndim) |
Real (Kind=nag_wp), Intent (Inout) |
:: |
opts(*), ruser(*) |
Real (Kind=nag_wp), Intent (Out) |
:: |
xb(ndim), fb |
External |
:: |
objfun, monmod |
|
C Header Interface
#include <nag.h>
void |
e05saf_ (const Integer *ndim, const Integer *npar, double xb[], double *fb, const double bl[], const double bu[], void (NAG_CALL *objfun)(Integer *mode, const Integer *ndim, const double x[], double *objf, double vecout[], const Integer *nstate, Integer iuser[], double ruser[]), void (NAG_CALL *monmod)(const Integer *ndim, const Integer *npar, double x[], const double xb[], const double *fb, const double xbest[], const double fbest[], const Integer itt[], Integer iuser[], double ruser[], Integer *inform), Integer iopts[], double opts[], Integer iuser[], double ruser[], Integer itt[], Integer *inform, Integer *ifail) |
|
C++ Header Interface
#include <nag.h> extern "C" {
void |
e05saf_ (const Integer &ndim, const Integer &npar, double xb[], double &fb, const double bl[], const double bu[], void (NAG_CALL *objfun)(Integer &mode, const Integer &ndim, const double x[], double &objf, double vecout[], const Integer &nstate, Integer iuser[], double ruser[]), void (NAG_CALL *monmod)(const Integer &ndim, const Integer &npar, double x[], const double xb[], const double &fb, const double xbest[], const double fbest[], const Integer itt[], Integer iuser[], double ruser[], Integer &inform), Integer iopts[], double opts[], Integer iuser[], double ruser[], Integer itt[], Integer &inform, Integer &ifail) |
}
|
The routine may be called by the names e05saf or nagf_glopt_bnd_pso.
Before calling
e05saf,
e05zkf must be called with
optstr set to ‘
Initialize = e05saf’. Optional parameters may also be specified by calling
e05zkf before the call to
e05saf.
3
Description
e05saf uses a stochastic method based on Particle Swarm Optimization (PSO) to search for the global optimum of a nonlinear function
, subject to a set of bound constraints on the variables. In the PSO algorithm (see
Section 11), a set of particles is generated in the search space, and advances each iteration to (hopefully) better positions using a heuristic velocity based upon
inertia,
cognitive memory and
global memory. The inertia is provided by a decreasingly weighted contribution from a particles current velocity, the cognitive memory refers to the best candidate found by an individual particle and the global memory refers to the best candidate found by all the particles. This allows for a global search of the domain in question.
Further, this may be coupled with a selection of local minimization routines, which may be called during the iterations of the heuristic algorithm, the interior phase, to hasten the discovery of locally optimal points, and after the heuristic phase has completed to attempt to refine the final solution, the exterior phase. Different options may be set for the local optimizer in each phase.
Without loss of generality, the problem is assumed to be stated in the following form:
where the objective
is a scalar function,
is a vector in
and the vectors
are lower and upper bounds respectively for the
variables. The objective function may be nonlinear. Continuity of
is not essential. For functions which are smooth and primarily unimodal, faster solutions will almost certainly be achieved by using
Chapter E04 routines directly.
For functions which are smooth and multi-modal, gradient dependent local minimization routines may be coupled with e05saf.
For multi-modal functions for which derivatives cannot be provided, particularly functions with a significant level of noise in their evaluation,
e05saf should be used either alone, or coupled with
e04cbf.
The
lower and upper box bounds on the variable
are included to initialize the particle swarm into a finite hypervolume, although their subsequent influence on the algorithm is user determinable (see the option
Boundary in
Section 12). It is strongly recommended that sensible bounds are provided for all variables.
e05saf may also be used to maximize the objective function (see the option
Optimize).
Due to the nature of global optimization, unless a predefined target is provided, there is no definitive way of knowing when to end a computation. As such several stopping heuristics have been implemented into the algorithm. If any of these is achieved,
e05saf will exit with
, and the parameter
inform will indicate which criteria was reached. See
inform for more information.
In addition, you may provide your own stopping criteria through
monmod and
objfun.
e05sbf provides a comprehensive interface, allowing for the inclusion of general nonlinear constraints.
4
References
Gill P E, Murray W and Wright M H (1981) Practical Optimization Academic Press
Kennedy J and Eberhart R C (1995) Particle Swarm Optimization Proceedings of the 1995 IEEE International Conference on Neural Networks 1942–1948
Koh B, George A D, Haftka R T and Fregly B J (2006) Parallel Asynchronous Particle Swarm Optimization International Journal for Numerical Methods in Engineering 67(4) 578–595
Vaz A I and Vicente L N (2007) A Particle Swarm Pattern Search Method for Bound Constrained Global Optimization Journal of Global Optimization 39(2) 197–219 Kluwer Academic Publishers
5
Arguments
Note: for descriptions of the symbolic variables, see
Section 11.
-
1:
– Integer
Input
-
On entry: , the number of dimensions.
Constraint:
.
-
2:
– Integer
Input
-
On entry:
, the number of particles to be used in the swarm. Assuming all particles remain within bounds, each complete iteration will perform at least
npar function evaluations. Otherwise, significantly fewer objective function evaluations may be performed.
Suggested value:
.
Constraint:
, where num_threads is the value returned by the OpenMP environment variable OMP_NUM_THREADS, or num_threads is for a serial version of this routine.
-
3:
– Real (Kind=nag_wp) array
Output
-
On exit: the location of the best solution found, , in .
-
4:
– Real (Kind=nag_wp)
Output
-
On exit: the objective value of the best solution, .
-
5:
– Real (Kind=nag_wp) array
Input
-
6:
– Real (Kind=nag_wp) array
Input
-
On entry:
is
, the array of lower bounds,
bu is
, the array of upper bounds. The
ndim entries in
bl and
bu must contain the lower and upper simple (box) bounds of the variables respectively. These must be provided to initialize the sample population into a finite hypervolume, although their subsequent influence on the algorithm is user determinable (see the option
Boundary in
Section 12).
If
for any
, variable
will remain locked to
regardless of the
Boundary option selected.
It is strongly advised that you place sensible lower and upper bounds on all variables, even if your model allows for variables to be unbounded (using the option ) since these define the initial search space.
Constraints:
- , for ;
- for at least one .
-
7:
– Subroutine, supplied by the user.
External Procedure
-
objfun must, depending on the value of
mode, calculate the objective function
and/or calculate the gradient of the objective function for a
-variable vector
. Gradients are only required if a local minimizer has been chosen which requires gradients. See the option
Local Minimizer for more information.
The specification of
objfun is:
Fortran Interface
Integer, Intent (In) |
:: |
ndim, nstate |
Integer, Intent (Inout) |
:: |
mode, iuser(*) |
Real (Kind=nag_wp), Intent (In) |
:: |
x(ndim) |
Real (Kind=nag_wp), Intent (Inout) |
:: |
objf, vecout(ndim), ruser(*) |
|
C++ Header Interface
#include <nag.h> extern "C" {
}
|
-
1:
– Integer
Input/Output
-
On entry: indicates which functionality is required.
- should be returned in objf. The value of objf on entry may be used as an upper bound for the calculation. Any expected value of that is greater than objf may be approximated by this upper bound; that is objf can remain unaltered.
- only
First derivatives can be evaluated and returned in vecout. Any unaltered elements of vecout will be approximated using finite differences.
- only
must be calculated and returned in objf, and available first derivatives can be evaluated and returned in vecout. Any unaltered elements of vecout will be approximated using finite differences.
- must be calculated and returned in objf. The value of objf on entry may not be used as an upper bound.
- or only
All first derivatives must be evaluated and returned in vecout.
- or only
must be calculated and returned in objf, and all first derivatives must be evaluated and returned in vecout.
On exit: if the value of
mode is set to be negative,
e05saf will exit as soon as possible with
and
.
-
2:
– Integer
Input
-
On entry: the number of dimensions.
-
3:
– Real (Kind=nag_wp) array
Input
-
On entry: , the point at which the objective function and/or its gradient are to be evaluated.
-
4:
– Real (Kind=nag_wp)
Input/Output
-
On entry: the value of
objf passed to
objfun varies with the argument
mode.
- objf is an upper bound for the value of , often equal to the best value of found so far by a given particle. Only objective function values less than the value of objf on entry will be used further. As such this upper bound may be used to stop further evaluation when this will only increase the objective function value above the upper bound.
- , , , or
- objf is meaningless on entry.
On exit: the value of
objf returned varies with the argument
mode.
- objf must be the value of . Only values of strictly less than objf on entry need be accurate.
- or
- Need not be set.
- , or
- must be calculated and returned in objf. The entry value of objf may not be used as an upper bound.
-
5:
– Real (Kind=nag_wp) array
Input/Output
-
On entry: if
or
,
the values of
vecout are used internally to indicate whether a finite difference approximation is required. See
e04ucf/e04uca.
On exit: the required values of
vecout returned to the calling routine depend on the value of
mode.
- or
- The value of vecout need not be set.
- or
- vecout can contain components of the gradient of the objective function for some , or acceptable approximations. Any unaltered elements of vecout will be approximated using finite differences.
- or
- vecout must contain the gradient of the objective function for all . Approximation of the gradient is strongly discouraged, and no finite difference approximations will be performed internally (see e04dgf/e04dga and e04kzf).
-
6:
– Integer
Input
-
On entry:
nstate indicates various stages of initialization throughout the routine. This allows for permanent global arguments to be initialized the least number of times. For example, you may initialize a random number generator seed.
- SMP users only. objfun is called for the first time in a parallel region on a new thread other than the master thread. You may use this opportunity to set up any thread-dependent information in iuser and ruser.
- objfun is called for the very first time. You may save computational time if certain data must be read or calculated only once.
- objfun is called for the first time by a NAG local minimization routine. You may save computational time if certain data required for the local minimizer need only be calculated at the initial point of the local minimization.
- Used in all other cases.
-
7:
– Integer array
User Workspace
-
8:
– Real (Kind=nag_wp) array
User Workspace
-
objfun is called with the arguments
iuser and
ruser as supplied to
e05saf. You should use the arrays
iuser and
ruser to supply information to
objfun.
objfun must either be a module subprogram USEd by, or declared as EXTERNAL in, the (sub)program from which
e05saf is called. Arguments denoted as
Input must
not be changed by this procedure.
Note: objfun should not return floating-point NaN (Not a Number) or infinity values, since these are not handled by
e05saf. If your code inadvertently
does return any NaNs or infinities,
e05saf is likely to produce unexpected results.
-
8:
– Subroutine, supplied by the NAG Library or the user.
External Procedure
-
A user-specified monitoring and modification function.
monmod is called once every complete iteration after a finalization check. It may be used to modify the particle locations that will be evaluated at the next iteration. This permits the incorporation of algorithmic modifications such as including additional advection heuristics and genetic mutations.
monmod is only called during the main loop of the algorithm, and as such will be unaware of any further improvement from the final local minimization. If no monitoring and/or modification is required,
monmod may be the dummy monitoring routine
e05sxm. (
e05sxm is included in the NAG Library).
The specification of
monmod is:
Fortran Interface
Subroutine monmod ( |
ndim, npar, x, xb, fb, xbest, fbest, itt, iuser, ruser, inform) |
Integer, Intent (In) |
:: |
ndim, npar, itt(6) |
Integer, Intent (Inout) |
:: |
iuser(*), inform |
Real (Kind=nag_wp), Intent (In) |
:: |
xb(ndim), fb, xbest(ndim,npar), fbest(npar) |
Real (Kind=nag_wp), Intent (Inout) |
:: |
x(ndim,npar), ruser(*) |
|
C Header Interface
void |
monmod_ (const Integer *ndim, const Integer *npar, double x[], const double xb[], const double *fb, const double xbest[], const double fbest[], const Integer itt[], Integer iuser[], double ruser[], Integer *inform) |
|
C++ Header Interface
#include <nag.h> extern "C" {
void |
monmod_ (const Integer &ndim, const Integer &npar, double x[], const double xb[], const double &fb, const double xbest[], const double fbest[], const Integer itt[], Integer iuser[], double ruser[], Integer &inform) |
}
|
-
1:
– Integer
Input
-
On entry: the number of dimensions.
-
2:
– Integer
Input
-
On entry: the number of particles.
-
3:
– Real (Kind=nag_wp) array
Input/Output
-
Note: the th component of the th particle, , is stored in .
On entry: the
npar particle locations,
, which will currently be used during the next iteration unless altered in
monmod.
On exit: the particle locations to be used during the next iteration.
-
4:
– Real (Kind=nag_wp) array
Input
-
On entry: the location, , of the best solution yet found.
-
5:
– Real (Kind=nag_wp)
Input
-
On entry: the objective value, , of the best solution yet found.
-
6:
– Real (Kind=nag_wp) array
Input
-
Note: the th component of the position of the th particle's cognitive memory, , is stored in .
On entry: the locations currently in the cognitive memory,
, for
(see
Section 11).
-
7:
– Real (Kind=nag_wp) array
Input
-
On entry: the objective values currently in the cognitive memory,
, for .
-
8:
– Integer array
Input
-
On entry: iteration and function evaluation counters (see description of
itt below).
-
9:
– Integer array
User Workspace
-
10:
– Real (Kind=nag_wp) array
User Workspace
-
monmod is called with the arguments
iuser and
ruser as supplied to
e05saf. You should use the arrays
iuser and
ruser to supply information to
monmod.
-
11:
– Integer
Input/Output
-
On entry:
, where
thread_num is the value returned by a call of
x06adf. If running in serial this will always be zero.
On exit: setting
will cause near immediate exit from
e05saf. This value will be returned as
inform with
. You need not set
inform unless you wish to force an exit.
monmod must either be a module subprogram USEd by, or declared as EXTERNAL in, the (sub)program from which
e05saf is called. Arguments denoted as
Input must
not be changed by this procedure.
Note: monmod should not return floating-point NaN (Not a Number) or infinity values, since these are not handled by
e05saf. If your code inadvertently
does return any NaNs or infinities,
e05saf is likely to produce unexpected results.
-
9:
– Integer array
Communication Array
-
Note: the dimension of this array is dictated by the requirements of associated functions that must have been previously called. This array
must be the same array passed as argument
iopts in the previous call to
e05zkf.
On entry: optional parameter array as generated and possibly modified by calls to
e05zkf. The contents of
iopts must not be modified directly between calls to
e05saf,
e05zkf or
e05zlf.
-
10:
– Real (Kind=nag_wp) array
Communication Array
-
Note: the dimension of this array is dictated by the requirements of associated functions that must have been previously called. This array
must be the same array passed as argument
opts in the previous call to
e05zkf.
On entry: optional parameter array as generated and possibly modified by calls to
e05zkf. The contents of
opts must not be modified directly between calls to
e05saf,
e05zkf or
e05zlf.
-
11:
– Integer array
User Workspace
-
iuser is not used by
e05saf, but is passed directly to
objfun and
monmod and may be used to pass information to these routines.
With care, you may also write information back into
iuser. This might be useful, for example, should there be a need to preserve the state of a random number generator.
With SMP-enabled versions of
e05saf the array
iuser provided are classified as OpenMP shared memory. Use of
iuser has to take account of this in order to preserve thread safety whenever information is written back to either of these arrays.
-
12:
– Real (Kind=nag_wp) array
User Workspace
-
ruser is not used by
e05saf, but is passed directly to
objfun and
monmod and may be used to pass information to these routines.
With care, you may also write information back into
ruser. This might be useful, for example, should there be a need to preserve the state of a random number generator.
With SMP-enabled versions of
e05saf the array
ruser provided are classified as OpenMP shared memory. Use of
ruser has to take account of this in order to preserve thread safety whenever information is written back to either of these arrays.
-
13:
– Integer array
Output
-
On exit: integer iteration counters for
e05saf.
- Number of complete iterations.
- Number of complete iterations without improvement to the current optimum.
- Number of particles converged to the current optimum.
- Number of improvements to the optimum.
- Number of function evaluations performed.
- Number of particles reset.
-
14:
– Integer
Output
-
On exit: indicates which finalization criterion was reached. The possible values of
inform are:
inform | Meaning |
| Exit from a user-supplied subroutine. |
0 | e05saf has detected an error and terminated. |
1 | The provided objective target has been achieved. (Target Objective Value). |
2 | The standard deviation of the location of all the particles is below the set threshold (Swarm Standard Deviation). If the solution returned is not satisfactory, you may try setting a smaller value of Swarm Standard Deviation, or try adjusting the options governing the repulsive phase (Repulsion Initialize, Repulsion Finalize). |
3 | The total number of particles converged (Maximum Particles Converged) to the current global optimum has reached the set limit. This is the number of particles which have moved to a distance less than Distance Tolerance from the optimum with regard to the norm. If the solution is not satisfactory, you may consider lowering the Distance Tolerance. However, this may hinder the global search capability of the algorithm. |
4 | The maximum number of iterations without improvement (Maximum Iterations Static) has been reached, and the required number of particles (Maximum Iterations Static Particles) have converged to the current optimum. Increasing either of these options will allow the algorithm to continue searching for longer. Alternatively if the solution is not satisfactory, re-starting the application several times with may lead to an improved solution. |
5 | The maximum number of iterations (Maximum Iterations Completed) has been reached. If the number of iterations since improvement is small, then a better solution may be found by increasing this limit, or by using the option Local Minimizer with corresponding exterior options. Otherwise if the solution is not satisfactory, you may try re-running the application several times with and a lower iteration limit, or adjusting the options governing the repulsive phase (Repulsion Initialize, Repulsion Finalize). |
6 | The maximum allowed number of function evaluations (Maximum Function Evaluations) has been reached. As with , increasing this limit if the number of iterations without improvement is small, or decreasing this limit and running the algorithm multiple times with , may provide a superior result. |
-
15:
– Integer
Input/Output
-
On entry:
ifail must be set to
,
. If you are unfamiliar with this argument you should refer to
Section 7 in the Introduction to the NAG Library CL Interface for details.
On exit: the most common exit will be
.
For this reason, the value
is recommended. If the output of error messages is undesirable, the value
is recommended; otherwise, the recommended value is
.
When the value is used it is essential to test the value of ifail on exit.
e05saf will return
if and only if a finalization criterion has been reached which can guarantee success. This may only happen if the option
Target Objective Value has been set and reached at a point within the search domain. The finalization criterion
Target Objective Value is not activated using default option settings, and must be explicitly set using
e05zkf if required.
e05saf will return if no error has been detected, and a finalization criterion has been achieved which cannot guarantee success. This does not indicate that the routine has failed, merely that the returned solution cannot be guaranteed to be the true global optimum.
The value of
inform should be examined to determine which finalization criterion was reached.
Other positive values of
ifail indicate that either an error or a warning has been triggered. See
Sections 6,
7 and
11 for more information.
6
Error Indicators and Warnings
If on entry
or
, explanatory error messages are output on the current error message unit (as defined by
x04aaf).
Errors or warnings detected by the routine:
-
A finalization criterion was reached that cannot guarantee success.
On exit, .
-
If the option
Target Warning has been activated, this indicates that the
Target Objective Value has been achieved to specified tolerances at a sufficiently constrained point, either during the initialization phase, or during the first two iterations of the algorithm. While this is not necessarily an error, it may occur if:
-
(i)The target was achieved at the first point sampled by the routine. This will be the mean of the lower and upper bounds.
-
(ii)The target may have been achieved at a randomly generated sample point. This will always be a possibility provided that the domain under investigation contains a point with a target objective value.
-
(iii)If the Local Minimizer has been set, then a sample point may have been inside the basin of attraction of a satisfactory point. If this occurs repeatedly when the routine is called, it may imply that the objective is largely unimodal, and that it may be more efficient to use the routine selected as the Local Minimizer directly.
Assuming that
objfun is correct, you may wish to set a better
Target Objective Value, or a stricter
Target Objective Tolerance.
-
User requested exit
during call to
monmod.
User requested exit
during call to
objfun.
-
On entry, .
Constraint: .
-
On entry, .
Constraint: , where num_threads is the value returned by the OpenMP environment variable OMP_NUM_THREADS, or num_threads is for a serial version of this routine.
-
On entry, and .
Constraint: for all .
On entry, for all .
Constraint: for at least one .
-
Error occurred whilst adjusting to exterior local minimizer options.
Error occurred whilst adjusting to interior local minimizer options.
-
Either the option arrays have not been initialized for e05saf, or they have become corrupted.
-
Derivative checks indicate possible errors in the supplied derivatives.
Gradient checks may be disabled by setting .
-
Multiple SMP threads have been detected; however, the option
SMP Callback Thread Safe has not been set.
Set
if the provided callbacks are thread safe.
Set
if the provided callbacks are not thread safe, to force serial execution.
An unexpected error has been triggered by this routine. Please
contact
NAG.
See
Section 7 in the Introduction to the NAG Library FL Interface for further information.
Your licence key may have expired or may not have been installed correctly.
See
Section 8 in the Introduction to the NAG Library FL Interface for further information.
Dynamic memory allocation failed.
See
Section 9 in the Introduction to the NAG Library FL Interface for further information.
7
Accuracy
If
(or
) or
on exit, either a
Target Objective Value or finalization criterion has been reached, depending on user selected options. As with all global optimization software, the solution achieved may not be the true global optimum. Various options allow for either greater search diversity or faster convergence to a (local) optimum (See
Sections 11 and
12).
Provided the objective function and constraints are sufficiently well behaved, if a local minimizer is used in conjunction with e05saf, then it is more likely that the final result will at least be in the near vicinity of a local optimum, and due to the global search characteristics of the particle swarm, this solution should be superior to many other local optima.
Caution should be used in accelerating the rate of convergence, as with faster convergence, less of the domain will remain searchable by the swarm, making it increasingly difficult for the algorithm to detect the basin of attraction of superior local optima. Using the options
Repulsion Initialize and
Repulsion Finalize described in
Section 12 will help to overcome this, by causing the swarm to diverge away from the current optimum once no more local improvement is likely.
On successful exit with guaranteed success,
. This may only happen if a
Target Objective Value is assigned and is reached by the algorithm.
On successful exit without guaranteed success, is returned. This will happen if another finalization criterion is achieved without the detection of an error.
In both cases, the value of
inform provides further information as to the cause of the exit.
8
Parallelism and Performance
e05saf is threaded by NAG for parallel execution in multithreaded implementations of the NAG Library.
e05saf makes calls to BLAS and/or LAPACK routines, which may be threaded within the vendor library used by this implementation. Consult the documentation for the vendor library for further information.
Please consult the
X06 Chapter Introduction for information on how to control and interrogate the OpenMP environment used within this routine. Please also consult the
Users' Note for your implementation for any additional implementation-specific information.
The algorithm has been parallelized to allow for a high degree of asynchronicity between threads. Each thread is assigned a static number of the
npar particles requested, and performs a sub-iteration using these particles and a private copy of
. The thread only updates this private copy if a superior solution is found. In these implementations, this routine may make calls to the user-supplied functions from within an OpenMP parallel region. Thus OpenMP directives within the user functions can only be used if you are compiling the user-supplied function and linking the executable in accordance with the instructions in the
Users' Note for your implementation.
Once a thread has completed a sub-iteration, it enters a brief critical section where it compares this private to a globally accessible version. If either is superior, the inferior version is updated and the thread continues into a new sub-iteration.
Parallelizing the algorithm in this way allows for individual threads to continue searching even if other threads are completing sub-iterations in inferior times. The optional parameter
SMP Thread Overrun allows you to force a synchronization across the team of threads once one thread completes sufficiently more sub-iterations than the slowest thread. In particular, this may be used to force synchronization after every sub-iteration if so desired.
When using an SMP parallel version of this routine, you must indicate that the callback routines are thread safe by setting the optional parameter
SMP Callback Thread Safe before calling
e05saf in a multithreaded environment. See
Section 12.2 for more information on this and other SMP options.
Note: the stochastic method used in e05saf will not produce repeatable answers when run on multiple threads.
The memory used by e05saf is relatively static throughout. As such, e05saf may be used in problems with high dimension number () without the concern of computational resource exhaustion, although the probability of successfully locating the global optimum will decrease dramatically with the increase in dimensionality.
Due to the stochastic nature of the algorithm, the result will vary over multiple runs. This is particularly true if arguments and options are chosen to accelerate convergence at the expense of the global search. However, the option may be set to initialize the internal random number generator using a preset seed, which will result in identical solutions being obtained.
(For SMP users only) The option
will use preset seeds to initialize the random number generator on each thread, however due to the unpredictable nature of parallel communication, this cannot ensure repeatable results when running on multiple threads, even with
SMP Thread Overrun set to force synchronization every iteration.
10
Example
This example uses a particle swarm to find the global minimum of the Schwefel function:
In two dimensions the optimum is , located at .
The example demonstrates how to initialize and set the options arrays using
e05zkf, how to query options using
e05zlf, and finally how to search for the global optimum using
e05saf. The function is minimized several times to demonstrate using
e05saf alone, and coupled with local minimizers. This program uses the non-default option
to produce repeatable solutions.
Note: for users of multithreaded implementations of the NAG Library example program does not include the setting of the optional parameter
SMP Callback Thread Safe, and as such if run on multiple threads it will issue an error message. An additional example program,
e05safe_smp.f90, is included with the distribution material of all implementations of multithreaded implementations of the NAG Library to illustrate how to safely access independent subsections of the provided
iuser and
ruser arrays from multiple threads and how to use
e05zkf to set additional SMP threading related options.
10.1
Program Text
10.2
Program Data
None.
10.3
Program Results
11
Algorithmic Details
The following pseudo-code describes the algorithm used with the repulsion mechanism.
The definition of terms used in the above pseudo-code are as follows.
|
the number of particles, npar |
|
array of ndim lower box bounds |
|
array of ndim upper box bounds |
|
position of particle |
|
best position found by particle |
|
best position found by any particle |
|
|
|
, best value found by particle |
|
, best value found by any particle |
|
velocity of particle |
|
weight on for velocity update, decreasing according to Weight Decrease |
|
maximum absolute velocity, dependent upon Maximum Variable Velocity |
|
swarm iteration counter |
|
iterations since was updated |
|
diagonal matrices with random elements in range |
|
the cognitive advance coefficient which weights velocity towards , adjusted using Advance Cognitive |
|
the global advance coefficient which weights velocity towards , adjusted using Advance Global |
|
the Distance Tolerance for resetting a converged particle |
|
an array of random numbers whose th element is drawn from a uniform distribution in the range , for |
|
local optimizer interior options |
|
local optimizer exterior options |
|
apply local optimizer using the set of options using the solution as the starting point, if used (not default) |
monmod |
monitor progress and possibly modify |
BOUNDARY |
apply required behaviour for outside bounding box, (see Boundary) |
new () |
true if , , were updated at this iteration |
Additionally a repulsion phase can be introduced by changing from the default values of options
Repulsion Finalize (
),
Repulsion Initialize (
) and
Repulsion Particles (
). If the number of static particles is denoted
then the following can be inserted after the new(
) check in the pseudo-code above.
12
Optional Parameters
This section can be skipped if you wish to use the default values for all optional parameters, otherwise, the following is a list of the optional parameters available and a full description of each optional parameter is provided in
Section 12.1.
12.1
Description of the Optional Parameters
For each option, we give a summary line, a description of the optional parameter and details of constraints.
The summary line contains:
- the keywords;
- a parameter value,
where the letters , and denote options that take character, integer and real values respectively;
- the default value, where the symbol is a generic notation for machine precision (see x02ajf), and represents the largest representable integer value (see x02bbf).
All options accept the value ‘DEFAULT’ in order to return single options to their default states.
Keywords and character values are case insensitive, however they must be separated by at least one space.
For
e05saf the maximum length of the argument
cvalue used by
e05zlf is
.
Advance Cognitive | | Default |
The cognitive advance coefficient, . When larger than the global advance coefficient, this will cause particles to be attracted toward their previous best positions. Setting will cause e05saf to act predominantly as a local optimizer. Setting may cause the swarm to diverge, and is generally inadvisable. At least one of the global and cognitive coefficients must be nonzero.
Advance Global | | Default |
The global advance coefficient, . When larger than the cognitive coefficient this will encourage convergence toward the best solution yet found. Values will inhibit particles overshooting the optimum. Values cause particles to fly over the optimum some of the time. Larger values can prohibit convergence. Setting will remove any attraction to the current optimum, effectively generating a Monte Carlo multi-start optimization algorithm. At least one of the global and cognitive coefficients must be nonzero.
Boundary | | Default |
Determines the behaviour if particles leave the domain described by the box bounds. This only affects the general PSO algorithm, and will not pass down to any NAG local minimizers chosen.
This option is only effective in those dimensions for which , .
- IGNORE
- The box bounds are ignored. The objective function is still evaluated at the new particle position.
- RESET
- The particle is re-initialized inside the domain. and are not affected.
- FLOATING
- The particle position remains the same, however the objective function will not be evaluated at the next iteration. The particle will probably be advected back into the domain at the next advance due to attraction by the cognitive and global memory.
- HYPERSPHERICAL
- The box bounds are wrapped around an -dimensional hypersphere. As such a particle leaving through a lower bound will immediately re-enter through the corresponding upper bound and vice versa. The standard distance between particles is also modified accordingly.
- FIXED
- The particle rests on the boundary, with the corresponding dimensional velocity set to .
Distance Scaling | | Default |
Determines whether distances should be scaled by box widths.
- ON
- When a distance is calculated between and , a scaled norm is used.
- OFF
- Distances are calculated as the standard norm without any rescaling.
Distance Tolerance | | Default |
This is the distance, between particles and the global optimum which must be reached for the particle to be considered converged, i.e., that any subsequent movement of such a particle cannot significantly alter the global optimum. Once achieved the particle is reset into the box bounds to continue searching.
Constraint:
.
Function Precision | | Default |
The parameter defines , which is intended to be a measure of the accuracy with which the problem function can be computed. If or , the default value is used.
The value of
should reflect the relative precision of
; i.e.,
acts as a relative precision when
is large, and as an absolute precision when
is small. For example, if
is typically of order
and the first six significant digits are known to be correct, an appropriate value for
would be
. In contrast, if
is typically of order
and the first six significant digits are known to be correct, an appropriate value for
would be
. The choice of
can be quite complicated for badly scaled problems; see Chapter 8 of
Gill et al. (1981) for a discussion of scaling techniques. The default value is appropriate for most simple functions that are computed with full accuracy. However when the accuracy of the computed function values is known to be significantly worse than full precision, the value of
should be large enough so that no attempt will be made to distinguish between function values that differ by less than the error inherent in the calculation.
Local Boundary Restriction | | Default |
Contracts the box boundaries used by a box constrained local minimizer to,
, containing the start point
, where
Smaller values of
thereby restrict the size of the domain exposed to the local minimizer, possibly reducing the amount of work done by the local minimizer.
Constraint:
.
Local Interior Iterations | | |
Local Interior Major Iterations | | |
Local Exterior Iterations | | |
Local Exterior Major Iterations | | |
The maximum number of iterations or function evaluations the chosen local minimizer will perform inside (outside) the main loop if applicable. For the NAG minimizers these correspond to:
Unless set, these are functions of the parameters passed to e05saf.
Setting will disable the local minimizer in the corresponding algorithmic region. For example, setting and will cause the algorithm to perform no local minimizations inside the main loop of the algorithm, and a local minimization with upto iterations after the main loop has been exited.
Note: currently
e04jyf or
e04kzf are restricted to using
and
as function evaluation limits respectively. This applies to both local minimizations inside and outside the main loop. They may still be deactivated in either phase by setting
, and may subsequently be reactivated in either phase by setting
.
Constraint:
, .
Local Interior Tolerance | | Default |
Local Exterior Tolerance | | Default |
This is the tolerance provided to a local minimizer in the interior (exterior) of the main loop of the algorithm.
Constraint:
,.
Local Interior Minor Iterations | | |
Local Exterior Minor Iterations | | |
Where applicable, the secondary number of iterations the chosen local minimizer will use inside (outside) the main loop. Currently the relevant default values are:
Constraint:
, .
Local Minimizer | | Default |
Allows for a choice of
Chapter E04 routines to be used as a coupled, dedicated local minimizer.
- No local minimization will be performed in either the INTERIOR or EXTERIOR sections of the algorithm.
- Use e04cbf as the local minimizer. This does not require the calculation of derivatives.
On a call to
objfun during a local minimization,
.
- Use e04kzf as the local minimizer. This requires the calculation of derivatives in objfun, as indicated by mode.
The box bounds forwarded to this routine from
e05saf will have been acted upon by
Local Boundary Restriction. As such, the domain exposed may be greatly smaller than that provided to
e05saf.
Accurate derivatives must be provided to this routine, and will not be approximated internally. Each iteration of this local minimizer also requires the calculation of both the objective function and its derivative. Hence on a call to
objfun during a local minimization,
.
- Use e04jyf as the local minimizer. This does not require the calculation of derivatives.
On a call to
objfun during a local minimization,
.
The box bounds forwarded to this routine from
e05saf will have been acted upon by
Local Boundary Restriction. As such, the domain exposed may be greatly smaller than that provided to
e05saf.
- Use e04dgf/e04dga as the local minimizer.
Accurate derivatives must be provided, and will not be approximated internally. Additionally, each call to
objfun during a local minimization will require either the objective to be evaluated alone, or both the objective and its gradient to be evaluated. Hence on a call to
objfun,
or
.
- Use e04ucf/e04uca as the local minimizer.
This operates such that any derivatives of the objective function that you cannot supply, will be approximated internally using finite differences.
Either, the objective, objective gradient, or both may be requested during a local minimization, and as such on a call to
objfun,
,
or
.
The box bounds forwarded to this routine from
e05saf will have been acted upon by
Local Boundary Restriction. As such, the domain exposed may be greatly smaller than that provided to
e05saf.
Maximum Function Evaluations | | Default |
The maximum number of evaluations of the objective function. When reached this will return and .
Constraint:
.
Maximum Iterations Completed | | Default |
The maximum number of complete iterations that may be performed. Once exceeded e05saf will exit with and .
Unless set, this adapts to the parameters passed to e05saf.
Constraint:
.
Maximum Iterations Static | | Default |
The maximum number of iterations without any improvement to the current global optimum. If exceeded
e05saf will exit with
and
. This exit will be hindered by setting
Maximum Iterations Static Particles to larger values.
Constraint:
.
Maximum Iterations Static Particles | | Default |
The minimum number of particles that must have converged to the current optimum before the routine may exit due to
Maximum Iterations Static with
and
.
Constraint:
.
Maximum Particles Converged | | Default |
The maximum number of particles that may converge to the current optimum. When achieved, e05saf will exit with and . This exit will be hindered by setting ‘Repulsion’ options, as these cause the swarm to re-expand.
Constraint:
.
Maximum Particles Reset | | Default |
The maximum number of particles that may be reset after converging to the current optimum. Once achieved no further particles will be reset, and any particles within
Distance Tolerance of the global optimum will continue to evolve as normal.
Constraint:
.
Maximum Variable Velocity | | Default |
Along any dimension , the absolute velocity is bounded above by . Very low values will greatly increase convergence time. There is no upper limit, although larger values will allow more particles to be advected out of the box bounds, and values greater than may cause significant and potentially unrecoverable swarm divergence.
Constraint:
.
Optimize | | Default |
Determines whether to maximize or minimize the objective function.
- MINIMIZE
- The objective function will be minimized.
- MAXIMIZE
- The objective function will be maximized. This is accomplished by minimizing the negative of the objective.
Repeatability | | Default |
Allows for the same random number generator seed to be used for every call to
e05saf.
is recommended in general.
- OFF
- The internal generation of random numbers will be nonrepeatable.
- ON
- The same seed will be used.
Repulsion Finalize | | Default |
The number of iterations performed in a repulsive phase before re-contraction. This allows a re-diversified swarm to contract back toward the current optimum, allowing for a finer search of the near optimum space.
Constraint:
.
Repulsion Initialize | | Default |
The number of iterations without any improvement to the global optimum before the algorithm begins a repulsive phase. This phase allows the particle swarm to re-expand away from the current optimum, allowing more of the domain to be investigated. The repulsive phase is automatically ended if a superior optimum is found.
Constraint:
.
Repulsion Particles | | Default |
The number of particles required to have converged to the current optimum before any repulsive phase may be initialized. This will prevent repulsion before a satisfactory search of the near optimum area has been performed, which may happen for large dimensional problems.
Constraint:
.
Sets the random number generator seed to be used when
. If set to 0, the default seed will be used. If not, the absolute value of
Seed will be used to generate the random number generator seed.
Swarm Standard Deviation | | Default |
The target standard deviation of the particle distances from the current optimum. Once the standard deviation is below this level, e05saf will exit with and . This criterion will be penalized by the use of ‘Repulsion’ options, as these cause the swarm to re-expand, increasing the standard deviation of the particle distances from the best point.
In SMP parallel implementations of
e05saf, the standard deviation will be calculated based only on the particles local to the particular thread that checks for finalization. Considerably fewer particles may be used in this calculation than when the algorithm is run in serial. It is therefore recommended that you provide a smaller value of
Swarm Standard Deviation when running in parallel than when running in serial.
Constraint:
.
Target Objective | | Default |
Target Objective Value | | Default |
Activate or deactivate the use of a target value as a finalization criterion. If active, then once the supplied target value for the objective function is found (beyond the first iteration if
Target Warning is active)
e05saf will exit with
and
. Other than checking for feasibility only (
), this is the only finalization criterion that guarantees that the algorithm has been successful. If the target value was achieved at the initialization phase or first iteration and
Target Warning is active,
e05saf will exit with
. This option may take any real value
, or the character ON/OFF as well as DEFAULT. If this option is queried using
e05zlf, the current value of
will be returned in
rvalue, and
cvalue will indicate whether this option is ON or OFF. The behaviour of the option is as follows:
- Once a point is found with an objective value within the Target Objective Tolerance of , e05saf will exit successfully with and .
- OFF
- The current value of will remain stored, however it will not be used as a finalization criterion.
- ON
- The current value of stored will be used as a finalization criterion.
- DEFAULT
- The stored value of will be reset to its default value (), and this finalization criterion will be deactivated.
Target Objective Safeguard | | Default |
If you have given a target objective value to reach in
(the value of the optional parameter
Target Objective Value),
sets your desired safeguarded termination tolerance, for when
is close to zero.
Constraint:
.
Target Objective Tolerance | | Default |
The optional tolerance to a user-specified target value.
Constraint:
.
Target Warning | | Default |
Activates or deactivates the error exit associated with the target value being achieved before entry into the main loop of the algorithm, .
- OFF
- No error will be returned, and the routine will exit normally.
- ON
- An error will be returned if the target objective is reached prematurely, and the routine will exit with .
Verify Gradients | | Default |
Adjusts the level of gradient checking performed when gradients are required. Gradient checks are only performed on the first call to the chosen local minimizer if it requires gradients. There is no guarantee that the gradient check will be correct, as the finite differences used in the gradient check are themselves subject to inaccuracies.
- OFF
- No gradient checking will be performed.
- ON
- A cheap gradient check will be performed on both the gradients corresponding to the objective through objfun.
- OBJECTIVE
FULL
- A more expensive gradient check will be performed on the gradients corresponding to the objective objfun.
Weight Decrease | | Default |
Determines how particle weights decrease.
- OFF
- Weights do not decrease.
- INTEREST
- Weights decrease through compound interest as , where is the Weight Value and is the current number of iterations.
- LINEAR
- Weights decrease linearly following , where is the iteration number and is the maximum number of iterations as set by Maximum Iterations Completed.
Weight Initial | | Default |
The initial value of any particle's inertial weight, , or the minimum possible initial value if initial weights are randomized. When set, this will override or , and as such these must be set afterwards if so desired.
Constraint:
.
Weight Initialize | | Default |
Determines how the initial weights are distributed.
- INITIAL
- All weights are initialized at the initial weight, , if set. If Weight Initial has not been set, this will be the maximum weight, .
- MAXIMUM
- All weights are initialized at the maximum weight, .
- RANDOMIZED
- Weights are uniformly distributed in or if Weight Initial has been set.
Weight Maximum | | Default |
The maximum particle weight, .
Constraint:
(If has been set then .)
Weight Minimum | | Default |
The minimum achievable weight of any particle, . Once achieved, no further weight reduction is possible.
Constraint:
(If has been set then .)
Weight Reset | | Default |
Determines how particle weights are re-initialized.
- INITIAL
- Weights are re-initialized at the initial weight if set. If Weight Initial has not been set, this will be the maximum weight.
- MAXIMUM
- Weights are re-initialized at the maximum weight.
- RANDOMIZED
- Weights are uniformly distributed in or if Weight Initial has been set.
Weight Value | | Default |
The constant used with .
Constraint:
.
12.2
Description of the SMP optional parameters
This section details additional options available to users of multithreaded implementations of the NAG Library. In particular it includes the option
SMP Callback Thread Safe, which must be set before calling
e05saf with multiple threads.
SMP Callback Thread Safe | | Default |
Declare that the callback routines you provide are or are not thread safe. In particular, this indicates that access to the shared memory arrays
iuser and
ruser from within your provided callbacks is done in a thread safe manner. If these arrays are just used to pass constant data, then you may assume they are thread safe. If these are also used for workspace, or passing variable data such as random number generator seeds, then you must ensure these are accessed and updated safely. Whilst this can be done using OpenMP critical sections, we suggest their use is minimized to prevent unnecessary bottlenecks, and that instead individual threads have access to independent subsections of the provided arrays where possible.
- YES
- The callback routines have been programmed in a thread safe way. The algorithm will use OMP_NUM_THREADS threads.
- NO
- The callback routines are not thread safe. Setting this option will force the algorithm to run on a single thread only, and is advisable only for debugging purposes, or if you wish to parallelize your callback functions.
- WARNING
- This will cause an immediate exit from e05saf with if multiple threads are detected. This is to inform you that you have not declared the callback functions either to be thread safe, or that they are thread unsafe and you wish the algorithm to run in serial.
An additional example program,
e05safe_smp.f90, is included with the distribution material of multithreaded implementations of the NAG Library to illustrate how to safely access independent subsections of the provided
iuser and
ruser arrays from multiple threads.
SMP Local Minimizer External | | Default |
Determines how many threads will attempt to locally minimize the best found solution after the routine has exited the main loop.
- MASTER
- Only the master thread will attempt to find any improvement. The local minimization will be launched from the best known solution. All other threads will remain effectively idle.
- ALL
- The master thread will perform a local minimization from the best known solution, while all other threads will perform a local minimization from randomly generated perturbations of the best known solution, increasing the chance of an improvement. Assuming all local minimizations will take approximately the same amount of computation, this will be effectively free in terms of real time. It will however increase the number of function evaluations performed.
SMP Monitor | | Default |
Determines whether the user-supplied function
monmod is invoked once every sub-iteration each thread performs, or only once by a single thread after all threads have completed at least one sub-iteration.
- SINGLE
- Only one thread will invoke monmod, after all threads have performed at least one sub-iteration.
- ALL
- Each thread will invoke monmod each time it completes a sub-iteration. If you wish to alter x using monmod you should use this option, as monmod will only receive the arrays x, xbest and fbest private to the calling thread.
Determines how many threads support a particle subswarm. This is an extra collection of particles constrained to search only within a hypercube of edge length of the best point known to an individual thread. This may improve the number of iterations required to find a provided target, particularly if no local minimizer is in use.
If , then this will be disabled on all the threads.
If , then all the threads will support a particle subswarm.
SMP Thread Overrun | | Default |
This option provides control over the level of asynchronicity present in a simulation. In particular, a barrier synchronization between all threads is performed if any thread completes sub-iterations more than the slowest thread, causing all threads to be exposed to the current best solution. Allowing asynchronous behaviour does however allow individual threads to focus on different global optimum candidates some of the time, which can inhibit convergence to unwanted sub-optima. It also allows for threads to continue searching when other threads are completing sub-iterations at a slower rate.
If , the algorithm will force a synchronization between threads at the end of each iteration.