Nested grid search. More...

#include <shark/Algorithms/DirectSearch/GridSearch.h>

Inheritance diagram for shark::NestedGridSearch:

Public Member Functions
	NestedGridSearch ()
	Constructor.

std::string	name () const
	From INameable: return the class name.

void	configure (const std::vector< double > &min, const std::vector< double > &max)
	Initialization of the nested grid search.

void	configure (size_t parameters, double min, double max)
	Initialization of the nested grid search.

virtual void	read (InArchive &archive)
	Read the component from the supplied archive.

virtual void	write (OutArchive &archive) const
	Write the component to the supplied archive.

virtual void	init (ObjectiveFunctionType const &objectiveFunction, SearchPointType const &startingPoint)
	if NestedGridSearch was not configured before this call, it is default initialized ti the range[-1,1] for every parameter

void	step (ObjectiveFunctionType const &objectiveFunction)

Public Member Functions inherited from shark::AbstractSingleObjectiveOptimizer< RealVector >
std::size_t	numInitPoints () const
	By default most single objective optimizers only require a single point.

virtual void	init (ObjectiveFunctionType const &function, std::vector< SearchPointType > const &initPoints)
	Initialize the optimizer for the supplied objective function using a set of initialisation points.

virtual const SolutionType &	solution () const
	returns the current solution of the optimizer

Public Member Functions inherited from shark::AbstractOptimizer< PointType, ResultT, SolutionTypeT >
const Features &	features () const

virtual void	updateFeatures ()

bool	requiresValue () const

bool	requiresFirstDerivative () const

bool	requiresSecondDerivative () const

bool	canSolveConstrained () const

bool	requiresClosestFeasible () const

virtual	~AbstractOptimizer ()

virtual void	init (ObjectiveFunctionType const &function)
	Initialize the optimizer for the supplied objective function.

virtual void	init (ObjectiveFunctionType const &function, std::vector< SearchPointType > const &initPoints)=0
	Initialize the optimizer for the supplied objective function using a set of initialisation points.

virtual void	step (ObjectiveFunctionType const &function)=0
	Carry out one step of the optimizer for the supplied objective function.

Public Member Functions inherited from shark::INameable
virtual	~INameable ()

Public Member Functions inherited from shark::ISerializable
virtual	~ISerializable ()
	Virtual d'tor.

void	load (InArchive &archive, unsigned int version)
	Versioned loading of components, calls read(...).

void	save (OutArchive &archive, unsigned int version) const
	Versioned storing of components, calls write(...).

	BOOST_SERIALIZATION_SPLIT_MEMBER ()

Protected Attributes
std::vector< double >	m_minimum
	minimum parameter value to check

std::vector< double >	m_maximum
	maximum parameter value to check

std::vector< double >	m_stepsize
	current step size for every parameter

bool	m_configured

Protected Attributes inherited from shark::AbstractSingleObjectiveOptimizer< RealVector >
SolutionType	m_best
	Current solution of the optimizer.

Protected Attributes inherited from shark::AbstractOptimizer< PointType, ResultT, SolutionTypeT >
Features	m_features

Additional Inherited Members
Public Types inherited from shark::AbstractSingleObjectiveOptimizer< RealVector >
typedef base_type::SearchPointType	SearchPointType

typedef base_type::SolutionType	SolutionType

typedef base_type::ResultType	ResultType

typedef base_type::ObjectiveFunctionType	ObjectiveFunctionType

Public Types inherited from shark::AbstractOptimizer< PointType, ResultT, SolutionTypeT >
enum	Feature { REQUIRES_VALUE = 1 , REQUIRES_FIRST_DERIVATIVE = 2 , REQUIRES_SECOND_DERIVATIVE = 4 , CAN_SOLVE_CONSTRAINED = 8 , REQUIRES_CLOSEST_FEASIBLE = 16 }
	Models features that the optimizer requires from the objective function. More...

typedef PointType	SearchPointType

typedef ResultT	ResultType

typedef SolutionTypeT	SolutionType

typedef AbstractObjectiveFunction< PointType, ResultType >	ObjectiveFunctionType

typedef TypedFlags< Feature >	Features

typedef TypedFeatureNotAvailableException< Feature >	FeatureNotAvailableException

Protected Member Functions inherited from shark::AbstractOptimizer< PointType, ResultT, SolutionTypeT >
void	checkFeatures (ObjectiveFunctionType const &objectiveFunction)
	Convenience function that checks whether the features of the supplied objective function match with the required features of the optimizer.

Detailed Description

Nested grid search.

: The NestedGridSearch class is an iterative optimizer, doing one grid search in every iteration. In every iteration, it halves the grid extent doubling the resolution in every coordinate.

: Although nested grid search is much less exhaustive than standard grid search, it still suffers from exponential time and memory complexity in the number of variables optimized. Therefore, if the number of variables is larger than 2 or 3, consider using the CMA instead.

: Nested grid search works as follows: The optimizer defined a 5x5x...x5 equi-distant grid (depending on the search space dimension) on an initially defined search cube. During every grid search iteration, the error is computed for all grid points. Then the grid is moved to the best grid point found so far and contracted by a factor of two in each dimension. Each call to the optimize() function performs one such step.

: Let N denote the number of parameters to optimize. To compute the error landscape at the current zoom level, the algorithm has to do \( 5^N \) error function evaluations in every iteration.

