The quantum-inspired evolutionary algorithm (QEA) and QEA with a pair-swap strategy (QEAPS), where each gene is represented by a quantum bit (qubit) in both algorithms, have shown superior search performance to the classical genetic algorithm in the 0-1 knapsack problem. Also, from experimental results for the integer knapsack problem, a novel integer-type gene-coding method that can obtain an integer value as an observation result by assigning multiple qubits in a gene locus has shown superior search performance to the conventional binary-type gene-coding method. However, the integer-type gene-coding method cannot deal with permutations simply. Therefore, we have proposed two interpretation methods that can deal with permutations in order to expand the gene-coding method based on the qubit representation. From the results of a computer experiment using the proposed interpretation methods in the traveling salesman problem, we have clarified that the two proposed interpretation methods can search for the optimal solution, even with the gene-coding method based on the qubit representation. Moreover, there are suitable rotation angles for discovering the optimal solution that depend on the algorithm.
The quantum-inspired evolutionary algorithm (QEA) and QEA with a pair-swap strategy (QEAPS), where each gene is represented by a quantum bit (qubit) in both algorithms, have shown superior search performance to the classical genetic algorithm in the 0-1 knapsack problem. Also, from experimental results for the integer knapsack problem, a novel integer-type gene-coding method that can obtain an integer value as an observation result by assigning multiple qubits in a gene locus has shown superior search performance to the conventional binary-type gene-coding method. However, the integer-type gene-coding method cannot deal with permutations simply. Therefore, we have proposed two interpretation methods that can deal with permutations in order to expand the gene-coding method based on the qubit representation. From the results of a computer experiment using the proposed interpretation methods in the traveling salesman problem, we have clarified that the two proposed interpretation methods can search for the optimal solution, even with the gene-coding method based on the qubit representation. Moreover, there are suitable rotation angles for discovering the optimal solution that depend on the algorithm.
The quantum-inspired evolutionary algorithm (QEA) is one of the evolutionary algorithms incorporating principles of quantum computation. In QEA, each gene is represented by a quantum bit (qubit), and the quantum superposition state is imitated. QEA can effectively shift from a global search to a local search. Han, et al. showed that QEA has superior search performance to a genetic algorithm (GA) in the 0-1 knapsack problem (0-1KP). Nakayama, et al. proposed a simpler algorithm that is referred to as QEA based on pair swap (QEAPS). QEAPS requires fewer parameters to be adjusted than QEA. Nakayama, et al. showed that QEAPS can find similar or even better quality solutions than QEA in 0-1KP. However, in QEA and QEAPS, each gene is represented by a qubit and both algorithms can only use a binary value as an observation result for a qubit. Therefore, Iimura, et al. proposed a novel integer-type gene-coding method that can obtain an integer value as an observation result by assigning multiple qubits in a gene locus. Moreover, they implemented the gene-coding method in both QEA and QEAPS and showed that it can search for similar or even better quality solutions in a shorter time than a conventional binary-type gene-coding method in the integer knapsack problem (IKP). However, the integer-type gene-coding method cannot deal with permutations simply.In order to expand the gene-coding method based on the qubit representation, Moriyama, et al. proposed two interpretation methods based on the integer-type gene-coding method that can deal with permutations. Also, they clarified that the two proposed interpretation methods can search for the optimal solution, even with the genecoding method based on the qubit representation. This paper proposes a new gene-coding method that can deal with permutations. The proposed method promises effect of improving a solution in permutation space, like the k-Opt method, and can search for the optimal solution of the traveling salesman problem (TSP) effectively. From experimental results for TSP, the discovery rate of the optimal solution using the proposed method is higher than using conventional method in many cases of QEA and QEAPS.
In order to expand the conventional binary-type gene-coding method based on the quantum bit representation, we propose a novel gene-coding method that can represent an integer-type gene as multiple quantum bits, and clarify its characteristics from experimental analysis using three classes of the integer knapsack problem (IKP). In this paper, the proposed gene-coding method is called the integer-type gene-coding method with multiple quantum bits. From the experimental analysis of the IKP, we have confirmed that the proposed integer-type gene-coding method can discover a quasi-optimal solution in a shorter search time than the conventional binary-type gene-coding method in the quantum-inspired evolutionary algorithm (QEA) and the QEA with a pair-swap strategy (QEAPS) using genes represented by quantum bits. Actually, a quasi-optimal solution that is not a strict optimal solution is practical enough for many real social problems. Furthermore, we have confirmed that the gene-coding method suitable for discovering the strict optimal solution in the IKP depends on the algorithm used, namely, the integer type is suitable for the QEA and the binary type is suitable for the QEAPS.
Quantum-Inspired Evolutionary Algorithm (QEA), a type of stochastic algorithm for solving combinatorial optimization problems, is evolutionary computation using quantum bits and superposition states in quantum computation. Although coarse-grained parallel, QEA has many parameters that must be adjusted manually. The simpler algorithm, Quantum-inspired Evolutionary Computation with Pair Swap operator (QEAPS), the authors propose involves just one population and a simple genetic operation exchanging best solution information between two individuals chosen randomly, instead of the migration operation used in QEA, and thereby fewer parameters to be adjusted. The authors found in experiments that QEAPS finds highly qualified solutions, is more robust against constraint handling, and has a higher search performance of thanks to diversified best solution information.
The quantum-inspired evolutionary algorithm (QEA) and QEA with a pair-swap strategy (QEAPS), where each gene is represented by a quantum bit (qubit) and the qubit is updated by a unitary transformation in both algorithms. QEA and QEAPS can automatically shift the evolution from a global search to a local search and have shown superior search performance to the classical genetic algorithm. However, the population gets into a locally optimal solution and the solution search stagnates when the probability amplitudes of qubit excessively converge to |0› or |1›. In this study, we have proposed a measure that can confirm convergence state of qubits. From the results of the computational experiment in the maximum cut problem, we have clarified that the proposed measure can estimate the state of the qubit, and the quality of the obtained solution is improved by applying the method for maintenance of diversity.
The quantum-inspired evolutionary algorithm (QEA) and QEA with a pair-swap strategy (QEAPS), where each gene is represented by a quantum bit (qubit) and the qubit is updated by a unitary transformation in both algorithms. QEA and QEAPS can automatically shift the evolution from a global search to a local search and have shown superior search performance to the classical genetic algorithm. However, the population gets into a locally optimal solution and the solution search stagnates when the probability amplitudes of qubit excessively converge to |0› or |1›. In this study, we have proposed a measure that can confirm convergence state of qubits. From the results of the computational experiment in the maximum cut problem, we have clarified that the proposed measure can estimate the state of the qubit, and the quality of the obtained solution is improved by applying the method for maintenance of diversity.
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.