A High Performance Algorithm for Solving Maximum Independent Set Problem

Software engineering plays an important role in computer science. Novel quantum algorithms can efficiently solve software-engineering problems. Not only software engineering but also many industries including logistics, finance, genomics, resource allocation, logistics, bioinformatics, mobile agents and more have optimization problems. Such problems may have long time solutions [15]. Research has been conducted to improve the performance of current solutions and to search for optimized solutions. Search-based software engineering (SBSE) uses computational techniques to determine optimized solutions in a large search space. There are SBSE problems such as Test Suite Minimization (TSM) and Maximum Independent Set (MIS) that require efficient solutions due to its important role. A quantum-inspired genetic algorithm had solved the TSM problem with higher performance than classical solutions [10]. The quantum-inspired genetic algorithm and quantum algorithm showed better performance results than classical solutions. This improvement motivated us to modify such algorithms in order to solve the MIS optimization problems [24, 25]. In addition, MIS has crucial applications in many domains. It can be applied in software engineering to separate related and unrelated requirements, which is of great support for project management. Resources, time, cost, and relevance can be updated accordingly. MIS can also be applied in network design, scheduling, resource allocation, logistics, bioinformatics, mobile agents, and more [17]. Quantum-inspired genetic algorithm combines quantum mechanics concepts and genetic algorithms which enhances search capability and provides efficient search mechanism [19]. In this study, a modified quantum-inspired genetic algorithm (QIGA) is proposed and implemented to find an optimized solution for the MIS problem. A classical genetic algorithm (GA) is implemented and has been tested. A Comparison is conducted to show the results of QIGA and GA to measure the performance improvement. Results and its analysis are displayed to show QIGA and GA convergence. The proposed algorithm has no prior assumptions.