SimulatedAnnealing.java
- /*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
- package org.apache.commons.math4.legacy.optim.nonlinear.scalar;
- import java.util.function.BiFunction;
- import java.util.function.DoublePredicate;
- import org.apache.commons.rng.UniformRandomProvider;
- import org.apache.commons.math4.legacy.stat.descriptive.moment.StandardDeviation;
- import org.apache.commons.math4.legacy.optim.OptimizationData;
- import org.apache.commons.math4.legacy.optim.nonlinear.scalar.noderiv.Simplex;
- /**
- * Simulated annealing setup.
- *
- * @since 4.0
- */
- public class SimulatedAnnealing implements OptimizationData {
- /** Number of iterations at fixed temperature. */
- private final int epochDuration;
- /** Initial acceptance probability. */
- private final double startProbability;
- /** Final acceptance probability. */
- private final double endProbability;
- /** Cooling function. */
- private final CoolingSchedule coolingSchedule;
- /** RNG. */
- private final UniformRandomProvider rng;
- /**
- * @param epoch Number of iterations performed at fixed temperature.
- * @param startProb Initial acceptance probablility.
- * @param endProb Final acceptance probablility.
- * @param cooling Computes the temperature as a function of the initial
- * temperature and the epoch.
- * It is called for computing a new temperature after each cycle of
- * {@code epoch} iterations.
- * Simulated annealing <em>assumes</em> that the function decreases
- * monotically wrt the epoch (cf. {@link CoolingSchedule#decreasingExponential(double)
- * provided implementation}).
- * @param random Random number generator.
- * @throws IllegalArgumentException if {@code epoch < 1} or
- * {@code startProb} or {@code endProb} is outside the {@code [0, 1]}
- * interval.
- */
- public SimulatedAnnealing(int epoch,
- double startProb,
- double endProb,
- CoolingSchedule cooling,
- UniformRandomProvider random) {
- if (epoch < 1) {
- throw new IllegalArgumentException("Epoch out of range: " +
- epoch);
- }
- if (startProb < 0 ||
- startProb > 1) {
- throw new IllegalArgumentException("Initial acceptance probability out of range: " +
- startProb);
- }
- if (endProb < 0 ||
- endProb > 1) {
- throw new IllegalArgumentException("Final acceptance probability out of range: " +
- endProb);
- }
- if (endProb >= startProb) {
- throw new IllegalArgumentException("Final probability larger than initial probability");
- }
- epochDuration = epoch;
- startProbability = startProb;
- endProbability = endProb;
- coolingSchedule = cooling;
- rng = random;
- }
- /**
- * @return the epoch duration.
- */
- public int getEpochDuration() {
- return epochDuration;
- }
- /**
- * @return the acceptance probability at the beginning of the SA process.
- */
- public double getStartProbability() {
- return startProbability;
- }
- /**
- * @return the acceptance probability at the end of the SA process.
- */
- public double getEndProbability() {
- return endProbability;
- }
- /**
- * @return the cooling schedule.
- */
- public CoolingSchedule getCoolingSchedule() {
- return coolingSchedule;
- }
- /**
- * Specifies the cooling schedule.
- * It computes the current temperature as a function of two arguments:
- * <ol>
- * <li>the previous temperature,</li>
- * <li>the current simplex.</li>
- * </ol>
- */
- public interface CoolingSchedule extends BiFunction<Double, Simplex, Double> {
- /**
- * Power-law cooling scheme:
- * \[
- * T_i = T_0 * f^i
- * \], where \( i \) is the current iteration.
- * <p>
- * Note: Simplex argument (of the returned function) is not used.
- *
- * @param f Factor by which the temperature is decreased.
- * @return the cooling schedule.
- */
- static CoolingSchedule decreasingExponential(final double f) {
- if (f <= 0 ||
- f >= 1) {
- throw new IllegalArgumentException("Factor out of range: " + f);
- }
- return (previousTemperature, simplex) -> f * previousTemperature;
- }
- /**
- * Aarst and van Laarhoven (1985) scheme:
- * \[
- * T_{i + 1} = \frac{T_{i}}{1 + \frac{T_i \ln(1 + \delta)}{3 \sigma}}
- * \]
- * <p>
- * The simplex argument is used to compute the standard deviation
- * (\(\sigma\)) of all the vertices' objective function value.
- *
- * @param delta Trajectory parameter. Values smaller than 1 entail slow
- * convergence; values larger than 1 entail convergence to local optimum.
- * @return the cooling schedule.
- */
- static CoolingSchedule aarstAndVanLaarhoven(final double delta) {
- if (delta <= 0) {
- throw new IllegalArgumentException("Trajectory parameter out of range: " +
- delta);
- }
- return (previousTemperature, simplex) -> {
- // Standard deviation of the values of the objective function.
- final StandardDeviation stddev = new StandardDeviation();
- for (int i = 0; i < simplex.getSize(); i++) {
- stddev.increment(simplex.get(i).getValue());
- }
- final double sigma = stddev.getResult();
- final double a = previousTemperature * Math.log(1 + delta);
- final double b = 3 * sigma;
- return previousTemperature / (1 + a / b);
- };
- }
- }
- /**
- * Factory for the Metropolis check for accepting a worse state.
- * \( e^{-|\Delta E| / T} \geq \mathrm{rand}(0, 1) \).
- *
- * <p>
- * It is assumed that this check is performed <em>after</em> ensuring
- * that the alternate state is <em>worse</em> than the current best state.
- *
- * @param temperature Current temperature.
- * @return the acceptance test.
- */
- public DoublePredicate metropolis(final double temperature) {
- // Absolute value takes care of both minimization and maximization cases.
- return deltaE -> Math.exp(Math.abs(deltaE) / temperature) >= rng.nextDouble();
- }
- }