A Metaheuristic Search Algorithm Based on Sampling and Clustering

Abstract

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.

Keywords

• Benchmarks
• heuristic methods
• Knapsack problem
• Montecarlo and clustering methods
• optimization