SolutionType
- solution type of the problems that may be solved using this search,
required to extend Solution
public abstract class Search<SolutionType extends Solution> extends Object implements Runnable
General abstract search used to solve a problem with the specified solution type. It provides general methods to start and stop the search, and to access state information and metadata such as the best solution found so far and the runtime of the current run. It also provides methods to add and remove search listeners and stop criteria.
A search can have five possible statuses: IDLE, INITIALIZING, RUNNING, TERMINATING or DISPOSED
(see SearchStatus
). When a search is created, it is IDLE. Upon calling start()
it first goes to INITIALIZING and then RUNNING, after successful initialization. While the search
is running, it iteratively calls searchStep()
to perform a search step as defined in each
specific search implementation.
Whenever a search is requested to stop, by calling stop()
, it goes to status TERMINATING. A terminating
search will stop after it has completed its current step, and then its status goes back to status IDLE. A search
may also terminate itself by calling stop()
internally, when it has come to its natural end.
In particular, a single step algorithm can be implemented by calling stop()
immediately at the end of
the first and only step, which guarantees that only one single step will be executed.
An idle search may be restarted at any time. The search state is retained across subsequent runs, including the best solution found so far and any search specific state elements, unless explicitely stated otherwise. On the other hand, the following metadata applies to the current run only:
This might also be the case for additional metadata in specific searches, which should be clearly indicated in their documentation. Note that stop criteria relying on such metadata will operate on a per-run basis.
An idle search can also be disposed (see dispose()
), upon which it will release all of its resources.
A disposed search can never be restarted. Note that it is important to always dispose a search after its last
run so that it does not hold on to any of its resources. Not disposing a search may prevent termination of the
application.
Constructor and Description |
---|
Search(Problem<SolutionType> problem)
Creates a search to solve the given problem, with default search name "Search".
|
Search(String name,
Problem<SolutionType> problem)
Creates a search to solve the given problem, with a custom search name.
|
Modifier and Type | Method and Description |
---|---|
void |
addSearchListener(SearchListener<? super SolutionType> listener)
Add a search listener.
|
void |
addStopCriterion(StopCriterion stopCriterion)
Adds a stop criterion used to decide when the search should stop running.
|
protected void |
assertIdle(String errorMessage)
Asserts that the search is currently idle, more precisely that its status is equal to
SearchStatus.IDLE . |
void |
clearSearchListeners()
Remove all search listeners.
|
void |
clearStopCriteria()
Removes all stop criteria.
|
protected double |
computeDelta(Evaluation currentEvaluation,
Evaluation previousEvaluation)
Computes the amount of improvement of
currentEvaluation over previousEvaluation ,
taking into account whether evaluations are being maximized or minimized. |
void |
dispose()
Dispose this search, upon which all of its resources are released.
|
SolutionType |
getBestSolution()
Returns the best solution found so far.
|
Evaluation |
getBestSolutionEvaluation()
Get the evaluation of the best solution found so far.
|
Validation |
getBestSolutionValidation()
Get the validation of the best solution found so far.
|
int |
getID()
Get the unique ID that has been assigned to this search.
|
double |
getMinDelta()
Get the minimum improvement in evaluation of a new best known solution over the previous best known solution,
found during the current (or last) run.
|
String |
getName()
Get the name that has been assigned to this search.
|
Problem<SolutionType> |
getProblem()
Get the problem being solved, as specified at construction.
|
Random |
getRandom()
Get the dedicated random generator used by this search.
|
long |
getRuntime()
Get the runtime of the current (or last) run, in milliseconds.
|
protected List<SearchListener<? super SolutionType>> |
getSearchListeners()
Retrieve search listeners (unmodifiable view).
|
SearchStatus |
getStatus()
Get the current search status.
|
protected Object |
getStatusLock()
Returns a lock to be acquired when executing blocks of code that can not be interrupted by a status update.
|
long |
getSteps()
Get the number of completed steps during the current (or last) run.
|
long |
getStepsWithoutImprovement()
Get the number of consecutive steps completed during the current (or last) run, without finding
any further improvement.
|
long |
getTimeWithoutImprovement()
Get the amount of time elapsed during the current (or last) run, without finding any further improvement
(in milliseconds).
|
void |
init()
Initializes and/or validates the search.
|
boolean |
removeSearchListener(SearchListener<? super SolutionType> listener)
Remove the given search listener.
|
boolean |
removeStopCriterion(StopCriterion stopCriterion)
Removes a stop criterion.
|
void |
run()
Equivalent to calling
start() . |
protected void |
searchDisposed()
This method is called when a search is disposed, immediately before the search status is updated.
|
protected void |
searchStarted()
This method is called when a search run is started.
|
protected abstract void |
searchStep()
This method is iteratively called while the search is running and should be implemented in every specific
search according to the corresponding search strategy.
|
protected void |
searchStopped()
This method is called when a search run has completed.
|
void |
setRandom(Random rnd)
Set custom random generator.
|
void |
setStopCriterionCheckPeriod(long period,
TimeUnit timeUnit)
Instructs the search to check its stop criteria at regular intervals separated by the given period.
|
void |
start()
Starts a search run and returns when this run has finished.
|
void |
stop()
Requests the search to stop.
|
String |
toString()
Returns a string representation of the search, formatted as "%name(%id)".
|
protected boolean |
updateBestSolution(SolutionType newSolution)
Checks whether a new best solution has been found and updates it accordingly.
|
protected boolean |
updateBestSolution(SolutionType newSolution,
Evaluation newSolutionEvaluation,
Validation newSolutionValidation)
Checks whether a new best solution has been found and updates it accordingly,
given that the solution has already been evaluated and validated.
|
public Search(Problem<SolutionType> problem)
problem
- problem to solveNullPointerException
- if problem
is null
public Search(String name, Problem<SolutionType> problem)
name
is null
, a default search name "Search" will
be assigned.problem
- problem to solvename
- custom search nameNullPointerException
- if problem
is null
public Problem<SolutionType> getProblem()
public Random getRandom()
setRandom(Random)
. The search should
pass this source of randomness to all applied randomized components.public void setRandom(Random rnd)
rnd
- new dedicated random generatorpublic String getName()
public int getID()
public String toString()
public void init()
Initializes and/or validates the search.
It is not required to manually initialize a search before it is started since init()
is called from
within searchStarted()
. However, it may also be called prior to starting the search. For example, a
search composed of multiple subsearches may choose to initialize these searches prior to execution.
A SearchException
may be thrown if initialization fails because the search has not been configured
validly. Moreover, any JamesRuntimeException
could be thrown when initialization depends on
malfunctioning components.
When overriding this method, always call super.init()
and take into account that the
method may be called multiple times prior to execution. For example, consider to perform computationally
expensive initializations only once, upon the first call. The default implementation is empty.
SearchException
- if initialization fails, e.g. because the search has not been configured validlyJamesRuntimeException
- in general, any JamesRuntimeException
may be thrown
in case of a malfunctioning component used during initializationpublic void start()
Starts a search run and returns when this run has finished. The search run may either complete internally, i.e.
come to its natural end, or be terminated by a stop criterion (see addStopCriterion(StopCriterion)
).
This method does not return anything; the best solution found during search can be obtained by calling
getBestSolution()
and its corresponding evaluation and validation with
getBestSolutionEvaluation()
and getBestSolutionValidation()
, respectively.
Note that a search can only be (re)started when it is idle (see getStatus()
). When attempting to start
a search which is already running, terminating or disposed, an exception will be thrown.
Before the search is actually started, some initialization may take place. This initialization can also include a verification of the search configuration and in case of an invalid configuration, an exception may be thrown.
SearchException
- if the search is currently not idle, or if initialization fails because of an invalid
search configurationJamesRuntimeException
- in general, any JamesRuntimeException
may be thrown
in case of a malfunctioning component used during initialization,
execution or finalizationpublic void stop()
Requests the search to stop. May be called from outside the search, e.g. by a stop criterion,
as well as internally, when the search comes to its natural end. In the latter case, it is
absolutely guaranteed that the step from which the search was requested to stop will be the
last step executed during the current run. If the current search status is not
SearchStatus.INITIALIZING
or SearchStatus.RUNNING
, calling this method has
no effect. Else, it changes the search status to SearchStatus.TERMINATING
.
In case the search is already requested to terminate during initialization, it will complete initialization, but is guaranteed to stop before executing any search steps.
public void dispose()
SearchStatus.DISPOSED
. When trying to dispose an already disposed search,
nothing happens, i.e. calling this method on a disposed search has no effect.SearchException
- if the search is currently not idle (and not already disposed)public void run()
public void addStopCriterion(StopCriterion stopCriterion)
stopCriterion
- stop criterion used to decide when the search should stop runningIncompatibleStopCriterionException
- if the given stop criterion is incompatible with the searchSearchException
- if the search is not idlepublic boolean removeStopCriterion(StopCriterion stopCriterion)
false
is returned.
Note that this method may only be called when the search is idle.stopCriterion
- stop criterion to be removedtrue
if the stop criterion has been successfully removedSearchException
- if the search is not idlepublic void clearStopCriteria()
SearchException
- if the search is not idlepublic void setStopCriterionCheckPeriod(long period, TimeUnit timeUnit)
StopCriterionChecker
, which is used internally for this purpose.
The period should be at least 1 millisecond, else the stop criterion checker may thrown an exception
when the search is started. Note that this method may only be called when the search is idle.
Regardless of the specified period, the stop criteria are also checked after each search step.
period
- time between subsequent stop criterion checks (> 0)timeUnit
- corresponding time unitSearchException
- if the search is not idleIllegalArgumentException
- if the given period is not strictly positivepublic void addSearchListener(SearchListener<? super SolutionType> listener)
listener
- search listener to add to the searchSearchException
- if the search is not idlepublic boolean removeSearchListener(SearchListener<? super SolutionType> listener)
false
is returned.
Note that this method may only be called when the search is idle.listener
- search listener to be removedtrue
if the listener was present and has now been removedSearchException
- if the search is not idlepublic void clearSearchListeners()
protected List<SearchListener<? super SolutionType>> getSearchListeners()
public SearchStatus getStatus()
protected Object getStatusLock()
protected void assertIdle(String errorMessage)
SearchStatus.IDLE
.
If not, a SearchException
is thrown, which includes the given errorMessage
and the current
search status (different from IDLE).errorMessage
- message to be included in the SearchException
thrown if the search is not idleSearchException
- if the search is not idlepublic SolutionType getBestSolution()
null
if no valid solutions have been evaluated yet, for example
when the search has just been created.null
otherwisepublic Evaluation getBestSolutionEvaluation()
null
if no best solution
has yet been set, for example when the search has just been created.null
otherwisepublic Validation getBestSolutionValidation()
null
if no best solution
has yet been set, for example when the search has just been created.null
otherwiseprotected boolean updateBestSolution(SolutionType newSolution)
Checks whether a new best solution has been found and updates it accordingly. The given solution is evaluated and validated, after which the best solution is updated only if the solution is valid and
If the new solution is invalid or has a worse evaluation than the current best solution, calling this method has no effect. Note that the best solution is retained across subsequent runs of the same search.
newSolution
- newly presented solutiontrue
if the given solution is accepted as the new best solutionprotected boolean updateBestSolution(SolutionType newSolution, Evaluation newSolutionEvaluation, Validation newSolutionValidation)
Checks whether a new best solution has been found and updates it accordingly, given that the solution has already been evaluated and validated. The best solution is updated only if the presented solution is valid and
If the new solution is invalid or has a worse evaluation than the current best solution, calling this method has no effect. Note that the best solution is retained across subsequent runs of the same search.
newSolution
- newly presented solutionnewSolutionEvaluation
- evaluation of given solutionnewSolutionValidation
- validation of given solutiontrue
if the given solution is accepted as the new best solutionpublic long getRuntime()
Get the runtime of the current (or last) run, in milliseconds. The precise return value depends on the status of the search:
JamesConstants.INVALID_TIME_SPAN
is returned.
JamesConstants.INVALID_TIME_SPAN
is returned.
The return value is always positive, except in those cases when
JamesConstants.INVALID_TIME_SPAN
is returned.
public long getSteps()
Get the number of completed steps during the current (or last) run. The precise return value depends on the status of the search:
JamesConstants.INVALID_STEP_COUNT
.
JamesConstants.INVALID_STEP_COUNT
is returned.
The return value is always positive, except in those cases when JamesConstants.INVALID_STEP_COUNT
is returned.
public long getTimeWithoutImprovement()
Get the amount of time elapsed during the current (or last) run, without finding any further improvement (in milliseconds). The precise return value depends on the status of the search:
JamesConstants.INVALID_TIME_SPAN
.
JamesConstants.INVALID_TIME_SPAN
is returned.
The return value is always positive, except in those cases when JamesConstants.INVALID_TIME_SPAN
is returned.
public long getStepsWithoutImprovement()
Get the number of consecutive steps completed during the current (or last) run, without finding any further improvement. The precise return value depends on the status of the search:
JamesConstants.INVALID_STEP_COUNT
.
JamesConstants.INVALID_STEP_COUNT
is returned.
The return value is always positive, except in those cases when JamesConstants.INVALID_STEP_COUNT
is returned.
public double getMinDelta()
Get the minimum improvement in evaluation of a new best known solution over the previous best known solution, found during the current (or last) run. The precise return value depends on the status of the search:
JamesConstants.INVALID_DELTA
is returned. Else, the minimum observed delta over all improvements
made during the current run is returned.
JamesConstants.INVALID_DELTA
.
JamesConstants.INVALID_DELTA
is returned.
The return value is always positive, except in those cases when JamesConstants.INVALID_DELTA
is returned.
It corresponds to increase when solving a maximization problem, and decrease in case of a minimization problem.
protected double computeDelta(Evaluation currentEvaluation, Evaluation previousEvaluation)
currentEvaluation
over previousEvaluation
,
taking into account whether evaluations are being maximized or minimized. Positive deltas indicate improvement.
In case of maximization the amount of increase is returned, which is equal to
currentEvaluation - previousEvaluationwhile the amount of decrease, equal to
previousEvaluation - currentEvaluationis returned in case of minimization.
currentEvaluation
- evaluation to be compared with previous evaluationpreviousEvaluation
- previous evaluationprotected void searchStarted()
This method is called when a search run is started.
It first initializes and validates the search by calling init()
, which may throw a
SearchException
if initialization fails because the search has not been configured validly.
Moreover, any JamesRuntimeException
could be thrown in case initialization depends on
malfunctioning components.
After initialization, all general per run metadata is (re)set, such as the step count and execution time.
Always call super.searchStarted()
when overriding this method.
Note however that it is preferred to override init()
instead.
SearchException
- if initialization fails, e.g. because the search has not been configured validlyJamesRuntimeException
- in general, any JamesRuntimeException
may be thrown
in case of a malfunctioning component used during initializationprotected void searchStopped()
This method is called when a search run has completed. It may be used to perform some finalization. Any
JamesRuntimeException
may be thrown when finalization depends on malfunctioning search components.
The default implementation ensures that the total runtime of the last run, if applicable, will be returned
when calling getRuntime()
on an idle search.
Always call super.searchStopped()
when overriding this method.
JamesRuntimeException
- in general, any JamesRuntimeException
may be thrown
in case of a malfunctioning component used during finalizationprotected void searchDisposed()
This method is called when a search is disposed, immediately before the search status is updated.
The default implementation is empty but should be overridden when a specific search uses resources that have to
be released (e.g. an active thread pool) when the search is no longer used. Any JamesRuntimeException
may
be thrown when trying to release malfunctioning resources.
Always call super.searchDisposed()
when overriding this method.
JamesRuntimeException
- in general, any JamesRuntimeException
may be thrown
when trying to release malfunctioning resourcesprotected abstract void searchStep()
stop()
from within this method, which will cause the search loop to terminate and prevent further
steps to be executed. Searches consisting of a single step may simply implement their strategy here and
immediately call stop()
at the end of the execution of the step, so that it will be executed
exactly once.JamesRuntimeException
- any JamesRuntimeException
may be thrown during a search step, when
the algorithm has been supplied with a malfunctioning componentCopyright © 2016. All rights reserved.