The Research And Application Of Quantum Bacterial Foraging Optimization

Quantum swarm intelligent optimization algorithms such as quantum genetic algorithm、quantum ant colony optimization、 quantum particle swarm optimization are new efficientalgorithms by integrating quantum computing into particle swarm optimization. They have theadvantages of better parallelism、faster convergence speed、better population variety、better globalsearch capability. Simple bacterial foraging optimization algorithm (BFO) is a bionic swarmalgorithm that simulates the mechanism of natural evolution. A new quantum bacterial foragingoptimization algorithm(QBFO) based on quantum computing and simple BFO will be proposed inthis paper. The algorithm is applied to0-1knapsack problem and traveling salesman problem. Themain research work of this paper can be summarized as follows:Firstly, the basic principle of BFO and the algorithm process are been analysized. Thenchemotaxis、reproduction、elimination and dispersal in detail are researched and the performance ofthe algorithm is tested by simulating on a series of benchmark functions. The simulation resultsshow that BFO has some advantage and shortage in solving optimal problems.Secondly, the basic conception and principle on quantum computing are analysized. A newQBFO is proposed by integrating quantum computing into simple BFO. The chromosome is used torepresent bacterium and the quantum rotation gate is used to update bacterium’s position. After thatit deeply discusses the concept of QBFO、quantum chromosome encoding、algorithm process andspecific methods of operation. Its performance is analyzed deeply by testing on various typicalbenchmark functions. The results indicate that QBFO has much better effects than original BFO.Thirdly, it analysizes some relevant conception、model、classification and common methods.The algorithm is applied to0-1knapsack problem and traveling salesman problem. The experimentssuccessfully demonstrate QBFO by testing on groups of data. It achieves combination of theory andpractice, and provides a new algorithm for Non-deterministic Polynomial problem.