An improved quantum-inspired evolutionary algorithm framework implemented to solve minimum vertex cover problem

doi:10.1007/s00158-025-04078-9

An improved quantum-inspired evolutionary algorithm framework implemented to solve minimum vertex cover problem

2025-08-04

0

PRE

AI

S

Sulabh Bansal

S

Shiladitya Bhattacharjee *

DOI：10.1007/s00158-025-04078-9

Original

Original request for help

Save

Abstract

En 中文

Combinatorial optimization addresses problems involving discrete functions and discrete variables. The solutions to these problems utilizing established precise deterministic algorithms suffer from exponential time complexity. Population-based metaheuristic strategies have gained popularity, necessitating customization to enhance their effectiveness in problem solving. Any of these can be used to derive viable answers for a range of such issues within an acceptable timeframe. Quantum-Inspired Evolutionary Algorithms (QIEAs) are the category of metaheuristic algorithms derived on principles of Quantum Computing. An enhanced framework for QIEA has been developed, incorporating several elements to facilitate the customization of QIEA for specific problems. A collection of attributes within the suggested framework utilizes problem-specific knowledge pertaining to a combinatorial optimization issue, while an additional set of attributes may enhance overall performance in a general context. The suggested framework has been applied to the Minimum Vertex Cover (MVC) problem, a well-known combinatorial optimization challenge recognized for its hardness in being solved by any accurate technique. Several established criteria for MVC have been used to develop the features of the proposed framework. The efficacy of the proposed framework has been validated by comparing its results with those of the fundamental QIEA and other enhanced iterations of the framework. Comparison of the performance of algorithms based on the average time taken to obtain the best possible MVC value for benchmark instances from well-known datasets of BHOSLIB and DIMACS is performed. The performance of the proposed framework has surpassed that of several previous heuristic and metaheuristic algorithms.

Keywords:

Exponential time complexity

Heuristic and metaheuristic algorithms

Quantum-Inspired Evolutionary Algorithms

Minimum Vertex Cover Problem

An improved quantum-inspired evolutionary algorithm framework implemented to solve minimum vertex cover problem

Abstract

Journal

Organization

Cited Papers