GClasses

GClasses::GProbeSearch Class Reference

This is somewhat of a multi-dimensional version of binary-search. It greedily probes the best choices first, but then starts trying the opposite choices at the higher divisions so that it can also handle non-monotonic target functions. Each iteration performs a binary (divide-and-conquer) search within the unit hypercube. (Your target function should scale the candidate vectors as necessary to cover the desired space.) Because the high-level divisions are typically less correlated with the quality of the final result than the low-level divisions, it searches through the space of possible "probes" by toggling choices in the order from high level to low level. In low-dimensional space, this algorithm tends to quickly find good solutions, especially if the target function is somewhat smooth. In high-dimensional space, the number of iterations to find a good solution seems to grow exponentially. More...

#include <GStabSearch.h>

Inheritance diagram for GClasses::GProbeSearch:
GClasses::GOptimizer

List of all members.

Public Member Functions

 GProbeSearch (GTargetFunction *pCritic)
virtual ~GProbeSearch ()
virtual double iterate ()
 Do a little bit more work toward finding a good vector.
virtual double * currentVector ()
 Returns the best vector yet found.
void setStabDepth (size_t n)
 Specify the number of times to divide the space before satisfactory accuracy is obtained. Larger values will result in more computation, but will find more precise values. For most problems, 20 to 30 should be sufficient.
size_t stabCount ()
 Returns the total number of completed stabs.
void setSampleCount (size_t n)
 Specify the number of vectors to use to sample each side of a binary-split division.

Static Public Member Functions

static void test ()
 Performs unit tests for this class. Throws an exception if there is a failure.

Protected Member Functions

void resetStab ()
void reset ()
double sample (bool greater)

Protected Attributes

GRand m_rand
size_t m_nDimensions
unsigned int m_nMask [4]
double * m_pMins
double * m_pMaxs
double * m_pVector
double * m_pBestYet
double m_bestError
size_t m_nStabDepth
size_t m_nCurrentDim
size_t m_nDepth
size_t m_nStabs
size_t m_samples

Detailed Description

This is somewhat of a multi-dimensional version of binary-search. It greedily probes the best choices first, but then starts trying the opposite choices at the higher divisions so that it can also handle non-monotonic target functions. Each iteration performs a binary (divide-and-conquer) search within the unit hypercube. (Your target function should scale the candidate vectors as necessary to cover the desired space.) Because the high-level divisions are typically less correlated with the quality of the final result than the low-level divisions, it searches through the space of possible "probes" by toggling choices in the order from high level to low level. In low-dimensional space, this algorithm tends to quickly find good solutions, especially if the target function is somewhat smooth. In high-dimensional space, the number of iterations to find a good solution seems to grow exponentially.


Constructor & Destructor Documentation

GClasses::GProbeSearch::GProbeSearch ( GTargetFunction pCritic)
virtual GClasses::GProbeSearch::~GProbeSearch ( ) [virtual]

Member Function Documentation

virtual double* GClasses::GProbeSearch::currentVector ( ) [inline, virtual]

Returns the best vector yet found.

Implements GClasses::GOptimizer.

virtual double GClasses::GProbeSearch::iterate ( ) [virtual]

Do a little bit more work toward finding a good vector.

Implements GClasses::GOptimizer.

void GClasses::GProbeSearch::reset ( ) [protected]
void GClasses::GProbeSearch::resetStab ( ) [protected]
double GClasses::GProbeSearch::sample ( bool  greater) [protected]
void GClasses::GProbeSearch::setSampleCount ( size_t  n) [inline]

Specify the number of vectors to use to sample each side of a binary-split division.

void GClasses::GProbeSearch::setStabDepth ( size_t  n) [inline]

Specify the number of times to divide the space before satisfactory accuracy is obtained. Larger values will result in more computation, but will find more precise values. For most problems, 20 to 30 should be sufficient.

size_t GClasses::GProbeSearch::stabCount ( ) [inline]

Returns the total number of completed stabs.

static void GClasses::GProbeSearch::test ( ) [static]

Performs unit tests for this class. Throws an exception if there is a failure.


Member Data Documentation

unsigned int GClasses::GProbeSearch::m_nMask[4] [protected]
double* GClasses::GProbeSearch::m_pMaxs [protected]
double* GClasses::GProbeSearch::m_pMins [protected]
double* GClasses::GProbeSearch::m_pVector [protected]