遗传算法的基本原理学习培训课件

1、第四章 遗传算法的基本原理 4.1 遗传算法的基本描述 4.2 遗传算法的模式理论4.3 遗传算法与其他搜索算法的比较4.4 遗传算法的高级实现4.1.1 标准遗传算法流程：1编码2初始群体的生成3适应度评估检测4WHILE DO1. 选择2. 交叉3. 变异4. 适应度评估检测5END DO 4.1 遗传算法的基本描述选择交叉当前代中间代下一代4.1 遗传算法的基本描述4.1.3 遗传编码定义：由问题空间向GA编码空间的映射称为编码，而由编码空间向问题空间的映射成为译码。问题编码一般应满足以下三个原则：1）完备性（completeness）：问题空间中的所有点都能能成为GA编码空间中的点的表

2、现型2）健全性（soundness）：GA编码空间中的染色体位串必须对应问题空间中的某一潜在解。3）非冗余性（non-redundancy）：染色体和潜在解必须一一对应。4.1 遗传算法的基本描述4.1.3 遗传编码根据模式定理，De Jong进一步提出了较为客观明确的编码评估准则，称之为编码原理。具体可以概括为两条规则：1）有意义积木块编码规则：编码应易于生成与所求问题相关的短距和低阶的积木块。2）最小字符集编码规则：编码应采用最小字符集，以使问题得到自然、简单的表示和描述。4.1 遗传算法的基本描述1二进制编码1）连续实函数的二进制编码设一维连续实函数 采用长度维L的二进制字符串进行定长编

3、码，建立位串空间：k=1,2,K; l=1,2,L; K=2L表示精度为 。将个体又从位串空间转换到问题空间的译码函数的公式定义为：4.1 遗传算法的基本描述对于n维连续函数 ，各维变量的二进制编码位串的长度为li,那么x的编码从左到右依次构成总长度为 的二进制编码位串。相应的GA编码空间为：，K=2L该空间上的个体位串结构为对于给定的二进制编码位串sk,位段译码函数的形式为 ， i = 1,2,n 4.1 遗传算法的基本描述2其他编码1) 大字符集编码（相对于二进制编码）2) 序列编码（TSP）3) 实数编码4) 树编码5) 自适应编码6) 乱序编码 4.1 遗传算法的基本描述4.1.4 群

4、体设定 1。初始群体的设定一般来讲，初始群体的设定可以采用如下的策略：根据问题固有知识，设法把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定初始群体。先随机生成一定数目的个体，然后从中挑出最好的个体加入到初始群体中。这一过程不断重复，直到初始群体中个体数达到了预定的规模。4.1 遗传算法的基本描述4.1.4 群体设定 2。群体规模的设定 根据模式定理，若群体规模为M，则遗传操作可从这M个个体中生成和检测O(M3)个模式，并在此基础上不断形成和优化积木块，直到找到最优解。群体规模N，模式阶i，被采样的模式数量的期望Mi (i = 1, 2, , )之间满足如下关系：群体规模

5、一般不随迭代而变化，但也不绝对。4.1 遗传算法的基本描述4.1.5 适应度函数（评价函数） 1。目标函数映射成适应度函数 2。适应度函数定标 1）线性定标（linear scaling）f = af + b2）截断（sigma truncation）3） 乘幂标f = fK4） 指数定标f = exp(-bf)4.1 遗传算法的基本描述4.1.6 遗传算子 包括三个基本遗传算子（genetic operator）：选择，交叉和变异。这三个遗传算子具有一些特点：（1）这三个算子的操作都是随机化操作，因此，群体中个体向最优解迁移的规则是随机的。需要强调的是，这种随机化操作和传统的随机搜索方法是有

6、区别的。遗传操作进行的是高效有向的搜索，而不是如一般随机搜索方法所进行的无向搜索。（2）遗传操作的效果和所取的操作概率、编码方法、群体大小，以及适应度函数的设定密切相关。（3）三个基本算子的操作方法和操作策略随具体求解问题的不同而异。或者说，是和个体的编码方式直接相关。 4.1.6 遗传算子一、选择（selection）算子 从群体中选择优胜个体，淘汰劣质个体的操作叫选择。选择算子有时又称为再生算子（reproduction operator）。选择即从当前群体中选择适应度值高的个体以生成配对池（mating pool）的过程。 4.1.6 遗传算子一、选择（selection）算子 1、适应

