Optimal Sampling and Speed-Up for Genetic Algorithms on the Sampled OneMax Problem

摘要

This paper investigates the optimal sampling and the speedup obtained through sampling for the sampled OneMax problem. Theoretical and experimental analyses are given for three different population-sizing models: the decision-making model, the gambler's ruin model, and the fixed population-sizing model. The results suggest that, when the desired solution quality is fixed to a high value, the decision-making model prefers a large sampling size, the fixed population-sizing model prefers a small sampling size, and the gambler's ruin model has no preference for large or small sizes. Among the three population-sizing models, sampling yields speed-up only when the fixed population-sizing model is valid. The results indicate that when the population is sized appropriately, sampling does not yield speed-up for problems with subsolutions of uniform salience.