optimiseSD_ssa: Spatial Simulated Annealing optimisation algorithm
In sensors4plumes: Test and Optimise Sampling Designs Based on Plume Simulations

Description Usage Arguments Details Value Author(s) Examples

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

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
  )

Some arguments are the same for all optimisation algorithms, they are marked by a *, for detail see optimiseSD. Others are directly forwarded to rbga.bin, they are marked by **

`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

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.

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

SD

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

Kristina B. Helle, kristina.helle@uni-muenster.de

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

## End(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
)