An Investigation into the Application of Iterated-Local-Search for Combinatorial Optimisation

My Final-Year-Project[1] investigated whether Iterated Local Search[2] (ILS) is better or worse than Random Mutation Hill Climbing (RMHC) at attempting to solve the combinatorial optimisation problem known as the Modularisation Problem[3]. The ability to reverse-engineer the underlying structure of software systems through graph-based clustering can enable engineers to understand the relationships evident within the source code of large systems. Monitoring the structure and internal relationships of a software system overtime can provide pivotal information for project management with indirect implications on maintenance and development teams. Despite the benefits of such research, the complexity of a software system can exponentially increase based on factors such as added features or whether a system is open-sourced. To investigate this problem, a framework was developed based on Munch[4] in which a software system diagram known as a Module Dependency Graph (MDG) is provided to both an ILS and RMHC algorithm. Our preliminary experiments consisted of 16 software systems. The results of these experiments proved that ILS was more reliable and accurate compared to the current state of the art techniques.