In the traditional estimation of distribution algorithms (EDAs), all the variables of candidate individuals are perturbed through sampling from a probability distribution of promising individuals. However, it may be unnecessary for the EDAs to perturb all variables of candidate individuals at each generation. This is because one variable may be dependent on another variable and all variables may have different saliences even if they are independent. Therefore, only a subset of all variables in EDAs really function at each generation. This paper proposes a novel class of EDAs, termed as subspace estimation of distribution algorithms (subEDAs), from a new perspective to reduce the space of variables for use in model building and model sampling based on EDAs' performance. In subEDAs, only part of all variables of candidate individuals are perturbed at each generation. Three schemes are described in details to determine which variables should be perturbed at each generation: the random picking method (RP), the majority voting based on the similarity between high quality individuals (MVSH) and the majority voting based on the difference between high quality and low quality individuals (MVDHL). Then, subEDAs + RP, subEDAs + MVSH and subEDAs + MVDHL are tested on several benchmark functions and their algorithmic results are compared with those obtained by EDAs. Our experimental results indicate that subEDAs are able to obtain a comparative result using only a subset of problem variables in the model when compared with traditional EDAs. © 2010 Elsevier B.V. All rights reserved.
Bibliographical noteThis work is supported by Hong Kong RGC GRF Grant 9041353 (CityU 115408), the Fundamental Research Funds for the Central Universities, SCUT (2009ZM0081), NSFC (10826053, 60825306, and U0735004) and GDSF (07118074).
- Estimation of Bayesian network algorithm (EBNA)
- Estimation of distribution algorithms (EDAs)
- Subspace estimation of distribution algorithms (subEDAs)
- Univariate marginal distribution algorithm (UMDA)