paal::local_search Namespace Reference

Local Search namespace. More...

Namespaces
	concepts
	Concepts of Local Search namespace.
	detail
	Detail of Local Search namespace.

Classes
class	Swap
	Swap. More...
struct	make_swap
	Functor creating Move. More...
class	gain_two_opt
	gain for two opt moves More...
struct	two_local_search_commit
	Commit class for local_search. More...
class	two_local_searchget_moves
	Commit class for local_search. More...
class	two_local_search_adapter
	adapts cycle to have begin and end pointing to edge collection More...
struct	conditional_gain_adaptor
	if the condition is not fulfilled this gain adaptor returns 0 More...
class	gain_cut_small_improves
	This is the gain adapter which accepts gains improving the current solution by more than epsilon. This adapter should be used only when ChooseFirstBetter strategy is applied. More...
class	stop_condition_count_limit
	This is custom StopCondition , it returns true after given count limit. More...
class	stop_condition_time_limit
	This is custom StopCondition, it returns true after given time limit. More...
struct	compute_gain_wrapper
	This wrapper counts sum of the improvements. It makes sense to use it only when ChooseFirstBetter strategy is applied. More...
struct	tabu_gain_adaptor
	Adapts gain to implement tabu search. More...
struct	record_solution_commit_adapter
	This is adaptor on Commit which allows to record solution basing on condition It is particularly useful in tabu search and simulated annealing in which we'd like to store the best found solution. More...
struct	facility_location_commit_add
	commit functor for add moves in facility location problem More...
struct	facility_locationget_moves_add
	gain functor for add moves in facility location problem More...
struct	facility_location_gain_add
	gain functor for add moves in facility location problem More...
struct	facility_location_gain_remove
	gain functor for facility location More...
struct	facility_location_commit_remove
	commit functor for facility location More...
struct	facility_locationget_moves_remove
	get moves functor for facility location remove More...
class	facility_location_solution_adapter
	facility_location_solution adapter chosen range and unchosen range must be joined into one homogenus collection of Facilities. More...
struct	facility_location_gain_swap
	gain functor for swap in facility location problem. More...
struct	facility_location_commit_swap
	commit functor for facility location problem More...
struct	facility_locationget_moves_swap
	get moves functor for facility location problem More...
struct	find_positive_predicate
	this predicates returns true if there is a move with positive gain and the commit was successful More...
struct	first_improving_strategy
	This strategy uses find_positive_predicate as stop condition. More...
struct	max_functor
	functor used in fold in order to find the most improving move. More...
struct	best_improving_strategy
	This strategy chooses the best possible move and if it is improving applies it to the solution. More...
struct	best_strategy
	This strategy chooses the best possible move and applies it to the solution. Note that this strategy might commit non-improving moves. More...
struct	search_obj_function_components_traits
	traits class for search_componentsObjFun More...
struct	Move
	class describing Move More...
struct	make_move
	Functor creating Move. More...
struct	n_queens_commit
	n_queens_commit functor More...
class	n_queensget_moves
	detail More...
struct	n_queens_gain
	n_queens_gain functor More...
struct	n_queens_solution_adapter
	Adapts vector representing n queen problem to class able to efficiently compute gain of given move. More...
struct	search_components_traits
	Traits class for search_components. More...
class	move_type_from_get_moves
	metafunction returns move type in single_solution case More...
struct	move_type
	metafunction returns move type in single_solution case More...
class	fitness_from_gain_and_get_moves
	metafunction returns Fitness type in single_solution case More...
struct	exponential_cooling_schema_dependant_on_time
	This functors returns potential (temperature) using the following schema. The start potential equals given startTemperature, the end temperature (after given duration) equals given endTemperature. In the beetween potential decreases (increase when startTemperature < endTemperature, which is not typical use case) in exponential manner. More...
struct	exponential_cooling_schema_dependant_on_iteration
	This functors returns potential (temperature) using the following schema. The start potential equals given startTemperature, once per numberOFRoundsWithSameTemperature the temperature is multiplied by given multiplier. More...
