Module es.upm.fi.cig.multictbnc
Package es.upm.fi.cig.multictbnc.learning.structure.optimisation.tabusearch

Class BNTabuSearch

java.lang.Object
es.upm.fi.cig.multictbnc.learning.structure.optimisation.hillclimbing.implementation.BNHillClimbing
es.upm.fi.cig.multictbnc.learning.structure.optimisation.tabusearch.BNTabuSearch
All Implemented Interfaces:
HillClimbingImplementation
public class BNTabuSearch extends BNHillClimbing
Implements the tabu search algorithm for Bayesian networks.

  • Constructor Details

    • BNTabuSearch

      public BNTabuSearch(BNScoreFunction scoreFunction, int tabuListSize, int maxNumNotImprovements)
      Initialises the tabu search algorithm by proving a score function and a tabu list size.
      Parameters:
      scoreFunction - score function
      tabuListSize - tabu list size
      maxNumNotImprovements - maximum number of iterations to continue without improvements in the score before stopping the search

  • Method Details

    • 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
      Overrides:
      getIdentifier in class BNHillClimbing
      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
      Overrides:
      getParametersAlgorithm in class BNHillClimbing
      Returns:
      a Map with the parameters used by the algorithm

    • 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
      Overrides:
      findStructure in class BNHillClimbing
      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)
      Description copied from class: BNHillClimbing
      Finds the best neighbour of the adjacency matrix "bestStructure" given an operation to perform (addition, deletion or reversal of arcs).
      Overrides:
      findBestNeighbor in class BNHillClimbing
      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

    • isScoreImproved

      protected boolean isScoreImproved(HillClimbingSolution solution, boolean[][][] adjacencyMatrices, int idxBestOperation, double iterationBestScore)
      Description copied from class: BNHillClimbing
      Checks if a solution given by the hill climbing algorithm in a certain iteration is better than the current solution.
      Overrides:
      isScoreImproved in class BNHillClimbing
      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