Package org.bigraphs.framework.simulation.modelchecking

Class SimulatedAnnealingFrontierStrategy<B extends Bigraph<? extends Signature<?>>>

java.lang.Object

org.bigraphs.framework.simulation.modelchecking.ModelCheckingStrategySupport<B>

org.bigraphs.framework.simulation.modelchecking.SimulatedAnnealingFrontierStrategy<B>

Type Parameters:

B - the type of bigraph elements processed by this strategy

All Implemented Interfaces:

ModelCheckingStrategy<B>

public abstract class SimulatedAnnealingFrontierStrategy<B extends Bigraph<? extends Signature<?>>>
extends ModelCheckingStrategySupport<B>

This class is an abstraction of a model checking strategy based on the Simulated Annealing algorithm.

This strategy is implemented using a cooling schedule, which helps in controlling the temperature of the annealing process. The temperature influences the probability of moving to a state of lower quality, allowing the algorithm to potentially escape local optima in the search space.

When computing state (bigraph) similarity via a kernel, the normalized kernel will be computed by this strategy afterward (kTilde(Bigraph, Bigraph).

The class is designed to be extended and requires subclasses to provide implementations for some specific methods such as:

• graphKernel(Bigraph, Bigraph): Calculation of a graph kernel for computing similarity between two bigraphs
• SimulatedAnnealingFrontierStrategy.CoolingSchedules: Default implementations are provided such as linear, geometric and logarithmic cooling.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static interface	SimulatedAnnealingFrontierStrategy.CoolingSchedule	Functional interface representing a cooling schedule used in simulated annealing processes.

Nested classes/interfaces inherited from class org.bigraphs.framework.simulation.modelchecking.ModelCheckingStrategySupport

ModelCheckingStrategySupport.MatchResult<B extends Bigraph<? extends Signature<?>>>

Field Summary

Fields

Modifier and Type	Field	Description
protected int	currentEpoch
protected final Map<B,Double>	energyCache	Caches
protected double	energyEps
protected final int	epochSize	Cool temperature after n iterations of an epoch before starting a new epoch.
protected int	fairnessCounter
protected final int	fairnessK	Fairness: every fairnessK expansions, do one FIFO expansion.
protected final Deque<B>	fifoQueue	Frontier as fairness queue
protected final List<B>	goalExemplars	Goal prototype states
protected boolean	internalStop
protected int	iterationInEpoch
int	maxEpoch
protected double	temperature	State variables of the SA algorithms

Fields inherited from class org.bigraphs.framework.simulation.modelchecking.ModelCheckingStrategySupport

decoder, encoder, isRunning, logger, modelChecker, occurrenceCounter, predicateChecker, worklistFilter

Constructor Summary

Constructors

Constructor	Description
SimulatedAnnealingFrontierStrategy(List<B> goalExemplars, double initialTemperature, int epochSize, int fairnessK)

Method Summary

Modifier and Type	Method	Description
void	addToWorklist(Collection<B> worklist, B bigraph)
protected B	boltzmannPick(Collection<B> worklist, double t)
Collection<B>	createWorklist()
protected double	energy(B s)
protected double	graphKernel(B graphA, B graphB)	A bigraph kernel (e.g., Weisfeiler–Lehman) over the encoded graphs.
protected double	kTilde(B s, B g)	Normalized bigraph kernel for two bigraphs.
protected B	popExistingInOpenFiFo(Collection<B> worklist)
B	removeNext(Collection<B> worklist)	Called when the framework wants the next state to expand.
protected void	stopProcedure(B chosen)
SimulatedAnnealingFrontierStrategy<B>	withCooling(SimulatedAnnealingFrontierStrategy.CoolingSchedule c)
SimulatedAnnealingFrontierStrategy<B>	withModelChecker(BigraphModelChecker<B> modelChecker)

Methods inherited from class org.bigraphs.framework.simulation.modelchecking.ModelCheckingStrategySupport

evaluatePredicates, getBigraphMatches, resetOccurrenceCounter, setFilter, synthesizeTransitionSystem

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Details

energyEps

protected double energyEps

internalStop

protected volatile boolean internalStop

fairnessK

protected final int fairnessK

Fairness: every fairnessK expansions, do one FIFO expansion.

epochSize

protected final int epochSize

Cool temperature after n iterations of an epoch before starting a new epoch.

goalExemplars

protected final List<B extends Bigraph<? extends Signature<?>>> goalExemplars

Goal prototype states

fifoQueue

protected final Deque<B extends Bigraph<? extends Signature<?>>> fifoQueue

Frontier as fairness queue

energyCache

protected final Map<B extends Bigraph<? extends Signature<?>>,Double> energyCache

Caches

temperature

protected double temperature

State variables of the SA algorithms

iterationInEpoch

protected int iterationInEpoch

currentEpoch

protected int currentEpoch

maxEpoch

public int maxEpoch

fairnessCounter

protected int fairnessCounter

Constructor Details

SimulatedAnnealingFrontierStrategy

public SimulatedAnnealingFrontierStrategy(List<B> goalExemplars,
 double initialTemperature,
 int epochSize,
 int fairnessK)

Method Details

withCooling

public SimulatedAnnealingFrontierStrategy<B> withCooling(SimulatedAnnealingFrontierStrategy.CoolingSchedule c)

withModelChecker

public SimulatedAnnealingFrontierStrategy<B> withModelChecker(BigraphModelChecker<B> modelChecker)

createWorklist

public Collection<B> createWorklist()

Specified by:

createWorklist in class ModelCheckingStrategySupport<B extends Bigraph<? extends Signature<?>>>

removeNext

public B removeNext(Collection<B> worklist)

Called when the framework wants the next state to expand. State is picked from worklist using either fairness FIFO or SA Boltzmann sampling.

Specified by:

removeNext in class ModelCheckingStrategySupport<B extends Bigraph<? extends Signature<?>>>

stopProcedure

protected void stopProcedure(B chosen)

addToWorklist

public void addToWorklist(Collection<B> worklist,
 B bigraph)

Specified by:

addToWorklist in class ModelCheckingStrategySupport<B extends Bigraph<? extends Signature<?>>>

graphKernel

protected double graphKernel(B graphA,
 B graphB)

A bigraph kernel (e.g., Weisfeiler–Lehman) over the encoded graphs. Return a non-negative similarity value.

kTilde

protected double kTilde(B s,
 B g)

Normalized bigraph kernel for two bigraphs.

The specific kernel specified in graphKernel(Bigraph, Bigraph) must be implemented via subclassing.

Parameters:

s - left bigraph

g - right bigraph

popExistingInOpenFiFo

protected B popExistingInOpenFiFo(Collection<B> worklist)

boltzmannPick

protected B boltzmannPick(Collection<B> worklist,
 double t)

energy

protected double energy(B s)