scheduleSPSANN: *spsann* annealing schedule

In samuel-rosa/spsann: Optimization of Spatial Samples via Simulated Annealing

spsann annealing schedule

Description

Set the control parameters of the annealing schedule.

Usage

scheduleSPSANN(
  initial.temperature = 0.001,
  chains = 500,
  x.max,
  x.min = 0,
  y.max,
  y.min = 0,
  cellsize,
  stopping = ceiling(chains * 0.5),
  chain.length = 1,
  temperature.decrease = 0.95,
  initial.acceptance = c(0.95, 0.99)
)

Arguments

initial.temperature	Numeric value larger than zero (0) defining the initial temperature of the system. A low initial.temperature, combined with a low initial.acceptance results in the optimization algorithm to behave as a greedy optimization algorithm, i.e. only better system configurations are accepted. Defaults to initial.temperature = 0.001.
chains	Integer value defining the maximum number of Markov chain, i.e. the number of cycles of jitters at which the temperature and the size of the neighbourhood should be kept constant. Defaults to chains = 500.
x.max, x.min, y.max, y.min	Numeric value defining the minimum and maximum quantity of random noise to be added to the Cartesian x- and y-coordinates. The units are the same as of the Cartesian x- and y-coordinates. If missing, they are estimated from candi – or eval.grid, in case a coarser evaluation grid is used –, x.min and y.min being set to zero, and x.max and y.max being set to half the maximum distance in the Cartesian x- and y-coordinates, respectively.
cellsize	Vector with two positive numeric values defining the spacing in the x- and y-coordinates between the candidate locations in candi, i.e. the grid resolution. A single value can be used if the spacing in the x- and y-coordinates is the same. If cellsize = 0 then a finite set of candidate locations is used (See Details).
stopping	Integer value defining the maximum allowable number of Markov chains without improvement of the objective function value. Defaults to stopping = ceiling(chains * 0.5), i.e. fifty percent the maximum number of chains.
chain.length	Integer value larger than zero (0) defining the length of each Markov chain relative to the number of samples. Defaults to chain.length = 1, i.e. one time the number of samples.
temperature.decrease	Numeric value between zero (0) and one (1) used as a multiplying factor to decrease the temperature at the end of each Markov chain. Defaults to temperature.decrease = 0.95. (Advanced users only!)
initial.acceptance	(Optional) Vector with two positive numeric values between zero (0) and one (1) defining the minimum and maximum initial acceptance probabilities. The initial acceptance probability is the proportion of candidate spatial sample configurations that should be accepted in the first Markov chain. The optimization is stopped and a warning is issued if the value is not within the predefined range. Defaults to initial.acceptance = c(0.95, 0.99). (Advanced users only!)

Details

Generating mechanism

There are multiple mechanism to generate a new sample configuration out of an existing one. The main step consists of randomly perturbing the coordinates of a single sample, a process known as ‘jittering’. These mechanisms can be classified based on how the set of candidate locations for the samples is defined. For example, one could use an infinite set of candidate locations, that is, any location in the spatial domain can be selected as a new sample location after a sample is jittered. All that is needed is a polygon indicating the boundary of the spatial domain. This method is more computationally demanding because every time an existing sample is jittered, it is necessary to check if the new sample location falls in spatial domain.

Another approach consists of using a finite set of candidate locations for the samples. A finite set of candidate locations is created by discretising the spatial domain, that is, creating a fine (regular) grid of points that serve as candidate locations for the jittered sample. This is a less computationally demanding jittering method because, by definition, the new sample location will always fall in the spatial domain.

Using a finite set of candidate locations has two important inconveniences. First, not all locations in the spatial domain can be selected as the new location for a jittered sample. Second, when a sample is jittered, it may be that the new location already is occupied by another sample. If this happens, another location has to be iteratively sought for, say, as many times as the size of the sample configuration. In general, the larger the size of the sample configuration, the more likely it is that the new location already is occupied by another sample. If a solution is not found in a reasonable time, the the sample selected to be jittered is kept in its original location. Such a procedure clearly is suboptimal.

