1 /* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 18 package org.apache.commons.math.optimization; 19 20 import java.util.Arrays; 21 import java.util.Comparator; 22 23 import org.apache.commons.math.FunctionEvaluationException; 24 import org.apache.commons.math.MathRuntimeException; 25 import org.apache.commons.math.analysis.MultivariateRealFunction; 26 import org.apache.commons.math.exception.util.LocalizedFormats; 27 import org.apache.commons.math.random.RandomVectorGenerator; 28 29 /** 30 * Special implementation of the {@link MultivariateRealOptimizer} interface adding 31 * multi-start features to an existing optimizer. 32 * <p> 33 * This class wraps a classical optimizer to use it several times in 34 * turn with different starting points in order to avoid being trapped 35 * into a local extremum when looking for a global one. 36 * </p> 37 * @version $Revision: 1073158 $ $Date: 2011-02-21 22:46:52 +0100 (lun. 21 fvr. 2011) $ 38 * @since 2.0 39 */ 40 public class MultiStartMultivariateRealOptimizer 41 implements MultivariateRealOptimizer { 42 43 /** Underlying classical optimizer. */ 44 private final MultivariateRealOptimizer optimizer; 45 46 /** Maximal number of iterations allowed. */ 47 private int maxIterations; 48 49 /** Maximal number of evaluations allowed. */ 50 private int maxEvaluations; 51 52 /** Number of iterations already performed for all starts. */ 53 private int totalIterations; 54 55 /** Number of evaluations already performed for all starts. */ 56 private int totalEvaluations; 57 58 /** Number of starts to go. */ 59 private int starts; 60 61 /** Random generator for multi-start. */ 62 private RandomVectorGenerator generator; 63 64 /** Found optima. */ 65 private RealPointValuePair[] optima; 66 67 /** 68 * Create a multi-start optimizer from a single-start optimizer 69 * @param optimizer single-start optimizer to wrap 70 * @param starts number of starts to perform (including the 71 * first one), multi-start is disabled if value is less than or 72 * equal to 1 73 * @param generator random vector generator to use for restarts 74 */ 75 public MultiStartMultivariateRealOptimizer(final MultivariateRealOptimizer optimizer, 76 final int starts, 77 final RandomVectorGenerator generator) { 78 this.optimizer = optimizer; 79 this.totalIterations = 0; 80 this.totalEvaluations = 0; 81 this.starts = starts; 82 this.generator = generator; 83 this.optima = null; 84 setMaxIterations(Integer.MAX_VALUE); 85 setMaxEvaluations(Integer.MAX_VALUE); 86 } 87 88 /** Get all the optima found during the last call to {@link 89 * #optimize(MultivariateRealFunction, GoalType, double[]) optimize}. 90 * <p>The optimizer stores all the optima found during a set of 91 * restarts. The {@link #optimize(MultivariateRealFunction, GoalType, 92 * double[]) optimize} method returns the best point only. This 93 * method returns all the points found at the end of each starts, 94 * including the best one already returned by the {@link 95 * #optimize(MultivariateRealFunction, GoalType, double[]) optimize} 96 * method. 97 * </p> 98 * <p> 99 * The returned array as one element for each start as specified 100 * in the constructor. It is ordered with the results from the 101 * runs that did converge first, sorted from best to worst 102 * objective value (i.e in ascending order if minimizing and in 103 * descending order if maximizing), followed by and null elements 104 * corresponding to the runs that did not converge. This means all 105 * elements will be null if the {@link #optimize(MultivariateRealFunction, 106 * GoalType, double[]) optimize} method did throw a {@link 107 * org.apache.commons.math.ConvergenceException ConvergenceException}). 108 * This also means that if the first element is non null, it is the best 109 * point found across all starts.</p> 110 * @return array containing the optima 111 * @exception IllegalStateException if {@link #optimize(MultivariateRealFunction, 112 * GoalType, double[]) optimize} has not been called 113 */ 114 public RealPointValuePair[] getOptima() throws IllegalStateException { 115 if (optima == null) { 116 throw MathRuntimeException.createIllegalStateException(LocalizedFormats.NO_OPTIMUM_COMPUTED_YET); 117 } 118 return optima.clone(); 119 } 120 121 /** {@inheritDoc} */ 122 public void setMaxIterations(int maxIterations) { 123 this.maxIterations = maxIterations; 124 } 125 126 /** {@inheritDoc} */ 127 public int getMaxIterations() { 128 return maxIterations; 129 } 130 131 /** {@inheritDoc} */ 132 public void setMaxEvaluations(int maxEvaluations) { 133 this.maxEvaluations = maxEvaluations; 134 } 135 136 /** {@inheritDoc} */ 137 public int getMaxEvaluations() { 138 return maxEvaluations; 139 } 140 141 /** {@inheritDoc} */ 142 public int getIterations() { 143 return totalIterations; 144 } 145 146 /** {@inheritDoc} */ 147 public int getEvaluations() { 148 return totalEvaluations; 149 } 150 151 /** {@inheritDoc} */ 152 public void setConvergenceChecker(RealConvergenceChecker checker) { 153 optimizer.setConvergenceChecker(checker); 154 } 155 156 /** {@inheritDoc} */ 157 public RealConvergenceChecker getConvergenceChecker() { 158 return optimizer.getConvergenceChecker(); 159 } 160 161 /** {@inheritDoc} */ 162 public RealPointValuePair optimize(final MultivariateRealFunction f, 163 final GoalType goalType, 164 double[] startPoint) 165 throws FunctionEvaluationException, OptimizationException, FunctionEvaluationException { 166 167 optima = new RealPointValuePair[starts]; 168 totalIterations = 0; 169 totalEvaluations = 0; 170 171 // multi-start loop 172 for (int i = 0; i < starts; ++i) { 173 174 try { 175 optimizer.setMaxIterations(maxIterations - totalIterations); 176 optimizer.setMaxEvaluations(maxEvaluations - totalEvaluations); 177 optima[i] = optimizer.optimize(f, goalType, 178 (i == 0) ? startPoint : generator.nextVector()); 179 } catch (FunctionEvaluationException fee) { 180 optima[i] = null; 181 } catch (OptimizationException oe) { 182 optima[i] = null; 183 } 184 185 totalIterations += optimizer.getIterations(); 186 totalEvaluations += optimizer.getEvaluations(); 187 188 } 189 190 // sort the optima from best to worst, followed by null elements 191 Arrays.sort(optima, new Comparator<RealPointValuePair>() { 192 public int compare(final RealPointValuePair o1, final RealPointValuePair o2) { 193 if (o1 == null) { 194 return (o2 == null) ? 0 : +1; 195 } else if (o2 == null) { 196 return -1; 197 } 198 final double v1 = o1.getValue(); 199 final double v2 = o2.getValue(); 200 return (goalType == GoalType.MINIMIZE) ? 201 Double.compare(v1, v2) : Double.compare(v2, v1); 202 } 203 }); 204 205 if (optima[0] == null) { 206 throw new OptimizationException( 207 LocalizedFormats.NO_CONVERGENCE_WITH_ANY_START_POINT, 208 starts); 209 } 210 211 // return the found point given the best objective function value 212 return optima[0]; 213 214 } 215 216 } 217
