遗传算法的理论基础

《遗传算法的理论基础》由会员分享，可在线阅读，更多相关《遗传算法的理论基础（17页珍藏版）》请在装配图网上搜索。

1、WORD格式可编辑第三章遗传算法的理论基础遗传算法有效性的理论依据为模式定理和积木块假设。模式定理保证了较优的模式(遗传算法的较优解)的样本呈指数级增长，从而满足了寻找最优解的必要条件，即遗传算法存在着 寻找到全局最优解的可能性。而积木块假设指出，遗传算法具备寻找到全局最优解的能力， 即具有低阶、短距、高平均适应度的模式(积木块)在遗传算子作用下，相互结合，能生成高阶、 长距、高平均适应度的模式，最终生成全局最优解。Holla nd的模式定理通过计算有用相似性，即模式(Pattern)奠定了遗传算法的数学基础。该定理是遗传算法的主要定理，在一定程度上解 释了遗传算法的机理、数学特性以及很强的计

2、算能力等特点。3.1模式定理不失一般性，本节以二进制串作为编码方式来讨论模式定理(Pattern Theorem)。定义3.1基于三值字符集0,1，*所产生的能描述具有某些结构相似性的0、1字符串集的字符串称作模式。以长度为5的串为例，模式*0001描述了在位置2、3、4、5具有形式“0001的所有字符串， 即(00001 , 10001)。由此可以看出，模式的概念为我们提供了一种简洁的用于描述在某些位 置上具有结构相似性的0、1字符串集合的方法。引入模式后，我们看到一个串实际上隐含着多个模式(长度为n的串隐含着2n个模式)，一个模式可以隐含在多个串中，不同的串之间通过模式而相互联系。遗传算法

3、中串的运算实 质上是模式的运算。因此，通过分析模式在遗传操作下的变化，就可以了解什么性质被延续， 什么性质被丢弃，从而把握遗传算法的实质，这正是模式定理所揭示的内容定义3.2模式H中确定位置的个数称作该模式的阶数，记作o(H)。比如，模式 011*1*的阶数为4，而模式0* * * * *的阶数为1。显然，一个模式的阶数越高，其样本数就越少，因而确定性越高。定义3.3 模式H中第一个确定位置和最后一个确定位置之间的距离称作该模式的定义 距，记作、：(H)。比如，模式 011*1*的定义距为4,而模式 0* * * *的定义距为0。模式的阶数和定义距描述了模式的基本性质。下面通过分析遗传算法的三

4、种基本遗传操作对模式的作用来讨论模式定理。令A(t)表示第t代中串的群体，以Aj(t)(j =1,2,，n)表示第t代中第j个个体串。1 选择算子在选择算子作用下，与某一模式所匹配的样本数的增减依赖于模式的平均适值，与群体 平均适值之比，平均适值高于群体平均适值的将呈指数级增长；而平均适值低于群体平均适 值的模式将呈指数级减少。其推导如下：设在第t代种群A(t)中模式所能匹配的样本数为m，记为m(H ,t)。在选择中，一个位串Aj以概率Pj =fj/v fi被选中并进行复制，其中fj是个体Aj (t)的适应度。假设一代中群体大小为n，且个体两两互不相同，则模式 H在第t 1代中的样本数为：m(

5、H,t 1) = m(H,t)(3.1)Z fi式中，f(H)是在t时刻对应于模式的位串的平均适值。令群体平均适值为ffj n，则有f (H )m(H ,t 1) =m(H ,t)-(3.2)f现在，假定模式 H的平均适值高于群体平均适值，且设高出部分为cf , C为常数，则有(3.3)(3.4)m(H ,t 1) =m(H ,t) f C f = (1 c)m(H ,t)假设从t =0开始，c保持为常值，则有m(H,t 1) =m(H ,0)(1 c)2 .交叉算子然而仅有选择操作，并不能产生新的个体，即不能对搜索空间中新的区域进行搜索，因 此引入了交叉操作。下面讨论模式在交叉算子作用下所发

