第二章--遗传算法的基本原理课件.ppt

1、第二章第二章 遗传算法的基本原理遗传算法的基本原理 2.1 遗传算法的基本描述遗传算法的基本描述 2.2 遗传算法的模式理论遗传算法的模式理论2.3 遗传算法与其他搜索算法的比较遗传算法与其他搜索算法的比较2.1 遗传算法的基本描述遗传算法的基本描述2.1.1 全局优化问题全局优化问题 全局优化问题的定义：全局优化问题的定义：给定非空集合给定非空集合S作为搜索空间，作为搜索空间，f：SR为目为目标函数，全局优化问题作为任务标函数，全局优化问题作为任务 给出，即在搜索空间中给出，即在搜索空间中找到至少一个使目标函数最大化的点。找到至少一个使目标函数最大化的点。全局最大值（点）的定义：全局最大值（

2、点）的定义：函数值函数值 称为一个全局称为一个全局最大值，当且仅当最大值，当且仅当 成立时，成立时，被称被称为一个全局最大值点（全局最大解）。为一个全局最大值点（全局最大解）。局部极大值与局部极大值点（解）的定义：局部极大值与局部极大值点（解）的定义：假设在假设在S上给定了某个距上给定了某个距离度量离度量 ，如果对，如果对 ，使得对，使得对 ，则称则称x为一个局部极大值点，为一个局部极大值点，f(x)为一个局部极大值。当目标函数有多个局部极大点时，被为一个局部极大值。当目标函数有多个局部极大点时，被称为多峰或多模态函数（称为多峰或多模态函数（multi-modality function）。）

3、。)(maxxfSx)(*xff)()(*xfxfSxSx*Sx 0Sx)()(),(xfxfxx 2.1.1 标准遗传算法流程：标准遗传算法流程：1编码编码 2初始群体的生成初始群体的生成 3适应度评估检测适应度评估检测 4WHILE DO 1.选择选择 2.交叉交叉 3.变异变异 4.适应度评估检测适应度评估检测 5END DO 2.1 遗传算法的基本描述遗传算法的基本描述选择选择交叉交叉当前代当前代中间代中间代下一代下一代2.1 遗传算法的基本描述遗传算法的基本描述2.1.3 遗传编码遗传编码定义定义：由问题空间向由问题空间向GA编码空间的映射称为编码空间的映射称为编码编码，而由，而由编

4、码空间向问题空间的映射成为编码空间向问题空间的映射成为译码译码。问题编码一般应满足以下三个原则：问题编码一般应满足以下三个原则：1）完备性完备性（completeness）：问题空间中的所有点都能）：问题空间中的所有点都能能成为能成为GA编码空间中的点的表现型编码空间中的点的表现型2）健全性健全性（soundness）：）：GA编码空间中的染色体位串编码空间中的染色体位串必须对应问题空间中的某一潜在解。必须对应问题空间中的某一潜在解。3）非冗余性非冗余性（non-redundancy）：染色体和潜在解必须）：染色体和潜在解必须一一对应。一一对应。2.1 遗传算法的基本描述遗传算法的基本描述2.

5、1.3 遗传编码遗传编码根据模式定理，根据模式定理，De Jong进一步提出了较为客观明确的进一步提出了较为客观明确的编码评估准则，称之为编码评估准则，称之为编码原理编码原理。具体可以概括为两。具体可以概括为两条规则：条规则：1）有意义积木块编码规则：有意义积木块编码规则：编码应易于生成与所求问题编码应易于生成与所求问题相关的短距和低阶的积木块。相关的短距和低阶的积木块。2）最小字符集编码规则：最小字符集编码规则：编码应采用最小字符集，以使编码应采用最小字符集，以使问题得到自然、简单的表示和描述。问题得到自然、简单的表示和描述。2.1 遗传算法的基本描述遗传算法的基本描述1二进制编码二进制编码

6、1）连续实函数的二进制编码）连续实函数的二进制编码设一维连续实函数设一维连续实函数 采用长度维采用长度维L的二进制字符串进的二进制字符串进行定长编码，建立位串空间：行定长编码，建立位串空间：k=1,2,K;l=1,2,L;K=2L表示精度为表示精度为 。将个体又从位串空间转换到问题空间的译码函数将个体又从位串空间转换到问题空间的译码函数的公式定义为：的公式定义为：,),(vuxxfKLxxxS,21),(21kLkkkaaax 1,0kla)12/()(Luvx,1,0:vuL)2(12),(121LjjLkjLkLkkkauvuaaax2.1 遗传算法的基本描述遗传算法的基本描述对于对于n维

7、连续函数维连续函数 ，各维变量的二进制编码位串的长度为各维变量的二进制编码位串的长度为li,那么那么x的编码从左到右依次构的编码从左到右依次构成总长度为成总长度为 的二进制编码位串。相应的的二进制编码位串。相应的GA编码空间为：编码空间为：，K=2L该空间上的个体位串结构为该空间上的个体位串结构为对于给定的二进制编码位串对于给定的二进制编码位串sk,位段译码函数的形式为位段译码函数的形式为，i=1,2,n),2,1(,),(),(21nivuxxxxxxfiiinniilL1,21KLxxxS1,0),(2121222211121121iklnklnknkiklikikklkkklkkkaaa

8、aaaaaaaaaaxninklnknkiklikikklkkklkkkniaaaaaaaaaaaax2121222211121121)2(12),(121iiiiljjlikjliiiiklikikiiauvuaaax2.1 遗传算法的基本描述遗传算法的基本描述2其他编码其他编码1)大字符集编码（相对于二进制编码）大字符集编码（相对于二进制编码）2)序列编码（序列编码（TSP）3)实数编码实数编码4)树编码树编码5)自适应编码自适应编码6)乱序编码乱序编码 2.1 遗传算法的基本描述遗传算法的基本描述2.1.4 群体设定群体设定 1。初始群体的设定。初始群体的设定一般来讲，初始群体的设定可以

