基于量子遗传算法的无线传感器网络QoS路由选择算法研究 第4页
子的确定不应当会造成群体中相似度值相近的个体增加，使得子代个体与父代个体相近，导致进化停止不前；或使适应度值偏大的个体误导群体的发展方向，使遗传失去多样性，产生早熟问题。常用的方法有：
① 轮盘赌或蒙特卡罗选择法：它是利用比例对于各个个体适应度的概率决定其子孙的遗传可能性。若某个个体为i，其适应度为fi，则其被选择的概率表示为： (2-1)
式（2-1）中，M为种群中的个体数。显然，选择概率大的个体能多次被选中，它的遗传因子就会在种群中扩大。
② 最佳个体保存方法：把群体中适应度最高的个体不进行配对交叉而直接复制到下一代中。
③ 排序选择方法：指在计算每个个体的适应度后，根据适应度大小顺序对群体中个体排序，然后把事先设计好的概率表按序分配给个体，作为各自的选择概率。所有个体按适应度大小排序，选择概率和适应度无直接关系而仅与序号有关。除此之外，还有随机遍历抽样法、联赛选择方法和分级选择方法等等。
(2) 交叉(crossover)
交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作，也称基因重组。交叉操作的作用是产生新的个体，交叉操作是GA区别于其它进化算法的重要特征，遗传算法中起核心作用的是遗传操作的交叉算子，各种交叉算子都包括两个基本内容：1) 在选择操作形成的群体中，对个体随机配对并按预先设定的交叉概率来决定每对是否需要进行交叉操作；2) 设定配对个体的交叉点，并对这些点前后的配对个体的部分结构(或基因)进行相互交换。常用的交叉操作方法有：
① 单点交叉算子
从群体中随机取出两个字符串，设串长为L，随机确定交叉点，它是1到L-1间的正整数。于是，将两个串的右半段互换再重新连接得到两个新串。当然，得到的新串不一定都能保留在下一代，需和原来的串进行比较，保留适应度大的两个，如：
父个体A： 0 1 0 0 1 1 0 0 0 1
父个体B： 1 1 0 1 0 0 1 1 1 1 (2-2)
若交叉点的位置为5，交叉后产生两个子个体为：
子个体1： 0 1 0 0 1 0 1 1 1 1
子个体2： 1 1 0 1 0 1 0 0 0 1
② 两点交叉算子
两点交叉是指在个体编码串中随机设置了两个交叉点，然后再进行两交叉点之间的部分染色体基因交换。对于式(2-2)，若两交叉点分别为3和8，则交叉后产生的子个体为：
子个体1： 0 1 0 1 0 0 1 0 0 1
子个体2： 1 1 0 0 1 1 0 1 1 1
③ 多点交叉算子
将单点交叉与两点交叉的概念加以推广，可得到多点交叉的概念。多点交叉是指在个体编码串中随机设置多个交叉点，然后进行基因交换。以式(2-2)为例，设交叉点位置为2、5、8，则交叉后的两个新的子个体为：
子个体1： 0 1 0 1 0 1 0 0 1 1
子个体2： 1 1 0 0 1 0 1 1 0 1
除了上述交叉方法，还有均匀交叉、部分匹配交叉、顺序交叉、循环交叉等交叉方法。
(3) 变异(mutation)
变异是对群体中的个体串的某些基因座上的基因值作变动。交叉和变异是遗传算法中最重要的部分，算法的结果受交叉和变异的影响最大。变异的目的有两个：1) 使遗传算法具有局部的随机搜索能力；2) 保持群体的多样性。选择和交叉算子基本上完成了遗传算法的大部分搜索功能，而变异则增加了遗传算法找到接近最优解的能力。变异就是以很小的概率随机地改变字符串某个位置的值。在二进制编码中，变异算子随机地将某个位置的“1”变成“0”，或者“0”变成“1”。变异本身是一种随机搜索，然而与复制、交叉算子结合在一起，就能避免由于复制与交叉算子而引起的某些信息的永久丢失，保证了遗传算法的有效性。
2.2.3 遗传算法的特点和应用
遗传算法不同于传统寻优算法的特点在于：①遗传算法在寻优过程中，仅需要得到适应度函数的值作为寻优的依据；②遗传算法的优化搜索是从问题解的集合（种群）开始，而不是从单个解开始；③遗传算法使用概率性的变换规则，而不是确定性的变换规则；④遗传算法适应度函数的计算相对于寻优过程是独立的；⑤遗传算法面对的是参数的编码集合，而并非参数集合本身，通用性强。它尤其适用于处理传统优化算法难于解决的复杂和非线性问题。
遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖与问题的具体领域，对问题的种类具有很强的鲁棒性，所以广泛应用于许多学科。下面是遗传算法的一些主要应用领域[18]。
（1）函数优化。函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评估的常用算例。很多人构造出了各种各样的复杂形式的测试函数，有连续函数也有离散函数，有凸函数也有凹函数，有低文函数也有高文函数，有确定函数也有随机函数，有单峰函数也有多峰函数等，人们用这些几何特性各异的函数来评价遗传算法的性能。而对于一些非线性、多模型、多目标的函数优化问题，用其他优化方法较难求解，遗传算法却可以方便地得到较好的结果。
（2）组合优化。随着问题规模的扩大，组合优化问题的搜索空间急剧扩大，有时在目前的计算机上用枚举法很难或者甚至不可能得到其精确最优解。对于这类复杂问题，人们已经意识到应把精力放在寻求其满意解上，而遗传算法则是寻求这种满意解的最佳工具之一。实践证明，遗传算法对于组合优化中的NP完全问题非常有效。例如，遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划分问题等方面得到成功的应用。
（3）生产调度问题。遗传算法已成为解决复杂生产调度问题的有效工具，在单件生产车间调度、流水线生产车间调度、生产规划、任务分配等方面都得到了有效应用。
（4）自动控制。在自动控制领域中的许多与优化相关的问题需要求解，遗传算法的应用日益增加，并显示了良好的效果。例如基于遗传算法的模糊控制器优化设计、基于遗传算法的参数辨识、利用遗传算法进行人工神经网络的结构优化设计和权值学习，都显示出了遗传算法在此领域中应用的可能性。
（5）图像处理和模式识别。这是计算机视觉中的一个重要研究领域。在图像处理过程中，如扫描、特征提取、图像分割等不可避免地会产生一些误差，这些误差会影响到图像处理和识别的效果。如何使这些误差最小使计算机视觉达到实用化的重要要求。遗传算法在图像处理中的优化计算方面是完全胜任的，目前已在图像恢复、图像边缘特征提取、几何形状等方面得到了应用。
另外，遗传算法在机器人智能控制，人工生命、机器学习等领域也已经有一些成功的应用。有关遗传算法的大量应用研究表明，遗传算法在许多领域都有十分广泛的实际应用前景。
2.3 量子遗传算法
量子遗传算法（Quantum Genetic Algorithm，QGA）是量子计算与遗传算法相结合的产物。它建立在量子的态矢量表述基础上，将量子比特的几率幅表示应用于染色体的编码，使得一条染色体可以表达多个态的叠加，并利用量子旋转门和量子非门实现染色体的更新操作，从而实现了目标的优化求解。它与经典遗传算法相比，区别在于采用量子比特编码方法、量子坍塌过程取代经典遗传算法的交叉操作、量子变异。
2.3.1 量子染色体
QGA使用一种基于量子比特的编码方式，即用一对复数定义一个量子比特位，一个有k个量子比特位的系统描述为 （2-3）
其中 是两个复数，是第i个量子比特的概率幅，其模满足归一化条件， 表示测量时发现 的概率， 表示发现 的概率。这种表示可表征任意的线性叠加态，例如有一个3量子比特系统 （2-4）
则系统的状态表示为
上一页 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] ... 下一页 >>
基于量子遗传算法的无线传感器网络QoS路由选择算法研究 第4页下载如图片无法显示或论文不完整，请联系qq752018766
