遗传算法的基本原理111.doc

第二章 遗传算法的基本原理2.1 遗传算法的基本描述2.1.1 全局优化问题全局优化问题的定义：给定非空集合S作为搜索空间，f：SR为目标函数，全局优化问题作为任务给出，即在搜索空间中找到至少一个使目标函数最大化的点。全局最大值（点）的定义：函数值称为一个全局最大值，当且仅当成立时，被称为一个全局最大值点（全局最大解）。局部极大值与局部极大值点（解）的定义：假设在S上给定了某个距离度量，如果对，使得对，则称x为一个局部极大值点，f(x)为一个局部极大值。当目标函数有多个局部极大点时，被称为多峰或多模态函数（multi-modality function）。主要考虑两类搜索空间：伪布尔优化问题：当S为离散空间BL=0,1L,即所有长度为L且取值为0或1的二进制位串的集合时，相应的优化问题在进化计算领域称为伪布尔优化问题。连续参数优化问题：当取S伪n维实数空间Rn中的有界集合，其中，i = 1, 2, , n时，相应的具有连续变量的优化问题称为连续参数优化问题。对S为BL=0,1L，常采用的度量时海明距离，当时，常采用的度量就是欧氏距离。2.1.2 遗传算法的基本流程遗传算法的基本步骤如下：1） 选择编码策略，把参数集合X和域转换为位串结构空间S；2） 定义适应度函数f(X)；3） 确定遗传策略，包括群体规模，选择、交叉、变异算子及其概率。4） 生成初始种群P；5） 计算群体中各个体的适应度值；6） 按照遗传策略，将遗传算子作用于种群，产生下一代种群；7） 迭代终止判定。遗传算法涉及六大要素：参数编码，初始群体的设定，适应度函数的设计，遗传操作的设计，控制参数的设定，迭代终止条件。2.1.3 遗传编码由于GA计算过程的鲁棒性，它对编码的要求并不苛刻。原则上任何形式的编码都可以，只要存在合适的对其进行操作的遗传算子，使得它满足模式定理和积木块假设。由于编码形式决定了交叉算子的操作方式，编码问题往往称作编码-交叉问题。对于给定的优化问题，由GA个体的表现型集合做组成的空间称为问题（参数）空间，由GA基因型个体所组成的空间称为GA编码空间。遗传算子在GA编码空间中对位串个体进行操作。定义：由问题空间向GA编码空间的映射称为编码，而有编码空间向问题空间的映射成为译码。问题编码一般应满足以下三个原则：1） 完备性（completeness）：问题空间中的所有点都能能成为GA编码空间中的点的表现型。即编码应能覆盖整个问题空间。2） 健全性（soundness）：GA编码空间中的染色体位串必须对应问题空间中的某一潜在解。即每个编码必须是有意义的。3） 非冗余性（non-redundancy）：染色体和潜在解必须一一对应。在某些情况下，为了提高GA的运行效率，允许生成包含致死基因的编码位串，它们对应于优化问题的非可行解。虽然会导致冗余或无效的搜索，但可能有助于生成全局最优解所对应的个体，所需的总计算量可能反而减少。根据模式定理，De Jong进一步提出了较为客观明确的编码评估准则，称之为编码原理。具体可以概括为两条规则：1） 有意义积木块编码规则：编码应易于生成与所求问题相关的短距和低阶的积木块。2） 最小字符集编码规则：编码应采用最小字符集，以使问题得到自然、简单的表示和描述。1二进制编码1）连续实函数的二进制编码设一维连续实函数采用长度维L的二进制字符串进行定长编码，建立位串空间：，k=1,2,K; l=1,2,L; K=2L其中，个体的向量表示为，其字符串形式为，sk称为个体ak对应的位串。表示精度为。将个体又位串空间转换到问题空间的译码函数的公式定义为：对于n维连续函数，各维变量的二进制编码位串的长度为li,那么x的编码从左到右依次构成总长度为的二进制编码位串。相应的GA编码空间为：，K=2L该空间上的个体位串结构为对于给定的二进制编码位串sk,位段译码函数的形式为， i = 1,2,n采用二进制编码的GA进行数值优化时，可以通过改变编码长度，协调搜索精度和搜索效率之间的关系。2） 组合问题的二进制编码在很多组合优化问题中，目标函数和约束函数均为离散函数，采用二进制编码往往具有直接的语义，可以将问题空间的特征与位串的基因相对应。2其他编码1) 大字符集编码2) 序列编码3) 实数编码4) 树编码5) 自适应编码6) 乱序编码7) 二倍体和显性规律Lawrence Davis等学者主张：采用的编码对问题来讲应该时最自然的，并可以据此设计能够处理该编码的遗传算子。2.1.4 群体设定遗传算法的两个主要特点之一就是基于群体搜索的策略，群体的设定，尤其是群体规模的设定，对遗传算法性能有着重要的影响。这中间包括两个问题：1）初始群体如何设定；2）进化过程中各代的规模如何维持？1 初始群体的设定遗传算法中初始群体中的个体是按一定的分布随机产生的，一般来讲，初始群体的设定可以采用如下的策略：1） 根据问题固有知识，设法把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定初始群体。2） 先随机生成一定数目的个体，然后从中挑出最好的个体加入到初始群体中。这一过程不断重复，直到初始群体中个体数达到了预定的规模。2 群体规模的设定根据模式定理，若群体规模为M，则遗传操作可从这M个个体中生成和检测O(M3)个模式，并在此基础上不断形成和优化积木块，直到找到最优解。显然M越大，遗传操作处理的模式就越多，生成有意义的积木块并逐渐进化为最优解的机会就越高。换句话说，群体规模越大，群体中个体的多样性越高，算法陷入局部最优解的危险就越小。另外，群体规模太小，会使遗传算法的搜索空间分布范围有限，因而搜索有可能停止在未成熟阶段，引起未成熟收敛（premature convergence）现象。但是，从计算效率来看，群体规模越大，其适应度评价次数越多，计算量也就越大，从而影响算法的效率。研究表明，在二进制编码的前提下，为了满足隐并行性，群体个体数只要设定为2L/2即可，L为个体串长度。这个数比较大，实际应用中群体规模一般取几十几百。2.1.4 适应度函数（评价函数）遗传算法在进化搜索中基本不用外部信息，仅用目标函数即适应度函数为依据。遗传算法的目标函数不受连续可微的约束且定义域可以为任意集合。对适应度函数的唯一要求是，针对输入可计算出能加以比较的非负结果（比例选择算子需要）。需要强调的是，适应度函数值是选择操作的依据，适应度函数设计直接影响到遗传算法的性能。1 目标函数映射成适应度函数对于给定的优化问题，目标函数有正有负，甚至可能是复数值，所以有必要通过建立适应度函数与目标函数的映射关系，保证映射后的适应度值是非负的，而且目标函数的优化方向应对应于适应度值增大的方向。1） 对最小化问题，建立如下适应函数和目标函数的映射关系：其中，cmax可以是一个输入值或是理论上的最大值，或者是当前所有大或最近K代中g(x)的最大值，此时cmax随着代数会有变化。2） 对于最大化问题，一般采用以下映射：其中，cmin可以是一个输入值，或者是当前所有代或最近K代中g(x)的最小值2 适应度函数定标在遗传进化的初期，通常会出现一些超常个体，若按比例选择策略，这些异常个体有可能在群体中占据很大的比例，导致未成熟收敛。显然，这些异常个体因竞争力太突出，会控制选择过程，从而影响算法的全局优化性能。另以方面，在遗传进化过程中，虽然群体中个体多样性尚存在，但往往会出现群体的平均适应度已接近最佳个体适应度，这时，个体间的竞争力相似，最佳个体和其它个体在选择过程中有几乎相等的选择机会，从而使有目标的优化过程趋于无目标大的随机搜索过程。对未成熟收敛现象，应设法降低某些异常个体的竞争力，这可以通过缩小相应的适应度值来实现。对于随机漫游现象，应设法提高个体间的竞争力差距，这可以通过放大相应的适应度值来实现。这种适应度的缩放调整称为适应度定标。1） 线性定标（linear scaling）f = af + b2） 截断（sigma truncation）3） 乘幂标f = fK4） 指数定标f = exp(-bf)2.1.5 遗传算子遗传操作是模拟生物基因遗传的操作。包括三个基本遗传算子（genetic operator）：选择，交叉和变异。这三个遗传算子具有一些特点：（1） 这三个算子的操作都是在随机扰动情况下进行的。换句话说，遗传操作是随机化操作，因此，群体中个体向最优解迁移的规则是随机的。需要强调的是，这种随机化操作和传统的随机搜索方法是有区别的。遗传操作进行的是高效有向的搜索，而不是如一般随机搜索方法所进行的无向搜索。（2） 遗传操作的效果和所取的操作概率、编码方法、群体大小，以及适应度函数的设定密切相关。（3） 三个基本算子的操作方法和操作策略随具体求解问题的不同而异。或者说，是和个体的编码方式直接相关。1、 选择（selection）算子从群体中选择优胜个体，淘汰劣质个体的操作叫选择。选择算子有时又称为再生算子（reproduction operator）。选择即从当前群体中选择适应度值高的个体以生成配对池（mating pool）的过程。为了防止由于选择误差，或者交叉和变异的破坏作用而导致当前群体的最佳个体在下一代的丢失，De Jong提出了精英选择（elitist selection）策略和代沟的概念。Holland等提出了稳态选择（steady-state selection）策略。下面一些概念可以用来比较不同的选择算法：(1)选择压力(selection pressure)：最佳个体选中的概率与平均选中概率的比值。(2)偏差(bias) 个体正规化适应度与其期望再生概率的绝对差值。(3)个体扩展(spread) 单个个体子代个数的范围。(4)多样化损失(loss of diversity) 在选择阶段末选中个体数目占种群的比例。(5)选择强度(selection intensity) 将正规高斯分布应用于选择方法，期望平均适应度。(6)选择方差(selection variance) 将正规高斯分布应用于选择方法，期望种群适应度的方差。1） 适应度比例选择是最基本的选择方法，其中每个个体被选择的期望数量与其适应度值和群体平均适应度值的比例有关，通常采用轮盘赌（roulette wheel）方式实现。这种方式首先计算每个个体的适应度值，然后计算出此适应度值在群体适应度值总和中所占的比例，表示该个体在选择过程中被选中的概率。选择过程体现了生物进化过程中“适者生存，优胜劣汰”的思想。对于给定的规模为n的群体，个体的适应度值为，其选择概率为：经过选择操作生成用于繁殖的配对池，其中父代种群中个体生存的期望数目为：当群体中个体适应度值的差异非常大时，最佳个体与最差个体被选择的概率之比（选择压力）业将按指数增长。最佳个体在下一代的生存机会将显著增加，而最差个体的生存机会将被剥夺。当前群体中的最佳个体将快速充满整个群体，导致群体的多样性迅速降低，GA也就过早地丧失了进化能力。这是适应度比例选择容易出现地问题。2） Boltzmann选择在群体进化过程中，不同阶段需要不同地选择压力。早期阶段选择压力较小，我们希望较差地个体也又一定地生存机会，使得群体保持较高地多样性；后期阶段，选择压力较大，我们希望GA缩小搜索邻域，加快当前最优解的改善速度。为了动态调整群体进化过程中的选择压力，Goldberg设计了Boltzmann选择方法。个体选择概率为：其中，T0是退火温度。T随着迭代地进行逐渐缩小，选择压力将随之升高。T是控制群体进化过程中选择压力的关键，一般T的选择需要考虑预计最大进化代数。3） 排序选择排序选择方法是将群体中个体按其适应度值由大到小的顺序排成一个序列，然后将事先设计好的序列概率分配给每个个体。显然，排序选择域个体的适应度值的绝对值之间无直接关系，仅仅与个体之间适应度值的相对大小有关。排序选择不利用个体适应度值绝对值的信息，可以避免群体进化过程中的适应度标度变换。由于排序选择概率比较容易控制，所以在实际计算过程中经常采用，特别是适用于动态调整选择概率，根据进化效果适时改变群体的选择压力。最常用的排序选择方法是采用线性函数将队列序号映射为期望的选择概率，即线性排序选择（linear ranking selection）。对于给定的规模为n的群体，并且满足个体适应度值降序排列。假设当前群体最佳个体a1在选择操作后的期望数量为，即；最差个体an在选择操作后的期望数量为。其它个体的期望数量按等差序列计算，则，故现在排序选择概率为由可以导出。要求，故。当时，即最差个体在下一代生存的期望数量为0，群体选择压力最大；当时，选择方式为按均匀分布的随机选择，群体选择压力最小。4） 联赛选择（tournament selection）联赛选择的基本思想是从当前群体中随机选择一定数量的个体（放回或者不放回），将其中适应值最大的个体放入配对池中。反复执行这一过程，直到配对池中的个体数量达到设定的值。联赛规模用q表示，也称q-联赛选择。联赛选择与个体的适应度值由间接关系，注重适应度值大小的比较。根据大量实验总结，联赛规模一般取q=2。联赛选择的选择概率也是比较容易控制的，实际计算中也经常采用，适用于在GA迭代过程中动态调整选择概率，将进化效果与群体选择压力联系起来。研究证明，当群体规模比较大时，联赛选择与排序选择的个体选择概率基本相同。5） 精英选择从GA的整个选择策略来讲，精英选择时群体收敛导优化问题全局最优解的一种基本保障。如果下一代群体的最佳个体适应度值小于当前群体最佳个体的适应度值，则将当前群体最佳个体或者适应度值大于下一代最佳个体适应度值的多个个体直接复制到下一代，随机替代和替代最差的下一代群体中的相应数量的个体。6） 稳态选择De Jong将下一代群体中生成的与上一代不同的新个体所占的比例称为“代沟”（generation gap）。代沟越大，说明新个体的生成比例越高，群体正在搜索新的编码空间。稳态选择操作中，仅有少量个体按适应度值比例选择方法被选择，通过遗传操作生成新的个体。新个体放回到群体中时，随机替代等量的旧个体，或者替代等量的最差的旧个体。Holland将稳态选择方法应用于分类器规则学习中，最大程度继承已获得的规则，实现增量学习。2、 交叉（crossover）算子交叉操作时进化算法中遗传算法具有的原始性的独有特征。GA交叉算子时模仿自然界有性繁殖的基因重组过程，其作用在于将已有的优良基因遗传给下一代个体，并生成包含更复杂基因结构的新个体。交叉操作一般分为以下几个步骤：1） 从配对池中随机取出要交配的一对个体；2） 根据位串长度L，对要交叉的一对个体，随机选取1, L-1中一个或多个整数k作为交叉位置；3） 根据交叉概率实施交叉操作，配对个体在交叉位置处，相互交换各自的部分内容，从而形成新的一对个体。实现个体结构重组的交叉算子的设计一般与所求解的具体问题有关，任何交叉算子需满足交叉算子的评估准则，即交叉算子需保证前一代中优秀个体的性状能在下一代的新个体中尽可能得到遗传何继承。此外，交叉算子设计和编码设计需协调操作。1） 一点交叉（one-point crossover）一点交叉是由Holland提出的最基础的一种交叉方式。一点交叉操作的信息量比较小，交叉点位置的选择可能带来较大的偏差（position bias）。按照Holland的思想，一点交叉算子不利于长距模式的保留和重组，而且位串末尾的重要基因总是被交换（尾点效应，end-point effect）。故实际应用中采用较多的是两点交叉。位串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 02） 两点交叉（two-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 13） 多点交叉（multi-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 04） 一致交叉一致交叉即染色体位串上的每一位按相同概率进行随机均匀交叉。一致交叉算子生成的新个体位：，操作描述如下：； x是取值为0，1上符合均匀分布的随机变量。Spears和De Jong认为一致交叉算子优于多点交叉算子，并提出一种带偏置概率的一致交叉（），不存在多点交叉算子操作引起的位置偏差，任意基因位的重要基因在一致交叉作用下均可以重组，并遗传给下一代个体。3、 逆转算子在自然遗传学中有一种称作倒位的现象，在染色体中有两个倒位点，在这两点之间的基因位置倒换，使得那些在父代中离得很远得基因位在后代中紧靠在一起。在GA中相当于重新定义基因块，使染色体位串上得重要基因更加紧凑，更不易被交叉算子所分裂。仿照此现象，Holland提出了逆转算子。逆转操作首先在个体位串上随机地选择两个点，位串染色体被这两个点分成三段，将中间段的左右顺序倒转过来与另两段相连，形成新的个体位串。比如：长度为10的二进制位串，其中下划线标示的等位基因为重要基因：1011101101（是倒位位置）经倒位后变为1011011101。新的位串中重要基因更为靠近，被单点交叉算子分离的可能性大大降低了。逆转算子一般要求采用类似于乱序编码的带基因位标号的染色体结构。比如，长度为10的位串：位串： 1 0 1 1 1 0 1 1 0 1基因位编号：1 2 3 4 5 6 7 8 9 10按照上述方法实施逆转操作后，编号也随之翻转：位串： 1 0 1 1 0 1 1 1 0 1基因位编号：1 2 8 7 6 5 4 3 9 10这样倒位操作就不会影响个体位串的适应值计算。但是，逆转算子对交叉算子有一定影响。考虑下列A，B位串之间的单点交叉：位串A：1 0 1 1 1 0 1 1 0 1基因位编号：1 2 3 4 5 6 7 8 9 10位串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 10两个子代位串中第3、4和7、8位基因在A、B中重复或遗漏，导致子代个体中包含冗余或不完整的遗传信息。为解决此问题，一般遵循五种交换规则：1）严格同序交换，只允许同序位串才能交换。2）生存性交换，允许不同序位串进行交换，如果子代码串不包含完整的遗传信息，则不把它们放入新一代群体中。3）任选方案交换，随意选择两个位串，并将其中任何一个指定为主序位申，另一个位串则按主序位串的次序映射，然后再进行通常的交换，这样保证了交换结果的合法性。4）最佳方案交换，与任选方案交换基本相同，只是将两个位串中适应值高的位串作为主序位串。5）结构修复，对于两个子代位串中重复或短缺的基因，随机将重复的基因改变为缺省的基因，形成完整的位串结构。目前，这五种原则在基于二进制编码的参数优化问题的GA求解中还很少采用。对于某些问题要求采用具有显著物理含义的特殊编码方式，可以根据GA进化的困难程度适当应用。4、 变异（mutation）算子变异操作模拟自然界生物体进化中染色体上某位基因发生的突变现象，从而改变染色体的结构和物理性状。在遗传算法中，变异算子通过按变异概率pm随机反转某位等位基因的二进制字符值来实现。对于给定的染色体位串，具体如下： 生成新的个体。其中，xi是对应于每一个基因位产生的均匀随机变量，。变异操作作用于个体位串的等位基因上，由于变异概率比较小，在实施过程中一些个体可能根本不发生一次变异，造成大量计算资源的浪费。因此，在GA具体应用中，我们可以采用一种变通措施，首先进行个体层次的变异发生的概率判断，然后再实施基因层次上的变异操作。一般包括两个基本步骤：1）计算个体发生变异的概率以原始的变异概率pm为基础，可以计算出群体中个体发生变异的概率：给定均匀随机变量，若，则对该个体进行变异，否则表示不发生变异。2）计算发生变异的个体上基因变异的概率由于变异操作方式发生了改变，被选择变异的个体上基因的变异概率也需要相应修改，以保证整个群体上基因发生变异的期望次数相等。传统变异方式下整个群体基因变异的期望次数为。设新的基因变异概率为，新的变异方式下整个群体基因变异的期望次数为：。要求两者相等，即可以导出：。，位串越短，越比大。当位串长度趋于无穷大时，两者相等，即。传统变异方式下的计算量为nL，新的变异方式下的计算量npm(aj)L，计算量差异为nL(1pm(aj)，显然新的变异方式比传统方式计算量降低了，且随着位串长度的增大而下降。但是，这种新变异方式也在一定程度上偏离了原来的变异基因位在全部群体个体基因位中的均匀分布的情况，当群体比较小时，可能会带来一定的变异误差。从第t代群体中由选择、交叉所生成的交配池中，依次选择个体进行随机变异操作的一般形式表示为P(t)m(P(t)，pm)变异操作按一定的概率pm对位串上的某些基因位的值进行变异，即1变为0，或0变成1。为了保证个体变异后不会与其父体产生太大的差异，变异概率一般取值较小，以保证种群发展的稳定性。当交叉操作产生的后代个体的适应值不再比它们的前辈更好，但又未达到全局最优解时，就会发生成熟前收敛或早熟收敛（Premature convergence）。这时引入变异算子往往能产生很好的效果。一方面，变异算子可以使群体进化过程中丢失的等位基因信息得以恢复，以保持群体中的个体差异性，防止发生成熟前收敛；另一方面，当种群规模较大时，在交叉操作基础上引人适度的变异，也能够提高遗传算法的局部搜索效率。在群体进化的整个过程中，交叉操作是主要的基因重组和群体更迭的手段，变异操作的作用是第二位的，变异算子仅仅充当背景性的角色（background role）。针对具体问题以及为了便于对进化过程实施控制，在标准变异算子的基础上，又引人了其他类型的变异算子，比如：特定有效位变异（高位、低位），变异概率自适应调整、面向领域知识的位变异等，使得遗传算法的应用范围和应用效果得到较好的改善。在很多组合优化问题中，往往存在着多个最优解或者最优解往往被环绕在大量的局部最优解之中，应用GA求解该类问题很容易形成模式欺骗问题，此时可以采用补算算子（Complementary operator）增加群体多样性或者克服模式欺骗性。基于1,0字符集表示的二进制染色体位串，补算算子具体操作形式如下：O(com, s): ai = 1 ai, i = 1,2, L对于位串上每一个基因位，若等位基因为0，则变为1，否则变为0，从而形成新得位串。例如：s = 10111011，补算运算结果：s = 01000100。2.1.6 循环终止条件关于GA迭代过程如何终止，一般采用设定最大代数的方法。该方法简单易行但不准确。其次，可以根据群体的收敛程度来判断，通过计算种群中的基因多样性测度，即所有基因位的相似性程度来进行控制。第三，根据算法的离线性能和在线性能的变化进行判定。最后，在采用精英保留选择策略的情况下，按每代最佳个体的适应值的变化情况确定。一般循环终止条件表示为T(P(t)true。2.1.7 标准GA的流程1） 设代数t = 02） 初始化种群3） 适应性评价4） while T(P(t)true doa) 选择b) 交叉c) 变异d) 新一代种群e) 适应性评价5） end do2.1.8 控制参数在遗传算法的运行过程中，存在着对其性能产生重大影响的一组参数。这组参数在初始阶段或群体进化过程中需要合理的选择和控制，以使 GA以最佳的搜索轨迹达到最优解。主要参数包括染色体位串长度L，群体规模n，交叉概率Pc以及变异概率Pm。许多学者进行了大量实验研究，给出了最优参数建议。1）位串长度L：位串长度L的选择取决于特定问题解的精度。要求的精度越高，位串越长，但需要更多的计算时间。为提高运算效率，变长度位串或者在当前所达到的较小可行域内重新编码，是一种可行的方法，并显示了良好性能。2）群体规模n：大群体含有较多模式，为遗传算法提供了足够的模式采样容量，可以改进GA搜索的质量，防止成熟前收敛。但大群体增加了个体适应性评价的计算量，从而使收敛速度降低。一般情况下专家建议n20200。3）交叉概率Pc：交叉概率控制着交叉算子的应用频率，在每一代新的群体中，需要对Pcn个个体的染色体结构进行交叉操作。交叉概率越高，群体中新结构的引人愈快，已获得的优良基因结构的丢失速度也相应升高。而交叉概率太低则可能导致搜索阻滞。一般取Pc = 0.601.00。4）变异概率Pm：变异操作是保持群体多样性的有效手段，交叉结束后，交配池中的全部个体位串上的每位等位基因按变异率Pm随机改变，因此每代中大约发生PmnL次变异。变异概率太小，可能使某些基因位过早丢失的信息无法恢复；而变异概率过高，则遗传搜索将变成随机搜索。一般取Pm = 0.0050.01。实际上，上述参数与问题的类型有着直接的关系。问题的目标函数越复杂，参数选择就越困难。从理论上来讲，不存在一组适用于所有问题的最佳参数值，随着问题特征的变化，有效参数的差异往往非常显著。如何设定遗传算法的控制参数以使遗传算法的性能得到改善，还需要结合实际问题深人研究，以及有赖于遗传算法理论研究的新进展。2.1.9 GA的性能评估GA的运行性能与很多因素有关。针对求解同一优化问题，不同参数设置的两个或者多个GA，或者GA与其他启发式搜索算法，如何进行性能比较呢？关于搜索类算法的性能评估，一般可以归纳为算法的求解效率和求解质量两个方面。算法的求解效率是比较获得同样的可行解所需要的计算时间。算法的求解质量是在规定的时间内（或者时间相关指标）所获得的可行解的优劣。这里主要介绍常用和通用的两个指标。1适应值函数计算次数该指标是指发现同样适应性的个体，或者找到同样质量的可行解，所需要的关于个体评价的适应值函数的计算次数（function evaluations）。显然，该值越小说明相应GA的搜索效率越高。同样，在预定的适应值函数计算次数的情况下，比较所发现的最佳个体或者找到的可行解的质量，也可以判断不同GA的搜索能力。该指标不仅可以用于不同参数设置GA的性能比较，也可以用于GA与其他搜索算法的比较。适应值函数的计算次数一般采用群体规模与进化代数的乘积，其中往往不考虑代沟大小的影响。2在线和离线性能函数De Jona在将 GA用于一组优化函数求解的比较分析时，提出了 GA的在线评价指标和离线评价指标两个函数。1） 线性能函数（on-line performance）：设GA的遗传策略为s（包括L，n，Pc，Pm，算子形式等），该策略的在线性能：即在线性能反映了群体平均适应值经平滑处理后的变化情况，描述了群体的整体性状和进化能力。2） 离线性能函数（offline performance）：对于GA遗传策略s，其离线性能其中，f(a*，t)maxf(al，t)，f(a2，t)，f(an，t)，即当前群体中最佳个体的适应值。该指标反映了群体中最佳个体适应值经平滑处理后的变化情况，描述了个体的进化能力和GA的搜索能力。关于上述适应值的平滑处理，也可以通过赋予进化过程中各代不同的权重，改变为适应值的加权平均计算，以消除初始群体带来的误差。3最优解搜索性能GA用于函数优化的目的就是发现问题的全局最优解，所以通常采用当前群体发现的最佳可行解的改善情况作为度量GA搜索能力的基本指标。对于GA遗传策略S，性能函数为：Pbest(s, t) = f(a*, t)其中，Pbest可以反映GA搜索到全局最优解的过程、速度、早熟等情况，也是适应性参数调整的基础。另外，结合具体的应用实例，还可以设计一系列具有不同物理含义的性能评价函数和指标。22 遗传算法的模式理论虽然GA计算过程和形式简单，但是其运行机理非常复杂。随着GA在复杂优化问题求解和实际工程设计中的应用，人们对GA的理论基础给予了越来越多的关注。主要问题包括：1）采用怎样的规律和模型来描述GA的宏观行为，GA进化过程中如何预测适应值的变化，以及特定GA形式下的群体结构的进化动力行为。2）如何评价GA性能的优劣，采用怎样的评价标准。3）GA适用于哪些问题的求解，即对于哪些问题求解GA性能表现优异，或者GA性能表现低劣。4）在什么条件下（问题性质、GA形式等），GA能够超越其他启发式搜索方法。关于以上问题的研究就形成了GA的基本理论。Holand在早期研究中提出了模式（scnema）概念以及模式定理（scnernatneorem），试图给予规范严格的理论分析。221 模式与模式空间遗传算法将实际问题表示成位串空间，以群体为基础，根据适者生存的原则，从中选择出高适应值的位串进行遗传操作，产生出下一代适应性好的位串集合，从而将整个群体不断转移到位串空间中适应值高的子集上，直到获得问题的最优解。在这一过程中，群体中是由哪些信息来指导和记忆寻优过程呢？Holland发现，位串上的某些等位基因的联结与适应值函数之间存在着某种联系，这种联系提供了寻优过程的指导信息，引导着群体在位串空间中的移动方向。遗传算法在工作过程中，建立并管理着问题参数空间、位串空间（或称为编码空间）、模式空间和适应值空间等四个空间及其之间的转换关系。采用字符集K=0，1对问题参数进行二进制编码，位串空间表示为SL1,0L，该空间的基数为|SL|2L。扩展字符集K0,1,*，其中*是通配符或无关符（wild cards，or“dont cares”），即可和0或 1匹配。扩展位串空间表示为SeL1,0,*L，该空间的基数为则称SeL为SL的模式空间。显然，包含2L个位串的位串空间，对应于3L个模式位串的模式空间。定义2.2.1 扩展位串空间SeL0,1,*L中的任何一个点，称为对应于位串空间 SL1,0L的一个模式（Schema）：其中a(al，a2，aL)，H(H1，H2，HL)，i = 1，2，L；，。模式是由SL中具有共同特征的位串所组成的集合，它描述了该集合中位串上共同的基因特征。Goldberg将模式称为“超平面”（hyper plane），指出了模式在编码空间上的几何意义，模式包含的位串是编码空间相应超平面上的点。例如：模式0 0 * *表示位串长度为4，两个高位基因为00的位串集合，即0000，0001，0010，00ll。定义2.3.2 模式的阶（schema order）是指模式中所含有0、1确定基因位的个数，记作O(H)。定义2.3.3 模式的定义距（defining length）是指模式中从左到右第一个非*位和最后一位非*位之间的距离，记作。定义2.3.4 模式的维数（schema dimension）是指模式中所包含的位串的个数，也称为模式的容量，记作D(H)，D(H) = 2L-O(H)。定义2.3.5 令m = m(H，t)为模式H在第t代群体中所含位串数量，模式在t代群体中包含的个体位串为a1, a2, ,am，称为模式H在群体中的生存数量（survivals）或者采样样本（samples），(j = 1，2，m)，则模式H在第 t代群体中的适应值估计为即模式的适应值估计（简称模式的适应值）是群体中其所包含的全部个体的适应值的平均值。从编码空间来看，m（H，t）是当前群体中包含于模式H的个体数量，反映了所对应的模式空间的分布情况，该数量越大说明群体搜索越集中于模式H代表的子空间。从模式空间来看，m（H，t）是模式H在当前群体中的个体采样数量，反映了所对应的编码空间的分布情况。该数量越大说明群体中的个体越趋向相似和一致，在编码空间的搜索范围越小。比如：模式H=*101*，O(H)=3，2，D(H)=224。可见，一个模式H由位串长度L、阶O(H)、定义距、容量D(H)和适应值f(H，t)等五个指标来描述。模式的引入为在一个有限字符集上定义的有限长度的位串之间的相似性度量和理论分析提供了有力的工具。222 模式定理和积木块假设在选择算子作用下，对于平均适应度高于群体平均适应度的模式，其样本数将呈指数级增长：而对于平均适应度低于群体平均适应度的模式，其样本数将呈指数级减少。在选择和交叉算子作用下，模式定义距越小，则群体中该模式个体数量越容易呈指数级增长；模式定义距越大，则群体中该模式个体数量越不容易呈指数级增长。在变异算子作用下，阶数越小模式H越易于生存；阶数越大，模式H越易于放破坏。定理2.3.1模式定理 在遗传算子选择、交叉、变异的作用下，那些低阶、定义距短的、超过群体平均适应度值的模式的生存数量，将随着迭代次数的增加以指数规律增长。理论基础：统计决策中的双臂赌机问题表明：按指数规律提高将硬币投往平均支付高的赌机的概率，可以获得最大的累积支付。应用到优化问题则是：要获得最优的可行解，则必须保证较优解的样本数呈指数级增长。而模式定理保证了较优的模式（遗传算法的较优解）的样本数呈指数级增长，从而给出了遗传算法的理论基础。由模式定理可知，具有低阶、短定义距以及平均适应度高于群体平均适应度的模式在子代中将以指数级增长。这类模式在遗传算法中非常重要，我们给它们一个特别的名字积木块（building block）。定义2.4 具有低阶、短定义距以及高适应度的模式称作积木块。正如搭积木一样，这些“好”的模式在遗传操作下相互拼搭、结合，产生适应度更高的串，从而找到更优的可行解，这正是积木块假设所揭示的内容。假设21积木块假设（building block hypothesis）低阶、短距、高平均适应度的模式（积木块）在遗传算于作用下，相互结合，能生成高阶、长距、高平均适应度的模式可最终生成全局最优解。上一节的模式定理保证了较优的模式（遗传算法的较优解）的样本数呈指数级增长，从而满足了寻找最优解的必要条件，即遗传算法存在着寻找到全局最优解的可能性。而本节的积木块假设则指出，遗传算法具备寻找到全局最优解的能力，即积木块在遗传算子作用下，能生成高阶、长距、高平均适应度的模式，最终生成全局最优解。然而，遗憾的是上述结论并没有得到证明，正因为如此才被称为假设，而非定理。目前已经有大量的实践证据支持这一假设，从20多年前Bagley和Rosenberg的两篇开创性的文章到最近大量的遗传算法应用实例都表明，积木块假设在许多领域都获得了成功，例如平滑多峰问题，带干扰多峰问题以及组合优化问题等等。尽管大量的证据并不等于理论证明，但至少可以肯定，对多数经常碰到的问题，遗传算法都是适用的。模式定理和建筑模块假设比较准确地模拟了自然界的物种竞争和遗传法则，其中模式定理描述了GA群体中模式之间的竞争关系，建筑模块假设说明了有效基因之间的继承与重组。因此，模式定理和建筑模块假设构成了关于GA进化过程能够发现最优解的一个充分条件，被认为是解释遗传算法寻优原理的较系统的理论，统称为模式理论（schernatheory）。它们也是 GA进化动力学的基本理论，尽管还存在着不完善之处，但是它为深入研究遗传算法的运行机理奠定了基础。虽然模式定理在一定意义上解决了基本遗传算法(SGA)的有效性，但它仍有以下的缺点：（1）模式定理只对二进制编码适用，对其他编码方案尚没有相应的结论成立。（2）模式定理只结出了在下世代包含模式H的个体数的下限。我们无法据此推断算法的收敛性。（3）模式定理没有解决算法设计中控制参数选取等问题。最近，Bethke的研究似乎为这个问题的解决带来了希望。Bethke采用 Walsh函数和一种巧妙的模式变换，提出了一种采用Walsh系数计算模式平均适应度的有效分析方法，这使得在一些特定的适应度函数和编码方式下，可以判定积木块通过相互组合是否会产生最优解或接近最优解。Holland把Bethke的方法推广到了当群体非均匀分布时的模式平均适应度分析上。可以用Walsh系数描述遗传算法操作：遗传算法渐近地估计Walsh系数，并且引导搜索朝着Walsh系数较大的分割中使Walsh函数取正值的模式进行，就是说，遗传算法是Walsh系数求和过程中的贪心。Bethke指出，如果一个函数的Walsh系数随着j（相应分割的序号）的阶和长度的增长而迅速降低，即重要的Walsh系数是与短的低阶分割相联系的，则这个函数容易用遗传算法求解，称为GA一易（GAeasy）。这时，通过估计低阶模式的平均值就可以发现全局最优点。这样的模式在群体中所占比例比高阶长模式更容易增长：“低阶”意味着它的样本较多，“短”使得它不容易被破坏。对遗传算法而言，估计它们的平均值要比估计高阶长模式容易得多。因此，Bethke得出结论，由于遗传算法难于对高阶分割中的高阶模式做出好的估计，在其它条件都相同的情况下，如果一个函数的Walsh分解中高阶分割对应了较重要（数值较大）的Walsh系数，则该函数难于用遗传算法求解，并称之为GA一难（GAhard）。从模式理论的角度来看，高阶系数小，意味着低阶模