量子遗传算法用于认知无线电频谱分配的应用研究 第4页
2.2经典遗传算法
2.2.1 遗传算法的基本原理
遗传算法是一种随机全局搜索算法, 它对目标空间进行随机搜索。
遗传算法的几个基本概念：
①染色体(Chromosome)：在使用GA时，需要把问题解编成具有固定结构的符号串，它的每一位代表一个基因。一个染色体就代表问题的一个解，每个染色体称为一个个体。
②群体(Population)：每代所产生的染色体总数。一个群体包含了该问题在这一代的一些解的集合。
③适应度(Fitness)：每个个体对应一个具体问题的解，每个解对应的函数值即为适应函数，它是衡量染色体对环境适应度的指标，也是反映实际问题的目标函数。
简单遗传算法（Simple Genetic Algorithms,SGA）是所有遗传算法的基础，也是研究各种遗传算法性能和优缺点的对象。遗传算法的基本流程如图2-1：简单遗传算法的基本步骤如下：
step1:对所涉及问题的可能解进行染色体（chromosome）编码；
step2:针对问题，寻找一个客观的适应度函数（fitness function）；
step3:生成满足所有约束条件的初始种群（initial population）；
step4:计算种群中每个染色体的适应度（fitness core）；
step5:若满足停机条件，退出循环，输出最优解；否则，继续向下执行；
step6:根据每个染色体的适应度，产生新的种群，即进行选择操作；
step7:进行交叉操作和变异操作。
step8:返回step4.进行计算
2.2.2 经典传算法的应用
遗传算法（Genetic Algorithm，GA）起源于对生物系统所进行的计算机模拟研究，是模拟自然界生物进化机制的一种算法，即遵循适者生存、优胜劣汰的法则，也就是寻优过程中有用的保留，无用的则去除。
2.2.3 遗传算法常见编码方法和基本操作
编码是应用遗传算法时要解决的首要问题，也是设计遗传算法时的一个关键步骤。而由遗传算法解空间向问题空间的转换称为解码[13]。
二进制编码方法是遗传算法中最主要的一种编码方法，它使用的编码符号集是由二进制符号0和1所组成的二值符号集{0，1}，它所构成的个体基因型是一个二进制编码符号串。二进制编码符号串的长度与问题所要求的求解精度有关。
浮点数编码方法是指个体的每个基因值用某一范围内的一个浮点数来表示，个体的编码长度等于其决策变量的个数。此编码方法可以用来解决一些多维、高精度要求的连续函数优化问题，因为二进制码在这类问题中不好用。
树形编码主要用于遗传规划中的演化编程或者表示。在树形编码中，每个基因都是由数字或符号组成的树形结构。
选用什么方法编码主要取决于所要解决的问题本身。
遗传算法包括三种基本的操作：选择、交叉、变异。
（1）选择（selection）
选择又称复制（Reproduction），是在群体中选择生命力强的个体产生新的群体的过程。常用的方法有：
①轮盘赌或蒙特卡罗选择法，它是利用比例于各个个体适应度的概率决定其子孙的遗传可能性。若某个个体为i，其适应度为fi，则其被选择的概率表示为：
                                                    （2.11）
显然，选择概率大的个体能多次被选中，它的遗传因子就会在种群中扩大。
②最佳个体保存方法，把群体中适应度最高的个体不进行配对交叉而直接复制到下一代中。
③排序选择方法，指在计算每个个体的适应度后，根据适应度对群体中个体排序，然后把事先设计好的概率表按序分配给个体，作为各自的选择概率。  
（2）交叉（crossover）
交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作，也称基因重组。常用的交叉操作方法有：单点交叉算子、两点交叉算子和多点交叉算子。除了上述交叉方法，还有均匀交叉、部分匹配交叉、顺序交叉、循环交叉等交叉方法。
（3） 变异（mutation）
变异即对群体中的个体串的某些基因座上的基因值作变动。交叉和变异是遗传算法中最重要的部分，算法的结果受交叉和变异的影响最大。变异的目的有两个：1)使遗传算法具有局部的随机搜索能力；2)保持群体的多样性。
2.2.4 遗传算法的特点
遗传算法的独特优点：①遗传算法在寻优过程中，仅需要得到适应度函数的值作为寻优的依据；②遗传算法的优化搜索是从问题解的集合（种群）开始，而不是从单个解开始；③遗传算法使用概率性的变换规则，而不是确定性的变换规则；④遗传算法适应度函数的计算相对于寻优过程是独立的；⑤遗传算法面对的是参数的编码集合，而并非参数集合本身，通用性强。它尤其适用于处理传统优化算法难于解决的复杂和非线性问题。
遗传算法提供了一种求解复杂系统优化问题的通用框架，可以广泛应用于许多学科。下面是遗传算法的一些主要应用领域[16],比如h函数优化、组合优化、生产调度问题自动控制、图像处理和模式识别。另外，遗传算法在机器人智能控制，人工生命、机器学习等领域也已经有一些成功的应用。
2.3 量子遗传算法
2.3.1 量子遗传算法概述
量子遗传算法（Quantum Genetic Algorithm，QGA）是量子计算与遗传算法相结合的产物。它建立在量子的态矢量表述基础上,将量子比特的几率幅表示应用于染色体的编码,使得一条染色体可以表达多个态的叠加，并利用量子旋转门或量子非门实现染色体的更新操作，从而实现了目标的优化求解。目前，这一领域的研究主要集中在量子模型上：一是量子衍生遗传算法（Quantum Inspired Genetic Algorithm）[15]；二是基于量子比特和量子态叠加特性的遗传量子算法（Genetic Quantum Algorithm）和并行量子遗传算法[16][17]。
本节是在综述经典遗传算法的基础上介绍量子遗传算法，它与经典遗传算法相比,区别在于采用量子比特编码方法、量子坍塌过程取代经典遗传算法的交叉操作以及量子变异的方法上。因此，改进的量子遗传算法既具有较好的种群多样性，又具有更好的全局搜索能力。
2.3.2 量子染色体
QGA使用一种基于量子比特的编码方式，即用一对复数定义一个量子比特位，一个有k个量子比特位的系统描述为

上一页  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]  ... 下一页  >>