struct	simulated_annealing_gain_adaptor
	This adaptor takes Gain functor and adopts it to simulated annealing. For each move, if it has positive gain it is chosen otherwise the move is chosen wit probability e^(movesGain/Temperature). Temperature is given by getTemperature functor. More...
struct	simulated_annealing_commit_adaptor
	This adaptor takes Cammit functor and adopts it to simulated annealing. If the input move has positive gain it is chosen otherwise the move is chosen wit probability e^(movesGain/Temperature). Temperature is given by getTemperature functor. More...

Typedefs
template<typename... Args>
using	TwoLocalcomponents = data_structures::components< Gain, data_structures::NameWithDefault< GetMoves, two_local_searchget_moves >, data_structures::NameWithDefault< Commit, two_local_search_commit >>::type< Args...>
	represents step of 2 local search in multi solution where Solution is Cycle, SolutionElement is pair of vertices and Move type is pair of vertices. See Local Search. There are three ways to provide search components More...
using	default_remove_fl_components = Multisearch_components< facility_locationget_moves_remove, facility_location_gain_remove, facility_location_commit_remove >
using	default_add_fl_components = Multisearch_components< facility_locationget_moves_add, facility_location_gain_add, facility_location_commit_add >
	add components for facility location
using	default_swap_fl_components = Multisearch_components< facility_locationget_moves_swap, facility_location_gain_swap, facility_location_commit_swap >
	Swap components for facility location.
using	default_k_median_components = Multisearch_components< facility_locationget_moves_swap, facility_location_gain_swap, facility_location_commit_swap >
template<typename... Args>
using	n_queens_local_search_components = data_structures::components< data_structures::NameWithDefault< GetMoves, n_queensget_moves >, data_structures::NameWithDefault< Gain, n_queens_gain >, data_structures::NameWithDefault< Commit, n_queens_commit >>::type< Args...>
	NQueen Compoenents. More...
typedef data_structures::components < GetMoves, Gain, Commit >	components
	Definition for the components class for local search usually this class is not directly used, see search_components.
template<typename... Args>
using	search_components = typename components::type< Args...>
	search_components template alias More...
template<typename... Args>
using	Multisearch_components = search_components< Args...>
	Multisearch_components template alias. More...
using	components_obj_fun = data_structures::components< GetMoves, ObjFunction, Commit >
	components for objective function local search. This usually this class is not used. See search_componentsObjFun class.
template<typename... Args>
using	search_components_obj_fun = typename components_obj_fun::type< Args...>
	search_componentsObjFun alias to components. More...
template<typename SearchComponents , typename Solution >
using	fitness_t = typename fitness_from_gain_and_get_moves< typename search_components_traits< SearchComponents >::GainT, typename search_components_traits< SearchComponents >::GetMovesT, Solution >::type
	metafunction returns Fitness type in single_solution case More...

Functions
template<typename Gain , typename GetMoves = two_local_searchget_moves>
auto	make_two_local_search_components (Gain ch, GetMoves gm=GetMoves{})
	make template function for TwoLocalcomponents, just to avoid providing type names in template. More...
template<typename Metric >
auto	get_default_two_local_components (const Metric &m)
	get default two local search components More...
template<typename SearchStrategy , typename ContinueOnSuccess , typename ContinueOnFail , typename Cycle , typename... components>
bool	two_local_search (Cycle &cycle, SearchStrategy searchStrategy, ContinueOnSuccess on_success, ContinueOnFail on_fail, components...comps)
	local search for two - opt in tsp adapts tsp to local_search_multi_solution More...
template<typename Cycle , typename... components>
bool	tsp_first_improving (Cycle &cycle, components...comps)
	simple version of two_local_search More...
template<typename Gain = utils::return_one_functor, typename Condition = utils::always_true>
conditional_gain_adaptor< Gain, Condition >	make_conditional_gain_adaptor (Gain gain=Gain(), Condition cond=Condition())
	make for conditional_gain_adaptor More...
