Inheritance diagram for frodo2.algorithms.localSearch.dsa.DSA< Val extends Addable< Val >, U extends Addable >:

[legend]

Classes
class	VariableInfo
	Container class for information needed for each variable. More...
interface	DetermineAssignment
	Interface used to implement the different decision strategies of DSA. More...
class	A
class	C
class	E
class	VarAssignment
	Container for a value assignment and its utility. More...

Public Member Functions
	DSA (Element parameters, DCOPProblemInterface< Val, U > problem)
	Constructor for the stats gatherer mode.
	DSA (DCOPProblemInterface< Val, U > problem, Element parameters) throws ClassNotFoundException
	Constructor.
	DSA (DCOPProblemInterface< Val, U > problem, Element parameters, int nbrCycles)
	Constructor.
void	reset ()
HashMap< String, ArrayList< CurrentAssignment< Val > > >	getAssignmentHistories ()
void	getStatsFromQueue (Queue queue)
Val	getCurrentValue (String variable)
	Getter method.
U	getCurrentUtility (String variable)
	Getter method.
void	setSilent (boolean silent)
Collection< MessageType >	getMsgTypes ()
void	notifyIn (Message msg)
void	setQueue (Queue queue)
Map< String, Val >	getCurrentSolution ()
Public Member Functions inherited from frodo2.communication.IncomingMsgPolicyInterface< T >
default void	notifyIn (Message msg, Object toAgent)
	Notifies the listener of an incoming message.

Static Public Attributes
static MessageType	START_MSG_TYPE = AgentInterface.START_AGENT
	The type of the message telling the module to start.
static MessageType	VALUE_MSG_TYPE = new MessageType ("DSA", "VALUE")
	The type of the message used to report a value to neighboring variables.
static final MessageType	CONV_STATS_MSG_TYPE = new MessageType ("DSA", "ConvStats")
	The type of the message containing the assignment history.

Protected Member Functions
void	setDecisionStrategy (String decisionStrategy)
	Method used to set the decision strategy.
void	init ()
	Initializes the agent's variables.
VariableInfo< Val, U >	createVariableInfo (String variableID, Val[] domain, String[] neighbours, DCOPProblemInterface< Val, U > problem)
	method used to create a VariableInfo object
void	log (String variableID, String message)
	Log function used to print the variables state during debugging.

Protected Attributes
final boolean	LOG = false
	When `true`, every variable writes log information to a log file.
HashMap< String, BufferedWriter >	loggers
	A list of buffered writers used to log information during debugging.
final boolean	convergence
	Whether the listener should record the assignment history or not.
HashMap< String, ArrayList< CurrentAssignment< Val > > >	assignmentHistoriesMap
	For each variable its assignment history.
DCOPProblemInterface< Val, U >	problem
	The agent's problem.
double	p
	The probability with which a new value is chosen.
int	numberOfVariables
	The number of variables owned by this agent.
Queue	queue
	The message queue.
HashMap< String, VariableInfo< Val, U > >	infos
	For each variable a container with information.
DetermineAssignment< Val, U >	decisionStrategy
	Strategy used to determine a new assignment.
boolean	started
	`true` when the module has been initialized, and false otherwise
Map< String, String >	owners
	For each variable the agent that owns it.
int	nbrCycles
	The number of synchronous cycles before termination (except for isolated variables).
int	variableFinishedCounter
	Counts the number of variables that have hit the desired cycle count.
boolean	terminated
	`true` when this agent has sent the agent finished message during initialization

Detailed Description

Author: Brammert Ottens, 10 aug 2009

This class implements the Distributed Local Search algorithm DSA as described in "Distributed stochastic search and distributed breakout: properties, comparison and applications to constraint optimization problems in sensor networks" by Zhang et al, 2005.

