免疫遗传算法的PID控制器设计 第二章 遗传算法概述
组成的染色体或者个体。执行过程中，编码问题很重要，它直接影响接下来的遗传操作。
编码的方法大致可分为三类：二进制编码方法，符号编码方法以及浮点数编码方法。本文运用二进制编码方法。二进制编码用二进制字符串（由0，1组成）来表示所求解的优化问题参数。若优化问题有m个参数对应m个一定长度的字符串，将m个字符串联接成一条染色体，称为个体，这就是编码的过程。在遗传算法中，遗传算子的操作对象是由字符串构成的染色体，而不是优化问题的各参数。由于遗传算法中的杂交和突变都是在字符串上进行的，所以所谓的整数或者实数表示也一定要转化为数位形式。例如一个变量的形式是实数，其范围是0～1，而要求的精度是0.001，那么可以用10个数位表示：0000000000表示0，1111111111表示1，那么0110001110就代表0.389。
表2.1 二进制编码的优缺点
二进制编码的优点
1 编码，解码操作相对简单。
2 交叉，变异等遗传操作容易实现。 3 利用模式定理（二进制编码基础）容易对算法进行理论分析。
二进制编码的缺点
1 连续函数离散化有映射误差。
2 不能直接反映出所求问题的本身结构特征。
2.1.3 初始种群
遗传操作是对众多个体同时进行的，这些个体组成群体。优化问题参数经二进制编码后，必须产生一个初始群体。如何确定群体规模m是初始种群设定的关键。如何设定，方法如下：
1．设法把握最优解所占空间在整个问题空间中的分布范围，在此分布范围内设定初始群体。
2．先随机产生一定数目的个体，挑出最好的那些个体，放入初始种群中。在不断迭代的过程中，积累优秀个体数达到预定规模。遗传优化的最终结果以及遗传算法的执行效率受群体规模影响很大。过小或者过大都会不理想，一般m会取10-200之间[18]。 2.1.4 适应度函数
适应度函数又称作评价函数，在遗传算法中使用适应度（Fitness）这个概念来度量群体中各个个体在优化计算中能达到或接近于或有助于找到最优解的优良程度。适应度较高的个体遗传到下一代的概率较大；适应度较低的个体相对较小。度量个体适应度的函数叫做适应度函数（Fitness Function）。 评价个体适应度的过程如下：
6
免疫遗传算法的PID控制器设计 第二章 遗传算法概述
Step1：得到个体的表现型（对个体编码串进行编码处理后）； Step2：计算出对应个体的目标函数值（根据个体的表现型）；
Step3： 由目标函数值按照一定转换规则求出个体的适应度（根据最优问题的类型）。
遗传算法在求解函数极值问题时往往以适应度函数为依据。其确定一般分为如下情况:
1．求函数u(x)最大值时，
?u(x)?C?(u(x)?Cmin?0)f(x)?? min (2.1)
?0?(else)2．求函数g(x)最小值时，
?C?g(x)?(g(x)?Cmax) f(x)??max?0?(else) (2.2)
式(2.1)中，Cmin 可以是合适的输入值，或是当前一代或前K代中的g(x) 的最小值，也可以是群体方差的函数。式(2.2)中，Cmax可以是一个合适的输入值，或是进化过程中g(x) 的最大值或当前群体中g(x) 的最大值。 2.1.5遗传算子
遗传算法的遗传操作包括三个基本遗传算子(genetic operator): 选择算子(selection operator)、交叉算子(crossover operator)和变异算子(mutation operator)
1. 选择算子(selection operator)
选择（Selection）又称复制（Reproduction），即在群体中找出适应度强的个体的过程。遗传算法使用选择算子来对群体中的个体进行优胜劣汰操作：选择的的标准就是个体适应度的大小，适应度强，留下的概率大，反之留下的概率小。这样一个过程就会使个体的性状不断的接近最优解。
选择算子在遗传算法中非常重要，一旦确定不当会使个体的适应度趋同，难以维持进化过程，甚至会使整个发展方向被一些适应度大的个体误导，失去种群多样性，产生早熟问题。本文的之后章节将会对早熟问题的解决办法做进一步的分析。
表2.2：部分选择算子以及特点
[19]
。
选择方式 轮盘赌选择 随机竞争选择 柔性分段复制
优势
选择误差相对来说偏大 性能好于轮盘赌选择
需要选择参数并可以有效防止基因的缺失。
7
免疫遗传算法的PID控制器设计 第二章 遗传算法概述
无回放随机选择 选择误差有所降低，但操作麻烦。
关于选择操作算子，很多学者都提出了自己的看法，所用的原理不尽相同，以上所介绍的只是其中的一部分选择操作算子。虽然轮盘赌选择的选择误差较大，但是该方法便于理解与掌握，对于不是要求很高的控制系统寻优来说仍然能够达到预期的效果，所以本文选用的是轮盘赌选择操作算子。
轮盘赌选择又叫做蒙特卡罗(Monte Carlo)选择法。设群体规模为m，其中个体i 的适应度值为fi，则i被选择的概率Psi为:
M Psi?fi?fi?1i (2.3)
概率Psi 反映了个体i的适应度在整个种群的个体适应度总和中所占的比例。个体适应度越大，其被选择的概率就越高，反之亦然[18]。
2. 交叉算子(crossover operator)
在生物的自然进化过程中，两个同源染色体通过交配和重组，形成新的染色体，从而产生出新的个体或者物种。交配重组是生物遗传和进化过程中的一个主要环节，模仿这个环节，遗传算法中使用交叉算子来产生新的个体。交叉（crossover）又称作重组（Recombination），是按较大的概率从群体中选择两个个体，交换两个个体的某个或某些位。遗传算法中所说的交叉，是指基于两个配对染色体相互交换一部分基因，进而形成了两个新的个体。
产生新个体的主要方法便是交叉运算，它是遗传算法的异它性特征，在遗传算法的过程中举足轻重。
表2.3：部分交叉操作以及特点
交叉形式 单点交叉 两点交叉 均匀交叉 多点交叉 启发式交叉
特点 标准遗传算法成员
使用较多 每一位以相同概率交叉
交叉点大于2 应用领域知识
[1]
适用条件 适用符号编码 适用符号编码 适用符号编码 适用符号编码 适用序号编码
本文中只涉及单点交叉，两点交叉和多点交叉的情况，现就这三种情况讨论如下：
单点交叉(one-point crossover)
单点交叉是指在个体串中随机设定一个交叉点。交叉时，互换该点前面或者后面的两个个体的部分结构，产生两个新个体:
8
免疫遗传算法的PID控制器设计 第二章 遗传算法概述
个体 A：1001 ┊ 111 →1001000 新个体 A' 个体 B：0011 ┊ 000 →0011111 新个体 B'
在第4和第5个基因座之间设置交叉点。交叉时，互相交换该交叉点后的两个个体的部分码串，从而得到新的个体A′ 和B′。由于交叉点是随机的，对于一个长为L的染色体，可能会实现L-1种不同交叉结果出来。
两点交叉(two-point crossover)
两点交叉随机设定两个交叉点。两个交叉点之间的码串相互交换，从而产生两个新个体:
个体 A：10┊110 ┊11 → 1001011 新个体 A' 个体 B：00┊010 ┊00 → 0011000 新个体 B'
对于两点交叉而言，由于交叉点是随机的，对于长为L的染色体，可能实现(L-2)(L-3)种不同交叉结果。
多点交叉(multi-point crossover)
多点交叉实质上是一点交叉和两点交叉的演变。用cp来表示交叉点数，当cp=1和cp=2时，分别表示一点交叉和二点交叉。由于多点交叉影响遗传算法的在线和离线性能，实际应用中很少被采用。
交叉概率Pc过低，遗传算法将陷入迟钝状态，Pc过高虽能增强搜索能力，但同时也会破坏高性能模式。一般Pc取0.25~0.90之间。
2. 变异算子(mutation operator)
生物遗传进化中，偶然的复制差错会出现在细胞的复制环节中，产生的后果便是
基因发生变异，产生新的个体，产生新的性状。
生物遗传和进化的过程为我们提出遗传算法提供了现实依据。在通常的情况下，变异（Mutation）概率是很小的，其过程就是对个体的编码串上的某个（或者某些）位值进行改变，如“0”变成“1”，或者反过来，进而产生新的个体。
有些学者对变异算法持怀疑态度，认为变异算法所取得的效果完全可以通过选择交叉来实现，本文认为从遗传算法过程中产生新个体的能力方面来说，变异本身是一种随机算法，通过和选择交叉算法的结合，能避免由于选择和交叉运算造成的某些信息的损失，从而保证遗传算法的有效性。
变异算子的作用有两个：其一可以对遗传算法局部搜索能力的改善起到关键作用。其二可以对群体的多样性的维持，防止出现早熟现象发挥很大的作用。
低概率的变异可防止群体中重要的、单一基因的丢失，具有很高概率的变异将会使遗传算法趋向于纯粹的随机搜索，因而一般变异概率Pm取0.001~0.02之间。
9
