Search algorithms

The following search algorithms are implemented for local score metrics;

• K2 [5]: hill climbing add arcs with a fixed ordering of variables.
  Specific option: randomOrder if true a random ordering of the nodes is made at the beginning of the search. If false (default) the ordering in the data set is used. The only exception in both cases is that in case the initial network is a naive Bayes network (initAsNaiveBayes set true) the class variable is made first in the ordering.
• Hill Climbing [2]: hill climbing adding and deleting arcs with no fixed ordering of variables.
  useArcReversal if true, also arc reversals are consider when determining the next step to make.
• Repeated Hill Climber starts with a randomly generated network and then applies hill climber to reach a local optimum. The best network found is returned.
  useArcReversal option as for Hill Climber.
• LAGD Hill Climbing does hill climbing with look ahead on a limited set of best scoring steps, implemented by Manuel Neubach. The number of look ahead steps and number of steps considered for look ahead are configurable.
• TAN [3,7]: Tree Augmented Naive Bayes where the tree is formed by calculating the maximum weight spanning tree using Chow and Liu algorithm [4].
  No specific options.
• Simulated annealing [1]: using adding and deleting arrows.
  The algorithm randomly generates a candidate network $B_S'$ close to the current network $B_S$. It accepts the network if it is better than the current, i.e., $Q(B_S',D) > Q(B_S,D)$. Otherwise, it accepts the candidate with probability
  
  $$e^{t_i \cdot(Q(B_S',D) -Q(B_S,D))}$$
  
  
  where $t_i$ is the temperature at iteration $i$. The temperature starts at $t_0$ and is slowly decreases with each iteration.
  

  Specific options:
  TStart start temperature $t_0$.
  delta is the factor $\delta$ used to update the temperature, so $t_{i+1}=t_i \cdot \delta$.
  runs number of iterations used to traverse the search space.
  seed is the initialization value for the random number generator.
  

• Tabu search [1]: using adding and deleting arrows.
  Tabu search performs hill climbing until it hits a local optimum. Then it steps to the least worse candidate in the neighborhood. However, it does not consider points in the neighborhood it just visited in the last $tl$ steps. These steps are stored in a so called tabu-list.
  

  Specific options:
  runs is the number of iterations used to traverse the search space.
  tabuList is the length $tl$ of the tabu list.

• Genetic search: applies a simple implementation of a genetic search algorithm to network structure learning. A Bayes net structure is represented by a array of $n\cdot n$ ($n$ = number of nodes) bits where bit $i\cdot n + j$ represents whether there is an arrow from node $j\to i$.
  
  

  Specific options:
  populationSize is the size of the population selected in each generation.
  descendantPopulationSize is the number of offspring generated in each generation.
  runs is the number of generation to generate.
  seed is the initialization value for the random number generator.
  useMutation flag to indicate whether mutation should be used. Mutation is applied by randomly adding or deleting a single arc.
  useCrossOver flag to indicate whether cross-over should be used. Cross-over is applied by randomly picking an index $k$ in the bit representation and selecting the first $k$ bits from one and the remainder from another network structure in the population. At least one of useMutation and useCrossOver should be set to true.
  useTournamentSelection when false, the best performing networks are selected from the descendant population to form the population of the next generation. When true, tournament selection is used. Tournament selection randomly chooses two individuals from the descendant population and selects the one that performs best.