6、生的变化，这里我们只考虑单点交 叉的情况。模式H只有当交叉点落在定义距之外才能生存。在简单交叉(单点交叉)下H的生存概率Ps =1 f(H)/(t-1)。例如一个长度为5的串以及隐含其中的两个模式为A = 010110H1* * *0H2 =11专业知识分享我们注意到模式H1的定义距为4，那么交叉点在6-仁5个位置随机产生时，H1遭破坏的概率Pd八(H2)/(m-1) =1/5，即生存概率为4/5。而交叉本身也是以一定的概率巳发生的，所以模式 H的生存概率为Ps=1PcPd =1巳石(H2)/(m 1)(3.5)现在我们考虑交叉发生在定义距内， 模式H不被破坏的可能性。在前面的例子中，若与A

7、交叉的串在位置2、6上有一位与A相同，则H1将被保留。考虑到这一点，式 (3.5)给出的生存 概率只是一个下界，即有(3.6)Ps1-R、(H)/(m-1)可见，模式在交叉算子作用下长度短的模式将增多。3 变异算子假定串的某一位置发生改变的概率为Pm，则该位置不变的概率为1- Pm，而模式H在变异算子作用下若要不受破坏，则其中所有的确定位置(或 的位)必须保持不变。因此模式H保持不变的概率为(1 - Pm)0(H)，其中0(H)为模式H的阶数。当Pm 0或。=1，q=0时，称人具有q超线性收敛速度。(3) 当- =2时，称xj具有q二阶收敛速度。具有超线性收敛速度和二阶收敛速度的迭代算法的收敛

8、速度比较快。关于算法的终止准则，实际应用中可以使用各种不同的方法进行确定。Himmeblau提出了下面的终止准则。当 I x| A g和 f (Xi) A g时，采用f (Xi+) f(Xi)f(Xi)(3.13)否则采用Xj Xj W 或f (Xj 书)f (Xj) E(3.14)式中，；为根据实际问题要求精度给出的适当小的正数。根据以上Himmeblau提出的终止准则，实际中可以用各代适应度函数的均值之差来衡量 遗传算法的收敛特性。定义收敛性测量函数为：1 T Ce(S)fe(t 1) fe(t)(3.15)T式中，f e (t)为时刻t或第t代中相应于环境e的目标函数或平均适应度函数。从

9、优化问题中寻找最优解或最优解组的角度考虑，可以定义部分在线特性:(3.16)1 Tfn(s)f e(t)T t t式中，fe(t)为群体中对应于最优解或最优解组的个体适应度的均值。3.6小生境技术和共享函数Cavicchio提出只有在子串的适应度超过父代的情况下，子串才能替代父串进入下一代群 体的预选择机制，该机制趋向于替换与其本身相似的个体，能够维持群体的分布特性，并且 不断地以优秀个体来更新种群，使种群不断被优化。De Jo ng提出基于排挤的机制，其思想来源于一个有趣的生物现象：在一个有限的生存空 间中，各种不同的生物为了延续生存，必须相互竞争各种有限的生存资源。差别较大的个体 由于生活

10、习性不同而很少竞争。处于平衡状态的大小固定的种群，新生个体将代替与之相似 的旧个体。排挤机制可以维护当前种群的多样性，排挤机制用海明距离来度量个体之间的相 似性。这就是小生境技术。Glodberg和Richardson利用共享函数来度量两个个体的相邻关系和程度。给定个体g，它的共享函数由它与种群中其它个体的相似程度决定。将g与种群中其它个体逐个比较，若很相似，则对g的共享函数加一个较大值；否则，就加一个较小值。个体共享度为该个体与 群体内其它个体共享函数值之和，即nS=S(dj)(3.17)j壬式中，dij为个体i和个体j之间的关系亲密程度；S为共享函数；S为个体i在群体中的共享度。个体的适应度的调整公式为：fs(i)f(i)(3.18)文明施工 依据业主、监理有关要求，落实施工组织文件，明确各工序管理、材料管理、机械管理、成本管理、劳动管理。 对全体职工，特别是民工，在进场前进行文明、安全施工教育，不断提高职工的文明施工意识和自身素质。 建立文明施工管理制度，采用统一规范临设，围档整齐，符合要求，临设要牢固整齐，材质符合要求。 运料车运料时要用帆布覆盖，以防沿路遗撒和扬尘。施工道路要保证湿润，以防车辆行驶扬尘。 场地内材料与设备要保持整齐，并保证场地内的清洁。