Implements Oscillating_Search. More...

#include <search_seq_os.hpp>

Inheritance diagram for FST::Search_OS< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, EVALUATOR >:

Public Types
typedef Search_Sequential< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, EVALUATOR >	parent
	base class alias
typedef parent::parent	grandparent
	the shared Search base (output detail, result tracker)
typedef Search_Ranking_BIF< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >	SearchBIF
	Best Individual Feature ranking search, used to grow/shrink an initial subset to the requested cardinality (see adjust_initial_subset()).
typedef std::shared_ptr< SearchBIF >	PSearchBIF
	shared pointer to a SearchBIF instance
typedef std::shared_ptr< EVALUATOR >	PEvaluator
	shared pointer to the sequential-step evaluator
typedef std::shared_ptr< CRITERION >	PCriterion
	shared pointer to the criterion the search optimizes
typedef std::shared_ptr< SUBSET >	PSubset
	shared pointer to a feature subset
Public Types inherited from FST::Search_Sequential< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, EVALUATOR >
typedef Search< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >	parent
	base class alias
typedef std::shared_ptr< EVALUATOR >	PEvaluator
	shared pointer to the sequential-step evaluator that implements Step()'s candidate generation and selection
typedef std::shared_ptr< CRITERION >	PCriterion
	shared pointer to the criterion the search optimizes
typedef std::shared_ptr< SUBSET >	PSubset
	shared pointer to a feature subset
Public Types inherited from FST::Search< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >
typedef std::shared_ptr< CRITERION >	PCriterion
	shared pointer to the criterion the search optimizes
typedef std::shared_ptr< SUBSET >	PSubset
	shared pointer to a feature subset
typedef std::shared_ptr< Result_Tracker< RETURNTYPE, SUBSET > >	PResultTracker
	shared pointer to the result tracker enabled via enable_result_tracking()
typedef Search_Observer< RETURNTYPE, SUBSET >	OBSERVER
	the observer interface type this search reports through (see Search_Observer)
typedef std::shared_ptr< OBSERVER >	PObserver
	shared pointer to an OBSERVER, as set via set_observer()

Public Member Functions
	Search_OS (const PEvaluator evaluator)
	`evaluator` must be non-null; unlike other sequential searches, initial_subset_enabled() is turned ON by construction since OS always starts from (and if needed adjusts) the supplied subset rather than an empty/full one
virtual bool	search (const DIMTYPE target_d, RETURNTYPE &result, const PSubset sub, const PCriterion crit, std::ostream &os=std::cout) override
	returns found subset + criterion value
void	set_delta (const DIMTYPE delta)
	oscillating cycle depth
DIMTYPE	get_delta () const
	the currently configured oscillating cycle depth (see set_delta())
virtual std::ostream &	print (std::ostream &os) const override
	writes a human-readable identification of the search and its configuration; base default writes nothing
Public Member Functions inherited from FST::Search_Sequential< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, EVALUATOR >
	Search_Sequential (const PEvaluator evaluator)
	`evaluator` must be non-null
bool	Step (const bool forward, RETURNTYPE &result, const PSubset sub, const PCriterion crit, std::ostream &os=std::cout)
	Performs one sequential step: adds (`forward`) or removes (!`forward`) the best g-tuple of features, g being the generalization level.
void	set_generalization_level (const DIMTYPE g)
	optional parameter to enlarge the number of considered candidates (g is the number of features added/removed in one Step)
DIMTYPE	get_generalization_level () const
	the currently configured generalization level (see set_generalization_level())
void	enable_initial_subset ()
	makes search() start from the caller-supplied contents of its `sub` argument instead of the concrete method's default (empty set for FORWARD, full set for BACKWARD)
void	disable_initial_subset ()
	reverts to the default: incoming `sub` contents are ignored by search()
bool	initial_subset_enabled () const
	true if enable_initial_subset() was called (and not since disabled by disable_initial_subset())
Public Member Functions inherited from FST::Search< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >
void	enable_result_tracking (PResultTracker tracker)
	assigns a result tracker to the search process, i.e., enables logging of all evaluated subsets for future reuse (re-evaluation, etc.)