: The grid is always centered around the best solution currently known. If this solution is located at the boundary, the landscape may exceed the parameter range defined m_minimum and m_maximum. These invalid landscape values are not used.

Definition at line 373 of file GridSearch.h.

Constructor & Destructor Documentation

◆ NestedGridSearch()

shark::NestedGridSearch::NestedGridSearch ( )

inline

Constructor.

Definition at line 377 of file GridSearch.h.

References m_configured.

Member Function Documentation

◆ configure() [1/2]

void shark::NestedGridSearch::configure	(	const std::vector< double > &	min,
		const std::vector< double > &	max
	)

inline

Initialization of the nested grid search.

: The min and max arrays define ranges for every parameter to optimize. These ranges are strict, that is, the algorithm will not try values beyond the range, even if is finds a boundary minimum.

Parameters

min	lower end of the parameter range
max	upper end of the parameter range

Definition at line 398 of file GridSearch.h.

References shark::AbstractSingleObjectiveOptimizer< RealVector >::m_best, m_configured, m_maximum, m_minimum, m_stepsize, and SIZE_CHECK.

Referenced by init().

◆ configure() [2/2]

void shark::NestedGridSearch::configure	(	size_t	parameters,
		double	min,
		double	max
	)

inline

Initialization of the nested grid search.

: The min and max values define ranges for every parameter to optimize. These ranges are strict, that is, the algorithm will not try values beyond the range, even if is finds a boundary minimum.

Parameters

parameters	number of parameters to optimize
min	lower end of the parameter range
max	upper end of the parameter range

Definition at line 427 of file GridSearch.h.

References shark::AbstractSingleObjectiveOptimizer< RealVector >::m_best, m_configured, m_maximum, m_minimum, m_stepsize, and SIZE_CHECK.

◆ init()

virtual void shark::NestedGridSearch::init	(	ObjectiveFunctionType const &	objectiveFunction,
		SearchPointType const &	startingPoint
	)

inlinevirtual

if NestedGridSearch was not configured before this call, it is default initialized ti the range[-1,1] for every parameter

Implements shark::AbstractSingleObjectiveOptimizer< RealVector >.

Definition at line 465 of file GridSearch.h.

References shark::AbstractOptimizer< PointType, ResultT, SolutionTypeT >::checkFeatures(), configure(), m_configured, m_stepsize, and SIZE_CHECK.

◆ name()

std::string shark::NestedGridSearch::name ( ) const

inlinevirtual

From INameable: return the class name.

Reimplemented from shark::INameable.

Definition at line 383 of file GridSearch.h.

◆ read()

virtual void shark::NestedGridSearch::read ( InArchive & archive )

inlinevirtual

Read the component from the supplied archive.

Parameters

[in,out] archive The archive to read from.

Reimplemented from shark::ISerializable.

Definition at line 444 of file GridSearch.h.

References shark::AbstractSingleObjectiveOptimizer< RealVector >::m_best, m_configured, m_maximum, m_minimum, and m_stepsize.

◆ step()

void shark::NestedGridSearch::step ( ObjectiveFunctionType const & objectiveFunction )

inline

Every call of the optimization member computes the error landscape on the current grid. It picks the best error value and zooms into the error landscape by a factor of 2.

Definition at line 480 of file GridSearch.h.

References shark::AbstractSingleObjectiveOptimizer< RealVector >::m_best, m_maximum, m_minimum, m_stepsize, SIZE_CHECK, and step().

Referenced by step().

◆ write()

virtual void shark::NestedGridSearch::write ( OutArchive & archive ) const

inlinevirtual

Write the component to the supplied archive.

Parameters

[in,out] archive The archive to write to.

Reimplemented from shark::ISerializable.

Definition at line 454 of file GridSearch.h.

References shark::AbstractSingleObjectiveOptimizer< RealVector >::m_best, m_configured, m_maximum, m_minimum, and m_stepsize.

Member Data Documentation

◆ m_configured

bool shark::NestedGridSearch::m_configured

protected

Definition at line 544 of file GridSearch.h.

Referenced by configure(), configure(), init(), NestedGridSearch(), read(), and write().

◆ m_maximum

std::vector<double> shark::NestedGridSearch::m_maximum

protected

maximum parameter value to check

Definition at line 539 of file GridSearch.h.

Referenced by configure(), configure(), read(), step(), and write().

◆ m_minimum

std::vector<double> shark::NestedGridSearch::m_minimum

protected

minimum parameter value to check

Definition at line 536 of file GridSearch.h.

Referenced by configure(), configure(), read(), step(), and write().

◆ m_stepsize

std::vector<double> shark::NestedGridSearch::m_stepsize

protected

current step size for every parameter

Definition at line 542 of file GridSearch.h.

Referenced by configure(), configure(), init(), read(), step(), and write().

The documentation for this class was generated from the following file:

include/shark/Algorithms/DirectSearch/GridSearch.h

Public Member Functions

Protected Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ NestedGridSearch()

Member Function Documentation

◆ configure() [1/2]

◆ configure() [2/2]

◆ init()

◆ name()

◆ read()

◆ step()

◆ write()

Member Data Documentation

◆ m_configured

◆ m_maximum

◆ m_minimum

◆ m_stepsize