1 /*========================================================================= 2 * 3 * Copyright Insight Software Consortium 4 * 5 * Licensed under the Apache License, Version 2.0 (the "License"); 6 * you may not use this file except in compliance with the License. 7 * You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0.txt 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 19 #ifndef itkParticleSwarmOptimizerBase_h 20 #define itkParticleSwarmOptimizerBase_h 21 22 #include "itkSingleValuedNonLinearOptimizer.h" 23 #include "itkMersenneTwisterRandomVariateGenerator.h" 24 #include "ITKOptimizersExport.h" 25 26 namespace itk 27 { 28 /** \class ParticleSwarmOptimizerBase 29 * \brief Abstract implementation of a Particle Swarm Optimization (PSO) algorithm. 30 * 31 * The PSO algorithm was originally presented in:<br> 32 * J. Kennedy, R. Eberhart, "Particle Swarm Optimization", 33 * Proc. IEEE Int. Neural Networks, 1995.<br> 34 * 35 * The algorithm is a stochastic global search optimization approach. 36 * Optimization is performed by maintaining a swarm of particles that traverse 37 * the parameter space, searching for the optimal function value. Associated 38 * with each particle are its location and speed, in parameter space. 39 * 40 * Swarm initialization is performed within the user supplied parameter bounds 41 * using either a uniform distribution or a normal distribution centered on 42 * the initial parameter values supplied by the user. The search terminates when 43 * the maximal number of iterations has been reached or when the change in the 44 * best value in the past \f$g\f$ generations is below a threshold and the swarm 45 * has collapsed (i.e. best personal particle locations are close to the 46 * swarm's best location in parameter space). 47 * 48 * The actual optimization procedure, updating the swarm, is performed in the 49 * subclasses, required to implement the UpdateSwarm() method. 50 * 51 * NOTE: This implementation only performs minimization. 52 * 53 * \ingroup Numerics Optimizers 54 * \ingroup ITKOptimizers 55 */ 56 class ITKOptimizers_EXPORT ParticleSwarmOptimizerBase : 57 public SingleValuedNonLinearOptimizer 58 { 59 public: 60 ITK_DISALLOW_COPY_AND_ASSIGN(ParticleSwarmOptimizerBase); 61 62 /** Standard "Self" type alias. */ 63 using Self = ParticleSwarmOptimizerBase; 64 using Superclass = SingleValuedNonLinearOptimizer; 65 using Pointer = SmartPointer<Self>; 66 using ConstPointer = SmartPointer<const Self>; 67 68 /** Run-time type information (and related methods). */ 69 itkTypeMacro( ParticleSwarmOptimizerBase, SingleValuedNonLinearOptimizer ) 70 71 using ParameterBoundsType = std::vector< std::pair<ParametersType::ValueType, 72 ParametersType::ValueType> >; 73 74 struct ParticleData 75 { 76 ParametersType m_CurrentParameters; 77 ParametersType m_CurrentVelocity; 78 CostFunctionType::MeasureType m_CurrentValue; 79 ParametersType m_BestParameters; 80 CostFunctionType::MeasureType m_BestValue; 81 }; 82 83 using SwarmType = std::vector<ParticleData>; 84 using NumberOfIterationsType = unsigned int; 85 using NumberOfParticlesType = unsigned int; 86 using NumberOfGenerationsType = unsigned int; 87 using MeasureType = CostFunctionType::MeasureType; 88 using ValueType = ParametersType::ValueType; 89 using RandomVariateGeneratorType = Statistics::MersenneTwisterRandomVariateGenerator; 90 91 /** Specify whether to initialize the particles using a normal distribution 92 * centered on the user supplied initial value or a uniform distribution. 93 * If the optimum is expected to be near the initial value it is likely 94 * that initializing with a normal distribution will result in faster 95 * convergence.*/ 96 itkSetMacro( InitializeNormalDistribution, bool ) 97 itkGetMacro( InitializeNormalDistribution, bool ) 98 itkBooleanMacro( InitializeNormalDistribution ) 99 100 /** 101 * Specify the initial swarm. Useful for evaluating PSO variants. If the 102 * initial swarm is set it will be used. To revert to random initialization 103 * (uniform or normal particle distributions) set using an empty swarm. 104 */ 105 void SetInitialSwarm( const SwarmType &initialSwarm ); 106 void ClearSwarm(); 107 108 /** 109 * Indicate whether or not to output the swarm information when printing an 110 * object. By default this option is turned off as it generates too much 111 * information. 112 */ 113 itkSetMacro( PrintSwarm, bool ) 114 itkGetMacro( PrintSwarm, bool ) 115 itkBooleanMacro( PrintSwarm ) 116 117 /** Start optimization. */ 118 void StartOptimization() override; 119 120 121 /** Set/Get number of particles in the swarm - the maximal number of function 122 evaluations is m_MaximalNumberOfIterations*m_NumberOfParticles */ 123 void SetNumberOfParticles( NumberOfParticlesType n ); 124 itkGetMacro( NumberOfParticles, NumberOfParticlesType ) 125 126 /** Set/Get maximal number of iterations - the maximal number of function 127 evaluations is m_MaximalNumberOfIterations*m_NumberOfParticles */ 128 itkSetMacro( MaximalNumberOfIterations, NumberOfIterationsType ) 129 itkGetMacro( MaximalNumberOfIterations, NumberOfIterationsType ) 130 131 /** Set/Get the number of generations to continue with minimal improvement in 132 * the function value, |f_best(g_i) - f_best(g_k)|<threshold where 133 * k <= i+NumberOfGenerationsWithMinimalImprovement 134 * Minimal value is one.*/ 135 itkSetMacro( NumberOfGenerationsWithMinimalImprovement, NumberOfGenerationsType ) 136 itkGetMacro( NumberOfGenerationsWithMinimalImprovement, NumberOfGenerationsType ) 137 138 /**Set/Get the parameter bounds. Search for optimal value is inside these 139 bounds. NOTE: It is assumed that the first entry is the minimal value, 140 second is the maximal value. */ 141 virtual void SetParameterBounds( ParameterBoundsType & bounds ); 142 void SetParameterBounds( std::pair<ParametersType::ValueType, 143 ParametersType::ValueType> &bounds, 144 unsigned int n ); 145 146 ParameterBoundsType GetParameterBounds() const; 147 148 /** The optimization algorithm will terminate when the function improvement 149 * in the last m_NumberOfGenerationsWithMinimalImprovement generations 150 * is less than m_FunctionConvergenceTolerance and the maximal distance 151 * between particles and the best particle in each dimension is less than 152 * m_ParametersConvergenceTolerance[i] for the specified percentage of the 153 * particles. 154 * That is, we haven't improved the best function value for a while and in 155 * the parameter space most (m%) of our particles attained their best value 156 * close to the swarm's best value. 157 * NOTE: The use of different tolerances for each dimension is desired when 158 * optimizing over non-commensurate parameters (e.g. rotation and 159 * translation). Alternatively, we could use ITK's parameter scaling 160 * approach. The current approach seems more intuitive. 161 */ 162 itkSetMacro( FunctionConvergenceTolerance, MeasureType ) 163 itkGetMacro( FunctionConvergenceTolerance, MeasureType ) 164 /**Set parameters convergence tolerance using the same value for all, sz, 165 parameters*/ 166 void SetParametersConvergenceTolerance( ValueType convergenceTolerance, 167 unsigned int sz ); 168 itkSetMacro( ParametersConvergenceTolerance, ParametersType ) 169 itkGetMacro( ParametersConvergenceTolerance, ParametersType ) 170 itkGetMacro( PercentageParticlesConverged, double ) 171 itkSetMacro( PercentageParticlesConverged, double ) 172 173 /**Set the random number seed for the swarm. Use this method to 174 * produce reaptible results, typically, for testing. 175 */ 176 itkSetMacro( Seed, RandomVariateGeneratorType::IntegerType) 177 itkGetMacro( Seed, RandomVariateGeneratorType::IntegerType) 178 179 /** Use a specific seed to initialize the random number 180 * generator. If On, use m_Seed to seed the random number 181 * generator. Default is Off. */ 182 itkSetMacro( UseSeed, bool ) 183 itkGetMacro( UseSeed, bool ) 184 itkBooleanMacro( UseSeed) 185 186 /** Get the function value for the current position. 187 * NOTE: This value is only valid during and after the execution of the 188 * StartOptimization() method.*/ 189 MeasureType GetValue() const; 190 191 /** Get the reason for termination */ 192 const std::string GetStopConditionDescription() const override; 193 194 /** Print the swarm information to the given output stream. Each line 195 * (particle data) is of the form: 196 * current_parameters current_velocity current_value best_parameters best_value 197 */ 198 void PrintSwarm( std::ostream& os, Indent indent ) const; 199 200 protected: 201 ParticleSwarmOptimizerBase(); 202 ~ParticleSwarmOptimizerBase() override; 203 void PrintSelf( std::ostream& os, Indent indent ) const override; 204 void PrintParamtersType( const ParametersType& x, std::ostream& os ) const; 205 206 /** 207 * Implement your update rule in this function.*/ 208 virtual void UpdateSwarm() = 0; 209 210 virtual void ValidateSettings(); 211 212 /** 213 * Initialize the particle swarm, and seed the random number generator. 214 */ 215 virtual void Initialize(); 216 217 void RandomInitialization(); 218 void FileInitialization(); 219 220 bool m_PrintSwarm; 221 std::ostringstream m_StopConditionDescription; 222 bool m_InitializeNormalDistribution; 223 NumberOfParticlesType m_NumberOfParticles; 224 NumberOfIterationsType m_MaximalNumberOfIterations; 225 NumberOfGenerationsType m_NumberOfGenerationsWithMinimalImprovement; 226 ParameterBoundsType m_ParameterBounds; 227 ParametersType m_ParametersConvergenceTolerance; 228 double m_PercentageParticlesConverged; 229 CostFunctionType::MeasureType m_FunctionConvergenceTolerance; 230 std::vector<ParticleData> m_Particles; 231 CostFunctionType::MeasureType m_FunctionBestValue{0}; 232 std::vector<MeasureType> m_FunctionBestValueMemory; 233 ParametersType m_ParametersBestValue; 234 NumberOfIterationsType m_IterationIndex{0}; 235 RandomVariateGeneratorType::IntegerType m_Seed; 236 bool m_UseSeed; 237 }; 238 } // end namespace itk 239 240 #endif 241