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

Computer Engineering and Applications Journal

Quantum-inspired ant algorithm for solving 0-1 knapsack problem

Xiaofeng He, Ma Liang

Published Jan 1, 2011• 6 citations
OpenAlex

Abstract

0-1 knapsack problem is a typical NP-hard problem in combinatorial optimization.A quantum-inspired ant colony algorithm for solving the 0-1 knapsack problem is proposed which is based on the combination of ant colony optimization and quantum computing.In the algorithm,the pheromone is expressed by quantum bits,and quantum rotation gates are used to update the ant pheromone.Series of test instances validate the effectiveness of the algorithm.The proposed algorithm can reduce the searching time and has better performance in reaching the global optimum.

Related papers

Quantum-inspired ant algorithm for knapsack problems

Wang Hong-gang, Ma Liang, Huizhen Zhang +1 more

The knapsack problem is a well-known combinatorial optimization problem which has been proved to be NP-hard. This paper proposes a new algorithm called quantum-inspired ant algorithm (QAA) to solve the knapsack problem. QAA takes the advantage of the principles in quantum computing, such as qubit, quantum gate, and quantum superposition of states, to get more probabilistic-based status with small colonies. By updating the pheromone in the ant algorithm and rotating the quantum gate, the algorithm can finally reach the optimal solution. The detailed steps to use QAA are presented, and by solving series of test cases of classical knapsack problems, the effectiveness and generality of the new algorithm are validated.

Journal of Systems Engineering and Electronics•Jan 18, 2012•6 citations

Hybrid Quantum Ant Colony Algorithm for Traveling Salesman Problem

Jia Rui-y

Aiming at the Traveling Salesman Problem based on ant colony optimization which is easy to fall into local optimums and has a slow convergence rate,a hybrid quantum ant colony optimization algorithm is presented.In this algorithm,the pheromone on each path is encoded by a group of quantum bits,the quantum rotation gate and ant's tour are used to update the pheromone so as to accelerate its convergence speed.To avoid the search falling into local optimum,the new neighborhood exchange strategy is designed to improve solution efficiency.Some cases from the TSP library(TSPLIB)are used to experiment,the results show that the algorithm has rapider convergence speed and higher accuracy than the classical ant colony algorithm.

Computer Engineering and Applications Journal•Jan 1, 2013•0 citations

Novel quantum ant colony algorithm for TSP

Fuxiao Tan

Ant Colony Algorithm(ACA) demonstrates the superiority in solving TSP,and Quantum Evolution Algorithm (QEA) has the performance of high efficiency on combinational optimization problems,so combining the thought of ACA with QEA,a novel quantum ant colony algorithm for TSP is proposed.In this algorithm,the pheromone on each path is encoded by a group of quantum bits,and a new pheromone representation is designed,called quantum pheromone.The quantum rotation gate and the best tour are applied to update the pheromone so as to accelerate its convergence speed.To avoid the search falling into local optimum,the strategy of quantum crossover is designed to improve the information structure of population.Simulation results show that the algorithm has fast convergence speed and global optimal ability,and the algorithm is more effective than ACS.

Computer Engineering and Applications Journal•Jan 1, 2011•1 citation

Quantum ant colony algorithm for continuous space optimization

Shiyong Li

To tackle the shortcoming of ant colony optimization which can only be applied to discrete problems and hold a slow convergence rate,a novel method for solving optimization problems in continuous space is presented.In this algorithm,each ant carries a group of quantum bits which represent the position of the ant.Firstly,the target where the ant is going to move is selected according to the selection probability based on pheromone information and heuristic information.Secondly,quantum bits of the ant are updated by quantum rotation gates so as to enable the ant to move.Some quantum bits are mutated by quantum non-gate so as to increase the variety of ant positions.Finally,pheromone information and the heuristic information are updated according to the new position of each ant arrived at.In this algorithm,both probability amplitudes of a quantum bit are regarded as position information belonging to an ant,a double searching space is acquired for ant colony which hold the same number of ants.At last,the availability of the algorithm is illustrated by two application examples of function optimization and weight optimization of neural networks.

Control theory & applications•Jan 1, 2008•19 citations

Research and Application on Ant Colony Optimization Based on Quantum Computing

Wang Xiao-mi

Aiming at the disadvantage of optimization problems based on traditional ant colony optimization (ACO)which easily falls into local optimums and has worse performance in convergence,the paper unifies the quantum evolutionary algorithm (QEA) and the ant colony algorithm,in this algorithm,pheromone is represented by quantum bits and updated by a new quantum rotation gate adjustment srrategy.And this paper applies separately this algorithm and the traditional ACO to traveling salesman problem(TSP),The simulation results show that the algorithm of this paper has excellent global optimization properties and quicker convergence than the traditional ACO.

Information Technology and Informatization•Jan 1, 2009•0 citations

