浅析基于排序的LDF改进遗传算法

作者：徐一凡

    遗传算法因为具备智能性、并行性，并不依赖问题的内部机理，能在多数可行解中根据特定要求搜索最优解，非常适合解决复杂的非结构化、非线性、非规律性的问题。但算法本身也存在一定的问题，针对这些问题，国内外学者对此进行了探索，提出了很多改进方法，大致包括：编码方式的改进、适应度函数的改进、算子的自适应改进以及与不同分布函数的结合应用等。本文根据前人提出的研究与改进方法，着重研究了算法收敛问题方面的改进，并在仿真实验部分测试了改进的效果，对比算法为PCCOs（parent - centric crossover operators）遗传算法。实验结果表明，该算法切实可行，仿真结果达到了预期要求。

1遗传算法简介

    遗传算法是一种随机性的全局优化算法，它不但具有较强的全局搜索功能和求解问题的能力，还具有简单通用、鲁棒性强、适于并行处理等特点，是一种较好的全局优化搜索算法。其核心内容按操作顺序一般分为以下5点。①参数编码。根据问题的复杂程度或者适应度选择合适的编码，常用的编码方式有二进制编码、格雷编码、实数编码等。②适应度函数。适应度是由目标函数变换而来，适应度的尺度变换是对目标函数域的某种映射变换，具有评价个体适应环境能力的作用，是选择操作的依据。③选择操作。遗传算法中的选择操作是在对个体的适应度评价的基础上，确定选取适当的个体复制到下一代中的方法，可以提高全局的收敛性，缩短整体搜索时间。常用的选择操作有轮盘赌选择法、排序选择法、联赛选择法等。④交叉操作。交叉操作是遗传算法中产生新个体的主要方式，也是区别于其他智能算法的重要特点，其作用是组合出新的个体，在解空间内进行有效搜索。常用的交叉算子有单点交叉、双点交叉、一致交叉、均匀交叉、算术交叉、顺序交叉和周期交叉等。⑤变异操作。变异是指将根据变异算子来替代个体编码中的某些基因值，以此产生一个新的个体。遗传算法中的变异运算是产生新个体的辅助方法，其目的是使遗传算法具有局部的随机搜索能力和保持群体的多样性。常用的变异算子有基本位变异、均匀变异、高斯变异等。这5部分对算法的优劣起着关键性的作用，正确的改进可以大大提升搜索到最优解的概率，并缩短搜索的时间；而不恰当的改进则会阻挠搜索到最优解的概率和效率。

2基于排序的LDF改进遗传算法

    如同大多数智能算法，遗传算法具有两个较为明显的收敛性问题：一是容易出现早熟，过快收敛于局部最优解；二是后期收敛速度过慢以及收敛结果不稳定的问题。针对这些问题，本文在采用实数编码的前提下，对标准遗传算法中的适应度函数以及交叉算子两部分进行了改进。

2.1适应度函数

    个体通过适应度函数可以得出其在种群中的地位，这将直接影响在下一代种群中出现的概率。传统的遗传算法中的适应度函数与目标函数呈线性关系，甚至一些简单的模型可以直接用目标函数作为适应度函数。但这种做法存在一些缺点，一是在算法的前期最大适应值与最小适应值很可能相差很大，很容易淘汰掉很多含有优秀基因片段的个体，而使得前期种群多样性遭到破坏；二是在算法后期个体间适应值的差异已经很小，使得遗传算法搜索全局最优解的能力下降。

    针对这些问题，前人也提出了各种改进方法，典型的有梯度改进遗传算法、基于约束区域的动态遗传算法等。梯度改进遗传算法考虑了函数在搜索点的函数值及其变化率，并将该信息加入适应度函数；基于约束区域的动态遗传算法将遗传算法的全局搜索和约束区域神经网络模型的局部搜索结合起来，使用神经网络确定动态遗传算法的适应度函数。但以上算法只考虑了局部最优解问题以及整体收敛速度问题，未考虑到不同时间段算法的选择压力变化问题。针对这一问题，在两者的基础上，引入了一种基于排序的适应度函数。

