1、第二章 遗传算法的基本原理2.1 遗传算法的基本描述2.1.1 全局优化问题全局优化问题的定义：给定非空集合 S 作为搜索空间，f：S R 为目标函数，全局优化问题作为任务 给出，即在搜索空间中找到至少一个使目)(maxfS标函数最大化的点。全局最大值（点）的定义：函数值 称为一个全局最大值，)(*xf当且仅当 成立时， 被称为一个全局最大值点（全)(*xffSxS局最大解） 。局部极大值与局部极大值点（解）的定义：假设在 S 上给定了某个距离度量 ，如果对 ， ，使得对 ，Sx 0Sx，则称 x为一个局部极大值点，f (x)为一个局部极大)(),( fxfx值。当目标函数有多个局部极大点时，
2、被称为多峰或多模态函数（multi-modality function） 。主要考虑两类搜索空间：伪布尔优化问题：当 S 为离散空间 BL=0,1L,即所有长度为 L 且取值为 0或 1 的二进制位串的集合时，相应的优化问题在进化计算领域称为伪布尔优化问题。连续参数优化问题：当取 S 伪 n 维实数空间 Rn 中的有界集合 ，,1inibaS其中 ，i = 1, 2, , n 时，相应的具有连续变量的优化问题称为连续参数iba优化问题。对 S 为 BL=0,1L，常采用的度量时海明距离，当 时，常采,1inibaS用的度量就是欧氏距离。2.1.2 遗传算法的基本流程遗传算法的基本步骤如下：1）
3、选择编码策略，把参数集合 X 和域转换为位串结构空间 S；2）定义适应度函数 f(X)；3）确定遗传策略，包括群体规模，选择、交叉、变异算子及其概率。4）生成初始种群 P；5）计算群体中各个体的适应度值；6）按照遗传策略，将遗传算子作用于种群，产生下一代种群；7）迭代终止判定。遗传算法涉及六大要素：参数编码，初始群体的设定，适应度函数的设计，遗传操作的设计，控制参数的设定，迭代终止条件。2.1.3 遗传编码由于 GA 计算过程的鲁棒性，它对编码的要求并不苛刻。原则上任何形式的编码都可以，只要存在合适的对其进行操作的遗传算子，使得它满足模式定理和积木块假设。由于编码形式决定了交叉算子的操作方式，
4、编码问题往往称作编码-交叉问题。对于给定的优化问题，由 GA 个体的表现型集合做组成的空间称为问题（参数）空间，由 GA 基因型个体所组成的空间称为 GA 编码空间。遗传算子在GA 编码空间中对位串个体进行操作。定义：由问题空间向 GA 编码空间的映射称为编码，而有编码空间向问题空间的映射成为译码。问题编码一般应满足以下三个原则：1）完备性（completeness）：问题空间中的所有点都能能成为 GA 编码空间中的点的表现型。即编码应能覆盖整个问题空间。2）健全性（soundness）：GA 编码空间中的染色体位串必须对应问题空间中的某一潜在解。即每个编码必须是有意义的。3）非冗余性（non
5、-redundancy ）：染色体和潜在解必须一一对应。在某些情况下，为了提高 GA 的运行效率，允许生成包含致死基因的编码位串，它们对应于优化问题的非可行解。虽然会导致冗余或无效的搜索，但可能有助于生成全局最优解所对应的个体，所需的总计算量可能反而减少。根据模式定理，De Jong 进一步提出了较为客观明确的编码评估准则，称之为编码原理。具体可以概括为两条规则：1）有意义积木块编码规则：编码应易于生成与所求问题相关的短距和低阶的积木块。2）最小字符集编码规则：编码应采用最小字符集，以使问题得到自然、简单的表示和描述。1二进制编码1）连续实函数的二进制编码设一维连续实函数 采用长度维 L 的二
6、进制字符串进行定长编,),(vuxf码，建立位串空间：， ，KLaS,21),(21kLkka1,0klk=1,2,K; l=1,2,L; K=2L其中，个体的向量表示为 ，其字符串形式为),(21kLkk，s k 称为个体 ak 对应的位串。表示精度为 。Lkkas21 )12/(Luvx将个体又位串空间转换到问题空间的译码函数 的公式定义,1,0:L为： )2(1),(21 LjjkkLkk auvax对于 n 维连续函数 ，各维变),21(,),(),21 nivuxxf iin 量的二进制编码位串的长度为 li,那么 x 的编码从左到右依次构成总长度为的二进制编码位串。相应的 GA 编
7、码空间为：nilL1，K=2 L,21KaS该空间上的个体位串结构为 1,0),( 212122112 iklnlkniklikklkklkk aaaa nlnilill aas 2112对于给定的二进制编码位串 sk,位段译码函数的形式为， i = 1,2,n)(12),(21 iiii ljjlkliklikii auvax采用二进制编码的 GA 进行数值优化时，可以通过改变编码长度，协调搜索精度和搜索效率之间的关系。2）组合问题的二进制编码在很多组合优化问题中，目标函数和约束函数均为离散函数，采用二进制编码往往具有直接的语义，可以将问题空间的特征与位串的基因相对应。2其他编码1) 大字符
8、集编码2) 序列编码3) 实数编码4) 树编码5) 自适应编码6) 乱序编码7) 二倍体和显性规律Lawrence Davis 等学者主张：采用的编码对问题来讲应该时最自然的，并可以据此设计能够处理该编码的遗传算子。2.1.4 群体设定遗传算法的两个主要特点之一就是基于群体搜索的策略，群体的设定，尤其是群体规模的设定，对遗传算法性能有着重要的影响。这中间包括两个问题：1）初始群体如何设定；2）进化过程中各代的规模如何维持？1初始群体的设定遗传算法中初始群体中的个体是按一定的分布随机产生的，一般来讲，初始群体的设定可以采用如下的策略：1） 根据问题固有知识，设法把握最优解所占空间在整个问题空间中
9、的分布范围，然后，在此分布范围内设定初始群体。2） 先随机生成一定数目的个体，然后从中挑出最好的个体加入到初始群体中。这一过程不断重复，直到初始群体中个体数达到了预定的规模。2群体规模的设定根据模式定理，若群体规模为 M，则遗传操作可从这 M 个个体中生成和检测 O(M3)个模式，并在此基础上不断形成和优化积木块，直到找到最优解。显然 M 越大，遗传操作处理的模式就越多，生成有意义的积木块并逐渐进化为最优解的机会就越高。换句话说，群体规模越大，群体中个体的多样性越高，算法陷入局部最优解的危险就越小。另外，群体规模太小，会使遗传算法的搜索空间分布范围有限，因而搜索有可能停止在未成熟阶段，引起未成
10、熟收敛（premature convergence）现象。但是，从计算效率来看，群体规模越大，其适应度评价次数越多，计算量也就越大，从而影响算法的效率。研究表明，在二进制编码的前提下，为了满足隐并行性，群体个体数只要设定为 2L/2 即可，L 为个体串长度。这个数比较大，实际应用中群体规模一般取几十几百。2.1.4 适应度函数（评价函数）遗传算法在进化搜索中基本不用外部信息，仅用目标函数即适应度函数为依据。遗传算法的目标函数不受连续可微的约束且定义域可以为任意集合。对适应度函数的唯一要求是，针对输入可计算出能加以比较的非负结果（比例选择算子需要） 。需要强调的是，适应度函数值是选择操作的依据，
11、适应度函数设计直接影响到遗传算法的性能。1目标函数映射成适应度函数对于给定的优化问题，目标函数有正有负，甚至可能是复数值，所以有必要通过建立适应度函数与目标函数的映射关系，保证映射后的适应度值是非负的，而且目标函数的优化方向应对应于适应度值增大的方向。1）对最小化问题，建立如下适应函数和目标函数的映射关系：否 则若,0)(),()( maxmaxcgcf其中，c max 可以是一个输入值或是理论上的最大值，或者是当前所有大或最近 K 代中 g(x)的最大值，此时 cmax 随着代数会有变化。2）对于最大化问题，一般采用以下映射： 否 则若,00)(,)(minminxgxgf其中，c min
12、可以是一个输入值，或者是当前所有代或最近 K 代中 g(x)的最小值2适应度函数定标在遗传进化的初期，通常会出现一些超常个体，若按比例选择策略，这些异常个体有可能在群体中占据很大的比例，导致未成熟收敛。显然，这些异常个体因竞争力太突出，会控制选择过程，从而影响算法的全局优化性能。另以方面，在遗传进化过程中，虽然群体中个体多样性尚存在，但往往会出现群体的平均适应度已接近最佳个体适应度，这时，个体间的竞争力相似，最佳个体和其它个体在选择过程中有几乎相等的选择机会，从而使有目标的优化过程趋于无目标大的随机搜索过程。对未成熟收敛现象，应设法降低某些异常个体的竞争力，这可以通过缩小相应的适应度值来实现。
13、对于随机漫游现象，应设法提高个体间的竞争力差距，这可以通过放大相应的适应度值来实现。这种适应度的缩放调整称为适应度定标。1）线性定标（linear scaling）f = af + b2） 截断（sigma truncation）)(cff3）乘幂标f = fK4）指数定标f = exp(-bf)2.1.5 遗传算子遗传操作是模拟生物基因遗传的操作。包括三个基本遗传算子（genetic operator）：选择，交叉和变异。这三个遗传算子具有一些特点：（1） 这三个算子的操作都是在随机扰动情况下进行的。换句话说，遗传操作是随机化操作，因此，群体中个体向最优解迁移的规则是随机的。需要强调的是，这
14、种随机化操作和传统的随机搜索方法是有区别的。遗传操作进行的是高效有向的搜索，而不是如一般随机搜索方法所进行的无向搜索。（2） 遗传操作的效果和所取的操作概率、编码方法、群体大小，以及适应度函数的设定密切相关。（3） 三个基本算子的操作方法和操作策略随具体求解问题的不同而异。或者说，是和个体的编码方式直接相关。1、选择（selection）算子从群体中选择优胜个体，淘汰劣质个体的操作叫选择。选择算子有时又称为再生算子（reproduction operator） 。选择即从当前群体中选择适应度值高的个体以生成配对池（mating pool）的过程。为了防止由于选择误差，或者交叉和变异的破坏作用而
15、导致当前群体的最佳个体在下一代的丢失，De Jong 提出了精英选择（elitist selection）策略和代沟的概念。Holland 等提出了稳态选择（steady-state selection）策略。下面一些概念可以用来比较不同的选择算法：(1)选择压力(selection pressure)：最佳个体选中的概率与平均选中概率的比值。(2)偏差(bias) 个体正规化适应度与其期望再生概率的绝对差值。(3)个体扩展(spread) 单个个体子代个数的范围。(4)多样化损失(loss of diversity) 在选择阶段末选中个体数目占种群的比例。(5)选择强度(selection
16、intensity) 将正规高斯分布应用于选择方法，期望平均适应度。(6)选择方差(selection variance) 将正规高斯分布应用于选择方法，期望种群适应度的方差。1）适应度比例选择是最基本的选择方法，其中每个个体被选择的期望数量与其适应度值和群体平均适应度值的比例有关，通常采用轮盘赌（roulette wheel）方式实现。这种方式首先计算每个个体的适应度值，然后计算出此适应度值在群体适应度值总和中所占的比例，表示该个体在选择过程中被选中的概率。选择过程体现了生物进化过程中“适者生存，优胜劣汰”的思想。对于给定的规模为 n 的群体 ，个体 的适应度值为,21naPPj，其选择概率
17、为：)(jafnjafpniijjs ,21,)()(1经过选择操作生成用于繁殖的配对池，其中父代种群中个体生存的期望数目为： njapnPjsj ,21),()( 当群体中个体适应度值的差异非常大时，最佳个体与最差个体被选择的概率之比（选择压力）业将按指数增长。最佳个体在下一代的生存机会将显著增加，而最差个体的生存机会将被剥夺。当前群体中的最佳个体将快速充满整个群体，导致群体的多样性迅速降低，GA 也就过早地丧失了进化能力。这是适应度比例选择容易出现地问题。2）Boltzmann 选择在群体进化过程中，不同阶段需要不同地选择压力。早期阶段选择压力较小，我们希望较差地个体也又一定地生存机会，使
18、得群体保持较高地多样性；后期阶段，选择压力较大，我们希望 GA 缩小搜索邻域，加快当前最优解的改善速度。为了动态调整群体进化过程中的选择压力，Goldberg 设计了Boltzmann 选择方法。个体选择概率为： njeapniTaffjsij ,21,)(1/)(/ 其中，T0 是退火温度。 T 随着迭代地进行逐渐缩小，选择压力将随之升高。T 是控制群体进化过程中选择压力的关键，一般 T 的选择需要考虑预计最大进化代数。3）排序选择排序选择方法是将群体中个体按其适应度值由大到小的顺序排成一个序列，然后将事先设计好的序列概率分配给每个个体。显然，排序选择域个体的适应度值的绝对值之间无直接关系，
19、仅仅与个体之间适应度值的相对大小有关。排序选择不利用个体适应度值绝对值的信息，可以避免群体进化过程中的适应度标度变换。由于排序选择概率比较容易控制，所以在实际计算过程中经常采用，特别是适用于动态调整选择概率，根据进化效果适时改变群体的选择压力。最常用的排序选择方法是采用线性函数将队列序号映射为期望的选择概率，即线性排序选择（linear ranking selection ） 。对于给定的规模为 n 的群体 ，并且满足个体适应度值降序,21naP排列 。假设当前群体最佳个体 a1 在选择操作后的期)()(21afaff望数量为 ，即 ；最差个体 an 在选择操作后的期望数量为1pn。其它个体的
20、期望数量按等差序列计算， 则np 11njj ，故现在排序选择概率为)1()1( jnjj njjnapjs ,2),() 由 可以导出 。要求 ，故 。当j10,ip21时，即最差个体在下一代生存的期望数量为 0，群体选择压力最0,2大；当 时，选择方式为按均匀分布的随机选择，群体选择压力最小。4）联赛选择（tournament selection ）联赛选择的基本思想是从当前群体中随机选择一定数量的个体（放回或者不放回） ，将其中适应值最大的个体放入配对池中。反复执行这一过程，直到配对池中的个体数量达到设定的值。联赛规模用 q 表示，也称 q-联赛选择。联赛选择与个体的适应度值由间接关系，
21、注重适应度值大小的比较。根据大量实验总结，联赛规模一般取 q=2。联赛选择的选择概率也是比较容易控制的，实际计算中也经常采用，适用于在 GA 迭代过程中动态调整选择概率，将进化效果与群体选择压力联系起来。研究证明，当群体规模比较大时，联赛选择与排序选择的个体选择概率基本相同。5）精英选择从 GA 的整个选择策略来讲，精英选择时群体收敛导优化问题全局最优解的一种基本保障。如果下一代群体的最佳个体适应度值小于当前群体最佳个体的适应度值，则将当前群体最佳个体或者适应度值大于下一代最佳个体适应度值的多个个体直接复制到下一代，随机替代和替代最差的下一代群体中的相应数量的个体。6）稳态选择De Jong
22、将下一代群体中生成的与上一代不同的新个体所占的比例称为“代沟” （generation gap） 。代沟越大，说明新个体的生成比例越高，群体正在搜索新的编码空间。稳态选择操作中，仅有少量个体按适应度值比例选择方法被选择，通过遗传操作生成新的个体。新个体放回到群体中时，随机替代等量的旧个体，或者替代等量的最差的旧个体。Holland 将稳态选择方法应用于分类器规则学习中，最大程度继承已获得的规则，实现增量学习。2、交叉（crossover）算子交叉操作时进化算法中遗传算法具有的原始性的独有特征。GA 交叉算子时模仿自然界有性繁殖的基因重组过程，其作用在于将已有的优良基因遗传给下一代个体，并生成包
23、含更复杂基因结构的新个体。交叉操作一般分为以下几个步骤：1）从配对池中随机取出要交配的一对个体；2）根据位串长度 L，对要交叉的一对个体，随机选取 1, L-1中一个或多个整数 k 作为交叉位置；3）根据交叉概率实施交叉操作，配对个体在交叉位置处，相互交换各自的部分内容，从而形成新的一对个体。实现个体结构重组的交叉算子的设计一般与所求解的具体问题有关，任何交叉算子需满足交叉算子的评估准则，即交叉算子需保证前一代中优秀个体的性状能在下一代的新个体中尽可能得到遗传何继承。此外，交叉算子设计和编码设计需协调操作。1）一点交叉（one-point crossover）一点交叉是由 Holland 提出
24、的最基础的一种交叉方式。一点交叉操作的信息量比较小，交叉点位置的选择可能带来较大的偏差（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 ）多点交叉是上述两种交叉的推广，有时又被称为广义交叉。一般来讲，多点交叉较少采用，因为它影响遗传算法的在线和离线性能。多点交叉不利于有效保存重要的模式。