7、度比例选择首先计算每个个体的适应度值，然后计算出此适应度值在群体适应度值总和中所占的比例，表示该个体在选择过程中被选中的概率。选择过程体现了生物进化过程中“适者生存，优胜劣汰”的思想。 对于给定的规模为n的群体 ，个体 的适应度值为 ，其选择概率为： 问题：易出现未成熟收敛4.1.6 遗传算子一、选择（selection）算子 2、Boltzmann选择在群体进化过程中，不同阶段需要不同地选择压力。早期阶段选择压力较小，我们希望较差地个体也又一定地生存机会，使得群体保持较高地多样性；后期阶段，选择压力较大，我们希望GA缩小搜索邻域，加快当前最优解的改善速度。为了动态调整群体进化过程中的选择压力

8、，Goldberg设计了Boltzmann选择方法。个体选择概率为： 4.1.6 遗传算子一、选择（selection）算子 3、排序选择 排序选择方法是将群体中个体按其适应度值由大到小的顺序排成一个序列，然后将事先设计好的序列概率分配给每个个体。排序选择不利用个体适应度值绝对值的信息，可以避免群体进化过程中的适应度标度变换。4.1.6 遗传算子一、选择（selection）算子 3、排序选择 对于给定的规模为n的群体 ，并且满足个体适应度值降序排列 。假设当前群体最佳个体a1在选择操作后的期望数量为 ，即；最差个体an在选择操作后的期望数量为 。其它个体的期望数量按等差序列计算， ，故现在排

9、序选择概率为 4.1.6 遗传算子一、选择（selection）算子 4、联赛选择（tournament selection）基本思想：从当前群体中随机选择一定数量的个体（放回或者不放回），将其中适应值最大的个体放入配对池中。反复执行这一过程，直到配对池中的个体数量达到设定的值。联赛规模用q表示，也称q-联赛选择。联赛选择与个体的适应度值由间接关系，注重适应度值大小的比较。联赛规模一般取q=2。4.1.6 遗传算子一、选择（selection）算子 5、精英选择 如果下一代群体的最佳个体适应度值小于当前群体最佳个体的适应度值，则将当前群体最佳个体或者适应度值大于下一代最佳个体适应度值的多个个体

10、直接复制到下一代，随机替代和替代最差的下一代群体中的相应数量的个体。 精英选择是群体收敛到全局最优解的一种基本保障。 4.1.6 遗传算子一、选择（selection）算子 6、稳态选择 稳态选择操作中，仅有少量个体按适应度值比例选择方法被选择，通过遗传操作生成新的个体。新个体放回到群体中时，随机替代等量的旧个体，或者替代等量的最差的旧个体。 Holland将稳态选择方法应用于分类器规则学习中，最大程度继承已获得的规则，实现增量学习。 De Jong将下一代群体中生成的与上一代不同的新个体所占的比例称为“代沟”（generation gap）。代沟越大，说明新个体的生成比例越高，群体搜索新的编

11、码空间的能力（探索）越强。4.1.6 遗传算子二、交叉（Crossover）算子 交叉算子是模仿自然界有性繁殖的基因重组过程，其作用在于将已有的优良基因遗传给下一代个体，并生成包含更复杂基因结构的新个体。交叉操作一般分为以下几个步骤：1）从配对池中随机取出要交配的一对个体；2）根据位串长度L，对要交叉的一对个体，随机选取1, L-1中一个或多个整数k作为交叉位置；3）根据交叉概率实施交叉操作，配对个体在交叉位置处，相互交换各自的部分内容，从而形成新的一对个体。4.1.6 遗传算子二、交叉（Crossover）算子 1、一点交叉（one-point crossover）位串A： 1 1 0 1

12、| 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 4.1.6 遗传算子二、交叉（Crossover）算子 1、两点交叉（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 1 4.1.6 遗传算子二、交叉（Crossover）算子 1、多点交叉（multi-point crossover）位串A： 1 1 | 0 1 | 1

13、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.1.6 遗传算子二、交叉（Crossover）算子 1、一致交叉一致交叉即染色体位串上的每一位按相同概率进行随机均匀交叉。一致交叉算子生成的新个体位：操作描述如下： ：，x是取值为0，1上符合均匀分布的随机变量。4.1.6 遗传算子三、变异（Mutation）算子 变异操作模拟自然界生物体进化中染色体上某位基因发生的突变现象，从而改变染色体的结构和物理性状。在标准遗传算法中，变异算子通过按变异概率pm随机反转某位等位基因的二进

