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.
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.
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.
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.
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.
The graph colouring problem (GCP) is one of the most interesting, studied and difficult combinatorial optimisation problems. That is why, several approaches were developed for solving this problem, including exact approaches, heuristic approaches, metaheuristics and hybrid approaches. In this paper, we try to solve the graph colouring problem using a new approach based on the quantum inspired cuckoo search algorithm. The first contribution consists in defining an appropriate quantum representation based on qubit representation to represent the graph colouring solutions. The second contribution is the proposition of a novel measure operator based on the adjacency matrix. The third contribution involves the proposition of an adapted hybrid quantum mutation operation. To show the feasibility and the effectiveness of the algorithm, we have used the standard DIMACS benchmark, and the obtained results are very encouraging.
In this paper, a generalization of the original Quantum-Inspired Evolutionary Algorithm (QIEA): the Generalized Quantum-Inspired Evolutionary Algorithm (GQIEA) is proposed. Like QIEA, GQIEA is also based on the quantum computing principle of superposition of states, but extending it not only to be used for binary values {0, 1}, but for any finite set of values {1, n}. GQIEA, as any other quantum inspired evolutionary algorithm, defines an own quantum individual, an evaluation function and population operators. As in QIEA, GQIEA also defines a generalized Q-gate operator, which is a variation operator to drive the individuals toward better solutions. To demonstrate its effectiveness and applicability, the proposal will be applied to the Knapsack Problem (KP), a classic combinatorial optimization problem. Results show that GQIEA has a good performance even with a small population.
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.