pydcop.algorithms.gdba
GDBA Algorithm
See the following article for more details on adaptation mode: Distributed Breakout Algorithm: Beyond Satisfaction’ (S. Okamoto, R. Zivan, A. Nahon, 2016)
Algorithm Parameters
modifier: str, “A” or “M”
How to increase costs dynamically to focus search: “A” (Additive) or “M” (Multiplicative). Default is “A”
violation: str, NZ”, “NM” or “MX”.
How to determine if a constraint is violated, Non-zero cost (NZ), Non-minimum (NM) or Maximum (MX). Default is “NZ”
increase_mode: str. “E”, “R”, “C”, or “T”
Determine which costs have to be increased. Possible values: ‘E’ (single-entry) or ‘C’ (column) or ‘R’ (row) or ‘T’ ( Transversal). default is “E”.
- class GdbaComputation(variable: Variable, constraints: Iterable[RelationProtocol], mode='min', modifier='A', violation='NZ', increase_mode='E', msg_sender=None, comp_def=None)
GdbaComputation implements an extension of DBA to suit DCOPs. Several adaptations are possible. There are 3 dimensions which have several modes, for a total of 24 variants. They are listed below:
EffCost: how to concretely increase the costs of constraints: increase of 1 or costs.
Possible values: ‘A’ (Additive) or ‘M’ (Multiplicative)
- IsViolated: How to define that a constraint is violated.
Possible values: ‘NZ’ (Non-zero cost) or ‘NM’ (Non-minimum) or ‘MX’ (Maximum)
IncreaseMode: Determine which costs have to be increased. Possible values: ‘E’ (single-entry) or ‘C’ (column) or ‘R’ (row) or ‘T’ ( Transversal)
See the following article for more details on those adaptation modes: ‘Distributed Breakout Algorithm: Beyond Satisfaction’ (S. Okamoto, R. Zivan, A. Nahon, 2016)
- compute_eval_value(val)
This function computes the effective cost of the current assignment for the agent’s variable.
- Param:
a value for the variable of this object (it must be a value
from the definition domain).
- Returns:
the evaluation value for the given value 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.
- class GdbaImproveMessage(improve)
- 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
- class GdbaOkMessage(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 main messages in DBA are the ‘ok?’ and ‘improve’ messages, which at most contains a value and a possible improvement. The size of the message does not depends on the source nor target variable, nor on their respective domains.
- 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 DBA computation.
Notes
With DBA, 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