template<typename TabuList , typename Gain = utils::always_true, typename AspirationCriteria = utils::always_true>
tabu_gain_adaptor< TabuList, Gain, AspirationCriteria >	make_tabu_gain_adaptor (TabuList tabuList, Gain gain=Gain(), AspirationCriteria aspirationCriteria=AspirationCriteria())
	make function for tabu_gain_adaptor More...
template<typename Commit , typename Solution , typename Condition >
record_solution_commit_adapter < Commit, Solution, Condition >	make_record_solution_commit_adapter (Solution &s, Commit commit, Condition c)
	make function for record_solution_commit_adapter More...
template<typename SearchStrategy , typename ContinueOnSuccess , typename ContinueOnFail , typename facility_location_solution , typename... components>
bool	facility_location_local_search (facility_location_solution &fls, SearchStrategy searchStrategy, ContinueOnSuccess on_success, ContinueOnFail on_fail, components...comps)
	this is model of LocalSearchStepMultiSolution concept. See Local Search. The Move is facility_location::Move. The Solution is adapted data_structures::facility_location_solution. The SolutionElement is facility_location::Facility Use DefaultFLcomponents for default search components. More...
template<typename facility_location_solution , typename... components>
bool	facility_location_first_improving (facility_location_solution &fls, components...comps)
	simple version of local search for facility location More...
template<typename SearchStrategy , typename ContinueOnSuccess , typename ContinueOnFail , typename Solution , typename... components>
bool	local_search (Solution &solution, SearchStrategy searchStrategy, ContinueOnSuccess succ, ContinueOnFail fail, components...comps)
	detail More...
template<typename Solution , typename... components>
bool	first_improving (Solution &solution, components...comps)
template<typename Solution , typename... components>
bool	best_improving (Solution &solution, components...comps)
	This local search chooses the best possible move and if the move is improving applies it to the solution. More...
template<typename Solution , typename ContinueOnSuccess , typename... components>
bool	best (Solution &solution, ContinueOnSuccess on_success, components...comps)
	This local search chooses the best possible move and applies it to the solution. Note that this strategy might commit non-improving moves. More...
template<typename SearchStrategy , typename ContinueOnSuccess , typename ContinueOnFail , typename Solution , typename SearchObjFunctionComponent , typename... SearchObjFunctionComponents>
bool	local_search_obj_fun (Solution &solution, SearchStrategy searchStrategy, ContinueOnSuccess on_success, ContinueOnFail on_fail, SearchObjFunctionComponent component, SearchObjFunctionComponents...components)
	local search function for objective function case.
template<typename Solution , typename... Components>
bool	obj_fun_first_improving (Solution &solution, Components...comps)
	simple version of local_search_obj_fun - first improving strategy
template<typename Solution , typename... Components>
bool	obj_fun_best_improving (Solution &solution, Components...comps)
	simple version of local_search_obj_fun - best improving strategy
template<typename SearchStrategy , typename ContinueOnSuccess , typename ContinueOnFail , typename NQueensPositionsVector , typename... components>
bool	n_queens_solution_local_search (NQueensPositionsVector &pos, SearchStrategy searchStrategy, ContinueOnSuccess on_success, ContinueOnFail on_fail, components...nQueenscomponents)
	n queen local search More...
template<typename NQueensPositionsVector , typename... components>
void	n_queens_solution_first_improving (NQueensPositionsVector &pos, components...nQueenscomponents)
	n queen local search (simple version) More...
template<typename... Args>
auto	make_search_components (Args &&...args)
	make function for search components More...
template<typename... Args>
auto	make_search_components_obj_fun (Args &&...args)
	make function for search_componentsObjFun More...
template<typename Clock = std::chrono::system_clock, typename Duration >
auto	make_exponential_cooling_schema_dependant_on_time (Duration duration, double startTemperature, double endTemperature)
	make function for exponential_cooling_schema_dependant_on_time More...
