pydcop.algorithms.dsa

DSA : Distributed Stochastic Algorithm

Distributed Stochastic Algorithm [ZWXW05] is a synchronous, stochastic, local search DCOP algorithm.

This is the classical synchronous version of DSA ; at each cycle each variable waits for the value of all its neighbors before computing the potential gain and making a decision. This means that this implementation is not robust to message loss.

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
stop_cycle: The number of cycle after which the algorithm stops, defaults to 0 If not defined (or equal to 0), the computation never stops.

Example

pydcop -t 3 solve -algo dsa  \
  --algo_param stop_cycle:30 \
  --algo_param variant:C \
  --algo_param probability:0.5 \
 -d adhoc graph_coloring_csp.yaml

{
  "assignment": {
    "v1": "G",
    "v2": "R",
    "v3": "G"
  },
  "cost": 0,
  "duration": 1.9972785034179688,
  "status": "TIMEOUT"
}

See also

algo_params

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

on_start()

Called when starting 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.

class DsaMessage(value)

property size

Returns the size of the message.

You should overwrite this methods in subclasses, will be used when computing the communication load of an algorithm and by some distribution methods that optimize the distribution of computation for communication load.

Returns:: size
Return type:: int

communication_load(src: VariableComputationNode, target: str) → float

Return the communication load between two variables.

Notes

The only message in DSA is the ‘value’ messages, which simply contains the current value.

Parameters:

src (VariableComputationNode) – The ComputationNode for the source variable.
target (str) – the name of the other variable src is sending messages to

Returns:

The size of messages sent from the src variable to the target variable.

Return type:

float

computation_memory(computation: VariableComputationNode) → float

Return the memory footprint of a DSA computation.

Notes

With DSA, a computation must only remember the current value for each of it’s neighbors.

Parameters:: computation (VariableComputationNode) – a computation in the hyper-graph computation graph
Returns:: the memory footprint of the computation.
Return type:: float