1、2108 单词， 3345 汉字 毕业论文（设计） 外文翻译 题 目 ： 学 院： 数理与信息学院 学生姓名： 专 业： 计算机科学与技术 班 级： 指导教师： 起 止 日期： 2014.11.28 至 2015.1.16 2015 年 1 月 15 日 毕业论文：外文翻译 1 Pager1 An Improved Quantum Genetic Algorithm GUO Jian, SUN Li-juan, WANG Ru-chuan, YU Zhong-gen College of Computer,Nanjing University of Posts and Telecommunic
2、ations, Nanjing, China, Abstract: Quantum genetic algorithm (QGA) is the combination between genetic algorithm and quantum computing. In this paper, a chromosome of the standard QGA is seen as a node and the chromosome population is regarded as a network. Then the reasons for the prematurity and th
3、e stagnation of the standard QGA are analyzed from the perspective of network structure. To solve the two problems, an improved quantum genetic algorithm (IQGA) based on the small world theory is proposed. In IQGA, chromosomes encoded with qubits are divided into some sub-groups and the NW network m
4、odel is introduced into the population structure. When updating chromosomes, an optimal chromosome in locality or in other sub-groups is chosen based on a certain probability as the evolution target for each chromosome. The new network structure of the chromosome population has a relatively moderate
5、 clustering coefficient and is favorable to the diversity of individual chromosomes. Tests of three classic functions prove the effectiveness and superiority of IQGA. Keywords: improved quantum genetic algorithm； quantum genetic algorithm； NW network model； small world 1.INTRODUCTION Genetic Algorit
6、hm (GA) is a random search algorithm based on the evolution theory of the survival of the fittest 1-5. It has characteristics of parallelism and versatility. However, in practical applications, GA has a slow convergence speed, and is subject to a local optimal solution. Many improvements have been m
7、ade. Among these, quantum genetic algorithm (QGA) proposed in the late nineties achieved significant results 6-13. QGA introduced some thoughts of quantum computing into GA, which greatly improved the parallelism of genetic manipulation and accelerated the convergence process. QGA has shortcomings a
8、s well. As QGA chooses one optimal quantum chromosome each round to guide the evolution of all chromosomes, this approach undermines the diversity of the population, making the process subject to a local optimal solution. 毕业论文：外文翻译 2 In this paper, analyses are given from the perspective of the stru
9、cture of chromosome population, and defects are analyzed. To overcome the defects, an improved quantum genetic algorithm (IQGA) based on the small world theory 14-16 is proposed. IQGA introduces the NW network model 15 and improves its population structure, so the diversity of the population is main
10、tained. The effectiveness and superiority of IQGA are demonstrated through the tests of classic functions. II. QUANTUM GENETIC ALGORITHM QGA is the combination between GA and quantum computing. It is based on the quantum vectors, representing chromosome by qubit coding, and updating chromosome by qu
11、antum rotation gate and quantum not gate. Eventually the optimal solution is supposed to be found out. A. Qubit encoding Qubit is the smallest unit of information in QGA. A qubit may be in either 1 or 0state, or in any superposition of the both, i.e. a qubit may be |0, |1, or in the in-between state
12、. Therefore, it can be expressed as: | = |0 + |1, (1) where and are two complex numbers satisfying |2 +|2 = 1. | |2 and |2 denote the probabilities of |0 and |1 respectively. In QGA, qubits are used to represent a gene which expresses all the probable information instead of a set of definite informa
13、tion. And any operation carried out on this gene may exert influence on all possible information simultaneously. Furthermore, a chromosome can be encoded as: where k denotes the number of qubits in each gene, while m is the number of genes in each chromosome. xy and xy (1 x m,1 y k) are two complex
14、numbers satisfying | xy|2 + |xy|2 = 1. B. Evolutionary operation Quantum rotation gate is the implementation of evolution operation. It operates as: where (i, i)T and ( i, i)T are the i-th (1 i mk) qubit of the pre-update and post-update chromosome respectively. i is the rotation angle, whose value and direction can be adjusted by some strategies 7,10,11.