DSA is a very simple algorithm, where each variable decides whether to changes its value based on the values of its neighbouring variables and some local decision procedure. If the variable value changes this is reported to its neighbours via a message. The decision procedures implemented here are as follows, where delta is the difference between the current local utility and the optimal local utility obtainable when changing one's value, in terms of number of conflicts if either one is infeasible, or in terms of utility if both are feasible. v is the value that gives this optimal utility and 0 <= p <= 1 a probability

                            delta @iliteral > @endiliteral  0               conflict, delta == 0            no conflict, delta == 0

DSA-A : v with p - - DSA-B : v with p v with p - DSA-C : v with p v with p v with p DSA-D : v v with p - DSA-E : v v with p v with p

Parameters

<Val>	type used for variable values
<U>	type used for utility values

Todo: Implement strategies B and D.

Constructor & Destructor Documentation

◆ DSA() [1/3]

frodo2.algorithms.localSearch.dsa.DSA< Val extends Addable< Val >, U extends Addable< U > >.DSA	(	Element	parameters,
		DCOPProblemInterface< Val, U >	problem )

Constructor for the stats gatherer mode.

Parameters

parameters	the parameters of the module
problem	the overall problem

References assignmentHistoriesMap, convergence, numberOfVariables, and problem.

◆ DSA() [2/3]

frodo2.algorithms.localSearch.dsa.DSA< Val extends Addable< Val >, U extends Addable< U > >.DSA	(	DCOPProblemInterface< Val, U >	problem,
		Element	parameters ) throws ClassNotFoundException

Constructor.

Parameters

problem	description of the local problem
parameters	parameters of the module

Exceptions

ClassNotFoundException if the module parameters specify an unknown class for utility values

References decisionStrategy, DSA(), nbrCycles, p, problem, and setDecisionStrategy().

Here is the call graph for this function:

◆ DSA() [3/3]

frodo2.algorithms.localSearch.dsa.DSA< Val extends Addable< Val >, U extends Addable< U > >.DSA	(	DCOPProblemInterface< Val, U >	problem,
		Element	parameters,
		int	nbrCycles )

Constructor.

Parameters

problem	description of the local problem
parameters	parameters of the module
nbrCycles	the number of cycles that the algorithm should run

References decisionStrategy, DSA(), nbrCycles, p, problem, and setDecisionStrategy().

Here is the call graph for this function:

Member Function Documentation

◆ createVariableInfo()

VariableInfo< Val, U > frodo2.algorithms.localSearch.dsa.DSA< Val extends Addable< Val >, U extends Addable< U > >.createVariableInfo	(	String	variableID,
		Val[]	domain,
		String[]	neighbours,
		DCOPProblemInterface< Val, U >	problem )

protected

method used to create a VariableInfo object

Author: Brammert Ottens, 16 feb. 2011

Parameters

variableID	the ID of the variable
domain	the domain of the variable
neighbours	the neighbors of the variable
problem	the local problem definition

Returns: a VariableInfo object for variableID

References problem.

Referenced by init().

◆ getAssignmentHistories()

HashMap< String, ArrayList< CurrentAssignment< Val > > > frodo2.algorithms.localSearch.dsa.DSA< Val extends Addable< Val >, U extends Addable >.getAssignmentHistories ( )

See also: frodo2.algorithms.StatsReporterWithConvergence.getAssignmentHistories()

Implements frodo2.algorithms.StatsReporterWithConvergence< Val extends Addable< Val > >.

References assignmentHistoriesMap.

◆ getCurrentSolution()

Map< String, Val > frodo2.algorithms.localSearch.dsa.DSA< Val extends Addable< Val >, U extends Addable >.getCurrentSolution ( )

See also: StatsReporterWithConvergence.getCurrentSolution()

Todo: Auto-generated method stub

Implements frodo2.algorithms.StatsReporterWithConvergence< Val extends Addable< Val > >.

◆ getCurrentUtility()

U frodo2.algorithms.localSearch.dsa.DSA< Val extends Addable< Val >, U extends Addable >.getCurrentUtility ( String variable )

