3遗传算法2.pptVIP

天津大学自动化学院 智能控制系统 天津大学电气与自动化工程学院 三 天津大学自动化学院 3. 遗传算法的理论基础 指导遗传算法的基本理论，是J.H.Holland教授创立的模式理论。该理论揭示了遗传算法的基本机理。 3.1 基本概念 问题的引出 例： 求 max f(x)=x2 x ∈ {0, 31} 天津大学自动化学院 3. 遗传算法的理论基础 [分析] ? 当编码的最左边字符为“1”时，其个体适配值较大，如2号个体和4号个体，我们将其记为 “ 1**** ”； 其中2号个体适配值最大，其编码的左边两位都是1，我们记为 “ 11*** ”； ? 当编码的最左边字符为“0”时，其个体适配值较小，如1号和3号个体，我们记为 “ 0**** ”。 天津大学自动化学院 3. 遗传算法的理论基础 [结论] 从这个例子可以看比，我们在分析编码字符串时，常常只关心某一位或某几位字符，而对其他字符不关心。换句话讲．我们只关心字符的某些特定形式，如 1****，11***，0**** 这种特定的组合形式就叫模式。 天津大学自动化学院 3. 遗传算法的理论基础 模式、模式位数及模式定义长度 模式(Schemata)——指编码的字符串在某些确定位置上具有相似性的位串子集的相似性模板。 使用三元素字母表 {0，1，*} 可以构造出任意模式。其中“*”称为通配符，表示这一位可以是{0，1}中任意一种。 使用大写字母H代表模式，例如H=1100* 天津大学自动化学院 3. 遗传算法的理论基础 匹配的定义 模式中的“0”和位串中的“0”匹配，模式中的“1”和位串中的“1”匹配，模式中的“*”和位串中的“0”或“1”匹配. 以五位二进制字符串为例。模式 *111* 可匹配4个个体： 01110，01111，11110，11111 模式 *0000 则匹配2个个体： 10000，00000 天津大学自动化学院 3. 遗传算法的理论基础 模式位数(Order)——指模式中有定义的非“*”位个数，记为O(H) 例如，若H=00*1*0，则O(H)=4 模式的定义长度（Defining Length）——指模式中最两端的有定义位置之间的距离，记为?(H) 例如，若H=00*1*0，则?(H)=6-1=5 若H=**11**，则?(H)=4-3=1 若H=******，则?(H)=0 天津大学自动化学院 3. 遗传算法的理论基础 模式长度越短，被破坏的可能性越小，长度为0的模式最难被破坏。 编码位串的模式数目 模式总数 二进制位串 假设字符串的长度为l，字符串中每一个字符可取( 0, 1, * ) 三个符号中任意一个，可能组成的模式数目最多为： 3×3×3×3×3…×3=3l 天津大学自动化学院 3. 遗传算法的理论基础 一般情况 假设字符的长度为l，字符串中有k种具体字符可取，可能组成的模式数目最多为： (k+1)× (k+1)× (k+1)× (k+1)× …× (k+1)= (k+1)l 某一特定编码串包含的模式数 二进制位串 对于长度为l的某二进制字符串，它含有的模式总数最多为： 2 ×2 ×2 × … ×2 = 2 l 天津大学自动化学院 3. 遗传算法的理论基础 [注]这个数目是指字符串已确定为0或1，每个字符只能在已定值 (0/1)或* 中选取。 某一特定群体所含模式数 在长度为l ，规模为n的二进制编码字符串群体中，一般包含有2 l ~ n · 2 l个模式。 天津大学自动化学院 3. 遗传算法的理论基础 3.2 模式定理 引入模式的概念之后，遗传算法的实质可看作是对模式的一种运算。对基本遗传算法(GA)而言，也就是某一模式H 的各个样本经过选择运算、交义运算、变异运算之后，得到一些新的样本和新的模式。 复制时的模式数目 [公式推导] 假设在第t次迭代时, 群体A(t)中有n个个体, 其中有m个符合特定模式Ｈ, 记作m(Ｈ,t)。 天津大学自动化学院 3. 遗传算法的理论基础 个体 Ａi 按其适配值 fi 的大小进行复制。从统计意义讲，个体Ａi被复制的概率pi是： 因此复制后在下一代群体 Ａ(t+1)中，群体内属于模式Ｈ（或称与模式Ｈ匹配）的个体数目 m(Ｈ,t+1) 可用平均适配值按下式近似计算(ｆ(Ｈ)是属于模式H的个体的平均适配值）： 天津大学自动化学