遗传算法基本原理

《遗传算法基本原理》由会员分享，可在线阅读，更多相关《遗传算法基本原理（70页珍藏版）》请在金锄头文库上搜索。

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

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

3、 采用长度维L的二进制字符串进 行定长编码，建立位串空间：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、序编码 4.1 遗传算法的基本描述4.1.4 群体设定 1。初始群体的设定一般来讲，初始群体的设定可以采用如下的策略：1) 根据问题固有知识，设法把握最优解所占空间在整个 问题空间中的分布范围，然后，在此分布范围内设定 初始群体。2) 先随机生成一定数目的个体，然后从中挑出最好的个 体加入到初始群体中。这一过程不断重复，直到初始 群体中个体数达到了预定的规模。4.1 遗传算法的基本描述4.1.4 群体设定 2。群体规模的设定 根据模式定理，若群体规模为M，则遗传操作可 从这M个个体中生成和检测O(M3)个模式，并在此基础上不断形成和优化积木块，直到找到最优解 。群体规模N，模式阶i，被采样的模

5、式数量的期望Mi (i = 1, 2, , )之间满足如下关系：群体规模一般不随迭代而变化，但也不绝对。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）。选择即从当前群体中选择适应度值高的个体以生成 配对池（matin

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

8、择压力较大，我们希望GA缩 小搜索邻域，加快当前最优解的改善速度。为了动态调整群体进 化过程中的选择压力，Goldberg设计了Boltzmann选择方法。个体 选择概率为： 4.1.6 遗传算子一、选择（selection）算子 3、排序选择 排序选择方法是将群体中个体按其适应度值由大到小的顺序排成 一个序列，然后将事先设计好的序列概率分配给每个个体。排序选择不利用个体适应度值绝对值的信息，可以避免群体进化 过程中的适应度标度变换。4.1.6 遗传算子一、选择（selection）算子 3、排序选择 对于给定的规模为n的群体 ，并且满足个体适应度值降序排列 。假设当前群体最佳个体a1在选择操

9、作后的期望数量为 ，即；最差个体an在选择操作后的期望数量为 。其它个体的期望数量按等差序列计算， ，故现在排序选择概率为 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将下一代群体中生成

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

12、体。4.1.6 遗传算子二、交叉（Crossover）算子 1、一点交叉（one-point crossover）位串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 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

13、遗传算子二、交叉（Crossover）算子 1、多点交叉（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.1.6 遗传算子二、交叉（Crossover）算子 1、一致交叉一致交叉即染色体位串上的每一位按相同概率进行随机均匀交叉。一致交叉算子生成的新个体位：操作描述如下：，x是取值为0，1上符合均匀分布的随机变量。4.1.6 遗传算子三、变异（Mutation）算子 变异操作模拟自然界生物体进化

14、中染色体上某位基因发生的突变 现象，从而改变染色体的结构和物理性状。 在标准遗传算法中，变异算子通过按变异概率pm随机反转某位等 位基因的二进制字符值来实现。 对于给定的染色体位串 ，具体如下：生成新的个体 。其中，xi是对应于每一个基因位产生的均匀随机变量， 。 4.1.6 遗传算子四、逆转（Inversion Operator）算子 逆转操作首先在个体位串上随机地选择两个点，位串染色体被这 两个点分成三段，将中间段的左右顺序倒转过来与另两段相连， 形成新的个体位串。例如：长度为10的二进制位串，其中下划线标示的等位基因为重 要基因：1011101101（是倒位位置）经倒位后变为101101

15、1101。新的位串中重要基因更为靠近，被单点交叉算子分离的可能性大 大降低了。4.1.6 遗传算子 四、换位（Swap Operator）算子换位操作首先在个体位串上随机地选择两个基因，将这两个基因 的位置互换，形成新的个体位串。 例如：长度为10的二进制位串，其中下划线标示的为随机选中的 基因： 1011101101经换位后变为1111101100 4.1.7 迭代终止条件一般采用设定最大代数的方法。其次，可以根据群体的收敛程度来判断，通过计算种群 中的基因多样性测度，即所有基因位的相似性程度来进 行控制。第三，根据算法的离线性能和在线性能的变化进行判定 。最后，在采用精英保留选择策略的情况下，按每代最佳 个体的适应值的变化情况确定。 4.1.8 控制参数1）位串长度L：位串长度L的选择取决于特定问题解的精度 。要求的精度越高，位串越长，但需要更多的计算时间 。为提高运算效率，变长度位串或者在当前所达到的较 小可行域内重新编码，是一种可行的方法，并显示了良 好性能。2）群体规模n：大群体含有较多模式，为遗传算法提供了 足够的模式采样容量，可以改进GA搜索的质量，防止成 熟前收敛。但大群体增加了个体适应性评价的计算量， 从而使收敛速度降低。一般情况下建议n