14、制字符值来实现。对于给定的染色体位串 ，具体如下：生成新的个体 。其中，xi是对应于每一个基因位产生的均匀随机变量， 。 4.1.6 遗传算子四、逆转（Inversion Operator）算子 逆转操作首先在个体位串上随机地选择两个点，位串染色体被这两个点分成三段，将中间段的左右顺序倒转过来与另两段相连，形成新的个体位串。例如：长度为10的二进制位串，其中下划线标示的等位基因为重要基因：1011101101（是倒位位置）经倒位后变为1011011101。新的位串中重要基因更为靠近，被单点交叉算子分离的可能性大大降低了。4.1.6 遗传算子四、换位（Swap Operator）算子换位操作首先

15、在个体位串上随机地选择两个基因，将这两个基因的位置互换，形成新的个体位串。例如：长度为10的二进制位串，其中下划线标示的为随机选中的基因：1011101101经换位后变为1111101100 4.1.7 迭代终止条件一般采用设定最大代数的方法。其次，可以根据群体的收敛程度来判断，通过计算种群中的基因多样性测度，即所有基因位的相似性程度来进行控制。第三，根据算法的离线性能和在线性能的变化进行判定。最后，在采用精英保留选择策略的情况下，按每代最佳个体的适应值的变化情况确定。 4.1.8 控制参数1）位串长度L：位串长度L的选择取决于特定问题解的精度。要求的精度越高，位串越长，但需要更多的计算时间。

16、为提高运算效率，变长度位串或者在当前所达到的较小可行域内重新编码，是一种可行的方法，并显示了良好性能。2）群体规模n：大群体含有较多模式，为遗传算法提供了足够的模式采样容量，可以改进GA搜索的质量，防止成熟前收敛。但大群体增加了个体适应性评价的计算量，从而使收敛速度降低。一般情况下建议n20200。4.1.8 控制参数3）交叉概率Pc：交叉概率控制着交叉算子的应用频率，在每一代新的群体中，需要对Pcn个个体的染色体结构进行交叉操作。交叉概率越高，群体中新结构的引人愈快，已获得的优良基因结构的丢失速度也相应升高。而交叉概率太低则可能导致搜索阻滞。一般取Pc=0.601.00。4）变异概率Pm：变

17、异操作是保持群体多样性的有效手段，交叉结束后，交配池中的全部个体位串上的每位等位基因按变异率Pm随机改变，因此每代中大约发生PmnL次变异。变异概率太小，可能使某些基因位过早丢失的信息无法恢复；而变异概率过高，则遗传搜索将变成随机搜索。一般取Pm = 0.0050.01。 4.1.8 控制参数从理论上来讲，不存在一组适用于所有问题的最佳参数值，随着问题特征的变化，有效参数的差异往往非常显著。 4.1.9 GA的性能评估 关于搜索类算法的性能评估，一般可以归纳为算法的求解效率和求解质量两个方面。算法的求解效率是比较获得同样的可行解所需要的计算时间。算法的求解质量是在规定的时间（或者时间相关指标）

18、内所获得的可行解的优劣。4.1.9 GA的性能评估 1适应值函数计算次数该指标是指发现同样适应性的个体，或者找到同样质量的可行解，所需要的关于个体评价的适应值函数的计算次数（function evaluations）。显然，该值越小说明相应GA的搜索效率越高。 该指标不仅可以用于不同参数设置GA的性能比较，也可以用于GA与其他搜索算法的比较。 4.1.9 GA的性能评估 2在线和离线性能函数 1）在线性能函数（on-line performance）：设GA的遗传策略为s（包括L，n，Pc，Pm，算子形式等），该策略的在线性能：即在线性能反映了群体平均适应值经平滑处理后的变化情况，描述了群体的

19、整体性状和进化能力。4.1.9 GA的性能评估 2在线和离线性能函数 2）离线性能函数（offline performance）：对于GA遗传策略s，其离线性能其中，f(a*，t)maxf(al, t)，f(a2, t)，f(an, t)，即当前群体中最佳个体的适应值。该指标反映了群体中最佳个体适应值经平滑处理后的变化情况，描述了个体的进化能力和GA的搜索能力。4.1.9 GA的性能评估 3最优解搜索性能 GA用于函数优化的目的就是发现问题的全局最优解，所以通常采用当前群体发现的最佳可行解的改善情况作为度量GA搜索能力的基本指标。 4.2 遗传算法的模式理论4.21 模式与模式空间位串上的某些

20、等位基因的联结与适应值函数之间存在着某种联系，这种联系提供了寻优过程的指导信息，引导着群体在位串空间中的移动方向。采用字符集K=0，1对问题参数进行二进制编码，位串空间表示为SL1,0L，该空间的大小为|SL|2L。扩展字符集K0,1,*，其中*是通配符或无关符（wild cards，or“dont cares”），即可和0或 1匹配。扩展位串空间表示为SeL1,0,*L，该空间的大小为| SeL |3L，则称SeL为SL的模式空间。显然，包含2L个位串的位串空间，对应于3L个模式位串的模式空间。4.2 遗传算法的模式理论4.21 模式与模式空间定义：扩展位串空间SeL0,1,*L中的任何一个