spsann uses a more elegant method which is based on using a finite set of candidate locations coupled with a form of two-stage random sampling as implemented in spcosa::spsample(). Because the candidate locations are placed on a finite regular grid, they can be taken as the centre nodes of a finite set of grid cells (or pixels of a raster image). In the first stage, one of the “grid cells” is selected with replacement, i.e. independently of already being occupied by another sample. The new location for the sample chosen to be jittered is selected within that “grid cell” by simple random sampling. This method guarantees that virtually any location in the spatial domain can be selected. It also discards the need to check if the new location already is occupied by another sample, speeding up the computations when compared to the first two approaches.

Annealing schedule

The search graph corresponds to the set of effective candidate locations for a sample location selected to be jittered. The size of the search graph, i.e. area within which a sample location can be moved around, is related to the concept of temperature. A larger search graph is equivalent to higher temperatures, which potentially result in more movement – or ‘agitation’ – of the set of sample locations.

The current version of the spsann-package uses a linear cooling schedule which depends upon the number of jitters to control the size of the search graph. The equations are

x_max = x_max0 - (chains_i / chains) * (x_max0 - x_min) + x_cellsize + x_min0

and

y_max = y_max0 - (chains_i / chains) * (y_max0 - y_min) + y_cellsize + y_min0,

where $x_max0$ and $y_max0$ are the maximum allowed shifts in the x- and y-coordinates in the first chain, $x_min$ and $y_min$ are the minimum required shifts in the x- and y-coordinates, $x_max$ and $y_max$ are the maximum allowed shifts in the x- and y-coordinates during the next chain, $chains$ and $chain_i$ are the total and current chains, and $x_cellsize$ and $y_cellsize$ are the grid spacing in the x- and y-coordinates. Because $x_cellsize$ and $y_cellsize$ can be equal to zero when a finite set of candidate locations is used, $x_min0$ and $y_min0$ are the maximum nearest neighbour distance in the x- and y-coordinates between candidate locations.

Value

A list with a set of control parameters of the annealing schedule.

Note

Distance between two points

spsann always computes the distance between two locations (points) as the Euclidean distance between them. This computation requires the optimization to operate in the two-dimensional Euclidean space, i.e. the coordinates of the sample, candidate and evaluation locations must be Cartesian coordinates, generally in metres or kilometres. spsann has no mechanism to check if the coordinates are Cartesian: you are the sole responsible for making sure that this requirement is attained.

Author(s)

Alessandro Samuel-Rosa [e-mail]

References

Aarts, E. H. L.; Korst, J. H. M. Boltzmann machines for travelling salesman problems. _European Journal of Operational Research_S, v. 39, p. 79-95, 1989.

Černý, V. Thermodynamical approach to the travelling salesman problem: an efficient simulation algorithm. Journal of Optimization Theory and Applications, v. 45, p. 41-51, 1985.

Brus, D. J.; Heuvelink, G. B. M. Optimization of sample patterns for universal kriging of environmental variables. Geoderma, v. 138, p. 86-95, 2007.

Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P. Optimization by simulated annealing. Science, v. 220, p. 671-680, 1983.

Metropolis, N.; Rosenbluth, A. W.; Rosenbluth, M. N.; Teller, A. H.; Teller, E. Equation of state calculations by fast computing machines. The Journal of Chemical Physics, v. 21, p. 1087-1092, 1953.

van Groenigen, J.-W.; Stein, A. Constrained optimization of spatial sampling using continuous simulated annealing. Journal of Environmental Quality. v. 27, p. 1078-1086, 1998.

Webster, R.; Lark, R. M. Field sampling for environmental science and management. London: Routledge, p. 200, 2013.

See Also

optimACDC, optimCORR, optimDIST, optimMKV, optimMSSD, optimPPL, optimSPAN, optimUSER.

Examples

#####################################################################
# NOTE: The settings below are unlikely to meet your needs.         #
#####################################################################
schedule <- scheduleSPSANN(initial.temperature = 100, cellsize = 30)

samuel-rosa/spsann documentation built on Nov. 6, 2023, 12:48 p.m.