template<typename Solution , typename ProbabilisticGain , typename GetMoves , typename SetTemperature >
double	start_temperature (Solution &solution, ProbabilisticGain gain, GetMoves get_moves, SetTemperature set_temperature, double acceptance_rate=0.4, int repeats_number=1e3, double epsilon=1e-4)
	This function takes gain functor which is assumed to be probabilistic and dependent on one nonnegative double called temperature. It calculates starting temperature for Simmulated Annealing. Using binary search it looks for temperature that percent of accepted moves is as close to acceptance_rate as possible. This function manipulates temperature using SetTemperature. The gain is assumed to be monotonic in temperature. The 0 temperature means no bad moves are accepted. More...
template<typename Gain , typename GetTemperature , typename random_generator = std::default_random_engine>
auto	make_simulated_annealing_gain_adaptor (Gain gain, GetTemperature getTemperature, random_generator rand=random_generator())
	make function for simulated_annealing_gain_adaptor More...
template<typename Commit , typename Gain , typename GetTemperature , typename random_generator = std::default_random_engine>
auto	make_simulated_annealing_commit_adaptor (Commit commit, Gain gain, GetTemperature getTemperature, random_generator rand=random_generator{})
	make for simulated_annealing_commit_adaptor More...

Detailed Description

Local Search namespace.

Typedef Documentation

template<typename SearchComponents , typename Solution >

using paal::local_search::fitness_t = typedef typename fitness_from_gain_and_get_moves< typename search_components_traits<SearchComponents>::GainT, typename search_components_traits<SearchComponents>::GetMovesT, Solution>::type

metafunction returns Fitness type in single_solution case

Template Parameters

search_components
Solution

Definition at line 90 of file search_traits.hpp.

template<typename... Args>

using paal::local_search::Multisearch_components = typedef search_components<Args...>

Multisearch_components template alias.

Template Parameters

Args

Definition at line 57 of file search_components.hpp.

template<typename... Args>

using paal::local_search::n_queens_local_search_components = typedef data_structures::components< data_structures::NameWithDefault<GetMoves, n_queensget_moves>, data_structures::NameWithDefault<Gain, n_queens_gain>, data_structures::NameWithDefault<Commit, n_queens_commit>>::type<Args...>

NQueen Compoenents.

Template Parameters

Args

Definition at line 37 of file n_queens_local_search.hpp.

template<typename... Args>

using paal::local_search::search_components = typedef typename components::type<Args...>

search_components template alias

Template Parameters

Args

Definition at line 49 of file search_components.hpp.

template<typename... Args>

using paal::local_search::search_components_obj_fun = typedef typename components_obj_fun::type<Args...>

search_componentsObjFun alias to components.

Template Parameters

Args

Definition at line 51 of file search_obj_func_components.hpp.

template<typename... Args>

using paal::local_search::TwoLocalcomponents = typedef data_structures::components< Gain, data_structures::NameWithDefault<GetMoves, two_local_searchget_moves>, data_structures::NameWithDefault<Commit, two_local_search_commit>>::type< Args...>

represents step of 2 local search in multi solution where Solution is Cycle, SolutionElement is pair of vertices and Move type is pair of vertices. See Local Search. There are three ways to provide search components

• use (TODO link does not generate) get_default_two_local_components(const Metric &) - this is the easiest way.
• use TwoLocalcomponents to provide your own search components
• write your own implementation of Multisearch_components

Basic usage of this algorithm is extremely simple and elegant.
We are using some helper functions from the library.

#include "test/test_utils/sample_graph.hpp"

#include "paal/local_search/2_local_search/2_local_search.hpp"
#include "paal/data_structures/cycle/cycle_algo.hpp"
#include "paal/data_structures/cycle/simple_cycle.hpp"

#include <vector>
#include <iostream>

using namespace paal::local_search;
using namespace paal;

int main() {
    // sample data
    typedef sample_graphs_metrics SGM;
    auto gm = SGM::get_graph_metric_small();
    const int size = gm.size();
    std::cout << size << std::endl;
    std::vector<int> v(size);
    std::iota(v.begin(), v.end(), 0);

    // create random solution
    std::random_shuffle(v.begin(), v.end());
    typedef data_structures::simple_cycle<int> Cycle;
    Cycle cycle(v.begin(), v.end());
    std::cout << "Length \t" << get_cycle_length(gm, cycle) << std::endl;

    // search
    tsp_first_improving(cycle, get_default_two_local_components(gm));

    // printing
    std::cout << "Length \t" << get_cycle_length(gm, cycle) << std::endl;

    return 0;
}

