遗传算法原理及其应用 第三章 遗传算法的基本实现技术

挺好

遗传算法原理及其应用王正山 wzs@

挺好

第三章 遗传算法的基本实现技术 掌握编码方法 掌握适应度函数的设计方法 掌握选择、交叉、变异算子的设计方法 了解遗传算法的运行参数设置 掌握约束条件处理方法 掌握Matlab遗传算法工具箱

挺好

3.1 编码方法 编码– 在遗传算法中如何描述问题的可行解，即把一个问题的可行解从 其解空间转换到遗传算法所能处理的搜索空间的转换方法称为编 码。设计一个完美的编码方案是遗传算法的应用难点之一。 设计一个完美的编码方案是遗传算法的应用难点之一。 设计一个完美的编码方案是遗传算法的应用难点之一

编码规则– 有意义的积木块编码原则：应使用能易于产生与所求问题相关的 有意义的积木块编码原则 且具有低阶、短定义长度模式的编码方案。 – 最小字符集编码原则 最小字符集编码原则：应使用能使问题得到自然表示或描述的具 有最小编码字符集的编码方案。

编码分类– 二进制编码方法 – 浮点编码方法 – 符号编码方法

挺好

3.1.1 二进制编码方法 二进制编码方法– 二进制编码方法使用的编码符号集是由二进制符号0和1所组成 的二值符号集{0,1},它构成的个体基因型是一个二进制编码的 符号串。 – 二进制编码符号串的长度与问题所要求的求解精度有关。假设 二进制编码符号串的长度与问题所要求的求解精度有关。 某一个参数的取值范围是[Umin, Umax],我们用长度为l的二进制 编码符号串来表示该参数，则它总共能够产生2l中不同的编码。 因此，二进制的编码精度为 δ = U max U min 。2l 1

– 二进制编码的优点

假设某一参数的编码是：

bl bl 1bl 2 b2b1 编码、解码操作简单易行。 交叉、变异等遗传操作便于实现。 则对应的解码公式为： 符合最小字符集编码原则。 l 便于利用模式定理对算法进行理论分析。 U max U min i 1

x = U min + (∑ bi 2 ) i =1

2l 1

挺好

3.1.2 格雷码编码方法 格雷码编码方法– 引入格雷码的原因 二进制编码不便于反映一些连续函 数优化问题的特征且使得遗传算法 的局部搜索能力较差。 g m = bm g i = bi +1 ⊕ bi十进制数 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

i = m - 1, m - 2, ,1二进制码 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 格雷码 0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000

– 格雷码要求连续的两个整数所对应 的编码值之间仅仅只有一个码位是 不同的，其余码位都完全相同。 – 右表是十进制0~15之间的二进制码 和相应的格雷码。 – 格雷码的优点

便于提高遗传算法的局部搜索能力。 交叉、变异等遗传操作便于实现。 符合最小字符集编码原则。 便于利用模式定理对算法进行理论 分析。 二进制 格雷码

编码和解码过程：决策向量

bm = g m bi = bi +1 ⊕ g i

i = m - 1, m - 2, ,1

挺好

3.1.3 浮点数编码方法 浮点数编码方法– 二进制编码的缺点 二进制编码存在着连续函数离散化时的映射误差。 二进制编码不便于反映所求问题的特定知识，也不便于处理非平凡约束条件。

– 浮点数编码 是指个体的每个基因值用某一范围内的一个浮点数来表示，个体的编码长度 等于其决策变量的个数。 例如，X=[5.80, 6.90, 3.50, 3.80, 5.00] 在浮点数编码方法中，必须保证基因值在给定的区间限制范围内。

– 浮点数编码的优点 适合于在遗传算法中表示范围较大的数。 适合于精度要求较高的遗传算法。 便于较大空间的遗传搜索。 改善了遗传算法的复杂性，提高了运算效率。 便于遗传算法与经典优化方法的混合使用。 便于设计针对问题的专门知识的知识型遗传算子。 便于处理复杂的决策变量约束条件。

挺好

3.1.4 无符号数编码方法 符号编码方法– 指个体染色体编码串中的基因值取自一个无数值含义、而只有代 码含义的符号集。这个符号集可以是一个字母表，也可以是一个 数字序号表。 – 旅行商问题:已知n个城市之间的相互距离。现有一推销员必须遍 访这n个城市，并且每个城市只能访问一次，最后又必须返回出发 城市。如何安排他对这些城市的访问次序，可使其旅行路线的总 长度最短? – 例如，对于旅行商问题，假设有n个城市分别记为C1, C2, …, Cn, 将各个城市的代号按其被访问的顺序连接在一起就可构成一个表 示旅行路线的个体。例如，X:[C1, C2, …, Cn]。若将各个城市按其 代号的下标进行编号，则这个个体也可表示为：X:[1,2, …,n ] 。 – 符号编码的优点 符合有意义积木块的编码原则。 便于在遗传算法中利用所求解问题的专门知识。 便于遗传算法与相关近似算法之间的混合使用。

