第9章进化计算信息处理方法与应用.doc

第9章进化计算信息处理方法与应用9.1标准遗传算法遗传算法是具有"生成+测试” (ge nerate and test)的迭代过程的搜索算法它的基本处 理流程如图9-1所示遗传算法是一种群体型操作，该操作以群体中的所有个体为对象图9-1遗传算法的基本流程复制(reproduction)，交叉(crossover)和变异(mutation)是遗传算法的3个主要操作算子， 它们构成了所谓的遗传操作 (genetic operation)，使遗传算法具有了其它传统搜索算法所没有的特征遗传算法中包含了 5个基本要素：参数编码；初始群体的设定；适应度 (fitness)函数的设计；遗传操作设计；控制参数设定 (主要是指群体大小和使用遗传操作的概率等 )这5个要素构成了遗传算法的核心内容 下面以函数优化为例来阐述遗传算法的基本概念和运行过程函数优化问题表述如下：有 n维映射f(x): RJR,求maxf(x)，无函数连续性的任何信息遗传算法把函数优化问题中的自变量 x当作生物体，将其转化为由基因构成的染色体(以下称串)，相应的函数值定义为适应度生物体的目标是进化成有最佳适应度的基因型 用遗传算法求解函数优化问题的步骤如下：1) 选择编码策略，把参数转换成串；编码策略有二进制编码和实数编码等， 若采用二进制码表示实数，每个二进制位即为一基因，若一维参数 x [a, b]，则l- i、gi2x = a 『 b -a . (9-1)2 -1其中I是串的长度，gi是第i个基因。

2) 定义串的适应度函数； 适应度函数是目标函数的映射， 它包含了对优化问题所需的信息3） 设置遗传算法的控制参数（群体规模N，交叉概率Pc,变异概率Pm等），随机产生N 个串构成群体；4） 计算群体中每个串的适应度，串解码所得的解越好，则适应度值越高；5） 从群体中复制两个串，串适应度越高，则被复制的概率越大；6） 在串上随机选择一个位置，以交叉概率 Pc对两个串进行交叉操作；7） 对两个串中的基因位以变异概率 Pm进行翻转；8） 转至5）直至复制 N个串；9） 转至4）重复进行，直到解满足性能指标或规定的进化代数以上遗传操作过程描述了最简单的进化模型步骤 1）和步骤2）是实际应用中的关键步骤5）至步骤7）进行三种基本遗传操作，复制实施了适者生存的原则，交叉的作用是组合 父代中有价值的信息， 产生新的后代，以实现高效搜索， 变异的作用是保持群体中基因的多样性假定用遗传算法求f（x）=x2函数的最大值，x [0,31]表2.1给出了用遗传算法求解此问 题的计算过程和结果1. 编码由于遗传算法不能直接处理解空间的解数据，因此必须通过编码将它们表示成遗传空 间的基因型串结构数据在表 9-1中，变量x编码为5位长的二进制无符号整数表示形式。

如x=13可以表示成 011012. 初始群体的生成由于遗传算法的群体型操作需要，所以必须为遗传操作准备一个由若干个初始解组成 的初始群体为了简化说明，在表2.1中取群体大小n=4，即群体由4个个体组成在表2.1 左端给出了这一初始群体的成员 需要说明的是，初始群体的每个个体都是通过随机方法产生的初始群体也称为进化的初始代，即第一代 （first generation）3. 适应度评估检测遗传算法在搜索进化过程中一般不需要其它外部信息，仅用评估函数值来评估个体或 解的优劣，并作为以后遗传操作的依据 评估函数值又称作适应度（fitness）这里，根据f（x）=x2来评估群体中各个体显然，为了利用 f（x）=x2这一评估函数，即适应度函数，要把基因个体译码成表现型个体，即搜索空间中的解，比如 11000要译码成244. 复制复制操作的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一 代繁殖子孙判断个体优良与否的准则就是各自的适应度值 显然这一操作是借用了达尔文适者生存的进化原则，即个体适应度越高， 其被选择的机会就越多 选择操作实现方式很多，这里采用和适应度值成比例的概率方法来进行选择的方法。

表9-1遗传算法求f（x）=x2极值（串处理）初始群体 适应度 选择概率 期望个数串号 （随机生成 n=4） x f（R=x2 Ps=fi/2f f f101101131690.140.58211000245760.491.973010008640.060.22410011193610.311.23总和11701.04.0平均2930.251.0最大5760.492.0表9-1（续）实际选择个数交叉（竖线表（比例选择）示交叉处）配偶新群体xf(x)=x210110|12011001214421100|011100125625011|00041101127729110|01131000016256总和1754平均439最大729注：表中平均适应度 I =為f . n具体地说，就是首先计算群体中所有个体适应度的总和 O f），再计算每个个体的适应度所占的比例（fi广f），并以此作为相应的选择概率 （Ps）表2.1给出了选择4个个体的概率，由此概 率计算出每个个体被选择的次数表 2.1给出了相应的结果：个体 1和个体4各复制一份，个体2复制2份，个体3不复制而被淘汰这是所期待的结果，即最优秀的个体 （个体2，适应度为576）获得了最多的生存繁殖机会 （2份复制），最差的个体（个体3，适应度为64）被 淘汰。

