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

IEEE Access

A Binary Multi-Scale Quantum Harmonic Oscillator Algorithm for 0–1 Knapsack Problem With Genetic Operator

Yan Huang, Peng Wang, Jianping Li, Xiuhong Chen, Tao Li

Published Jan 1, 2019• 14 citations
Publisher

Abstract

The 0-1 knapsack problem is a typical discrete combinatorial optimization problem with numerous applications. In this paper, a binary multi-scale quantum harmonic oscillator algorithm (BMQHOA) with genetic operator is proposed for solving 0-1 knapsack problem. The framework of BMQHOA is consisted of three nested phases including energy level stablization, energy level decline and scale adjustment. In BMQHOA, the number of different bits between solutions is defined as the distance between solutions to map the continuous search space into the discrete search space. Repair operator with greedy strategy is adopted in BMQHOA to guarantee the knapsack capacity constraint. The current best solution is used to perform a random mutation with the origin solutions, making solutions evolve towards the current optimal solution. The performance of BMQHOA is evaluated on two low-dimensional and three high-dimensional KP01 data sets, and computational results are compared with several state-of-art 0-1 knapsack algorithms. Experimental results demonstrate that the proposed BMQHOA can get the best solutions of most knapsack data sets, and performs well on convergence and stability.

DOI
10.1109/access.2019.2942340

Related papers

Adaptive Multi-scale Quantum Harmonic Oscillator Algorithm Based on Evolutionary Strategy

Xinggui Ye, Peng Wang

This paper proposes a novel adaptive multi-scale quantum harmonic oscillator algorithm based on evolutionary strategies (AMQHOA-ES) for global numerical optimization. Since the original Multi-scale Quantum Harmonic Oscillator Algorithm (MQHOA) utilizes a fixed contraction factor to narrow the search scale, the searching step decreases too fast at the later stage of the evolution and is more likely to suffer premature convergence and stagnation. To improve the convergence performance, an adaptive attenuation mechanism of scaling is proposed to dynamically adjust the exploration and exploitation properties. Evolutionary strategies such as selection, crossover and DE/rand/1 mutation are implemented in the proposed algorithm to enhance the exploration and exploitation abilities. Experimental results evaluated on several unimodal and multimodal benchmark functions indicate the significant improvement of the proposed algorithm to the original MQHOA. Meanwhile, the experimental results compared with several state-of-the-art optimizers show the superiority or competitiveness of the proposed algorithm.

IEEE Congress on Evolutionary Computation (CEC)•Jul 1, 2020•3 citations

Multi-Scale Quantum Harmonic Oscillator for High-Dimensional Function Global Optimization Algorithm

Wang Pen

With the multi-scale binary sampling methods on the basis of Gaussian scaling function,the model of multi-scale quantum harmonic oscillator algorithm for high-dimensional function global optimization problems is proposed.High-dimensional function optimization process is divided into two steps,scale convergence and quantum harmonic oscillator convergence.This algorithm model is based on the same convergence process probability interpretations between function optimization problem and quantum harmonic oscillator from high-energy state to ground state.This algorithm,which has explicit physical model,can realize highdimensional function optimization without coding or complex initial conditions.Experiments and analysis are done for 15 typical two-dimensional optimized test functions and 6 typical high-dimensional optimized test functions.The results show that multi-scale quantum harmonic oscillator algorithm gets precise global optimum for high-dimensional function quickly,and withreduced frequencyapproach,the search speed of function withhigh frequency component improves significantly.

Dianzi xuebao•Jan 1, 2013•17 citations

An improved quantum genetic algorithm with mutation and its application to 0-1 knapsack problem

Rui Wang, Ning Guo, Fenghong Xiang +1 more

An improved quantum genetic algorithm (IQGA) is proposed in this paper, which codes the chromosome with probability amplitudes represented by sine and cosine functions, and uses an adaptive strategy of the rotation angle to update the population. Then the mutation operation is considered in this improved quantum genetic algorithm (MIQGA). Rapid convergence and good global search capability characterize the performance of MIQGA. While testing, a variance function is introduced to estimate the stability of the algorithm. When solving 0-1 knapsack problem, greedy repair function is used to repair unfeasible solutions. Experimental results show MIQGA has better comprehensive performance than traditional genetic algorithm (GA), standard quantum genetic algorithm (QGA) and IQGA, especially the superiority in terms of optimization quality and population diversity.