Getter method.

Author: Brammert Ottens, 12 aug 2009

Parameters

variable the variable for which the utility is requested

Returns: the current utility

References infos.

◆ getCurrentValue()

Val frodo2.algorithms.localSearch.dsa.DSA< Val extends Addable< Val >, U extends Addable >.getCurrentValue ( String variable )

Getter method.

Author: Brammert Ottens, 12 aug 2009

Parameters

variable the variable for which the value is requested

Returns: the value of the variable

References infos.

◆ getMsgTypes()

Collection< MessageType > frodo2.algorithms.localSearch.dsa.DSA< Val extends Addable< Val >, U extends Addable >.getMsgTypes ( )

See also: frodo2.communication.IncomingMsgPolicyInterface.getMsgTypes()

Implements frodo2.communication.MessageListener< T >.

References frodo2.algorithms.AgentInterface< V extends Addable< V > >.AGENT_FINISHED, START_MSG_TYPE, frodo2.algorithms.AgentInterface< V extends Addable< V > >.STOP_AGENT, and VALUE_MSG_TYPE.

◆ getStatsFromQueue()

void frodo2.algorithms.localSearch.dsa.DSA< Val extends Addable< Val >, U extends Addable >.getStatsFromQueue ( Queue queue )

See also: frodo2.algorithms.StatsReporter.getStatsFromQueue(frodo2.communication.Queue)

Implements frodo2.algorithms.StatsReporter.

References CONV_STATS_MSG_TYPE, and queue.

◆ init()

void frodo2.algorithms.localSearch.dsa.DSA< Val extends Addable< Val >, U extends Addable >.init ( )

protected

Initializes the agent's variables.

Author: Brammert Ottens, 10 aug 2009

References frodo2.algorithms.AgentInterface< V extends Addable< V > >.AGENT_FINISHED, assignmentHistoriesMap, CONV_STATS_MSG_TYPE, convergence, createVariableInfo(), frodo2.algorithms.localSearch.dsa.DSA< Val extends Addable< Val >, U extends Addable >.VariableInfo< Val extends Addable< Val >, U extends Addable >.currentValue, frodo2.algorithms.localSearch.dsa.DSA< Val extends Addable< Val >, U extends Addable >.VariableInfo< Val extends Addable< Val >, U extends Addable >.cycleCounter, infos, frodo2.algorithms.localSearch.dsa.DSA< Val extends Addable< Val >, U extends Addable >.VariableInfo< Val extends Addable< Val >, U extends Addable >.lastSentMsgs, numberOfVariables, owners, problem, queue, frodo2.communication.Queue.sendMessageToSelf(), started, frodo2.algorithms.AgentInterface< V extends Addable< V > >.STATS_MONITOR, terminated, and variableFinishedCounter.

Referenced by notifyIn().

Here is the call graph for this function:

◆ log()

void frodo2.algorithms.localSearch.dsa.DSA< Val extends Addable< Val >, U extends Addable< U > >.log	(	String	variableID,
		String	message )

protected

Log function used to print the variables state during debugging.

Parameters

variableID	The ID of the variable that is logging
message	The message that must be logged

References LOG, and loggers.

◆ notifyIn()

void frodo2.algorithms.localSearch.dsa.DSA< Val extends Addable< Val >, U extends Addable >.notifyIn ( Message msg )

See also: StatsReporterWithConvergence.notifyIn(Message)

Todo: Reusing messages is no longer useful

Implements frodo2.communication.IncomingMsgPolicyInterface< T >.

References frodo2.algorithms.AgentInterface< V extends Addable< V > >.AGENT_FINISHED, CONV_STATS_MSG_TYPE, frodo2.communication.MessageType.equals(), init(), notifyIn(), and VALUE_MSG_TYPE.

Referenced by notifyIn().

Here is the call graph for this function:

◆ reset()

void frodo2.algorithms.localSearch.dsa.DSA< Val extends Addable< Val >, U extends Addable >.reset ( )

See also: StatsReporterWithConvergence.reset()

Todo: Auto-generated method stub

Implements frodo2.algorithms.StatsReporter.

◆ setDecisionStrategy()

void frodo2.algorithms.localSearch.dsa.DSA< Val extends Addable< Val >, U extends Addable >.setDecisionStrategy ( String decisionStrategy )

protected

Method used to set the decision strategy.

Author: Brammert Ottens, 23 mrt. 2011

Parameters

decisionStrategy the decision strategy to be used

References decisionStrategy, DSA(), and setDecisionStrategy().

Referenced by DSA(), DSA(), and setDecisionStrategy().

Here is the call graph for this function:

◆ setQueue()

void frodo2.algorithms.localSearch.dsa.DSA< Val extends Addable< Val >, U extends Addable >.setQueue ( Queue queue )

See also: frodo2.communication.IncomingMsgPolicyInterface.setQueue(frodo2.communication.Queue)

Implements frodo2.communication.MessageListener< T >.

References queue.

◆ setSilent()

void frodo2.algorithms.localSearch.dsa.DSA< Val extends Addable< Val >, U extends Addable >.setSilent ( boolean silent )

See also: StatsReporterWithConvergence.setSilent(boolean)

Implements frodo2.algorithms.StatsReporter.

Member Data Documentation

◆ assignmentHistoriesMap

HashMap<String, ArrayList<CurrentAssignment<Val> > > frodo2.algorithms.localSearch.dsa.DSA< Val extends Addable< Val >, U extends Addable >.assignmentHistoriesMap

protected

For each variable its assignment history.

Referenced by DSA(), getAssignmentHistories(), and init().

◆ CONV_STATS_MSG_TYPE

final MessageType frodo2.algorithms.localSearch.dsa.DSA< Val extends Addable< Val >, U extends Addable >.CONV_STATS_MSG_TYPE = new MessageType ("DSA", "ConvStats")

static

The type of the message containing the assignment history.

Referenced by getStatsFromQueue(), init(), and notifyIn().

◆ convergence

final boolean frodo2.algorithms.localSearch.dsa.DSA< Val extends Addable< Val >, U extends Addable >.convergence

protected

Whether the listener should record the assignment history or not.

Referenced by DSA(), and init().

◆ decisionStrategy

DetermineAssignment<Val, U> frodo2.algorithms.localSearch.dsa.DSA< Val extends Addable< Val >, U extends Addable >.decisionStrategy

protected

Strategy used to determine a new assignment.

Referenced by DSA(), DSA(), and setDecisionStrategy().

◆ infos

HashMap<String, VariableInfo<Val, U> > frodo2.algorithms.localSearch.dsa.DSA< Val extends Addable< Val >, U extends Addable >.infos

protected

For each variable a container with information.

Referenced by getCurrentUtility(), getCurrentValue(), and init().

◆ LOG

final boolean frodo2.algorithms.localSearch.dsa.DSA< Val extends Addable< Val >, U extends Addable >.LOG = false

protected

When true, every variable writes log information to a log file.

Referenced by log().

◆ loggers

HashMap<String, BufferedWriter> frodo2.algorithms.localSearch.dsa.DSA< Val extends Addable< Val >, U extends Addable >.loggers

protected

A list of buffered writers used to log information during debugging.

Referenced by log().

◆ nbrCycles

int frodo2.algorithms.localSearch.dsa.DSA< Val extends Addable< Val >, U extends Addable >.nbrCycles

protected

The number of synchronous cycles before termination (except for isolated variables).

Referenced by DSA(), and DSA().

◆ numberOfVariables

int frodo2.algorithms.localSearch.dsa.DSA< Val extends Addable< Val >, U extends Addable >.numberOfVariables

