pydcop.algorithms.adsa

A-DSA : Asynchronous Distributed Stochastic Algorithm

ADSA [FM03] is an asynchronous version of DSA, the Distributed Stochastic Algorithm [ZWXW05] ( stochastic, local search DCOP algorithm.) Instead of waiting for its neighbors, each variables periodically determines if it should select a new values, based on the values received from its neighbors.

Algorithm Parameters

variant: ‘A’, ‘B’ or ‘C’ ; the variant of the algorithm, as defined in [ZWXW05] . Defaults to B.
probability: probability of changing a value. Defaults to 0.7.
period: The period between variables’ activations, in seconds. Defaults to 0.5.

Example

pydcop -t 10 solve --algo adsa \
  --algo_param variant:B  \
  --algo_param probability:0.5 \
  --algo_param period:0.2
  graph_coloring_50.yaml

See also

DSA-tuto: for a very simple implementation of DSA, made for tutorials.

DSA: for a synchronous implementation of DSA.

class ADsaComputation(comp_def)

exists_violated_constraint() → bool: Tells if there is a violated soft constraint regarding the current assignment :return: a boolean

find_best_values(assignment: Dict[Any, float]) → Tuple[List[Any], float]

Find the best values for our variable, given the current assignment.

Find the values from the domain of our variable that yield the best cost (min or max depending of mode) given the assignment known for our neighbors.

Parameters:

assignment – The current assignment

Returns:

List[Any] – A list of values from the domain of our variable
float – The cost achieved with these values.

on_pause(paused: bool)

Called when pausing or resuming the computation.

This method is meant to be overwritten in subclasses.

Parameters:: paused (boolean) – the new pause status. This method is only called is the status has changed

on_start()

Called when starting the computation.

This method is meant to be overwritten in subclasses.

on_stop()

Called when stopping the computation

This method is meant to be overwritten in subclasses.

probabilistic_change(best_cost, best_values): Select a new value if we randomly reach the probability threshold.

variant_a(delta, best_cost, best_values): DSA-A value change : only if gain is strictly positive.

variant_b(delta, best_cost, best_values): DSA-B value change : only if gain is positive or == 0 but some constraints are still violated (i.e. not at their optimal value).

variant_c(delta, best_cost, best_values): DSA-B value change : if gain is <= 0.

build_computation(comp_def: ComputationDef) → DcopComputation

Build a DSA computation

Parameters:: comp_def (a ComputationDef object) – the definition of the DSA computation
Returns:: a message passing computation that implements the DSA algorithm for one variable.
Return type:: MessagePassingComputation