Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Transactions of the Japanese Society for Artificial Intelligence

Permutation Optimization Using a Gene-Coding Method of Quantum Bit by Local Improvement like the k-Opt

Yoshifumi Moriyama, Ichiro Iimura, Tomotsugu Ohno, Shigeru Nakayama

Published Jan 1, 2016• 0 citations
Publisher

Abstract

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.

DOI
10.1527/tjsai.ai30-b

Related papers

An Experimental Study on Optimization in Permutation Spaces by Quantum-Inspired Evolutionary Algorithm Using Quantum Bit Representation

Yoshifumi Moriyama, Ichiro Iimura, Tomotsugu Ohno +1 more

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.

Journal of Signal Processing•Jan 1, 2015•4 citations

Integer-Type Gene-Coding Method Based on Quantum Bit Representation in Quantum-Inspired Evolutionary Algorithm: Application to Integer Knapsack Problem

Ichiro Iimura, Yoshifumi Moriyama, Shigeru Nakayama

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.

Journal of Signal Processing•Jan 1, 2012•3 citations

Experimental Study on Pair Swap Strategy in Quantum-Inspired Evolutionary Algorithm

Takahiro Imabeppu, Shigeru Nakayama, Satoshi Ono

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.

Journal of Advanced Computational Intelligence and Intelligent Informatics•Mar 20, 2009•2 citations

Quantum-inspired evolutionary algorithm for a class of combinatorial optimization

Kuk-Hyun Han, Jong-Hwan Kim

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.

IEEE Transactions on Evolutionary Computation•Dec 1, 2002•1,592 citations

Search performance analysis of qubit convergence measure for quantum-inspired evolutionary algorithm introducing on maximum cut problem

Yoshifumi Moriyama, Ichiro Iimura, Shigeru Nakayama

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.

International Journal of Computational Intelligence Studies•Jan 1, 2018•0 citations

Search performance analysis of qubit convergence measure for quantum-inspired evolutionary algorithm introducing on maximum cut problem

Shigeru Nakayama, Yoshifumi Moriyama, Ichiro Iimura

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.

International Journal of Computational Intelligence Studies•Jan 1, 2018•0 citations
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.
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.
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.
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.
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.