Grid.h
Go to the documentation of this file.
1 /*!
2  * \brief
3  *
4  * \author T.Voss
5  * \date 2011
6  *
7  *
8  * \par Copyright 1995-2015 Shark Development Team
9  *
10  * <BR><HR>
11  * This file is part of Shark.
12  * <http://image.diku.dk/shark/>
13  *
14  * Shark is free software: you can redistribute it and/or modify
15  * it under the terms of the GNU Lesser General Public License as published
16  * by the Free Software Foundation, either version 3 of the License, or
17  * (at your option) any later version.
18  *
19  * Shark is distributed in the hope that it will be useful,
20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22  * GNU Lesser General Public License for more details.
23  *
24  * You should have received a copy of the GNU Lesser General Public License
25  * along with Shark. If not, see <http://www.gnu.org/licenses/>.
26  *
27  */
28 #ifndef SHARK_EA_GRID_H
29 #define SHARK_EA_GRID_H
30 
31 #include <boost/foreach.hpp>
32 
33 #include <map>
34 #include <vector>
35 
36 namespace shark {
37  /** \cond */
38  class AdaptiveGrid {
39  public:
40  struct Hypercube {
41  Hypercube() : m_size( 0. ),
42  m_noSolutions( 0 ),
43  m_isOccupied( false ) {
44  }
45 
46  double m_size;
47  unsigned int m_noSolutions;
48  bool m_isOccupied;
49  };
50 
51  typedef std::map< std::size_t, Hypercube >::iterator iterator;
52  typedef std::map< std::size_t, Hypercube >::const_iterator const_iterator;
53 
54  std::map< std::size_t, Hypercube > m_denseGrid;
55  iterator m_mostOccupiedHypercube;
56 
57  /**
58  * Number of bi-divisions of the objective space
59  */
60  unsigned int m_noBisections;
61 
62  /**
63  *
64  * Grid lower bounds
65  */
66  RealVector m_lowerBounds;
67 
68  /**
69  * Grid upper bounds
70  */
71  RealVector m_upperBounds;
72 
73  /************************************************************************/
74  /* Extens of the grid */
75  /************************************************************************/
76  RealVector m_extents;
77 
78  /**
79  * Constructor.
80  * Creates an instance of AdaptativeGrid.
81  * @param noBisections Number of bi-divisions of the objective space.
82  * @param nObjetives Number of objectives of the problem.
83  */
84  AdaptiveGrid( unsigned int noBisections = 0, unsigned int noObjectives = 0 ) {
85  reset( noBisections, noObjectives );
86  } //AdaptativeGrid
87 
88  void reset( unsigned int noBisections, unsigned int noObjectives ) {
89  m_noBisections = noBisections;
90 
91  m_lowerBounds = RealVector( noObjectives, std::numeric_limits<double>::max() );
92  m_upperBounds = RealVector( noObjectives, -std::numeric_limits<double>::max() );
93 
94  m_extents = RealVector( noObjectives, 0 );
95 
96  // m_denseGrid = std::vector< Hypercube >( static_cast<std::size_t>( ::pow( 2., noBisections * noObjectives ) ) );
97  m_denseGrid.clear();
98  m_mostOccupiedHypercube = m_denseGrid.end();
99  }
100 
101  /**
102  * Updates the grid limits considering the solutions contained in a
103  * <code>SolutionSet</code>.
104  * @param solutionSet The <code>SolutionSet</code> considered.
105  */
106  template<typename Set>
107  void updateLimits( const Set & solutionSet ) {
108 
109  m_lowerBounds = RealVector( m_lowerBounds.size(), std::numeric_limits<double>::max() );
110  m_upperBounds = RealVector( m_lowerBounds.size(), -std::numeric_limits<double>::max() );
111 
112  typename Set::const_iterator it;
113  for( it = solutionSet.begin(); it != solutionSet.end(); ++it ) {
114 
115  for( unsigned int i = 0; i < it->fitness( shark::tag::PenalizedFitness() ).size(); i++ ) {
116  m_lowerBounds( i ) = std::min( m_lowerBounds( i ), it->fitness( shark::tag::PenalizedFitness() )[i] );
117  m_upperBounds( i ) = std::max( m_upperBounds( i ), it->fitness( shark::tag::PenalizedFitness() )[i] );
118  }
119  }
120  m_extents = m_upperBounds - m_lowerBounds;
121  } //updateLimits
122 
123  /**
124  * Updates the grid adding solutions contained in a specific
125  * <code>SolutionSet</code>.
126  * <b>REQUIRE</b> The grid limits must have been previously calculated.
127  * @param solutionSet The <code>SolutionSet</code> considered.
128  */
129  template<typename Set>
130  void addSolutionSet( const Set & solutionSet) {
131  m_mostOccupiedHypercube = m_denseGrid.begin();
132  int itt;
133  typename Set::const_iterator it;
134  for( it = solutionSet.begin(); it != solutionSet.end(); ++it ) {
135  itt = location( *it );
136 
137  if( itt == -1 )
138  throw( shark::Exception( "AdaptiveGrid::addSolutionSet: The grid limits need to be calculated before." ) );
139 
140  /*itt->second.m_noSolutions++;
141  if( m_mostOccupiedHypercube->second.m_noSolutions > itt->second.m_noSolutions )
142  std::swap( m_mostOccupiedHypercube, itt );*/
143  addSolution( itt );
144  } // for
145 
146  //The grid has been updated, so also update ocuppied's hypercubes
147  // calculateOccupied();
148  }
149 
150 
151  /**
152  * Updates the grid limits and the grid content adding the solutions contained
153  * in a specific <code>SolutionSet</code>.
154  * @param solutionSet The <code>SolutionSet</code>.
155  */
156  template<typename Set>
157  void updateGrid( const Set & solutionSet ){
158 
159  //Update lower and upper limits
160  updateLimits( solutionSet );
161 
162  m_denseGrid.clear();
163  m_mostOccupiedHypercube = m_denseGrid.end();
164 
165  //Add the population
166  addSolutionSet(solutionSet);
167  } //updateGrid
168 
169 
170  /**
171  * Updates the grid limits and the grid content adding a new
172  * <code>Solution</code>.
173  * If the solution falls out of the grid bounds, the limits and content of the
174  * grid must be re-calculated.
175  * @param solution <code>Solution</code> considered to update the grid.
176  * @param solutionSet <code>SolutionSet</code> used to update the grid.
177  */
178  template<typename Solution, typename Set>
179  void updateGrid( const Solution & solution, const Set & solutionSet ) {
180 
181  int it = location( solution );
182  if ( it == -1 ) {
183  //Update lower and upper limits
184  updateLimits( solutionSet );
185 
186  //Actualize the lower and upper limits whit the individual
187  for( std::size_t i = 0; i < solution.fitness( shark::tag::PenalizedFitness() ).size(); i++ ){
188  m_lowerBounds( i ) = std::min( m_lowerBounds( i ), solution.fitness( shark::tag::PenalizedFitness() )[i] );
189  m_upperBounds( i ) = std::max( m_upperBounds( i ), solution.fitness( shark::tag::PenalizedFitness() )[i] );
190  } // for
191 
192  m_extents = m_upperBounds - m_lowerBounds;
193 
194  m_denseGrid.clear();
195  m_mostOccupiedHypercube = m_denseGrid.end();
196 
197  //add the population
198  addSolutionSet(solutionSet);
199  } // if
200  } //updateGrid
201 
202 
203  /**
204  * Calculates the hypercube of a solution.
205  * @param solution The <code>Solution</code>.
206  */
207  template<typename Solution>
208  int location( const Solution & solution ) const {
209  //Create a int [] to store the range of each objective
210  std::vector< std::size_t > positions( solution.fitness( shark::tag::PenalizedFitness() ).size(), 0 );
211 
212  //Calculate the position for each objective
213  for( std::size_t obj = 0; obj < solution.fitness( shark::tag::PenalizedFitness() ).size(); obj++ ) {
214 
215  if( solution.fitness( shark::tag::PenalizedFitness() )[ obj ] > m_upperBounds( obj ) )
216  return( -1 );
217  if( solution.fitness( shark::tag::PenalizedFitness() )[ obj ] < m_lowerBounds( obj ) )
218  return( -1 );
219 
220  if( solution.fitness( shark::tag::PenalizedFitness() )[ obj ] == m_lowerBounds[obj] ) {
221  positions[ obj ] = 0;
222  continue;
223  }
224 
225  if( solution.fitness( shark::tag::PenalizedFitness() )[ obj ] == m_upperBounds[ obj ] ) {
226  positions[obj] = static_cast<std::size_t>( (::pow( 2.0, static_cast<double>( m_noBisections ) ) )-1 );
227  continue;
228  }
229 
230 
231  double tmpSize = m_extents( obj );
232  double value = solution.fitness( shark::tag::PenalizedFitness() )[ obj ];
233  double account = m_lowerBounds( obj );
234  std::size_t ranges = static_cast<std::size_t>( (::pow( 2.0, static_cast<double>( m_noBisections ) ) ) );
235 
236  for( unsigned int b = 0; b < m_noBisections; b++ ) {
237  tmpSize /= 2.0;
238  ranges /= 2;
239  if( value > (account + tmpSize) ) {
240  positions[ obj ] += ranges;
241  account += tmpSize;
242  }
243  }
244  }
245 
246  //Calculate the location into the hypercubes
247  std::size_t location = 0;
248  for( unsigned int obj = 0; obj < solution.fitness( shark::tag::PenalizedFitness() ).size(); obj++ ) {
249  location += positions[obj] * static_cast<std::size_t>( (::pow( 2.0, obj * static_cast<double>( m_noBisections ) ) ) );
250  }
251  return( location );
252  } //location
253 
254  /**
255  * Returns the value of the most populated hypercube.
256  * @return The hypercube with the maximum number of solutions.
257  */
258  iterator mostPopulated() {
259  return( m_mostOccupiedHypercube );
260  } // getMostPopulated
261 
262  /**
263  * Returns the number of solutions into a specific hypercube.
264  * @param idx Number of the hypercube.
265  * @return The number of solutions into a specific hypercube.
266  */
267  unsigned int locationDensity( std::size_t idx ) {
268  iterator it = m_denseGrid.find( idx );
269  if( it == m_denseGrid.end() )
270  return( 0 );
271  return( it->second.m_noSolutions );
272  } //getLocationDensity
273 
274  /**
275  * Decreases the number of solutions into a specific hypercube.
276  * @param location Number of hypercube.
277  */
278  int removeSolution( std::size_t location ) {
279  iterator it = m_denseGrid.find( location );
280  if( it == m_denseGrid.end() ) //TODO: Throw exception here?
281  return( -1 );
282  //Decrease the solutions in the location specified.
283  it->second.m_noSolutions--;
284 
285  if( m_mostOccupiedHypercube == it )
286  for( iterator itt = m_denseGrid.begin(); itt != m_denseGrid.end(); ++itt )
287  if( itt->second.m_noSolutions > m_mostOccupiedHypercube->second.m_noSolutions )
288  m_mostOccupiedHypercube = itt;
289 
290  //If hypercubes[location] now becomes to zero, then update ocupped hypercubes
291  if( it->second.m_noSolutions == 0 ) {
292  m_denseGrid.erase( it );
293  calculateOccupied();
294 
295  return( 0 );
296  }
297  return( it->second.m_noSolutions );
298  } //removeSolution
299 
300  /**
301  * Increases the number of solutions into a specific hypercube.
302  * @param location Number of hypercube.
303  */
304  void addSolution( std::size_t location ) {
305  Hypercube & h = m_denseGrid[location];
306  h.m_noSolutions++;
307 
308  if( m_mostOccupiedHypercube != m_denseGrid.end() ) {
309  if( h.m_noSolutions > m_mostOccupiedHypercube->second.m_noSolutions ) {
310  m_mostOccupiedHypercube = m_denseGrid.find( location );
311  }
312  } else
313  m_mostOccupiedHypercube = m_denseGrid.find( location );
314 
315  //if hypercubes[location] becomes to one, then recalculate
316  //the occupied hypercubes
317  if( h.m_noSolutions == 1 )
318  calculateOccupied();
319  } //addSolution
320 
321  /**
322  * Returns the number of bi-divisions performed in each objective.
323  * @return the number of bi-divisions.
324  */
325  unsigned int noBisections() {
326  return( m_noBisections );
327  } //getBisections
328 
329  /**
330  * Returns a random hypercube using a rouleteWheel method.
331  * @return the number of the selected hypercube.
332  */
333  // public int rouletteWheel(){
334  // //Calculate the inverse sum
335  // double inverseSum = 0.0;
336  // for (int i = 0; i < hypercubes_.length; i++) {
337  // if (hypercubes_[i] > 0) {
338  // inverseSum += 1.0 / (double)hypercubes_[i];
339  // }
340  // }
341  //
342  // //Calculate a random value between 0 and sumaInversa
343  // double random = PseudoRandom.randDouble(0.0,inverseSum);
344  // int hypercube = 0;
345  // double accumulatedSum = 0.0;
346  // while (hypercube < hypercubes_.length){
347  // if (hypercubes_[hypercube] > 0) {
348  // accumulatedSum += 1.0 / (double)hypercubes_[hypercube];
349  // } // if
350  //
351  // if (accumulatedSum > random) {
352  // return hypercube;
353  // } // if
354  //
355  // hypercube++;
356  // } // while
357  //
358  // return hypercube;
359  // } //rouletteWheel
360 
361  /**
362  * Calculates the number of hypercubes having one or more solutions.
363  * return the number of hypercubes with more than zero solutions.
364  */
365  std::size_t calculateOccupied() {
366  return( m_denseGrid.size() );
367  } //calculateOcuppied
368 
369  /**
370  * Returns the number of hypercubes with more than zero solutions.
371  * @return the number of hypercubes with more than zero solutions.
372  */
373  std::size_t occupiedHypercubes(){
374  return( m_denseGrid.size() );
375  } // occupiedHypercubes
376 
377 
378  /**
379  * Returns a random hypercube that has more than zero solutions.
380  * @return The hypercube.
381  */
382 // iterator randomOccupiedHypercube(){
383 // return( m_denseGrid.begin() + Rng::discrete( 0, m_denseGrid.size() ) );
384 // } //randomOccupiedHypercube
385  }; //AdaptativeGrid
386 }
387 
388 /** \endcond */
389 #endif