GestureRecognitionToolkit  Version: 0.1.0
The Gesture Recognition Toolkit (GRT) is a cross-platform, open-source, c++ machine learning library for real-time gesture recognition.
ParticleSwarmOptimization.h
Go to the documentation of this file.
1 
12 /*
13  GRT MIT License
14  Copyright (c) <2012> <Nicholas Gillian, Media Lab, MIT>
15 
16  Permission is hereby granted, free of charge, to any person obtaining a copy of this software
17  and associated documentation files (the "Software"), to deal in the Software without restriction,
18  including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense,
19  and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so,
20  subject to the following conditions:
21 
22  The above copyright notice and this permission notice shall be included in all copies or substantial
23  portions of the Software.
24 
25  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT
26  LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
27  IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
28  WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
29  SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
30  */
31 
32 #ifndef GRT_PARTICLE_SWARM_OPTIMIZATION_HEADER
33 #define GRT_PARTICLE_SWARM_OPTIMIZATION_HEADER
34 
35 #include "../../Util/GRTCommon.h"
36 #include "PSOParticle.h"
37 
38 GRT_BEGIN_NAMESPACE
39 
40 template<class PARTICLE_TYPE,class OBSERVATION_TYPE>
42 
43 public:
47  ParticleSwarmOptimization() : infoLog("[ParticleSwarmOptimization]"), errorLog("[ERROR ParticleSwarmOptimization]") {
48  initialized = false;
49  minImprovement = 1.0e-10;
50  maxIter = 500;
51  maxNumIterNoChange = 10;
52  }
53 
58  globalBestX.clear();
59  particles.clear();
60  }
61 
68  PARTICLE_TYPE& operator[](const unsigned int &index){
69  return particles[ index ];
70  }
71 
88  virtual bool init(const unsigned int numParticles,const unsigned int K,const VectorFloat &xMin,const VectorFloat &xMax,const VectorFloat &propagationModel){
89 
90  initialized = false;
91 
92  if( K != xMin.size() || K != xMax.size() ) return false;
93 
94  this->K = K;
95  this->xMin = xMin;
96  this->xMax = xMax;
97  this->propagationModel = propagationModel;
98 
99  //Clear any previous searches
100  particles.clear();
101  iterHistory.clear();
102  globalBestXHistory.clear();
103 
104  //Reset the global variables
105  globalBestCost = 0;
106  globalBestX.clear();
107  globalBestX.resize(K,0);
108 
109  //Initialize the new particles with random positions and velocities
110  Random random;
111  particles.resize(numParticles);
112  typename Vector< PARTICLE_TYPE >::iterator pIter = particles.begin();
113  for(pIter = particles.begin(); pIter != particles.end(); pIter++){
114  pIter->setRandomSeed( random.getRandomNumberInt(0, 100000) );
115  pIter->init(K,xMin,xMax);
116  }
117 
118  //Store the initial distrubution
119  iterHistory.push_back( particles );
120  globalBestXHistory.push_back( globalBestX );
121 
122  //Flag that everything has been initialized
123  initialized = true;
124 
125  return true;
126  }
127 
133  virtual bool reset(){
134 
135  if( !initialized ) return false;
136 
137  typename Vector< PARTICLE_TYPE >::iterator pIter = particles.begin();
138  for(pIter = particles.begin(); pIter != particles.end(); pIter++){
139  pIter->reset();
140  }
141 
142  return true;
143  }
144 
151  virtual bool search(OBSERVATION_TYPE &observation){
152 
153  if( !initialized ) return false;
154 
155  //Propagate all the particles
156  typename Vector< PARTICLE_TYPE >::iterator pIter;
157  for(pIter = particles.begin(); pIter != particles.end(); pIter++){
158  if( !pIter->propagate( propagationModel ) ){
159  errorLog << "search(...) - Particle propagation failed!" << std::endl;
160  return false;
161  }
162  }
163 
164  unsigned int iterCounter = 0;
165  unsigned int numIterNoChangeCounter = 0;
166  Float currentMaxima = 0;
167  Float lastMaxima = 0;
168  Float delta = 0;
169  bool keepSearching = true;
170 
171  //Decrement the global best cost
172  globalBestCost = 0;
173 
174  while( keepSearching ){
175  currentMaxima = searchIteration( observation );
176 
177  iterHistory.push_back( particles );
178  globalBestXHistory.push_back( globalBestX );
179 
180  delta = fabs( currentMaxima - lastMaxima );
181  lastMaxima = currentMaxima;
182 
183  if( delta < minImprovement ){
184  if( ++numIterNoChangeCounter >= maxNumIterNoChange ){
185  keepSearching = false;
186  infoLog << "search(...) - Reached no change limit, stopping search at iteration: " << iterCounter << " with a change of: " << fabs( currentMaxima - lastMaxima ) << std::endl;
187  }
188  }else numIterNoChangeCounter = 0;
189 
190  if( ++iterCounter == maxIter ){
191  keepSearching = false;
192  infoLog << "search(...) - Max iteration reached, stopping search at iteration: " << iterCounter << std::endl;
193  }
194  }
195 
196  //Compute the final state estimation
198 
199  return true;
200  }
201 
209  virtual Float searchIteration(OBSERVATION_TYPE &observation){
210 
211  if( !initialized ) return 0;
212 
213  unsigned int index = 0;
214  unsigned int bestIndex = 0;
215  Float currentBestMaxima = 0;
216  Float epsilon = 0;
217  typename Vector< PARTICLE_TYPE >::iterator pIter;
218 
219  //Compute the cost for each particle, tracking the best cost of all the particles in the swarm
220  for(pIter = particles.begin(); pIter != particles.end(); pIter++){
221 
222  //Evaluate the current particle
223  epsilon = pIter->evaluate(observation);
224 
225  //Check to see if this is the best
226  if( epsilon > currentBestMaxima ){
227  currentBestMaxima = epsilon;
228  bestIndex = index;
229  }
230 
231  index++;
232  }
233 
234  //Check to see if we need to update the global cost and position
235  if( currentBestMaxima > globalBestCost ){
236  globalBestCost = currentBestMaxima;
237  globalBestX = particles[ bestIndex ].x;
238  }
239 
240  //Update the position and velocity of all of the particles
241  for(pIter = particles.begin(); pIter != particles.end(); pIter++){
242  pIter->update( globalBestX );
243  }
244 
245  return currentBestMaxima;
246  }
247 
255 
256  if( !initialized ) return false;
257 
258  this->propagationModel = propagationModel;
259 
260  return true;
261  }
262 
263  bool initialized;
264  unsigned int K;
265  Float minImprovement;
266  unsigned int maxIter;
267  unsigned int maxNumIterNoChange;
277 
278  InfoLog infoLog;
279  ErrorLog errorLog;
280 };
281 
282 GRT_END_NAMESPACE
283 
284 #endif //GRT_PARTICLE_SWARM_OPTIMIZATION_HEADER
bool initialized
A flag to indicate if the PSO algorithm has been initialized.
Definition: Random.h:40
virtual bool resize(const unsigned int size)
Definition: Vector.h:133
VectorFloat globalBestX
The state Vector of the particle with the best cost.
VectorFloat xMin
The minimum range of the state space.
Float globalBestCost
The current global best cost over all the particles.
bool setPropagationModel(const VectorFloat &propagationModel)
Vector< PARTICLE_TYPE > particles
A Vector containing all the particles used for the search.
Vector< Vector< PARTICLE_TYPE > > iterHistory
A buffer to keep track of the search history.
unsigned int K
The size of the particles state Vector.
PARTICLE_TYPE & operator[](const unsigned int &index)
int getRandomNumberInt(int minRange, int maxRange)
Definition: Random.h:88
Vector< VectorFloat > globalBestXHistory
A buffer to keep track of the search history.
virtual Float searchIteration(OBSERVATION_TYPE &observation)
Definition: Vector.h:41
VectorFloat propagationModel
The propagation model used to update each particle.
VectorFloat xMax
The maximum range of the state space.
virtual bool init(const unsigned int numParticles, const unsigned int K, const VectorFloat &xMin, const VectorFloat &xMax, const VectorFloat &propagationModel)
VectorFloat finalX
The final estimate.
virtual bool search(OBSERVATION_TYPE &observation)