由此得到的 4份复制送到配对库（mating pool），以备配对繁殖5. 交叉操作简单的交叉（即一点交叉）可分两步进行：首先对配对库中的个体进行随机配对；其次，在配对个体中随机设定交叉处 （表2.1中的配对库中的竖线表示交叉处 ），配对个体彼此交换部分信息由表 2.1可见，配对库中的个体 2与个体1配对，交叉处为 4,通过交叉得到了 两个新的个体：01100和11001同样，配对库中的个体 3和个体4的配对交叉（交叉处为2）得到另外两个新个体 11011和10000这4个新个体形成了新的群体，即新一代需要指出的是，交叉操作是遗传算法中最主要的遗传操作 由于交叉操作得到了新一代个体 仔细观察比较表2.1中的新旧个体，不难发现新群体中个体适应度的平均值和最大值都有了明显提 高由于这个例子的适应度函数也就是函数本身 f（x）=x2，所以函数值也变大了由此可见，新群体中的个体（即解）的确朝着期望的方向进化了6. 变异变异操作是按位进行的，即把某一位的内容进行变异对于二进制编码的个体来说，若某位原为0,则通过变异操作就变成了 1，反之亦然变异操作同样也是随机进行的一般而言，变异概率 Pm都取得很小。

在这个例子中，取 Pm=0.001，由于群体中共有 20 X0.00仁0.02位可以变异，这就意味群体中没有一位可变异 变异操作是十分微妙的遗传操作，它需要和交叉操作妥善配合使用， 目的是挖掘群体中个体的多样性， 克服有可能限于局部解的弊病在本例的模拟计算中， 仅通过一代进化就使问题的解得到了优化， 如果按表2.1那样进行多次迭代处理，或者说群体继续不断地一代代进化下去， 那么，最终一定可以得到最优解或近似最优解上述的遗传算法操作过程构成了标准的遗传算法 (Standard GA, SGA),有时也叫简单遗传算法，简称也是 SGA(Simple GA)通过上述的简单例子的讨论，不难发现，遗传算法所 依赖的两个必不可少而又最重要的操作 (即复制和交叉)，是出乎意料的简单可行除了随机数产生、串结构数据复制以及部分串结构数据互换外， 似乎没有更多更复杂行为在这种简单而似乎有些盲目的结构数据复制和重组的操作中， 遗传算法究竟做了些什么？其中是否存在某种规律或带有指导性的结论？以下将对这些问题进行深入的讨论7•遗传算法算例为了更清楚的地说明上述过程的细节，我们举一实例设休要解决的问题是：寻找f ( x ) =「X2 31 X 10这一函数，当自变量x在0-31之间取整数时函数值的最大值。

若要用枚举法来求解，则要比较 x从0至31的所有值，尽管此法是可靠的，但是这是一种效率低的方法而若要做到小数点后若干位，枚举法甚至由于计算工作量大而成为不可能 下面我们用遗传来求解这个问题1) 编码(coding )(解决初始化种群)其目的是将寻求优化解的参数用若干代码串来表示 这种代码就称为染色体，这一个过程称为编码编码的方法很多，最简单的办法是用二进制来编码 编码的基本要求是要为染色体的基因型(代码串)和表现型(参数值)建立对应关系采用二进制代码时，这种对应 关系就是二进制数与十进制数的转化关系在本例中， x值在0-31之间变化，所以有5位二进制代码串就可以组成所有染色体的基因型即所有的染色体基因型在 00000-11111之间接下来是要选择初始染色体种群的个体数及个体的具体基因型 一般种群的个体数要适中，太少了可能迭代次数要增加，甚至得不到结果，太大了会增加计算量，降低效率在本 例中我们设种群的大小为 4,即有4个个体基因型的选择是随机的，一般在 x值的定义域中较均匀地随机分布，例如在本例中，我们随机取 4个x值：1, 28, 8, 19相对应的4个基因型为：00001 , 11100, 01000, 10011。

这样便完成了遗传算法的准备工作，产生了初始染色体种群的基因型2) .计算适应度f i (fitness )决定适应度fi的计算公式，是一个技巧性很高的、而理论上的研究又很不充分的复杂问题一般要根据优化的目标函数来决定在本例中，选择求解最大值的函数 f ( x ) - -x 2 31 x 10来作适应度f i的计算公式对应所选的 4个个体，计算出的适应度f i的值分别是：40, 94,194, 238如表9-1所示表9-1复制操作之前的各项数据izh 口 串号初始种群 （基因型）x值（表现 型）适应度仃2f i = _x + 31 x + 10复制概 率/Zfi期望复制 数%复制数Ri1000011400.0710.284021110028940.1660.664130100081940.3431.3721410011192380.4201.6802总计5661.004.004平均141.50.251.001取大值2380.421.6802(3).复制(reproduct ion )按照达尔文的适者生存理论，愈能适应环境的生物品种，愈能繁衍（复制）其后代，而不适应环境的生物，其生存和繁衍的能力比较低，甚至被淘汰。

在本例中，初始种群的适应 度仁已计算出来复制的原则是：适应度f i愈高的染色体，其复制的可能及复制的数愈多具体的计算是利用随机方法来实现的首先按下式来计算复制概率 P i。