首先，将目标函数作为中间函数，把个体代入目标函数中fi=J（xi），i =1，2…，，m，其中m为种群规模，再将工按照从大到小进行排列得到一个序列{f}．，其中f i=max{f,}，以此类推；然后，作映射fi_x；，i =1，2…．，m，得到一个基于适应值大小排列的{xi}，i =1，2…，，m；最后代人公式，得到每个个体的基于排序的适应值。

式中：SP为选择压力，本文取2；m为种群规模。

    这样改进的好处在于可以在算法前期极大地减小个体之间适应度的差异，以减小选择压力，确保前期种群的多样性，从而避免过早陷入局部最优解；同时，在算法后期相对于标准遗传算法增大了选择压力，间接加快了算法整体收敛速度。

2.2交叉算子

    遗传算法中的交叉运算，是指将两个进行配对的染色体按交叉算子互相交换其部分基因，形成两个新的个体。交叉运算在遗传算法中起着关键的作用，也是遗传算法区别于其他智能算法的重要特征。常用的交叉算子有单点交叉、双点交叉、一致交叉、均匀交叉、算术交叉、顺序交叉和周期交叉等。对于交叉算子的改进，典型的有多亲遗传算法、自适应杂交算子遗传算法等。多亲遗传算法是一种利用了群体中心交叉方法来改进算子的遗传算法，并能将其应用到数据聚类等相关问题；自适应杂交算子遗传算法则是提出一种基于进化代数和个体适应值的交叉算子，使交叉操作向有利于算法收敛的方向进行。多亲遗传算法虽然涉及到与函数分布有关的指数型增长或是减少问题，但它的前提是必须满足一定的假设条件；而自适应杂交算子遗传算法是根据进化代数来直接修改适应度较小的个体，虽然结论表明自适应性良好，但修改后的个体有可能超出可行域。

    针对以上问题，本文采用了将拉普拉斯函数与交叉算子相结合的拉普拉斯交叉算子。经改进后，该算子综合了两者的优点，既能利用函数分布特性来满足算法自适应性，同时产生的后代也仍然在其可行域内，回避了大多数情况下算子与函数结合后可行域变化的问题。

拉普拉斯的密度函数：

拉普拉斯的分布函数：

式中：a为位置参数；b为尺度参数。

    当a=0时，如b越接近0，中心附近的父代产生后代的概率较高；如b越接近1，则离中心较远处的父代产生后代的概率增大。

拉普拉斯算子交叉后的后代：

  其思想来源于中间重组交叉算子和拉普拉斯分布函数。B由以下公式得出：

式中：p通过反转拉普拉斯分布函数得到；M为服从0~1之间的均匀分布的随机数。同时，为了使结果不超出仿真实验中轧钢精轧机组的实际可行域，需要规定u的取值必须大于

    拉普拉斯分布函数与交叉算子结合的好处在于：可以通过改变a的取值来适应不同的具体实例，具有一定的校正作用。通过改变b的取值可以影响在解空间内搜索的整体倾向性：b值越大则搜索的结果越集中，b值越小则搜索的结果越松散。因此，需要调整适当的b值使算法在前期相对松散，以保持种群的多样性，并在后期相对集中以加快算法的收敛速度并保持收敛的稳定性。该算子也具有自适应性和一定的跳出性。根据拉普拉斯分布函数的特性，彼此接近的父代更倾向于产生彼此接近的子代，相互远离的父代更倾向于产生彼此较远的子代，产生的子代也更倾向于在父代附近，大大减少了收敛过快或者过早陷入局部最优解的情况。在陷入局部最优解的情况下，改进后的算子在不超出整体可行域的前提下具有一定的概率跳出该局部极值，重新在解空间内搜索全局最优解。为证明该算子的可行性，下文将对轧钢热连轧精轧机组进行仿真模拟。