International Conference on Measurement, Information and Control•May 1, 2012•4 citations

Multi-Scale Quantum Harmonic Oscillator Algorithm With Truncated Mean Stabilization Strategy for Global Numerical Optimization Problems

Xinggui Ye, Peng Wang, Gang Xin +2 more

A multi-scale quantum harmonic oscillator algorithm (MQHOA) is a quantum population-based algorithm proposed recently. It utilizes the quantum wave function to locate the global optimum of a global numerical optimization problem. As the MQHOA employs the elitism to replace the worst particle in each iteration cycle, it reduces one of the particles in each run, which will cripple the diversity of the population and slow down the convergence speed. Therefore, the particles will be easily trapped into local optima. In this paper, we suggest a new MQHOA with truncated mean stabilization (TS-MQHOA) policy to alleviate the above-mentioned problems. The theoretical and experimental analyses indicate that the truncated mean stabilization strategy helps to diversify the populations and improve the convergence efficiency. The proposed TS-MQHOA is evaluated on a number of dimension-wise unimodal and multimodal CEC benchmark functions, and the computational results are compared with several popular population-based algorithms. The experimental results on complex test problems demonstrate that the proposed TS-MQHOA, in most function evaluations, is able to obtain better convergence toward the global optimum compared with several renowned heuristic algorithms based on swarm intelligence. Meanwhile, the comparative results reveal the competitiveness and superiority of the proposed algorithm, especially on high-dimensional function evaluations.

IEEE Access•Jan 1, 2019•11 citations

Genetic quantum algorithm and its application to combinatorial optimization problem

Kuk-Hyun Han, Jong-Hwan Kim

This paper proposes a novel evolutionary computing method called a genetic quantum algorithm (GQA). GQA is based on the concept and principles of quantum computing such as qubits and superposition of states. Instead of binary, numeric, or symbolic representation, by adopting qubit chromosome as a representation GQA can represent a linear superposition of solutions due to its probabilistic representation. As genetic operators, quantum gates are employed for the search of the best solution. Rapid convergence and good global search capability characterize the performance of GQA. The effectiveness and the applicability of GQA are demonstrated by experimental results on the knapsack problem, which is a well-known combinatorial optimization problem. The results show that GQA is superior to other genetic algorithms using penalty functions, repair methods and decoders.

IEEE Congress on Evolutionary Computation (CEC)•Nov 7, 2002•672 citations

A multi-start quantum-inspired evolutionary algorithm for solving combinatorial optimization problems

Parvaz Mahdabi, Saeed Jalili, Mahdi Abadi

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.

