Maximum Clique Problem (MCP) is one of the most important NP-hard problems in the area of soft computing and it has many real world applications in numerous fields ranging from coding theory to the determination of the structure of a protein molecule. Different heuristic, Meta heuristic and hybrid solution approaches have been applied to obtain the solution. In this paper, we demonstrate a Quantum-inspired Evolutionary Algorithm (QEA) to solve MCP. We have used one dimensional arrays of Q-bits called Q-bit individuals to produce binary individuals. After production of binary individuals, we have repaired and improved them. Here, Q-gate is the main variation operator applied on Q-bit individuals. Our algorithm was tested on DIMACS benchmark graphs and 40 of them were tested. The results obtained here are extremely encouraging. For almost all of the datasets, we get the optimal results reported on DIMACS benchmark and also compared our results with other related works. For some cases we get better results than other works.
Maximum Clique Problem (MCP) is one of the most important NP-hard problems in the area of soft computing and it has many real world applications in numerous fields ranging from coding theory to the determination of the structure of a protein molecule. Different heuristic, Meta heuristic and hybrid solution approaches have been applied to obtain the solution. In this paper, we demonstrate a Quantum-inspired Evolutionary Algorithm (QEA) to solve MCP. We have used one dimensional arrays of Q-bits called Q-bit individuals to produce binary individuals. After production of binary individuals, we have repaired and improved them. Here, Q-gate is the main variation operator applied on Q-bit individuals. Our algorithm was tested on DIMACS benchmark graphs and 40 of them were tested. The results obtained here are extremely encouraging. For almost all of the datasets, we get the optimal results reported on DIMACS benchmark and also compared our results with other related works. For some cases we get better results than other works.
Graph Coloring Problem (GCP) bears an enormous significance to the researchers in the field of soft computing. In this paper, we demonstrate a Quantum-Inspired Evolutionary Algorithm (QEA) to solve GCP. We use two dimensional arrays of Q-bits called Q-bit individual to produce binary individual. Q-gate operation is applied as a variation operator on Q-bit individuals. In traditional evolutionary algorithm (EA) for GCP, k-coloring approach is used and the EA is run several times for decreasing value of k until lowest possible k is reached. In our QEA, we start with the number of colors equal to the theoretical upper bound of the chromatic number, which is maximum out-degree + 1, and during evolution some colors are made unused to reduce the number of color in each generation. As a result, solution is found in a single run. We test 36 datasets from DIMACS benchmark and compare the result with several recent works. For five datasets, our algorithm obtains better solution than other. Keywords—quantum-inspired evolutionary algorithm (QEA), graph coloring problem (GCP), combinatorial optimization, Qbit representation, Q-gate.
This paper proposes a novel evolutionary algorithm inspired by quantum computing, called a quantum-inspired evolutionary algorithm (QEA), which is based on the concept and principles of quantum computing, such as a quantum bit and superposition of states. Like other evolutionary algorithms, QEA is also characterized by the representation of the individual, evaluation function, and population dynamics. However, instead of binary, numeric, or symbolic representation, QEA uses a Q-bit, defined as the smallest unit of information, for the probabilistic representation and a Q-bit individual as a string of Q-bits. A Q-gate is introduced as a variation operator to drive the individuals toward better solutions. To demonstrate its effectiveness and applicability, experiments were carried out on the knapsack problem, which is a well-known combinatorial optimization problem. The results show that QEA performs well, even with a small population, without premature convergence as compared to the conventional genetic algorithm.
Abstract The maximum clique problem (MCP) is to find the largest complete subgraph in an undirected graph, that is, the subgraph in which there are edges between every two different vertices. It is an NP-Hard problem with wide applications, including bioinformatics, social networks, data mining, and other fields. This paper proposes an enhanced quantum solution method that introduces a pre-detection phase based on a hybrid heuristic algorithm and a vertex pruning strategy, encoding the prior constraints on clique size into quantum registers as global information. It encodes the prior constraints on clique size into quantum registers as global information. In contrast, state-of-the-art Grover-based methods for n-vertex graphs require O ( n 2 n ) iterations and O ( n ) measurements. By leveraging a global information encoding mechanism, the proposed method compresses the number of iterations to O ( 2 n ) and only needs a constant number of measurements to identify all maximum cliques. We validate algorithmic correctness through simulations on IBM’s Qiskit platform and benchmark qubit/gate efficiency against existing Grover-based MCP solvers.
Quantum-inspired evolutionary algorithms (QIEAs), as a subset of evolutionary computation, are based on the principles of quantum computing such as quantum bits and quantum superposition. In this paper, we propose a multi-start quantum-inspired evolutionary algorithm, called MSQIEA. To improve the performance of the algorithm, a multi-measurement operator and a new strategy for updating the rotation angle is proposed. When Q-bit individuals start to converge to their final states, the best solution is stored and all Q-bits in each Q-bit individual are reinitialized. We compare the effectiveness of MSQIEA with a popular quantum-inspired evolutionary algorithm, called QEA, for solving 0-1 knapsack problem. The experimental results show that MSQIEA outperforms QEA and finds a solution with higher profit.
In this paper, we propose a novel quantum-inspired evolutionary algorithm, called NQEA, for solving combinatorial optimization problems. NQEA uses a new Q-bit update operator to increase the balance between the exploration and exploitation of the search space. In the operator, first, the Q-bits of each individual in the population are updated based on the personal best measurement of that individual and the best measurement of current generation. Then, a restriction is applied to each Q-bit to prevent the premature convergence of its values. The results of experiments on the 0-1 knapsack and NK-landscapes problems show that NQEA performs better than a classical genetic algorithm, CGA, and two quantum-inspired evolutionary algorithms, QEA and vQEA, in terms of convergence speed and accuracy.
From recent research on combinatorial optimization of the knapsack problem, quantum-inspired evolutionary algorithm (QEA) was proved to be better than conventional genetic algorithms. To improve the performance of the QEA, this paper proposes research issues on QEA such as a termination criterion, a Q-gate, and a two-phase scheme, for a class of numerical and combinatorial optimization problems. A new termination criterion is proposed which gives a clearer meaning on the convergence of Q-bit individuals. A novel variation operator H/sub /spl epsi// gate, which is a modified version of the rotation gate, is proposed along with a two-phase QEA scheme based on the analysis of the effect of changing the initial conditions of Q-bits of the Q-bit individual in the first phase. To demonstrate the effectiveness and applicability of the updated QEA, several experiments are carried out on a class of numerical and combinatorial optimization problems. The results show that the updated QEA makes QEA more powerful than the previous QEA in terms of convergence speed, fitness, and robustness.