An Analysis of a KNN Perturbation Operator: An Application to the Binarization of Continuous Metaheuristics
Open Access
- 24 January 2021
- journal article
- research article
- Published by MDPI AG in Mathematics
- Vol. 9 (3), 225
- https://doi.org/10.3390/math9030225
Abstract
The optimization methods and, in particular, metaheuristics must be constantly improved to reduce execution times, improve the results, and thus be able to address broader instances. In particular, addressing combinatorial optimization problems is critical in the areas of operational research and engineering. In this work, a perturbation operator is proposed which uses the k-nearest neighbors technique, and this is studied with the aim of improving the diversification and intensification properties of metaheuristic algorithms in their binary version. Random operators are designed to study the contribution of the perturbation operator. To verify the proposal, large instances of the well-known set covering problem are studied. Box plots, convergence charts, and the Wilcoxon statistical test are used to determine the operator contribution. Furthermore, a comparison is made using metaheuristic techniques that use general binarization mechanisms such as transfer functions or db-scan as binarization methods. The results obtained indicate that the KNN perturbation operator improves significantly the results.Keywords
Funding Information
- Fondo Nacional de Desarrollo Científico y Tecnológico (11180056)
This publication has 52 references indexed in Scilit:
- Krill herd: A new bio-inspired optimization algorithmCommunications in Nonlinear Science and Numerical Simulation, 2012
- Parameter tuning for configuring and analyzing evolutionary algorithmsSwarm and Evolutionary Computation, 2011
- Teaching–learning-based optimization: A novel method for constrained mechanical design optimization problemsComputer-Aided Design, 2011
- Discovering the suitability of optimisation algorithms by learning from evolved instancesAnnals of Mathematics and Artificial Intelligence, 2011
- GSA: A Gravitational Search AlgorithmInformation Sciences, 2009
- Globally Multimodal Problem Optimization Via an Estimation of Distribution Algorithm Based on Unsupervised Learning of Bayesian NetworksEvolutionary Computation, 2005
- A New Heuristic Optimization Algorithm: Harmony SearchSIMULATION, 2001
- A genetic algorithm for the set covering problemEuropean Journal of Operational Research, 1996
- An algorithm for set covering problemEuropean Journal of Operational Research, 1987
- Set Partitioning: A surveySIAM Review, 1976