Local Search

Index:

• Preliminaries - containing preliminaries to Local Search and our interpretation of it.
• LOCAL SEARCH INTERFACE - containing C++ interfaces of Local Search classes.
  • LOCAL SEARCH INTERFACE
  • CUSTOM COMPONENTS

Preliminaries

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.

LOCAL SEARCH INTERFACE

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.

• We can iterate through moves until we find the move with positive gain. This strategy is called ChooseFirstBetter and this is this is the default strategy.
• We can iterate through all moves and chose one with the largest gain. This strategy is called SteepestSlope.

The LOCAL SEARCH INTERFACE section introduces complete interface of the local search.

LOCAL SEARCH INTERFACE

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:

1. GetMoves is a concept class responsible for getting the neighborhood of the current solution

       GetMovesArchetype {
           MoveIteratorsRange operator()(const Solution & s)
       }
       

2. Gain is a concept class responsible for checking if the specific move improve the solution.

       GainArchetype {
           int operator()(const Solution & s, const Move & move);
       }
       

3. Commit is a concept class responsible for updating the solution with the move.

       CommitArchetype {
           int operator()(Solution & s, const Move & move);
       }
       

4. SearchComponents All of the previous concepts are grouped together into one class using Components class with four components: GetMoves, Gain, Commit, StopCondition.

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

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:

1. get_moves functor
2. gain functor
3. commit functor

#include "paal/local_search/local_search.hpp"

#include <vector>
#include <iostream>

namespace ls = paal::local_search;
using namespace paal;

int f(int x) { return -x * x + 12 * x - 27; }

struct get_moves {
    const std::vector<int> neighb;

  public:

    get_moves() : neighb({ 10, -10, 1, -1 }) {}

    const std::vector<int> &operator()(int x) const { return neighb; }
};

struct gain {
    int operator()(int s, int u) { return f(s + u) - f(s); }
};

struct commit {
    bool operator()(int &s, int u) {
        s = s + u;
        return true;
    }
};

typedef ls::search_components<get_moves, gain, commit> search_comps;

After we've defined components we run LS.

    // creating solution
    int solution(0);

    // search
    first_improving(solution, search_comps());

    // print
    std::cout << "Local search solution: " << solution << std::endl;
    return 0;
}

CUSTOM COMPONENTS

The library provides a number of custom components which might be very helpful.

1. paal::local_search::gain_cut_small_improves
2. paal::local_search::stop_condition_time_limit
3. paal::local_search::stop_condition_count_limit
4. paal::local_search::compute_gain_wrapper
5. paal::local_search::record_solution_commit_adapter
6. paal::local_search::tabu_gain_adaptor
7. paal::local_search::simulated_annealing_gain_adaptor

Since library employs the iterators, the following utilities might be helpful

1. boost::transform_iterator
2. boost::filter_iterator
3. boost::function_input_iterator
4. paal::iterator_with_stop_condition
5. paal::data_structures::combine_iterator
6. paal::data_structures::subsets_iterator