遗传算法基本原理幻灯片.ppt

遗传算法基本原理第1页，共70页，编辑于2022年，星期三第2页，共70页，编辑于2022年，星期三4.1.1标准遗传算法流程：标准遗传算法流程：1编码编码2初始群体的生成初始群体的生成3适应度评估检测适应度评估检测4WHILEDO1.选择选择2.交叉交叉3.变异变异4.适应度评估检测适应度评估检测5ENDDO4.1遗传算法的基本描述遗传算法的基本描述第3页，共70页，编辑于2022年，星期三选择选择交叉交叉当前代当前代中间代中间代下一代下一代第4页，共70页，编辑于2022年，星期三4.1遗传算法的基本描述遗传算法的基本描述4.1.3遗传编码遗传编码定定义义：由由问问题题空空间间向向GA编编码码空空间间的的映映射射称称为为编编码码，而而由由编编码码空空间向问题空间的映射成为间向问题空间的映射成为译码译码。问题编码一般应满足以下三个原则：问题编码一般应满足以下三个原则：1）完完备备性性（completeness）：问问题题空空间间中中的的所所有有点点都都能能能能成成为为GA编码空间中的点的表现型编码空间中的点的表现型2）健健全全性性（soundness）：GA编编码码空空间间中中的的染染色色体体位位串串必必须须对对应问题空间中的某一潜在解。应问题空间中的某一潜在解。3）非非冗冗余余性性（non-redundancy）：染染色色体体和和潜潜在在解解必必须须一一一一对应。对应。第5页，共70页，编辑于2022年，星期三4.1遗传算法的基本描述遗传算法的基本描述4.1.3遗传编码遗传编码根根据据模模式式定定理理，DeJong进进一一步步提提出出了了较较为为客客观观明明确确的的编编码码评估准则，称之为评估准则，称之为编码原理编码原理。具体可以概括为两条规则：。具体可以概括为两条规则：1）有有意意义义积积木木块块编编码码规规则则：编编码码应应易易于于生生成成与与所所求求问问题题相相关关的短距和低阶的积木块。的短距和低阶的积木块。2）最最小小字字符符集集编编码码规规则则：编编码码应应采采用用最最小小字字符符集集，以以使使问问题题得到自然、简单的表示和描述。得到自然、简单的表示和描述。第6页，共70页，编辑于2022年，星期三4.1遗传算法的基本描述遗传算法的基本描述1二进制编码二进制编码1）连续实函数的二进制编码）连续实函数的二进制编码设一维连续实函数设一维连续实函数采采用用长长度度维维L的的二二进进制制字字符符串串进进行行定定长长编编码码，建立位串空间：建立位串空间：k=1,2,K;l=1,2,L;K=2L表示精度为表示精度为。将个体又从位串空间转换到问题空间的译码函数将个体又从位串空间转换到问题空间的译码函数的公式定义为：的公式定义为：第7页，共70页，编辑于2022年，星期三4.1遗传算法的基本描述遗传算法的基本描述对于对于n维连续函数维连续函数，各各维维变变量量的的二二进进制制编编码码位位串串的的长长度度为为li,那那么么x的的编编码码从左到右依次构成总长度为从左到右依次构成总长度为的的二二进进制制编编码码位位串串。相相应应的的GA编编码码空空间为：间为：，K=2L该空间上的个体位串结构为该空间上的个体位串结构为对于给定的二进制编码位串对于给定的二进制编码位串sk,位段译码函数的形式为位段译码函数的形式为，i=1,2,n第8页，共70页，编辑于2022年，星期三4.1遗传算法的基本描述遗传算法的基本描述2其他编码其他编码1)大字符集编码（相对于二进制编码）大字符集编码（相对于二进制编码）2)序列编码（序列编码（TSP）3)实数编码实数编码4)树编码树编码5)自适应编码自适应编码6)乱序编码乱序编码 第9页，共70页，编辑于2022年，星期三4.1遗传算法的基本描述遗传算法的基本描述4.1.4群体设定群体设定1。初始群体的设定。初始群体的设定一般来讲，初始群体的设定可以采用如下的策略：一般来讲，初始群体的设定可以采用如下的策略：1)根根据据问问题题固固有有知知识识，设设法法把把握握最最优优解解所所占占空空间间在在整整个个问问题题空空间中的分布范围，然后，在此分布范围内设定初始群体。间中的分布范围，然后，在此分布范围内设定初始群体。2)先先随随机机生生成成一一定定数数目目的的个个体体，然然后后从从中中挑挑出出最最好好的的个个体体加加入入到到初初始始群群体体中中。这这一一过过程程不不断断重重复复，直直到到初初始始群群体体中个体数达到了预定的规模。中个体数达到了预定的规模。第10页，共70页，编辑于2022年，星期三4.1遗传算法的基本描述遗传算法的基本描述4.1.4群体设定群体设定2。群体规模的设定。群体规模的设定根根据据模模式式定定理理，若若群群体体规规模模为为M，则则遗遗传传操操作作可可从从这这M个个个个体体中中生生成成和和检检测测O(M3)个个模模式式，并并在在此此基基础础上上不不断断形形成和优化积木块，直到找到最优解。成和优化积木块，直到找到最优解。群群体体规规模模N N，模模式式阶阶i i，被被采采样样的的模模式式数数量量的的期期望望M Mi i(i(i=1,2,1,2,),)之间满足如下关系：之间满足如下关系：群体规模一般不随迭代而变化，但也不绝对。群体规模一般不随迭代而变化，但也不绝对。第11页，共70页，编辑于2022年，星期三4.1遗传算法的基本描述遗传算法的基本描述4.1.5适应度函数（评价函数）适应度函数（评价函数）1。目标函数映射成适应度函数。目标函数映射成适应度函数2。适应度函数定标。适应度函数定标1）线性定标线性定标（linearscaling）f=af+b2）截断截断（sigmatruncation）3）乘幂标乘幂标f=fK4）指数定标指数定标f=exp(-bf)第12页，共70页，编辑于2022年，星期三4.1遗传算法的基本描述遗传算法的基本描述4.1.6遗传算子遗传算子包包括括三三个个基基本本遗遗传传算算子子（geneticoperator）：选选择择，交交叉叉和和变变异异。这这三个遗传算子具有一些特点：三个遗传算子具有一些特点：（1）这这三三个个算算子子的的操操作作都都是是随随机机化化操操作作，因因此此，群群体体中中个个体体向向最最优优解解迁迁移移的的规规则则是是随随机机的的。需需要要强强调调的的是是，这这种种随随机机化化操操作作和和传传统统的的随随机机搜搜索索方方法法是是有有区区别别的的。遗遗传传操操作作进进行行的的是是高高效效有有向向的的搜搜索索，而而不不是是如如一一般般随随机机搜搜索索方方法法所所进进行的无向搜索。行的无向搜索。（2）遗遗传传操操作作的的效效果果和和所所取取的的操操作作概概率率、编编码码方方法法、群群体体大大小小，以以及及适适应度函数的设定密切相关。应度函数的设定密切相关。（3）三三个个基基本本算算子子的的操操作作方方法法和和操操作作策策略略随随具具体体求求解解问问题题的的不不同同而而异异。或者说，是和个体的编码方式直接相关。或者说，是和个体的编码方式直接相关。第13页，共70页，编辑于2022年，星期三4.1.6遗传算子遗传算子一、选择一、选择（selection）算子算子从从群群体体中中选选择择优优胜胜个个体体，淘淘汰汰劣劣质质个个体体的的操操作作叫叫选选择择。选选择择算算子子有有时时又又称称为为再再生生算算子子（reproductionoperator）。选选择择即即从从当当前前群群体体中中选选择择适适应应度度值值高高的的个个体体以以生生成成配配对对池池（matingpool）的的过程。过程。第14页，共70页，编辑于2022年，星期三4.1.6遗传算子遗传算子一、选择一、选择（selection）算子算子1、适应度比例选择、适应度比例选择首首先先计计算算每每个个个个体体的的适适应应度度值值，然然后后计计算算出出此此适适应应度度值值在在群群体体适适应应度度值值总总和和中中所所占占的的比比例例，表表示示该该个个体体在在选选择择过过程程中中被被选选中中的的概概率率。选选择择过过程程体体现现了了生生物物进进化过程中化过程中“适者生存，优胜劣汰适者生存，优胜劣汰”的思想。的思想。对对于于给给定定的的规规模模为为n的的群群体体 ，个个体体 的的适适应应度度值值为为 ，其选择概率为：，其选择概率为：问题：易出现未成熟收敛问题：易出现未成熟收敛第15页，共70页，编辑于2022年，星期三4.1.6遗传算子遗传算子一、选择一、选择（selection）算子算子2、Boltzmann选择选择在在群群体体进进化化过过程程中中，不不同同阶阶段段需需要要不不同同地地选选择择压压力力。早早期期阶阶段段选选择择压压力力较较小小，我我们们希希望望较较差差地地个个体体也也又又一一定定地地生生存存机机会会，使使得得群群体体保保持持较较高高地地多多样样性性；后后期期阶阶段段，选选择择压压力力较较大大，我我们们希希望望GA缩缩小小搜搜索索邻邻域域，加加快快当当前前最最优优解解的的改改善善速速度度。为为了了动动态态调调整整群群体体进进化化过过程程中中的的选选择择压压力力，Goldberg设设计计了了Boltzmann选择方法。个体选择概率为：选择方法。个体选择概率为：第16页，共70页，编辑于2022年，星期三4.1.6遗传算子遗传算子一、选择一、选择（selection）算子算子3、排序选择、排序选择排排序序选选择择方方法法是是将将群群体体中中个个体体按按其其适适应应度度值值由由大大到到小小的的顺顺序序排排成成一一个个序序列列，然后将事先设计好的序列概率分配给每个个体。然后将事先设计好的序列概率分配给每个个体。排排序序选选择择不不利利用用个个体体适适应应度度值值绝绝对对值值的的信信息息，可可以以避避免免群群体体进进化化过过程程中中的的适适应应度标度变换。度标度变换。第17页，共70页，编辑于2022年，星期三4.1.6遗传算子遗传算子一、选择一、选择（selection）算子算子3、排序选择、排序选择对对于于给给定定的的规规模模为为n n的的群群体体 ，并并且且满满足足个个体体适适应应度度值值降降序序排排列列 。假假设设当当前前群群体体最最佳佳个个体体a a1 1在在选选择择操操作作后后的的期期望望数数量量为为 ，即，即；最最差差个个体体a an n在在选选择择操操作作后后的的期期望望数数量量为为 。其它个体的期望数量按等差序列计算其它个体的期望数量按等差序列计算，故现在排序选择概率为，故现在排序选择概率为 第18页，共70页，编辑于2022年，星期三4.1.6遗传算子遗传算子一、选择一、选择（selection）算子算子4、联赛选择、联赛选择（tournamentselection）基基本本思思想想：从从当当前前群群体体中中随随机机选选择择一一定定数数量量的的个个体体（放放回回或或者者不不放放回回），将将其其中中适适应应值值最最大大的的个个体体放放入入配配对对池池中中。反反复复执执行行这这一一过过程程，直直到到配配对对池池中中的的个个体体数数量量达达到到设定的值。设定的值。联赛规模用联赛规模用q q表示，也称表示，也称q q-联赛选择。联赛选择。联赛选择与个体的适应度值由间接关系，注重适应度值大小的比较。联赛选择与个体的适应度值由间接关系，注重适应度值大小的比较。联赛规模一般取联赛规模一般取q q=2=2。第19页，共70页，编辑于2022年，星期三4.1.6遗传算子遗传算子一、选择一、选择（selection）算子算子5、精英选择、精英选择如如果果下下一一代代群群体体的的最最佳佳个个体体适适应应度度值值小小于于当当前前群群体体最最佳佳个个体体的的适适应应度度值值，则则将将当当前前群群体体最最佳佳个个体体或或者者适适应应度度值值大大于于下下一一代代最最佳佳个个体体适适应应度度值值的的多多个个个个体体直直接接复制到下一代，随机替代和替代最差的下一代群体中的相应数量的个体。复制到下一代，随机替代和替代最差的下一代群体中的相应数量的个体。精英选择是群体收敛到全局最优解的一种基本保障。精英选择是群体收敛到全局最优解的一种基本保障。第20页，共70页，编辑于2022年，星期三4.1.6遗传算子遗传算子一、选择一、选择（selection）算子算子6、稳态选择、稳态选择稳稳态态选选择择操操作作中中，仅仅有有少少量量个个体体按按适适应应度度值值比比例例选选择择方方法法被被选选择择，通通过过遗遗传传操操作作生生成成新新的的个个体体。新新个个体体放放回回到到群群体体中中时时，随随机机替替代代等等量量的的旧旧个个体，或者替代等量的最差的旧个体。体，或者替代等量的最差的旧个体。Holland将将稳稳态态选选择择方方法法应应用用于于分分类类器器规规则则学学习习中中，最最大大程程度度继继承承已已获获得的规则，实现增量学习。得的规则，实现增量学习。DeJong将将下下一一代代群群体体中中生生成成的的与与上上一一代代不不同同的的新新个个体体所所占占的的比比例例称称为为“代代沟沟”（generationgap）。代代沟沟越越大大，说说明明新新个个体体的的生生成成比比例例越越高高，群群体体搜索新的编码空间的能力（探索）越强。搜索新的编码空间的能力（探索）越强。第21页，共70页，编辑于2022年，星期三4.1.6遗传算子遗传算子二、交叉二、交叉（CrossoverCrossover）算子算子交交叉叉算算子子是是模模仿仿自自然然界界有有性性繁繁殖殖的的基基因因重重组组过过程程，其其作作用用在在于于将将已已有有的优良基因遗传给下一代个体，并生成包含更复杂基因结构的新个体。的优良基因遗传给下一代个体，并生成包含更复杂基因结构的新个体。交叉操作一般分为以下几个步骤：交叉操作一般分为以下几个步骤：1）从配对池中随机取出要交配的一对个体；）从配对池中随机取出要交配的一对个体；2）根根据据位位串串长长度度L，对对要要交交叉叉的的一一对对个个体体，随随机机选选取取1,L-1中中一一个个或多个整数或多个整数k作为交叉位置；作为交叉位置；3）根根据据交交叉叉概概率率实实施施交交叉叉操操作作，配配对对个个体体在在交交叉叉位位置置处处，相相互互交交换换各各自的部分内容，从而形成新的一对个体。自的部分内容，从而形成新的一对个体。第22页，共70页，编辑于2022年，星期三4.1.6遗传算子遗传算子二、交叉二、交叉（CrossoverCrossover）算子算子1、一点交叉、一点交叉（one-pointcrossover）位串位串A：1101|1010位串位串B：1011|0101位串位串A：1101|0101位串位串B：1011|1010第23页，共70页，编辑于2022年，星期三4.1.6遗传算子遗传算子二、交叉二、交叉（CrossoverCrossover）算子算子1、两点交叉、两点交叉（twotwo-pointcrossover）位串位串A：11|011|010位串位串B：10|110|101位串位串A：11|110|010位串位串B：10|011|101第24页，共70页，编辑于2022年，星期三4.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|10第25页，共70页，编辑于2022年，星期三4.1.6遗传算子遗传算子二、交叉二、交叉（CrossoverCrossover）算子算子1、一致交叉、一致交叉一致交叉即染色体位串上的每一位按相同概率进行随机均匀交叉。一致交叉即染色体位串上的每一位按相同概率进行随机均匀交叉。一致交叉算子生成的新个体位：一致交叉算子生成的新个体位：操作描述如下：操作描述如下：，x是取值为是取值为0，1上符合均匀分布的随机变量。上符合均匀分布的随机变量。第26页，共70页，编辑于2022年，星期三4.1.6遗传算子遗传算子三、变异三、变异（MutationMutation）算子算子变变异异操操作作模模拟拟自自然然界界生生物物体体进进化化中中染染色色体体上上某某位位基基因因发发生生的的突突变变现现象象，从从而而改改变变染染色体的结构和物理性状。色体的结构和物理性状。在在标标准准遗遗传传算算法法中中，变变异异算算子子通通过过按按变变异异概概率率pm随随机机反反转转某某位位等等位位基基因的二进制字符值来实现。因的二进制字符值来实现。对于给定的染色体位串对于给定的染色体位串，具体如下：，具体如下：生成新的个体生成新的个体 。其其中中，xi是是对对应应于于每每一一个个基基因因位位产产生生的的均均匀匀随随机变量，机变量，。第27页，共70页，编辑于2022年，星期三4.1.6遗传算子遗传算子四、逆转（四、逆转（InversionOperator）算子）算子逆逆转转操操作作首首先先在在个个体体位位串串上上随随机机地地选选择择两两个个点点，位位串串染染色色体体被被这这两两个个点点分分成成三三段段，将中间段的左右顺序倒转过来与另两段相连，形成新的个体位串。将中间段的左右顺序倒转过来与另两段相连，形成新的个体位串。例如：长度为例如：长度为10的二进制位串，其中下划线标示的等位基因为重要基因：的二进制位串，其中下划线标示的等位基因为重要基因：1011101101（是倒位位置）是倒位位置）经倒位后变为经倒位后变为1011011101。新的位串中重要基因更为靠近，被单点交叉算子分离的可能性大大降低了。新的位串中重要基因更为靠近，被单点交叉算子分离的可能性大大降低了。第28页，共70页，编辑于2022年，星期三4.1.6遗传算子遗传算子四、换位（四、换位（SwapOperator）算子）算子换位操作首先在个体位串上随机地选择两个基因，将这两个基因的位置换位操作首先在个体位串上随机地选择两个基因，将这两个基因的位置互换，形成新的个体位串。互换，形成新的个体位串。例如：长度为例如：长度为10的二进制位串，其中下划线标示的为随机选中的基因：的二进制位串，其中下划线标示的为随机选中的基因：1011101101经换位后变为经换位后变为1111101100第29页，共70页，编辑于2022年，星期三4.1.7迭代终止条件迭代终止条件一般采用设定最大代数的方法一般采用设定最大代数的方法。其其次次，可可以以根根据据群群体体的的收收敛敛程程度度来来判判断断，通通过过计计算算种种群群中中的的基基因多样性测度，即所有基因位的相似性程度来进行控制因多样性测度，即所有基因位的相似性程度来进行控制。第三，根据算法的离线性能和在线性能的变化进行判定第三，根据算法的离线性能和在线性能的变化进行判定。最最后后，在在采采用用精精英英保保留留选选择择策策略略的的情情况况下下，按按每每代代最最佳佳个个体体的的适应值的变化情况确定适应值的变化情况确定。第30页，共70页，编辑于2022年，星期三4.1.8控制参数控制参数1 1）位位串串长长度度L L：位位串串长长度度L L的的选选择择取取决决于于特特定定问问题题解解的的精精度度。要要求求的的精精度度越越高高，位位串串越越长长，但但需需要要更更多多的的计计算算时时间间。为为提提高高运运算算效效率率，变变长长度度位位串串或或者者在在当当前前所所达达到到的的较较小小可可行行域域内重新编码，是一种可行的方法，并显示了良好性能。内重新编码，是一种可行的方法，并显示了良好性能。2 2）群群体体规规模模n n：大大群群体体含含有有较较多多模模式式，为为遗遗传传算算法法提提供供了了足足够够的的模模式式采采样样容容量量，可可以以改改进进GAGA搜搜索索的的质质量量，防防止止成成熟熟前前收收敛敛。但但大大群群体体增增加加了了个个体体适适应应性性评评价价的的计计算算量量，从从而而使使收收敛敛速速度度降降低低。一般情况下建议一般情况下建议n n2020200200。第31页，共70页，编辑于2022年，星期三4.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。第32页，共70页，编辑于2022年，星期三4.1.8控制参数控制参数从从理理论论上上来来讲讲，不不存存在在一一组组适适用用于于所所有有问问题题的的最最佳佳参参数数值值，随着问题特征的变化，有效参数的差异往往非常显著。随着问题特征的变化，有效参数的差异往往非常显著。第33页，共70页，编辑于2022年，星期三4.1.9GA的性能评估的性能评估关关于于搜搜索索类类算算法法的的性性能能评评估估，一一般般可可以以归归纳纳为为算算法法的的求求解解效效率率和和求解质量求解质量两个方面。两个方面。算法的求解效率算法的求解效率是比较获得同样的可行解所需要的计算时间。是比较获得同样的可行解所需要的计算时间。算算法法的的求求解解质质量量是是在在规规定定的的时时间间（或或者者时时间间相相关关指指标标）内内所所获获得的可行解的优劣。得的可行解的优劣。第34页，共70页，编辑于2022年，星期三4.1.9GA的性能评估的性能评估1 1适应值函数计算次数适应值函数计算次数该该指指标标是是指指发发现现同同样样适适应应性性的的个个体体，或或者者找找到到同同样样质质量量的的可可行行解解，所所需需要要的的关关于于个个体体评评价价的的适适应应值值函函数数的的计计算算次次数数（function function evaluationsevaluations）。显然，该值越小说明相应）。显然，该值越小说明相应GAGA的搜索效率越高。的搜索效率越高。该该指指标标不不仅仅可可以以用用于于不不同同参参数数设设置置GAGA的的性性能能比比较较，也也可可以以用用于于GAGA与其他搜索算法的比较。与其他搜索算法的比较。第35页，共70页，编辑于2022年，星期三4.1.9GA的性能评估的性能评估2 2在线和离线性能函数在线和离线性能函数 1 1）在在线线性性能能函函数数（on-line on-line performanceperformance）：设设GAGA的的遗遗传传策策略略为为s s（包包括括LL，n n，PcPc，PmPm，算算子子形形式式等等），该该策策略略的的在在线线性能：性能：即即在在线线性性能能反反映映了了群群体体平平均均适适应应值值经经平平滑滑处处理理后后的的变变化化情情况况，描描述述了群体的整体性状和进化能力。了群体的整体性状和进化能力。第36页，共70页，编辑于2022年，星期三4.1.9GA的性能评估的性能评估2 2在线和离线性能函数在线和离线性能函数 2 2）离离线线性性能能函函数数（offlineperformance）：对对于于GA遗遗传传策策略略s，其离线性能，其离线性能其其中中，f(a*，t)maxf(al,t)，f(a2,t)，f(an,t)，即即当当前前群群体体中中最最佳佳个个体体的的适适应应值值。该该指指标标反反映映了了群群体体中中最最佳佳个个体体适适应应值值经经平平滑滑处处理理后后的的变变化化情情况况，描描述述了了个个体体的的进进化化能能力力和和GA的的搜索能力。搜索能力。第37页，共70页，编辑于2022年，星期三4.1.9GA的性能评估的性能评估3 3最优解搜索性能最优解搜索性能 GA用用于于函函数数优优化化的的目目的的就就是是发发现现问问题题的的全全局局最最优优解解，所所以以通通常常采采用用当当前前群群体体发发现现的的最最佳佳可可行行解解的的改改善善情情况况作作为为度度量量GA搜搜索索能能力的基本指标。力的基本指标。第38页，共70页，编辑于2022年，星期三4.2遗传算法的模式理论遗传算法的模式理论4.21模式与模式空间模式与模式空间位串上的某些等位基因的联结与适应值函数之间存在着某种联系，这种位串上的某些等位基因的联结与适应值函数之间存在着某种联系，这种联系提供了寻优过程的指导信息，引导着群体在位串空间中的移动方向。联系提供了寻优过程的指导信息，引导着群体在位串空间中的移动方向。采用字符集采用字符集K=0，1对问题参数进行二进制编码，位串空间表示为对问题参数进行二进制编码，位串空间表示为SL1,0L，该空间的大小为，该空间的大小为|SL|2L。扩展字符集。扩展字符集K0,1,*，其中，其中*是通配符或无关符是通配符或无关符（wildcards，or“dontcares”），即可和），即可和0或或1匹配。扩展位串空间表示为匹配。扩展位串空间表示为SeL1,0,*L，该空间的大小为，该空间的大小为|SeL|3L，则称，则称SeL为为SL的模式空间。显然，的模式空间。显然，包含包含2L个位串的位串空间，对应于个位串的位串空间，对应于3L个模式位串的模式空间。个模式位串的模式空间。第39页，共70页，编辑于2022年，星期三4.2遗传算法的模式理论遗传算法的模式理论4.21模式与模式空间模式与模式空间定义：定义：扩展位串空间扩展位串空间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*第40页，共70页，编辑于2022年，星期三4.2遗传算法的模式理论遗传算法的模式理论4.21模式与模式空间模式与模式空间模模式式是是由由SL中中具具有有共共同同特特征征的的位位串串所所组组成成的的集集合合（对对应应于于位位串串空空间间的的子子空空间间），它它描描述述了了该该集集合合中中位位串串上上共共同同的的基基因因特特征征。集合的大小集合的大小N由模式中由模式中*的个数的个数k决定，决定，N=2k。例例如如：模模式式00*表表示示位位串串长长度度为为4，两两个个高高位位基基因因为为00的的位位串集合，即串集合，即0000，0001，0010，0011如果包含这一模式的所有位串都具有较好的适应度，则如果包含这一模式的所有位串都具有较好的适应度，则该模式可能是一个重要的模式。该模式可能是一个重要的模式。第41页，共70页，编辑于2022年，星期三GoldbergGoldberg将将 模模 式式 称称 为为“超超 平平 面面”（hyper hyper planeplane），指指出出了了模模式式在在编编码码空空间间上上的的几几何何意意义义，模模式式包包含含的的位位串串是是编编码码空空间间相相应应超超平平面面上上的点。的点。第42页，共70页，编辑于2022年，星期三模式模式H1=1*表示函数解空间的右半区域表示函数解空间的右半区域模式模式H2=0*表示函数解空间的左半区域表示函数解空间的左半区域Y=X2第43页，共70页，编辑于2022年，星期三模式模式H3=*1表示函数解空间的阴影区域（奇数位串）表示函数解空间的阴影区域（奇数位串）模式模式H4=*0表示函数解空间的空白区域（偶数位串）表示函数解空间的空白区域（偶数位串）第44页，共70页，编辑于2022年，星期三模式模式H5=*1*表示函数解空间的阴影区域表示函数解空间的阴影区域模式模式H6=*0*表示函数解空间的空白区域表示函数解空间的空白区域第45页，共70页，编辑于2022年，星期三模式模式H7=10*的表示域，代表了的表示域，代表了1/4的解空间的解空间第46页，共70页，编辑于2022年，星期三模式模式H8=*1*1的表示域，代表了的表示域，代表了1/4的解空间的解空间第47页，共70页，编辑于2022年，星期三第48页，共70页，编辑于2022年，星期三4.2遗传算法的模式理论遗传算法的模式理论4.21模式与模式空间模式与模式空间模模式式的的阶阶（schemaorder）是是指指模模式式中中所所含含有有0、1确确定定基基因因位位的个数，记作的个数，记作O(H)。模模式式的的定定义义距距（defininglength）是是指指模模式式中中从从左左到到右右第第一一个个非非*位和最后一位非位和最后一位非*位之间的距离，记作位之间的距离，记作模模式式的的维维数数（schemadimension）是是指指模模式式中中所所包包含含的的位位串串的的个个数，也称为模式的容量，记作数，也称为模式的容量，记作D(H)，D(H)=2L-O(H)。第49页，共70页，编辑于2022年，星期三4.2遗传算法的模式理论遗传算法的模式理论4.21模式与模式空间模式与模式空间令令m=m(H，t)为为模模式式H在在第第t代代群群体体中中所所含含位位串串数数量量，模模式式在在t代代群群体体中中包包含含的的个个体体位位串串为为a1,a2,am，称称为为模模式式H在在群群体体中中的的生生存存数数量量（survivals）或或者者采采样样样样本本（samples），），(j=1，2，m)，则则模模式式H在在第第t代代群群体中的适应值估计为体中的适应值估计为即即模模式式的的适适应应值值估估计计（简简称称模模式式的的适适应应值值）是是群群体体中中其其所所包包含含的的全部个体的适应值的平均值。全部个体的适应值的平均值。第50页，共70页，编辑于2022年，星期三4.2遗传算法的模式理论遗传算法的模式理论4.21模式与模式空间模式与模式空间从从编编码码空空间间来来看看，m（H，t）是是当当前前群群体体中中包包含含属属于于模模式式H的的个个体体数数量量，反反映映了了所所对对应应的的模模式式空空间间的的分分布布情情况况，该该数数量量越越大大说说明明群群体体搜搜索索越越集集中中于于模模式式H代表的子空间。代表的子空间。从从模模式式空空间间来来看看，m（H，t）是是模模式式H在在当当前前群群体体中中的的个个体体采采样样数数量量，反反映映了了所所对对应应的的编编码码空空间间的的分分布布情情况况。该该数数量量越越大大说说明明群群体体中中的的个个体体越越趋趋向相似和一致，在编码空间的搜索范围越小。向相似和一致，在编码空间的搜索范围越小。一一个个模模式式H由由位位串串长长度度L、阶阶O(H)、定定义义距距、容容量量D(H)和和适适应应值值f(H，t)等等五五个个指指标标来来描描述述。模模式式的的引引入入为为在在一一个个有有限限字字符符集集上上定定义义的的有有限限长长度度的的位位串之间的相似性度量和理论分析提供了有力的工具。串之间的相似性度量和理论分析提供了有力的工具。第51页，共70页，编辑于2022年，星期三4.2遗传算法的模式理论遗传算法的模式理论4.22模式定理和积木块假设模式定理和积木块假设在在选选择择算算子子作作用用下下，对对于于平平均均适适应应度度高高于于群群体体平平均均适适应应度度的的模模式式，其其样样本本数数将将呈呈指指数数级级增增长长：而而对对于于平平均均适适应应度度低低于于群群体体平平均均适适应应度的模式，其样本数将呈指数级减少。度的模式，其样本数将呈指数级减少。在在选选择择和和交交叉叉算算子子作作用用下下，模模式式定定义义距距越越小小，则则群群体体中中该该模模式式个个体体数数量量越越容容易易呈呈指指数数级级增增长长；模模式式定定义义距距越越大大，则则群群体体中中该该模模式式个个体数量越不容易呈指数级增长。体数量越不容易呈指数级增长。在变异算子作用下在变异算子作用下，阶数越小模式，阶数越小模式H越易于生存；阶数越大，模式越易于生存；阶数越大，模式H越易于被破坏。越易于被破坏。第52页，共70页，编辑于2022年，星期三4.2遗传算法的模式理论遗传算法的模式理论4.22模式定理和积木块假设模式定理和积木块假设模模式式定定理理：在在遗遗传传算算子子选选择择、交交叉叉、变变异异的的作作用用下下，那那些些低低阶阶、定定义义距距短短的的、超超过过群群体体平平均均适适应应度度值值的的模模式式的的生生存存数数量量，将将随随着迭代次数的增加以指数规律增长。着迭代次数的增加以指数规律增长。模模式式定定理理的的意意义义：统统计计决决策策中中的的双双臂臂赌赌机机问问题题表表明明：按按指指数数规规律律提提高高将将硬硬币币投投往往平平均均支支付付高高的的赌赌机机的的概概率率，可可以以获获得得最最大大的的累累积积支支付付。应应用用到到优优化化问问题题则则是是：要要获获得得最最优优的的可可行行解解，则则必必须须保保证证较较优优解解的的样样本本数数呈呈指指数数级级增增长长。而而模模式式定定理理保保证证了了较较优优的的模模式式（遗遗传传算算法法的的较较优优解解）的样本数呈指数级增长，从而给出了遗传算法的理论基础。的样本数呈指数级增长，从而给出了遗传算法的理论基础。第53页，共70页，编辑于2022年，星期三4.2遗传算法的模式理论遗传算法的模式理论4.22模式定理和积木块假设模式定理和积木块假设定义定义：具有低阶、短定义距以及高适应度的模式称作积木块。具有低阶、短定义距以及高适应度的模式称作积木块。积积木木块块假假设设（building building block block hypothesishypothesis）：低低阶阶、短短距距高高平平均均适适应应度度的的模模式式（积积木木块块）在在遗遗传传算算子子作作用用下下，相相互互结结合合，能能生生成成高高阶阶、长距、高平均适应度的模式，并可最终生成全局最优解。长距、高平均适应度的模式，并可最终生成全局最优解。第54页，共70页，编辑于2022年，星期三4.2遗传算法的模式理论遗传算法的模式理论4.22模式定理和积木块假设模式定理和积木块假设模模式式定定理理和和积积木木块块假假设设比比较较准准确确地地模模拟拟了了自自然然界界的的物物种种竞竞争争和和遗遗传传法法则则，其其中中模模式式定定理理描描述述了了GAGA群群体体中中模模式式之之间间的的竞竞争争关关系系，积积木木块块假假设设说说明明了了有有效效基基因因之之间间的的继继承承与与重重组组。因因此此，模模式式定定理理和和积积木木块块假假设设构构成成了了关关于于GAGA进进化化过过程程能能够够发发现现最最优优解解的的一一个个解解释释，被被认认为为是是解解释释遗遗传传算算法法寻寻优优原原理理的的较较系系统统的的理理论论，统统称称为为模模式式理理论论（schema schema theorytheory）。它它们们也也是是GAGA进进化化动动力力学学的的基基本本理理论论，尽尽管管还还存存在在着着不不完完善善之之处处，但但是它为深入研究遗传算法的运行机理奠定了基础。是它为深入研究遗传算法的运行机理奠定了基础。第55页，共70页，编辑于2022年，星期三4.2遗传算法的模式理论遗传算法的模式理论4.22模式定理和积木块假设模式定理和积木块假设模模式式定定理理在在一一定定程程度度上上证证明明了了标标准准遗遗传传算算法法的的有有效效性性，但但它它仍仍有有以下的缺点：以下的缺点：（1 1）模模式式定定理理只只对对二二进进制制编编码码适适用用，对对其其他他编编码码方方案案尚尚没没有有相相应应的的结结论成立。论成