Binary Relation Learning and Classifying for Preselection in Evolutionary Algorithms

Evolutionary algorithms (EAs) are a kind of population-based heuristic optimization method by using trial-and-error. Therefore, the search efficiency is a major concern in both of the algorithm design and applications. The preselection, which estimates the quality of candidate solutions and discards unpromising ones before fitness evaluation, is a widely used component for reducing the number of fitness evaluations in EAs. The surrogate models, such as regression and classification, are usually applied for quality estimation. In some EA frameworks, the relationship between a pair of solutions helps to distinguish 'good' and 'bad' solutions. In such cases, it is not necessary to estimate the specific quality of each candidate solution but the binary relationship of a pair of solutions. Following this idea, this article proposes a new preselection strategy, called relationship classification-based preselection (RCPS). In RCPS, a classification model is built to learn the relationship between a pair of solutions based on a given training data set, and promising candidate solutions are prescreened by this relation. The mechanism of RCPS is visualized and analyzed. The advantages of RCPS over traditional surrogate model-based preselection strategies are illustrated through a comprehensive empirical study. The experimental results suggest that on two sets of test suits, RCPS outperforms the comparison preselection strategies. To achieve a same accuracy, an EA with RCPS needs a smaller number of fitness evaluations than the one without RCPS.