Surrogate-Assisted Genetic Algorithm for Wrapper Feature Selection

• URL: http://arxiv.org/abs/2111.09074v1
• Date: Wed, 17 Nov 2021 12:33:18 GMT
• Title: Surrogate-Assisted Genetic Algorithm for Wrapper Feature Selection
• Authors: Mohammed Ghaith Altarabichi, S{\l}awomir Nowaczyk, Sepideh Pashami and Peyman Sheikholharam Mashhad
• Abstract summary: We propose a novel multi-stage feature selection framework utilizing multiple levels of approximations, or surrogates. Our experiments show that SAGA can arrive at near-optimal solutions three times faster than a wrapper GA, on average.
• Score: 4.89253144446913
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Fast Genetic Algorithm for feature selection -- A qualitative approximation approach [5.279268784803583]
  We propose a two-stage surrogate-assisted evolutionary approach to address the computational issues arising from using Genetic Algorithm (GA) for feature selection. We show that CHCQX converges faster to feature subset solutions of significantly higher accuracy, particularly for large datasets with over 100K instances.
  arXiv  Detail & Related papers  (2024-04-05T10:15:24Z)
• GE-AdvGAN: Improving the transferability of adversarial samples by gradient editing-based adversarial generative model [69.71629949747884]
  Adversarial generative models, such as Generative Adversarial Networks (GANs), are widely applied for generating various types of data. In this work, we propose a novel algorithm named GE-AdvGAN to enhance the transferability of adversarial samples.
  arXiv  Detail & Related papers  (2024-01-11T16:43:16Z)
• Genetic Engineering Algorithm (GEA): An Efficient Metaheuristic Algorithm for Solving Combinatorial Optimization Problems [1.8434042562191815]
  Genetic Algorithms (GAs) are known for their efficiency in solving optimization problems. This paper proposes a new metaheuristic algorithm called the Genetic Engineering Algorithm (GEA) that draws inspiration from genetic engineering concepts.
  arXiv  Detail & Related papers  (2023-09-28T13:05:30Z)
• The FAIRy Tale of Genetic Algorithms [1.0957528713294875]
  We have extended Findable, Accessible, Interoperable and Reusable (FAIR) data principles to enable Genetic and reusability of algorithms. We have presented an overview of methodological developments and variants of GA that makes it challenging to reproduce or even find the right source. This work can be extended to numerous machine learning algorithms/methods.
  arXiv  Detail & Related papers  (2023-04-29T11:36:09Z)
• Massively Parallel Genetic Optimization through Asynchronous Propagation of Populations [50.591267188664666]
  Propulate is an evolutionary optimization algorithm and software package for global optimization. We provide an MPI-based implementation of our algorithm, which features variants of selection, mutation, crossover, and migration. We find that Propulate is up to three orders of magnitude faster without sacrificing solution accuracy.
  arXiv  Detail & Related papers  (2023-01-20T18:17:34Z)
• Exploring the effectiveness of surrogate-assisted evolutionary algorithms on the batch processing problem [0.0]
  This paper introduces a simulation of a well-known batch processing problem in the literature. Evolutionary algorithms such as Genetic Algorithm (GA), Differential Evolution (DE) are used to find the optimal schedule for the simulation. We then compare the quality of solutions obtained by the surrogate-assisted versions of the algorithms against the baseline algorithms.
  arXiv  Detail & Related papers  (2022-10-31T09:00:39Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  In online algorithm selection (OAS), instances of an algorithmic problem class are presented to an agent one after another, and the agent has to quickly select a presumably best algorithm from a fixed set of candidate algorithms. For decision problems such as satisfiability (SAT), quality typically refers to the algorithm's runtime. In this work, we revisit multi-armed bandit algorithms for OAS and discuss their capability of dealing with the problem. We adapt them towards runtime-oriented losses, allowing for partially censored data while keeping a space- and time-complexity independent of the time horizon.
  arXiv  Detail & Related papers  (2021-09-13T18:10:52Z)
• AdaLead: A simple and robust adaptive greedy search algorithm for sequence design [55.41644538483948]
  We develop an easy-to-directed, scalable, and robust evolutionary greedy algorithm (AdaLead) AdaLead is a remarkably strong benchmark that out-competes more complex state of the art approaches in a variety of biologically motivated sequence design challenges.
  arXiv  Detail & Related papers  (2020-10-05T16:40:38Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• Balancing Rates and Variance via Adaptive Batch-Size for Stochastic Optimization Problems [120.21685755278509]
  In this work, we seek to balance the fact that attenuating step-size is required for exact convergence with the fact that constant step-size learns faster in time up to an error. Rather than fixing the minibatch the step-size at the outset, we propose to allow parameters to evolve adaptively.
  arXiv  Detail & Related papers  (2020-07-02T16:02:02Z)
• Devolutionary genetic algorithms with application to the minimum labeling Steiner tree problem [0.0]
  This paper characterizes and discusses devolutionary genetic algorithms and evaluates their performances in solving the minimum labeling Steiner tree (MLST) problem. We define devolutionary algorithms as the process of reaching a feasible solution by devolving a population of super-optimal unfeasible solutions over time. We show how classical evolutionary concepts, such as crossing, mutation and fitness can be adapted to aim at reaching an optimal or close-to-optimal solution.
  arXiv  Detail & Related papers  (2020-04-18T13:27:28Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.