# A family of heuristic algorithms that aims at finding high scoring directed acyclic graphs

Source:`R/search_heuristic.R`

`searchHeuristic.Rd`

A flexible implementation of multiple greedy search algorithms to find high scoring network (DAG)

## Usage

```
searchHeuristic(score.cache, score = "mlik",
num.searches = 1, seed = 42L, start.dag = NULL,
max.steps = 100,
algo = "hc", tabu.memory = 10, temperature = 0.9,
verbose = FALSE, ...)
```

## Arguments

- score.cache
output from

`buildScoreCache()`

.- score
which score should be used to score the network. Possible choices are

`aic, bic, mdl, mlik`

.- num.searches
a positive integer giving the number of different search to run, see details.

- seed
a non-negative integer which sets the seed.

- start.dag
a DAG given as a matrix, see details for format, which can be used to explicity provide a starting point for the structural search.

- max.steps
a constant giving the number of search steps per search, see details.

- algo
which heuristic algorithm should be used. Possible choices are:

`hc, tabu, sa`

.- tabu.memory
a non-negative integer number to set the memory of the

`tabu`

search.- temperature
a real number giving the update in temperature for the

`sa`

(simulated annealing) search algorithm.- verbose
if TRUE then provides some additional output.

- ...
further arguments passed to or from other methods.

## Value

An object of class `abnHeuristic`

(which extends the class `abnLearnd`

) and contains list with entires:

- dags
a list of DAGs

- scores
a vector giving the network score for the locally optimal network for each search

- detailed.score
a vector giving the evolution of the network score for the all the random restarts

- score
a number giving the network score for the locally optimal network

- score.cache
the pre-computed cache of scores

- num.searches
a numeric giving the number of random restart

- max.steps
a numeric giving the maximal number of optimization steps within each search

- algorithm
a character for indicating the algorithm used

## Details

This function is a flexible implementation of multiple greedy heuristic algorithms,
particularly well adapted to the `abn`

framework.
It targets multi-random restarts heuristic algorithms.
The user can select the `num.searches`

and the maximum number of steps
within by `max.steps`

. The optimization algorithm within each search is
relatively rudimentary.

The function `searchHeuristic`

is different from the
`searchHillClimber`

in the sense that this function is fully
written in R, whereas the `searchHillClimber`

is written in C
and thus expected to be faster. The function `searchHillClimber`

at each hill-climbing step consider every information from the pre-computed
scores cache while the function `searchHeuristic`

performs a local
stepwise optimization. This function chooses a structural move (or edge move)
and compute the score's change. On this point, it is closer to the MCMCMC
algorithm from Madigan and York (1995) and Giudici and Castelo (2003)
with a single edge move.

If the user select `random`

, then a random valid DAG is selected.
The routine used favourise low density structure.
The function implements three algorithm selected with the
parameter `algo`

: `hc`

, `tabu`

or `sa`

.

If `algo=hc`

:
The Hill-climber algorithm (`hc`

) is a single move algorithm.
At each Hill-climbing step within a search an arc is attempted to be added.
The new score is computed and compared to the previous network's score.

If `algo=tabu`

:
The same algorithm is as with `hc`

is used, but a list of banned moves
is computed. The parameter `tabu.memory`

controls the length of the tabu
list. The idea is that the classical Hill-climber algorithm is inefficient
when it should cross low probability regions to unblock from a local maximum
and reaching a higher score peak. By forcing the algorithm to choose some not
already used moves, this will force the algorithm to escape the local maximum.

If `algo=sa`

:
This variant of the heuristic search algorithm is based on simulated annealing
described by Metropolis et al. (1953).
Some accepted moves could result in a decrease of the network score.
The acceptance rate can be monitored with the parameter `temperature`

.

## References

Heckerman, D., Geiger, D. and Chickering, D. M. (1995). Learning Bayesian networks: The combination of knowledge and statistical data. *Machine Learning*, 20, 197-243.
Madigan, D. and York, J. (1995) "Bayesian graphical models for discrete data". International Statistical Review, 63:215232.
Giudici, P. and Castelo, R. (2003). "Improving Markov chain Monte Carlo model search for data mining". Machine Learning, 50:127158.
Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., & Teller, E. (1953). "Equation of state calculations by fast computing machines". The journal of chemical physics, 21(6), 1087-1092.

## Examples

```
if (FALSE) {
##############################################
## example: use built-in simulated data set
##############################################
mydat <- ex1.dag.data ## this data comes with abn see ?ex1.dag.data
## setup distribution list for each node
mydists<-list(b1="binomial", p1="poisson", g1="gaussian", b2="binomial",
p2="poisson", b3="binomial", g2="gaussian", b4="binomial",
b5="binomial", g3="gaussian")
mycache <- buildScoreCache(data.df = mydat, data.dists = mydists, max.parents = 2)
## Now peform 10 greedy searches
heur.res <- searchHeuristic(score.cache = mycache, data.dists = mydists,
start.dag = "random", num.searches = 10,
max.steps = 50)
## Plot (one) dag
plotAbn(heur.res$dags[[1]], data.dists = mydists)
}
```