Evaluation of a heuristic search algorithm based on sampling and clustering

Systems have evolved in such a way that today’s parallel systems are capable of offering high capacity and better performance. The design of approaches seeking for the best set of parameters in the context of a high-performance execution is fundamental. Although complex, heuristic methods are strategies that deal with high-dimensional optimization problems. We are proposing to enhance the evaluation method of a baseline heuristic that uses sampling and clustering techniques to optimize a complex, large and dynamic system. To carry out our proposal we selected the benchmark test functions and perform a density-based analysis along with k-means to cluster into feasible regions, discarding the non-relevant areas. With this, we aim to avoid getting trapped in local minima. Ultimately, the recursive execution of our methodology will guarantee to obtain the best value, thus, getting closer to method validation without forgetting the future lines, e.g. its distributed parallel implementation. Preliminary results turned out to be satisfactory, having obtained a solution quality above 99%.

Facultad de Informática