local_search

local_search#

class SATemperatureSchedule[source]#

Bases: ABC

Describes how temperature changes as the annealing process goes on. The function maps a degree of completion (in the interval from 0 to 1) to a temperature value.

abstract temperature(degree_of_completion: float) → float[source]#: Computes the temperature for a degree of completion in [0, 1] :param degree_of_completion: the degree to which the simulated annealing process has completed in [0, 1] :return: the temperature

probability(degree_of_completion: float, cost_delta: float) → Tuple[float, float][source]#

class SATemperatureScheduleFixed(t)[source]#

Bases: SATemperatureSchedule

A schedule with a constant temperature

temperature(degree_of_completion)[source]#: Computes the temperature for a degree of completion in [0, 1] :param degree_of_completion: the degree to which the simulated annealing process has completed in [0, 1] :return: the temperature

class SATemperatureScheduleExponential(t0, t1, exponent_factor)[source]#

Bases: SATemperatureSchedule

A temperature schedule for simulated annealing where the temperature drops exponentially.

Parameters:

t0 – temperature at the beginning (degree of completion 0)
t1 – temperature at the end (degree of completion 1), which must be smaller than t0 and larger than 0
exponent_factor – factor with which to multiply the exponent (the larger the factor, the faster the temperature drops)

temperature(degree_of_completion)[source]#: Computes the temperature for a degree of completion in [0, 1] :param degree_of_completion: the degree to which the simulated annealing process has completed in [0, 1] :return: the temperature

reverse_sigmoid(degree_of_completion, v0, v1, steepness, mid_degree=0.5)[source]#

class SATemperatureScheduleReverseSigmoid(t0, t1, steepness, mid_degree=0.5)[source]#

Bases: SATemperatureSchedule

A temperature schedule for simulated annealing where the temperature drops in a reverse sigmoid curve (based on the logistic function)

Parameters:

t0 – temperature at the beginning (degree of completion 0)
t1 – temperature at the end (degree of completion 1), which must be smaller than t0 and larger than 0
steepness – Factor which roughly corresponds to the (negative) slope at the inflection point 0.5. For the sigmoid shape to be sufficiently pronounced, a value of at least 5 is recommended (the closer the value is to 1, the more the curve approaches a linear decay).
mid_degree – the degree of completion at which the function shall return the temperature (t0+t1)/2

temperature(degree_of_completion)[source]#: Computes the temperature for a degree of completion in [0, 1] :param degree_of_completion: the degree to which the simulated annealing process has completed in [0, 1] :return: the temperature

class SATemperatureScheduleReverseSigmoidSymmetric(t0, t1, steepness, cost_delta_for_symmetry)[source]#

Bases: SATemperatureScheduleReverseSigmoid

A variant of the logistic schedule with a reverse sigmoid shape, where the probability of acceptance for a given assumed positive cost delta is symmetric. “Symmetric” here means that half the schedule is to be above 0.5 and half of it below 0.5.

Parameters:

t0 – temperature at the beginning (degree of completion 0)
t1 – temperature at the end (degree of completion 1), which must be smaller than t0 and larger than 0
steepness – Factor which roughly corresponds to the (negative) slope at the inflection point 0.5. For the sigmoid shape to be sufficiently pronounced, a value of at least 8 is recommended (the closer the value is to 1, the more the curve approaches a linear decay).
cost_delta_for_symmetry – the (positive) cost delta value which the curve shall be “symmetric”

class SATemperatureSchedulePower(t0, t1, exponent)[source]#

Bases: SATemperatureSchedule

A temperature schedule for simulated annealing where the temperature drops with powers of the degree of completion d, i.e. the temperature drop is proportional to d to the power of e for a given exponent e.

Parameters:

t0 – temperature at the beginning (degree of completion 0)
t1 – temperature at the end (degree of completion 1), which must be smaller than t0 and larger than 0
exponent – the exponent of the power function

temperature(degree_of_completion)[source]#: Computes the temperature for a degree of completion in [0, 1] :param degree_of_completion: the degree to which the simulated annealing process has completed in [0, 1] :return: the temperature

class SAProbabilityFunction(**params_dict)[source]#: Bases: ABC

class SAProbabilityFunctionLinear(p0=1.0, p1=0.0)[source]#

Bases: SAProbabilityFunction

