Skip to main content

Research Repository

Advanced Search

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

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

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


Authors

Hoang Lam Le

Ferrante Neri



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 Mar 29, 2024
Journal Swarm and Evolutionary Computation
Print ISSN 2210-6502
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

Files




You might also like



Downloadable Citations