Large Neighborhood Search applied to the Software Module Clustering problem

The Software Module Clustering problem seeks to distribute the modules comprising a software system into clusters to maximize cluster cohesion and minimize coupling between clusters. Metaheuristics based on local search have been successfully applied to find good solutions for this problem, outperforming more-complex, population-based heuristics. In this paper, we present a heuristic based on Large Neighborhood Search to address the Software Module Clustering problem. We also perform what is to our knowledge the largest experimental study addressing this problem to date, involving 124 instances of varying size and complexity and comparing our proposed algorithm to the heuristic that has found the best results for the problem so far. Our proposed algorithm outperformed the state-of-the-art heuristic on 93 out of 124 instances with 95% confidence level. We also report new upper bounds on the MQ value for 44 instances and evaluated the relative goodness of the solutions obtained by our proposed algorithm for 89 instances. Considering the 77 instances for which optimal solutions are proven, the proposed algorithm found the optimal solution for 30 instances (39%). Additionally, thirteen developers participate in a study focused on the distribution of the modules comprising a software project into clusters. We used JodaMoney as our study object and we compared the characteristics of the solutions generated by its authors, the best solution generated by LNS_SMC and the solution generated by each of the 13 subjects. LNS_SMC solution performs better than inexperienced subjects ones in issue resolution prediction but performs worse than the solutions proposed by experienced subjects and also the author's solution. For the prediction of concomitant changes, the LNS_SMC solution was outperformed by both subjects and authors solutions.