void	disable_result_tracking ()
	detaches any result tracker (result_tracker_active() then returns false)
bool	result_tracker_active () const
	true if a result tracker was assigned via enable_result_tracking() and not since disabled
void	set_output_detail (OutputDetail detail)
	sets the amount of information that is logged to output stream throughout the course of search
OutputDetail	get_output_detail () const
	the currently configured output detail level
bool	output_normal () const
	true unless output detail is SILENT
bool	output_detailed () const
	true only at the DETAILED output level
void	set_observer (PObserver observer)
	redirects search progress reporting away from the default syncout text output to `observer`

Protected Types
enum	SwingPhase { RESTART =0 , DOWN =1 , RETURN_UP =2 , UP =4 , RETURN_DOWN =8 }
	Oscillating-cycle phase for the OS swing state machine driving search_one()'s inline switch. More...

Protected Member Functions
virtual bool	search_one (RETURNTYPE &result, const PSubset sub, const PCriterion crit, std::ostream &os)
	standard OS initialized by sub, target dimensionality sub->get_d()
virtual bool	adjust_initial_subset (const DIMTYPE target_d, const PSubset sub, const PSearchBIF bif, std::ostream &os)
	Brings `sub` to exactly `target_d` features before the oscillation starts: an undersized subset is supplemented with the best-ranked individual features, an oversized one is reduced by removing the worst-ranked ones. A subset that already has `target_d` features is left untouched.
Protected Member Functions inherited from FST::Search< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >
void	report (std::ostream &os, const msgbuf &m) const
	delivers one pre-formatted progress message: to the observer if attached, otherwise as syncout text to os
void	report_solution (std::ostream &os, const RETURNTYPE value, const SUBSET &sub, const msgbuf &m) const
	like report(), for sites announcing a new (sub-)solution; fires on_solution instead

Protected Attributes
DIMTYPE	_delta
	current oscillating cycle depth (max swing extent); see set_delta()
std::unique_ptr< SUBSET >	pivotsub
	the current pivot: the best-known subset for the ongoing search_one() call, around which DOWN/UP swings are performed
