annealing_solver {mwcsr} | R Documentation |
Construct an annealing solver
Description
Simulated annealing is a heuristic method of solving optimization problems. Typically, it allows to find some good solution in a short time. This implementation doesn't compute any upper bound on solution, so there is no guarantee of optimality of solution provided.
Usage
annealing_solver(
schedule = c("fast", "boltzmann"),
initial_temperature = 1,
final_temperature = 1e-06,
verbose = FALSE
)
Arguments
schedule |
boltzmann annealing or fast annealing |
initial_temperature |
initial value for the temperature |
final_temperature |
final value for the temperature |
verbose |
whether be verbose or not |
Details
Algorithm maintains connected subgraph staring with empty subgraph. Each iteration one random action is considered. It may be a removal of a vertex or an edge which does not separate graph or addition of an extra vertex or an edge neighboring existing graph. If the subgraph is empty all vertices are considered as candidates to form a subgaph. After candidate is chosen two subgraph scores are considered: for a new subgraph and for an old one. Simulated annealing operates with a notion of temperature. The candidate action is accepted with probability: p(S'|S) = exp(-E / T), where E is weight difference between subgraphs and T is current temperature.
Temperature is calculated in each iteration. in mwcsr
there are two
temperature schedules supported. So called Boltmann annealing uses the formula:
T(k) = T0 / (ln(1 + k)), while in case of fast annealing this one is used:
T(k) = T0 / k, where k is iteration number.
To tune the algorithm it is useful to realize how typical changes in the goal function for single actions are distributed. Calculating the acceptance probabilities at initial temperature and final temperatures may help to choose schedule and temperatures.
Value
An object of class mwcs_solver
See Also
rnc_solver will probably be a better choice with minimal tuning necessary