第二章 基本遗传算法（GA） 2.1 基本遗传算法描述 基本遗传算法的构成要素 (1) 染色体编码方法

Presentation on theme: "第二章 基本遗传算法（GA） 2.1 基本遗传算法描述 基本遗传算法的构成要素 (1) 染色体编码方法"— Presentation transcript:

1 第二章 基本遗传算法（GA） 2.1 基本遗传算法描述 2.1.1 基本遗传算法的构成要素 (1) 染色体编码方法
2.1 基本遗传算法描述 遗传算法在自然与社会现象模拟、工程计算等方面得到了广泛的应用。在各个不同的应用领域，为了取得更好的结果，人们对GA进行了大量的改进，为了不至于混淆，我们把Holland提出的算法称为基本遗传算法，简称 GA、SGA（Simple Genetic Algorithm )、CGA（Canonical Genetic Algorithm），将其它的“GA类”算法称为GAs(Genetic Algorithms）,可以把GA看作是GAs的一种特例。 基本遗传算法的构成要素 (1) 染色体编码方法 基本遗传算法使用固定长度的二进制符号串来表示群体中的个体，其等位基 因由二值符号集{0，1}组成。 初始群体中各个个体的基因值用均匀分布的随机数来生成。如： x； 就可表示一个个体，该个体的染色体长度是 l＝18。

2 (2) 个体适应度评价 基本遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体遗传 到下一代群体中的机会多少。为正确计算这个概率，这里要求所有个体的适应 度必须为正数或零。这样，根据不同种类的问题，必须预先确定好由目标函数 值到个体适应度之间的转换规则，特别是要预先确定好当目标函数值为负数时 的处理方法。 (3) 遗传算子 基本遗传算法使用下述三种遗传算子： • 选择运算：使用比例选择算子； • 交叉运算：使用单点交叉算子； • 变异运算：使用基本位变异算子。 (4) 基本遗传算法的运行参数 基本遗传算法有下述4个运行参数需要提前设定： • M：群体大小，即群体中所含个体的数量，一般取为20 ~ 100。 • T：遗传运算的终止进化代数，一般取为100 ~ 500 • pc：交叉概率，一般取为0.4 ~ 0.99 • pm：变异概率，一般取为 ~ 0.1

3 2.1.2 基本遗传算法的形式化定义 [说明] 这4个运行参数对遗传算法的求解结果和求解效率都有一定的影响，但目前
尚无合理选择它们的理论依据。在遗传算法的实际应用中，往往需要经过多次试 算后才能确定出这些参数合理的取值大小或取值范围。 2.1.2 基本遗传算法的形式化定义 基本遗传算法可定义为一个7元组： GA＝ (M, F, s, c, m, pc, pm ) M——群体大小； F——个体适应度评价函数； s——选择操作算于； c——交叉操作算子： m——变异操作算于； pc——交叉概率； pm——变异概率；

4 2.1.3 基本遗传算法描述 Procedure GA Begin initialize P(0); t=0;
基本遗传算法描述 Procedure GA Begin initialize P(0); t=0; while (t<=T) do for i=1 to M do Evaluate fitness of P(t); end for Select operation to P(t); for i=1 to M/2 do Crossover operation to P(t); for i=1 to M do Mutation operation to P(t); P(t+1) = P(t); t=t+1 end while end

5 2.2 基本遗传算法的实现 根据上面对基本遗传算法构成要素的分析和算法描述，我们可以很方便地用计 算机语言来实现这个基本遗传算法。
2.2 基本遗传算法的实现 根据上面对基本遗传算法构成要素的分析和算法描述，我们可以很方便地用计 算机语言来实现这个基本遗传算法。 现对具体实现过程中的问题作以下说明： 2.2.1 编码与解码 (1) 编码 假设某一参数的取值范围是[umin , umax]，我们用长度为l的二进制编码符号串来表示该参数，则它总共能够产生 2l种不同的编码，参数编码时的对应关系如下： … ＝ umin … ＝ umin +  … ＝ umin + 2 …… … =2l– umax

6  = Umax  umin Umax  umin
其中， 为二进制编码的编码精度，其公式为：  = Umax  umin 2l  1 (2) 解码 假设某一个体的编码是： x： bl bl-1 bl-2……b2b1 则对应的解码公式为： x = umin + (  bi · 2i-1 ) · 1 i=l Umax  umin 2l  1

7  = Umax  umin  Umax  umin + 1 1/10000 12.1 + 3.0
2l  1 [例] 设 ≤ x ≤ , 精度要求 =1/10000，由公式：  Umax  umin 2l = + 1 1/10000 = = 得： 即： 217 < < 218 x需要18位 {0/1} 符号表示。 如： 解码： x = umin + (  bi · 2i-1) · 1 i=l Umax  umin 2l  1 = (12.1+3)/(218-1) =

8 2.2.2 个体适应度评价 如前所述，要求所有个体的适应度必须为正数或零，不能是负数。
个体适应度评价 如前所述，要求所有个体的适应度必须为正数或零，不能是负数。 (1) 当优化目标是求函数最大值，并且目标函数总取正值时，可以直接设定个体 的适应度F(X)就等于相应的目标函数值f(X)，即： F(X)＝f(X) (2) 对于求目标函数最小值的优化问题，理论上只需简单地对其增加一个负号就 可将其转化为求目标函数最大值的优化问题，即： min f(X)＝max ( - f(X)) 但实际优化问题中的目标函数值有正也有负，优化目标有求函数最大值，也有 求函数最小值，显然上面两式保证不了所有情况下个体的适应度都是非负数这个 要求。

9 基本遗传算法一般采用下面两种方法之一将目标函数值 f(x)变换为个体的适应度F(x)：
方法一：对于求目标函数最大值的优化问题，变换方法为： 其中，Cmin为一个适当地相对比较小的数，它可用下面方法之一来选取： • 预先指定的一个较小的数。 • 进化到当前代为止的最小目标函数值。 • 当前代或最近几代群体中的最小目标函数值。 方法二：对于求目标函数最小值的优化问题，变换方法为： 其中，Cmax是一个适当地相对比较大的数，它可用下面几种方法求得： • 预先指定的一个较大的数。 • 进化到当前代为止的最大目标函数值。 • 当前代或最近几代群体中的最大目标函数值。 F(X) = f(X)+Cmin if f(X)+Cmin> 0 if f(X)+Cmin ≤ 0 F(X) = Cmax - f(X) if f(X)  Cmax if f(X)  Cmax

10 2.2.3 比例选择算子 (1) 选择算子或复制算子的作用： 从当前代群体中选择出一些比较优良的个体，并将其复制到下一代群体中。
比例选择算子 (1) 选择算子或复制算子的作用： 从当前代群体中选择出一些比较优良的个体，并将其复制到下一代群体中。 (2) 最常用和最基本的选择算子： 比例选择算子。 (3) 比例选择算子： 指个体被选中并遗传到下一代群体中的概率与该个体的适应度大小成正比。 (4) 执行比例选择的手段是轮盘选择。 轮盘法的基本精神是：个体被选中的概率取决于个体的相对适应度： pi = fi / fi ( i=1,2,…,M ) 式中 pi——个体i被选中的概率； fi——个体i的适应度； fi——群体的累加适应度。 显然，个体适应度愈高，被选中的概率愈大。但是，适应度小的个体也有可 能被选中，以便增加下一代群体的多样性。

11 轮盘选择的原理： 图中指针固定不动，外圈的圆环可以 自由转动， 圆环上的刻度代表各个个 体的适应度。当圆环旋转若干圈后停止， 指针指定的位置便是被选中的个体。 从统计意义讲，适应度大的个体，其 刻度长，被选中的可能性大；反之，适 应度小的个体被选中的可能性小，但有 时也会被“破格”选中。

12 [论盘选择示例] 上述轮盘选择过程，可描述如下： Ⅰ. 顺序累计群体内各个体的适应度，得相应的累计值Si，最后一个累计值为Sn； Ⅱ. 在[0, Sn]区间内产生均匀分布的随机数r； Ⅲ. 依次用Si与r比较，第一个出现Si大于或等于r的个体j被选为复制对象； Ⅳ. 重复 Ⅲ、Ⅳ 项，直至新群体的个体数目等于父代群体的规模。

13 单点交叉算子 (1) 交叉算子作用 通过交叉，子代的基因值不同于父代。交换是遗传算法产生新个体的主要手段。正是有了交换操作，群体的性态才多种多样。 (2) 最常用和最基本——单点交叉算子。 (3) 单点交叉算子的具体计算过程如下： Ⅰ. 对群体中的个体进行两两随机配对。 若群体大小为M，则共有 [ M/2 ]对相互 配对的个体组。 Ⅱ. 每一对相互配对的个体，随机设置某一基因座之后的位置为交叉点。 若染色体的长度为l ，则共有(l-1)个可能的交叉点位置。 Ⅲ. 对每一对相互配对的个体，依设定的交叉概率pc在其交叉点处相互交换两个个 体的部分染色体，从而产生出两个新的个体。 单点交叉运算的示例如下所示: 单点交叉 A； A’： B： B’：

14 交叉概率 pc = Mc M 式中 M——群体中个体的数目； Mc——群体中被交换个体的数目。 [交叉操作示例] 交叉的个体是随机确定的，如下表所示。某群体有n个个体，每个个体含8 个等位基因。针对每个个体产生一个[0, 1] 区间的均匀随机数。假设交叉概率 pc = 0.6，则随机数小于0.6的对应个体与其随机确定的另一个个体交叉，交叉 点随机确定。 个体编号 个体 随机数 交叉操作 新个体 1 0.728 2 0.589 3 0.678 4 0.801 …

15 2.2.5 基本位变异算子 基本位变异算子是最简单和最基本的变异操作算子。
基本位变异算子 基本位变异算子是最简单和最基本的变异操作算子。 对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作 的某一基因座上的原有基因值为0，则变异操作将该基因值变为1，反之，若原有 基因值为1，则变异操作将其变为0。 基本位变异因子的具体执行过程是： Ⅰ. 对个体的每一个基因座，依变异概率pm指定其为变异点。 Ⅱ. 对每一个指定的变异点，对其基因值做取反运算或用其它等位基因值来代替， 从而产生出一个新的个体。 基本位变异运算的示例如下所示： A： A’： 基本位变异 变异点

16 变异概率 变异是针对个体的某一个或某一些基因座上的基因值执行的，因此变异概率pm 也是针对基因而言，即： Pm = B M · l 式中 B——每代中变异的基因数目； M——每代中群体拥有的个体数目 l——个体中基因串长度。

17 [变异操作示例] 变异字符的位置是随机确定的，如下表所示。某群体有3个个体，每个体含4 个基因。针对每个个体的每个基因产生一个[0, 1] 区间具有3位有效数字的均 匀随机数。假设变异概率 pm = 0.01，则随机数小于0.01的对应基因值产生变 异。表中3号个体的第4位的随机数为0.001，小于0.01，该基因产生变异， 使3号个体由 0010 变为 0011 。其余基因的随机数均大于0.01，不产生变异。

18 2.2.6 算法流程图 Y N pm pc 开始 Gen=0 编码 随机产生M个初始个体 满足终止条件? 计算群体中各个体适应度
从左至右依次执行遗传算子 j = 0 根据适应度选择复制个体 选择两个交叉个体 选择个体变异点 执行变异 执行交叉 执行复制 将复制的个体添入新群体中 将交叉后的两个新个体添入新群体中 将变异后的个体添入新群体中 j = j+1 j = j+2 j = M? j = pc·M? j = pm·L·M? Gen=Gen+1 输出结果 终止 Y N pc pm 算法流程图

19 2.3 基本遗传算法应用举例 —— 基本遗传算法在函数优化中的应用。
[例] Rosenbrock函数的全局最大值计算。 max f(x1,x2) = 100 (x12-x22)2 + (1-x1)2 s.t ≤ xi ≤ (xi=1,2) 如图所示： 该函数有两个局部极大点， 分别是: f(2.048, -2048)= 和 f(-2.048, )= 其中后者为全局最大点。

20 下面介绍求解该问题的遗传算法的构造过程：
第一步：确定决策变量及其约束条件。 s.t ≤ xi ≤ (xi=1,2) 第二步：建立优化模型。 max f(x1,x2) = 100 (x12-x22)2 + (1-x1)2 第三步；确定编码方法。 用长度为l0位的二进制编码串来分别表示二个决策变量x1,x2。 lO位二进制编码串可以表示从0到1023之间的1024个不同的数，故将x1,x2的定义域离散化为1023个均等的区域，包括两个端点在内共有1024个不同的离散点。从离散点-2.048到离散点2.048，依次让它们分别对应于从 (0)到 (1023)之间的二进制编码。再将分别表示x1和x2的二个10位长的二进制编码串连接在一起，组成一个20位长的二进制编码串，它就构成了这个函数优化问题的染色体编码方法。例如 X： 就表示一个个体的基因型。

21 第四步：确定解码方法。 解码时先将20位长的二进制编码串切断为二个10位长的二进制编码串，然后分别将它们转换为对应的十进制整数代码，分别记为y1和y2。 依据前述个体编码方法相对定义域的离散化方法可知，将代码yi转换为变量xi的解码公式为： xi =  yi 1023  ( i = 1,2) 例如，对前述个体 X： 它由这样的两个代码所组成： y1= 55 y2 = 881 经上式的解码处理后，得到： x1= x2= 1.476

22 第五步：确定个体评价方法。 由式 f(x1,x2) = 100 (x12-x22)2 + (1-x1) 可知， Rosenbrock函数的值域总是非负的，并且优化目标是求函数的最大值，故这里可将个体的适应度直接取为对应的目标函数值，并且不再对它作其他变换处理，即有： F(x) = f(x1,x2) 第六步：设计遗传算子。 选择运算使用比例选择算子； 交叉运算使用单点交叉算子； 变异运算使用基本位变异算子。 第七步：确定遗传算法的运行参数。 对于本例，设定基本遗传算法的运行参数如下： 群体大小: M＝80 终止代数: T＝200 交叉概率：pc＝0.6 变异概率：pm＝0.001

23 下图为其进化过程示例及运行结果。 图中两条曲线分别为各代群体中个体适应度的最大值和平均值。

24 下图所示分别为初始群体、第5代群体、第10代群体和第100代群体中个体的分布情况。
在图(a)中各个个体分布得比较均匀。 (a)

25 在图(b)中大量的个体分布在最优点和次最优点附近。

26 从图(c) 中可以看出，次最优点也被淘汰。

27 (d) 从图(d)中可以看出，个体更加集中在最优点附近。
由该组图我们可以看出，随着进化过程的进行，群体中适应度较低的一些个体被逐渐淘汰掉，而适应度较高的一些个体会越来越多．并且它们都集中在所求问题的最优点附近，从而最终就可搜索到问题的最优解。