挺好

3.1.5 多参数级联编码方法 多参数级联编码– 对含有多个变量的个体进行编码的方法就称为多参数编码方法。 – 将各个参数分别以某种编码方法进行编码，然后再将它们的编码按一 定顺序联接在一起就组成了表示全部参数的个体编码。这种编码方法 称为多参数级联编码方法。 – 在进行多参数级联编码时，每个参数的编码方式可以是二进制编码、 格雷码、浮点数编码或符号编码等编码方式中的一种，每个参数可以 真有不同的上下界，也可以有不同的编码长度或编码

精度。

b11b12 b1l1 | b21b22 b2l2 | | bn1bn 2 bnlnx1 x2 xn

挺好

3.1.6 多参数交叉编码方法 多参数交叉编码方法– 基本思想 将各个参数中起主要作用的码位集中在一起。

– 具体方法 在进行多参数交叉编码时，可先对各个参数进行分组编码(假设共有 n个参数，每个参数都用长度为m的地二进制串表示); n m ) 然后取各个参数编码串中的最高位联接在一起，以它们作为个体编 码串的前n位编码；再取各个参数编码串中的次高位联接在一 起，…。 这样所组成的长度为mn位的编码串就是多参数的一个交叉编码串。

b11b21 bn1 | b12b22 bn 2 | | b1mb2 m bnm– 思考题：多参数级联编码与多参数交叉编码方法的适用范围？

挺好

3.2 适应度函数 目标函数与适应度函数– 目标函数 是指所关心的目标(某一变量y)与相关的因素(某些变量xi)的函 数关系。

– 适应度函数 度量个体适应度的函数称为适应度函数。

– 评价个体适应度的一般过程 对个体编码串进行解码处理后，可得到个体的表现型。 由个体的表现型可计算出对应个体的目标函数值。 根据最优化问题的类型，由目标函数值按一定的转换规则求出 个体的适应度。第二章中给出的是基本遗传算法的目标函数到 第二章中给出的是基本遗传算法的目标函数到 适应度函数的变换方法。 适应度函数的变换方法。F(X) = f(X)+Cmin if f(X)+Cmin> 0 0 if f(X)+Cmin ≤ 0

挺好

3.2 适应度函数…– 适应度函数尺度变化的原因 在遗传算法运行早期– 群体中可能会有少数几个个体的适应度相对其他个体来说非常高 非常高。 非常高 若按照常用的比例选择算子来确定个体的遗传数量时，则这几个 相对较好的个体将在下一代群体中占有很高的比例，在极端情况 下或当群体现模较小时，新的群体甚至完全由这样的少数几个个 体所组成。这时产生新个体作用较大的交叉算子就起不了什么作 这时产生新个体作用较大的交叉算子就起不了什么作 用，因为相同的两个个体不论在何处进行交叉操作都永远不会产 生出新的个体。 生出新的个体。

在遗传算法运行的后期阶段– 群体中所有个体的平均适应度可能会接近于群体中最佳个体的适 应度。也就是说，大部分个体的适应度和最佳个体的适应度差异 差异 不大，它们之间无竞争力，都会有以相接近的概率被遗传到下一 不大 代的可能性，从而使得进化过程无竞争性可言，只是一种随机的 只是一种随机的 选择过程。 选择过程。

挺好

3.2 适应度函数…– 适应度尺度变换方法 线性尺度变换(图示见下页)F ' = aF + b (F : 原适应度， F': 尺度变换后的新适应度，a

和b是系数)

乘幂尺度变换F'= F k (F : 原始适应度， F': 尺度变换后的新适应度 ， k是系数)

指数尺度变换F ' = exp( β F ) (F : 原适应度， F': 尺度变换后的新适应度，β是系数)

挺好

3.2 适应度函数…– 线性比例尺度变换的正常情况 示意图 种群规模大小为50~100时， 时 种群规模大小为 C的取值是 的取值是1.2~2。 的取值是 。C*Favg F’max F’avg 新 适 应 度 F’min

Fmin

Favg

Fmax

满足两个条件

原适度度

– 尺度变换后全部个体的新适应度的平均值要等于其原始适应度的平均 适应值。 – 尺度变换后群体中新的最大适应度要等于其原平均适应度的指定倍数。

使用适应度尺度变换时，群体中少数几个优良个体的适应度 按比例缩小，同时几个较差个体的适应度也按比例扩大。

挺好

3.2 适应度函数…– 线性比例尺度变换的非正常情况 示意图

