001 /* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017 018 package org.apache.commons.math.optimization; 019 020 import java.util.Arrays; 021 import java.util.Comparator; 022 023 import org.apache.commons.math.FunctionEvaluationException; 024 import org.apache.commons.math.MathRuntimeException; 025 import org.apache.commons.math.analysis.MultivariateRealFunction; 026 import org.apache.commons.math.exception.util.LocalizedFormats; 027 import org.apache.commons.math.random.RandomVectorGenerator; 028 029 /** 030 * Special implementation of the {@link MultivariateRealOptimizer} interface adding 031 * multi-start features to an existing optimizer. 032 * <p> 033 * This class wraps a classical optimizer to use it several times in 034 * turn with different starting points in order to avoid being trapped 035 * into a local extremum when looking for a global one. 036 * </p> 037 * @version $Revision: 1073158 $ $Date: 2011-02-21 22:46:52 +0100 (lun. 21 f??vr. 2011) $ 038 * @since 2.0 039 */ 040 public class MultiStartMultivariateRealOptimizer 041 implements MultivariateRealOptimizer { 042 043 /** Underlying classical optimizer. */ 044 private final MultivariateRealOptimizer optimizer; 045 046 /** Maximal number of iterations allowed. */ 047 private int maxIterations; 048 049 /** Maximal number of evaluations allowed. */ 050 private int maxEvaluations; 051 052 /** Number of iterations already performed for all starts. */ 053 private int totalIterations; 054 055 /** Number of evaluations already performed for all starts. */ 056 private int totalEvaluations; 057 058 /** Number of starts to go. */ 059 private int starts; 060 061 /** Random generator for multi-start. */ 062 private RandomVectorGenerator generator; 063 064 /** Found optima. */ 065 private RealPointValuePair[] optima; 066 067 /** 068 * Create a multi-start optimizer from a single-start optimizer 069 * @param optimizer single-start optimizer to wrap 070 * @param starts number of starts to perform (including the 071 * first one), multi-start is disabled if value is less than or 072 * equal to 1 073 * @param generator random vector generator to use for restarts 074 */ 075 public MultiStartMultivariateRealOptimizer(final MultivariateRealOptimizer optimizer, 076 final int starts, 077 final RandomVectorGenerator generator) { 078 this.optimizer = optimizer; 079 this.totalIterations = 0; 080 this.totalEvaluations = 0; 081 this.starts = starts; 082 this.generator = generator; 083 this.optima = null; 084 setMaxIterations(Integer.MAX_VALUE); 085 setMaxEvaluations(Integer.MAX_VALUE); 086 } 087 088 /** Get all the optima found during the last call to {@link 089 * #optimize(MultivariateRealFunction, GoalType, double[]) optimize}. 090 * <p>The optimizer stores all the optima found during a set of 091 * restarts. The {@link #optimize(MultivariateRealFunction, GoalType, 092 * double[]) optimize} method returns the best point only. This 093 * method returns all the points found at the end of each starts, 094 * including the best one already returned by the {@link 095 * #optimize(MultivariateRealFunction, GoalType, double[]) optimize} 096 * method. 097 * </p> 098 * <p> 099 * 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 }