A probability function where probabilities decay linearly

class SAProbabilityFunctionReverseSigmoid(p0=1.0, p1=0.0, steepness=10)[source]#

Bases: SAProbabilityFunction

A probability function where probabilities decay in a reverse sigmoid shape

Parameters:

p0 – the probability at the beginning (degree of completion 0)
p1 – the probability at the end (degree of completion 1)
steepness – the steepness of the sigmoid curve

class SAProbabilityFunctionConstant(p)[source]#

Bases: SAProbabilityFunction

A constant probability function (which returns the same probability for all degrees of completion)

class SAProbabilitySchedule(reference_cost_delta: Optional[float], probability_function: SAProbabilityFunction)[source]#

Bases: SATemperatureSchedule

A temperature schedule where temperatures are derived from a probability schedule that is to apply to a reference cost delta, which is either given or is computed from observed values (the latter resulting in an adaptive schedule). It converts a function that returns probabilities for degrees of completion into a corresponding temperature schedule.

Creates a temperature schedule for a reference cost delta (which can also be computed automatically from observed data) and probability function: The schedule will return temperatures such that for referenceCostDelta, the probability of acceptance of a move at degree of completion d in [0,1] will be probabilityFunction(d).

Parameters:

reference_cost_delta – the (positive) cost delta for which the probability function is to apply; if None, adaptively determine it from the empirical mean
probability_function – a function which maps degrees of completion in [0,1] to probabilities in [0,1]

temperature(degree_of_completion)[source]#: Computes the temperature for a degree of completion in [0, 1] :param degree_of_completion: the degree to which the simulated annealing process has completed in [0, 1] :return: the temperature

probability(degree_of_completion, cost_delta)[source]#

class SACostValue[source]#

Bases: ABC

Representation of an immutable cost value

abstract value()[source]#: Returns the numeric cost value

abstract add(other) → SACostValue[source]#

class SACostValueNumeric(scalar)[source]#

Bases: SACostValue

value()[source]#: Returns the numeric cost value

add(other: SACostValueNumeric) → SACostValueNumeric[source]#

class SAState(r: Random)[source]#

Bases: ABC

Represents the state/variable assignment during a simulated annealing process

abstract compute_cost_value() → SACostValue[source]#: Computes the costs of this state (from scratch)

abstract get_state_representation()[source]#

Returns a compact state representation (for the purpose of archiving a hitherto best result), which can later be applied via applyStateRepresentation.

Returns:: a compact state representation of some sort

abstract apply_state_representation(representation)[source]#

Applies the given state representation (as returned via getStateRepresentation) in order for the optimisation result to be obtained by the user. Note that the function does not necessarily need to change this state to reflect the representation, as its sole purpose is for the optimsation result to be obtainable thereafter (it is not used during the optimisation process as such).

Parameters:: representation – a representation as returned by getStateRepresentation

class SAOperator(state: TSAState)[source]#

Bases: Generic[TSAState]

An operator which, when applied with appropriately chosen parameters, can transform a state into another state during simulated annealing

Parameters:: state – the state to which the operator is applied

apply_cost_change(cost_delta: SACostValue)[source]#

Applies the cost change to the state given at construction

Parameters:: cost_delta – the cost change to apply

abstract apply_state_change(*params)[source]#

Applies the operator to the state, i.e. it makes the changes to the state only (and does not update the associated costs)

Parameters:: params – the parameters with which the operator is to be applied
Returns:

apply(params: Tuple, cost_delta: SACostValue)[source]#

Applies the operator to the state given at construction, changing the state and updating the costs appropriately

Parameters:

params – the parameters with which the operator is to be applied
cost_delta – the cost change that results from the application

Returns:

abstract cost_delta(*params) → SACostValue[source]#

Computes the cost change that would apply when applying this operator with the given parameters

Parameters:: params – an arbitrary list of parameters (specific to the concrete operator)
Returns:

abstract choose_params() → Optional[Tuple[Tuple, Optional[SACostValue]]][source]#

Chooses parameters for the application of the operator (e.g. randomly or greedily).

Returns:: a tuple (params, costValue) or None if no suitable parameters are found, where params is the list of chosen parameters and costValue is either an instance of CostValue or None if the costs have not been computed.

