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.
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 from a global search to a local search and have shown superior search performance to the classical genetic algorithm. However, it is important to appropriately manage the convergence speed of qubits. In this study, we have proposed a measure that can confirm convergence state of qubits, and applied the measure to a method for keeping diversity. From the results of the computational experiment in the maximum cut problem, we have clarified that the proposed measure can confirm the state of the qubit, and the discovery rate of the optimal solution improves with to apply the method for maintenance of diversity.
The quantum-inspired evolutionary algorithm (QEA) and QEA with a pair-swap strategy (QEAPS) have quantum-inspired individuals, where each gene is represented by a quantum bit (qubit). QEA and QEAPS iterate the evolution using the unitary transformation of probability amplitudes in each qubit, and can automatically shift the evolution from a global search to a local search. Here, the convergence speed depends on the rotation angle of each qubit toward either the |0〉 or |1〉 state vector, and the probability amplitude diverges or the population is likely to fall into a local solution if the rotation angle is too large. If the rotation angle is too small, the convergence speed may become low and the search performance will degrade. In this study, we introduce nonuniform convergence speeds into the quantum-inspired individuals and regard the convergence speed as the individual feature (individuality) of each quantum-inspired individual. Introducing the proposed individuality can eliminate the cumbersome process required to design a rotation angle while ensuring the quality of the obtained solution.
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.
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) 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.