SPMS-ALS: A Single-Point Memetic structure with accelerated local search for instance reduction

Le, Hoang Lam; Neri, Ferrante; Triguero, Isaac

Abstract

Real-world optimisation problems pose domain specific challenges that often require an ad-hoc algorithmic design to be efficiently addressed. The present paper investigates the optimisation of a key stage in data mining, known as instance reduction, which aims to shrink the input data prior to applying a learning algorithm. Performing a smart selection or creation of a reduced number of samples that represent the original data may become a complex large-scale optimisation problem, characterised by a computationally expensive objective function, which has been often tackled by sophisticated population-based metaheuristics that suffer from a high runtime. Instead, by following the Ockham's Razor in Memetic Computing, we propose a Memetic Computing approach that we refer to as fast Single-Point Memetic Structure with Accelerated Local Search (SPMS-ALS). Using the k-nearest neighbours algorithm as base classifier, we first employ a simple local search for large-scale problems that exploits the search logic of Pattern Search, perturbing an n-dimensional vector along the directions identified by its design variables one by one. This point-by-point perturbation mechanism allows us to design a strategy to re-use most of the calculations previously made to compute the objective function of a candidate solution. The proposed Accelerated Local Search is integrated within a single-point memetic framework and coupled with a resampling mechanism and a crossover. A thorough experimental analysis shows that SPMS-ALS, despite its simplicity, displays an excellent performance which is as good as that of the state-of-the-art while reducing up to approximately 85% of the runtime with respect to any other algorithm that performs the same number of function calls.

Citation

Le, H. L., Neri, F., & Triguero, I. (2022). SPMS-ALS: A Single-Point Memetic structure with accelerated local search for instance reduction. Swarm and Evolutionary Computation, 69, Article 100991. https://doi.org/10.1016/j.swevo.2021.100991

• Journal Article Type: Article
• Acceptance Date: Sep 28, 2021
• Online Publication Date: Oct 4, 2021
• Publication Date: 2022-03
• Deposit Date: Sep 29, 2021
• Publicly Available Date: Oct 5, 2023
• Journal: Swarm and Evolutionary Computation
• Print ISSN: 2210-6502
• Electronic ISSN: 2210-6510
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 69
• Article Number: 100991
• DOI: https://doi.org/10.1016/j.swevo.2021.100991
• Keywords: Memetic Algorithm; Pattern Search; Instance Reduction; Classification; Data Science; Ockham's Razor in Memetic Computing
• Public URL: https://nottingham-repository.worktribe.com/output/6345925
• Publisher URL: https://www.sciencedirect.com/science/article/pii/S221065022100153X