Quantum-Inspired Genetic Algorithm for Resource-Constrained Project-Scheduling

Abstract

The Resource-Constrained Project-Scheduling Problem (RCPSP) is an NP-hard problem which can be found in many research domains. The optimal solution of the RCPSP problems requires a balance between exploration/exploitation and diversification/intensification. With this in mind, quantum-inspired evolutionary algorithms' ability to improve the population and quality of solutions, this work investigates the performance of a quantum-inspired genetic algorithm (QIGA), which has been adapted to work with RCPSPs. The proposed QIGA possesses the same structure as classical genetic algorithms, but the initial and updated populations are implemented using quantum gates and quantum superposition, bearing in mind the adaptation of such operators to fit with discrete problems. This work aims to solve RCPSPs using the QIGA to investigate the influence of the various quantum parameters in the proposed algorithm, such as the quantum population size, different options for the quantum gates and re-combination to use in the QIGA. The well-known PSPLIB benchmark instances of J30, J60 and J120 activities are used to test the effectiveness and performance of the proposed QIGA. It is apparent from the results that quantum mutation, quantum crossover and representation of quantum superposition using quantum gates enhances population diversity. The QIGA is also found to outperform many other evolutionary algorithms.

Keywords

• Quantum-inspired evolutionary algorithm
• resource-constrained project-scheduling problems
• NP-hard problems
• genetic algorithm
• quantum gates
• quantum superposition