A quantum-inspired ant colony algorithm for graph coloring problem

Ma Liang

A quantum-inspired ant colony algorithm(QACA) for the classic graph coloring problem is proposed based upon the combination of ant colony optimization and quantum computing.The quantum bits and quantum logic gates are introduced to the ant colony algorithm(ACA),and the disadvantage of getting into the local optimum can be effectively avoided.The computational speed of the algorithm is therefore significantly improved.Series of simulation instances of the graph coloring problem are tested.And the results show that the QACA is a feasible,effective and versatile method for solving the graph coloring problem.

Or Transactions•Jan 1, 2013•2 citations
0-1 knapsack problem is a typical NP-hard problem in combinatorial optimization.A quantum-inspired ant colony algorithm for solving the 0-1 knapsack problem is proposed which is based on the combination of ant colony optimization and quantum computing.In the algorithm,the pheromone is expressed by quantum bits,and quantum rotation gates are used to update the ant pheromone.Series of test instances validate the effectiveness of the algorithm.The proposed algorithm can reduce the searching time and has better performance in reaching the global optimum.
The knapsack problem is a well-known combinatorial optimization problem which has been proved to be NP-hard. This paper proposes a new algorithm called quantum-inspired ant algorithm (QAA) to solve the knapsack problem. QAA takes the advantage of the principles in quantum computing, such as qubit, quantum gate, and quantum superposition of states, to get more probabilistic-based status with small colonies. By updating the pheromone in the ant algorithm and rotating the quantum gate, the algorithm can finally reach the optimal solution. The detailed steps to use QAA are presented, and by solving series of test cases of classical knapsack problems, the effectiveness and generality of the new algorithm are validated.
Aiming at the Traveling Salesman Problem based on ant colony optimization which is easy to fall into local optimums and has a slow convergence rate,a hybrid quantum ant colony optimization algorithm is presented.In this algorithm,the pheromone on each path is encoded by a group of quantum bits,the quantum rotation gate and ant's tour are used to update the pheromone so as to accelerate its convergence speed.To avoid the search falling into local optimum,the new neighborhood exchange strategy is designed to improve solution efficiency.Some cases from the TSP library(TSPLIB)are used to experiment,the results show that the algorithm has rapider convergence speed and higher accuracy than the classical ant colony algorithm.
Ant Colony Algorithm(ACA) demonstrates the superiority in solving TSP,and Quantum Evolution Algorithm (QEA) has the performance of high efficiency on combinational optimization problems,so combining the thought of ACA with QEA,a novel quantum ant colony algorithm for TSP is proposed.In this algorithm,the pheromone on each path is encoded by a group of quantum bits,and a new pheromone representation is designed,called quantum pheromone.The quantum rotation gate and the best tour are applied to update the pheromone so as to accelerate its convergence speed.To avoid the search falling into local optimum,the strategy of quantum crossover is designed to improve the information structure of population.Simulation results show that the algorithm has fast convergence speed and global optimal ability,and the algorithm is more effective than ACS.
To tackle the shortcoming of ant colony optimization which can only be applied to discrete problems and hold a slow convergence rate,a novel method for solving optimization problems in continuous space is presented.In this algorithm,each ant carries a group of quantum bits which represent the position of the ant.Firstly,the target where the ant is going to move is selected according to the selection probability based on pheromone information and heuristic information.Secondly,quantum bits of the ant are updated by quantum rotation gates so as to enable the ant to move.Some quantum bits are mutated by quantum non-gate so as to increase the variety of ant positions.Finally,pheromone information and the heuristic information are updated according to the new position of each ant arrived at.In this algorithm,both probability amplitudes of a quantum bit are regarded as position information belonging to an ant,a double searching space is acquired for ant colony which hold the same number of ants.At last,the availability of the algorithm is illustrated by two application examples of function optimization and weight optimization of neural networks.
Aiming at the disadvantage of optimization problems based on traditional ant colony optimization (ACO)which easily falls into local optimums and has worse performance in convergence,the paper unifies the quantum evolutionary algorithm (QEA) and the ant colony algorithm,in this algorithm,pheromone is represented by quantum bits and updated by a new quantum rotation gate adjustment srrategy.And this paper applies separately this algorithm and the traditional ACO to traveling salesman problem(TSP),The simulation results show that the algorithm of this paper has excellent global optimization properties and quicker convergence than the traditional ACO.
A quantum-inspired ant colony algorithm(QACA) for the classic graph coloring problem is proposed based upon the combination of ant colony optimization and quantum computing.The quantum bits and quantum logic gates are introduced to the ant colony algorithm(ACA),and the disadvantage of getting into the local optimum can be effectively avoided.The computational speed of the algorithm is therefore significantly improved.Series of simulation instances of the graph coloring problem are tested.And the results show that the QACA is a feasible,effective and versatile method for solving the graph coloring problem.