遗传算法笔记

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

1、211 基本遗传算法的构成要素(1) 染色体编码方法。(2) 个体适应度评价。这样，根据不同种类的问题，必须预先确定好由目标函数值到个 体适应度之间的转换规则，特别是要预先确定好当目标函数值为负数时的处理方法。(3) 遗传算子。基本遗传算法使用下述三种遗传算子选择运算使用比例选择算子；交叉运算使用单点交叉算子； 变异运算使用基本位变异算子或均匀变异算子。(4) 基本遗传舆法的运行参数。基本遗传算法有下述4 个运行参数需要提前设定： M：群体大小，即群体中所含个体的数量，一般取为20100。 T：遗传运算的终止进化代数，一般取为100500 Pc:交叉概率，一般取为0.40.99。 Pm:变异概

2、率，一般取为0. 00010.10需要说明的是，这4个运行参数对遗传算法的求解结果和求解效率都有一定的影响， 但目前尚无合理选择它们的理论依据。在遗传算法的实际应用中，往往需要经过多次试算后 才能确定出这些参数合理的取值大小或取值范围。2. 2 基本遗传算法的实现2. 2. 1 个体适应度评价为满足适应度取非负值的要求.基本遗传算法一般采用下面两种方法之一将目标函数 值f(x)变换为个体的适应度F(x)。方法一：对求目标函数最大值的优化问题，变换方法为c mm 为一个适当地相对比较小的数，它可用下面几种方；之一来选取。预先指定的 个较小的数。进化到当前代为止的最小目标函数值。当前代或最近几代群

3、体中的最小日初i函数值。方法二：对于求目标函数最小值的优化问题.变换方法为式小，cmx为一个适当地相对比较大的数，它可用下面几种方法预先指定的一个较大的数。进化到当前代为止的最大目标函数值。 当前代或最近几代群体中的最大日标函数值。2. 2. 2 比例选择算子选择算子是比例选择算子。所谓比例选择算子，是指个体被选中并遗传到下一 代群体中的概率与该个体的适应度大小成正比。比例选择算子的具体执行过程是：(1) 先计算出群体中所有个体的适应度的总和。(2) 其次计算出每个个体的相对适应度的大小，即为各个个体被遗传到下代群体 中的概率。(3) 最后再使用模拟赌盘操作(即0到1之间的随机数)来确定各个个

4、体被选中的次数。2. 2. 3 单点交叉算子单点交叉算子是最常用和最基本的交叉操作其子。单点交叉算子的具体执行过程如下。(1) 对群体中的个体进行两两随机配对。若群体大小为M,则共有M/2对相互配 对的个体组。其中X表示不大于x的最大的整数。(2) 对每一对相互配对的个体，随机设置某一基因座之后的位置为交叉点。若染色 体的长度为n贝哄有(n1)个可能的交叉点位置。(3) 对每一对相互配对的个体，依设定的交叉概率Pc在其文叉点处相互交换两个 个体的部分染色体，从而产生出两个新的个体。224 基本位变异算子 基本位变异算子是最简单和最基本的变异操作算子。对于基本遗传算法中用二进制 编码符号串所表示

5、的个体，若需要进行变异操作的某基因座上的原有基因值为0，贝变异 操作将该基因值变为1反之，若原有基因值为1，贝变异操作将其变为0。基本位变异其子的具体执行过程是：(1) 对个体的每一个基因座，依变异概率Pm指定其为变异点(2) 对每一个指定的变异点，对其基因值做取反运算或用其他等位基因值来代替， 从而产生出一个新的个体。23 基本遗传算法应用举例 由前述我们可以知道基本遗传算法是一个这代过程，它模仿生物在自然环境中 的遗传和进化机理，反复将选择算子、交叉算子、变异算子作用于群体，最终可得到问题的 最优解或近似最优解。虽然算法的思想比较单纯，结构也比较简单，但它却也具有一定的实 用价值，能够解决

