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.math3.optimization.univariate; 019 020 import java.util.Arrays; 021 import java.util.Comparator; 022 023 import org.apache.commons.math3.analysis.UnivariateFunction; 024 import org.apache.commons.math3.exception.MathIllegalStateException; 025 import org.apache.commons.math3.exception.NotStrictlyPositiveException; 026 import org.apache.commons.math3.exception.NullArgumentException; 027 import org.apache.commons.math3.exception.util.LocalizedFormats; 028 import org.apache.commons.math3.random.RandomGenerator; 029 import org.apache.commons.math3.optimization.GoalType; 030 import org.apache.commons.math3.optimization.ConvergenceChecker; 031 032 /** 033 * Special implementation of the {@link UnivariateOptimizer} interface 034 * adding multi-start features to an existing optimizer. 035 * 036 * This class wraps a classical optimizer to use it several times in 037 * turn with different starting points in order to avoid being trapped 038 * into a local extremum when looking for a global one. 039 * 040 * @param <FUNC> Type of the objective function to be optimized. 041 * 042 * @version $Id: UnivariateMultiStartOptimizer.java 1422230 2012-12-15 12:11:13Z erans $ 043 * @deprecated As of 3.1 (to be removed in 4.0). 044 * @since 3.0 045 */ 046 @Deprecated 047 public class UnivariateMultiStartOptimizer<FUNC extends UnivariateFunction> 048 implements BaseUnivariateOptimizer<FUNC> { 049 /** Underlying classical optimizer. */ 050 private final BaseUnivariateOptimizer<FUNC> optimizer; 051 /** Maximal number of evaluations allowed. */ 052 private int maxEvaluations; 053 /** Number of evaluations already performed for all starts. */ 054 private int totalEvaluations; 055 /** Number of starts to go. */ 056 private int starts; 057 /** Random generator for multi-start. */ 058 private RandomGenerator generator; 059 /** Found optima. */ 060 private UnivariatePointValuePair[] optima; 061 062 /** 063 * Create a multi-start optimizer from a single-start optimizer. 064 * 065 * @param optimizer Single-start optimizer to wrap. 066 * @param starts Number of starts to perform. If {@code starts == 1}, 067 * the {@code optimize} methods will return the same solution as 068 * {@code optimizer} would. 069 * @param generator Random generator to use for restarts. 070 * @throws NullArgumentException if {@code optimizer} or {@code generator} 071 * is {@code null}. 072 * @throws NotStrictlyPositiveException if {@code starts < 1}. 073 */ 074 public UnivariateMultiStartOptimizer(final BaseUnivariateOptimizer<FUNC> optimizer, 075 final int starts, 076 final RandomGenerator generator) { 077 if (optimizer == null || 078 generator == null) { 079 throw new NullArgumentException(); 080 } 081 if (starts < 1) { 082 throw new NotStrictlyPositiveException(starts); 083 } 084 085 this.optimizer = optimizer; 086 this.starts = starts; 087 this.generator = generator; 088 } 089 090 /** 091 * {@inheritDoc} 092 */ 093 public ConvergenceChecker<UnivariatePointValuePair> getConvergenceChecker() { 094 return optimizer.getConvergenceChecker(); 095 } 096 097 /** {@inheritDoc} */ 098 public int getMaxEvaluations() { 099 return maxEvaluations; 100 } 101 102 /** {@inheritDoc} */ 103 public int getEvaluations() { 104 return totalEvaluations; 105 } 106 107 /** 108 * Get all the optima found during the last call to {@link 109 * #optimize(int,UnivariateFunction,GoalType,double,double) optimize}. 110 * The optimizer stores all the optima found during a set of 111 * restarts. The {@link #optimize(int,UnivariateFunction,GoalType,double,double) optimize} 112 * method returns the best point only. This method returns all the points 113 * found at the end of each starts, including the best one already 114 * returned by the {@link #optimize(int,UnivariateFunction,GoalType,double,double) optimize} 115 * method. 116 * <br/> 117 * The returned array as one element for each start as specified 118 * in the constructor. It is ordered with the results from the 119 * runs that did converge first, sorted from best to worst 120 * objective value (i.e in ascending order if minimizing and in 121 * descending order if maximizing), followed by {@code null} elements 122 * corresponding to the runs that did not converge. This means all 123 * elements will be {@code null} if the {@link 124 * #optimize(int,UnivariateFunction,GoalType,double,double) optimize} 125 * method did throw an exception. 126 * This also means that if the first element is not {@code null}, it is 127 * the best point found across all starts. 128 * 129 * @return an array containing the optima. 130 * @throws MathIllegalStateException if {@link 131 * #optimize(int,UnivariateFunction,GoalType,double,double) optimize} 132 * has not been called. 133 */ 134 public UnivariatePointValuePair[] getOptima() { 135 if (optima == null) { 136 throw new MathIllegalStateException(LocalizedFormats.NO_OPTIMUM_COMPUTED_YET); 137 } 138 return optima.clone(); 139 } 140 141 /** {@inheritDoc} */ 142 public UnivariatePointValuePair optimize(int maxEval, final FUNC f, 143 final GoalType goal, 144 final double min, final double max) { 145 return optimize(maxEval, f, goal, min, max, min + 0.5 * (max - min)); 146 } 147 148 /** {@inheritDoc} */ 149 public UnivariatePointValuePair optimize(int maxEval, final FUNC f, 150 final GoalType goal, 151 final double min, final double max, 152 final double startValue) { 153 RuntimeException lastException = null; 154 optima = new UnivariatePointValuePair[starts]; 155 totalEvaluations = 0; 156 157 // Multi-start loop. 158 for (int i = 0; i < starts; ++i) { 159 // CHECKSTYLE: stop IllegalCatch 160 try { 161 final double s = (i == 0) ? startValue : min + generator.nextDouble() * (max - min); 162 optima[i] = optimizer.optimize(maxEval - totalEvaluations, f, goal, min, max, s); 163 } catch (RuntimeException mue) { 164 lastException = mue; 165 optima[i] = null; 166 } 167 // CHECKSTYLE: resume IllegalCatch 168 169 totalEvaluations += optimizer.getEvaluations(); 170 } 171 172 sortPairs(goal); 173 174 if (optima[0] == null) { 175 throw lastException; // cannot be null if starts >=1 176 } 177 178 // Return the point with the best objective function value. 179 return optima[0]; 180 } 181 182 /** 183 * Sort the optima from best to worst, followed by {@code null} elements. 184 * 185 * @param goal Goal type. 186 */ 187 private void sortPairs(final GoalType goal) { 188 Arrays.sort(optima, new Comparator<UnivariatePointValuePair>() { 189 public int compare(final UnivariatePointValuePair o1, 190 final UnivariatePointValuePair o2) { 191 if (o1 == null) { 192 return (o2 == null) ? 0 : 1; 193 } else if (o2 == null) { 194 return -1; 195 } 196 final double v1 = o1.getValue(); 197 final double v2 = o2.getValue(); 198 return (goal == GoalType.MINIMIZE) ? 199 Double.compare(v1, v2) : Double.compare(v2, v1); 200 } 201 }); 202 } 203 }