1、中文 2718 字， 1680 单词 原文： Pager2 Genetic Algorithm Based-On the Quantum Probability Bin LIand Zhen-quanZhuang Laboratory of Quantum Communication and Quantum Computation, University of Science and Technology of China, Hefei, 230026, China Abstract:A genetic algorithm based on the quantum probability re
2、presentation(GAQPR) is proposed, in which each individual evolves independently； a newcrossover operator is designed to integrate searching processes of multiple individuals into a more efficient global searching process； a new mutation operatoris also proposed and analyzed. Optimization capability
3、of GAQPR is studiedvia experiments on function optimization, results of experiments show that, formulti-peak optimization problem, GAQPR is more efficient than GQA4. 1 Introduction Research development in quantum computation presents us not only with a temptingperspective of future computational cap
4、ability 1, but also with inspirations of improving classical algorithms by reconsidering them from a standpoint of quantum mechanics. Genetic algorithm is a well-known heuristic searching algorithm, and hasbeen proved successful in many applications 2. Research work on merging geneticalgorithm and q
5、uantum computation has been started by some researchers since1990s. Only two practical models have been proposed till now. QIGA (Quantum-Inspired Genetic Algorithm), proposed by AjitNarayanam, introduces the theory of many universes in quantum mechanics into the implementationof genetic algorithm 3.
6、 The main contribution of 3 is that it proves the efficiencyof the strategy that uses multiple colonies to search in parallel, and uses a joint cross-over operator to enable the information exchange among colonies. Kuk-Hyun Han proposed a Genetic Quantum Algorithm (GQA) 4, in which theprobability am
7、plitude of qubit was used for the first time to encode the chromosome,and the formula of quantum rotation gate was used to implement the updating ofchromosome. GQA is basically a probability algorithm, not a 毕业论文：外文翻译 1 genetic algorithm. Allindividuals evolve towards one Contemporary Evolutionary T
8、arget (CET). Importantgenetic operators, such as crossover and mutation, are not adopted in it. In this paper, a new Genetic Algorithm based on the Quantum Probability Representation (GAQPR) is proposed, in which each individual has its own ContemporaryEvolutionary Target (CET) and evolves independe
9、ntly； a new crossover operator isdesigned to enable the efficient exchange of evolution information between differentindividuals. A new mutation operator is also proposed,its effect is studied in experiments. Experiments on two typical function optimization problems prove that, formultipeak optimiza
10、tion problem, GAQPR is more efficient than GQA. The remaining part of this paper is organized as follow: section 2 describes theprinciple and procedure of GAQPR, which includes the introduction of representationand updating strategy of chromosomes, main procedure of GAQPR, and procedureof the new de
11、signed crossover and mutation operators. Section 3 is the description ofexperiment. Section 4 is the conclusion of the whole paper. 2 GAQPR 2.1 Representation and Updating of Chromosomes In quantum computation, the elementary unit for storing information is a quantumsystem with two states, called qu
12、antum bit (qubit). The key characteristic that makesqubit differ from classical bit is that it can be at the superposition of two quantumstates simultaneously. This superposition can be expressed as follow: | = | 0+|1, (1) where ( , ) is a pair of complex invariables, called probability amplitude of
13、 qubit,which satisfies | |2 + |2 = 1(2) |0 and |1 represent two different states of qubit respectively, so one qubit can storethe information of both states at the same time. In GQA, each gene has only two states, so one qubitis enough for encoding onegene. But it is often the case in applications t
14、hat one gene may have more than twostates. In this paper, following the binary coding methods in classical genetic algorithm, we use more than one qubit to encode gene with more than two states. A chromosome is defined as follow: 毕业论文：外文翻译 2 Whereqtjis the j-th chromosome in the colony at generation
15、 t, m is the number ofgenes in a chromosome, and k is the number of qubit used to encode one gene, whichcan be calculated by function k = ceil(logn2),(4) where n is the state number of each gene, function ceil(x) finds the nearest integerfrom x towards + Gene updating follows the formula of quantum
16、rotation gate shown as follow: where ( i , i) is the pair of probability amplitude of the ithqubit in chromosome, i = s (i i) i4, and the values of s( i, i) and iare determined by a predefinedstrategy shown in table 1. The strategy proposed in 4 is designed for the knapsackproblem, which has bias. I
17、n this paper we do some adjustment to make it a universalstrategy. Table 1. Tuning strategy of rotation angle Tuning pace of rotation angle “Delta” may take different values in different operations. For example, in regular evolution operation “Delta” can take the value a littlelarger than that in crossover operation. This provides an easy way to control the effectof crossover operator.