Genetic and Evolutionary Computation Conference (GECCO)•Jul 12, 2008•16 citations
The 0-1 knapsack problem is a typical discrete combinatorial optimization problem with numerous applications. In this paper, a binary multi-scale quantum harmonic oscillator algorithm (BMQHOA) with genetic operator is proposed for solving 0-1 knapsack problem. The framework of BMQHOA is consisted of three nested phases including energy level stablization, energy level decline and scale adjustment. In BMQHOA, the number of different bits between solutions is defined as the distance between solutions to map the continuous search space into the discrete search space. Repair operator with greedy strategy is adopted in BMQHOA to guarantee the knapsack capacity constraint. The current best solution is used to perform a random mutation with the origin solutions, making solutions evolve towards the current optimal solution. The performance of BMQHOA is evaluated on two low-dimensional and three high-dimensional KP01 data sets, and computational results are compared with several state-of-art 0-1 knapsack algorithms. Experimental results demonstrate that the proposed BMQHOA can get the best solutions of most knapsack data sets, and performs well on convergence and stability.
This paper proposes a novel adaptive multi-scale quantum harmonic oscillator algorithm based on evolutionary strategies (AMQHOA-ES) for global numerical optimization. Since the original Multi-scale Quantum Harmonic Oscillator Algorithm (MQHOA) utilizes a fixed contraction factor to narrow the search scale, the searching step decreases too fast at the later stage of the evolution and is more likely to suffer premature convergence and stagnation. To improve the convergence performance, an adaptive attenuation mechanism of scaling is proposed to dynamically adjust the exploration and exploitation properties. Evolutionary strategies such as selection, crossover and DE/rand/1 mutation are implemented in the proposed algorithm to enhance the exploration and exploitation abilities. Experimental results evaluated on several unimodal and multimodal benchmark functions indicate the significant improvement of the proposed algorithm to the original MQHOA. Meanwhile, the experimental results compared with several state-of-the-art optimizers show the superiority or competitiveness of the proposed algorithm.
With the multi-scale binary sampling methods on the basis of Gaussian scaling function,the model of multi-scale quantum harmonic oscillator algorithm for high-dimensional function global optimization problems is proposed.High-dimensional function optimization process is divided into two steps,scale convergence and quantum harmonic oscillator convergence.This algorithm model is based on the same convergence process probability interpretations between function optimization problem and quantum harmonic oscillator from high-energy state to ground state.This algorithm,which has explicit physical model,can realize highdimensional function optimization without coding or complex initial conditions.Experiments and analysis are done for 15 typical two-dimensional optimized test functions and 6 typical high-dimensional optimized test functions.The results show that multi-scale quantum harmonic oscillator algorithm gets precise global optimum for high-dimensional function quickly,and withreduced frequencyapproach,the search speed of function withhigh frequency component improves significantly.
An improved quantum genetic algorithm (IQGA) is proposed in this paper, which codes the chromosome with probability amplitudes represented by sine and cosine functions, and uses an adaptive strategy of the rotation angle to update the population. Then the mutation operation is considered in this improved quantum genetic algorithm (MIQGA). Rapid convergence and good global search capability characterize the performance of MIQGA. While testing, a variance function is introduced to estimate the stability of the algorithm. When solving 0-1 knapsack problem, greedy repair function is used to repair unfeasible solutions. Experimental results show MIQGA has better comprehensive performance than traditional genetic algorithm (GA), standard quantum genetic algorithm (QGA) and IQGA, especially the superiority in terms of optimization quality and population diversity.
A multi-scale quantum harmonic oscillator algorithm (MQHOA) is a quantum population-based algorithm proposed recently. It utilizes the quantum wave function to locate the global optimum of a global numerical optimization problem. As the MQHOA employs the elitism to replace the worst particle in each iteration cycle, it reduces one of the particles in each run, which will cripple the diversity of the population and slow down the convergence speed. Therefore, the particles will be easily trapped into local optima. In this paper, we suggest a new MQHOA with truncated mean stabilization (TS-MQHOA) policy to alleviate the above-mentioned problems. The theoretical and experimental analyses indicate that the truncated mean stabilization strategy helps to diversify the populations and improve the convergence efficiency. The proposed TS-MQHOA is evaluated on a number of dimension-wise unimodal and multimodal CEC benchmark functions, and the computational results are compared with several popular population-based algorithms. The experimental results on complex test problems demonstrate that the proposed TS-MQHOA, in most function evaluations, is able to obtain better convergence toward the global optimum compared with several renowned heuristic algorithms based on swarm intelligence. Meanwhile, the comparative results reveal the competitiveness and superiority of the proposed algorithm, especially on high-dimensional function evaluations.
This paper proposes a novel evolutionary computing method called a genetic quantum algorithm (GQA). GQA is based on the concept and principles of quantum computing such as qubits and superposition of states. Instead of binary, numeric, or symbolic representation, by adopting qubit chromosome as a representation GQA can represent a linear superposition of solutions due to its probabilistic representation. As genetic operators, quantum gates are employed for the search of the best solution. Rapid convergence and good global search capability characterize the performance of GQA. The effectiveness and the applicability of GQA are demonstrated by experimental results on the knapsack problem, which is a well-known combinatorial optimization problem. The results show that GQA is superior to other genetic algorithms using penalty functions, repair methods and decoders.
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.