Although the basic usage is very simple, the sophisticated user can still easily change default parameters and exchange them with his ones.

Template Parameters

Cycle	input cycle, hast to be model of the Cycle concept
search_components	this is model Multisearch_components

Definition at line 55 of file 2_local_search.hpp.

Function Documentation

template<typename Solution , typename ContinueOnSuccess , typename... components>

bool paal::local_search::best	(	Solution &	solution,
		ContinueOnSuccess	on_success,
		components...	comps
	)

This local search chooses the best possible move and applies it to the solution. Note that this strategy might commit non-improving moves.

Template Parameters

Solution
ContinueOnSuccess
components

Parameters

solution
on_success
comps

Returns

Definition at line 302 of file local_search.hpp.

template<typename Solution , typename... components>

bool paal::local_search::best_improving	(	Solution &	solution,
		components...	comps
	)

This local search chooses the best possible move and if the move is improving applies it to the solution.

Template Parameters

Solution
components

Parameters

solution
comps

Returns

Definition at line 281 of file local_search.hpp.

template<typename facility_location_solution , typename... components>

bool paal::local_search::facility_location_first_improving	(	facility_location_solution &	fls,
		components...	comps
	)

simple version of local search for facility location

Template Parameters

facility_location_solution
components

Parameters

fls
comps

Returns

Definition at line 107 of file facility_location.hpp.

template<typename SearchStrategy , typename ContinueOnSuccess , typename ContinueOnFail , typename facility_location_solution , typename... components>

bool paal::local_search::facility_location_local_search	(	facility_location_solution &	fls,
		SearchStrategy	searchStrategy,
		ContinueOnSuccess	on_success,
		ContinueOnFail	on_fail,
		components...	comps
	)

this is model of LocalSearchStepMultiSolution concept. See Local Search.
The Move is facility_location::Move.
The Solution is adapted data_structures::facility_location_solution.
The SolutionElement is facility_location::Facility
Use DefaultFLcomponents for default search components.

facility_location_local_search The FacilityLocationLocalSearchStep takes as constructor parameter data_structures::facility_location_solution. WARNING get_solution of the FacilityLocationLocalSearchStep returns type object_with_copy<facility_location_solution>. If you want to perform search, then change the solution object and continue local search you should perform all the operations on object_with_copy.
example:

#include "test/test_utils/sample_graph.hpp"

#include "paal/local_search/facility_location/facility_location.hpp"
#include "paal/utils/functors.hpp"

#include <boost/range/algorithm/copy.hpp>

#include <iostream>

using namespace paal::local_search;

int main() {


    // sample data
    typedef sample_graphs_metrics SGM;
    auto gm = SGM::get_graph_metric_small();
    std::vector<int> fcosts{ 7, 8 };
    typedef paal::utils::array_to_functor<std::vector<int>> Cost;

    // define voronoi and solution
    typedef paal::data_structures::voronoi<decltype(gm)> VorType;
    typedef paal::data_structures::facility_location_solution<Cost, VorType>
        Sol;
    typedef paal::data_structures::voronoi_traits<VorType> VT;
    typedef VT::GeneratorsSet GSet;
    typedef VT::VerticesSet VSet;
    typedef Sol::UnchosenFacilitiesSet USet;

    // create voronoi and solution
    VorType voronoi(GSet{}, VSet{ SGM::A, SGM::B, SGM::C, SGM::D, SGM::E }, gm);
    Sol sol(std::move(voronoi), USet{ SGM::A, SGM::B },
            paal::utils::make_array_to_functor(fcosts));

    // create facility location local search components
    default_remove_fl_components rem;
    default_add_fl_components add;
    default_swap_fl_components swap;

    // search
    facility_location_first_improving(sol, rem, add, swap);

    // print result
    boost::copy(sol.get_chosen_facilities(), std::ostream_iterator<int>(std::cout, ","));
    std::cout << std::endl;

    return true;
}

