| /* |
| * 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.math.optimization; |
| |
| import org.apache.commons.math.ConvergenceException; |
| import org.apache.commons.math.FunctionEvaluationException; |
| import org.apache.commons.math.MathRuntimeException; |
| import org.apache.commons.math.analysis.UnivariateRealFunction; |
| import org.apache.commons.math.exception.util.LocalizedFormats; |
| import org.apache.commons.math.random.RandomGenerator; |
| import org.apache.commons.math.util.FastMath; |
| |
| /** |
| * Special implementation of the {@link UnivariateRealOptimizer} interface adding |
| * multi-start features to an existing optimizer. |
| * <p> |
| * This class wraps a classical optimizer to use it several times in |
| * turn with different starting points in order to avoid being trapped |
| * into a local extremum when looking for a global one. |
| * </p> |
| * @version $Revision: 1070725 $ $Date: 2011-02-15 02:31:12 +0100 (mar. 15 févr. 2011) $ |
| * @since 2.0 |
| */ |
| public class MultiStartUnivariateRealOptimizer implements UnivariateRealOptimizer { |
| |
| /** Serializable version identifier. */ |
| private static final long serialVersionUID = 5983375963110961019L; |
| |
| /** Underlying classical optimizer. */ |
| private final UnivariateRealOptimizer optimizer; |
| |
| /** Maximal number of iterations allowed. */ |
| private int maxIterations; |
| |
| /** Maximal number of evaluations allowed. */ |
| private int maxEvaluations; |
| |
| /** Number of iterations already performed for all starts. */ |
| private int totalIterations; |
| |
| /** Number of evaluations already performed for all starts. */ |
| private int totalEvaluations; |
| |
| /** Number of starts to go. */ |
| private int starts; |
| |
| /** Random generator for multi-start. */ |
| private RandomGenerator generator; |
| |
| /** Found optima. */ |
| private double[] optima; |
| |
| /** Found function values at optima. */ |
| private double[] optimaValues; |
| |
| /** |
| * Create a multi-start optimizer from a single-start optimizer |
| * @param optimizer single-start optimizer to wrap |
| * @param starts number of starts to perform (including the |
| * first one), multi-start is disabled if value is less than or |
| * equal to 1 |
| * @param generator random generator to use for restarts |
| */ |
| public MultiStartUnivariateRealOptimizer(final UnivariateRealOptimizer optimizer, |
| final int starts, |
| final RandomGenerator generator) { |
| this.optimizer = optimizer; |
| this.totalIterations = 0; |
| this.starts = starts; |
| this.generator = generator; |
| this.optima = null; |
| setMaximalIterationCount(Integer.MAX_VALUE); |
| setMaxEvaluations(Integer.MAX_VALUE); |
| } |
| |
| /** {@inheritDoc} */ |
| public double getFunctionValue() { |
| return optimaValues[0]; |
| } |
| |
| /** {@inheritDoc} */ |
| public double getResult() { |
| return optima[0]; |
| } |
| |
| /** {@inheritDoc} */ |
| public double getAbsoluteAccuracy() { |
| return optimizer.getAbsoluteAccuracy(); |
| } |
| |
| /** {@inheritDoc} */ |
| public int getIterationCount() { |
| return totalIterations; |
| } |
| |
| /** {@inheritDoc} */ |
| public int getMaximalIterationCount() { |
| return maxIterations; |
| } |
| |
| /** {@inheritDoc} */ |
| public int getMaxEvaluations() { |
| return maxEvaluations; |
| } |
| |
| /** {@inheritDoc} */ |
| public int getEvaluations() { |
| return totalEvaluations; |
| } |
| |
| /** {@inheritDoc} */ |
| public double getRelativeAccuracy() { |
| return optimizer.getRelativeAccuracy(); |
| } |
| |
| /** {@inheritDoc} */ |
| public void resetAbsoluteAccuracy() { |
| optimizer.resetAbsoluteAccuracy(); |
| } |
| |
| /** {@inheritDoc} */ |
| public void resetMaximalIterationCount() { |
| optimizer.resetMaximalIterationCount(); |
| } |
| |
| /** {@inheritDoc} */ |
| public void resetRelativeAccuracy() { |
| optimizer.resetRelativeAccuracy(); |
| } |
| |
| /** {@inheritDoc} */ |
| public void setAbsoluteAccuracy(double accuracy) { |
| optimizer.setAbsoluteAccuracy(accuracy); |
| } |
| |
| /** {@inheritDoc} */ |
| public void setMaximalIterationCount(int count) { |
| this.maxIterations = count; |
| } |
| |
| /** {@inheritDoc} */ |
| public void setMaxEvaluations(int maxEvaluations) { |
| this.maxEvaluations = maxEvaluations; |
| } |
| |
| /** {@inheritDoc} */ |
| public void setRelativeAccuracy(double accuracy) { |
| optimizer.setRelativeAccuracy(accuracy); |
| } |
| |
| /** Get all the optima found during the last call to {@link |
| * #optimize(UnivariateRealFunction, GoalType, double, double) optimize}. |
| * <p>The optimizer stores all the optima found during a set of |
| * restarts. The {@link #optimize(UnivariateRealFunction, GoalType, |
| * double, double) optimize} method returns the best point only. This |
| * method returns all the points found at the end of each starts, |
| * including the best one already returned by the {@link |
| * #optimize(UnivariateRealFunction, GoalType, double, double) optimize} |
| * method. |
| * </p> |
| * <p> |
| * The returned array as one element for each start as specified |
| * in the constructor. It is ordered with the results from the |
| * runs that did converge first, sorted from best to worst |
| * objective value (i.e in ascending order if minimizing and in |
| * descending order if maximizing), followed by Double.NaN elements |
| * corresponding to the runs that did not converge. This means all |
| * elements will be NaN if the {@link #optimize(UnivariateRealFunction, |
| * GoalType, double, double) optimize} method did throw a {@link |
| * ConvergenceException ConvergenceException}). This also means that |
| * if the first element is not NaN, it is the best point found across |
| * all starts.</p> |
| * @return array containing the optima |
| * @exception IllegalStateException if {@link #optimize(UnivariateRealFunction, |
| * GoalType, double, double) optimize} has not been called |
| * @see #getOptimaValues() |
| */ |
| public double[] getOptima() throws IllegalStateException { |
| if (optima == null) { |
| throw MathRuntimeException.createIllegalStateException(LocalizedFormats.NO_OPTIMUM_COMPUTED_YET); |
| } |
| return optima.clone(); |
| } |
| |
| /** Get all the function values at optima found during the last call to {@link |
| * #optimize(UnivariateRealFunction, GoalType, double, double) optimize}. |
| * <p> |
| * The returned array as one element for each start as specified |
| * in the constructor. It is ordered with the results from the |
| * runs that did converge first, sorted from best to worst |
| * objective value (i.e in ascending order if minimizing and in |
| * descending order if maximizing), followed by Double.NaN elements |
| * corresponding to the runs that did not converge. This means all |
| * elements will be NaN if the {@link #optimize(UnivariateRealFunction, |
| * GoalType, double, double) optimize} method did throw a {@link |
| * ConvergenceException ConvergenceException}). This also means that |
| * if the first element is not NaN, it is the best point found across |
| * all starts.</p> |
| * @return array containing the optima |
| * @exception IllegalStateException if {@link #optimize(UnivariateRealFunction, |
| * GoalType, double, double) optimize} has not been called |
| * @see #getOptima() |
| */ |
| public double[] getOptimaValues() throws IllegalStateException { |
| if (optimaValues == null) { |
| throw MathRuntimeException.createIllegalStateException(LocalizedFormats.NO_OPTIMUM_COMPUTED_YET); |
| } |
| return optimaValues.clone(); |
| } |
| |
| /** {@inheritDoc} */ |
| public double optimize(final UnivariateRealFunction f, final GoalType goalType, |
| final double min, final double max) |
| throws ConvergenceException, FunctionEvaluationException { |
| |
| optima = new double[starts]; |
| optimaValues = new double[starts]; |
| totalIterations = 0; |
| totalEvaluations = 0; |
| |
| // multi-start loop |
| for (int i = 0; i < starts; ++i) { |
| |
| try { |
| optimizer.setMaximalIterationCount(maxIterations - totalIterations); |
| optimizer.setMaxEvaluations(maxEvaluations - totalEvaluations); |
| final double bound1 = (i == 0) ? min : min + generator.nextDouble() * (max - min); |
| final double bound2 = (i == 0) ? max : min + generator.nextDouble() * (max - min); |
| optima[i] = optimizer.optimize(f, goalType, |
| FastMath.min(bound1, bound2), |
| FastMath.max(bound1, bound2)); |
| optimaValues[i] = optimizer.getFunctionValue(); |
| } catch (FunctionEvaluationException fee) { |
| optima[i] = Double.NaN; |
| optimaValues[i] = Double.NaN; |
| } catch (ConvergenceException ce) { |
| optima[i] = Double.NaN; |
| optimaValues[i] = Double.NaN; |
| } |
| |
| totalIterations += optimizer.getIterationCount(); |
| totalEvaluations += optimizer.getEvaluations(); |
| |
| } |
| |
| // sort the optima from best to worst, followed by NaN elements |
| int lastNaN = optima.length; |
| for (int i = 0; i < lastNaN; ++i) { |
| if (Double.isNaN(optima[i])) { |
| optima[i] = optima[--lastNaN]; |
| optima[lastNaN + 1] = Double.NaN; |
| optimaValues[i] = optimaValues[--lastNaN]; |
| optimaValues[lastNaN + 1] = Double.NaN; |
| } |
| } |
| |
| double currX = optima[0]; |
| double currY = optimaValues[0]; |
| for (int j = 1; j < lastNaN; ++j) { |
| final double prevY = currY; |
| currX = optima[j]; |
| currY = optimaValues[j]; |
| if ((goalType == GoalType.MAXIMIZE) ^ (currY < prevY)) { |
| // the current element should be inserted closer to the beginning |
| int i = j - 1; |
| double mIX = optima[i]; |
| double mIY = optimaValues[i]; |
| while ((i >= 0) && ((goalType == GoalType.MAXIMIZE) ^ (currY < mIY))) { |
| optima[i + 1] = mIX; |
| optimaValues[i + 1] = mIY; |
| if (i-- != 0) { |
| mIX = optima[i]; |
| mIY = optimaValues[i]; |
| } else { |
| mIX = Double.NaN; |
| mIY = Double.NaN; |
| } |
| } |
| optima[i + 1] = currX; |
| optimaValues[i + 1] = currY; |
| currX = optima[j]; |
| currY = optimaValues[j]; |
| } |
| } |
| |
| if (Double.isNaN(optima[0])) { |
| throw new OptimizationException( |
| LocalizedFormats.NO_CONVERGENCE_WITH_ANY_START_POINT, |
| starts); |
| } |
| |
| // return the found point given the best objective function value |
| return optima[0]; |
| |
| } |
| |
| /** {@inheritDoc} */ |
| public double optimize(final UnivariateRealFunction f, final GoalType goalType, |
| final double min, final double max, final double startValue) |
| throws ConvergenceException, FunctionEvaluationException { |
| return optimize(f, goalType, min, max); |
| } |
| } |