HedarFukushimaTransform.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.noderiv;

import java.util.Comparator;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
import java.util.function.UnaryOperator;
import java.util.function.DoublePredicate;
import org.apache.commons.rng.UniformRandomProvider;
import org.apache.commons.rng.simple.RandomSource;
import org.apache.commons.rng.sampling.distribution.ContinuousSampler;
import org.apache.commons.rng.sampling.distribution.ContinuousUniformSampler;
import org.apache.commons.math4.legacy.analysis.MultivariateFunction;
import org.apache.commons.math4.legacy.optim.PointValuePair;

/**
 * DSSA algorithm.
 *
 * Described in
 * <blockquote>
 *  <em>Abdel-Rahman Hedar and Masao Fukushima (2002)</em>,
 *  <b>
 *   Hybrid simulated annealing and direct search method
 *   for nonlinear unconstrained global optimization
 *  </b>,
 *  Optimization Methods and Software, 17:5, 891-912,
 *  DOI: 10.1080/1055678021000030084
 * </blockquote>
 *
 * <p>
 * A note about the {@link #HedarFukushimaTransform(double) "shrink" factor}:
 * Per DSSA's description, the simplex must keep its size during the simulated
 * annealing (SA) phase to avoid premature convergence.  This assumes that the
 * best candidates from the SA phase will each subsequently serve as starting
 * point for another optimization to hone in on the local optimum.
 * Values lower than 1 and no subsequent "best list" search correspond to the
 * "SSA" algorithm in the above paper.
 */
public class HedarFukushimaTransform
    implements Simplex.TransformFactory {
    /** Shrinkage coefficient. */
    private final double sigma;
    /** Sampler for reflection coefficient. */
    private final ContinuousSampler alphaSampler;
    /** No shrink indicator. */
    private final boolean noShrink;

    /**
     * @param sigma Shrink factor.
     * @param rng Random generator.
     * @throws IllegalArgumentException if {@code sigma <= 0} or
     * {@code sigma > 1}.
     */
    public HedarFukushimaTransform(double sigma,
                                   UniformRandomProvider rng) {
        if (sigma <= 0 ||
            sigma > 1) {
            throw new IllegalArgumentException("Shrink factor out of range: " +
                                               sigma);
        }

        this.sigma = sigma;
        alphaSampler = ContinuousUniformSampler.of(rng, 0.9, 1.1);
        noShrink = sigma == 1d;
    }

    /**
     * @param sigma Shrink factor.
     * @throws IllegalArgumentException if {@code sigma <= 0} or
     * {@code sigma > 1}.
     */
    public HedarFukushimaTransform(double sigma) {
        this(sigma, RandomSource.KISS.create());
    }

    /**
     * Disable shrinking of the simplex (as mandated by DSSA).
     */
    public HedarFukushimaTransform() {
        this(1d);
    }

    /** {@inheritDoc} */
    @Override
    public UnaryOperator<Simplex> create(final MultivariateFunction evaluationFunction,
                                         final Comparator<PointValuePair> comparator,
                                         final DoublePredicate saAcceptance) {
        if (saAcceptance == null) {
            throw new IllegalArgumentException("Missing SA acceptance test");
        }

        return original -> transform(original,
                                     saAcceptance,
                                     evaluationFunction,
                                     comparator);
    }

    /**
     * Simulated annealing step (at fixed temperature).
     *
     * @param original Current simplex.  Points must be sorted from best to worst.
     * @param sa Simulated annealing acceptance test.
     * @param eval Evaluation function.
     * @param comp Objective function comparator.
     * @return a new instance.
     */
    private Simplex transform(Simplex original,
                              DoublePredicate sa,
                              MultivariateFunction eval,
                              Comparator<PointValuePair> comp) {
        final int size = original.getSize();
        // Current best point.
        final PointValuePair best = original.get(0);
        final double bestValue = best.getValue();

        for (int k = 1; k < size; k++) {
            // Perform reflections of the "k" worst points.
            final List<PointValuePair> reflected = reflectPoints(original, k, eval);
            Collections.sort(reflected, comp);

            // Check whether the best of the reflected points is better than the
            // current overall best.
            final PointValuePair candidate = reflected.get(0);
            final boolean candidateIsBetter = comp.compare(candidate, best) < 0;
            final boolean candidateIsAccepted = candidateIsBetter ||
                sa.test(candidate.getValue() - bestValue);

            if (candidateIsAccepted) {
                // Replace worst points with the reflected points.
                return original.replaceLast(reflected);
            }
        }

        // No direction provided a better point.
        return noShrink ?
            original :
            original.shrink(sigma, eval);
    }

    /**
     * @param simplex Current simplex (whose points must be sorted, from best
     * to worst).
     * @param nPoints Number of points to reflect.
     * The {@code nPoints} worst points will be reflected through the centroid
     * of the {@code n + 1 - nPoints} best points.
     * @param eval Evaluation function.
     * @return the (unsorted) list of reflected points.
     * @throws IllegalArgumentException if {@code nPoints < 1} or
     * {@code nPoints > n}.
     */
    private List<PointValuePair> reflectPoints(Simplex simplex,
                                               int nPoints,
                                               MultivariateFunction eval) {
        final int size = simplex.getSize();
        if (nPoints < 1 ||
            nPoints >= size) {
            throw new IllegalArgumentException("Out of range: " + nPoints);
        }

        final int nCentroid = size - nPoints;
        final List<PointValuePair> centroidList = simplex.asList(0, nCentroid);
        final List<PointValuePair> reflectList = simplex.asList(nCentroid, size);

        final double[] centroid = Simplex.centroid(centroidList);

        final List<PointValuePair> reflected = new ArrayList<>(nPoints);
        for (int i = 0; i < reflectList.size(); i++) {
            reflected.add(newReflectedPoint(reflectList.get(i),
                                            centroid,
                                            eval));
        }

        return reflected;
    }

    /**
     * @param point Current point.
     * @param centroid Coordinates through which reflection must be performed.
     * @param eval Evaluation function.
     * @return a new point with Cartesian coordinates set to the reflection
     * of {@code point} through {@code centroid}.
     */
    private PointValuePair newReflectedPoint(PointValuePair point,
                                             double[] centroid,
                                             MultivariateFunction eval) {
        final double alpha = alphaSampler.sample();
        return Simplex.newPoint(centroid,
                                -alpha,
                                point.getPoint(),
                                eval);
    }

    /** {@inheritDoc} */
    @Override
    public String toString() {
        return "Hedar-Fukushima [s=" + sigma + "]";
    }
}