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]:*T*ree*A*ugmented*N*aive 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 close to the current network . It accepts the network if it is better than the current, i.e., . Otherwise, it accepts the candidate with probability

where is the temperature at iteration . The temperature starts at and is slowly decreases with each iteration.Specific options:

`TStart`start temperature .`delta`is the factor used to update the temperature, so .`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 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 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 ( = number of nodes) bits where bit represents whether there is an arrow from node .

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 in the bit representation and selecting the first 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.