陕师大 计算机科学学院 雷秀娟1基本遗传算法The The Simple Simple GeneticGenetic Algorithms (SGA) Algorithms (SGA)陕西师范大学计算机科学学院雷秀娟陕师大 计算机科学学院 雷秀娟2基本遗传算法的描述1基本遗传算法的实现2基本遗传算法应用举例3主要内容l 遗传算法的构成要素l 遗传算法的形式化定义l 遗传算法的大致流程l 编码与解码l 群体的设置l 个体适应度评价l 比例选择算子l 单点交叉算子l 基本位变异算子l 算法流程图l 在函数优化中的应用4遗传算法的性能评估陕师大 计算机科学学院 雷秀娟3对于自然界中生物遗传与进化机理的模仿，针对不同的问题，很多学者设计了许多不同的编码方法来表示问题的可行解，开发出了许多种 不同的遗传算子来模仿不同环境下的生物遗传特性这样，由不同的编 码方法和不同的遗传算子就构成了各种不同的遗传算法这些遗传算法都有共同的特点，即通过对生物遗传和进化过程中选 择、交叉、变异机理的模仿,来完成对问题最优解的自适应搜索过程基 于这个共同特点，Goldberg总结出了一种统一的最基本的遗传算法—基 本遗传算法（Simple Genetic Algorithms,简称SGA）。
基本遗传算法只使用选择算子、交叉算子和变异算子这三种基本遗传算子，其遗传进化操作过程简单，容易理解，是其他一些遗传算法的 雏形和基础，它不仅给各种遗传算法提供了一个基本框架，同时也具有 一定的应用价值基本遗传算法的描述陕师大 计算机科学学院 雷秀娟4(1)(1) 染色体编码方法染色体编码方法基本遗传算法使用固定长度的二进制符号串来表示群体中的个体，其等位基因由二值符号集{0，1}组成初始群体中各个个体的基因值用均匀分布的随机数来生成如 ：x；100111001000101101就可表示一个个体，该个体的染色体长度是 l＝18 (2)(2) 个体适应度评价个体适应度评价基本遗传算法按与个体适应度成正比的概率来决定当前群体中每 个个体遗传到下一代群体中的机会多少为正确计算这个概率，这里 要求所有个体的适应度必须为正数或零这样，根据不同种类的问题 ，必须预先确定好由目标函数值到个体适应度之间的转换规则，特别 是要预先确定好当目标函数值为负数时的处理方法基本遗传算法的构成要素陕师大 计算机科学学院 雷秀娟5(3) (3) 遗传算子遗传算子基本遗传算法使用下述三种遗传算子：• 选择运算：使用比例选择算子；• 交叉运算：使用单点交叉算子；• 变异运算：使用基本位变异算子。
4) (4) 基本遗传算法的运行参数基本遗传算法的运行参数基本遗传算法有下述4个运行参数需要提前设定：• MM：群体大小，即群体中所含个体的数量，一般取为20 ~ 100• T T：遗传运算的终止进化代数，一般取为100 ~ 500• p pc c：交叉概率，一般取为0.4 ~ 0.99• p pmm：变异概率，一般取为 0.0001 ~ 0.1 [ [说明说明] ]这4个运行参数对遗传算法的求解结果和求解效率都有一定的影响，但目前尚无合理选择它们的理论依据在遗传算法的实际应用中，往往 需要经过多次试算后才能确定出这些参数合理的取值大小或取值范围陕师大 计算机科学学院 雷秀娟6基本遗传算法可定义为一个8元组：GAGA＝＝C—个体的编码方法；E—个体适应度评价函数；P0—初始群体； M—群体大小；—选择算子；—交叉算子；—变异算子；T—遗传运算终止条件 基本遗传算法的形式化定义陕师大 计算机科学学院 雷秀娟7Procedure GA Begininitialize P(0);t=0;while (t 00 if f(X)+Cmin ≤ 0(1) (1) 目标函数目标函数f(X)f(X)映射成适应度函数映射成适应度函数F(X)F(X)陕师大 计算机科学学院 雷秀娟21方法二方法二：对于求目标函数最小值的优化问题，变换方法为：其中，Cmax是一个适当地相对比较大的数，它可用下面几种方法求得：• 预先指定的一个较大的数。
• 进化到当前代为止的最大目标函数值• 当前代或最近几代群体中的最大目标函数值F(X) =Cmax - f(X) if f(X) Cmax0 if f(X) Cmax 陕师大 计算机科学学院 雷秀娟22在遗传进化的初期，通常会出现一些超常个体，若按比例选择策略，这些异常个体有可能在群体中占据很大的比例，导致未成熟收敛显然，这些异常个体因竞争力太突出，会控制选择过程，从而影响算法的全局优化性能另一方面，在遗传进化过程中，虽然群体中个体多样性尚存在，但往往会出现群体的平均适应度已接近最佳个体适应度，这时，个体间的竞争力相似，最佳个体和其它个体在选择过程中有几乎相等的选择机会，从而使有目标的优化过程趋于无目标的随机搜索过程2) (2) 适应度函数定标适应度函数定标陕师大 计算机科学学院 雷秀娟23l 对于未成熟收敛现象，应设法降低某些异常个体的竞争力，这可以通过缩小相应的适应度值来实现l 对于随机漫游现象，应设法提高个体间的竞争力差距，这可以通过放大相应的适应度值来实现l 这种适应度的缩放调整称为适应度定标常用适应度定标方法 ：l 线性定标（linear scaling ）f’ = af + bl 乘幂标f’ = fKl 指数定标f’ = exp(-bf)l 截断陕师大 计算机科学学院 雷秀娟24l 选择(复制)算子的作用：从当前代群体中选择出一些比较优良的个体，并将其复制到下一代群体中。
l 最常用和最基本的选择算子：比例选择算子，执行比例选择的手段是轮盘选择l 比例选择算子：指个体被选中并遗传到下一代群体中的概率与该个体的适应度大小成正比l 为了防止由于选择误差，或者交叉和变异的破坏作用而导致当前群体的最佳个体在下一代的丢失，De Jong提出了精英选择（elitist selection）策略和代沟的概念Holland等提出了稳态选择（steady-state selection）策略比例选择算子陕师大 计算机科学学院 雷秀娟25(1) (1) 轮盘选择的原理：轮盘选择的原理：图中指针固定不动，外圈的圆环可以自由转动， 圆环上的刻度代表各个个体的适应度当圆环旋转若干圈后停止，指针指定的位置便是被选中的个体从统计意义讲，适应度大的个体，其刻度长，被选中的可能性大；反之，适应度小的个体被选中的可能性小，但有时也会被“破格”选中陕师大 计算机科学学院 雷秀娟26个体被选中的概率取决于个体的相对适应度：pi = fi / fi ( i=1,2,…,M ) 式中pi——个体i被选中的概率；fi——个体i的适应度；fi——群体的累加适应度显然，个体适应度愈高，被选中的概率愈大。
但是，适应度小的个体也有可能被选中，以便增加下一代群体的多样性2) (2) 轮盘法的基本精神是：轮盘法的基本精神是：陕师大 计算机科学学院 雷秀娟27上述轮盘选择过程，可描述如下：Ⅰ. 顺序累计群体内各个体的适应度，得相应的累计值Si，最后一个累计值 为Sn；Ⅱ. 在[0, Sn]区间内产生均匀分布的随机数r；Ⅲ. 依次用Si与r比较，第一个出现Si大于或等于r的个体j被选为复制对象；Ⅳ. 重复 Ⅲ、Ⅳ 项，直至新群体的个体数目等于父代群体的规模3) (3) 轮盘选择示例：轮盘选择示例：陕师大 计算机科学学院 雷秀娟28l 交叉算子作用： 通过交叉，子代的基因值不同于父代交换是遗传算法产生新个体的主要手段正是有了交换操作，群体的性态才多种多样l 最常用和最基本：单点交叉算子l 单点交叉运算的示例如下所示:单点交叉算子单点交叉A；10110111 00 A’：10110111 11B：00011100 11 B’：00011100 00陕师大 计算机科学学院 雷秀娟29Ⅰ.对群体中的个体进行两两随机配对。
若群体大小为M，则共有[ M/2 ]对相互配对的个体组Ⅱ.每一对相互配对的个体，随机设置某一基因座之后的位置为交叉点若染色体的长度为L，则共有(L-1)个可能的交叉点位置Ⅲ.对每一对相互配对的个体，依设定的交叉概率Pc在其交叉点处相互交换两个个体的部分染色体，从而产生出两个新的个体1) (1) 单点交叉算子的具体计算过程如下：单点交叉算子的具体计算过程如下：(2) (2) 交叉概率交叉概率 pc = Mc M式中 M——群体中个体的数目；Mc——群体中被交换个体的数目陕师大 计算机科学学院 雷秀娟30l 基本位变异算子是最简单和最基本的变异操作算子对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则变异操作将该基因值变为1，反之，若原有基因值为1，则变异操作将其变为0l 基本位变异运算的示例如下所示：A：1010 1 01010 A’：1010 0 01010变异点基本位变异基本位变异算子陕师大 计算机科学学院 雷秀娟31变异是针对个体的某一个或某一些基因座上的基因值执行的，因此变异概率pm也是针对基因而言，即：式中 B——每代中变异的基因数目；M——每代中群体拥有的个体数目l——个体中基因串长度。
Pm = B M · l (2) (2) 变异概率变异概率(1) (1) 基本位变异因子的具体执行过程是：基本位变异因子的具体执行过程是：Ⅰ. 对个体的每一个基因座，依变异概率Pm指定其为变异点Ⅱ. 对每一个指定的变异点，对其基因值做取反运算或用其它等位基因值来代替，从而产生出一个新的个体陕师大 计算机科学学院 雷秀娟32变异字符的位置是随机确定的，如下表所示某群体有3个个体，每个体含4个基因针对每个个体的每个基因产生一个[0, 1] 区间具有3位有效数字的均匀随机数假设变异概率 pm = 0.01，则随机数小于0.01的对应基因值产生变异表中3号个体的第4位的随机数为0.001，小于0.01，该基因产生变异，使3号个体由 0010 变为 0011 其余基因的随机数均大于0.01，不产生变异3) (3) 变异操作示例变异操作示例陕师大 计算机科学学院 雷秀娟33开始Gen=0编码随机产生M个初始个体满足终止条件?计算群体中各个体适应度从左至右依次执行遗传算子j = 0j = 0j = 0根据适应度选择复制个体选择两个交叉个体选择个体变异点执行变异执行交叉执行复制将复制的个体添入 新群体中将交叉后的两个新个体 添入新群体中将变异后的个体添入 新群体中j = j+1j = j+2j = j+1j = M? j = pc·M? j = pm·L·M?Gen=Gen+1输出结果终止YNYYYNNNpcpm算法流程图陕师大 计算机科学学院 雷秀娟34[例] Rosenbrock函数的全局最大值计算。
max f(x1,x2) = 100 (x2-x12)2 + (1-x1)2s.t. -2.048 ≤ xi ≤ 2.048 (xi=1,2)如图所示：该函数有两个局部极大点，分别是:f(2.048, -2048)=3897.7342和f(-2.048,-2.0048)=3905.9262其中后者为全局最大点基本遗传算法在函数优化中的应用陕师大 计算机科学学院 雷秀娟35下面介绍求解该问题的遗传算法的构造过程：下面介绍求解该问题的遗传算法的构造过程：第一步：确定决策变量及其约束条件s.t. -2.048 ≤ xi ≤ 2.048 (xi=1,2)第二步：建。