Search PubMed⌕ Search

Biomedical subjects

E B Baum

Publications and source records attributed to E B Baum.

3 recordsLinked to original sources
PubMed2001

Where genetic algorithms excel.

We analyze the performance of a genetic algorithm (GA) we call Culling, and a variety of other algorithms, on a problem we refer to as the Additive Search Problem (ASP). We show that the problem of learning the Ising perceptron is reducible to a noisy version of ASP. Noisy ASP is the first problem we are aware of where a genetic-type algorithm bests all known competitors. We generalize ASP to k-ASP to study whether GAs will achieve "implicit parallelism" in a problem with many more schemata. GAs fail to achieve this implicit parallelism, but we describe an algorithm we call Explicitly Parallel Search that succeeds. We also compute the optimal culling point for selective breeding, which turns out to be independent of the fitness function or the population distribution. We also analyze a mean field theoretic algorithm performing similarly to Culling on many problems. These results provide insight into when and how GAs can beat competing methods.

Algorithms↗
PubMed1999

Propagating distributions up directed acyclic graphs.

In a previous article, we considered game trees as graphical models. Adopting an evaluation function that returned a probability distribution over values likely to be taken at a given position, we described how to build a model of uncertainty and use it for utility-directed growth of the search tree and for deciding on a move after search was completed. In some games, such as chess and Othello, the same position can occur more than once, collapsing the game tree to a directed acyclic graph (DAG). This induces correlations among the distributions at sibling nodes. This article discusses some issues that arise in extending our algorithms to a DAG. We give a simply described algorithm for correctly propagating distributions up a game DAG, taking account of dependencies induced by the DAG structure. This algorithm is exponential time in the worst case. We prove that it is #P complete to propagate distributions up a game DAG correctly. We suggest how our exact propagation algorithm can yield a fast but inexact heuristic.

Algorithms↗