optimiseSD_ssa: Spatial Simulated Annealing optimisation algorithm

Description

Runs Spatial Simulated Annealing (SSA) optimisation for a given Simulations object and cost function. The aim is a cost value. The algorithm moves the initial sensors to reach the aim. In each iteration SSA moves one or more sensors randomly within their neighbourhood; the size of shifts decreases during the run. If a movement decreases cost, it is accepted. Else it may be accepted, too: the decision is random, with higher probability for acceptance in the beginning of the run and if the move increases cost only little. Acceptance of worse results helps to escape from local optima

Usage

optimiseSD_ssa(simulations, costFun,
  locationsAll = 1:nLocations(simulations), locationsFix = integer(0),
  locationsInitial = integer(0),
  aimCost = NA, aimNumber = NA,
  nameSave = NA, plot = FALSE, verbatim = FALSE,
  maxShiftNumber = length(locationsInitial), startMoveProb = 0.5,
  maxShiftFactor = 0.2, minShiftFactor = 0.01,
  maxIterations = 5000, maxStableIterations = 500,
  maxIterationsJumpBack = maxStableIterations - 1,
  acceptanceMethod = "vanGroenigen",
  start_acc_vG = 0.5, end_acc_vG = 0.0001, 
  cooling_vG = 0.999, startAcceptance_vG = 0.5,
  start_acc_iI = 0.2
  )

Arguments

simulations

*

costFun

*

locationsAll

*

locationsFix

*

locationsInitial

*

aimCost

*

aimNumber

*; if no locationsInitial given, it starts from this number of random locations

nameSave

*

plot

not yet implemented

verbatim

if more output is to be written to the console

maxShiftNumber

how many of the sensors can maximally be shifted in each iteration

startMoveProb

initial probability to move sensors -in any case at least one sensor is moved

maxShiftFactor

initial maximal size of shifts (as fraction of extent)

minShiftFactor

final maximal size of shifts (as fraction of extent)

maxIterations

maximal number of iterations (iteration means tried sensor changes, not all are accepted)

maxStableIterations

it stops after this number of iterations in a row without improvement

maxIterationsJumpBack

if for this number of iterations the best result is not improved, the sampling design jumps back to the last best design; by default this does not occur

acceptanceMethod

formula to compute probability to accept worse result: for "vanGroenigen" acceptance decreases relative to worsening, for "intamapInteractive" it does not; for both probability of acceptance decreases during the run

start_acc_vG

acceptance worse results in first iteration (for acceptanceMethod = "vanGroenigen")

end_acc_vG

acceptance of worse results in maxIterations-th iteration (for acceptanceMethod = "vanGroenigen")

cooling_vG

cooling parameter (for acceptanceMethod = "vanGroenigen"), see details

startAcceptance_vG

second cooling parameter (for acceptanceMethod = "van Groenigen"), see details

start_acc_iI

calibration factor of acceptance for acceptanceMethod = "intamapInteractive" (equals start_p in ssaOptim in package intamapInteractive), see details

Value

A list A list, the first two entries are common to all optimisation algorithms, they are marked with *, see optimiseSD for details.

* best sampling designs

evaluation

* cost and size of SD

report

a list of SD_final: final sampling design (not necessarily best, including locationsFix) SD_best: best sampling design ever found (including locationsFix), same as SD[[1]] cost_final: cost of SD_final cost_best: cost of SD_best iterations: data.frame with columns cost and accepted, rows refer to iterations.

If verbatim = TRUE more information is returned in report: The iterations has additional columns: costTest (cost of the design tested in this iteration, no matter if it was accepted; cost refers to the currently accepted design); costBest (best cost until then); chi (random value that was used for the acceptance decision).

In addition it returns a matrix each for SDs, SDs_test, SDs_test with the current, tested and best known sampling designs of all iterations.

If acceptanceMethod = "vanGroenigen" it returns the cooling parameters cooling and startAcceptance as they may be computed inside the algorithm.

It gives the iterations with jumpBack i.e. when the current sampling design was replaced by the known best.

Details