protected

The number of variables owned by this agent.

Referenced by DSA(), and init().

◆ owners

Map<String, String> frodo2.algorithms.localSearch.dsa.DSA< Val extends Addable< Val >, U extends Addable >.owners

protected

For each variable the agent that owns it.

Referenced by init().

◆ p

double frodo2.algorithms.localSearch.dsa.DSA< Val extends Addable< Val >, U extends Addable >.p

protected

The probability with which a new value is chosen.

Referenced by DSA(), and DSA().

◆ problem

DCOPProblemInterface<Val, U> frodo2.algorithms.localSearch.dsa.DSA< Val extends Addable< Val >, U extends Addable >.problem

protected

The agent's problem.

Referenced by createVariableInfo(), DSA(), DSA(), DSA(), init(), and frodo2.algorithms.localSearch.dsa.DSA< Val extends Addable< Val >, U extends Addable >.VariableInfo< Val extends Addable< Val >, U extends Addable >.VariableInfo().

◆ queue

Queue frodo2.algorithms.localSearch.dsa.DSA< Val extends Addable< Val >, U extends Addable >.queue

protected

The message queue.

Referenced by getStatsFromQueue(), init(), and setQueue().

◆ START_MSG_TYPE

MessageType frodo2.algorithms.localSearch.dsa.DSA< Val extends Addable< Val >, U extends Addable >.START_MSG_TYPE = AgentInterface.START_AGENT

static

The type of the message telling the module to start.

Referenced by getMsgTypes().

◆ started

boolean frodo2.algorithms.localSearch.dsa.DSA< Val extends Addable< Val >, U extends Addable >.started

protected

true when the module has been initialized, and false otherwise

Referenced by init().

◆ terminated

boolean frodo2.algorithms.localSearch.dsa.DSA< Val extends Addable< Val >, U extends Addable >.terminated

protected

true when this agent has sent the agent finished message during initialization

Referenced by init().

◆ VALUE_MSG_TYPE

MessageType frodo2.algorithms.localSearch.dsa.DSA< Val extends Addable< Val >, U extends Addable >.VALUE_MSG_TYPE = new MessageType ("DSA", "VALUE")

static

The type of the message used to report a value to neighboring variables.

Referenced by getMsgTypes(), notifyIn(), frodo2.algorithms.localSearch.dsa.VALUEmsg< Val extends Addable< Val > >.VALUEmsg(), and frodo2.algorithms.localSearch.dsa.VALUEmsg< Val extends Addable< Val > >.VALUEmsg().

◆ variableFinishedCounter

int frodo2.algorithms.localSearch.dsa.DSA< Val extends Addable< Val >, U extends Addable >.variableFinishedCounter

protected

Counts the number of variables that have hit the desired cycle count.

Referenced by init().

The documentation for this class was generated from the following file:

src/frodo2/algorithms/localSearch/dsa/DSA.java

Classes

Public Member Functions

Static Public Attributes

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ DSA() [1/3]

◆ DSA() [2/3]

◆ DSA() [3/3]

Member Function Documentation

◆ createVariableInfo()

◆ getAssignmentHistories()

◆ getCurrentSolution()

◆ getCurrentUtility()

◆ getCurrentValue()

◆ getMsgTypes()

◆ getStatsFromQueue()

◆ init()

◆ log()

◆ notifyIn()

◆ reset()

◆ setDecisionStrategy()

◆ setQueue()

◆ setSilent()

Member Data Documentation

◆ assignmentHistoriesMap

◆ CONV_STATS_MSG_TYPE

◆ convergence

◆ decisionStrategy

◆ infos

◆ LOG

◆ loggers

◆ nbrCycles

◆ numberOfVariables

◆ owners

◆ p

◆ problem

◆ queue

◆ START_MSG_TYPE

◆ started

◆ terminated

◆ VALUE_MSG_TYPE

◆ variableFinishedCounter