Biased Random-key Genetic Algorithm with Q-Learning for Constrained Clustering

This paper presents a technique to solve the Constrained Clustering Problem, a semi-supervised problem that uses external specialist knowledge to guide clustering. Several algorithms were proposed in the literature to solve this problem, but their results may differ in terms of quality. A recent paper introduced an integer linear programming model based on k-medoids that consider consensus information while clustering. Their results showed how this information could improve clustering quality. This model, however, is time-consuming in some datasets. This paper describes how a Biased Random-key Genetic Algorithm with Q-Learning (BRKGA-QL) metaheuristic was adapted to use such ideas. The experiments evaluated the quality of the solutions and computational time obtained by BRKGA-QL and the integer linear programming model in 25 datasets from the literature. The experimental results show that the BRKGA-QL was able to reduce computational burden while maintaining solution quality