9、采用如下的策略：一般来讲，初始群体的设定可以采用如下的策略：1)根据问题固有知识，设法把握最优解所占空间在整个根据问题固有知识，设法把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定问题空间中的分布范围，然后，在此分布范围内设定初始群体。初始群体。2)先随机生成一定数目的个体，然后从中挑出最好的个先随机生成一定数目的个体，然后从中挑出最好的个体加入到初始群体中。这一过程不断重复，直到初始体加入到初始群体中。这一过程不断重复，直到初始群体中个体数达到了预定的规模。群体中个体数达到了预定的规模。2.1 遗传算法的基本描述遗传算法的基本描述2.1.4 群体设定群体设定 2。群体规

10、模的设定。群体规模的设定 根据模式定理，若群体规模为根据模式定理，若群体规模为M，则遗传操作可则遗传操作可从这从这M个个体中生成和检测个个体中生成和检测O(M3)个模式，并在此个模式，并在此基础上不断形成和优化积木块，直到找到最优解。基础上不断形成和优化积木块，直到找到最优解。群体规模群体规模N N，模式阶模式阶i i，被采样的模式数量的期望被采样的模式数量的期望M Mi i(i=1,2,)(i=1,2,)之间满足如下关系：之间满足如下关系：群体规模一般不随迭代而变化，但也不绝对。群体规模一般不随迭代而变化，但也不绝对。iiNM22.1 遗传算法的基本描述遗传算法的基本描述2.1.5 适应度函

