第二章__遗传算法的基本原理课件

第二章第二章遗传算法的基本原理遗传算法的基本原理 2.1遗传算法的基本描述遗传算法的基本描述 2.2遗传算法的模式理论遗传算法的模式理论2.3 遗传算法与其他搜索算法的比较遗传算法与其他搜索算法的比较第二章 遗传算法的基本原理 2.1 遗传算法的基本描述 12.1遗传算法的基本描述遗传算法的基本描述2.1.1全局优化问题全局优化问题全全局局优优化化问问题题的的定定义义：给给定定非非空空集集合合S作作为为搜搜索索空空间间，f：SR为为目目标标函函数数，全全局局优优化化问问题题作作为为任任务务给给出出，即即在在搜搜索索空空间间中中找到至少一个使目标函数最大化的点。找到至少一个使目标函数最大化的点。全局最大值（点）的定义：全局最大值（点）的定义：函数值函数值称称为为一一个个全全局局最最大值，当且仅当大值，当且仅当成立时，成立时，被被称称为一个全局最大值点（全局最大解）。为一个全局最大值点（全局最大解）。局局部部极极大大值值与与局局部部极极大大值值点点（解解）的的定定义义：假假设设在在S上上给给定定了了某某个个距距离离度度量量 ，如如果果对对 ，使使得得对对 ，则则称称x为为一一个个局局部部极极大大值值点点，f(x)为为一一个个局局部部极极大大值值。当当目目标标函函数数有有多多个个局局部部极极大大点点时时，被被称称为多峰或多模态函数（为多峰或多模态函数（multi-modalityfunction）。）。2.1 遗传算法的基本描述2.1.1 全局优化问题 2第二章_遗传算法的基本原理课件3第二章_遗传算法的基本原理课件4第二章_遗传算法的基本原理课件5第二章_遗传算法的基本原理课件62.1.1标准遗传算法流程：标准遗传算法流程：1编码编码2初始群体的生成初始群体的生成3适应度评估检测适应度评估检测4WHILEDO1.选择选择2.交叉交叉3.变异变异4.适应度评估检测适应度评估检测5ENDDO2.1遗传算法的基本描述遗传算法的基本描述2.1.1 标准遗传算法流程：2.1 遗传算法的基本描述7选择选择交叉交叉当前代当前代中间代中间代下一代下一代选择交叉当前代中间代下一代82.1遗传算法的基本描述遗传算法的基本描述2.1.3遗传编码遗传编码定定义义：由由问问题题空空间间向向GA编编码码空空间间的的映映射射称称为为编编码码，而而由由编码空间向问题空间的映射成为编码空间向问题空间的映射成为译码译码。问题编码一般应满足以下三个原则：问题编码一般应满足以下三个原则：1）完完备备性性（completeness）：问问题题空空间间中中的的所所有有点点都都能能能成为能成为GA编码空间中的点的表现型编码空间中的点的表现型2）健健全全性性（soundness）：GA编编码码空空间间中中的的染染色色体体位位串串必须对应问题空间中的某一潜在解。必须对应问题空间中的某一潜在解。3）非非冗冗余余性性（non-redundancy）：染染色色体体和和潜潜在在解解必必须须一一对应。一一对应。2.1 遗传算法的基本描述2.1.3 遗传编码92.1遗传算法的基本描述遗传算法的基本描述2.1.3遗传编码遗传编码根根据据模模式式定定理理，DeJong进进一一步步提提出出了了较较为为客客观观明明确确的的编编码码评评估估准准则则，称称之之为为编编码码原原理理。具具体体可可以以概概括括为为两两条规则：条规则：1）有有意意义义积积木木块块编编码码规规则则：编编码码应应易易于于生生成成与与所所求求问问题题相关的短距和低阶的积木块。相关的短距和低阶的积木块。2）最最小小字字符符集集编编码码规规则则：编编码码应应采采用用最最小小字字符符集集，以以使使问题得到自然、简单的表示和描述。问题得到自然、简单的表示和描述。2.1 遗传算法的基本描述2.1.3 遗传编码102.1遗传算法的基本描述遗传算法的基本描述1二进制编码二进制编码1）连续实函数的二进制编码）连续实函数的二进制编码设一维连续实函数设一维连续实函数采采用用长长度度维维L的的二二进进制制字字符符串串进进行定长编码，建立位串空间：行定长编码，建立位串空间：k=1,2,K;l=1,2,L;K=2L表示精度为表示精度为。将个体又从位串空间转换到问题空间的译码函数将个体又从位串空间转换到问题空间的译码函数的公式定义为：的公式定义为：2.1 遗传算法的基本描述1二进制编码112.1遗传算法的基本描述遗传算法的基本描述对于对于 n维连续函数维连续函数 ，各各维维变变量量的的二二进进制制编编码码位位串串的的长长度度为为li,那那么么x的的编编码码从从左左到到右右依依次次构成总长度为构成总长度为的的二二进进制制编编码码位位串串。相相应应的的GA编编码码空空间间为：为：，K=2L该空间上的个体位串结构为该空间上的个体位串结构为对于给定的二进制编码位串对于给定的二进制编码位串sk,位段译码函数的形式为位段译码函数的形式为，i=1,2,n2.1 遗传算法的基本描述对于n维连续函数 122.1遗传算法的基本描述遗传算法的基本描述2其他编码其他编码1)大字符集编码（相对于二进制编码）大字符集编码（相对于二进制编码）2)序列编码（序列编码（TSP）3)实数编码实数编码4)树编码树编码5)自适应编码自适应编码6)乱序编码乱序编码 2.1 遗传算法的基本描述2其他编码132.1遗传算法的基本描述遗传算法的基本描述2.1.4群体设定群体设定1。初始群体的设定。初始群体的设定一般来讲，初始群体的设定可以采用如下的策略：一般来讲，初始群体的设定可以采用如下的策略：1)根根据据问问题题固固有有知知识识，设设法法把把握握最最优优解解所所占占空空间间在在整整个个问问题题空空间间中中的的分分布布范范围围，然然后后，在在此此分分布布范范围围内内设设定定初始群体。初始群体。2)先先随随机机生生成成一一定定数数目目的的个个体体，然然后后从从中中挑挑出出最最好好的的个个体体加加入入到到初初始始群群体体中中。这这一一过过程程不不断断重重复复，直直到到初初始始群体中个体数达到了预定的规模。群体中个体数达到了预定的规模。2.1 遗传算法的基本描述2.1.4 群体设定 142.1遗传算法的基本描述遗传算法的基本描述2.1.4群体设定群体设定2。群体规模的设定。群体规模的设定根根据据模模式式定定理理，若若群群体体规规模模为为M，则则遗遗传传操操作作可可从从这这M个个个个体体中中生生成成和和检检测测O(M3)个个模模式式，并并在在此此基础上不断形成和优化积木块，直到找到最优解。基础上不断形成和优化积木块，直到找到最优解。群群体体规规模模N N，模模式式阶阶i i，被被采采样样的的模模式式数数量量的的期期望望M Mi i(i=1,2,)(i=1,2,)之间满足如下关系：之间满足如下关系：群体规模一般不随迭代而变化，但也不绝对。群体规模一般不随迭代而变化，但也不绝对。2.1 遗传算法的基本描述2.1.4 群体设定 152.1遗传算法的基本描述遗传算法的基本描述2.1.5适应度函数（评价函数）适应度函数（评价函数）1。目标函数映射成适应度函数。目标函数映射成适应度函数2。适应度函数定标。适应度函数定标1）线性定标线性定标（linearscaling）f=af+b2）截断截断（sigmatruncation）3）乘幂标乘幂标f=fK4）指数定标指数定标f=exp(-bf)2.1 遗传算法的基本描述2.1.5 适应度函数（评价函162.1遗传算法的基本描述遗传算法的基本描述2.1.6遗传算子遗传算子包包括括三三个个基基本本遗遗传传算算子子（geneticoperator）：选选择择，交交叉叉和和变变异异。这三个遗传算子具有一些特点：这三个遗传算子具有一些特点：（1）这这三三个个算算子子的的操操作作都都是是随随机机化化操操作作，因因此此，群群体体中中个个体体向向最最优优解解迁迁移移的的规规则则是是随随机机的的。需需要要强强调调的的是是，这这种种随随机机化化操操作作和和传传统统的的随随机机搜搜索索方方法法是是有有区区别别的的。遗遗传传操操作作进进行行的的是是高高效效有有向向的的搜搜索索，而不是如一般随机搜索方法所进行的无向搜索。而不是如一般随机搜索方法所进行的无向搜索。（2）遗遗传传操操作作的的效效果果和和所所取取的的操操作作概概率率、编编码码方方法法、群群体体大大小小，以以及适应度函数的设定密切相关。及适应度函数的设定密切相关。（3）三三个个基基本本算算子子的的操操作作方方法法和和操操作作策策略略随随具具体体求求解解问问题题的的不不同同而而异。或者说，是和个体的编码方式直接相关。异。或者说，是和个体的编码方式直接相关。2.1 遗传算法的基本描述2.1.6 遗传算子 172.1.6遗传算子遗传算子一、选择一、选择（selection）算子算子从从群群体体中中选选择择优优胜胜个个体体，淘淘汰汰劣劣质质个个体体的的操操作作叫叫选选择择。选选 择择 算算 子子 有有 时时 又又 称称 为为 再再 生生 算算 子子（reproductionoperator）。选选择择即即从从当当前前群群体体中中选选择择适适应应度度值值高高的的个个体以生成体以生成配对池配对池（matingpool）的过程。）的过程。2.1.6 遗传算子一、选择（selection）算子 182.1.6遗传算子遗传算子一、选择一、选择（selection）算子算子1、适应度比例选择、适应度比例选择首首先先计计算算每每个个个个体体的的适适应应度度值值，然然后后计计算算出出此此适适应应度度值值在在群群体体适适应应度度值值总总和和中中所所占占的的比比例例，表表示示该该个个体体在在选选择择过过程程中中被被选选中中的的概概率率。选选择择过过程程体体现现了了生生物物进进化化过过程程中中“适适者者生生存存，优优胜胜劣劣汰汰”的的思想。思想。对对于于给给定定的的规规模模为为n的的群群体体 ，个个体体 的的适适应应度值为度值为 ，其选择概率为：，其选择概率为：问题：易出现未成熟收敛问题：易出现未成熟收敛2.1.6 遗传算子一、选择（selection）算子 192.1.6遗传算子遗传算子一、选择一、选择（selection）算子算子2、Boltzmann选择选择在在群群体体进进化化过过程程中中，不不同同阶阶段段需需要要不不同同地地选选择择压压力力。早早期期阶阶段段选选择择压压力力较较小小，我我们们希希望望较较差差地地个个体体也也又又一一定定地地生生存存机机会会，使使得得群群体体保保持持较较高高地地多多样样性性；后后期期阶阶段段，选选择择压压力力较较大大，我我们们希希望望GA缩缩小小搜搜索索邻邻域域，加加快快当当前前最最优优解解的的改改善善速速度度。为为了了动动态态调调整整群群体体进进化化过过程程中中的的选选择择压压力力，Goldberg设设计计了了Boltzmann选选择择方方法法。个个体体选择概率为：选择概率为：2.1.6 遗传算子一、选择（selection）算子 202.1.6遗传算子遗传算子一、选择一、选择（selection）算子算子3、排序选择、排序选择排排序序选选择择方方法法是是将将群群体体中中个个体体按按其其适适应应度度值值由由大大到到小小的的顺顺序序排排成成一个序列，然后将事先设计好的序列概率分配给每个个体。一个序列，然后将事先设计好的序列概率分配给每个个体。排排序序选选择择不不利利用用个个体体适适应应度度值值绝绝对对值值的的信信息息，可可以以避避免免群群体体进进化化过程中的适应度标度变换。过程中的适应度标度变换。2.1.6 遗传算子一、选择（selection）算子 212.1.6遗传算子遗传算子一、选择一、选择（selection）算子算子3、排序选择、排序选择对对于于给给定定的的规规模模为为n n的的群群体体 ，并并且且满满足足个个体体适适应应度值降序排列度值降序排列 。假假设设当当前前群群体体最最佳佳个个体体a a1 1在选择操作后的期望数量为在选择操作后的期望数量为 ，即，即；最最差差个个体体a an n在在选选择择操操作作后后的的期期望望数数量量为为 。其其它它个个体体的的期期望望数数量量按按等等差差序序列计算列计算，则则 ，故现在排序选择概率为，故现在排序选择概率为 2.1.6 遗传算子一、选择（selection）算子 222.1.6遗传算子遗传算子一、选择一、选择（selection）算子算子4、联赛选择、联赛选择（tournamentselection）基基本本思思想想：从从当当前前群群体体中中随随机机选选择择一一定定数数量量的的个个体体（放放回回或或者者不不放放回回），将将其其中中适适应应值值最最大大的的个个体体放放入入配配对对池池中中。反反复复执执行行这这一一过过程，直到配对池中的个体数量达到设定的值。程，直到配对池中的个体数量达到设定的值。联赛规模用联赛规模用q q表示，也称表示，也称q q-联赛选择。联赛选择。联赛选择与个体的适应度值由间接关系，注重适应度值大小的比较。联赛选择与个体的适应度值由间接关系，注重适应度值大小的比较。联赛规模一般取联赛规模一般取q q=2=2。2.1.6 遗传算子一、选择（selection）算子 232.1.6遗传算子遗传算子一、选择一、选择（selection）算子算子5、精英选择、精英选择如如果果下下一一代代群群体体的的最最佳佳个个体体适适应应度度值值小小于于当当前前群群体体最最佳佳个个体体的的适适应应度度值值，则则将将当当前前群群体体最最佳佳个个体体或或者者适适应应度度值值大大于于下下一一代代最最佳佳个个体体适适应应度度值值的的多多个个个个体体直直接接复复制制到到下下一一代代，随随机机替替代代和和替替代代最最差差的的下一代群体中的相应数量的个体。下一代群体中的相应数量的个体。精英选择是群体收敛到全局最优解的一种基本保障。精英选择是群体收敛到全局最优解的一种基本保障。2.1.6 遗传算子一、选择（selection）算子 242.1.6遗传算子遗传算子一、选择一、选择（selection）算子算子6、稳态选择、稳态选择稳稳态态选选择择操操作作中中，仅仅有有少少量量个个体体按按适适应应度度值值比比例例选选择择方方法法被被选选择择，通通过过遗遗传传操操作作生生成成新新的的个个体体。新新个个体体放放回回到到群群体体中中时时，随随机机替替代代等量的旧个体，或者替代等量的最差的旧个体。等量的旧个体，或者替代等量的最差的旧个体。Holland将将稳稳态态选选择择方方法法应应用用于于分分类类器器规规则则学学习习中中，最最大大程程度度继继承承已获得的规则，实现增量学习。已获得的规则，实现增量学习。DeJong将将下下一一代代群群体体中中生生成成的的与与上上一一代代不不同同的的新新个个体体所所占占的的比比例例称称为为“代代沟沟”（generationgap）。代代沟沟越越大大，说说明明新新个个体体的的生生成成比例越高，群体搜索新的编码空间的能力（探索）越强。比例越高，群体搜索新的编码空间的能力（探索）越强。2.1.6 遗传算子一、选择（selection）算子 252.1.6遗传算子遗传算子二、交叉二、交叉（CrossoverCrossover）算子算子交交叉叉算算子子是是模模仿仿自自然然界界有有性性繁繁殖殖的的基基因因重重组组过过程程，其其作作用用在在于于将将已已有有的的优优良良基基因因遗遗传传给给下下一一代代个个体体，并并生生成成包包含含更更复复杂杂基基因因结结构构的的新个体。新个体。交叉操作一般分为以下几个步骤：交叉操作一般分为以下几个步骤：1）从配对池中随机取出要交配的一对个体；）从配对池中随机取出要交配的一对个体；2）根根据据位位串串长长度度L，对对要要交交叉叉的的一一对对个个体体，随随机机选选取取1,L-1中中一一个或多个整数个或多个整数k作为交叉位置；作为交叉位置；3）根根据据交交叉叉概概率率实实施施交交叉叉操操作作，配配对对个个体体在在交交叉叉位位置置处处，相相互互交交换各自的部分内容，从而形成新的一对个体。换各自的部分内容，从而形成新的一对个体。2.1.6 遗传算子二、交叉（Crossover）算子 262.1.6遗传算子遗传算子二、交叉二、交叉（CrossoverCrossover）算子算子1、一点交叉、一点交叉（one-pointcrossover）位串位串A：1101|1010位串位串B：1011|0101位串位串A：1101|0101位串位串B：1011|10102.1.6 遗传算子二、交叉（Crossover）算子 272.1.6遗传算子遗传算子二、交叉二、交叉（CrossoverCrossover）算子算子1、两点交叉、两点交叉（twotwo-pointcrossover）位串位串A：11|011|010位串位串B：10|110|101位串位串A：11|110|010位串位串B：10|011|1012.1.6 遗传算子二、交叉（Crossover）算子 282.1.6遗传算子遗传算子二、交叉二、交叉（CrossoverCrossover）算子算子1、多点交叉、多点交叉（multimulti-pointcrossover）位串位串A：11|01|10|10位串位串B：10|11|01|01位串位串A：11|11|10|01位串位串B：10|01|01|102.1.6 遗传算子二、交叉（Crossover）算子 292.1.6遗传算子遗传算子二、交叉二、交叉（CrossoverCrossover）算子算子1、一致交叉、一致交叉一致交叉即染色体位串上的每一位按相同概率进行随机均匀交叉。一致交叉即染色体位串上的每一位按相同概率进行随机均匀交叉。一致交叉算子生成的新个体位：一致交叉算子生成的新个体位：操作描述如下：操作描述如下：，x是取值为是取值为0，1上符合均匀分布的随机变量。上符合均匀分布的随机变量。2.1.6 遗传算子二、交叉（Crossover）算子 302.1.6遗传算子遗传算子三、变异三、变异（MutationMutation）算子算子变变异异操操作作模模拟拟自自然然界界生生物物体体进进化化中中染染色色体体上上某某位位基基因因发发生生的的突突变变现象，从而改变染色体的结构和物理性状。现象，从而改变染色体的结构和物理性状。在在标标准准遗遗传传算算法法中中，变变异异算算子子通通过过按按变变异异概概率率pm随随机机反反转转某某位位等等位基因的二进制字符值来实现。位基因的二进制字符值来实现。对于给定的染色体位串对于给定的染色体位串，具体如下：，具体如下：生成新的个体生成新的个体 。其其中中，xi是是对对应应于于每每一一个个基基因因位位产产生的均匀随机变量，生的均匀随机变量，。2.1.6 遗传算子三、变异（Mutation）算子 312.1.6遗传算子遗传算子四、逆转（四、逆转（InversionOperator）算子）算子逆逆转转操操作作首首先先在在个个体体位位串串上上随随机机地地选选择择两两个个点点，位位串串染染色色体体被被这这两两个个点点分分成成三三段段，将将中中间间段段的的左左右右顺顺序序倒倒转转过过来来与与另另两两段段相相连连，形形成成新的个体位串。新的个体位串。比比如如：长长度度为为10的的二二进进制制位位串串，其其中中下下划划线线标标示示的的等等位位基基因因为为重重要要基基因：因：1011101101（是倒位位置）是倒位位置）经经倒倒位位后后变变为为1011011101。新新的的位位串串中中重重要要基基因因更更为为靠靠近近，被被单单点点交交叉算子分离的可能性大大降低了。叉算子分离的可能性大大降低了。2.1.6 遗传算子四、逆转（Inversion Oper322.1.6遗传算子遗传算子四、逆转（四、逆转（InversionOperator）算子）算子逆逆转转算算子子有有时时要要求求采采用用类类似似于于乱乱序序编编码码的的带带基基因因位位标标号号的的染染色色体体结结构构。比如，长度为比如，长度为10的位串：的位串：位串：位串：10|111011|01基因位编号：基因位编号：12|345678|910按照上述方法实施逆转操作后，编号也随之翻转：按照上述方法实施逆转操作后，编号也随之翻转：位串：位串：1011011101基因位编号：基因位编号：12876543910这样倒位操作就不会影响个体位串的适应值计算。这样倒位操作就不会影响个体位串的适应值计算。2.1.6 遗传算子四、逆转（Inversion Oper332.1.6遗传算子遗传算子四、逆转（四、逆转（InversionOperator）算子）算子但但是是，逆逆转转算算子子对对交交叉叉算算子子有有一一定定影影响响。考考虑虑下下列列A，B位位串串之之间间的的单单点交叉：点交叉：位串位串A：1011|101101基因位编号：基因位编号：1234|5678910位串位串B：1011|011101基因位编号：基因位编号：1287|6543910若简单地将第若简单地将第4个基因位以右的部分位串进行交换，得到：个基因位以右的部分位串进行交换，得到：位串位串A：1011|011101基因位编号：基因位编号：1234|6543910位串位串B：1011|101101基因位编号：基因位编号：1287|56789102.1.6 遗传算子四、逆转（Inversion Oper342.1.6遗传算子遗传算子四、逆转（四、逆转（InversionOperator）算子）算子为解决此问题，一般遵循五种交换规则：为解决此问题，一般遵循五种交换规则：1）严格同序交换严格同序交换，只允许同序位串才能交换。，只允许同序位串才能交换。2）生生存存性性交交换换，允允许许不不同同序序位位串串进进行行交交换换，如如果果子子代代码码串串不不包包含含完完整整的遗传信息，则不把它们放入新一代群体中。的遗传信息，则不把它们放入新一代群体中。3）任任选选方方案案交交换换，随随意意选选择择两两个个位位串串，并并将将其其中中任任何何一一个个指指定定为为主主序序位位串串，另另一一个个位位串串则则按按主主序序位位串串的的次次序序映映射射，然然后后再再进进行行通通常常的的交换，这样保证了交换结果的合法性。交换，这样保证了交换结果的合法性。4）最最佳佳方方案案交交换换，与与任任选选方方案案交交换换基基本本相相同同，只只是是将将两两个个位位串串中中适适应应值高的位串作为主序位串。值高的位串作为主序位串。5）结结构构修修复复，对对于于两两个个子子代代位位串串中中重重复复或或短短缺缺的的基基因因，随随机机将将重重复复的的基因改变为缺省的基因，形成完整的位串结构。基因改变为缺省的基因，形成完整的位串结构。2.1.6 遗传算子四、逆转（Inversion Oper352.1.7迭代终止条件迭代终止条件一般采用设定最大代数的方法一般采用设定最大代数的方法。其其次次，可可以以根根据据群群体体的的收收敛敛程程度度来来判判断断，通通过过计计算算种种群群中中的的基基因因多多样样性性测测度度，即即所所有有基基因因位位的的相相似似性性程程度度来来进进行控制行控制。第三，根据算法的离线性能和在线性能的变化进行判定第三，根据算法的离线性能和在线性能的变化进行判定。最最后后，在在采采用用精精英英保保留留选选择择策策略略的的情情况况下下，按按每每代代最最佳佳个体的适应值的变化情况确定个体的适应值的变化情况确定。2.1.7 迭代终止条件一般采用设定最大代数的方法。362.1.8控制参数控制参数1 1）位位串串长长度度L L：位位串串长长度度L L的的选选择择取取决决于于特特定定问问题题解解的的精精度度。要要求求的的精精度度越越高高，位位串串越越长长，但但需需要要更更多多的的计计算算时时间间。为为提提高高运运算算效效率率，变变长长度度位位串串或或者者在在当当前前所所达达到到的的较较小小可可行行域域内内重重新新编编码码，是是一一种种可可行行的的方方法法，并并显显示示了了良良好好性能。性能。2 2）群群体体规规模模n n：大大群群体体含含有有较较多多模模式式，为为遗遗传传算算法法提提供供了了足足够够的的模模式式采采样样容容量量，可可以以改改进进GAGA搜搜索索的的质质量量，防防止止成成熟熟前前收收敛敛。但但大大群群体体增增加加了了个个体体适适应应性性评评价价的的计计算算量量，从而使收敛速度降低。一般情况下专家建议从而使收敛速度降低。一般情况下专家建议n n2020200200。2.1.8 控制参数1）位串长度L：位串长度L的选择取决于372.1.8控制参数控制参数3 3）交交叉叉概概率率PcPc：交交叉叉概概率率控控制制着着交交叉叉算算子子的的应应用用频频率率，在在每每一一代代新新的的群群体体中中，需需要要对对PcnPcn个个个个体体的的染染色色体体结结构构进进行行交交叉叉操操作作。交交叉叉概概率率越越高高，群群体体中中新新结结构构的的引引人人愈愈快快，已已获获得得的的优优良良基基因因结结构构的的丢丢失失速速度度也也相相应应升升高高。而而交交叉叉概概率率太太低低则则可可能能导导致致搜搜索索阻阻滞滞。一一般般取取Pc=0.60Pc=0.601.001.00。4 4）变变异异概概率率PmPm：变变异异操操作作是是保保持持群群体体多多样样性性的的有有效效手手段段，交交叉叉结结束束后后，交交配配池池中中的的全全部部个个体体位位串串上上的的每每位位等等位位基基因因按按变变异异率率PmPm随随机机改改变变，因因此此每每代代中中大大约约发发生生PmPmnnL L次次变变异异。变变异异概概率率太太小小，可可能能使使某某些些基基因因位位过过早早丢丢失失的的信信息息无无法法恢恢复复；而而变变异异概概率率过过高高，则则遗遗传传搜搜索索将将变变成成随随机搜索。一般取机搜索。一般取Pm=0.0050.01Pm=0.0050.01。2.1.8 控制参数3）交叉概率Pc：交叉概率控制着交叉算382.1.8控制参数控制参数从从理理论论上上来来讲讲，不不存存在在一一组组适适用用于于所所有有问问题题的的最最佳佳参参数数值值，随随着着问问题题特特征征的的变变化化，有有效效参参数数的的差差异异往往往往非非常常显显著。著。2.1.8 控制参数392.1.9GA的性能评估的性能评估关关于于搜搜索索类类算算法法的的性性能能评评估估，一一般般可可以以归归纳纳为为算算法法的的求求解效率解效率和和求解质量求解质量两个方面。两个方面。算算法法的的求求解解效效率率是是比比较较获获得得同同样样的的可可行行解解所所需需要要的的计计算算时间。时间。算算法法的的求求解解质质量量是是在在规规定定的的时时间间（或或者者时时间间相相关关指指标标）内所获得的可行解的优劣。内所获得的可行解的优劣。2.1.9 GA的性能评估 关于搜索类算法的性能评估，一402.1.9GA的性能评估的性能评估1 1适应值函数计算次数适应值函数计算次数该该指指标标是是指指发发现现同同样样适适应应性性的的个个体体，或或者者找找到到同同样样质质量量的的可可行行解解，所所需需要要的的关关于于个个体体评评价价的的适适应应值值函函数数的的计计算算次次数数（function function evaluationsevaluations）。显显然然，该该值值越越小小说说明明相应相应GAGA的搜索效率越高。的搜索效率越高。该该指指标标不不仅仅可可以以用用于于不不同同参参数数设设置置GAGA的的性性能能比比较较，也也可可以用于以用于GAGA与其他搜索算法的比较。与其他搜索算法的比较。2.1.9 GA的性能评估 1适应值函数计算次数412.1.9GA的性能评估的性能评估2 2在线和离线性能函数在线和离线性能函数 1 1）在在线线性性能能函函数数（on-line on-line performanceperformance）：设设GAGA的的遗遗传传策策略略为为s s（包包括括LL，n n，PcPc，PmPm，算算子子形形式式等等），该该策略的在线性能：策略的在线性能：即即在在线线性性能能反反映映了了群群体体平平均均适适应应值值经经平平滑滑处处理理后后的的变变化化情况，描述了群体的整体性状和进化能力。情况，描述了群体的整体性状和进化能力。2.1.9 GA的性能评估 2在线和离线性能函数 422.1.9GA的性能评估的性能评估2 2在线和离线性能函数在线和离线性能函数 2 2）离离线线性性能能函函数数（offlineperformance）：对对于于GA遗遗传策略传策略s，其离线性能，其离线性能其其中中，f(a*，t)maxf(al,t)，f(a2,t)，f(an,t)，即即当当前前群群体体中中最最佳佳个个体体的的适适应应值值。该该指指标标反反映映了了群群体体中中最最佳佳个个体体适适应应值值经经平平滑滑处处理理后后的的变变化化情情况况，描描述述了了个个体体的进化能力和的进化能力和GA的搜索能力。的搜索能力。2.1.9 GA的性能评估 2在线和离线性能函数 432.1.9GA的性能评估的性能评估3 3最优解搜索性能最优解搜索性能 GA用用于于函函数数优优化化的的目目的的就就是是发发现现问问题题的的全全局局最最优优解解，所所以以通通常常采采用用当当前前群群体体发发现现的的最最佳佳可可行行解解的的改改善善情情况况作作为度量为度量GA搜索能力的基本指标。搜索能力的基本指标。2.1.9 GA的性能评估 3最优解搜索性能 442.2遗传算法的模式理论遗传算法的模式理论221模式与模式空间模式与模式空间位串上的某些等位基因的联结与适应值函数之间存在着某种联系，位串上的某些等位基因的联结与适应值函数之间存在着某种联系，这种联系提供了寻优过程的指导信息，引导着群体在位串空间中这种联系提供了寻优过程的指导信息，引导着群体在位串空间中的移动方向。的移动方向。采用字符集采用字符集K=0，1对问题参数进行二进制编码，位串空间表示对问题参数进行二进制编码，位串空间表示为为SL1,0L，该空间的基数为，该空间的基数为|SL|2L。扩展字符集。扩展字符集K0,1,*，其中，其中*是通配符或无关符（是通配符或无关符（wildcards，or“dontcares”），即可和），即可和0或或1匹配。扩展位串空间表示为匹配。扩展位串空间表示为SeL1,0,*L，该空间的基数为，该空间的基数为则称则称SeL为为SL的模式空间。显然，包含的模式空间。显然，包含2L个位串的位串空间，对应于个位串的位串空间，对应于3L个模式位串的模式空间。个模式位串的模式空间。2.2 遗传算法的模式理论221 模式与模式空间452.2遗传算法的模式理论遗传算法的模式理论221模式与模式空间模式与模式空间定义：定义：扩展位串空间扩展位串空间SeL0,1,*L中的任何一个点中的任何一个点H H，称，称为对应于位串空间为对应于位串空间SL1,0L的一个模式（的一个模式（Schema）：）：其中其中a(al，a2，aL)，H(H1，H2，HL)，i=1，2，L；，例如：例如：0*10，1*1*，0*，2.2 遗传算法的模式理论221 模式与模式空间，462.2遗传算法的模式理论遗传算法的模式理论221模式与模式空间模式与模式空间模模式式是是由由SL中中具具有有共共同同特特征征的的位位串串所所组组成成的的集集合合，它它描述了该集合中位串上共同的基因特征。描述了该集合中位串上共同的基因特征。Goldberg将将模模式式称称为为“超超平平面面”（hyperplane），指指出出了了模模式式在在编编码码空空间间上上的的几几何何意意义义，模模式式包包含含的的位位串串是编码空间相应超平面上的点。是编码空间相应超平面上的点。例例如如：模模式式00*表表示示位位串串长长度度为为4，两两个个高高位位基基因因为为00的位串集合，即的位串集合，即0000，0001，0010，0011。2.2 遗传算法的模式理论221 模式与模式空间47第二章_遗传算法的基本原理课件48模式模式H1=1*表示函数解空间的右半区域表示函数解空间的右半区域模式模式H2=0*表示函数解空间的左半区域表示函数解空间的左半区域模式 H1=1*表示函数解空间的右半区域49模式模式H3=*1表示函数解空间的阴影区域（奇数位串）表示函数解空间的阴影区域（奇数位串）模式模式H4=*0表示函数解空间的空白区域（偶数位串）表示函数解空间的空白区域（偶数位串）模式 H3=*1表示函数解空间的阴影区域（50模式模式H5=*1*表示函数解空间的阴影区域表示函数解空间的阴影区域模式模式H6=*0*表示函数解空间的空白区域表示函数解空间的空白区域模式 H5=*1*表示函数解空间的阴影区域51模式模式H7=10*的表示域，代表了的表示域，代表了1/4的解空间的解空间模式 H7=1 0*的表示域，代表了1/4的52模式模式H8=*1*1的表示域，代表了的表示域，代表了1/4的解空间的解空间模式 H8=*1*1 的表示域，代表了1/4的53第二章_遗传算法的基本原理课件542.2遗传算法的模式理论遗传算法的模式理论221模式与模式空间模式与模式空间模模式式的的阶阶（schemaorder）是是指指模模式式中中所所含含有有0、1确确定定基基因位的个数，记作因位的个数，记作O(H)。模模式式的的定定义义距距（defininglength）是是指指模模式式中中从从左左到到右右第第一个非一个非*位和最后一位非位和最后一位非*位之间的距离，记作位之间的距离，记作模模式式的的维维数数（schemadimension）是是指指模模式式中中所所包包含含的的位位串的个数，也称为模式的容量，记作串的个数，也称为模式的容量，记作D(H)，D(H)=2L-O(H)。2.2 遗传算法的模式理论221 模式与模式空间552.2遗传算法的模式理论遗传算法的模式理论221模式与模式空间模式与模式空间令令m=m(H，t)为为模模式式H在在第第t代代群群体体中中所所含含位位串串数数量量，模模式式在在t代代群群体体中中包包含含的的个个体体位位串串为为a1,a2,am，称称为为模模式式H在在群群体体中中的的生生存存数数量量（survivals）或或者者采采样样样本（样本（samples），），(j=1，2，m)，则则模式模式H在第在第t代群体中的适应值估计为代群体中的适应值估计为即即模模式式的的适适应应值值估估计计（简简称称模模式式的的适适应应值值）是是群群体体中中其所包含的全部个体的适应值的平均值。其所包含的全部个体的适应值的平均值。2.2 遗传算法的模式理论221 模式与模式空间562.2遗传算法的模式理论遗传算法的模式理论221模式与模式空间模式与模式空间从从编编码码空空间间来来看看，m（H，t）是是当当前前群群体体中中包包含含于于模模式式H的的个个体体数数量量，反反映映了了所所对对应应的的模模式式空空间间的的分分布布情情况况，该该数数量量越越大大说说明明群群体搜索越集中于模式体搜索越集中于模式H代表的子空间。代表的子空间。从从模模式式空空间间来来看看，m（H，t）是是模模式式H在在当当前前群群体体中中的的个个体体采采样样数数量量，反反映映了了所所对对应应的的编编码码空空间间的的分分布布情情况况。该该数数量量越越大大说说明明群群体中的个体越趋向相似和一致，在编码空间的搜索范围越小。体中的个体越趋向相似和一致，在编码空间的搜索范围越小。一一个个模模式式H由由位位串串长长度度L、阶阶O(H)、定定义义距距、容容量量D(H)和和适适应应值值f(H，t)等等五五个个指指标标来来描描述述。模模式式的的引引入入为为在在一一个个有有限限字字符符集集上上定定义义的的有有限限长长度度的的位位串串之之间间的的相相似似性性度度量量和和理理论论分分析析提提供供了了有有力的工具。力的工具。2.2 遗传算法的模式理论221 模式与模式空间572.2遗传算法的模式理论遗传算法的模式理论222模式定理和积木块假设模式定理和积木块假设在在选选择择算算子子作作用用下下，对对于于平平均均适适应应度度高高于于群群体体平平均均适适应应度度的的模模式式，其其样样本本数数将将呈呈指指数数级级增增长长：而而对对于于平平均均适适应应度度低低于群体平均适应度的模式，其样本数将呈指数级减少。于群体平均适应度的模式，其样本数将呈指数级减少。在在选选择择和和交交叉叉算算子子作作用用下下，模模式式定定义义距距越越小小，则则群群体体中中该该模模式式个个体体数数量量越越容容易易呈呈指指数数级级增增长长；模模式式定定义义距距越越大大，则则群体中该模式个体数量越不容易呈指数级增长。群体中该模式个体数量越不容易呈指数级增长。在变异算子作用下在变异算子作用下，阶数越小模式，阶数越小模式H越易于生存；阶数越越易于生存；阶数越大，模式大，模式H越易于被破坏。越易于被破坏。2.2 遗传算法的模式理论222 模式定理和积木块假设582.2遗传算法的模式理论遗传算法的模式理论222模式定理和积木块假设模式定理和积木块假设模模式式定定理理：在在遗遗传传算算子子选选择择、交交叉叉、变变异异的的作作用用下下，那那些些低低阶阶、定定义义距距短短的的、超超过过群群体体平平均均适适应应度度值值的的模模式式的的生生存存数量，将随着迭代次数的增加以指数规律增长。数量，将随着迭代次数的增加以指数规律增长。理理论论基基础础：统统计计决决策策中中的的双双臂臂赌赌机机问问题题表表明明：按按指指数数规规律律提提高高将将硬硬币币投投往往平平均均支支付付高高的的赌赌机机的的概概率率，可可以以获获得得最最大大的的累累积积支支付付。应应用用到到优优化化问问题题则则是是：要要获获得得最最优优的的可可行行解解，则则必必须须保保证证较较优优解解的的样样本本数数呈呈指指数数级级增增长长。而而模模式式定定理理保保证证了了较较优优的的模模式式（遗遗传传算算法法的的较较优优解解）的的样样本本数数呈呈指指数数级级增长，从而给出了遗传算法的理论基础。增长，从而给出了遗传算法的理论基础。2.2 遗传算法的模式理论222 模式定理和积木块假设592.2遗传算法的模式理论遗传算法的模式理论222模式定理和积木块假设模式定理和积木块假设定定义义：具具有有低低阶阶、短短定定义义距距以以及及高高适适应应度度的的模模式式称称作作积积木木块。块。积积木木块块假假设设（building building block block hypothesishypothesis）：低低阶阶、短短距距高高平平均均适适应应度度的的模模式式（积积木木块块）在在遗遗传传算算子子作作用用下下，相相互互结结合合，能能生生成成高高阶阶、长长距距、高高平平均均适适应应度度的的模模式式，并并可可最最终生成全局最优解。终生成全局最优解。2.2 遗传算法的模式理论222 模式定理和积木块假设602.2遗传算法的模式理论遗传算法的模式理论222模式定理和积木块假设模式定理和积木块假设模模式式定定理理和和积积木木块块假假设设比比较较准准确确地地模模拟拟了了自自然然界界的的物物种种竞竞争争和和遗遗传传法法则则，其其中中模模式式定定理理描描述述了了GAGA群群体体中中模模式式之之间间的的竞竞争争关关系系，积积木木块块假假设设说说明明了了有有效效基基因因之之间间的的继继承承与与重重组组。因因此此，模模式式定定理理和和积积木木块块假假设设构构成成了了关关于于GAGA进进化化过过程程能能够够发发现现最最优优解解的的一一个个充充分分条条件件，被被认认为为是是解解释释遗遗传传算算法法寻寻优优原原理理的的较较系系统统的的理理论论，统统称称为为模模式式理理论论（schema schema theorytheory）。它它们们也也是是GAGA进进化化动动力力学学的的基基本本理理论论，尽尽管管还还存存在在着着不不完完善善之处，但是它为深入研究遗传算法的运行机理奠定了基础。之处，但是它为深入研究遗传算法的运行机理奠定了基础。2.2 遗传算法的模式理论222 模式定理和积木块假设612.2遗传算法的模式理论遗传算法的模式理论222模式定理和积木块假设模式定理和积木块假设模模式式定定理理在在一一定定程程度度上上证证明明了了标标准准遗遗传传算算法法的的有有效效性性，但但它仍有以下的缺点：它仍有以下的缺点：（1 1）模模式式定定理理只只对对二二进进制制编编码码适适用用，对对其其他他编编码码方方案案尚尚没没有有相应的结论成立。相应的结论成立。（2 2）模模式式定定理理只只给给出出了了在在下下一一代代包包含含模模式式H H的的个个体体数数的的下下限限。我们无法据此推断算法的收敛性。我们无法据此推断算法的收敛性。（3 3）模式定理没有解决算法设计中控制参数选取等问题。）模式定理没有解决算法设计中控制参数选取等问题。2.2 遗传算法的模式理论222 模式定理和积木块假设622.2遗传算法的模式理论遗传算法的模式理论222模式定理和积木块假设模式定理和积木块假设BethkeBethke采采用用WalshWalsh函函数数和和一一种种巧巧妙妙的的模模式式变变换换，提提出出了了一一种种采采用用WalshWalsh系系数数计计算算模模式式平平均均适适应应度度的的有有效效分分析析方方法法，这这使使得得在在一一些些特特定定的的适适应应度度函函数数和和编编码码方方式式下下，可可以以判判定定积积木木块通过相互组合是否会产生最优解或接近最优解。块通过相互组合是否会产生最优解或接近最优解。HollandHolland把把BethkeBethke的的方方法法推推广广到到了了当当群群体体非非均均匀匀分分布布时时的的模模式平均适应度分析上。式平均适应度分析上。2.2 遗传算法的模式理论222 模式定理和积木块假设632.2遗传算法的模式理论遗传算法的模式理论23骗问题骗问题骗骗问问题题（deceptiveProblem），即即构构造造一一个个问问题题，给给定定一一些些带带欺欺骗骗性性质质的的初初始始条条件件，“迷迷惑惑”遗遗传传算算法法，使使其其偏偏离离全全局最优解。局最优解。为为此此，要要最最大大限限度度地地违违背背积积木木块块假假设设，即即使使得得低低阶阶、短短距距高于平均适应度的模式生成局部最优点。高于平均适应度的模式生成局部最优点。由由模模式式理理论论，一一个个问问题题能能否否用用遗遗传传算算法法有有效效地地求求解解，取取决决于于问问题题编编码码是是否否满满足足积积木木块块假假设设，满满足足者者用用遗遗传传算算法法求求解解效率较高，不满足者效率效率较高，不满足者效率较低、甚至找不到满意解。较低、甚至找不到满意解。2.2 遗传算法的模式理论23 骗问题 642.2遗传算法的模式理论遗传算法的模式理论23骗问题骗问题定定义义(竞竞争争模模式式)：若若模模式式H与与H中中*的的位位置置完完全全一一致致，但但任任一确定位的编码均不同，则称一确定位的编码均不同，则称H与与H互为竞争模式。互为竞争模式。定定义义(欺欺骗骗性性)：假假设设f(x)的的最最大大值值对对应应的的x集集合合为为x*，H为为一一包包含含x*的的m阶阶模模式式。H的的竞竞争争模模式式为为H，而而且且f(H)f(H)，则则f为为m阶欺骗。阶欺骗。2.2 遗传算法的模式理论23 骗问题 65