pydcop.algorithms.dba¶
DBA : Distributed Breakout Algorithm¶
The Distributed Breakout algorithm [YH96] is a local-search algorithm, built as a a distributed version of the Breakout algorithm for CSP [Mor93]. It is meant to solve distributed constraints satisfaction problems (and not optimization problems).
See also [WZ03] on using DBA for optimization problems.
Algorithm Parameters¶
Our DBA implementation supports two parameters:
infinity: the value used as ‘infinity’, returned as the cost of a violated constraint (it must map the value used in your dcop definition). Defaults to 10 000
max_distance : an upper bound for the maximum distance between two agents in the graph. Ideally you would use the graph diameter or simply the number of variables in the problem. It is used for termination detection (which in DBA only works is there is a solution to the problem). Defaults to 50
Example
pydcop -t 2 solve -a dba -p infinity:10000 max_distance:3 -d adhoc graph_coloring_csp.yaml
{
"assignment": {
"v1": "G",
"v2": "R",
"v3": "G"
},
"cost": 0,
"duration": 1.9932785034179688,
"status": "TIMEOUT"
}
Messages¶
-
class
DbaOkMessage
(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
-
property
-
class
DbaImproveMessage
(improve, current_eval, termination_counter)¶ -
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
-
property
-
class
DbaEndMessage
¶ -
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
-
property
Computation¶
-
class
DbaComputation
(variable: pydcop.dcop.objects.Variable, constraints: Iterable[pydcop.dcop.relations.RelationProtocol], msg_sender=None, mode='min', infinity=10000, max_distance=50, comp_def=None)¶ DBAComputation implements DBA.
See. the following article for a description of original DBA: ‘Distributed Breakout Algorithm for Solving Distributed Constraint Satisfaction Problems’ (Makoto Yokoo, Katsutoshi Hirayama, 1996)
-
compute_eval_value
(val, relations)¶ This function compute the evaluation value (the number of violated constraints) regarding the current assignment.
- Parameters
val (Any) – A value for the variable of this object. You can choose any of the definition domain, according to the context in which you use the function.
relations (list of constraints objects) – The list of constraints involving the variable of this computation, with the values of other variables set to the values sent by the neighbors
- Returns
The evaluation value for the given assignment and the list
of indices of the violated constraints for this value
-
property
neighbors
¶ The neighbors of this computation.
Notes
This is just a convenience shorthand to the neighbors of the node in the computation node :
my_dcop_computation.computation_def.node.neighbors
- Returns
a list containing the names of the neighbor computations.
- Return type
list of string
-
on_start
()¶ Called when starting the computation.
This method is meant to be overwritten in subclasses.
-