example file is facility_location_example.cpp

Template Parameters

voronoi
FacilityCost
Multisearch_components

Definition at line 85 of file facility_location.hpp.

template<typename Solution , typename... components>

bool paal::local_search::first_improving	(	Solution &	solution,
		components...	comps
	)

Parameters

solution	the initial solution which going to be possibly improved by local_search
comps

Returns

true if the solution is improved

Definition at line 263 of file local_search.hpp.

template<typename Metric >

auto paal::local_search::get_default_two_local_components

(

const Metric &

m

)

get default two local search components

Template Parameters

Metric

is model of Metric concept

Parameters

m

metric

Definition at line 80 of file 2_local_search.hpp.

template<typename SearchStrategy , typename ContinueOnSuccess , typename ContinueOnFail , typename Solution , typename... components>

bool paal::local_search::local_search	(	Solution &	solution,
		SearchStrategy	searchStrategy,
		ContinueOnSuccess	succ,
		ContinueOnFail	fail,
		components...	comps
	)

detail

local search simple solution

Parameters

solution	the initial solution which going to be possibly improved by local_search
searchStrategy
succ	post search action
fail	global stop condition
comps

Returns

true if the solution is improved

Definition at line 230 of file local_search.hpp.

template<typename Gain = utils::return_one_functor, typename Condition = utils::always_true>

conditional_gain_adaptor<Gain, Condition> paal::local_search::make_conditional_gain_adaptor	(	Gain	gain = Gain(),
		Condition	cond = Condition()
	)

make for conditional_gain_adaptor

Template Parameters

Gain
Condition

Parameters

gain
cond

Returns

Definition at line 81 of file custom_components.hpp.

template<typename Clock = std::chrono::system_clock, typename Duration >

auto paal::local_search::make_exponential_cooling_schema_dependant_on_time	(	Duration	duration,
		double	startTemperature,
		double	endTemperature
	)

make function for exponential_cooling_schema_dependant_on_time

Template Parameters

Clock
Duration

Parameters

duration
startTemperature
endTemperature

Returns

Definition at line 94 of file simulated_annealing.hpp.

template<typename Commit , typename Solution , typename Condition >

record_solution_commit_adapter<Commit, Solution, Condition> paal::local_search::make_record_solution_commit_adapter	(	Solution &	s,
		Commit	commit,
		Condition	c
	)

make function for record_solution_commit_adapter

Template Parameters

Commit
Solution
Condition

Parameters

s
commit
c

Returns

Definition at line 402 of file custom_components.hpp.

template<typename... Args>

auto paal::local_search::make_search_components

(

Args &&...

args

)

make function for search components

Template Parameters

Args

Returns

search_components or Multisearch_components

Definition at line 67 of file search_components.hpp.

template<typename... Args>

auto paal::local_search::make_search_components_obj_fun

(

Args &&...

args

)

make function for search_componentsObjFun

Template Parameters

Args

Parameters

args

Returns

Definition at line 62 of file search_obj_func_components.hpp.

template<typename Commit , typename Gain , typename GetTemperature , typename random_generator = std::default_random_engine>

auto paal::local_search::make_simulated_annealing_commit_adaptor	(	Commit	commit,
		Gain	gain,
		GetTemperature	getTemperature,
		random_generator	rand = random_generator{}
	)

make for simulated_annealing_commit_adaptor

Template Parameters

Commit
Gain
GetTemperature
random_generator

Definition at line 457 of file simulated_annealing.hpp.

template<typename Gain , typename GetTemperature , typename random_generator = std::default_random_engine>

auto paal::local_search::make_simulated_annealing_gain_adaptor	(	Gain	gain,
		GetTemperature	getTemperature,
		random_generator	rand = random_generator()
	)

make function for simulated_annealing_gain_adaptor

Template Parameters

Gain
GetTemperature
random_generator

Parameters

gain
getTemperature
rand

Returns

Definition at line 391 of file simulated_annealing.hpp.

template<typename TabuList , typename Gain = utils::always_true, typename AspirationCriteria = utils::always_true>

