辽宁工程技术大学毕业设计（论文）
5)便于遗传算法与经典优化方法的混合使用 6)便于设计针对问题的专门知识的知识型遗传算子 7)便于处理复杂的决策变量约束条件
c 符号编码方法
符号编码法是指个体染色体编码串中的基因值取自一个无数值含义、而只有代码含义的符号集如｛A,B,C?｝。
符号编码的优点是：1)符合有意义积术块编码原则
2)便于在遗传算法中利用所求解问题的专门知识 3)便于遗传算法与相关近似算法之间的混合使用
但对于使用符号编码方法的遗传算法，一般需要认真设计交叉、变异等遗传运算的操作方法，以满足问题的各种约束条件，这样才能提高算法的搜索性能。
综上所述，不同的编码方法具有不同的特点，真正有效的编码设计应根据各编码方法的特点，并结合实际问题和编码与遗传操作的关系来确定。 2)适应度函数
类似于生物学家使用适应度这个术语来度量某个物种对于生存环境的适应程度，在遗传算法中使用适应度这个概念来度量群体中各个个体在优化计算中有可能达到或者接近于或者有助于找到最优解的优良程度。适应度高的个体遗传到下一代的概率就大，反之则较小。度量个体适应度的函数就称为适应度函数。
遗传算法仅使用所求问题的目标函数值就可得到下一步的有关搜索信息。而对目标函数值的使用是通过评价个体的适应度来体现的。评价个体的适应度的一般过程是：首先对个体编码串进行解码处理后，可得到个体表现型；其次由个体表现型可计算出对应个体的目标函数值；最后根据最优化问题的类型，由目标函数值按一定的转换规则求出个体适应度。适应度函数基本上有以下三种[10]： a 直接法
以待求解的目标函数的转化为适应度函数，即： 若目标函数为最大化问题，有
Fit(f(t))?f(t) （4-3）
若目标函数为最小化问题，有
Fit(f(t))??f(t) (4-4）
15
基于遗传算法的PID控制器参数优化与仿真研究
这种适应度函数简单直观，但存在两个问题:其一是可能不满足常用的轮盘赌选择中概率非负的要求；其二是某些待求解的函数在函数值分布上相差很大，由此得到的平均适应度可能不利于体现种群的平均性能，从而影响算法的性能。 b 界限构造法 若目标函数为最小问题，则 ?0,其他Fit(f(x))???Cmax?f(x),f(x)?Cmax 若目标函数为最大问题，则 （4-5） ?f(x)?Cmin,f(x)?CminFit(f(x))???0,其他 （4-6） 式子中Cmin,Cmax分别为f(x)的最小和最大估计值。 这种方法是对第一种方法的改进，但有时存在界限值预先估计困难,从而不可能精确的问题。 c 保守估计法 若目标函数为最小问题 Fit(f(x))?1,c?0,c?f(x)?01?c?f(x) （4-7） 若目标函数为最大问题 Fit(f(x))?1,c?0,c?f(x)?01?c?f(x) （4-8） 这种方法与第二种方法类似，为目标函数界限的保守估计值。 在遗传算法运行不同阶段，有时还需对个体的适应度进行适当的缩放调整即适应度定标。常用的定标方法有：线性定标、乘幂定标、指数定标。 3）遗传算子 遗传操作的三个基本算子分别是选择算子、交叉算子和变异算子。 a 选择算子 遗传算法使用选择算子来进行优胜略汰操作：适应度较高的个体被遗传到下一代群体的概率较大；适应度较低的个体被遗传到下一代群体的概率较小；选择操作就是用来确定如何从父代群体中按照某种方法选取哪些个体遗传到下一代群体中的一种遗传运算。选择16
辽宁工程技术大学毕业设计（论文）
操作是建立在对个体的适应度进行评价的基础之上。选择操作的目的是为了避免基因缺失、提高全局收敛性和计算效率。 1) 比例选择 当使用比例选择算子进行操作时,如果个体适应度值越大则群体中的个体被选中的概率就越高。假设某群体规模M,其中的某个个体i适应度值大小为Fi，那么个体i 被选中的概率大小为 ： Pis?FiM ?Fi?1,?i?1,2...M?i （4-9） 由于是随机操作的原因，这种选择方法的选择误差比较大，有时甚至连适应度较高的个体也选择不上。如果某个体的个体适应度值过大,也有可能使算法过早收敛,致使运算后期算法的效率降低,搜索速度减慢。 2) 最优保存策略 当前群体中适应度最高的个体不参与交叉和变异运算，而用它代替本代群体中经过交叉、变异等遗传操作后所产生的适应度最低的个体[17]。 在遗传算法运行过程中，通过对个体的进行交叉、变异等遗传操作会不断产生新的个体。随着群体进化会不断产生优良个体。但是由于操作的随机性，有可能破坏当前群体中适应度最好的个体，会降低群体的平均适应度，且对遗传算法的运行效率、收敛性都有不利的影响，可以采用最优保存策略，避免这种不良影响。 其他的还有确定式采样选择，无放回随机选择，无放回余数随机选择，排序选择和随机联赛选择等。 b 交叉算子 两个相互配对的染色体按照某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是区别于其他进化算法的重要特征，在遗传算法中起着关键作用，是产生新个体的主要方法。交叉时首先对种群中的个体进行随机配对，以交叉概率决定是否进行交叉。其次在配对个体中随机设定交叉处，配对个体彼此交换部分信息。 1)单点交叉 在个体编码串中只随机设置一个交叉点，然后在该点相互交换两个配对个体的部分染色体。例如从群体中取两个个体, 其中冒号表示交叉点位置。 A: 1 0 1 :1 1 0
17
基于遗传算法的PID控制器参数优化与仿真研究
B: 1 1 1 ：0 0 1 交叉后形成新的个体
A’:1 0 1 : 0 0 1 B’:1 1 1 : 1 1 0
单点交叉的重要特点是：若相邻的基因座之间的关系能够提供较好的个体性状和较高适应度的个体适应度的话，则这种单点交叉操作破坏这种个体性状和降低个体适应度的可能性最小。
2)双点交叉和多点交叉
双点交叉和多点交叉是指在编码串中设置两个或多个交叉点，然后再进行部分基因交换。但是一般不太使用多点交叉算子，它有可能破坏一些好的模式。随着交叉点数的增多，个体结构被破坏的可能性也逐渐增大，这样很难有效地保存较好的模式，从而影响遗传算法的性能。
3)均匀交叉
均匀交叉是将种群中的个体部分按照相同概率进行交叉变换,然后获得两个新个体。 4)算数交叉
算数交叉是指将两个个体的线性组合而产生两个新的个体。为了能够进行线性组合运算，算数交叉的操作对象一般是由浮点数编码所表示的个体。
c 变异算子
变异是对群体中的个体串的某些基因座上的基因值作变动。在群体中所有个体的串范围内随机的确定基因座，以变异概率来对这些基因座的基因值用该基因座的其它等位基因来代替。变异运算只是产生新个体的辅助方法，但它也是必不可少的一个运算步骤，它决定了遗传算法的局部搜索能力，维持群体的多样性，以防止出现早熟收敛现象。交叉算子与变异算子的相互配合，共同完成对搜索空间的全局搜索和局部搜索，从而使得遗传算法能够以良好的搜索性能完成最优化问题的寻优过程。常使用基本位变异，即对个体编码串中以变异概率Pm随机指定的某一位或者某几位基因值做变异运算。 如原个体A：1 0 1 0 1 1 新个体 ：A’:1 0 1 0 1 0
其他变异操作方法包括均匀变异，边界变异，非均匀变异，高斯变异等。
4）运行参数 主要有个体编码串长度L、群体大小M、交叉概率Pc、变异概率Pm，终止代数G等。
a 个体编码串长度 L
18
辽宁工程技术大学毕业设计（论文）
使用二进制编码来表示个体时，L 的选取与所求问题的求解精度有关；使用浮点数编码来表示个体时，L与被优化的变量的个数相等；使用符号编码来表示个体时，L由问题的编码方式决定。
b 群体规模 M
定义群体中个体的数目，群体规模的确定受遗传操作中选择操作的影响很大。群体规模越大，群体中个体的多样性越高，算法陷入局部最优解的危险性越小，所以从群体的多样性考虑，群体规模应较大。但是群体规模太大则计算量增加会影响法效能，由于大多数适应度不高的个体会被淘汰，这会影响种群的形成，从而影响交叉操作。另一方面，群体规模太小，会使遗传算法的搜索空间分布范围有限，因而搜索有可能停止在未成熟阶段，引起未成熟现象，所以必须保持群体的多样性，群体规模不能太小。一般在实际应用中群体个体数取值范围为20—100。
c 交叉概率Pc
定义操作中个体产生交叉的概率。因为交叉是遗传算法中产生新个体的主要方法，所以交叉概率一般应取较大值。但若取值过大，又会破坏群体的优良模式，对进化运算反而不利；若取值过小，产生新个体的速度又较慢。一般建议取值范围是0.4—0.99，也可以使用自适应思想确定交叉概率。
d 变异概率Pm
定义每次遗传操作中个体产生变异的概率。变异概率取值过大，虽能产生出较多的新个体，但有可能破坏很多较好的模式，使遗传算法的性能近似于随机搜索法的性能；若取值太小，则变异产生新个体的能力和抑制早熟现象的能力较差。一般建议的取值范围为0.0001—0.1，也可以使用自适应思想确定变异概率。
e 迭代终止条件
经典的方法是设终止代数G，遗传算法运行到指定的进化代数之后就停止运行。一般取值范围是100—1000。但遗传算法是随机的，到达最大迭代次数不一定是最优解。现在的方法是大多利用某种判定准则，当判定种群已经进化成熟且不在有进化趋势时就可以终止算法的运行。
4.2.3 遗传算法的运算过程
步骤1、初始化 通过初始化从种群中随机选取M个个体产生初始群体P(0),设置进化代数计数器t以及最大进化代数G;
19