基于量子遗传算法的无线传感器网络QoS路由选择算法研究 第3页
第二章 量子遗传算法
遗传算法(Genetic Algorithm，GA)起源于对生物系统所进行的计算机模拟研究，是模拟自然界生物进化机制的一种算法，即遵循适者生存、优胜劣汰的法则，也就是寻优过程中有用的保留，无用的则去除。在科学和生产实践中表现为，在所有可能的解决方法中找出最符合该问题所要求的条件的解决方法，即找出一个最优解。这种算法是由美国Michigan大学的J. Holland教授于1975年首次提出的[11]。其最初的目的是研究自然系统的自适应行为，并设计具有自适应功能的软件系统。它的特点是对参数进行编码运算，不需要有关体系的任何先验知识，沿多种路线进行平行搜索，不会落入局部较优的陷阱，能在许多局部较优中找到全局最优点，是一种全局最优化方法。
2.1 遗传算法的基本原理
遗传算法[12-14]是一种随机全局搜索算法，它对目标空间进行随机搜索。它将问题域中的可能解看作是群体的一个个体或染色体，并对每一个个体用二进制表示法或浮点数表示法进行编码，现有模型的参数化，把代表模型集参数空间中的每一点都一一映射到染色体空间的染色体上，对群体反复进行基于遗传学的操作，据预定的目标函数对每个个体进行评价。经过基本的遗传操作过程，反复迭代不断优化繁殖以产生新的一代，不断得到更优的群体，同时以全局并行搜索方式来搜索优化群体中的最优个体，得满足要求的最优解。
在很多情况下，我们解决一个问题就是从一大堆的数据中寻找一个解，而通常这个解都是混杂在数据中的。所有可行解组成的空间称之为搜索空间(也称为状态空间)。搜索空间中的每一个点都是一个可行解，每一个可行解都可以被它的函数值或是它的适应度标记。问题的解是搜索空间中的一个点，于是我们就要从搜索空间中找到这个点。这样，求解问题就可以转化为在搜索空间中寻找极值点。搜索空间在求解问题时可能是完全已知的，但一般来说我们只知道一些孤立的点，然后我们逐渐地生成其它点。可能这个搜索过程会很复杂，甚至于我们不知道该去哪里搜索或者该从什么地方开始搜索。但是，有很多寻找合适解的方法，比如说爬山法(Hill Climbing)、模拟退火算法(Simulated Annealing)以及遗传算法等等。用遗传算法求解出来的解一般被认为是一个比较好的解。
遗传算法的几个基本概念：
①. 染色体(Chromosome)：在使用GA时，需要把问题解编成具有固定结构
的符号串，它的每一位代表一个基因。一个染色体就代表问题的一个可行解，每个染色体称为一个个体。
②. 种群(Population)：每代遗传所产生的染色体总数。一个种群包含了该问
题在某一遗传代中的一些可行解的集合。
③. 适应度(Fitness)：每个染色体对应具体问题的一个解，每个解都对应的
评估函数值即为适应度，它是衡量染色体对环境适应度的指标，也是反映实际问题的目标函数。
简单遗传算法(Simple Genetic Algorithms, SGA)是所有遗传算法的基础，也是研究各种遗传算法性能和优缺点的对象。虽然在一般的应用中不会直接应用简单的遗传算法，但对它的深入了解对我们掌握遗传算法的基本思想有重要的意义。简单遗传算法的基本流程如图2.1所示。
简单遗传算法的基本步骤如下：
（1） 对所涉及问题的可行解进行染色体(chromosome)编码；
（2） 针对问题，寻找一个客观的适应度函数(fitness function)；
（3） 生成满足所有约束条件的初始种群(initial population)；
（4） 计算种群中每个染色体的适应度(fitness core)；
（5） 若满足停机条件，退出循环，输出最优解；否则，继续向下执行；
（6） 根据每个染色体的适应度，产生新的种群，即进行选择操作；
（7） 进行交叉操作和变异操作；
（8） 返回（4）进行计算。
图2.1  遗传算法流程图
2.2 遗传算法常见编码方法和基本操作
2.2.1 编码问题
如何将问题的解编码成为染色体是遗传算法使用中的关键问题。在遗传算法执行过程中，对不同的具体问题进行编码，编码的好坏直接影响选择、交叉和变异等遗传算法基本操作。在遗传算法中描述问题的可行解，即把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间，这种转换方法就称编码。而由遗传算法可行解空间向问题可行解空间的转换称为解码(或称译码，Decoding)。
根据采用何种的符号作为基因的等位基因，编码的方式可以分类如下[15]：
 二进制编码（binary encoding）
 实数编码（real-number encoding）
 整数和字母排列编码
 一般数据结构编码
二进制编码方法[16]是遗传算法中最主要的一种编码方法，它使用的编码符号集是由二进制符号0和1所组成的二值符号集{0，1}，它所构成的个体基因型是一个二进制编码符号串。二进制编码符号串的长度与问题所要求的求解精度有关。
二进制编码不便于反映所求问题的结构特征，对于一些连续函数的优化问题，也由于遗传运算的随机特性而使得其局部搜索能力较差。为了改进这个特性，人们提出用格雷码(Gray Code)来对个体进行编码。格雷码是这样一种编码方法，其连续的两个整数所对应的编码之间仅仅只有一个码位是不同的。格雷码是二进制编码方法的一种变形。
实数编码对于函数优化问题最为有效。关于实数编码在函数优化和约束优化领域比二进制编码和Gray编码更有效的说法，已经得到了广泛的验证[17]。由于实数编码基因型空间中的拓扑结构与其表现型空间中的拓扑结构一致，因此很容易从传统优化方法中借鉴好的技巧来形成有效的遗传算子。
整数和字母排列编码对于组合优化问题最为有效。由于组合优化问题最关键的是要寻找满足约束项目的最佳排列和组合，因此字母排列编码对于这类问题是最有效的方法。
选用什么编码方法主要取决于所要解决的问题本身。文中选用解决函数优化问题最为有效的实数编码。
2.2.2 基本操作
遗传算法包括三种基本的操作：选择、交叉、变异。
(1) 选择(selection)
选择又称复制(Reproduction)，是在群体中选择生命力强的个体产生新的群体的过程。遗传算法使用选择算子来对群体中的个体进行优胜劣汰操作：根据每个个体的适应度值大小选择，适应度较高的个体被遗传到下一代群体中的概率较大；适应度较低的个体被遗传到下一代群体中的概率较小。这样就可以使得群体中个体的适应度值不断接近最优解。选择操作建立在对个体的适应度进行评价的基础之上。选择操作的主要目的是为了避免有用遗传信息的丢失，提高全局收敛性和计算效率。选择算子确定的好坏，直接影响到遗传算法的计算结果。选择算

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