class SAChain(state_factory: Callable[[Random], TSAState], schedule: SATemperatureSchedule, ops_and_weights: Sequence[Tuple[Callable[[TSAState], SAOperator[TSAState]], float]], random_seed, collect_stats=False)[source]#

Bases: Generic[TSAState]

Manages the progression of one state during simulated annealing

log = <Logger sensai.local_search.SAChain (WARNING)>#

step(degree_of_completion)[source]#

log_stats()[source]#

apply_best_state()[source]#: Applies the best state representation found in this chain to the chain’s state

plot_series(series_name)[source]#

Plots one of the logged series

Parameters:: series_name – the name of the series (see getSeries)

get_series(series_name)[source]#

Gets one of the logged series (for collectStats==True)

Parameters:: series_name – name of the series: one of “temperatures”, “probabilities”, “costDeltas”, “bestCostValues”, “costValues

class SimulatedAnnealing(schedule_factory: Callable[[], SATemperatureSchedule], ops_and_weights: Sequence[Tuple[Callable[[TSAState], SAOperator[TSAState]], float]], max_steps: Optional[int] = None, duration: Optional[float] = None, random_seed=42, collect_stats=False)[source]#

Bases: Generic[TSAState]

The simulated annealing algorithm for discrete optimisation (cost minimisation)

Parameters:

schedule_factory – a factory for the creation of the temperature schedule for the annealing process
ops_and_weights – a list of operator factories with associated weights, where weights are to indicate the (non-normalised) probability of choosing the associated operator
max_steps – the number of steps for which to run the optimisation; may be None (if not given, duration must be provided)
duration – the duration, in seconds, for which to run the optimisation; may be None (if not given, maxSteps must be provided)
random_seed – the random seed to use for all random choices
collect_stats – flag indicating whether to collect additional statics which will be logged

log = <Logger sensai.local_search.SimulatedAnnealing (WARNING)>#

optimise(state_factory: Callable[[Random], TSAState]) → TSAState[source]#

Applies the annealing process, starting with a state created via the given factory.

Parameters:: state_factory – the factory with which to create the (initial) state
Returns:: the state with the least-cost representation found during the optimisation applied

get_chain() → Optional[SAChain[TSAState]][source]#: Gets the chain used by the most recently completed application (optimise call) of this object for the case where stats collection was enabled; the chain then contains relevant series and may be used to generate plots. If stats collection was not enabled, returns None.

class ParallelTempering(num_chains, ops_and_weights: Sequence[Tuple[Callable[[TSAState], SAOperator[TSAState]], float]], schedule: Optional[SATemperatureSchedule] = None, probability_function: Optional[SAProbabilityFunction] = None, max_steps: Optional[int] = None, duration: Optional[float] = None, random_seed=42, log_cost_progression=False)[source]#

Bases: Generic[TSAState]

The parallel tempering algorithm for discrete optimisation (cost minimisation)

Creates a parallel tempering optimiser with the given number of chains and operators for each chain. To determine the schedule to use for each chain, either schedule or probabilityFunction must be provided. It is usually more robust to use adaptive schedules and therefore to provide probabilityFunction.

Parameters:

num_chains – the number of parallel chains
ops_and_weights – a list of operators with associated weights (which are to indicate the non-normalised probability of choosing the associated operator)
schedule – the temperature schedule from which numChains temperatures of chains are drawn (using equidistant degrees of completion); if None, must provide probabilityFunction
probability_function – the probability function from which numChains probabilities for adaptive probability schedules, each using a constant probability, are to be drawn; if None, must provide schedule
max_steps – the number of steps for which to run the optimisation; may be None (if not given, duration must be provided)
duration – the duration, in seconds, for which to run the optimisation; may be None (if not given, maxSteps must be provided)
random_seed – the random seed to use for all random choices
log_cost_progression – whether to log cost progression of all chains (such that it can be plotted after the fact via plotCostProgression)

log = <Logger sensai.local_search.ParallelTempering (WARNING)>#

optimise(state_factory: Callable[[Random], SAState]) → SAState[source]#

Applies the optimisation process, starting, in each chain, with a state created via the given factory.

Parameters:: state_factory – the factory with which to create the states for all chains
Returns:: the state with the least-cost representation found during the optimisation (among all parallel chains) applied

plot_cost_progression()[source]#