std::unique_ptr< SUBSET >	pivot_top
	the subset the last UP swing ended on; when the cycle depth grows, the next UP swing resumes from here instead of repeating the steps already taken (valid only while search_one()'s corresponding avail flag is set)
std::unique_ptr< SUBSET >	pivot_bottom
	the subset the last DOWN swing ended on, used the same way to resume a deeper DOWN swing without repeating steps
std::unique_ptr< SUBSET >	inisub
	target_d==0 only: an untouched copy of the caller's initial subset, re-used as the starting point for every cardinality tried
std::shared_ptr< SUBSET >	tmpsub
	target_d==0 only: the working subset one cardinality is searched in, before it is compared with the best result so far
Protected Attributes inherited from FST::Search_Sequential< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, EVALUATOR >
PEvaluator	_evaluator
	the sequential-step evaluator injected at construction; drives Step()'s candidate generation and best/worst choice
DIMTYPE	_generalization_level
	number of features added/removed together in one Step() call (see set_generalization_level())
bool	_initial_subset_enabled
	by default all concrete search methods ignore the contents of supplied 'PSubset set' and initialize sub according to their definition; if enabled, then (if possible) the search() starts from supplied 'PSubset sub' contents
Protected Attributes inherited from FST::Search< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >
PResultTracker	_tracker
	the assigned result tracker, or null (see enable_result_tracking()/result_tracker_active())
OutputDetail	_detail
	the output detail level set via set_output_detail(); read by output_normal()/output_detailed()
PObserver	_observer
	the attached progress observer, or null (see set_observer(), report(), report_solution())

Private Attributes
bool	track
	whether result tracking is enabled, cached per search() call and read throughout search_one()

Detailed Description

template<class RETURNTYPE, typename DIMTYPE, class SUBSET, class CRITERION, class EVALUATOR>
class FST::Search_OS< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, EVALUATOR >

Implements Oscillating_Search.

\note By default sub is expected to be initialized prior to search() call, i.e., it should contain a valid initial subset of requested size,
      from which the search will start. If this is not the case and sub does not contain target_d features, sub contents are adjusted 
      (sub is enlarged by adding features or shrinked by removing features based on individual 
      feature ranking) before the search actually starts. Setting target_d to 0 leads to repeated search() calls for each possible
      subset size, to eventually select among them the solution with highest criterion value.
      To ensure that any initial contents of sub are completely ignored (and initial subset is composed from scratch based purely
      on individual feature ranking), call disable_initial_subset().

Warning: Search_OS can not be used with Sequential_Step_Hybrid() parametrized _keep_perc==0 (due to initial filtercrit and crit values mix-up)

Member Enumeration Documentation

◆ SwingPhase

template<class RETURNTYPE, typename DIMTYPE, class SUBSET, class CRITERION, class EVALUATOR>

enum FST::Search_OS::SwingPhase

protected

Oscillating-cycle phase for the OS swing state machine driving search_one()'s inline switch.

RESTART = adopt sub as the new pivot (current best) and begin a DOWN swing; DOWN = shrink the pivot by generalization_level features at a time, down to the current cycle depth; RETURN_UP = restore back up to the pivot's cardinality and check whether the DOWN swing improved on the pivot (if so, RESTART; otherwise try UP); UP = grow the pivot; RETURN_DOWN = restore back down to the pivot's cardinality and check whether the UP swing improved (if so, RESTART; otherwise the cycle depth is increased and DOWN retried). Unlike Search_DOS, improvement is checked only once a swing completes (RETURN_UP/RETURN_DOWN), never after an intermediate Step().

Member Function Documentation

◆ adjust_initial_subset()

template<class RETURNTYPE, typename DIMTYPE, class SUBSET, class CRITERION, class EVALUATOR>

bool FST::Search_OS< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, EVALUATOR >::adjust_initial_subset	(	const DIMTYPE	target_d,
		const PSubset	sub,
		const PSearchBIF	bif,
		std::ostream &	os )

protectedvirtual

Brings sub to exactly target_d features before the oscillation starts: an undersized subset is supplemented with the best-ranked individual features, an oversized one is reduced by removing the worst-ranked ones. A subset that already has target_d features is left untouched.

Parameters

target_d	the cardinality to reach; must be >0 and at most sub->get_n()
sub	the subset to adjust in place
bif	a ranking search whose evaluate_individuals() has already been run on the same criterion and feature space; it supplies the individual-feature order
os	messages are written here at NORMAL output detail or above

Returns: false if bif yields no ranking, or if the adjustment could not reach target_d

◆ print()

template<class RETURNTYPE, typename DIMTYPE, class SUBSET, class CRITERION, class EVALUATOR>

std::ostream & FST::Search_OS< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, EVALUATOR >::print ( std::ostream & os ) const

overridevirtual

writes a human-readable identification of the search and its configuration; base default writes nothing

Reimplemented from FST::Search< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >.

◆ search()

template<class RETURNTYPE, typename DIMTYPE, class SUBSET, class CRITERION, class EVALUATOR>

bool FST::Search_OS< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, EVALUATOR >::search	(	const DIMTYPE	target_d,
		RETURNTYPE &	result,
		const PSubset	sub,
		const PCriterion	crit,
		std::ostream &	os = std::cout )

overridevirtual

returns found subset + criterion value

Implements FST::Search_Sequential< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, EVALUATOR >.

◆ search_one()

template<class RETURNTYPE, typename DIMTYPE, class SUBSET, class CRITERION, class EVALUATOR>

bool FST::Search_OS< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, EVALUATOR >::search_one	(	RETURNTYPE &	result,
		const PSubset	sub,
		const PCriterion	crit,
		std::ostream &	os )

protectedvirtual

standard OS initialized by sub, target dimensionality sub->get_d()

returns found subset + criterion value

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

/Users/psms/dev/devtest1/_src_search/search_seq_os.hpp

Public Types

Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Private Attributes

Detailed Description

Member Enumeration Documentation

◆ SwingPhase

Member Function Documentation

◆ adjust_initial_subset()

◆ print()

◆ search()

◆ search_one()