21、点H，称为对应于位串空间 SL1,0L的一个模式（Schema）： 其中a(al，a2，aL)，H(H1，H2，HL)， ，i = 1，2，L； ， 例如：0 * * 1 0，1 * 1 * *，0 * * * *4.2 遗传算法的模式理论4.21 模式与模式空间模式是由SL中具有共同特征的位串所组成的集合（对应于位串空间的子空间），它描述了该集合中位串上共同的基因特征。集合的大小N由模式中*的个数k决定，N=2k。例如：模式0 0 * *表示位串长度为4，两个高位基因为00的位串集合，即0000，0001，0010，0011如果包含这一模式的所有位串都具有较好的适应度，则该模式可能是一个重要

22、的模式。Goldberg将模式称为“超平面”（hyper plane），指出了模式在编码空间上的几何意义，模式包含的位串是编码空间相应超平面上的点。模式 H1 = 1 * * * *表示函数解空间的右半区域模式 H2 = 0 * * * *表示函数解空间的左半区域Y = X2模式 H3 = * * * * 1表示函数解空间的阴影区域（奇数位串）模式 H4 = * * * * 0表示函数解空间的空白区域（偶数位串）模式 H5 = * * * 1 *表示函数解空间的阴影区域模式 H6 = * * * 0 *表示函数解空间的空白区域模式 H7 = 1 0 * * * 的表示域，代表了1/4的解空间模

23、式 H8 = * * 1 * 1 的表示域，代表了1/4的解空间4.2 遗传算法的模式理论4.21 模式与模式空间模式的阶（schema order）是指模式中所含有0、1确定基因位的个数，记作O(H)。模式的定义距（defining length）是指模式中从左到右第一个非 * 位和最后一位非 * 位之间的距离，记作模式的维数（schema dimension）是指模式中所包含的位串的个数，也称为模式的容量，记作D(H)，D(H)=2L-O(H)。4.2 遗传算法的模式理论4.21 模式与模式空间令m = m(H，t)为模式H在第t代群体中所含位串数量，模式在t代群体中包含的个体位串为a1,

24、 a2, ,am，称为模式H在群体中的生存数量（survivals）或者采样样本（samples），(j = 1，2，m)，则模式H在第 t代群体中的适应值估计为即模式的适应值估计（简称模式的适应值）是群体中其所包含的全部个体的适应值的平均值。4.2 遗传算法的模式理论4.21 模式与模式空间从编码空间来看，m（H，t）是当前群体中包含属于模式H的个体数量，反映了所对应的模式空间的分布情况，该数量越大说明群体搜索越集中于模式H代表的子空间。从模式空间来看，m（H，t）是模式H在当前群体中的个体采样数量，反映了所对应的编码空间的分布情况。该数量越大说明群体中的个体越趋向相似和一致，在编码空间的搜

25、索范围越小。 一个模式H由位串长度L、阶O(H)、定义距 、容量D(H)和适应值f(H，t)等五个指标来描述。模式的引入为在一个有限字符集上定义的有限长度的位串之间的相似性度量和理论分析提供了有力的工具。4.2 遗传算法的模式理论4.22 模式定理和积木块假设 在选择算子作用下，对于平均适应度高于群体平均适应度的模式，其样本数将呈指数级增长：而对于平均适应度低于群体平均适应度的模式，其样本数将呈指数级减少。在选择和交叉算子作用下，模式定义距越小，则群体中该模式个体数量越容易呈指数级增长；模式定义距越大，则群体中该模式个体数量越不容易呈指数级增长。在变异算子作用下，阶数越小模式H越易于生存；阶数

26、越大，模式H越易于被破坏。 4.2 遗传算法的模式理论4.22 模式定理和积木块假设 模式定理：在遗传算子选择、交叉、变异的作用下，那些低阶、定义距短的、超过群体平均适应度值的模式的生存数量，将随着迭代次数的增加以指数规律增长。 模式定理的意义：统计决策中的双臂赌机问题表明：按指数规律提高将硬币投往平均支付高的赌机的概率，可以获得最大的累积支付。应用到优化问题则是：要获得最优的可行解，则必须保证较优解的样本数呈指数级增长。而模式定理保证了较优的模式（遗传算法的较优解）的样本数呈指数级增长，从而给出了遗传算法的理论基础。 4.2 遗传算法的模式理论4.22 模式定理和积木块假设 定义：具有低阶、

