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.DifferentiableMultivariateRealFunction; 026 import org.apache.commons.math.random.RandomVectorGenerator; 027 028 /** 029 * Special implementation of the {@link DifferentiableMultivariateRealOptimizer} interface adding 030 * multi-start features to an existing optimizer. 031 * <p> 032 * This class wraps a classical optimizer to use it several times in 033 * turn with different starting points in order to avoid being trapped 034 * into a local extremum when looking for a global one. 035 * </p> 036 * @version $Revision: 811685 $ $Date: 2009-09-05 13:36:48 -0400 (Sat, 05 Sep 2009) $ 037 * @since 2.0 038 */ 039 public class MultiStartDifferentiableMultivariateRealOptimizer 040 implements DifferentiableMultivariateRealOptimizer { 041 042 /** Underlying classical optimizer. */ 043 private final DifferentiableMultivariateRealOptimizer optimizer; 044 045 /** Maximal number of iterations allowed. */ 046 private int maxIterations; 047 048 /** Number of iterations already performed for all starts. */ 049 private int totalIterations; 050 051 /** Maximal number of evaluations allowed. */ 052 private int maxEvaluations; 053 054 /** Number of evaluations already performed for all starts. */ 055 private int totalEvaluations; 056 057 /** Number of gradient evaluations already performed for all starts. */ 058 private int totalGradientEvaluations; 059 060 /** Number of starts to go. */ 061 private int starts; 062 063 /** Random generator for multi-start. */ 064 private RandomVectorGenerator generator; 065 066 /** Found optima. */ 067 private RealPointValuePair[] optima; 068 069 /** 070 * Create a multi-start optimizer from a single-start optimizer 071 * @param optimizer single-start optimizer to wrap 072 * @param starts number of starts to perform (including the 073 * first one), multi-start is disabled if value is less than or 074 * equal to 1 075 * @param generator random vector generator to use for restarts 076 */ 077 public MultiStartDifferentiableMultivariateRealOptimizer(final DifferentiableMultivariateRealOptimizer optimizer, 078 final int starts, 079 final RandomVectorGenerator generator) { 080 this.optimizer = optimizer; 081 this.totalIterations = 0; 082 this.totalEvaluations = 0; 083 this.totalGradientEvaluations = 0; 084 this.starts = starts; 085 this.generator = generator; 086 this.optima = null; 087 setMaxIterations(Integer.MAX_VALUE); 088 setMaxEvaluations(Integer.MAX_VALUE); 089 } 090 091 /** Get all the optima found during the last call to {@link 092 * #optimize(DifferentiableMultivariateRealFunction, GoalType, double[]) 093 * optimize}. 094 * <p>The optimizer stores all the optima found during a set of 095 * restarts. The {@link #optimize(DifferentiableMultivariateRealFunction, 096 * GoalType, double[]) optimize} method returns the best point only. This 097 * method returns all the points found at the end of each starts, 098 * including the best one already returned by the {@link 099 * #optimize(DifferentiableMultivariateRealFunction, GoalType, double[]) 100 * optimize} method. 101 * </p> 102 * <p> 103 * The returned array as one element for each start as specified 104 * in the constructor. It is ordered with the results from the 105 * runs that did converge first, sorted from best to worst 106 * objective value (i.e in ascending order if minimizing and in 107 * descending order if maximizing), followed by and null elements 108 * corresponding to the runs that did not converge. This means all 109 * elements will be null if the {@link #optimize(DifferentiableMultivariateRealFunction, 110 * GoalType, double[]) optimize} method did throw a {@link 111 * org.apache.commons.math.ConvergenceException ConvergenceException}). 112 * This also means that if the first element is non null, it is the best 113 * point found across all starts.</p> 114 * @return array containing the optima 115 * @exception IllegalStateException if {@link #optimize(DifferentiableMultivariateRealFunction, 116 * GoalType, double[]) optimize} has not been called 117 */ 118 public RealPointValuePair[] getOptima() throws IllegalStateException { 119 if (optima == null) { 120 throw MathRuntimeException.createIllegalStateException("no optimum computed yet"); 121 } 122 return optima.clone(); 123 } 124 125 /** {@inheritDoc} */ 126 public void setMaxIterations(int maxIterations) { 127 this.maxIterations = maxIterations; 128 } 129 130 /** {@inheritDoc} */ 131 public int getMaxIterations() { 132 return maxIterations; 133 } 134 135 /** {@inheritDoc} */ 136 public int getIterations() { 137 return totalIterations; 138 } 139 140 /** {@inheritDoc} */ 141 public void setMaxEvaluations(int maxEvaluations) { 142 this.maxEvaluations = maxEvaluations; 143 } 144 145 /** {@inheritDoc} */ 146 public int getMaxEvaluations() { 147 return maxEvaluations; 148 } 149 150 /** {@inheritDoc} */ 151 public int getEvaluations() { 152 return totalEvaluations; 153 } 154 155 /** {@inheritDoc} */ 156 public int getGradientEvaluations() { 157 return totalGradientEvaluations; 158 } 159 160 /** {@inheritDoc} */ 161 public void setConvergenceChecker(RealConvergenceChecker checker) { 162 optimizer.setConvergenceChecker(checker); 163 } 164 165 /** {@inheritDoc} */ 166 public RealConvergenceChecker getConvergenceChecker() { 167 return optimizer.getConvergenceChecker(); 168 } 169 170 /** {@inheritDoc} */ 171 public RealPointValuePair optimize(final DifferentiableMultivariateRealFunction f, 172 final GoalType goalType, 173 double[] startPoint) 174 throws FunctionEvaluationException, OptimizationException { 175 176 optima = new RealPointValuePair[starts]; 177 totalIterations = 0; 178 totalEvaluations = 0; 179 totalGradientEvaluations = 0; 180 181 // multi-start loop 182 for (int i = 0; i < starts; ++i) { 183 184 try { 185 optimizer.setMaxIterations(maxIterations - totalIterations); 186 optimizer.setMaxEvaluations(maxEvaluations - totalEvaluations); 187 optima[i] = optimizer.optimize(f, goalType, 188 (i == 0) ? startPoint : generator.nextVector()); 189 } catch (FunctionEvaluationException fee) { 190 optima[i] = null; 191 } catch (OptimizationException oe) { 192 optima[i] = null; 193 } 194 195 totalIterations += optimizer.getIterations(); 196 totalEvaluations += optimizer.getEvaluations(); 197 totalGradientEvaluations += optimizer.getGradientEvaluations(); 198 199 } 200 201 // sort the optima from best to worst, followed by null elements 202 Arrays.sort(optima, new Comparator<RealPointValuePair>() { 203 public int compare(final RealPointValuePair o1, final RealPointValuePair o2) { 204 if (o1 == null) { 205 return (o2 == null) ? 0 : +1; 206 } else if (o2 == null) { 207 return -1; 208 } 209 final double v1 = o1.getValue(); 210 final double v2 = o2.getValue(); 211 return (goalType == GoalType.MINIMIZE) ? 212 Double.compare(v1, v2) : Double.compare(v2, v1); 213 } 214 }); 215 216 if (optima[0] == null) { 217 throw new OptimizationException( 218 "none of the {0} start points lead to convergence", 219 starts); 220 } 221 222 // return the found point given the best objective function value 223 return optima[0]; 224 225 } 226 227 }