package cz.logio.jsprit.simulator;
import com.graphhopper.jsprit.core.algorithm.SearchStrategy;
import com.graphhopper.jsprit.core.algorithm.VehicleRoutingAlgorithm;
import com.graphhopper.jsprit.core.algorithm.listener.AlgorithmStartsListener;
import com.graphhopper.jsprit.core.algorithm.listener.IterationStartsListener;
import com.graphhopper.jsprit.core.algorithm.termination.PrematureAlgorithmTermination;
import com.graphhopper.jsprit.core.problem.VehicleRoutingProblem;
import com.graphhopper.jsprit.core.problem.solution.VehicleRoutingProblemSolution;
import org.apache.commons.math3.stat.StatUtils;
import org.apache.commons.math3.stat.descriptive.moment.StandardDeviation;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import java.util.Collection;
import java.util.Deque;
import java.util.LinkedList;
public class OptimalSolutionTermination implements
PrematureAlgorithmTermination, AlgorithmStartsListener, IterationStartsListener {
private static final Logger log = LoggerFactory.getLogger(OptimalSolutionTermination.class);
private static final int MEMORY_SIZE = 20;
private static final double VARIATION_THRESHOLD = 0.015;
private static final double VARIATION_WEIGHT = 1.2;
private static final double IMPROVEMENT_THRESHOLD = 0.125;
private static final double IMPROVEMENT_WEIGHT = 2;
private static final double PROGRESS_THRESHOLD = 0.25;
private static final double PROGRESS_WEIGHT = 1.8;
private final Deque<Double> memory = new LinkedList<>();
private double best = Double.MAX_VALUE;
private double worst;
private int iteration;
private int maxIteration;
private VehicleRoutingProblemSolution getBest(Collection<VehicleRoutingProblemSolution> solutions) {
VehicleRoutingProblemSolution worstBest = null;
for (VehicleRoutingProblemSolution solution : solutions) {
if (worstBest == null) {
worstBest = solution;
} else {
if (solution.getCost() < worstBest.getCost()) {
worstBest = solution;
}
}
}
return worstBest;
}
private double progressWeight() {
var progress = (double) iteration / maxIteration;
if(progress > 0.) {
return Math.min(
progress / PROGRESS_THRESHOLD,
PROGRESS_WEIGHT * Math.exp(-1. * Math.log(PROGRESS_WEIGHT) / (progress / PROGRESS_THRESHOLD))
);
}
return 0.;
}
private double scoreWeight() {
var improvement = ((worst - best) / worst);
if(improvement > 0.) {
return Math.min(
improvement / IMPROVEMENT_THRESHOLD,
IMPROVEMENT_WEIGHT * Math.exp(-1. * Math.log(IMPROVEMENT_WEIGHT) / (improvement / IMPROVEMENT_THRESHOLD))
);
}
return 0.;
}
private double variationCoefficient() {
if (memory.size() == MEMORY_SIZE) {
var values = this.memory.stream().mapToDouble(i -> i).toArray();
var mean = StatUtils.mean(values);
var stdev = new StandardDeviation().evaluate(values, mean);
return stdev / mean * 100;
}
return Double.MAX_VALUE;
}
private double variationWeight() {
var variationCoefficient = variationCoefficient();
return VARIATION_WEIGHT * Math.exp(-1. * Math.log(VARIATION_WEIGHT) * variationCoefficient / VARIATION_THRESHOLD);
}
private double currentThreshold() {
var progress = progressWeight();
var improvement = scoreWeight();
var variation = variationWeight();
log.info("Progress: {}, improvement: {}, variation: {}]",
String.format("%.3f", progress),
String.format("%.3f", improvement),
String.format("%.3f", variation)
);
return progress * improvement * variation;
}
private void memorize(SearchStrategy.DiscoveredSolution discoveredSolution) {
if (discoveredSolution.isAccepted()) {
memory.add(discoveredSolution.getSolution().getCost());
if (memory.size() > MEMORY_SIZE) {
memory.remove();
}
if (best > discoveredSolution.getSolution().getCost()) {
best = discoveredSolution.getSolution().getCost();
if (log.isInfoEnabled()) {
log.info("Found new best score: {}.", String.format("%.2f", best));
}
}
}
}
@Override
public boolean isPrematureBreak(SearchStrategy.DiscoveredSolution discoveredSolution) {
memorize(discoveredSolution);
var threshold = currentThreshold();
if (log.isInfoEnabled()) {
log.info("Iteration: {}, threshold: {}.", iteration, String.format("%.5f", threshold));
}
if (threshold > 1) {
log.info("Iteration terminated due too much iteration without significant improvement.");
return true;
}
return false;
}
@Override
public void informAlgorithmStarts(VehicleRoutingProblem problem, VehicleRoutingAlgorithm algorithm, Collection<VehicleRoutingProblemSolution> solutions) {
var worstBest = getBest(solutions);
worst = worstBest != null ? worstBest.getCost() : Double.MAX_VALUE;
maxIteration = algorithm.getMaxIterations();
log.info("Initialize {}", this);
}
@Override
public void informIterationStarts(int i, VehicleRoutingProblem problem, Collection<VehicleRoutingProblemSolution> solutions) {
iteration = i;
}
@Override
public String toString() {
return "OptimalSolutionTermination{" +
"memorySize=" + MEMORY_SIZE +
", variationThreshold=" + VARIATION_THRESHOLD +
", variationWeight=" + VARIATION_WEIGHT +
", improvementThreshold=" + IMPROVEMENT_THRESHOLD +
", improvementWeight=" + IMPROVEMENT_WEIGHT +
", progressThreshold=" + PROGRESS_THRESHOLD +
", progressWeight=" + PROGRESS_WEIGHT +
", maxIteration=" + maxIteration +
"}";
}
}
For now I have maxIterations set to 20_000. For now improvement and progress weights are calculated by linear-logarithmic function. Variation is pure logarithmic. In next phase I’d like to use sigmoid for progress and improvement weights, but still cannot figure out how to make sigmoit work with threshold. But maybe this helps someone.