27、短定义距以及高适应度的模式称作积木块。积木块假设（building block hypothesis）：低阶、短距高平均适应度的模式（积木块）在遗传算子作用下，相互结合，能生成高阶、长距、高平均适应度的模式，并可最终生成全局最优解。 4.2 遗传算法的模式理论4.22 模式定理和积木块假设 模式定理和积木块假设比较准确地模拟了自然界的物种竞争和遗传法则，其中模式定理描述了GA群体中模式之间的竞争关系，积木块假设说明了有效基因之间的继承与重组。因此，模式定理和积木块假设构成了关于GA进化过程能够发现最优解的一个解释，被认为是解释遗传算法寻优原理的较系统的理论，统称为模式理论（schema the

28、ory）。它们也是GA进化动力学的基本理论，尽管还存在着不完善之处，但是它为深入研究遗传算法的运行机理奠定了基础。 4.2 遗传算法的模式理论4.22 模式定理和积木块假设 模式定理在一定程度上证明了标准遗传算法的有效性，但它仍有以下的缺点：（1）模式定理只对二进制编码适用，对其他编码方案尚没有相应的结论成立。（2）模式定理只给出了在下一代包含模式H的个体数的下限。我们无法据此推断算法的收敛性。（3）模式定理没有解决算法设计中控制参数选取等问题。4.2 遗传算法的模式理论4.22 模式定理和积木块假设 Bethke采用Walsh函数和一种巧妙的模式变换，提出了一种采用Walsh系数计算模式平均

29、适应度的有效分析方法，这使得在一些特定的适应度函数和编码方式下，可以判定积木块通过相互组合是否会产生最优解或接近最优解。Holland把Bethke的方法推广到了当群体非均匀分布时的模式平均适应度分析上。 4.2 遗传算法的模式理论4.3 骗问题 骗问题（deceptive Problem），即构造一个问题，给定一些带欺骗性质的初始条件，“迷惑”遗传算法，使其偏离全局最优解。为此，要最大限度地违背积木块假设，即使得低阶、短距高于平均适应度的模式生成局部最优点。由模式理论，一个问题能否用遗传算法有效地求解，取决于问题编码是否满足积木块假设，满足者用遗传算法求解效率较高，不满足者效率 较低、甚至找

30、不到满意解。 4.4 遗传算法的高级实现 4.4.1 小生境遗传算法生物总是倾向于与自己特征、性状相类似的生物(同类)生活在一起，一般总是与同类交配繁衍后代。这种正选型交配方式在生物遗传进化过程中是有其积极的作用的。生物学上，小生境(Niche)是指特定环境中一种组织(organism)的功能，而把有共同特性的组织称作物种(species)。 4.4.1 小生境遗传算法 4.4.1 小生境遗传算法1基于预选择机制的小生境技术1970年，Cavicchio率先在遗传算法中引入了基于预选择机制的小生境技术。只有在子串的适应度超过其父串的情况下，子串才能替换其父串，进入下一代群体。由于这种方式趋向于

31、替换与其本身相似的个体(父与子之间的性状遗传)，因而能够较好地维持群体的分布特性。Cavicchio声称使用这种方法可以在群体规模相对较小的情况下维持较高的群体分布特性。4.4 小生境遗传算法2基于排挤机制的小生境技术（ De Jong，1975年）(1)初始化;（建立初始群体，确定遗传参数，设定排挤因子CF）(2)计算个体的适应度；(3)遗传操作(选择、交叉和变异)；(4)从当前群体中随机选取群体规模的1CF个个体组成排挤因子成员(5)比较新产生的个体与排挤因子成员之间的相似性；(6)用新产生的个体去替换排挤因子成员中最相似的个体，形成新的当前群体；(7)如未满足算法终止条件则返回第(2)步

32、，否则算法终止。 4.4 小生境遗传算法3基于共享(sharing)机制的小生境技术（ Goldberg和Richardson， 1987年）定义了共享函数(sharing function)，用来确定每个个体在群体中的共享度。一个个体的共享度等于该个体与群体内的各个其它个体之间的共享函数值的总和。共享函数是关于两个体之间的关系密切程度(基因型的相似性或表现型的相似性)的函数，当个体间关系比较密切时，共享函数值较大，反之，则共享函数值较小。 4.4 小生境遗传算法设dij表示个体i和个体j之间的关系密切程度，S为共享函数，Si表示个体i在群体中的共享度，则有： 在计算了各个体的共享度后，个体的适应度f(i)依据