Index:
Let us consider a maximization problem:
max f(x) over x in X.
A well known heuristic for solving such problems is the local search(LS).
Assume that we have feasible solution x' in X.
The LS algorithm searches the neighborhood N(x') (the set of posible moves) of x' and tries to find between them a better solution x'' with f(x'') > f(x').
If a better solution is found we set x' to x'' and continue.
If a better solution couldn't be found we finish the search with resulting local optimum x*.
This algorithm can be repeated and the best local optimum is presented.
Let us write the pseudocode for this operation:
local_search() { x <- random_solution(X) do { for_each(Move m in Neighborhood(x)) { if(gain(apply m on x) > 0) { x <- apply m on x } } while (success) return x }
Note that we are working with moves (not with the full solution). This idea will be used in the our C++ implementation.
We use this approach because usually moves are much lighter then full solutions.
Our local search procedes in steps. One step of the local search consists on checking possible moves and finding a move with positive gain (or the move with the biggest gain in the SteepestSlope strategy). In other words, by the one step of the local search we understand one search through the neighborhood.
In the default variant, we prolong search as long as the last step is producing the move with positive gain. In the more general case one can check some additional stop condition and perform some operations between the local search steps. In order to make it possible we introduce two additional concepts:
class PostSearchActionArchetype { void operator()(Solution &); }
The PostSearchAction functor is invoked after each successful search step.
class GlobalStopConditionArchetype { bool operator()(Solution &); }
The GlobalStopCondition is checked after each successful search step.
As mentioned before there are two possible strategies in step excecution.
The LOCAL SEARCH INTERFACE section introduces complete interface of the local search.
In order to present the local search step interface we first need to introduce several concepts.
Note that Solution is the solution type and Move is the type of single move.
MoveIteratorsRange is assumed to be std::pair of iterators, pointing to the begin and end of the collection of moves.
Concepts:
GetMovesArchetype { MoveIteratorsRange operator()(const Solution & s) }
GainArchetype { int operator()(const Solution & s, const Move & move); }
CommitArchetype { int operator()(Solution & s, const Move & move); }
Now we can introduce the paal::local_search::local_search interface. Note that you can pass arbitrary number of SearchComponents to one local search. If your problem has many different Move types it might be useful to provide SearchComponents for each type of Move.
The simple version of local search:
template <typename SearchStrategy = search_strategies::choose_first_better, typename Solution, typename... Components> bool local_search_simple(Solution & solution, Components... components);
The more sophisticated version of local search:
template <typename SearchStrategy = search_strategies::choose_first_better, typename PostSearchAction, typename GlobalStopCondition, typename Solution, typename... Components> bool local_search( Solution & solution, PostSearchAction psa, GlobalStopCondition gsc, Components... components);
example file: local_search_example.cpp
In this example we are going to maximize function \(-x^2 + 12x -27\) for integer \(x\). In this problem the solution is just an int and move is also a number which denotes the shift on the solution. Hence, a new potential solution is just the old solution plus the move. We start with defining search components, that is:
After we've defined components we run LS.
The library provides a number of custom components which might be very helpful.
Since library employs the iterators, the following utilities might be helpful