6、一些复杂系统的优化计算问题。231 遗传算法的应用步骤 遗传算法提供厂一种求解复杂系统优化问题的通用框架，它不依赖于问题的领域 和种类。对一个需要进行优化计算的实际应用问题，一般可按下述步骤来构造求解该问题的 遗传算法。第一步：确定决策变量及其各种约束条件，即确定出个体的表现型x和问题的解 空间。第二步：建立优化模型，即确定出目标函数的类型(是求目标函数的最大值还是求 目标函数的最小值?)及其数学描述形式或量化方法。第三步：确定表示可行解的染色体编码方法，也即确定出个体的基因型x及遗传 算法的搜索空间。第四步：确定编码方法，即确定出由个体基因型X到个体表现型X的对应关系或 转换方法。第五步；确

7、定个体适应度的量化评价方法，即确定出由目标函数值f(x)到个体适 应度F(x)的转换规则。第六步：设计遗传算子，即确定出选择运算、交叉运算、变异运算等遗传算子的 具体操作方法。第七步；确定遗传算法的有关运行参数，即确定出遗传算法的M、T、Pc、Pm等 参数。由上述构造步骤可以看出，可行解的编码方法、遗传算子的设计是构造遗传算法 时需要考虑的两个主要问题，也是设计遗传算法时的两个关键步骤。对不同的优化问题需要 使用不同的编码方法和不同躁作的遗传算子，它们与所求解的具体问题密切相关，因而对所 求解问题的理解程度是遗传算法应用成功与否的关键。第三章 遗传算法的基本实现技术3l 编码方法在遗传算法中如

8、何描述问题的可行解，即把一个问题的叮行解从其解空间转换到遗传 算法所能处理的搜索空间的转换方法就称为编码。编码原则一(有意义积木块编码原则)：应使用能易于产生与所求问题相关的且具有 低阶、短定义长度模式的编码方案o编码原则二(最小字符集编码原则)：应使用能使问题得到自然表示或描述的具有最 小编码字符集的编码方案。311 二进制编码方法 二进制编码方法有下述一些优点：(1) 编码、解码操作简单易行。(2) 交叉、变异等遗传操作便于实现。(3) 符合最小字符集编码原则。(4) 便于利用模式定理对算法进行理论分析312 格雷码编码方法 二进制编码不便于反映所求问题的结构特征，对于一些连续函数的优化问

9、题等，也由 于遗传运算的随机特性而使得其局部搜索能力较差。为改进这个待性，人们提出用格雷码 (gray code)格雷码有这样一个持点：任意两个整数的差是这两个整数所对应的格雷码之间的海明 距离(Hamming Distance)。这个持点是遗传算法中使用格雷码来进行个体编码的主要原因。格雷码编码方法的主要优点是： ：1)便于提高遗传算法的局部搜索能力。：2)交叉、变异等遗传操作便于实现。 ：3)符合最小字符集编码原则。：4)便于利用模式定理对算法进行理论分析。313 浮点数编码方法 对于一些多维、高精度要求的连续函数优化问题，使用二进制编码来表示个体时 将会有一些不利之处。首先是二进制编码存

10、在着连续函数离散化时的映射误差。个体编码串的长度较短 时可能达不到精度要求；而个体编码串的长度较长时，虽然能提高编码精度，但却会使遗 传算法的搜索空间急剧扩大。其次是二进制编码不便于反映所求问题的特定知识，这样也就不便于开发针对问题 专门知识的遗传运算算子，人们在一些经典优化算法的研究中所总结出的一些宝贵经验也就 无法在这里加以利用，也不便于处理非平凡约束条件。所谓浮点数编码方法，是指个体的每个基因值用某一范围内的一个浮点数来表示，个 体的编码长度等于其决策变量的个数。因为这种编码方法使用的是决策变量的真实值，所以 浮点数编码方法也叫做真值编码方法。浮点数编码方法有下面几个优点：(1) 适合于