3仿真实验

    本文使用了从现场采集的数据，用基于排序的LDF改进遗传算法对热连轧精轧机组负荷分配进行优化计算。同时，为了对比其效果，本文将比较标准遗传算法、只改进交叉算子的LDF遗传算法、基于排序的LDF改进遗传算法以及PCCOs遗传算法。

精轧机组仿真模型中的目标函数为：

    实验钢种为Q235，来料宽度Bo =1 535 mm，来料厚度Ho =36.7 mm，成品厚度为5.7 mm，粗轧出口温度TRC =10 670 cC，精轧机组出口温度TFC =8 911℃，目标凸度CR。=0.016  mm，机架数n=7。实验中，算法的结构参数为：种群数大小M= 500，最大遗传代数T= 200，交叉概率P。=0.9，变异概率Pm =0.01，改进交叉算子中a=0，6=0.1。

表1是各遗传算法优化负荷分配的结果，包括各机架的轧制力F．—F，以及目标函数值．，。在符合轧制规程的情况下，目标函数值-，越小，表明总体负荷分配就越合理。

图1为各算法的收敛曲线，本文采取的模型中共有7个机架。实验表明，编号越靠后的机架，收敛速度相对越慢。为使结果具有代表性，该收敛曲线是取第7个机架的变动值。

    从仿真结果可以看出，图1(a)中的标准遗传算法几乎很快就陷入了局部最优解，收敛速度非常快，且不能跳出搜索到的局部最优解；而图1(b)中的只改进交叉算子的LDF遗传算法，搜索的范围明显大于标准遗传算法，并有明显的跳出局部最优解，但可以看出，其后期稳定性并不是很好；图1(c)中，改进了适应度函数，大大提高了前期种群的多样性，搜索范围再次增大，且有多次跳出局部最优解的过程，但可以看出，即使在接近收敛时，仍会有小范围的跳出最优解，只是其很快又收敛到最优解的过程，直至最后完全收敛；图1(d)采用PCCOs遗传算法，可以看出算法前期多样性很好，但却陷入局部最优解而无法跳出，收敛速度则适中。由以上分析可以看出，基于排序的LDF改进遗传算法得出的结果优于其他3种遗传算法：在符合实际生产要求的前提下，保证了算法前期的多样性，以及后期的收敛速度与稳定性，避免了出现前期陷入局部最优解以及后期收敛速度较慢等问题。

4结束语

本文针对传统优化算法和标准遗传算法不能有效解决高维数据建模的问题，通过将适应度函数进行基于排序的自适应改进，并将拉普拉斯分布函数与交叉算子相结合，提出了基于排序的LDF改进遗传算法。基于排序的LDF改进遗传算法针对遗传算法的多种收敛性问题，既保证了算法前期的多样性，又保证了算法后期的收敛速度与稳定性，解决了大多数遗传算法过快收敛至局部最优解，以及后期收敛速度过慢与不稳定等问题。该算法成功应用于轧钢热连轧精轧机组的负荷分配模型。通过仿真实验的对比结果可知，该算法切实可行，在遗传算法的收敛性问题方面有了很大的改善。

5摘要：针对高维数据建模过程中常见的非线性复杂问题，使用遗传算法进行全局寻优。考虑到标准遗传算法在搜索过程中存在的多种收敛性问题，提出基于排序的拉普拉斯分布函数( LDF)改进遗传算法。该算法针对性地改进了遗传算法的多种收敛性问题，解决了遗传算法过快收敛至局部最优解以及后期收敛速度过慢等问题。根据实际生产数据，对轧钢精轧机组进行了仿真模拟，仿真实验结果表明了该算法切实可行，在保证了优化效果的同时，也保证了算法的总体收敛速度和稳定性，具有良好的应用前景。