28 #ifndef SHARK_EA_GRID_H 29 #define SHARK_EA_GRID_H 31 #include <boost/foreach.hpp> 41 Hypercube() : m_size( 0. ),
43 m_isOccupied( false ) {
47 unsigned int m_noSolutions;
51 typedef std::map< std::size_t, Hypercube >::iterator iterator;
52 typedef std::map< std::size_t, Hypercube >::const_iterator const_iterator;
54 std::map< std::size_t, Hypercube > m_denseGrid;
55 iterator m_mostOccupiedHypercube;
60 unsigned int m_noBisections;
66 RealVector m_lowerBounds;
71 RealVector m_upperBounds;
84 AdaptiveGrid(
unsigned int noBisections = 0,
unsigned int noObjectives = 0 ) {
85 reset( noBisections, noObjectives );
88 void reset(
unsigned int noBisections,
unsigned int noObjectives ) {
89 m_noBisections = noBisections;
94 m_extents = RealVector( noObjectives, 0 );
98 m_mostOccupiedHypercube = m_denseGrid.end();
106 template<
typename Set>
107 void updateLimits(
const Set & solutionSet ) {
112 typename Set::const_iterator it;
113 for( it = solutionSet.begin(); it != solutionSet.end(); ++it ) {
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] );
120 m_extents = m_upperBounds - m_lowerBounds;
129 template<
typename Set>
130 void addSolutionSet(
const Set & solutionSet) {
131 m_mostOccupiedHypercube = m_denseGrid.begin();
133 typename Set::const_iterator it;
134 for( it = solutionSet.begin(); it != solutionSet.end(); ++it ) {
135 itt = location( *it );
138 throw(
shark::Exception(
"AdaptiveGrid::addSolutionSet: The grid limits need to be calculated before." ) );
156 template<
typename Set>
157 void updateGrid(
const Set & solutionSet ){
160 updateLimits( solutionSet );
163 m_mostOccupiedHypercube = m_denseGrid.end();
166 addSolutionSet(solutionSet);
178 template<
typename Solution,
typename Set>
179 void updateGrid(
const Solution & solution,
const Set & solutionSet ) {
181 int it = location( solution );
184 updateLimits( solutionSet );
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] );
192 m_extents = m_upperBounds - m_lowerBounds;
195 m_mostOccupiedHypercube = m_denseGrid.end();
198 addSolutionSet(solutionSet);
207 template<
typename Solution>
208 int location(
const Solution & solution )
const {
210 std::vector< std::size_t > positions( solution.fitness( shark::tag::PenalizedFitness() ).size(), 0 );
213 for( std::size_t obj = 0; obj < solution.fitness( shark::tag::PenalizedFitness() ).size(); obj++ ) {
215 if( solution.fitness( shark::tag::PenalizedFitness() )[ obj ] > m_upperBounds( obj ) )
217 if( solution.fitness( shark::tag::PenalizedFitness() )[ obj ] < m_lowerBounds( obj ) )
220 if( solution.fitness( shark::tag::PenalizedFitness() )[ obj ] == m_lowerBounds[obj] ) {
221 positions[ obj ] = 0;
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 );
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 ) ) ) );
236 for(
unsigned int b = 0; b < m_noBisections; b++ ) {
239 if( value > (account + tmpSize) ) {
240 positions[ obj ] += ranges;
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 ) ) ) );
258 iterator mostPopulated() {
259 return( m_mostOccupiedHypercube );
267 unsigned int locationDensity( std::size_t idx ) {
268 iterator it = m_denseGrid.find( idx );
269 if( it == m_denseGrid.end() )
271 return( it->second.m_noSolutions );
278 int removeSolution( std::size_t location ) {
279 iterator it = m_denseGrid.find( location );
280 if( it == m_denseGrid.end() )
283 it->second.m_noSolutions--;
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;
291 if( it->second.m_noSolutions == 0 ) {
292 m_denseGrid.erase( it );
297 return( it->second.m_noSolutions );
304 void addSolution( std::size_t location ) {
305 Hypercube &
h = m_denseGrid[location];
308 if( m_mostOccupiedHypercube != m_denseGrid.end() ) {
309 if( h.m_noSolutions > m_mostOccupiedHypercube->second.m_noSolutions ) {
310 m_mostOccupiedHypercube = m_denseGrid.find( location );
313 m_mostOccupiedHypercube = m_denseGrid.find( location );
317 if( h.m_noSolutions == 1 )
325 unsigned int noBisections() {
326 return( m_noBisections );
365 std::size_t calculateOccupied() {
366 return( m_denseGrid.size() );
373 std::size_t occupiedHypercubes(){
374 return( m_denseGrid.size() );