11、在遗传算法中表示范围较大的数。(2) 适合于精度要求较高的遗传算法。(3) 便于较大空间的遗传搜索。(4) 改善了遗传算法的计算复杂性，提高了运算效率。5)便于遗传算法与经典优化方法的混合使用。(6) 便于设计针对问题的专门知识的知识型遗传算于。(7) 便于处理复杂的决策变量约束条件。314 符号编码方法 符号编码方法是指个体染色体编码串中的基因值取自一个无数值含义、而只有代码含义的符号集。符号编码的主要优点是：(1) 符合有意义积木块编码原则。(2) 便于在遗传算法中利用所求解问题的专门知识。(3) 便 1遗传算法与相关近似算法之间的混合使用。但对于使用符号编码方法的遗传算法，一般需要认真设

12、计交叉、变异等遗传运算 的操作方法，以满足问题的各种约束要求这样才能提高算法的搜索性能。315 多参数级联编码方法一般常见的优化问题中往往合有多个决策变量。例如六峰值驼背函数(Six hump CamelBack Function)：f (J, y) = ( 4 一 2.1异+专)/ 十 q + ( - 4 + 4j?2) y1其实在我们前面的例子中己遇到过多参数编码的一种最常用和最基本的方法：将各 个参数分别以某种编码方法进行编码，然后再将它们的编码按一定顺序联接在一起就组成了 表示全部参数的个体编码。这种编码方法称为多参数级联编码方法。316 多参数交叉编码方法 多参数交叉编码方法的基本思

13、想是：将各个参数个起主要作用的码位集中在一 起，这样它们就不易于被遗传算子破坏掉。在前述多参数的级联编码方法中，各个参数的编码值集中在一 起，这样各个参数的 局部编码结构就不易被遗传算子破坏掉，它适合于备参数之间的相互关系较弱，特别是某一 个或少数几个参数起主要作用时的优化问题。而多参数的交叉编码方法特别适用于各个参数之间的相互关系较强、各参数对最优解 的贡献相当时的优化问题，因为在这种交叉编码方法中，用来表示各个参数值的二进制编码 的最高位被集中在了一起，它们就不易被遗传算子破坏掉，而这些最高位在表示各个参数值 时所起的作用最强这样就可以尽量地维持各参数之间的相互关系。3，2 适应度函数32

14、1 目标函数与适应度函数评价个体适应度的一般过程是；(1) 对个体编码串进行解码处理后可得到个体的表现型。(2) 由个体的表现型可计算出对应个体的目标函数值。(3) 根据最优化问题的类型，由目标函数值按一定的转换规则求出个体的适应度 对于求最大值的问题，作下述转换：(3-6)f(X) +C餉 if f (X) + Cmin0IOtif f (X) 4-式中，为一个适当地相对较小的数。对于求最小值的问题，作下述转换；32， 2 适应度尺度变换这时产生新个体作用较大的交叉算子就起不了什么作用，因为相同的两个个体不论在何处进行交叉操作都永远不会产生出新的个体，这样就会使群体的多样性降低，容易导致遗

15、传算法发生早熟现象(或称；早期收效)，使遗传算法所求到的解停留在某局部最优点上。我们希望在遗传算法运行的后期阶段，算法能够对个体的适应度进行适当的放大，扩 大最佳个体适应度与其他个体适应度之间的差异程度，以提高个体之间的竞争性。这种对个体适应度所做的扩大或缩小变换就称为适应度尺度变换(Fitting Scaling)。目 前常用的个体适应度尺度变换方法主要有三种：线性尺度变换、乘幂尺度变换和指数尺度变 换。33 选择算子 选择操作建立在对个体的适应度进行评价的基础之上。选择操作的主要目的是为了避 免基因缺失、提高全局收敛性和计算效率。331 比例选择332 最优保存策略最优保存策略进化模型的具体操作过程是：(1) 找出当前群体中适应度最高的个体和适应度最低的个体。(2) 若当前群体中最佳个体的适应度比总的迄今为止的最好个体的适应度还要高则以 当前群体中的最佳个体作为新的迄今为止的最好个体。(3) 用迄今为止的最好个体替换掉当前群体中的最差个体。 最优保存策略可视为选择操作的一部分。该策略的实施可保证迄今为止所得到的最优个体不会被交叉、变异等遗传运算所破坏，它是遗传其法收敛性的一个重