原因：在遗传算法搜索过程的后期阶段，随着个体适应度从总体 上的不断改进，群体中个体的最大适应度和全部个体的平均适应 度较接近，而少数几个较差的个体的适应度却远远低于最大适应 度，这时要想维持C的值不变， 将有可能会使较差个体的适应度 为负数。 解决方法：把原最小适应度Fmin映射为F’min,使得F’min值为0, 并且保持原平均适应度Favg与新的平均适应度F’avg相等。

挺好

3.3 选择算子 比例选择– 各个个体被选中的概率与其适应度大小成正比。设群体大小为M,个 体i的适应度为Fi,则个体i被选中的概率pis为：

pis = Fi / ∑ Fii =1

M

(i = 1,2, , M)

最优保存策略– 迄今为止的适应度最高的个体不参与交叉运算和变异运算，而是用它 来替换掉本代群体中经过交叉、变异等遗传操作后所产生的适应度最 低的个体。 – 具体操作过程 找出当前群体中适应度最高的个体 适应度最高的个体和适应度最低的个体。 适应度最高的个体 最佳个体的适应度比总的迄今为止的最好个体的适应度 迄今为止的最好个体的适应度还要 若当前群体中最佳个体的适应度 最佳个体的适应度 迄今为止的最好个体的适应度 高，则以当前种群中的最佳个体 最佳个体作为新的迄今为止的最好个体 新的迄今为止的最好个体。 最佳个体 新的迄今为止的最好个体 用迄今为止的最好个体 迄今为止的最好个体替换掉当前群体中的最差个体 当前群体中的最差个体。 迄今为止的最好个体 当前群体中的最差个体

– 最优保存策略可视为选择操作的一部分。

当前种群的最佳个体 当前种群的最差个体 迄今为止的最好个体

挺好

3.3.3 确定式采样选择 确定式采样选择– 基本思想 按照一种确定的方式来进行选择操

作。

– 操作过程 计算群体中各个个体在下一代群体中的期望生存数目Ni = ( Fi / sum(Fi) ) x M。 用Ni的整数部分确定各个对应个体在下一代群体中的生存数目。 按照Ni的小数部分对个体进行降序排序，顺序取前苦干个个体 使得下一代群体中的个体数目达到M-sum(Ni)个。

挺好

3.3.4 无回放随机选择 无回放随机选择– 基本思想 根据每个个体在下一代群体中的生存期望值来进行随机运算。

– 操作过程 计算群体中每个个体在下一代群体中的生存期望数目Ni。 若某一个个体被选中参与交叉运算，则它在下一代中的生存期 望数目减去0.5;若某一个个体没有被选中参与交叉运算，则 它在下一代中的生存期望数目减去1.0。 随着选择过程的进行，若某一个个体的生存期望数目小于0, 则该个体就不再有机会被选中。

挺好

3.3.5 无回放余数随机选择 无回放余数随机选择– 操作过程 计算群体中每一个个体在下一代群体中的生存期望数目Ni。 取Ni的整数部分为对应个体在一下代群体中的生存数目。这 样共可确定出下一代群体中的 ∑ N i 个个体。i =1 M

以

Fi N i ∑ Fi / Mi =1

M

为各个个体的新的适应度，用比例选择方

法来随机确定下一代群体中还没有确定的个体。

挺好

3.3.6 排序选择 排序选择– 基本思想 对群体中的所有个体按其适应度大小进行排序，基于这个排序 来分配各个个体被选中的概率。

– 具体过程 对群体中的所有个体按其适应度大小进行降序排序。 根据具体求解问题，设计一个概率分配表，将各个概率值按上 述排列次序分配给各个个体。 以各个个体所分配到的概率值作为其能够被遗传到下一代的概 率，基于这些概率值用比例选择的方法来产生下一代群体。

– 关键问题 必须根据对所研究问题的分析和理解情况预先设计一个概率分 配表。 配表

挺好

3.3.7 随机联赛选择 随机联赛选择– 基本思想 每次选取几个个体之中适应值最高的一个个体遗传到下一代群 体中。

– 具体过程 从群体中随机选取N个个体进行适应度大小的比较，将其中适 应度最高的上体遗传到下一代群体中。 将上述过程复复M次，就可得到下一代群体中的M个个体。

– N的值 通常情况下，联赛规模N的取值是2。

挺好

3.4 交叉算子 交叉算子– 是指对两个相互配对的染色体按某种方式相互交换其 部分基因，从而形成两个新的个体。 主要方法，它决定 – 交叉运算是遗传算法产生新个体的主要方法 主要方法 了遗传算法的全局搜索 全局搜索能力。 全局搜索

配对策略– 随机配对，即将群体中的M个个体以

随机的方式组成 M/2对配对个体组。

研究内容– 如何确定交叉点的位置？ – 如何进行部分基因交换？

本文来源：https://www.bwwdw.com/article/6g71.html