On sampling-and-classification optimization in discrete domains

As a kind of model-based optimization framework, the sampling-and-classification (SAC) algorithms, where the model is specified to be a classifier, has been recently studied in both theoretical foundation and algorithm implementation. However, the previous work only studied SAC algorithms in real domains. While significant progresses of theoretical evolutionary algorithm have been developed major in discrete domains, it is interesting to understand the SAC algorithms also in finite discrete domains. This paper studies the (e,ó)-query complexity of SAC algorithms, which measures how soon can an algorithm obtain a solution with the desired approximation quality with a probability. Some classical pseudo-Boolean problems are employed to probe the SAC algorithms, including OneMax problem, linear pseudo-Boolean functions, LeadingOnes problem, and Trap problem. The theoretical results disclose that SAC algorithms can achieve a small complexity for approximating these problems. Moreover, an implementation of the SAC framework, the RACOS algorithm, is compared with the well-analyzed (1+1)-EA on these problems.