Surrogate-Assisted Genetic Algorithm for Wrapper Feature Selection
Feature selection is an intractable problem, therefore practical algorithms often trade off the solution accuracy against the computation time. In this paper, we propose a novel multi-stage feature selection framework utilizing multiple levels of approximations, or surrogates. Such a framework allows for using wrapper approaches in a much more computationally efficient way, significantly increasing the quality of feature selection solutions achievable, especially on large datasets. We design and evaluate a Surrogate-Assisted Genetic Algorithm (SAGA) which utilizes this concept to guide the evolutionary search during the early phase of exploration. SAGA only switches to evaluating the original function at the final exploitation phase. We prove that the run-time upper bound of SAGA surrogate-assisted stage is at worse equal to the wrapper GA, and it scales better for induction algorithms of high order of complexity in number of instances. We demonstrate, using 14 datasets from the UCI ML repository, that in practice SAGA significantly reduces the computation time compared to a baseline wrapper Genetic Algorithm (GA), while converging to solutions of significantly higher accuracy. Our experiments show that SAGA can arrive at near-optimal solutions three times faster than a wrapper GA, on average. We also showcase the importance of evolution control approach designed to prevent surrogates from misleading the evolutionary search towards false optima.
Code (1)
Tasks
feature selectionMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Fast Genetic Algorithm for feature selection -- A qualitative approximation approach
Evolutionary Algorithms (EAs) are often challenging to apply in real-world settings since evolutionary computations involve a large number of evaluations of a typically expensive fitness function. For example, an evaluat…
Evolutionary Algorithmsfeature selectionBenchmarking Surrogate-Assisted Genetic Recommender Systems
We propose a new approach for building recommender systems by adapting surrogate-assisted interactive genetic algorithms. A pool of user-evaluated items is used to construct an approximative model which serves as a surro…
BenchmarkingEvolutionary AlgorithmsRecommendation SystemsSurrogate Assisted Evolutionary Multi-objective Optimisation applied to a Pressure Swing Adsorption system
Chemical plant design and optimisation have proven challenging due to the complexity of these real-world systems. The resulting complexity translates into high computational costs for these systems' mathematical formulat…
BIG-bench Machine LearningComputational EfficiencyEvolutionary AlgorithmsExploring the effectiveness of surrogate-assisted evolutionary algorithms on the batch processing problem
Real-world optimisation problems typically have objective functions which cannot be expressed analytically. These optimisation problems are evaluated through expensive physical experiments or simulations. Cheap approxima…
Evolutionary AlgorithmsSurrogate-Assisted Evolution for Efficient Multi-branch Connection Design in Deep Neural Networks
State-of-the-art Deep Neural Networks (DNNs) often incorporate multi-branch connections, enabling multi-scale feature extraction and enhancing the capture of diverse features. This design improves network capacity and ge…
Evolutionary Algorithms