A Novel Surrogate-assisted Evolutionary Algorithm Applied to Partition-based Ensemble Learning

We propose a novel surrogate-assisted Evolutionary Algorithm for solving\nexpensive combinatorial optimization problems. We integrate a surrogate model,\nwhich is used for fitness value estimation, into a state-of-the-art P3-like\nvariant of the Gene-Pool Optimal Mixing Algorithm (GOMEA) and adapt the\nresulting algorithm for solving non-binary combinatorial problems. We test the\nproposed algorithm on an ensemble learning problem. Ensembling several models\nis a common Machine Learning technique to achieve better performance. We\nconsider ensembles of several models trained on disjoint subsets of a dataset.\nFinding the best dataset partitioning is naturally a combinatorial non-binary\noptimization problem. Fitness function evaluations can be extremely expensive\nif complex models, such as Deep Neural Networks, are used as learners in an\nensemble. Therefore, the number of fitness function evaluations is typically\nlimited, necessitating expensive optimization techniques. In our experiments we\nuse five classification datasets from the OpenML-CC18 benchmark and\nSupport-vector Machines as learners in an ensemble. The proposed algorithm\ndemonstrates better performance than alternative approaches, including Bayesian\noptimization algorithms. It manages to find better solutions using just several\nthousand fitness function evaluations for an ensemble learning problem with up\nto 500 variables.\n