A Metaheuristic Search Algorithm based on Sampling and Clustering
Harita, Maria (Universitat Autònoma de Barcelona. Departament d'Arquitectura de Computadors i Sistemes Operatius)
Wong, Álvaro (Universitat Autònoma de Barcelona. Departament d'Arquitectura de Computadors i Sistemes Operatius)
Suppi Boldrito, Remo (Universitat Autònoma de Barcelona. Departament d'Arquitectura de Computadors i Sistemes Operatius)
Rexachs del Rosario, Dolores Isabel (Universitat Autònoma de Barcelona. Departament d'Arquitectura de Computadors i Sistemes Operatius)
Luque, Emilio (Universitat Autònoma de Barcelona. Departament d'Arquitectura de Computadors i Sistemes Operatius)

Data:	2024
Resum:	As optimization problems become more complicated and extensive, parameterization becomes complex, resulting in a difficult task requiring significant amounts of time and resources. In this paper we propose a heuristic search algorithm we call MCSA (Montecarlo-Clustering Search Algorithm), which is based on Montecarlo sampling, and a clustering strategy involving two techniques. Our objective is to apply MCSA, an inherently stochastic method, to address optimization problems. To assess its performance, we conducted an evaluation using classical benchmark optimization functions. Additionally, we leveraged the CEC2017 benchmark suite to comprehensively evaluate the algorithm, highlighting the pivotal role of the Exploration stage in our methodology. Subsequently, we extended our methodology to tackle a practical combinatorial problem, the Knapsack problem. This NP-Hard problem holds significant real-world applications in resource allocation, scheduling, planning, logistics, and more. Our contributions lie in parameterizing the Knapsack Problem to align with MCSA's parameters for reference indicators adjustment and achieving high-quality solutions, surpassing 90% in comparison to exhaustive methods such as branch and bound.
Ajuts:	Agencia Estatal de Investigación PID2020-112496GB-I00
Drets:	Aquest document està subjecte a una llicència d'ús Creative Commons. Es permet la reproducció total o parcial, la distribució, la comunicació pública de l'obra i la creació d'obres derivades, fins i tot amb finalitats comercials, sempre i quan es reconegui l'autoria de l'obra original.
Llengua:	Anglès
Document:	Article ; recerca ; Versió publicada
Matèria:	Benchmarks ; Heuristic Methods ; Knapsack Problem ; Montecarlo and Clustering Methods ; Optimization
Publicat a:	IEEE Access, Vol. 12 (January 2024) , p. 15493-15508, ISSN 2169-3536

DOI: 10.1109/access.2024.3354714

16 p, 3.0 MB

El registre apareix a les col·leccions:
Documents de recerca > Documents dels grups de recerca de la UAB > Centres i grups de recerca (producció científica) > Enginyeries > HPC4EAS (High Performance Computing for Efficient Applications and Simulation Research Group)
Articles > Articles de recerca
Articles > Articles publicats