In general the function is used within the wrapper optimiseSD. The following parameters are specific to optimiseSD_ssa: maxShiftNumber, startMoveProb, maxShiftFactor, minShiftFactor, maxIterations, maxStableIterations, maxIterationsJumpBack, acceptanceMethod, start_acc_vG, end_acc_vG, cooling_vG, startAcceptance_vG, start_acc_iI. They may be changed beforehand via replaceDefault with type = "optimisationFun.optimiseSD"; all other parameters are forwarded from optimiseSD.

In one iteration more than one sensor may be moved: first maxShiftNumber sensors are selected; for each of them, probability to move it is \(startMoveProb * (1 - k / maxIterations)\) where \(k\) indicates the iteration; only the first is moved in any case. The decision if the movement is accepted refers to the common movement of all finally selected sensors. Moving many sensors allows for big changes, it can be useful if initial sensors are supposed to be far from the optimum.

maxShiftFactor and minShiftFactor are given as fractions of the extent. If the underlying spatial object of the simulations is gridded, a shift size below cellsize would not allow any shifts. Therefore in this case it is set to at least cell size (independently in both coordinates).

Acceptance of worse results for acceptanceMethod = "vanGroenigen" is \(exp((costOld - costCurrent) / (startAcceptance * cooling ^ k)\). This means it is higher for small cost difference and decreases with iteration k. You may set the parameters cooling_vG and startAcceptance_vG directly - to achieve this, set either start_acc_vG or end_acc_vG to NULL. However, start_acc_vG and end_acc_vG provide a more intuitive way to define acceptance: the algorithm computes the median cost difference when moving one sensor randomly or within the close neighbourhood (to next point) and adjusts cooling and startAcceptance to achieve the indicated acceptance rates. For acceptanceMethod = "intamapInteractive" acceptance of worse results is \(start_acc_iI * exp(-10 * k / maxIterations)\). It is the same no matter how much worse the new design is, it just decreases with iteration k.

Examples

Run this code

# NOT RUN {
# the function is to be used inside of optimiseSD
# change parameters
optimSD_ssa1 = replaceDefault(
  optimiseSD_ssa,  newDefaults = list(
    start_acc_vG = 0.1,
    aimCost = 0,
    verbatim = TRUE,
    maxIterations = 3000,
    maxStableIterations = 500,
    maxIterationsJumpBack = 200
  ),
  type = "optimisationFun.optimiseSD")[[1]]

# load data
demo(radioactivePlumes_addProperties)
# define possible, fix, and initial sensors
I = nLocations(radioactivePlumes)
set.seed(22347287)
locDel3 = sample.int(I, 5)
locKeep3 = sample(setdiff(1:I, locDel3), 10)
locAll3 = c(sample(setdiff(1:I,
  c(locDel3, locKeep3)), 10), locDel3)


costInitial1 = multipleDetection(simulations = radioactivePlumes,
  locations = c(locKeep3, locDel3))

# run optimisation
# }
# NOT RUN {
## takes some time
SDssa = optimiseSD(
  simulations = radioactivePlumes,
  costFun = multipleDetection,
  locationsAll = setdiff(1:nLocations(radioactivePlumes), c(locKeep3, locAll3)),
  locationsFix = locKeep3,
  locationsInitial = locDel3,
  aimCost = 0.05 * costInitial1[[1]],
  aimNumber = length(locDel3) + length(locKeep3),
  optimisationFun = optimSD_ssa1
)
# }
# NOT RUN {
## this result is also in data(SDssa)

# visualise
data(SDssa)
## cost curve
optimisationCurve(optSD = SDssa, type = "ssa")
## designs
singleDet = replaceDefault(singleDetection, 
  newDefaults = list(plot = TRUE), type = "costFun.optimiseSD")[[1]]
plotSD(radioactivePlumes, 
  SD = SDssa[[1]],
  locationsFix = locKeep3, 
  locationsInitial = locDel3, 
  locationsAll = setdiff(1:nLocations(radioactivePlumes), c(locKeep3, locAll3)),
  costMap = singleDet
)
# }

Run the code above in your browser using DataLab