Search lifecycle
This page contains detailed information about the lifecycle of a search.
A search has a specific status at every point in time: IDLE, INITIALIZING, RUNNING, TERMINATING or DISPOSED. When a search is created it has status IDLE. An idle search may be started by calling start() which will change the status to INITIALIZING. After initialization, the status goes to RUNNING until the search is requested to stop. Calling stop() sets the status to TERMINATING but the search is allowed to finish its current step so that it can gracefully terminate. Subsequently, the search run is complete and the status goes back to IDLE.
An idle search may be restarted and its configuration can be changed between subsequent runs. However, when a search is no longer used, it should be disposed by calling dispose(). A disposed search will release all its resources and can never be restarted. It is important to always call dispose() after the last search run to ensure proper termination of the application, i.e. to prevent that searches are still holding on to vital resources (such as active thread pools).
The sequence diagrams below show how a search is started and subsequently terminated when a stop criterion is satisfied.
When the search is created it has status IDLE and creates its personal stop criterion checker, which holds a reference to the search. Any stop criteria added to the search are passed to this checker, after verifying compatibility. The stop criterion checker will periodically check the stop criteria (by default every second). In addition, a manual check is performend after every completed search step. The latter ensures a fine granularity for searches that perform a large number of steps per time, while the former guarantees that any search will eventually be requested to stop even if it e.g. performs a single step that never terminates internally.
Calling start() starts a search run. First, the status goes to INITIALIZING and the search executes an internal procedure searchStarted() which first calls the public method init() to take care of initialization and/or check the search configuration, after which it (re)sets all per run metadata such as the execution time and step count.
The default implementation of init() is empty but this method can be overridden in a specific search. For example, a local search generates its default random initial solution when calling init().
Note that it is also allowed to manually initialize the search before execution. For example, searches that are composed of multiple subsearches may choose to initialize all subsearches when the main search is initialized.
It should thus be taken into account that init() may be called multiple times prior to execution, for example by performing computationally demanding initializations only once, upon the first call.
After initialization, the search instructs the stop criterion checker to start checking in the background. For this purpose, the checker schedules a task for periodical execution in a separate thread.
Then, the search status changes to RUNNING and a loop is initiated in which searchStep() is iteratively called until continueSearch() returns false because the search was requested to stop. After every step, the search manually checks if any stop criterion is satisfied. If so, the search stops itself. Simultaneously, the stop criterion checker periodically checks the stop criteria. If a stop criterion is satisfied, the checker asks the search to stop by calling stop(). This sets the search status to TERMINATING upon which continueSearch() will return false but lets the search continue until it has finished its current step. Before requesting the search to stop, the checker also cancels further executions of the scheduled task dedicated to checking the stop criteria.
When entering the next iteration of the search loop, the search detects that is was requested to stop and the loop is terminated. Subsequently, searchStopped() is executed internally, which takes care of finalization. Finally, the search status goes back to IDLE and start() returns, as the search run is now complete.
Note that start() does not have a return value. When the search run is complete, the best solution found during search can be obtained with getBestSolution(). The corresponding evaluation can be retrieved using getBestSolutionEvaluation().
An idle search may be restarted. The search state is retained across subsequent runs, including the best solution found so far and the current solution in case of a local search. State elements of specific searches, such as the current neighbourhood in variable neighbourhood search, the tabu memory in tabu search, the already explored part of the search space in exhaustive search, etc. are also retained across runs unless explicitly stated otherwise in a search's documentation.
On the other hand, the following metadata applies to the current run only:
- current runtime
- current number of steps
- time and steps without improvement
- minimum delta
- number of accepted and rejected moves (for neighbourhood searches only)
Therefore, stop criteria relying on this metadata operate on a per-run basis.
When a search is no longer used, it should be disposed by calling dispose() upon which the search releases all its resources. A disposed search can not be (re)started. Not disposing a search may prevent termination of the application.
The first sequence diagram shows a scenario in which the search is terminated by its stop criterion checker, when a periodical check observes that a stop criterion is satisfied.
The second diagram visualizes the other scenario in which the search itself detects that a stop criterion is satisfied after completing a search step (manual check).
It is possible that a search comes to its natural end instead of relying on stop criteria, for example when an exhaustive search has explored the entire solution space, when no more improvement is found by a steepest descent search, or if all neighbours happen to be tabu in a tabu search.
In such case, the search calls stop() from within searchStep(). The status first goes to TERMINATING and then IDLE after finalization.
The diagram below demonstrates this scenario. The stop criterion checker is again included in the diagram, but now it is never activated since no stop criteria have been assigned. Calling startChecking() simply does not have any effect, i.e. the task dedicated to checking the stop criteria is never scheduled. Also, no stop criteria are to be checked after a completed search step.
When the search has stopped, it informs the checker that it can stop checking. In this particular scenario, this call has no effect since the checker was inactive, but it would have been active if at least one stop criterion were added. Thus, it is important that the search does always terminate the stop criterion checker at the end of a search run.
