Quantum-Ready Genetic Algorithm with Novel Operators to Solve Combinatorial Optimization Problems
摘要
Real-world combinatorial optimization problems, characterized by their vast and discrete solution set, present significant challenges when solving large-scale problems. Nature of these problems are often NP-hard, where the search for optimal solutions becomes increasingly difficult due to the exponential growth of possible combinations. Therefore, finding an optimal solution with a reasonable computational investment gets harder as the problem gets more complex. Quantum-inspired evolutionary algorithms have gained significant attention over time and has been recognized as a very promising direction in the paradigm of optimization. Traditional quantum-inspired genetic algorithm (QiGA) face scalability issues, limited operator diversity, lack of quantum hardware integration, insufficient preprocessing, and parameter sensitivity, hindering performance and usability. To address these challenges, a novel quantum-inspired genetic algorithm that incorporates preprocessing, learning mechanism, and introduces new operators to navigate search space smartly is proposed. This approach is designed in a generalized manner, ensuring that it is quantum-ready which means it can be seamlessly deployed on quantum hardware once it becomes readily available. To showcase the efficacy and relevance of QiGA, a comparative analysis was conducted between popular combinatorial optimization problems like job scheduling and 0/1 knapsack and their real-world equivalents. The results show that QiGA performs well in terms of solution time, without premature convergence as compared to other conventional solvers. The proposed innovative framework represents a significant step forward in the integration of quantum computing principles with genetic algorithms.