Module es.upm.fi.cig.multictbnc
Package es.upm.fi.cig.multictbnc.learning.structure.optimisation.hillclimbing.implementation

Class BNHillClimbing

java.lang.Object
es.upm.fi.cig.multictbnc.learning.structure.optimisation.hillclimbing.implementation.BNHillClimbing
All Implemented Interfaces:
HillClimbingImplementation
Direct Known Subclasses:
BNHillClimbingHybridAlgorithm, BNTabuSearch
public class BNHillClimbing extends Object implements HillClimbingImplementation
Implements hill climbing algorithm for BNs.

  • Constructor Details

    • BNHillClimbing

      public BNHillClimbing(BNScoreFunction scoreFunction)
      Constructor that receives the score function to optimise.
      Parameters:
      scoreFunction - score function for Bayesian networks

  • Method Details

    • isScoreImproved

      protected boolean isScoreImproved(HillClimbingSolution solution, boolean[][][] adjacencyMatrices, int idxBestOperation, double iterationBestScore)
      Checks if a solution given by the hill climbing algorithm in a certain iteration is better than the current solution.
      Parameters:
      solution - current solution
      adjacencyMatrices - best adjacency matrices given by each possible operation
      idxBestOperation - index of the best operation
      iterationBestScore - score of the iteration solution
      Returns:
      true if the solution of the iteration is better than the current solution, false otherwise

    • findStructure

      public HillClimbingSolution findStructure(PGM<? extends Node> pgm)
      Description copied from interface: HillClimbingImplementation
      Finds a structure for a given PGM.
      Specified by:
      findStructure in interface HillClimbingImplementation
      Parameters:
      pgm - a probabilistic graphical model
      Returns:
      solution given by the hill climbing algorithm

    • findBestNeighbor

      protected void findBestNeighbor(BN<? extends Node> bn, HillClimbingSolution bestSolution, double[] scores, boolean[][][] adjacencyMatrices, String operation)
      Finds the best neighbour of the adjacency matrix "bestStructure" given an operation to perform (addition, deletion or reversal of arcs).
      Parameters:
      bn - Bayesian network whose structure is being learnt
      bestSolution - best structure so far
      scores - two-dimensional double array containing the structure scores after applying each of the possible operations over the adjacency matrix
      adjacencyMatrices - three-dimensional boolean array containing the resulting adjacency matrices after applying each of the possible operations over the original matrix
      operation - operation to perform over the adjacency matrix

    • computeScore

      protected double computeScore(BN<? extends Node> bn, boolean[][] adjacencyMatrix)
      Computes the score of a structure given an adjacency matrix.
      Parameters:
      bn - Bayesian network whose structure is being learnt
      adjacencyMatrix - adjacency matrix of the structure
      Returns:
      score of the structure

    • getInfoScoreFunction

      public Map<String,String> getInfoScoreFunction()
      Description copied from interface: HillClimbingImplementation
      Returns a Map with the name of the score function that is optimised and the name of the applied penalisation function (if any).
      Specified by:
      getInfoScoreFunction in interface HillClimbingImplementation
      Returns:
      a Map with the name of the score function that is optimised and the name of the penalisation function that is applied

    • findStructure

      public HillClimbingSolution findStructure(PGM<? extends Node> pgm, int idxNode)
      Description copied from interface: HillClimbingImplementation
      Finds the local structure of a given node of a PGM.
      Specified by:
      findStructure in interface HillClimbingImplementation
      Parameters:
      pgm - a probabilistic graphical model
      idxNode - node index
      Returns:
      a HillClimbingSolution

    • findStructure

      public HillClimbingSolution findStructure(PGM<? extends Node> pgm, List<Integer> idxNodes)
      Description copied from interface: HillClimbingImplementation
      Finds the local structure of some given nodes of a PGM.
      Specified by:
      findStructure in interface HillClimbingImplementation
      Parameters:
      pgm - a probabilistic graphical model
      idxNodes - node indexes
      Returns:
      a HillClimbingSolution

    • increaseNumEdgesTested

      protected void increaseNumEdgesTested()
      Increases the number of evaluated edges in one.

    • resetNumEdgesTested

      protected void resetNumEdgesTested()
      Sets to zero the number of evaluated edges.

    • getNumEdgesTested

      public int getNumEdgesTested()
      Returns the number of edges that have been evaluated so far.
      Returns:
      number of edges that have been evaluated so far

    • getIdentifier

      public String getIdentifier()
      Description copied from interface: HillClimbingImplementation
      Returns a unique identifier for the hill climbing-based algorithm.
      Specified by:
      getIdentifier in interface HillClimbingImplementation
      Returns:
      unique identifier for the hill climbing-based algorithm

    • getParametersAlgorithm

      public Map<String,String> getParametersAlgorithm()
      Description copied from interface: HillClimbingImplementation
      Returns the parameters that are used by the hill climbing implementation.
      Specified by:
      getParametersAlgorithm in interface HillClimbingImplementation
      Returns:
      a Map with the parameters used by the algorithm