Software module clustering using a hyper-heuristic based multi-objective genetic algorithm

This paper presents a Fast Multi-objective Hyper-heuristic Genetic Algorithm (MHypGA) for the solution of Multi-objective Software Module Clustering Problem. Multi-objective Software Module Clustering Problem is an important and challenging problem in Software Engineering whose main goal is to obtain a good modular structure of the Software System. Software Engineers greatly emphasize on good modular structure as it is easier to comprehend, develop and maintain such software systems. In recent times, the problem has been converted into a Search-based Software Engineering Problem with multiple objectives. This problem is NP hard as it is an instance of Graph Partitioning and hence cannot be solved using traditional optimization techniques. The MHypGA is a fast and effective metaheuristic search technique for suggesting software module clusters in a software system while maximizing cohesion and minimizing the coupling of the software modules. It incorporates twelve low-level heuristics which are based on different methods of selection, crossover and mutation operations of Genetic Algorithms. The selection mechanism to select a low-level heuristic is based on reinforcement learning with adaptive weights. The efficacy of the algorithm has been studied on six real-world module clustering problems reported in the literature and the comparison of the results prove the superiority of the MHypGA in terms of quality of solutions and computational time.

I. Introduction

Software maintenance is a crucial activity in the software development life cycle. Boehm [2] found through his research that the maintenance costs can be up to ten times those of an initial development and also Parikh and Zvegintzov [12] pointed out that it consumes 50% of all computer and human resources. Due to the increase in the complexity and size of the software systems, maintenance has become a challenging issue for software engineers. The situation becomes awful, when the software lacks proper documentation on the changes that are performed during system evolution. As a consequence, it becomes practically difficult to maintain the software in future. The replacement of such software with a new one is also not a feasible option, as it does not guarantee the full functionality. The practices such as reverse engineering and reengineering have emerged to handle such software systems. As the source code is the only exact replication of the system available to software developers and maintainers, the reverse engineering community is working towards the development of methods to extract the high-level structural information from the source code directly. Such methods are inclined to focus on design recovery through software clustering, program slicing, source code analysis etc.