《第三章遗传算法的理论基础》由会员分享，可在线阅读，更多相关《第三章遗传算法的理论基础（10页珍藏版）》请在金锄头文库上搜索。
1、.第三章 遗传算法的理论基础遗传算法有效性的理论依据为模式定理和积木块假设。模式定理保证了较优的模式的样本呈指数级增长,从而满足了寻找最优解的必要条件,即遗传算法存在着寻找到全局最优解的可能性。而积木块假设指出,遗传算法具备寻找到全局最优解的能力,即具有低阶、短距、高平均适应度的模式在遗传算子作用下,相互结合,能生成高阶、长距、高平均适应度的模式,最终生成全局最优解。Holland的模式定理通过计算有用相似性,即模式奠定了遗传算法的数学基础。该定理是遗传算法的主要定理,在一定程度上解释了遗传算法的机理、数学特性以及很强的计算能力等特点。3.1 模式定理不失一般性,本节以二进制串作为编码方式来讨
2、论模式定理。定义3.1基于三值字符集0,1,*所产生的能描述具有某些结构相似性的0、1字符串集的字符串称作模式。以长度为5的串为例,模式*0001描述了在位置2、3、4、5具有形式0001的所有字符串,即 。由此可以看出,模式的概念为我们提供了一种简洁的用于描述在某些位置上具有结构相似性的0、1字符串集合的方法。引入模式后,我们看到一个串实际上隐含着多个模式 ,一个模式可以隐含在多个串中,不同的串之间通过模式而相互联系。遗传算法中串的运算实质上是模式的运算。因此,通过分析模式在遗传操作下的变化,就可以了解什么性质被延续,什么性质被丢弃,从而把握遗传算法的实质,这正是模式定理所揭示的内容定义3.
3、2 模式H中确定位置的个数称作该模式的阶数,记作o。比如,模式 011*1*的阶数为4,而模式 0* * * * *的阶数为1。显然,一个模式的阶数越高,其样本数就越少,因而确定性越高。定义3.3 模式中第一个确定位置和最后一个确定位置之间的距离称作该模式的定义距,记作。比如,模式 011*1*的定义距为4,而模式 0* * * * *的定义距为0。模式的阶数和定义距描述了模式的基本性质。下面通过分析遗传算法的三种基本遗传操作对模式的作用来讨论模式定理。令表示第代中串的群体,以表示第代中第个个体串。1选择算子在选择算子作用下,与某一模式所匹配的样本数的增减依赖于模式的平均适值,与群体平均适值之
4、比,平均适值高于群体平均适值的将呈指数级增长；而平均适值低于群体平均适值的模式将呈指数级减少。其推导如下：设在第代种群中模式所能匹配的样本数为,记为。在选择中,一个位串以概率被选中并进行复制,其中是个体的适应度。假设一代中群体大小为,且个体两两互不相同,则模式在第代中的样本数为： 式中,是在时刻对应于模式的位串的平均适值。令群体平均适值为,则有= 现在,假定模式的平均适值高于群体平均适值,且设高出部分为为常数,则有= 假设从开始,保持为常值,则有 2交叉算子然而仅有选择操作,并不能产生新的个体,即不能对搜索空间中新的区域进行搜索,因此引入了交叉操作。下面讨论模式在交叉算子作用下所发生的变化,这
5、里我们只考虑单点交叉的情况。模式只有当交叉点落在定义距之外才能生存。在简单交叉 下的生存概率。例如一个长度为5的串以及隐含其中的两个模式为A = 010110H1 = *1* * *0H2 =* * *11* 我们注意到模式H1的定义距为4,那么交叉点在6-1=5个位置随机产生时,H1遭破坏的概率,即生存概率为。而交叉本身也是以一定的概率发生的,所以模式的生存概率为 现在我们考虑交叉发生在定义距内,模式不被破坏的可能性。在前面的例子中,若与交叉的串在位置2、6上有一位与相同,则H1将被保留。考虑到这一点,式 给出的生存概率只是一个下界,即有 可见,模式在交叉算子作用下长度短的模式将增多。3变异
6、算子假定串的某一位置发生改变的概率为,则该位置不变的概率为1,而模式在变异算子作用下若要不受破坏,则其中所有的确定位置 必须保持不变。因此模式保持不变的概率为,其中为模式H的阶数。当时,模式H在变异算子作用下的生存概率为 综上所述,模式在遗传算子选择、交叉和变异的共同作用下,其子代的样本数为 式 忽略了极小项。通过式 ,我们就可以给出模式定理。定理3.1在遗传算子选择、交叉和变异的作用下,具有阶数低、长度短、平均适值高于群体平均适应度的模式在子代中将以指数级增长。统计学的研究表明：在随机搜索中,要获得最优的可行解,则必须保证较优解的样本呈指数级增长,而模式定理保证了较优的模式 的样本呈指数级增
7、长,从而给出了遗传算法的理论基础。另外,由于遗传算法总能以一定的概率遍历到解空间的每一个部分,因此在选择算子的条件下总能得到问题的最优解。3.2 积木块假设由模式定理可知,具有阶数低、长度短、平均适值高于群体平均适值的模式在子代中将以指数级增长。这类模式在遗传算法中非常重要,在这一节给这些模式一个特别的名字积木块。定义3.4 阶数低、长度短和适值高的模式称为积木块。由模式定理可知,积木块将以指数级增长。正如搭积木一样,这些好的模式在遗传操作下相互拼搭、结合,产生适应度更高的串,从而得到更优的可行解,这正是积木块假设所揭示的内容。假设3.1积木块假设 阶数低、长度短、适应度高的模式 在遗传算子作
8、用下,相互结合,能生成阶数高、长度长、适值高的模式,可最终生成全局最优解。与积木块一样,一些好的模式在遗传算法操作下相互拼搭、结合,产生适应度更高的串,从而找到更优的可行解,这正是积木块假设所揭示的内容。下面用图来说明遗传算法中积木块生成最优解的过程。假设每代种群规模为8,Si表示每代群体中第i个个体,问题的最优解由积木块AA、BB、CC组成。图3.1为初始种群,个体S1、S7含有AA,个体S4、S8含有BB,个体S3含有CC。S1AAS2S3CCS4BBS5S6S7AAS8BB图3.1 初始种群当种群进化一代后,图3.2为第二代种群,个体S1、S3、S7含有AA,个体S2、S7含有BB,个体
9、S3、S6含有CC。个体S3含有AA、CC,个体S7含有AA、BB。当种群进化到第二代后,图3.3为第三代种群,在群体中,出现了含有积木块AA、BB、CC的个体S3,个体S3就是问题的最优解。S1AAS2BBS3AACCS4S5S6CCS7AABBS8图3.2 第二代种群S1AAS2BBS3AABBCCS4S5S6BBS7AACCS8图3.3 第三代种群模式定理保证了较优的模式 样本数呈指数增长,从而满足了寻找最优解的必要条件,即遗传算法存在着寻找到全局最优解的可能性。而这里的积木块假设则指出,遗传算法具备找到全局最优解的能力,即积木块在遗传算子作用下,能生成阶数高、长度长、适应度高的模式,最
10、终生成全局最优解。3.3 欺骗问题在遗传算法中,将所有妨碍适应度高的个体的生成从而影响遗传算法正常工作的问题统称为欺骗问题。遗传算法运行过程具有将阶数低、长度短、平均适应度高于群体平均适应度的模式重组成高阶模式的趋势。如果在低阶模式中包含了最优解,则遗传算法就可能找出这个最优解来。但是低阶、高适应度的模式可能没有包含最优串的具体取值,于是遗传算法就会收敛到一个次优的结果。下面给出有关欺骗性的概念。定义3.5 若模式和中,* 的位置完全一致,但任一确定位的编码均不同,则称和互为竞争模式。定义3.6 假设的最大值对应的的集合为,为一包含的阶模式。的竞争模式为,而且,则为阶欺骗。定义3.7 在欺骗问
11、题中,为了造成骗局所需设置的最小的问题规模 。其主要思想是在最大程度上违背积木块假设,是优于由平均的短积木块生成局部最优点的方法。这里的最小是指问题规模采用两位。下面是一个由4个阶数为2、有2个确定位置的模式集：为简单 起见,我们不考虑 * 位,令为全局最优解,为了欺骗遗传算法,Goldberg设计了两种情况：Type1：Type2：满足或者。按Holland的模式定理,最小欺骗问题将给遗传算法造成很大困难,遗传算法甚至找不到最优解。但Goldberg实验的结果却是：Type1问题基本上都很快找到了最优解,Type2问题找到和找不到两种情况都可能出现。遗传算法中欺骗性的产生往往与适应度函数确定
12、和调整、基因编码方式选取相关。采用合适的编码方式或调整适应度函数,就可能化解和避免欺骗问题。下面以合适的编码方式为例来说明。一个2位编码的适应度函数为采用二进制编码,计算个体的函数值见表3.1,则存在第二类欺骗问题。采用格雷编码,计算个体的函数值见表3.2,则第二类欺骗问题化解为第一类欺骗问题。表3.1 二进制编码及函数值 表3.2 格雷编码及函数值.编码对应整数解函数值0004011310211135编码对应整数解函数值0004011311211035.采用适当的适应度函数调整方法,设：如果适应度函数,则故存在欺骗问题。如果用适应度函数的调整方法,则得,故不会产生欺骗问题。3.4 遗传算法的
13、未成熟收敛问题及其防止在实际中,很多参数优化问题是多参数和非线性的,且往往还伴随着不可微和参数耦合等问题。这时用传统的优化方法解决这种问题,效率很低,有时候甚至根本得不出结果。遗传算法的高鲁棒性和有效性为解决这类问题提供了一种有效的途径。在实际应用中,遗传算法显示出了顽强的生命力,以其突出的优点而越来越受到重视。但是遗传算法也存在着缺点,在实际应用中也因此出现了一些问题,其中很重要的是遗传算法未成熟收敛 问题。对于遗传算法的应用,解决未成熟收敛问题是必要的,否则,遗传算法的一些优良性能 将无法完全体现出来。3.4.1 遗传算法的未成熟收敛问题1未成熟收敛现象未成熟收敛现象主要表现在两个方面：(1) 体中所有的个体都陷于同一极值而停止进化。(2) 接近最优解的个体总是被淘汰,进化过程不收敛。未成熟收敛现象是遗传算法中的特有现象,且十分常见。它指的是,当还未达到全局最优解或满意解时,群体中不能再产生性能超过父代的后代,群体中的各个个体非常相似。未成熟收敛的重要特征是群体中个体结构的多样性急剧减少。这将导致遗传算法的交叉算子和选择算子不能再产生更有生命力的新个体。遗传算法希望找到最优解或满意解,而不是在找到最优解或满意解之前,整个群体就收敛到一个非优个体,它希望能
