1 November 2020 in IEEE Latin America Transactions
Heuristics denote a powerful concept, covering a wide range of computational, economic, and psychological sciences, as the ability to handle challenging problems with minimal resources. From a computational perspective, heuristics are commonly used in decision making - when vast amounts of information are available in complex environments - or even when dealing with intractable problems. Through shortcuts and tricks, they can produce acceptable solutions even with few resources compared to exhaustive approaches. Although found on many practical applications, their rich interdisciplinary history is not commonly explored in literature. This paper presents a recent and comprehensive literature review on the topic of heuristics. We present historical data that emphasizing the growth of this concept in several research fields, since the 1950s, and the authors' perspective on future directions. This history is told with a timeline as background, highlighting from the bounded rationality to computational intractability.
1 July 2022 in RAIRO - Operations Research
This paper presents a biased random-key genetic algorithm for k-medoids clustering problem. A novel heuristic operator was implemented and combined with a parallelized local search procedure. Experiments were carried out with fifty literature data sets with small, medium, and large sizes, considering several numbers of clusters, showed that the proposed algorithm outperformed eight other algorithms, for example, the classics PAM and CLARA algorithms. Furthermore, with the results of a linear integer programming formulation, we found that our algorithm obtained the global optimal solutions for most cases and, despite its stochastic nature, presented stability in terms of quality of the solutions obtained and the number of generations required to produce such solutions. In addition, considering the solutions (clusterings) produced by the algorithms, a relative validation index (average silhouette) was applied, where, again, was observed that our method performed well, producing cluster with a good structure.
25 January 2017 in Communications in Statistics - Simulation and Computation
A new optimization algorithm is presented to solve the stratification problem. Assuming the number L of strata and the total sample size n are fixed, we obtain strata boundaries by using an objective function associated with the variance. In this problem, strata boundaries must be determined so that the elements in each stratum are more homogeneous among themselves. To produce more homogeneous strata, this paper proposes a new algorithm that uses the Greedy Randomized Adaptive Search Procedure (GRASP) methodology. Computational results are presented for a set of problems, with the application of the new algorithm and some algorithms from literature.
3 February 2020 in Communications in Statistics - Simulation and Computation
Over the last decades, many researchers have studied and proposed new methods for the solution of the multivariate optimal allocation problem, which can be performed by choosing one of the following goals: (i) minimizing the weighted combination of relative variances, considering the sample size fixed or (ii) minimizing the sample size in a way that the coefficients of variation are lower or equal to the previously fixed coefficients of variation. Taking each goal into account, the present article proposes two heuristic algorithms that were developed by studying the optimization technique called biased random key genetic algorithm. The computational experiments reported in the end of this work indicate that the proposed algorithms can be a good alternative for the solution of this problem, when compared with the two methods from literature.
26 January 2022 in IEEE Latin America Transactions
This paper proposes an algorithm based on VNS metaheuristcs for k-medoids clustering, which is a NP-hard optimization problem. The VNS algorithm was applied in fifty data bases (instances) with small, medium, and large sizes, considering the number of clusters between 2 and 7. The obtained results from these experiments show the effectiveness of this approach, comparing it with nine other related clustering algorithms and an optimization formulation. Furthermore, we found that our algorithm obtained the optimal solutions for the vast majority of the cases.
8 June 2021 in IEEE Latin America Transactions
This paper introduces two heuristic algorithms for the Maximum-Diameter Clustering Problem (MDCP), based on the Biased Random-Key Genetic Algorithm (BRKGA) and the Greedy Randomized Adaptive Search Procedure (GRASP) metaheuristics. This problem consists of finding k clusters that minimize the largest within-cluster distance (diameter) among all clusters. The MDCP is classified as NP-hard and presents increased difficulty when attempting to determine the optimal solution for any instance. The results obtained in the experiments using 50 well-known instances indicate a good performance of proposed heuristics, that outperformed both three algorithms and an integer programming model from the literature.