tabu_gain_adaptor<TabuList, Gain, AspirationCriteria> paal::local_search::make_tabu_gain_adaptor	(	TabuList	tabuList,
		Gain	gain = Gain(),
		AspirationCriteria	aspirationCriteria = AspirationCriteria()
	)

make function for tabu_gain_adaptor

Template Parameters

TabuList
Gain
AspirationCriteria

Parameters

tabuList
gain
aspirationCriteria

Returns

Definition at line 321 of file custom_components.hpp.

template<typename Gain , typename GetMoves = two_local_searchget_moves>

auto paal::local_search::make_two_local_search_components	(	Gain	ch,
		GetMoves	gm = GetMoves{}
	)

make template function for TwoLocalcomponents, just to avoid providing type names in template.

Template Parameters

Gain
GetMoves

Parameters

ch
gm

Returns

Definition at line 69 of file 2_local_search.hpp.

template<typename NQueensPositionsVector , typename... components>

void paal::local_search::n_queens_solution_first_improving	(	NQueensPositionsVector &	pos,
		components...	nQueenscomponents
	)

n queen local search (simple version)

Template Parameters

NQueensPositionsVector
components

Parameters

pos
nQueenscomponents

Definition at line 78 of file n_queens_local_search.hpp.

template<typename SearchStrategy , typename ContinueOnSuccess , typename ContinueOnFail , typename NQueensPositionsVector , typename... components>

bool paal::local_search::n_queens_solution_local_search	(	NQueensPositionsVector &	pos,
		SearchStrategy	searchStrategy,
		ContinueOnSuccess	on_success,
		ContinueOnFail	on_fail,
		components...	nQueenscomponents
	)

n queen local search

Template Parameters

SearchStrategy
ContinueOnSuccess
ContinueOnFail
NQueensPositionsVector
components

Parameters

pos
searchStrategy
on_success
on_fail
nQueenscomponents

Returns

Definition at line 58 of file n_queens_local_search.hpp.

template<typename Solution , typename ProbabilisticGain , typename GetMoves , typename SetTemperature >

double paal::local_search::start_temperature	(	Solution &	solution,
		ProbabilisticGain	gain,
		GetMoves	get_moves,
		SetTemperature	set_temperature,
		double	acceptance_rate = 0.4,
		int	repeats_number = 1e3,
		double	epsilon = 1e-4
	)

This function takes gain functor which is assumed to be probabilistic and dependent on one nonnegative double called temperature. It calculates starting temperature for Simmulated Annealing. Using binary search it looks for temperature that percent of accepted moves is as close to acceptance_rate as possible. This function manipulates temperature using SetTemperature. The gain is assumed to be monotonic in temperature. The 0 temperature means no bad moves are accepted.

Template Parameters

Solution
ProbabilisticGain
GetMoves
SetTemperature

Parameters

solution
gain
get_moves
set_temperature	functor, takes temperature, no return
acceptance_rate	acceptance rate to achive
repeats_number	denotes number of iterations needed to compute success rate for given temperature
epsilon	used to compare doubles.

Returns

Definition at line 171 of file simulated_annealing.hpp.

template<typename Cycle , typename... components>

bool paal::local_search::tsp_first_improving	(	Cycle &	cycle,
		components...	comps
	)

simple version of two_local_search

Template Parameters

Cycle
components

Parameters

cycle
comps

Returns

Definition at line 126 of file 2_local_search.hpp.

template<typename SearchStrategy , typename ContinueOnSuccess , typename ContinueOnFail , typename Cycle , typename... components>

bool paal::local_search::two_local_search	(	Cycle &	cycle,
		SearchStrategy	searchStrategy,
		ContinueOnSuccess	on_success,
		ContinueOnFail	on_fail,
		components...	comps
	)

local search for two - opt in tsp adapts tsp to local_search_multi_solution

Template Parameters

SearchStrategy
ContinueOnSuccess
ContinueOnFail
Cycle
components

Parameters

cycle
searchStrategy
on_success
on_fail
comps

Returns

Definition at line 103 of file 2_local_search.hpp.