Hill Climbing and simulated annealing in large scale next release problem

Next release problem is a software engineering problem, lately often solved using heuristic algorithms. It deals with selecting a subset of requirements that should appear in next release of a software product. The problem lies in satisfying various parts interested in project development with acceptable costs. This paper compares two rather simple, but often used and efficient heuristic algorithms: Hill Climbing and Simulated Annealing. The aim of this paper was to compare the performance of these algorithms and their modifications on a large scale problem. We investigated the differences between four variations of Hill Climbing and two variations of Simulated Annealing, while Random Search was used to verify the benefit of using a heuristic algorithm. The evaluation was performed in terms of finding the best solution for a given budget and in calculating the proportion of non-dominated solutions that form the joint Pareto-optimal front. Our research was done on publicly available realistic datasets that were obtained mining the bug repositories. The results indicate Simulated Annealing as the more successful algorithm but point out that Simulated Annealing together with Hill Climbing provides a more thorough insight into the problem search space.