1、第四章第四章 遗传算法的基本原理遗传算法的基本原理 4.1 4.1 遗传算法的基本描述遗传算法的基本描述 4.2 4.2 遗传算法的模式理论遗传算法的模式理论4.3 遗传算法与其他搜索算法的比较遗传算法与其他搜索算法的比较4.4 4.4 遗传算法的高级实现遗传算法的高级实现4.1.1 标准遗传算法流程：标准遗传算法流程：1编码编码 2初始群体的生成初始群体的生成 3适应度评估检测适应度评估检测 4WHILE DO 1.选择选择 2.交叉交叉 3.变异变异 4.适应度评估检测适应度评估检测 5END DO 4.1 遗传算法的基本描述遗传算法的基本描述选择选择交叉交叉当前代当前代中间代中间代下一代
2、下一代4.1 遗传算法的基本描述遗传算法的基本描述4.1.3 遗传编码遗传编码定义定义：由问题空间向由问题空间向GA编码空间的映射称为编码空间的映射称为编码编码，而由，而由编码空间向问题空间的映射成为编码空间向问题空间的映射成为译码译码。问题编码一般应满足以下三个原则：问题编码一般应满足以下三个原则：1）完备性完备性（completeness）：问题空间中的所有点都能）：问题空间中的所有点都能能成为能成为GA编码空间中的点的表现型编码空间中的点的表现型2）健全性健全性（soundness）：）：GA编码空间中的染色体位串编码空间中的染色体位串必须对应问题空间中的某一潜在解。必须对应问题空间中的
3、某一潜在解。3）非冗余性非冗余性（non-redundancy）：染色体和潜在解必须）：染色体和潜在解必须一一对应。一一对应。4.1 遗传算法的基本描述遗传算法的基本描述4.1.3 遗传编码遗传编码根据模式定理，根据模式定理，De Jong进一步提出了较为客观明确的进一步提出了较为客观明确的编码评估准则，称之为编码评估准则，称之为编码原理编码原理。具体可以概括为两。具体可以概括为两条规则：条规则：1）有意义积木块编码规则：有意义积木块编码规则：编码应易于生成与所求问题编码应易于生成与所求问题相关的短距和低阶的积木块。相关的短距和低阶的积木块。2）最小字符集编码规则：最小字符集编码规则：编码应采
4、用最小字符集，以使编码应采用最小字符集，以使问题得到自然、简单的表示和描述。问题得到自然、简单的表示和描述。4.1 遗传算法的基本描述遗传算法的基本描述1二进制编码二进制编码1）连续实函数的二进制编码）连续实函数的二进制编码设一维连续实函数设一维连续实函数 采用长度维采用长度维L的二进制字符串进的二进制字符串进行定长编码，建立位串空间：行定长编码，建立位串空间：k=1,2,K;l=1,2,L;K=2L表示精度为表示精度为 。将个体又从位串空间转换到问题空间的译码函数将个体又从位串空间转换到问题空间的译码函数的公式定义为：的公式定义为：,),(vuxxfKLxxxS,21),(21kLkkkaa
5、ax 1,0kla)12/()(Luvx,1,0:vuL)2(12),(121LjjLkjLkLkkkauvuaaax4.1 遗传算法的基本描述遗传算法的基本描述对于对于n维连续函数维连续函数 ，各维变量的二进制编码位串的长度为各维变量的二进制编码位串的长度为li,那么那么x的编码从左到右依次构的编码从左到右依次构成总长度为成总长度为 的二进制编码位串。相应的的二进制编码位串。相应的GA编码空间为：编码空间为：，K=2L该空间上的个体位串结构为该空间上的个体位串结构为对于给定的二进制编码位串对于给定的二进制编码位串sk,位段译码函数的形式为位段译码函数的形式为，i=1,2,n),2,1(,),
6、(),(21nivuxxxxxxfiiinniilL1,21KLxxxS1,0),(2121222211121121iklnklnknkiklikikklkkklkkkaaaaaaaaaaaaaxninklnknkiklikikklkkklkkkniaaaaaaaaaaaax2121222211121121)2(12),(121iiiiljjlikjliiiiklikikiiauvuaaax4.1 遗传算法的基本描述遗传算法的基本描述2其他编码其他编码1)大字符集编码（相对于二进制编码）大字符集编码（相对于二进制编码）2)序列编码（序列编码（TSP）3)实数编码实数编码4)树编码树编码5)自适
7、应编码自适应编码6)乱序编码乱序编码 4.1 遗传算法的基本描述遗传算法的基本描述4.1.4 群体设定群体设定 1。初始群体的设定。初始群体的设定一般来讲，初始群体的设定可以采用如下的策略：一般来讲，初始群体的设定可以采用如下的策略：1)根据问题固有知识，设法把握最优解所占空间在整个根据问题固有知识，设法把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定问题空间中的分布范围，然后，在此分布范围内设定初始群体。初始群体。2)先随机生成一定数目的个体，然后从中挑出最好的个先随机生成一定数目的个体，然后从中挑出最好的个体加入到初始群体中。这一过程不断重复，直到初始体加入到初始群体
8、中。这一过程不断重复，直到初始群体中个体数达到了预定的规模。群体中个体数达到了预定的规模。4.1 遗传算法的基本描述遗传算法的基本描述4.1.4 群体设定群体设定 2。群体规模的设定。群体规模的设定 根据模式定理，若群体规模为根据模式定理，若群体规模为M，则遗传操作可，则遗传操作可从这从这M个个体中生成和检测个个体中生成和检测O(M3)个模式，并在此个模式，并在此基础上不断形成和优化积木块，直到找到最优解。基础上不断形成和优化积木块，直到找到最优解。群体规模群体规模N N，模式阶，模式阶i i，被采样的模式数量的期望，被采样的模式数量的期望M Mi i(i=1,2,(i=1,2,),)之间满足
9、如下关系：之间满足如下关系：群体规模一般不随迭代而变化，但也不绝对。群体规模一般不随迭代而变化，但也不绝对。iiNM24.1 遗传算法的基本描述遗传算法的基本描述4.1.5 适应度函数（评价函数）适应度函数（评价函数）1。目标函数映射成适应度函数。目标函数映射成适应度函数 2。适应度函数定标。适应度函数定标 1）线性定标线性定标（linear scaling）f=af+b2）截断截断（sigma truncation）3）乘幂标乘幂标f=fK4）指数定标指数定标f=exp(-bf)(cfff4.1 遗传算法的基本描述遗传算法的基本描述4.1.6 遗传算子遗传算子 包括三个基本遗传算子（包括三个
10、基本遗传算子（genetic operator）：）：选择选择，交叉交叉和和变异变异。这三个遗传算子具有一些特点：这三个遗传算子具有一些特点：（1）这三个算子的操作都是随机化操作，因此，群体中个体向最优）这三个算子的操作都是随机化操作，因此，群体中个体向最优解迁移的规则是随机的。需要强调的是，这种随机化操作和传解迁移的规则是随机的。需要强调的是，这种随机化操作和传统的随机搜索方法是有区别的。遗传操作进行的是高效有向的统的随机搜索方法是有区别的。遗传操作进行的是高效有向的搜索，而不是如一般随机搜索方法所进行的无向搜索。搜索，而不是如一般随机搜索方法所进行的无向搜索。（2）遗传操作的效果和所取的操
11、作概率、编码方法、群体大小，以）遗传操作的效果和所取的操作概率、编码方法、群体大小，以及适应度函数的设定密切相关。及适应度函数的设定密切相关。（3）三个基本算子的操作方法和操作策略随具体求解问题的不同而三个基本算子的操作方法和操作策略随具体求解问题的不同而异。或者说，是和个体的编码方式直接相关。异。或者说，是和个体的编码方式直接相关。4.1.6 遗传算子遗传算子一、选择一、选择（selection）算子算子 从群体中选择优胜个体，淘汰劣质个体的操作叫从群体中选择优胜个体，淘汰劣质个体的操作叫选择选择。选择算子有时又称为选择算子有时又称为再生算子再生算子（reproduction operato
12、r）。选择即从当前群体中选择适应度值高的个）。选择即从当前群体中选择适应度值高的个体以生成体以生成配对池配对池（mating pool）的过程。）的过程。4.1.6 遗传算子遗传算子一、选择一、选择（selection）算子算子 1、适应度比例选择、适应度比例选择首先计算每个个体的适应度值，然后计算出此适应度值在群体适首先计算每个个体的适应度值，然后计算出此适应度值在群体适应度值总和中所占的比例，表示该个体在选择过程中被选中的概应度值总和中所占的比例，表示该个体在选择过程中被选中的概率。选择过程体现了生物进化过程中率。选择过程体现了生物进化过程中“适者生存，优胜劣汰适者生存，优胜劣汰”的的思想
13、。思想。对于给定的规模为对于给定的规模为n的群体的群体 ，个体，个体 的适应的适应度值为度值为 ，其选择概率为：，其选择概率为：问题：易出现未成熟收敛问题：易出现未成熟收敛,21naaaPPaj)(jafnjafafapniijjs,2,1,)()()(14.1.6 遗传算子遗传算子一、选择一、选择（selection）算子算子 2、Boltzmann选择选择在群体进化过程中，不同阶段需要不同地选择压力。在群体进化过程中，不同阶段需要不同地选择压力。早期阶段选早期阶段选择压力较小择压力较小，我们希望较差地个体也又一定地生存机会，使得群，我们希望较差地个体也又一定地生存机会，使得群体保持较高地多
14、样性；体保持较高地多样性；后期阶段，选择压力较大后期阶段，选择压力较大，我们希望，我们希望GA缩缩小搜索邻域，加快当前最优解的改善速度。为了动态调整群体进小搜索邻域，加快当前最优解的改善速度。为了动态调整群体进化过程中的选择压力，化过程中的选择压力，Goldberg设计了设计了Boltzmann选择方法。个体选择方法。个体选择概率为：选择概率为：njeeapniTafTafjsij,2,1,)(1/)(/)(4.1.6 遗传算子遗传算子一、选择一、选择（selection）算子算子 3、排序选择、排序选择 排序选择方法是将群体中个体按其适应度值由大到小的顺序排成排序选择方法是将群体中个体按其适
15、应度值由大到小的顺序排成一个序列，然后将事先设计好的序列概率分配给每个个体。一个序列，然后将事先设计好的序列概率分配给每个个体。排序选择不利用个体适应度值绝对值的信息，可以避免群体进化排序选择不利用个体适应度值绝对值的信息，可以避免群体进化过程中的适应度标度变换。过程中的适应度标度变换。4.1.6 遗传算子遗传算子一、选择一、选择（selection）算子算子 3、排序选择、排序选择 对于给定的规模为对于给定的规模为n n的群体的群体 ，并且满足个体适应，并且满足个体适应度值降序排列度值降序排列 。假设当前群体最佳个体。假设当前群体最佳个体a a1 1在选择操作后的期望数量为在选择操作后的期望
16、数量为 ，即，即；最差个体；最差个体a an n在选择在选择操作后的期望数量为操作后的期望数量为 。其它个体的期望数量按等差序。其它个体的期望数量按等差序列计算列计算，故现在排序选择概率为故现在排序选择概率为 ,21naaaP)()()(21nafafaf1pnnpn11njj)1(1)()1(jnjjnjjnnapjs,2,1),1(1)(1)(4.1.6 遗传算子遗传算子一、选择一、选择（selection）算子算子 4、联赛选择、联赛选择（tournament selection）基本思想：基本思想：从当前群体中随机选择一定数量的个体（放回或者不从当前群体中随机选择一定数量的个体（放回或
17、者不放回），将其中适应值最大的个体放入配对池中。反复执行这一放回），将其中适应值最大的个体放入配对池中。反复执行这一过程，直到配对池中的个体数量达到设定的值。过程，直到配对池中的个体数量达到设定的值。联赛规模用联赛规模用q q表示，也称表示，也称q q-联赛选择。联赛选择。联赛选择与个体的适应度值由间接关系，注重适应度值大小的比联赛选择与个体的适应度值由间接关系，注重适应度值大小的比较。较。联赛规模一般取联赛规模一般取q q=2=2。4.1.6 遗传算子遗传算子一、选择一、选择（selection）算子算子 5、精英选择、精英选择 如果下一代群体的最佳个体适应度值小于当前群体最佳个体的适如果下
18、一代群体的最佳个体适应度值小于当前群体最佳个体的适应度值，则将当前群体最佳个体或者适应度值大于下一代最佳个应度值，则将当前群体最佳个体或者适应度值大于下一代最佳个体适应度值的多个个体直接复制到下一代，随机替代和替代最差体适应度值的多个个体直接复制到下一代，随机替代和替代最差的下一代群体中的相应数量的个体。的下一代群体中的相应数量的个体。精英选择是群体收敛到全局最优解的一种基本保障。精英选择是群体收敛到全局最优解的一种基本保障。4.1.6 遗传算子遗传算子一、选择一、选择（selection）算子算子 6、稳态选择、稳态选择 稳态选择操作中，稳态选择操作中，仅有少量个体仅有少量个体按适应度值比例
19、选择方法被选择，按适应度值比例选择方法被选择，通过遗传操作生成新的个体。新个体放回到群体中时，随机替代通过遗传操作生成新的个体。新个体放回到群体中时，随机替代等量的旧个体，或者替代等量的最差的旧个体。等量的旧个体，或者替代等量的最差的旧个体。Holland将稳态选择方法应用于分类器规则学习中，最大程度继承将稳态选择方法应用于分类器规则学习中，最大程度继承已获得的规则，实现增量学习。已获得的规则，实现增量学习。De Jong将下一代群体中生成的与上一代不同的新个体所占的比例将下一代群体中生成的与上一代不同的新个体所占的比例称为称为“代沟代沟”（generation gap）。代沟越大，说明新个体
20、的生成）。代沟越大，说明新个体的生成比例越高，群体搜索新的编码空间的能力（探索）越强。比例越高，群体搜索新的编码空间的能力（探索）越强。4.1.6 遗传算子遗传算子二、交叉二、交叉（CrossoverCrossover）算子算子 交叉算子是模仿自然界有性繁殖的基因重组过程，其作用在于将交叉算子是模仿自然界有性繁殖的基因重组过程，其作用在于将已有的优良基因遗传给下一代个体，并生成包含更复杂基因结构已有的优良基因遗传给下一代个体，并生成包含更复杂基因结构的新个体。的新个体。交叉操作一般分为以下几个步骤：交叉操作一般分为以下几个步骤：1）从配对池中随机取出要交配的一对个体；）从配对池中随机取出要交配
21、的一对个体；2）根据位串长度）根据位串长度L，对要交叉的一对个体，随机选取，对要交叉的一对个体，随机选取1,L-1中一中一个或多个整数个或多个整数k作为交叉位置；作为交叉位置；3）根据交叉概率实施交叉操作，配对个体在交叉位置处，相互交）根据交叉概率实施交叉操作，配对个体在交叉位置处，相互交换各自的部分内容，从而形成新的一对个体。换各自的部分内容，从而形成新的一对个体。4.1.6 遗传算子遗传算子二、交叉二、交叉（CrossoverCrossover）算子算子 1、一点交叉、一点交叉（one-point crossover）位串位串A：1 1 0 1|1 0 1 0位串位串B：1 0 1 1|0
22、 1 0 1位串位串A：1 1 0 1|0 1 0 1位串位串B：1 0 1 1|1 0 1 0 4.1.6 遗传算子遗传算子二、交叉二、交叉（CrossoverCrossover）算子算子 1、两点交叉、两点交叉（twotwo-point crossover）位串位串A：1 1|0 1 1|0 1 0位串位串B：1 0|1 1 0|1 0 1位串位串A：1 1|1 1 0|0 1 0位串位串B：1 0|0 1 1|1 0 1 4.1.6 遗传算子遗传算子二、交叉二、交叉（CrossoverCrossover）算子算子 1、多点交叉、多点交叉（multimulti-point crossove
23、r）位串位串A：1 1|0 1|1 0|1 0位串位串B：1 0|1 1|0 1|0 1位串位串A：1 1|1 1|1 0|0 1位串位串B：1 0|0 1|0 1|1 04.1.6 遗传算子遗传算子二、交叉二、交叉（CrossoverCrossover）算子算子 1、一致交叉、一致交叉一致交叉即染色体位串上的每一位按相同概率进行随机均匀交叉。一致交叉即染色体位串上的每一位按相同概率进行随机均匀交叉。一致交叉算子生成的新个体位：一致交叉算子生成的新个体位：操作描述如下：操作描述如下：，x是取值为是取值为0，1上符合均匀分布的随机变量。上符合均匀分布的随机变量。Laaas112111Laaas2
24、22212),(xpOc2/1,2/1,211xaxaaiii2/1,2/1,122xaxaaiii4.1.6 遗传算子遗传算子三、变异三、变异（MutationMutation）算子算子 变异操作模拟自然界生物体进化中染色体上某位基因发生的突变变异操作模拟自然界生物体进化中染色体上某位基因发生的突变现象，从而改变染色体的结构和物理性状。现象，从而改变染色体的结构和物理性状。在标准遗传算法中，变异算子通过按变异概率在标准遗传算法中，变异算子通过按变异概率pm随机反转某位等随机反转某位等位基因的二进制字符值来实现。位基因的二进制字符值来实现。对于给定的染色体位串对于给定的染色体位串 ，具体如下：
25、，具体如下：生成新的个体生成新的个体 。其中，。其中，xi是对应于每一个基因位产是对应于每一个基因位产生的均匀随机变量，生的均匀随机变量，。Laaas21:),(xpOm否则若,1imiiiapxaa,2,1LiLaaas210,1 ix4.1.6 遗传算子遗传算子四、逆转（四、逆转（Inversion Operator）算子）算子 逆转操作首先在个体位串上随机地选择两个点，位串染色体被这逆转操作首先在个体位串上随机地选择两个点，位串染色体被这两个点分成三段，将中间段的左右顺序倒转过来与另两段相连，两个点分成三段，将中间段的左右顺序倒转过来与另两段相连，形成新的个体位串。形成新的个体位串。例如
26、：长度为例如：长度为10的二进制位串，其中下划线标示的等位基因为重的二进制位串，其中下划线标示的等位基因为重要基因：要基因：1011101101（是倒位位置）是倒位位置）经倒位后变为经倒位后变为1011011101。新的位串中重要基因更为靠近，被单点交叉算子分离的可能性大新的位串中重要基因更为靠近，被单点交叉算子分离的可能性大大降低了。大降低了。4.1.6 遗传算子遗传算子 四、换位（四、换位（Swap Operator）算子）算子换位操作首先在个体位串上随机地选择两个基因，将这两个基因换位操作首先在个体位串上随机地选择两个基因，将这两个基因的位置互换，形成新的个体位串。的位置互换，形成新的个
27、体位串。例如：长度为例如：长度为10的二进制位串，其中下划线标示的为随机选中的的二进制位串，其中下划线标示的为随机选中的基因：基因：1011101101经换位后变为经换位后变为1111101100 4.1.7 迭代终止条件迭代终止条件一般采用设定最大代数的方法一般采用设定最大代数的方法。其次，可以根据群体的收敛程度来判断，通过计算种群其次，可以根据群体的收敛程度来判断，通过计算种群中的基因多样性测度，即所有基因位的相似性程度来进中的基因多样性测度，即所有基因位的相似性程度来进行控制行控制。第三，根据算法的离线性能和在线性能的变化进行判定第三，根据算法的离线性能和在线性能的变化进行判定。最后，在
28、采用精英保留选择策略的情况下，按每代最佳最后，在采用精英保留选择策略的情况下，按每代最佳个体的适应值的变化情况确定个体的适应值的变化情况确定。4.1.8 控制参数控制参数1 1）位串长度位串长度L L：位串长度位串长度L L的选择取决于特定问题解的精度。的选择取决于特定问题解的精度。要求的精度越高，位串越长，但需要更多的计算时间。要求的精度越高，位串越长，但需要更多的计算时间。为提高运算效率，变长度位串或者在当前所达到的较小为提高运算效率，变长度位串或者在当前所达到的较小可行域内重新编码，是一种可行的方法，并显示了良好可行域内重新编码，是一种可行的方法，并显示了良好性能。性能。2 2）群体规模
29、群体规模n n：大群体含有较多模式，为遗传算法提供了大群体含有较多模式，为遗传算法提供了足够的模式采样容量，可以改进足够的模式采样容量，可以改进GAGA搜索的质量，防止成搜索的质量，防止成熟前收敛。但大群体增加了个体适应性评价的计算量，熟前收敛。但大群体增加了个体适应性评价的计算量，从而使收敛速度降低。一般情况下建议从而使收敛速度降低。一般情况下建议n n2020200200。4.1.8 控制参数控制参数3 3）交叉概率交叉概率PcPc：交叉概率控制着交叉算子的应用频率，在交叉概率控制着交叉算子的应用频率，在每一代新的群体中，需要对每一代新的群体中，需要对PcPcn n个个体的染色体结构个个体
30、的染色体结构进行交叉操作。交叉概率越高，群体中新结构的引人愈进行交叉操作。交叉概率越高，群体中新结构的引人愈快，已获得的优良基因结构的丢失速度也相应升高。而快，已获得的优良基因结构的丢失速度也相应升高。而交叉概率太低则可能导致搜索阻滞。一般取交叉概率太低则可能导致搜索阻滞。一般取Pc=0.60Pc=0.601.001.00。4 4）变异概率变异概率PmPm：变异操作是保持群体多样性的有效手段，变异操作是保持群体多样性的有效手段，交叉结束后，交配池中的全部个体位串上的每位等位基交叉结束后，交配池中的全部个体位串上的每位等位基因按变异率因按变异率PmPm随机改变，因此每代中大约发生随机改变，因此每
31、代中大约发生PmPmn nL L次变异。变异概率太小，可能使某些基因位过早丢失的次变异。变异概率太小，可能使某些基因位过早丢失的信息无法恢复；而变异概率过高，则遗传搜索将变成随信息无法恢复；而变异概率过高，则遗传搜索将变成随机搜索。一般取机搜索。一般取Pm=0.0050.01Pm=0.0050.01。4.1.8 控制参数控制参数从理论上来讲，不存在一组适用于所有问题的最佳参数从理论上来讲，不存在一组适用于所有问题的最佳参数值，随着问题特征的变化，有效参数的差异往往非常显值，随着问题特征的变化，有效参数的差异往往非常显著。著。4.1.9 GA的性能评估的性能评估 关于搜索类算法的性能评估，一般可
32、以归纳为算法的关于搜索类算法的性能评估，一般可以归纳为算法的求求解效率解效率和和求解质量求解质量两个方面。两个方面。算法的求解效率算法的求解效率是比较获得同样的可行解所需要的计算是比较获得同样的可行解所需要的计算时间。时间。算法的求解质量算法的求解质量是在规定的时间（或者时间相关指标）是在规定的时间（或者时间相关指标）内所获得的可行解的优劣。内所获得的可行解的优劣。4.1.9 GA的性能评估的性能评估 1 1适应值函数计算次数适应值函数计算次数该指标是指发现同样适应性的个体，或者找到同样质量该指标是指发现同样适应性的个体，或者找到同样质量的可行解，所需要的关于个体评价的适应值函数的计算的可行解
33、，所需要的关于个体评价的适应值函数的计算次数（次数（function evaluationsfunction evaluations）。显然，该值越小说明）。显然，该值越小说明相应相应GAGA的搜索效率越高。的搜索效率越高。该指标不仅可以用于不同参数设置该指标不仅可以用于不同参数设置GAGA的性能比较，也可的性能比较，也可以用于以用于GAGA与其他搜索算法的比较。与其他搜索算法的比较。4.1.9 GA的性能评估的性能评估 2 2在线和离线性能函数在线和离线性能函数 1 1）在线性能函数在线性能函数（on-line performanceon-line performance）：设）：设GAGA
34、的遗的遗传策略为传策略为s s（包括（包括LL，n n，PcPc，PmPm，算子形式等），该，算子形式等），该策略的在线性能：策略的在线性能：即在线性能反映了群体平均适应值经平滑处理后的变化即在线性能反映了群体平均适应值经平滑处理后的变化情况，描述了群体的整体性状和进化能力。情况，描述了群体的整体性状和进化能力。TtnjjlineontafTnsP01,_)()1(1)(4.1.9 GA的性能评估的性能评估 2 2在线和离线性能函数在线和离线性能函数 2 2）离线性能函数离线性能函数（offline performance）：对于）：对于GA遗遗传策略传策略s，其离线性能，其离线性能其中，其中
35、，f(a*，t)maxf(al,t)，f(a2,t)，f(an,t)，即，即当前群体中最佳个体的适应值。该指标反映了群体中最当前群体中最佳个体的适应值。该指标反映了群体中最佳个体适应值经平滑处理后的变化情况，描述了个体的佳个体适应值经平滑处理后的变化情况，描述了个体的进化能力和进化能力和GA的搜索能力。的搜索能力。TtlineofftafTsP0*_),(11)(4.1.9 GA的性能评估的性能评估 3 3最优解搜索性能最优解搜索性能 GA用于函数优化的目的就是发现问题的全局最优解，用于函数优化的目的就是发现问题的全局最优解，所以通常采用当前群体发现的最佳可行解的改善情况作所以通常采用当前群体
36、发现的最佳可行解的改善情况作为度量为度量GA搜索能力的基本指标。搜索能力的基本指标。4.2 遗传算法的模式理论遗传算法的模式理论4.21 模式与模式空间模式与模式空间位串上的某些等位基因的联结与适应值函数之间存在着某种联系，位串上的某些等位基因的联结与适应值函数之间存在着某种联系，这种联系提供了寻优过程的指导信息，引导着群体在位串空间中这种联系提供了寻优过程的指导信息，引导着群体在位串空间中的移动方向。的移动方向。采用字符集采用字符集K=0，1对问题参数进行二进制编码，位串空间表示对问题参数进行二进制编码，位串空间表示为为SL1,0L，该空间的大小为，该空间的大小为|SL|2L。扩展字符集。扩
37、展字符集K0,1,*，其中其中*是通配符或无关符（是通配符或无关符（wild cards，or“dont cares”），即可），即可和和0或或 1匹配。扩展位串空间表示为匹配。扩展位串空间表示为SeL1,0,*L，该空间的大小，该空间的大小为为|SeL|3L，则称，则称SeL为为SL的模式空间。显然，包含的模式空间。显然，包含2L个位串的位个位串的位串空间，对应于串空间，对应于3L个模式位串的模式空间。个模式位串的模式空间。4.2 遗传算法的模式理论遗传算法的模式理论4.21 模式与模式空间模式与模式空间定义：定义：扩展位串空间扩展位串空间SeL0,1,*L中的任何一个点中的任何一个点H H
38、，称为，称为对应于位串空间对应于位串空间 SL1,0L的一个模式（的一个模式（Schema）：）：其中其中a(al，a2，aL)，H(H1，H2，HL)，i=1，2，L；，例如：例如：0*1 0，1*1*，0*,|iiiLeaHHiSHHH1,0ia,1,0iHLSaLeSH 4.2 遗传算法的模式理论遗传算法的模式理论4.21 模式与模式空间模式与模式空间模式模式是由是由SL中具有共同特征的中具有共同特征的位串所组成的集合（对位串所组成的集合（对应于位串空间的子空间）应于位串空间的子空间），它描述了该集合中位串上，它描述了该集合中位串上共同的基因特征。集合的大小共同的基因特征。集合的大小N由
39、模式中由模式中*的个数的个数k决决定，定，N=2k。例如：模式例如：模式0 0*表示位串长度为表示位串长度为4，两个高位基因为，两个高位基因为00的位串集合，即的位串集合，即0000，0001，0010，0011如果包含这一模式的所有位串都具有较好的适应度，如果包含这一模式的所有位串都具有较好的适应度，则该模式可能是一个重要的模式。则该模式可能是一个重要的模式。GoldbergGoldberg将模式称将模式称为为“超 平 面超 平 面”（hyper planehyper plane），），指出了模式在编码指出了模式在编码空间上的几何意义，空间上的几何意义，模式包含的位串是模式包含的位串是编码空
40、间相应超平编码空间相应超平面上的点。面上的点。模式模式 H1=1*表示函数解空间的右半区域表示函数解空间的右半区域模式模式 H2=0*表示函数解空间的左半区域表示函数解空间的左半区域Y=X2模式模式 H3=*1表示函数解空间的阴影区域（奇数位串）表示函数解空间的阴影区域（奇数位串）模式模式 H4=*0表示函数解空间的空白区域（偶数位串）表示函数解空间的空白区域（偶数位串）模式模式 H5=*1*表示函数解空间的阴影区域表示函数解空间的阴影区域模式模式 H6=*0*表示函数解空间的空白区域表示函数解空间的空白区域模式模式 H7=1 0*的表示域，代表了的表示域，代表了1/4的解空间的解空间模式模式
41、 H8=*1*1 的表示域，代表了的表示域，代表了1/4的解空间的解空间4.2 遗传算法的模式理论遗传算法的模式理论4.21 模式与模式空间模式与模式空间模式的阶模式的阶（schema order）是指模式中所含有）是指模式中所含有0、1确定基确定基因位的个数，记作因位的个数，记作O(H)。模式的定义距模式的定义距（defining length）是指模式中从左到右第）是指模式中从左到右第一个非一个非*位和最后一位非位和最后一位非*位之间的距离，记作位之间的距离，记作模式的维数模式的维数（schema dimension）是指模式中所包含的位）是指模式中所包含的位串的个数，也称为模式的容量，记
42、作串的个数，也称为模式的容量，记作D(H)，D(H)=2L-O(H)。)(H4.2 遗传算法的模式理论遗传算法的模式理论4.21 模式与模式空间模式与模式空间令令m=m(H，t)为模式为模式H在第在第t代群体中所含位串数量，代群体中所含位串数量，模式在模式在t代群体中包含的个体位串为代群体中包含的个体位串为a1,a2,am，称，称为模式为模式H在群体中的生存数量（在群体中的生存数量（survivals）或者采样样）或者采样样本（本（samples），），(j=1，2，m)，则模式，则模式H在第在第 t代群体中的适应值估计为代群体中的适应值估计为即模式的适应值估计（简称模式的适应值）是群体中即模
43、式的适应值估计（简称模式的适应值）是群体中其所包含的全部个体的适应值的平均值。其所包含的全部个体的适应值的平均值。HajmjjmaftHf1/)(),(4.2 遗传算法的模式理论遗传算法的模式理论4.21 模式与模式空间模式与模式空间从编码空间来看从编码空间来看，m（H，t）是当前群体中包含属于模式是当前群体中包含属于模式H的个的个体数量，反映了所对应的模式空间的分布情况，该数量越大说明体数量，反映了所对应的模式空间的分布情况，该数量越大说明群体搜索越集中于模式群体搜索越集中于模式H代表的子空间。代表的子空间。从模式空间来看从模式空间来看，m（H，t）是模式是模式H在当前群体中的个体采样在当前
44、群体中的个体采样数量，反映了所对应的编码空间的分布情况。该数量越大说明群数量，反映了所对应的编码空间的分布情况。该数量越大说明群体中的个体越趋向相似和一致，在编码空间的搜索范围越小。体中的个体越趋向相似和一致，在编码空间的搜索范围越小。一个模式一个模式H由位串长度由位串长度L、阶、阶O(H)、定义距、定义距 、容量、容量D(H)和适和适应值应值f(H，t)等五个指标来描述。模式的引入为在一个有限字符集等五个指标来描述。模式的引入为在一个有限字符集上定义的有限长度的位串之间的相似性度量和理论分析提供了有上定义的有限长度的位串之间的相似性度量和理论分析提供了有力的工具。力的工具。)(H4.2 遗传
45、算法的模式理论遗传算法的模式理论4.22 模式定理和积木块假设模式定理和积木块假设 在选择算子作用下在选择算子作用下，对于平均适应度高于群体平均适应度，对于平均适应度高于群体平均适应度的模式，其样本数将呈指数级增长：而对于平均适应度低的模式，其样本数将呈指数级增长：而对于平均适应度低于群体平均适应度的模式，其样本数将呈指数级减少。于群体平均适应度的模式，其样本数将呈指数级减少。在选择和交叉算子作用下在选择和交叉算子作用下，模式定义距越小，则群体中该，模式定义距越小，则群体中该模式个体数量越容易呈指数级增长；模式定义距越大，则模式个体数量越容易呈指数级增长；模式定义距越大，则群体中该模式个体数量
46、越不容易呈指数级增长。群体中该模式个体数量越不容易呈指数级增长。在变异算子作用下在变异算子作用下，阶数越小模式，阶数越小模式H越易于生存；阶数越越易于生存；阶数越大，模式大，模式H越易于被破坏。越易于被破坏。4.2 遗传算法的模式理论遗传算法的模式理论4.22 模式定理和积木块假设模式定理和积木块假设 模式定理模式定理：在遗传算子选择、交叉、变异的作用下，那些：在遗传算子选择、交叉、变异的作用下，那些低阶、定义距短的、超过群体平均适应度值的模式的生存低阶、定义距短的、超过群体平均适应度值的模式的生存数量，将随着迭代次数的增加以指数规律增长。数量，将随着迭代次数的增加以指数规律增长。模式定理的意
47、义模式定理的意义：统计决策中的统计决策中的双臂赌机问题双臂赌机问题表明：表明：按指按指数规律提高将硬币投往平均支付高的赌机的概率，可以获数规律提高将硬币投往平均支付高的赌机的概率，可以获得最大的累积支付得最大的累积支付。应用到优化问题则是：。应用到优化问题则是：要获得最优的要获得最优的可行解，则必须保证较优解的样本数呈指数级增长可行解，则必须保证较优解的样本数呈指数级增长。而模。而模式定理保证了较优的模式（遗传算法的较优解）的样本数式定理保证了较优的模式（遗传算法的较优解）的样本数呈指数级增长，从而给出了遗传算法的理论基础。呈指数级增长，从而给出了遗传算法的理论基础。4.2 遗传算法的模式理论
48、遗传算法的模式理论4.22 模式定理和积木块假设模式定理和积木块假设 定义定义：具有低阶、短定义距以及高适应度的模式称作积木具有低阶、短定义距以及高适应度的模式称作积木块。块。积木块假设积木块假设（building block hypothesisbuilding block hypothesis）：低阶、短距）：低阶、短距高平均适应度的模式（积木块）在遗传算子作用下，相互高平均适应度的模式（积木块）在遗传算子作用下，相互结合，能生成高阶、长距、高平均适应度的模式，并可最结合，能生成高阶、长距、高平均适应度的模式，并可最终生成全局最优解。终生成全局最优解。4.2 遗传算法的模式理论遗传算法的模
49、式理论4.22 模式定理和积木块假设模式定理和积木块假设 模式定理和积木块假设比较准确地模拟了自然界的物种竞模式定理和积木块假设比较准确地模拟了自然界的物种竞争和遗传法则，其中争和遗传法则，其中模式定理描述了模式定理描述了GAGA群体中模式之间的群体中模式之间的竞争关系，积木块假设说明了有效基因之间的继承与重组竞争关系，积木块假设说明了有效基因之间的继承与重组。因此，模式定理和积木块假设构成了关于因此，模式定理和积木块假设构成了关于GAGA进化过程能够进化过程能够发现最优解的一个解释，被认为是解释遗传算法寻优原理发现最优解的一个解释，被认为是解释遗传算法寻优原理的较系统的理论，统称为的较系统的
50、理论，统称为模式理论（模式理论（schema theoryschema theory）。它。它们也是们也是GAGA进化动力学的基本理论，尽管还存在着不完善之进化动力学的基本理论，尽管还存在着不完善之处，但是它为深入研究遗传算法的运行机理奠定了基础。处，但是它为深入研究遗传算法的运行机理奠定了基础。4.2 遗传算法的模式理论遗传算法的模式理论4.22 模式定理和积木块假设模式定理和积木块假设 模式定理在一定程度上证明了标准遗传算法的有效性，但模式定理在一定程度上证明了标准遗传算法的有效性，但它仍有以下的缺点：它仍有以下的缺点：（1 1）模式定理只对二进制编码适用，对其他编码方案尚没有）模式定理只
