基本遗传算法GA课件

1、基本遗传算法GA 遗传算法在自然与社会现象模拟、工程计算等方面得到了广泛的应用。在各遗传算法在自然与社会现象模拟、工程计算等方面得到了广泛的应用。在各个不同的应用领域，为了取得更好的结果，人们对个不同的应用领域，为了取得更好的结果，人们对GA进行了大量的改进，为了进行了大量的改进，为了不至于混淆，我们把不至于混淆，我们把Holland提出的算法称为基本遗传算法，简称提出的算法称为基本遗传算法，简称 GA、SGA（Simple Genetic Algorithm )、CGA（Canonical Genetic Algorithm），将其它），将其它的的“GA类类”算法称为算法称为GAs(Gene

2、tic Algorithms）,可以把可以把GA看作是看作是GAs的一种特的一种特例。例。 基本遗传算法使用基本遗传算法使用来表示群体中的个体，其等位基来表示群体中的个体，其等位基 因由二值符号集因由二值符号集0，1组成。组成。 初始群体中各个个体的基因值用均匀分布的随机数来生成。如：初始群体中各个个体的基因值用均匀分布的随机数来生成。如： x；1101101 就可表示一个个体，该个体的染色体长度是就可表示一个个体，该个体的染色体长度是 l18。基本遗传算法GA 基本遗传算法基本遗传算法为正确计算这个概率，这里要求所有个体的适应为正确计算这个概率，这里要求所有个体的适应 度必须为正数或零。这样

3、，根据不同种类的问题，必须预先确定好由目标函数度必须为正数或零。这样，根据不同种类的问题，必须预先确定好由目标函数 值到个体适应度之间的转换规则，特别是要预先确定好当目标函数值为负数时值到个体适应度之间的转换规则，特别是要预先确定好当目标函数值为负数时 的处理方法。的处理方法。 基本遗传算法使用下述三种遗传算子：基本遗传算法使用下述三种遗传算子： 选择运算：使用选择运算：使用； 交叉运算：使用交叉运算：使用； 变异运算：使用变异运算：使用。 基本遗传算法有下述基本遗传算法有下述4个运行参数需要提前设定：个运行参数需要提前设定： ：群体大小，即群体中所含个体的数量，一般取为：群体大小，即群体中所

4、含个体的数量，一般取为20 100。 ：遗传运算的终止进化代数，一般取为：遗传运算的终止进化代数，一般取为100 500 ：交叉概率，一般取为：交叉概率，一般取为0.4 0.99 ：变异概率，一般取为：变异概率，一般取为 0.0001 0.1 基本遗传算法GA 这这4个运行参数对遗传算法的求解结果和求解效率都有一定的影响，但目前个运行参数对遗传算法的求解结果和求解效率都有一定的影响，但目前 尚无合理选择它们的理论依据。在遗传算法的实际应用中，往往需要经过多次试尚无合理选择它们的理论依据。在遗传算法的实际应用中，往往需要经过多次试 算后才能确定出这些参数合理的取值大小或取值范围。算后才能确定出这

5、些参数合理的取值大小或取值范围。 基本遗传算法可定义为一个基本遗传算法可定义为一个7元组：元组： M群体大小；群体大小； F个体适应度评价函数；个体适应度评价函数； s选择操作算子；选择操作算子； c交叉操作算子：交叉操作算子： m变异操作算子；变异操作算子； pc交叉概率；交叉概率； pm变异概率；变异概率；基本遗传算法GAProcedure GABegin initialize P(0); t=0; while (t=T) do for i=1 to M do Evaluate fitness of P(t); end for for i=1 to M do Select operatio

6、n to P(t); end for for i=1 to M/2 do Crossover operation to P(t); end for for i=1 to M do Mutation operation to P(t); end for for i=1 to M do P(t+1) = P(t); end for t=t+1 end whileend基本遗传算法GA 根据上面对基本遗传算法构成要素的分析和算法描述，我们可以很方便地用计根据上面对基本遗传算法构成要素的分析和算法描述，我们可以很方便地用计 算机语言来实现这个基本遗传算法。算机语言来实现这个基本遗传算法。 现对具体实现

7、过程中的问题作以下说明：现对具体实现过程中的问题作以下说明： 假设某一参数的取值范围是假设某一参数的取值范围是umin , umax，我们用长度为，我们用长度为l的二进制编码符号串的二进制编码符号串来表示该参数，则它总共能够产生来表示该参数，则它总共能够产生 2l种不同的编码，参数编码时的对应关系如种不同的编码，参数编码时的对应关系如下：下： 00000000000000000 umin 00000000000000011 umin + 00000000000000102 umin + 2 1111111111111111=2l1 umax 基本遗传算法GA x = umin + ( bi 2

8、i-1 ) 1 1i=lUmax umin2l 1 其中，其中， 为二进制编码的编码精度，其公式为：为二进制编码的编码精度，其公式为： = Umax umin2l 1 假设某一个体的编码是：假设某一个体的编码是： x： bl bl-1 bl-2b2b1 则对应的解码公式为：则对应的解码公式为：基本遗传算法GA例例 设设 -3.0 x 12.1 , 精度要求精度要求 =1/10000，由公式：，由公式： Umax umin2l =+ 11/1000012.1 + 3.0+ 1= 151001151001 即：即： 217 151001 00 if f(X)+Cmin 0F(X) =Cmax -

9、f(X) if f(X) Cmax0 if f(X) Cmax 基本遗传算法GA 从当前代群体中选择出一些比较优良的个体，并将其复制到下一代群体中。从当前代群体中选择出一些比较优良的个体，并将其复制到下一代群体中。 ： 比例选择算子。比例选择算子。 指个体被选中并遗传到下一代群体中的概率与该个体的适应度大小成正比。指个体被选中并遗传到下一代群体中的概率与该个体的适应度大小成正比。 轮盘法的基本精神是：个体被选中的概率取决于个体的相对适应度：轮盘法的基本精神是：个体被选中的概率取决于个体的相对适应度： pi = fi / fi ( i=1,2,M ) 式中式中 pi个体个体i被选中的概率；被选中

10、的概率； fi个体个体i的适应度；的适应度； fi群体的累加适应度。群体的累加适应度。 显然，个体适应度愈高，被选中的概率愈大。但是，适应度小的个体也有可显然，个体适应度愈高，被选中的概率愈大。但是，适应度小的个体也有可 能被选中，以便增加下一代群体的多样性。能被选中，以便增加下一代群体的多样性。基本遗传算法GA 图中指针固定不动，外圈的圆环可以图中指针固定不动，外圈的圆环可以 自由转动，自由转动， 圆环上的刻度代表各个个圆环上的刻度代表各个个 体的适应度。当圆环旋转若干圈后停止，体的适应度。当圆环旋转若干圈后停止， 指针指定的位置便是被选中的个体。指针指定的位置便是被选中的个体。 从统计意义

11、讲，适应度大的个体，其从统计意义讲，适应度大的个体，其 刻度长，被选中的可能性大；反之，适刻度长，被选中的可能性大；反之，适 应度小的个体被选中的可能性小，但有应度小的个体被选中的可能性小，但有 时也会被时也会被“破格破格”选中。选中。基本遗传算法GA 上述轮盘选择过程，可描述如下：上述轮盘选择过程，可描述如下： . 顺序累计群体内各个体的适应度，得相应的累计值顺序累计群体内各个体的适应度，得相应的累计值Si，最后一个累计值为，最后一个累计值为Sn； . 在在0, Sn区间内产生均匀分布的随机数区间内产生均匀分布的随机数r； . 依次用依次用Si与与r比较，第一个出现比较，第一个出现Si大于或

12、等于大于或等于r的个体的个体j被选为复制对象；被选为复制对象； . 重复重复 、 项，直至新群体的个体数目等于父代群体的规模。项，直至新群体的个体数目等于父代群体的规模。论盘选择示例论盘选择示例基本遗传算法GA 通过交叉，子代的基因值不同于父代。交换是遗传算法产生新个体的主要手段。通过交叉，子代的基因值不同于父代。交换是遗传算法产生新个体的主要手段。正是有了交换操作，群体的性态才多种多样。正是有了交换操作，群体的性态才多种多样。单点交叉算子。单点交叉算子。 . 对群体中的个体进行两两对群体中的个体进行两两随机随机配对。配对。 若群体大小为若群体大小为M，则共有，则共有 M/2 对相互对相互 配

13、对的个体组。配对的个体组。 . 每一对相互配对的个体，每一对相互配对的个体，随机随机设置某一基因座之后的位置为交叉点。设置某一基因座之后的位置为交叉点。 若染色体的长度为若染色体的长度为l ，则共有，则共有(l-1)个可能的交个可能的交叉点位置。叉点位置。 . 对每一对相互配对的个体，依设定的交叉概率对每一对相互配对的个体，依设定的交叉概率pc在其在其交交叉点处相互交换两个个叉点处相互交换两个个 体的部分染色体，从而产生出两个新的个体。体的部分染色体，从而产生出两个新的个体。 单点交叉运算的示单点交叉运算的示例例如下所示如下所示: 单点交叉单点交叉A；10110111 00 A：1011011

14、1 11B：00011100 11 B：00011100 00基本遗传算法GA pc = McM 式中式中 M群体中个体的数目；群体中个体的数目； Mc群体中被交换个体的数目。群体中被交换个体的数目。交叉操作示例交叉操作示例 交叉的个体是随机确定的，如下表所示。某群体有交叉的个体是随机确定的，如下表所示。某群体有n个个体，每个个体含个个体，每个个体含8 个等位基因。针对每个个体产生一个个等位基因。针对每个个体产生一个0, 1 区间的均匀随机数。假设交叉概率区间的均匀随机数。假设交叉概率 pc = 0.6，则随机数小于，则随机数小于0.6的对应个体与其随机确定的另一个个体交叉，交叉的对应个体与其

15、随机确定的另一个个体交叉，交叉 点随机确定。点随机确定。个体编号个体编号个体个体随机数随机数交叉操作交叉操作新个体新个体10.72820.589101010 11101010 0130.67840.801100011 01100011 11基本遗传算法GA 对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作 的某一基因座上的原有基因值为的某一基因座上的原有基因值为0，则变异操作将该基因值变为，则变异操作将该基因值变为1，反之，若原有，反之，若原有 基因值为基因值为1，则变异操作将其变为，则变异操作将其变为0。

16、 . 对个体的每一个基因座，依变异概率对个体的每一个基因座，依变异概率pm指定其为变异点。指定其为变异点。 . 对每一个指定的变异点，对其基因值做取反运算或用其它等位基因值来代替，对每一个指定的变异点，对其基因值做取反运算或用其它等位基因值来代替， 从而产生出一个新的个体。从而产生出一个新的个体。 基本位变异运算的示例如下所示：基本位变异运算的示例如下所示： A：1010 1 01010 A：1010 0 01010 变异点变异点基本位变异基本位变异基本遗传算法GA 变异是针对个体的某一个或某一些基因座上的基因值执行的，因此变异概率变异是针对个体的某一个或某一些基因座上的基因值执行的，因此变异

17、概率pm 也是针对基因而言，即：也是针对基因而言，即：式中式中 B每代中变异的基因数目；每代中变异的基因数目； M每代中群体拥有的个体数目每代中群体拥有的个体数目 l个体中基因串长度。个体中基因串长度。Pm = B M l 基本遗传算法GA变异操作示例变异操作示例 变异字符的位置是随机确定的，如下表所示。某群体有变异字符的位置是随机确定的，如下表所示。某群体有3个个体，每个体含个个体，每个体含4 个基因。针对每个个体的每个基因产生一个个基因。针对每个个体的每个基因产生一个0, 1 区间具有区间具有3位有效数字的均位有效数字的均 匀随机数。假设变异概率匀随机数。假设变异概率 pm = 0.01，

18、则随机数小于，则随机数小于0.01的对应基因值产生变的对应基因值产生变 异。表中异。表中3号个体的第号个体的第4位的随机数为位的随机数为0.001，小于，小于0.01，该基因产生变异，该基因产生变异， 使使3号个体由号个体由 0010 变为变为 0011 。其余基因的随机数均大于。其余基因的随机数均大于0.01，不产生变异。，不产生变异。基本遗传算法GA开开始始Gen=0编码编码随机产生随机产生M个初始个体个初始个体满足终止条件满足终止条件?计算群体中各个体适应度计算群体中各个体适应度从左至右依次执行遗传算子从左至右依次执行遗传算子j = 0j = 0j = 0根据适应度选择复制个体根据适应度

19、选择复制个体选择两个交叉个体选择两个交叉个体选择个体变异点选择个体变异点执行变异执行变异执行交叉执行交叉执行复制执行复制将复制的个体添入将复制的个体添入新群体中新群体中将交叉后的两个新个体将交叉后的两个新个体添入新群体中添入新群体中将变异后的个体添入将变异后的个体添入新群体中新群体中j = j+1j = j+2j = j+1 j = M? j = pcM? j = pmLM?Gen=Gen+1输出结果输出结果终终止止YNYYYNNNpcpm基本遗传算法GA。 例例 Rosenbrock函数的全局最大值计算。函数的全局最大值计算。 max f(x1,x2) = 100 (x12-x22)2 +

20、(1-x1)2 s.t. -2.048 xi 2.048 (xi=1,2)如图所示：如图所示：该函数有两个局部极大点，该函数有两个局部极大点，分别是分别是: f(2.048, -2048)=3897.7342 和和 f(-2.048,-2.0048)=3905.9262其中后者为全局最大点。其中后者为全局最大点。基本遗传算法GA：确定决策变量及其约束条件。：确定决策变量及其约束条件。 s.t. -2.048 xi 2.048 (xi=1,2)建立优化模型。建立优化模型。 max f(x1,x2) = 100 (x12-x22)2 + (1-x1)2确定编码方法。确定编码方法。 用长度为用长度为

21、l0l0位的二进制编码串来分别表示二个决策变量位的二进制编码串来分别表示二个决策变量x x1 1,x,x2 2。 lOlO位二进制编码串可以表示从位二进制编码串可以表示从0 0到到10231023之间的之间的10241024个不同的数，故将个不同的数，故将x x1 1,x,x2 2的的定义域离散化为定义域离散化为10231023个均等的区域，包括两个端点在内共有个均等的区域，包括两个端点在内共有10241024个不同的离散个不同的离散点。从离散点点。从离散点-2.048-2.048到离散点到离散点2.0482.048，依次让它们分别，依次让它们分别对应于从对应于从0000000000(0)到到

22、1111111111(1023)之间的二进制编码。再将分别表示之间的二进制编码。再将分别表示x x1 1和和x x2 2的二个的二个10位长的二进制位长的二进制编码串连接在一起，组成一个编码串连接在一起，组成一个20位长的二进制编码串，它就构成了这个函数优位长的二进制编码串，它就构成了这个函数优化问题的染色体编码方法。例如化问题的染色体编码方法。例如 X：0000110111 11011 10001 就表示一个个体的基因型。就表示一个个体的基因型。基本遗传算法GA确定解码方法。确定解码方法。 解码时先将解码时先将20位长的二进制编码串切断为二个位长的二进制编码串切断为二个10位长的二进制编码串

23、，然后位长的二进制编码串，然后分别将它们转换为对应的十进制整数代码，分别记为分别将它们转换为对应的十进制整数代码，分别记为y1和和y2。 依据前述个体编码方法相对定义域的离散化方法可知，将代码依据前述个体编码方法相对定义域的离散化方法可知，将代码yi转换为变量转换为变量xi的解码公式为：的解码公式为：例如，对前述个体例如，对前述个体 X： 0000110111 11011 10001 它由这样的两个代码所组成：它由这样的两个代码所组成： y1= 55 y2 = 881 经上式的解码处理后，得到：经上式的解码处理后，得到： x1= -1.828 x2= 1.476 xi = 4.096 yi 1

24、023 2.048 ( i = 1,2)基本遗传算法GA 确定个体评价方法。确定个体评价方法。 由式由式 f(x1,x2) = 100 (x12-x22)2 + (1-x1)2 可知，可知， Rosenbrock函数的值域总是函数的值域总是非负的，并且优化目标是求函数的最大值，故这里可将个体的适应度直接取为非负的，并且优化目标是求函数的最大值，故这里可将个体的适应度直接取为对应的目标函数值，并且不再对它作其他变换处理，即有：对应的目标函数值，并且不再对它作其他变换处理，即有： F(x) = f(x1,x2)设计遗传算子。设计遗传算子。 选择运算使用比例选择算子；选择运算使用比例选择算子； 交叉运算使用单点交叉算子；交叉运算使用单点交叉算子； 变异运算使用基本位变异算子。变异运算使用基本位变异算子。确定遗传算法的运行参数。确定遗传算法的运行参数。 对于本例，设定基本遗传算法的运行参数如下：对于本例，设定基本遗传算法的运行参数如下： 群体大小群体大小: M80 终止代数终止代数: T200 交叉概率：交叉概率：pc0.6 变异概率：变异概率：pm0.001基本遗传算法GA 下图