11、数（评价函数）适应度函数（评价函数）1。目标函数映射成适应度函数。目标函数映射成适应度函数 2。适应度函数定标。适应度函数定标 1）线性定标线性定标（linear scaling）f=af+b2）截断截断（sigma truncation）3）乘幂标乘幂标f=fK4）指数定标指数定标f=exp(-bf)(cfff2.1 遗传算法的基本描述遗传算法的基本描述2.1.6 遗传算子遗传算子 包括三个基本遗传算子（包括三个基本遗传算子（genetic operator）：）：选择选择，交叉交叉和和变异变异。这三个遗传算子具有一些特点：这三个遗传算子具有一些特点：（1）这三个算子的操作都是随机化操作，因

12、此，群体中个体向最优）这三个算子的操作都是随机化操作，因此，群体中个体向最优解迁移的规则是随机的。需要强调的是，这种随机化操作和传解迁移的规则是随机的。需要强调的是，这种随机化操作和传统的随机搜索方法是有区别的。遗传操作进行的是高效有向的统的随机搜索方法是有区别的。遗传操作进行的是高效有向的搜索，而不是如一般随机搜索方法所进行的无向搜索。搜索，而不是如一般随机搜索方法所进行的无向搜索。（2）遗传操作的效果和所取的操作概率、编码方法、群体大小，以）遗传操作的效果和所取的操作概率、编码方法、群体大小，以及适应度函数的设定密切相关。及适应度函数的设定密切相关。（3）三个基本算子的操作方法和操作策略随

13、具体求解问题的不同而三个基本算子的操作方法和操作策略随具体求解问题的不同而异。或者说，是和个体的编码方式直接相关。异。或者说，是和个体的编码方式直接相关。2.1.6 遗传算子遗传算子一、选择一、选择（selection）算子算子 从群体中选择优胜个体，淘汰劣质个体的操作叫从群体中选择优胜个体，淘汰劣质个体的操作叫选择选择。选择算子有时又称为选择算子有时又称为再生算子再生算子（reproduction operator）。选择即从当前群体中选择适应度值高的个）。选择即从当前群体中选择适应度值高的个体以生成体以生成配对池配对池（mating pool）的过程。）的过程。2.1.6 遗传算子遗传算子

14、一、选择一、选择（selection）算子算子 1、适应度比例选择、适应度比例选择首先计算每个个体的适应度值，然后计算出此适应度值在群体适首先计算每个个体的适应度值，然后计算出此适应度值在群体适应度值总和中所占的比例，表示该个体在选择过程中被选中的概应度值总和中所占的比例，表示该个体在选择过程中被选中的概率。选择过程体现了生物进化过程中率。选择过程体现了生物进化过程中“适者生存，优胜劣汰适者生存，优胜劣汰”的的思想。思想。对于给定的规模为对于给定的规模为n的群体的群体 ，个体，个体 的适应的适应度值为度值为 ，其选择概率为：，其选择概率为：问题：易出现未成熟收敛问题：易出现未成熟收敛,21na

15、aaPPaj)(jafnjafafapniijjs,2,1,)()()(12.1.6 遗传算子遗传算子一、选择一、选择（selection）算子算子 2、Boltzmann选择选择在群体进化过程中，不同阶段需要不同地选择压力。在群体进化过程中，不同阶段需要不同地选择压力。早期阶段选早期阶段选择压力较小择压力较小，我们希望较差地个体也又一定地生存机会，使得群，我们希望较差地个体也又一定地生存机会，使得群体保持较高地多样性；体保持较高地多样性；后期阶段，选择压力较大后期阶段，选择压力较大，我们希望，我们希望GA缩缩小搜索邻域，加快当前最优解的改善速度。为了动态调整群体进小搜索邻域，加快当前最优解的

16、改善速度。为了动态调整群体进化过程中的选择压力，化过程中的选择压力，Goldberg设计了设计了Boltzmann选择方法。个体选择方法。个体选择概率为：选择概率为：njeeapniTafTafjsij,2,1,)(1/)(/)(2.1.6 遗传算子遗传算子一、选择一、选择（selection）算子算子 3、排序选择、排序选择 排序选择方法是将群体中个体按其适应度值由大到小的顺序排成排序选择方法是将群体中个体按其适应度值由大到小的顺序排成一个序列，然后将事先设计好的序列概率分配给每个个体。一个序列，然后将事先设计好的序列概率分配给每个个体。排序选择不利用个体适应度值绝对值的信息，可以避免群体进

17、化排序选择不利用个体适应度值绝对值的信息，可以避免群体进化过程中的适应度标度变换。过程中的适应度标度变换。2.1.6 遗传算子遗传算子一、选择一、选择（selection）算子算子 3、排序选择、排序选择 对于给定的规模为对于给定的规模为n n的群体的群体 ，并且满足个体适应，并且满足个体适应度值降序排列度值降序排列 。假设当前群体最佳个体。假设当前群体最佳个体a a1 1在选择操作后的期望数量为在选择操作后的期望数量为 ，即，即；最差个体；最差个体a an n在选择在选择操作后的期望数量为操作后的期望数量为 。其它个体的期望数量按等差序。其它个体的期望数量按等差序列计算列计算，则，则 ，故现

18、在排序选择概率为故现在排序选择概率为 ,21naaaP)()()(21nafafaf1pnnpn11njj)1(1)()1(jnjjnjjnnapjs,2,1),1(1)(1)(2.1.6 遗传算子遗传算子一、选择一、选择（selection）算子算子 4、联赛选择、联赛选择（tournament selection）基本思想：基本思想：从当前群体中随机选择一定数量的个体（放回或者不从当前群体中随机选择一定数量的个体（放回或者不放回），将其中适应值最大的个体放入配对池中。反复执行这一放回），将其中适应值最大的个体放入配对池中。反复执行这一过程，直到配对池中的个体数量达到设定的值。过程，直到配对

19、池中的个体数量达到设定的值。联赛规模用联赛规模用q q表示，也称表示，也称q q-联赛选择。联赛选择。联赛选择与个体的适应度值由间接关系，注重适应度值大小的比联赛选择与个体的适应度值由间接关系，注重适应度值大小的比较。较。联赛规模一般取联赛规模一般取q q=2=2。2.1.6 遗传算子遗传算子一、选择一、选择（selection）算子算子 5、精英选择、精英选择 如果下一代群体的最佳个体适应度值小于当前群体最佳个体的适如果下一代群体的最佳个体适应度值小于当前群体最佳个体的适应度值，则将当前群体最佳个体或者适应度值大于下一代最佳个应度值，则将当前群体最佳个体或者适应度值大于下一代最佳个体适应度值

20、的多个个体直接复制到下一代，随机替代和替代最差体适应度值的多个个体直接复制到下一代，随机替代和替代最差的下一代群体中的相应数量的个体。的下一代群体中的相应数量的个体。精英选择是群体收敛到全局最优解的一种基本保障。精英选择是群体收敛到全局最优解的一种基本保障。2.1.6 遗传算子遗传算子一、选择一、选择（selection）算子算子 6、稳态选择、稳态选择 稳态选择操作中，稳态选择操作中，仅有少量个体仅有少量个体按适应度值比例选择方法被选择，按适应度值比例选择方法被选择，通过遗传操作生成新的个体。新个体放回到群体中时，随机替代通过遗传操作生成新的个体。新个体放回到群体中时，随机替代等量的旧个体，

21、或者替代等量的最差的旧个体。等量的旧个体，或者替代等量的最差的旧个体。Holland将稳态选择方法应用于分类器规则学习中，最大程度继承将稳态选择方法应用于分类器规则学习中，最大程度继承已获得的规则，实现增量学习。已获得的规则，实现增量学习。De Jong将下一代群体中生成的与上一代不同的新个体所占的比例将下一代群体中生成的与上一代不同的新个体所占的比例称为称为“代沟代沟”（generation gap）。）。代沟越大，说明新个体的生成代沟越大，说明新个体的生成比例越高，群体搜索新的编码空间的能力（探索）越强。比例越高，群体搜索新的编码空间的能力（探索）越强。2.1.6 遗传算子遗传算子二、交叉

22、二、交叉（CrossoverCrossover）算子算子 交叉算子是模仿自然界有性繁殖的基因重组过程，其作用在于将交叉算子是模仿自然界有性繁殖的基因重组过程，其作用在于将已有的优良基因遗传给下一代个体，并生成包含更复杂基因结构已有的优良基因遗传给下一代个体，并生成包含更复杂基因结构的新个体。的新个体。交叉操作一般分为以下几个步骤：交叉操作一般分为以下几个步骤：1）从配对池中随机取出要交配的一对个体；）从配对池中随机取出要交配的一对个体；2）根据位串长度）根据位串长度L，对要交叉的一对个体，随机选取对要交叉的一对个体，随机选取1,L-1中一中一个或多个整数个或多个整数k作为交叉位置；作为交叉位置

23、；3）根据交叉概率实施交叉操作，配对个体在交叉位置处，相互交）根据交叉概率实施交叉操作，配对个体在交叉位置处，相互交换各自的部分内容，从而形成新的一对个体。换各自的部分内容，从而形成新的一对个体。2.1.6 遗传算子遗传算子二、交叉二、交叉（CrossoverCrossover）算子算子 1、一点交叉、一点交叉（one-point crossover）位串位串A：1 1 0 1|1 0 1 0位串位串B：1 0 1 1|0 1 0 1位串位串A：1 1 0 1|0 1 0 1位串位串B：1 0 1 1|1 0 1 0 2.1.6 遗传算子遗传算子二、交叉二、交叉（CrossoverCrosso

24、ver）算子算子 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 2.1.6 遗传算子遗传算子二、交叉二、交叉（CrossoverCrossover）算子算子 1、多点交叉、多点交叉（multimulti-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|1 0|0 1位串位串B：1 0|0 1|0 1|1 02

25、.1.6 遗传算子遗传算子二、交叉二、交叉（CrossoverCrossover）算子算子 1、一致交叉、一致交叉一致交叉即染色体位串上的每一位按相同概率进行随机均匀交叉。一致交叉即染色体位串上的每一位按相同概率进行随机均匀交叉。一致交叉算子生成的新个体位：一致交叉算子生成的新个体位：操作描述如下：操作描述如下：，x是取值为是取值为0，1上符合均匀分布的随机变量。上符合均匀分布的随机变量。Laaas112111Laaas222212),(xpOc2/1,2/1,211xaxaaiii2/1,2/1,122xaxaaiii2.1.6 遗传算子遗传算子三、变异三、变异（MutationMutati

26、on）算子算子 变异操作模拟自然界生物体进化中染色体上某位基因发生的突变变异操作模拟自然界生物体进化中染色体上某位基因发生的突变现象，从而改变染色体的结构和物理性状。现象，从而改变染色体的结构和物理性状。在标准遗传算法中，变异算子通过按变异概率在标准遗传算法中，变异算子通过按变异概率pm随机反转某位等随机反转某位等位基因的二进制字符值来实现。位基因的二进制字符值来实现。对于给定的染色体位串对于给定的染色体位串 ，具体如下：，具体如下：生成新的个体生成新的个体 。其中，。其中，xi是对应于每一个基因位产是对应于每一个基因位产生的均匀随机变量，生的均匀随机变量，。Laaas21:),(xpOm否则

27、若,1imiiiapxaa,2,1LiLaaas210,1 ix2.1.6 遗传算子遗传算子四、逆转（四、逆转（Inversion Operator）算子）算子 逆转操作首先在个体位串上随机地选择两个点，位串染色体被这两个逆转操作首先在个体位串上随机地选择两个点，位串染色体被这两个点分成三段，将中间段的左右顺序倒转过来与另两段相连，形成点分成三段，将中间段的左右顺序倒转过来与另两段相连，形成新的个体位串。新的个体位串。比如：长度为比如：长度为10的二进制位串，其中下划线标示的等位基因为重要基的二进制位串，其中下划线标示的等位基因为重要基因：因：1011101101（是倒位位置）是倒位位置）经倒

28、位后变为经倒位后变为1011011101。新的位串中重要基因更为靠近，被单点交。新的位串中重要基因更为靠近，被单点交叉算子分离的可能性大大降低了。叉算子分离的可能性大大降低了。2.1.6 遗传算子遗传算子四、逆转（四、逆转（Inversion Operator）算子）算子 逆转算子有时要求采用类似于乱序编码的带基因位标号的染色体结构。逆转算子有时要求采用类似于乱序编码的带基因位标号的染色体结构。比如，长度为比如，长度为10的位串：的位串：位串：位串：1 0|1 1 1 0 1 1|0 1基因位编号：基因位编号：1 2|3 4 5 6 7 8|9 10按照上述方法实施逆转操作后，编号也随之翻转：

29、按照上述方法实施逆转操作后，编号也随之翻转：位串：位串：1 0 1 1 0 1 1 1 0 1基因位编号：基因位编号：1 2 8 7 6 5 4 3 9 10这样倒位操作就不会影响个体位串的适应值计算。这样倒位操作就不会影响个体位串的适应值计算。2.1.6 遗传算子遗传算子四、逆转（四、逆转（Inversion Operator）算子）算子 但是，逆转算子对交叉算子有一定影响。考虑下列但是，逆转算子对交叉算子有一定影响。考虑下列A，B位串之间的单位串之间的单点交叉：点交叉：位串位串A：1 0 1 1|1 0 1 1 0 1基因位编号：基因位编号：1 2 3 4|5 6 7 8 9 10位串位串

30、B：1 0 1 1|0 1 1 1 0 1基因位编号：基因位编号：1 2 8 7|6 5 4 3 9 10若简单地将第若简单地将第4个基因位以右的部分位串进行交换，得到：个基因位以右的部分位串进行交换，得到：位串位串A：1 0 1 1|0 1 1 1 0 1基因位编号：基因位编号：1 2 3 4|6 5 4 3 9 10位串位串B：1 0 1 1|1 0 1 1 0 1基因位编号：基因位编号：1 2 8 7|5 6 7 8 9 102.1.6 遗传算子遗传算子四、逆转（四、逆转（Inversion Operator）算子）算子 为解决此问题，一般遵循五种交换规则：为解决此问题，一般遵循五种交换

31、规则：1）严格同序交换严格同序交换，只允许同序位串才能交换。，只允许同序位串才能交换。2）生存性交换生存性交换，允许不同序位串进行交换，如果子代码串不包含完整，允许不同序位串进行交换，如果子代码串不包含完整的遗传信息，则不把它们放入新一代群体中。的遗传信息，则不把它们放入新一代群体中。3）任选方案交换任选方案交换，随意选择两个位串，并将其中任何一个指定为主序，随意选择两个位串，并将其中任何一个指定为主序位串，另一个位串则按主序位串的次序映射，然后再进行通常的位串，另一个位串则按主序位串的次序映射，然后再进行通常的交换，这样保证了交换结果的合法性。交换，这样保证了交换结果的合法性。4）最佳方案交

32、换最佳方案交换，与任选方案交换基本相同，只是将两个位串中适应，与任选方案交换基本相同，只是将两个位串中适应值高的位串作为主序位串。值高的位串作为主序位串。5）结构修复结构修复，对于两个子代位串中重复或短缺的基因，随机将重复的，对于两个子代位串中重复或短缺的基因，随机将重复的基因改变为缺省的基因，形成完整的位串结构。基因改变为缺省的基因，形成完整的位串结构。2.1.7 迭代终止条件迭代终止条件一般采用设定最大代数的方法一般采用设定最大代数的方法。其次，可以根据群体的收敛程度来判断，通过计算种群其次，可以根据群体的收敛程度来判断，通过计算种群中的基因多样性测度，即所有基因位的相似性程度来进中的基因

33、多样性测度，即所有基因位的相似性程度来进行控制行控制。第三，根据算法的离线性能和在线性能的变化进行判定第三，根据算法的离线性能和在线性能的变化进行判定。最后，在采用精英保留选择策略的情况下，按每代最佳最后，在采用精英保留选择策略的情况下，按每代最佳个体的适应值的变化情况确定个体的适应值的变化情况确定。2.1.8 控制参数控制参数1 1）位串长度位串长度L L：位串长度位串长度L L的选择取决于特定问题解的精度。的选择取决于特定问题解的精度。要求的精度越高，位串越长，但需要更多的计算时间。要求的精度越高，位串越长，但需要更多的计算时间。为提高运算效率，变长度位串或者在当前所达到的较小为提高运算效

34、率，变长度位串或者在当前所达到的较小可行域内重新编码，是一种可行的方法，并显示了良好可行域内重新编码，是一种可行的方法，并显示了良好性能。性能。2 2）群体规模群体规模n n：大群体含有较多模式，为遗传算法提供了大群体含有较多模式，为遗传算法提供了足够的模式采样容量，可以改进足够的模式采样容量，可以改进GAGA搜索的质量，防止成搜索的质量，防止成熟前收敛。但大群体增加了个体适应性评价的计算量，熟前收敛。但大群体增加了个体适应性评价的计算量，从而使收敛速度降低。一般情况下专家建议从而使收敛速度降低。一般情况下专家建议n n2020200200。2.1.8 控制参数控制参数3 3）交叉概率交叉概率

35、PcPc：交叉概率控制着交叉算子的应用频率，在交叉概率控制着交叉算子的应用频率，在每一代新的群体中，需要对每一代新的群体中，需要对PcPcn n个个体的染色体结构个个体的染色体结构进行交叉操作。交叉概率越高，群体中新结构的引人愈进行交叉操作。交叉概率越高，群体中新结构的引人愈快，已获得的优良基因结构的丢失速度也相应升高。而快，已获得的优良基因结构的丢失速度也相应升高。而交叉概率太低则可能导致搜索阻滞。一般取交叉概率太低则可能导致搜索阻滞。一般取Pc=0.60Pc=0.601.001.00。4 4）变异概率变异概率PmPm：变异操作是保持群体多样性的有效手段，变异操作是保持群体多样性的有效手段，

36、交叉结束后，交配池中的全部个体位串上的每位等位基交叉结束后，交配池中的全部个体位串上的每位等位基因按变异率因按变异率PmPm随机改变，因此每代中大约发生随机改变，因此每代中大约发生PmPmn nL L次次变异。变异概率太小，可能使某些基因位过早丢失的信变异。变异概率太小，可能使某些基因位过早丢失的信息无法恢复；而变异概率过高，则遗传搜索将变成随机息无法恢复；而变异概率过高，则遗传搜索将变成随机搜索。一般取搜索。一般取Pm=0.0050.01Pm=0.0050.01。2.1.8 控制参数控制参数从理论上来讲，不存在一组适用于所有问题的最佳参数从理论上来讲，不存在一组适用于所有问题的最佳参数值，随

37、着问题特征的变化，有效参数的差异往往非常显值，随着问题特征的变化，有效参数的差异往往非常显著。著。2.1.9 GA的性能评估的性能评估 关于搜索类算法的性能评估，一般可以归纳为算法的关于搜索类算法的性能评估，一般可以归纳为算法的求求解效率解效率和和求解质量求解质量两个方面。两个方面。算法的求解效率算法的求解效率是比较获得同样的可行解所需要的计算是比较获得同样的可行解所需要的计算时间。时间。算法的求解质量算法的求解质量是在规定的时间（或者时间相关指标）是在规定的时间（或者时间相关指标）内所获得的可行解的优劣。内所获得的可行解的优劣。2.1.9 GA的性能评估的性能评估 1 1适应值函数计算次数适

38、应值函数计算次数该指标是指发现同样适应性的个体，或者找到同样质量该指标是指发现同样适应性的个体，或者找到同样质量的可行解，所需要的关于个体评价的适应值函数的计算的可行解，所需要的关于个体评价的适应值函数的计算次数（次数（function evaluationsfunction evaluations）。显然，该值越小说明）。显然，该值越小说明相应相应GAGA的搜索效率越高。的搜索效率越高。该指标不仅可以用于不同参数设置该指标不仅可以用于不同参数设置GAGA的性能比较，也可的性能比较，也可以用于以用于GAGA与其他搜索算法的比较。与其他搜索算法的比较。2.1.9 GA的性能评估的性能评估 2 2

39、在线和离线性能函数在线和离线性能函数 1 1）在线性能函数在线性能函数（on-line performanceon-line performance）：设）：设GAGA的遗的遗传策略为传策略为s s（包括（包括LL，n n，PcPc，PmPm，算子形式等），该，算子形式等），该策略的在线性能：策略的在线性能：即在线性能反映了群体平均适应值经平滑处理后的变化即在线性能反映了群体平均适应值经平滑处理后的变化情况，描述了群体的整体性状和进化能力。情况，描述了群体的整体性状和进化能力。TtnjjlineontafTnsP01,_)()1(1)(2.1.9 GA的性能评估的性能评估 2 2在线和离线性能

40、函数在线和离线性能函数 2 2）离线性能函数离线性能函数（offline performance）：对于）：对于GA遗遗传策略传策略s，其离线性能，其离线性能其中，其中，f(a*，t)maxf(al,t)，f(a2,t)，f(an,t)，即，即当前群体中最佳个体的适应值。该指标反映了群体中最当前群体中最佳个体的适应值。该指标反映了群体中最佳个体适应值经平滑处理后的变化情况，描述了个体的佳个体适应值经平滑处理后的变化情况，描述了个体的进化能力和进化能力和GA的搜索能力。的搜索能力。TtlineofftafTsP0*_),(11)(2.1.9 GA的性能评估的性能评估 3 3最优解搜索性能最优解搜

41、索性能 GA用于函数优化的目的就是发现问题的全局最优解，用于函数优化的目的就是发现问题的全局最优解，所以通常采用当前群体发现的最佳可行解的改善情况作所以通常采用当前群体发现的最佳可行解的改善情况作为度量为度量GA搜索能力的基本指标。搜索能力的基本指标。2.2 遗传算法的模式理论遗传算法的模式理论221 模式与模式空间模式与模式空间位串上的某些等位基因的联结与适应值函数之间存在着某种联系，位串上的某些等位基因的联结与适应值函数之间存在着某种联系，这种联系提供了寻优过程的指导信息，引导着群体在位串空间中这种联系提供了寻优过程的指导信息，引导着群体在位串空间中的移动方向。的移动方向。采用字符集采用字

42、符集K=0，1对问题参数进行二进制编码，位串空间表示对问题参数进行二进制编码，位串空间表示为为SL1,0L，该空间的基数为，该空间的基数为|SL|2L。扩展字符集。扩展字符集K0,1,*，其中其中*是通配符或无关符（是通配符或无关符（wild cards，or“dont cares”），即），即可和可和0或或 1匹配。扩展位串空间表示为匹配。扩展位串空间表示为SeL1,0,*L，该空间的基，该空间的基数为数为 则称则称SeL为为SL的模式空间。显然，包含的模式空间。显然，包含2L个位串的位串个位串的位串空间，对应于空间，对应于3L个模式位串的模式空间。个模式位串的模式空间。LLeS3|2.2

43、遗传算法的模式理论遗传算法的模式理论221 模式与模式空间模式与模式空间定义：定义：扩展位串空间扩展位串空间SeL0,1,*L中的任何一个点中的任何一个点H H，称，称为对应于位串空间为对应于位串空间 SL1,0L的一个模式（的一个模式（Schema）：）：其中其中a(al，a2，aL)，H(H1，H2，HL)，i=1，2，L；，例如：例如：0*1 0，1*1*，0*,|iiiLaHHiSaaH1,0ia,1,0iH，LSaLeSH 2.2 遗传算法的模式理论遗传算法的模式理论221 模式与模式空间模式与模式空间模式是由模式是由SL中具有共同特征的位串所组成的集合，它中具有共同特征的位串所组成

44、的集合，它描述了该集合中位串上共同的基因特征。描述了该集合中位串上共同的基因特征。Goldberg将模式称为将模式称为“超平面超平面”（hyper plane），指），指出了模式在编码空间上的几何意义，模式包含的位串出了模式在编码空间上的几何意义，模式包含的位串是编码空间相应超平面上的点。是编码空间相应超平面上的点。例如：模式例如：模式0 0*表示位串长度为表示位串长度为4，两个高位基因为，两个高位基因为00的位串集合，即的位串集合，即0000，0001，0010，0011。模式模式 H1=1*表示函数解空间的右半区域表示函数解空间的右半区域模式模式 H2=0*表示函数解空间的左半区域表示函数

45、解空间的左半区域模式模式 H3=*1表示函数解空间的阴影区域（奇数位串）表示函数解空间的阴影区域（奇数位串）模式模式 H4=*0表示函数解空间的空白区域（偶数位串）表示函数解空间的空白区域（偶数位串）模式模式 H5=*1*表示函数解空间的阴影区域表示函数解空间的阴影区域模式模式 H6=*0*表示函数解空间的空白区域表示函数解空间的空白区域模式模式 H7=1 0*的表示域，代表了的表示域，代表了1/4的解空间的解空间模式模式 H8=*1*1 的表示域，代表了的表示域，代表了1/4的解空间的解空间2.2 遗传算法的模式理论遗传算法的模式理论221 模式与模式空间模式与模式空间模式的阶模式的阶（sc

46、hema order）是指模式中所含有）是指模式中所含有0、1确定基确定基因位的个数，记作因位的个数，记作O(H)。模式的定义距模式的定义距（defining length）是指模式中从左到右第）是指模式中从左到右第一个非一个非*位和最后一位非位和最后一位非*位之间的距离，记作位之间的距离，记作模式的维数模式的维数（schema dimension）是指模式中所包含的位）是指模式中所包含的位串的个数，也称为模式的容量，记作串的个数，也称为模式的容量，记作D(H)，D(H)=2L-O(H)。)(H2.2 遗传算法的模式理论遗传算法的模式理论221 模式与模式空间模式与模式空间令令m=m(H，t)

47、为模式为模式H在第在第t代群体中所含位串数量，代群体中所含位串数量，模式在模式在t代群体中包含的个体位串为代群体中包含的个体位串为a1,a2,am，称，称为模式为模式H在群体中的生存数量（在群体中的生存数量（survivals）或者采样样）或者采样样本（本（samples），），(j=1，2，m)，则模式，则模式H在第在第 t代群体中的适应值估计为代群体中的适应值估计为即模式的适应值估计（简称模式的适应值）是群体中即模式的适应值估计（简称模式的适应值）是群体中其所包含的全部个体的适应值的平均值。其所包含的全部个体的适应值的平均值。HajmjjmaftHf1/)(),(2.2 遗传算法的模式理论

48、遗传算法的模式理论221 模式与模式空间模式与模式空间从编码空间来看从编码空间来看，m（H，t）是当前群体中包含于模式是当前群体中包含于模式H的个体的个体数量，反映了所对应的模式空间的分布情况，该数量越大说明群数量，反映了所对应的模式空间的分布情况，该数量越大说明群体搜索越集中于模式体搜索越集中于模式H代表的子空间。代表的子空间。从模式空间来看从模式空间来看，m（H，t）是模式是模式H在当前群体中的个体采样在当前群体中的个体采样数量，反映了所对应的编码空间的分布情况。该数量越大说明群数量，反映了所对应的编码空间的分布情况。该数量越大说明群体中的个体越趋向相似和一致，在编码空间的搜索范围越小。体

49、中的个体越趋向相似和一致，在编码空间的搜索范围越小。一个模式一个模式H由位串长度由位串长度L、阶、阶O(H)、定义距、定义距 、容量、容量D(H)和适和适应值应值f(H，t)等五个指标来描述。模式的引入为在一个有限字符集等五个指标来描述。模式的引入为在一个有限字符集上定义的有限长度的位串之间的相似性度量和理论分析提供了有上定义的有限长度的位串之间的相似性度量和理论分析提供了有力的工具。力的工具。)(H2.2 遗传算法的模式理论遗传算法的模式理论222 模式定理和积木块假设模式定理和积木块假设 在选择算子作用下在选择算子作用下，对于平均适应度高于群体平均适应度，对于平均适应度高于群体平均适应度的

50、模式，其样本数将呈指数级增长：而对于平均适应度低的模式，其样本数将呈指数级增长：而对于平均适应度低于群体平均适应度的模式，其样本数将呈指数级减少。于群体平均适应度的模式，其样本数将呈指数级减少。在选择和交叉算子作用下在选择和交叉算子作用下，模式定义距越小，则群体中该，模式定义距越小，则群体中该模式个体数量越容易呈指数级增长；模式定义距越大，则模式个体数量越容易呈指数级增长；模式定义距越大，则群体中该模式个体数量越不容易呈指数级增长。群体中该模式个体数量越不容易呈指数级增长。在变异算子作用下在变异算子作用下，阶数越小模式，阶数越小模式H越易于生存；阶数越越易于生存；阶数越大，模式大，模式H越易于