bijective dif-
nsions. They
a kernel pro-
ind abs -jacobian
rd kernel, the
.
X EB
only used to
ext where the
composed as
bjects binary
e thus tightly
uration is a
ffers vector_-
ion models.
he latter em-
and non-zero
s.
ble to provide
Marked Point
pes) are sup-
of objects as
1 this context,
ts have them
ig function so
stic.
'orts energies
Ja) energies:
y) Q)
2010)
inary)
»ctor flow
section
ergy models
rea(xNy) by
inary_energy(),
lary energy
ibution is de-
ampler, which
r each object
niform object
les.
3.34 Accelerator Concept When queried with a configu-
ration c and an object x, an accelerator provides a subset of the
set of objects in c that interact with x (i.e. that have a non-zero
binary energy with it). If the binary energy becomes null or neg-
ligible when objects are further apart than a given threshold, an
accelerator may only report objects that intersect a suitable ball
centered on the query object x. Further releases of the library
may include accelerators based for instance on quad-trees, uni-
form grids or Kd-trees. However, the only model of this concept
is currently the trivial_accelerator that returns the whole range
of objects of the query configuration.
335 MPP Kernels For efficiency, the energy evolution AU
of the modifications proposed by the kernels must be easy to com-
pute. Thus MPP Kernels usually only delete and/or insert a small
number of objects. A Modification class thus keeps a vector
of iterators to the death-proposed objects and a vector of birth-
proposed new objects. The simplest MPP kernels that are suffi-
cient for convergence are provided: RIMCMC:uniform birth kernel
and its reverse kernel RJMCMC::uniform death kernel.
3.4 Simulated Annealing Concepts
The main simulated annealing function is the following free func-
tion that performs the optimization loop until the convergence
EndTest succeeds, advancing the temperature Schedule and calling
the visitor functor at each iteration:
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Volume XXXIX-B3, 2012
XXII ISPRS Congress, 25 August — 01 September 2012, Melbourne, Australia
3.4.2 EndTest concept Models of the EndTest concept pro-
vide a simple predicate that informs the simulated annealing frame-
work that the process has converged or whatever reason requiring
to stop the simulated annealing iterations, such as a user-issued
cancellation. The only requirements of this concept is to provide
the following member function:
template«tvpename Configuration, typename Sampler
bool operator()(const Configuration& configuration,
const Sampler& sampler, double temperature);
template< class Configuration, class Sampler,
class Schedule, class EndTest, ciass Visitor >
void simulated annealing::optimize(
Configuration& config, Sampler& sampler,
Schedule& schedule, EndTest& end test, Visitor& vis)
double t = «schedule;
visitor.begin(config,sampler,t);
for(; lend test(config,sampler,t); t - x(++schedule ))
sampler(config,t y
visitor.visit(config,sampler,t);
}
visitor.end(config,sampler,t);
Provided models are max_iteration_end_test that fails after a given
number of iterations and delta_energy_end_test that fails after a
given number of iterations without energy change. They may be
combined using the composite end test model.
Available EndTest Models
max iteration end test i 2 na
delta_energy_end_test Vi >t—-7, AU; =0
composite_end_test< Lo, EA, pom or( Eo(), Ei () en)
3.4.8 Visitorconcept Visitorsarehighly customizable ob-
jects passed to the simulated annealing process. They may be
used to visualize or to gather statistics on the current state of
the optimization. Available models offer console (figure 1) or
GUI (based on Gilviewer and WxWidgets, figure 2) feedback, or
shapefile saving of the current configuration. They may be com-
bined using a composite_visitor. This extensibility mechanism
offer the possibility to compile the same RIMCMC code with
a GUI to build intuition and monitor the running algorithm and
without for batch timing purposes.
34.1 Schedule concept Models of the Schedule concept
are responsible for providing the evolution of the temperature
throughout the simulated annealing process. The Schedule con-
cept is a refinement of the Inputlicrator concept of the C++ Stan-
dard Template Library.
Available Schedule Models
geometric_schedule Tr = at To
; 3 em To
logarithmic schedule n = logo (20
inverse linear schedule + = #— +tAT
step schedule« T" d Ti;
Whereas the 1ogarithmic schedule is the one that ensures conver-
gence (Descombes, 2011), the geonetric schedule is usually used
instead in practice for computational efficiency. The step_schedule
wraps another schedule to offer constant temperature periods of
T iterations, enabling statistics computation through a visitor.
The evaluation of a suitable initial temperature is not trivial. On
the one hand, too high a temperature will unnecessarily prolong
the initial phase of the simulated annealing where the sampling is
unbiased by the target distribution. On the other hand, too low a
temperature prevents the exploration of the whole configuration
space and results in the convergence to a local minimum only.
(Salamon et al., 2002) suggests considering an estimation of the
variance of the energy of configurations sampled according to the
reference process to estimate the initial temperature. The corre-
sponding saiamon initial schedule Tp estimation function is pro-
vided, which performs well in the absence of hardcore energy
terms.
template«typename Configuration, typename Sampler
void begin(const Configuration& configuration,
const Sampler& sampler, double temperature);
template«typename Configuration, typéname Sampler
void visit(const Configuration& configuration,
const Sampler& sampler, double temperature);
template«typename Configuration, iypename Sampler>
255
void end(const Configuration& configuration,
const Sampler& sampler, double temperature);
4 SAMPLES
4.1 Circle packing
This section details a simple example use of the 1ibrjmcmc li-
brary. The goal is to find a set of circles that minimizes a simple
objective function. Each circle center lie in the unit square and
its radius is constrained in an interval [rmin; Tmaz]. Notice that
the cardinality of set itself is unknown. The minimized function
awards a negative constant value for each circle and penalizes ev-
ery pair of overlapping circles by its intersection area. Basically,
it tries to pack as many circles as possible into the unit square
while minimizing their overlap. First, one needs to define the ob-
ject type of the MPP, with all its geometric methods. Then, the
object container is defined as well as an objective function as the
sum of a unary term for each object and a binary term for each
pair of objects. The set of objects is then probabilized using a
Poisson reference process and uniform birth. A basic birth and
death RIMCMC sampler is then defined to enable the sampling
of the MPP relative to the Poisson reference process, modulated
by the score of the objective function and a temperature parame-
ter. Then header files relative to the optimization of the objective
function are included. A sufficiently slow temperature decrease
morphs the probability distribution function from the one of the
reference process to a combination of Dirac masses at the global
mimima of the objective function, thus achieving its minimiza-
tion. A geometric scheduling of the temperature decrease is sub-
optimal but is more practical and thus more commonly used.