Using over-sampling in a Bayesian classifier EDA to solve deceptive and hierarchical problems

Evolutionary algorithms based on probabilistic modeling is a growing research field. Hybrids that borrow ideas from the field of classification were introduced. We extend such hybrids, and evaluate four strategies for truncation of an over-sized population of samples. The strategies are evaluated over a number of difficult problems from the literature, among them, a hierarchical 256-bit HIFF problem. We show that over-sampling in conjunction with a truncation strategy can guide the search without increasing the number of performed fitness evaluations per generation, and that a truncation strategy which inverses the sampling pressure can, fitness-wise, perform significantly better than regular sampling.