Package com.graphhopper.jsprit.core.algorithm.acceptor

Class SchrimpfAcceptance

java.lang.Object
com.graphhopper.jsprit.core.algorithm.acceptor.SchrimpfAcceptance
All Implemented Interfaces:
SolutionAcceptor, AlgorithmStartsListener, IterationStartsListener, VehicleRoutingAlgorithmListener
public class SchrimpfAcceptance extends Object implements SolutionAcceptor, IterationStartsListener, AlgorithmStartsListener
ThresholdAcceptance-Function defined by Schrimpf et al. (2000).

The idea can be described as follows: Most problems do not only have one unique minimum (maximum) but a number of local minima (maxima). To avoid to get stuck in a local minimum at the beginning of a search this threshold-acceptance function accepts also worse solution at the beginning (in contrary to a greedy approach which only accepts better solutions), and converges to a greedy approach at the end.
The difficulty is to define (i) an appropriate initial threshold and (ii) a corresponding function describing how the threshold converges to zero, i.e. the greedy threshold.

ad i) The initial threshold is determined by a random walk through the search space. The random walk currently runs with the following algorithm: src/main/resources/randomWalk.xml. It runs as long as it is specified in nuOfWarmupIterations. In the first iteration or walk respectively the algorithm generates a solution. This solution in turn is the basis of the next walk yielding to another solution value ... and so on. Each solution value is memorized since the initial threshold is essentially a function of the standard deviation of these solution values. To be more precise: initial threshold = stddev(solution values) / 2.

ad ii) The threshold of iteration i is determined as follows: threshold(i) = initialThreshold * Math.exp(-Math.log(2) * (i / nuOfTotalIterations) / alpha) To get a better understanding of the threshold-function go to Wolfram Alpha and plot the following line (just copy and paste it into Wolfram's console: www.wolframalpha.com):

100. * exp(-log(2)* (x/1000) / 0.1) (x from 0 to 1000) (y from 0 to 100)

with
initialThreshold = 100
nuOfTotalIter = 1000
alpha = 0.1
x corresponds to i iterations and
y to the threshold(i)

Gerhard Schrimpf, Johannes Schneider, Hermann Stamm- Wilbrandt, and Gunter Dueck (2000). Record breaking optimization results using the ruin and recreate principle. Journal of Computational Physics, 159(2):139 – 171, 2000. ISSN 0021-9991. doi: 10.1006/jcph.1999. 6413. URL http://www.sciencedirect.com/science/article/ pii/S0021999199964136

Author:
schroeder