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 <GGridSearch.h>

Inheritance diagram for GClasses::GProbeSearch:

Public Member Functions
	GProbeSearch (GTargetFunction *pCritic)
virtual	~GProbeSearch ()
virtual double *	currentVector ()
	Returns the best vector yet found. More...
virtual double	iterate ()
	Do a little bit more work toward finding a good vector. More...
void	setSampleCount (size_t n)
	Specify the number of vectors to use to sample each side of a binary-split division. More...
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. More...
size_t	stabCount ()
	Returns the total number of completed stabs. More...
Public Member Functions inherited from GClasses::GOptimizer
	GOptimizer (GTargetFunction *pCritic)
virtual	~GOptimizer ()
double	searchUntil (size_t nBurnInIterations, size_t nIterations, double dImprovement)
	This will first call iterate() nBurnInIterations times, then it will repeatedly call iterate() in blocks of nIterations times. If the error heuristic has not improved by the specified ratio after a block of iterations, it will stop. (For example, if the error before the block of iterations was 50, and the error after is 49, then training will stop if dImprovement is > 0.02.) If the error heuristic is not stable, then the value of nIterations should be large. More...

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

Protected Member Functions
void	reset ()
void	resetStab ()
double	sample (bool greater)

Protected Attributes
double	m_bestError
size_t	m_nCurrentDim
size_t	m_nDepth
size_t	m_nDimensions
unsigned int	m_nMask [4]
size_t	m_nStabDepth
size_t	m_nStabs
double *	m_pBestYet
double *	m_pMaxs
double *	m_pMins
double *	m_pVector
GRand	m_rand
size_t	m_samples
Protected Attributes inherited from GClasses::GOptimizer
GTargetFunction *	m_pCritic

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 ( )

inlinevirtual

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

double GClasses::GProbeSearch::m_bestError

protected

size_t GClasses::GProbeSearch::m_nCurrentDim

protected

size_t GClasses::GProbeSearch::m_nDepth

protected

size_t GClasses::GProbeSearch::m_nDimensions

protected

unsigned int GClasses::GProbeSearch::m_nMask[4]

protected

size_t GClasses::GProbeSearch::m_nStabDepth

protected

size_t GClasses::GProbeSearch::m_nStabs

protected

double* GClasses::GProbeSearch::m_pBestYet

protected

double* GClasses::GProbeSearch::m_pMaxs

protected

double* GClasses::GProbeSearch::m_pMins

protected

double* GClasses::GProbeSearch::m_pVector

protected

GRand GClasses::GProbeSearch::m_rand

protected

size_t GClasses::GProbeSearch::m_samples

protected