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


Hoang Lam Le

Ferrante Neri


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.

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
Peer Reviewed Peer Reviewed
Volume 69
Article Number 100991
Keywords Memetic Algorithm; Pattern Search; Instance Reduction; Classification; Data Science; Ockham's Razor in Memetic Computing
Public URL
Publisher URL


You might also like

Downloadable Citations