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 */ 017package org.apache.commons.math3.optim; 018 019import org.apache.commons.math3.exception.MathIllegalStateException; 020import org.apache.commons.math3.exception.NotStrictlyPositiveException; 021import org.apache.commons.math3.exception.TooManyEvaluationsException; 022import org.apache.commons.math3.random.RandomVectorGenerator; 023 024/** 025 * Base class multi-start optimizer for a multivariate function. 026 * <br/> 027 * This class wraps an optimizer in order to use it several times in 028 * turn with different starting points (trying to avoid being trapped 029 * in a local extremum when looking for a global one). 030 * <em>It is not a "user" class.</em> 031 * 032 * @param <PAIR> Type of the point/value pair returned by the optimization 033 * algorithm. 034 * 035 * @since 3.0 036 */ 037public abstract class BaseMultiStartMultivariateOptimizer<PAIR> 038 extends BaseMultivariateOptimizer<PAIR> { 039 /** Underlying classical optimizer. */ 040 private final BaseMultivariateOptimizer<PAIR> optimizer; 041 /** Number of evaluations already performed for all starts. */ 042 private int totalEvaluations; 043 /** Number of starts to go. */ 044 private int starts; 045 /** Random generator for multi-start. */ 046 private RandomVectorGenerator generator; 047 /** Optimization data. */ 048 private OptimizationData[] optimData; 049 /** 050 * Location in {@link #optimData} where the updated maximum 051 * number of evaluations will be stored. 052 */ 053 private int maxEvalIndex = -1; 054 /** 055 * Location in {@link #optimData} where the updated start value 056 * will be stored. 057 */ 058 private int initialGuessIndex = -1; 059 060 /** 061 * Create a multi-start optimizer from a single-start optimizer. 062 * <p> 063 * Note that if there are bounds constraints (see {@link #getLowerBound()} 064 * and {@link #getUpperBound()}), then a simple rejection algorithm is used 065 * at each restart. This implies that the random vector generator should have 066 * a good probability to generate vectors in the bounded domain, otherwise the 067 * rejection algorithm will hit the {@link #getMaxEvaluations()} count without 068 * generating a proper restart point. Users must be take great care of the <a 069 * href="http://en.wikipedia.org/wiki/Curse_of_dimensionality">curse of dimensionality</a>. 070 * </p> 071 * @param optimizer Single-start optimizer to wrap. 072 * @param starts Number of starts to perform. If {@code starts == 1}, 073 * the {@link #optimize(OptimizationData[]) optimize} will return the 074 * same solution as the given {@code optimizer} would return. 075 * @param generator Random vector generator to use for restarts. 076 * @throws NotStrictlyPositiveException if {@code starts < 1}. 077 */ 078 public BaseMultiStartMultivariateOptimizer(final BaseMultivariateOptimizer<PAIR> optimizer, 079 final int starts, 080 final RandomVectorGenerator generator) { 081 super(optimizer.getConvergenceChecker()); 082 083 if (starts < 1) { 084 throw new NotStrictlyPositiveException(starts); 085 } 086 087 this.optimizer = optimizer; 088 this.starts = starts; 089 this.generator = generator; 090 } 091 092 /** {@inheritDoc} */ 093 @Override 094 public int getEvaluations() { 095 return totalEvaluations; 096 } 097 098 /** 099 * Gets all the optima found during the last call to {@code optimize}. 100 * The optimizer stores all the optima found during a set of 101 * restarts. The {@code optimize} method returns the best point only. 102 * This method returns all the points found at the end of each starts, 103 * including the best one already returned by the {@code optimize} method. 104 * <br/> 105 * The returned array as one element for each start as specified 106 * in the constructor. It is ordered with the results from the 107 * runs that did converge first, sorted from best to worst 108 * objective value (i.e in ascending order if minimizing and in 109 * descending order if maximizing), followed by {@code null} elements 110 * corresponding to the runs that did not converge. This means all 111 * elements will be {@code null} if the {@code optimize} method did throw 112 * an exception. 113 * This also means that if the first element is not {@code null}, it is 114 * the best point found across all starts. 115 * <br/> 116 * The behaviour is undefined if this method is called before 117 * {@code optimize}; it will likely throw {@code NullPointerException}. 118 * 119 * @return an array containing the optima sorted from best to worst. 120 */ 121 public abstract PAIR[] getOptima(); 122 123 /** 124 * {@inheritDoc} 125 * 126 * @throws MathIllegalStateException if {@code optData} does not contain an 127 * instance of {@link MaxEval} or {@link InitialGuess}. 128 */ 129 @Override 130 public PAIR optimize(OptimizationData... optData) { 131 // Store arguments in order to pass them to the internal optimizer. 132 optimData = optData; 133 // Set up base class and perform computations. 134 return super.optimize(optData); 135 } 136 137 /** {@inheritDoc} */ 138 @Override 139 protected PAIR doOptimize() { 140 // Remove all instances of "MaxEval" and "InitialGuess" from the 141 // array that will be passed to the internal optimizer. 142 // The former is to enforce smaller numbers of allowed evaluations 143 // (according to how many have been used up already), and the latter 144 // to impose a different start value for each start. 145 for (int i = 0; i < optimData.length; i++) { 146 if (optimData[i] instanceof MaxEval) { 147 optimData[i] = null; 148 maxEvalIndex = i; 149 } 150 if (optimData[i] instanceof InitialGuess) { 151 optimData[i] = null; 152 initialGuessIndex = i; 153 continue; 154 } 155 } 156 if (maxEvalIndex == -1) { 157 throw new MathIllegalStateException(); 158 } 159 if (initialGuessIndex == -1) { 160 throw new MathIllegalStateException(); 161 } 162 163 RuntimeException lastException = null; 164 totalEvaluations = 0; 165 clear(); 166 167 final int maxEval = getMaxEvaluations(); 168 final double[] min = getLowerBound(); 169 final double[] max = getUpperBound(); 170 final double[] startPoint = getStartPoint(); 171 172 // Multi-start loop. 173 for (int i = 0; i < starts; i++) { 174 // CHECKSTYLE: stop IllegalCatch 175 try { 176 // Decrease number of allowed evaluations. 177 optimData[maxEvalIndex] = new MaxEval(maxEval - totalEvaluations); 178 // New start value. 179 double[] s = null; 180 if (i == 0) { 181 s = startPoint; 182 } else { 183 int attempts = 0; 184 while (s == null) { 185 if (attempts++ >= getMaxEvaluations()) { 186 throw new TooManyEvaluationsException(getMaxEvaluations()); 187 } 188 s = generator.nextVector(); 189 for (int k = 0; s != null && k < s.length; ++k) { 190 if ((min != null && s[k] < min[k]) || (max != null && s[k] > max[k])) { 191 // reject the vector 192 s = null; 193 } 194 } 195 } 196 } 197 optimData[initialGuessIndex] = new InitialGuess(s); 198 // Optimize. 199 final PAIR result = optimizer.optimize(optimData); 200 store(result); 201 } catch (RuntimeException mue) { 202 lastException = mue; 203 } 204 // CHECKSTYLE: resume IllegalCatch 205 206 totalEvaluations += optimizer.getEvaluations(); 207 } 208 209 final PAIR[] optima = getOptima(); 210 if (optima.length == 0) { 211 // All runs failed. 212 throw lastException; // Cannot be null if starts >= 1. 213 } 214 215 // Return the best optimum. 216 return optima[0]; 217 } 218 219 /** 220 * Method that will be called in order to store each found optimum. 221 * 222 * @param optimum Result of an optimization run. 223 */ 224 protected abstract void store(PAIR optimum); 225 /** 226 * Method that will called in order to clear all stored optima. 227 */ 228 protected abstract void clear(); 229}