遗传算法非线性方程组的研究范文

《电子科技杂志》2014年第五期

1遗传算法求解非线性方程组的改进

1.1搜索空间方面的改进搜索空间是遗传算法求解非线性方程组中由定义域D决定的一个或多个范围。搜索空间的大小，在一定程度上决定了求解的效率。曾毅［6］提出了一种将种群中的个体按照适应值从大到小排列，根据前N位个体变量的对应二进制编码最高位与最优解对应的二进制编码的最高位是否相同的情况，对搜索空间进行缩小和移动的方法。该方法使得每个变量对应的二进制编码长度无需过长，便可求出高精度的解。成媛媛等提出了根据历代最优解将搜索区间不断划分成较小的区间，不断在各个小的搜索区间递归地调用动态自适应遗传算法，直到达到精度要求或小区间宽度为零停止的方法。这一方法较好地克服了传统方法的局限性，能够在较大的初始区间上以概率为1搜索到区间内的全部解，并能较好地实现并行计算，大幅提高了一般遗传算法求解非线性方程组的收敛速度和稳定性。排新颖等提出了一种梯度的变异步长，即在迭代开始时使用大的步长来进行全局寻优，在后期基本确定真正解的区间时，采用较小的步长进行局部细化搜索。从上述文献来看，在搜索空间方面的改进，主要以动态缩小搜索空间等为主。缩小了搜索空间，意味这提高了求解的速度。因此，这些改进将是对基本遗传算法求解非线性方程组的一种有效补充。

1.2编码方面的改进综上所述，在基本遗传算法求解非线性方程组的过程中，采用了二进制编码。其在程序上易于实现，但实践发现，该编码也带来了编码和解码误差等问题。因此，曾毅，彭灵翔［10］均提出了在求解过程的编码环节使用实数编码来替代二进制编码，从而省略了复杂的编码和解码过程。实数编码虽使得设计和分析难度增加，但通用性较好，可方便地表示范围较大的数，便于在较大的空间进行搜索，同时也改善了遗传算法的计算复杂性，提高了运算效率。传统二进制编码存在Hamming悬崖问题。对于二进制编码方法表示的个体，变异操作有时虽只是一个基因座的差异，而对应的参数值却相差较大。但若使用格雷码来对个体进行编码，则编码串之间的一位差异，对应的参数值也只有微小的差别。这就相当于增强了遗传算法的局部搜索能力，便于对连续函数进行局部空间搜索。因此AngelFernandoKuri－Morales采用格雷码，取得了较好的使用效果。

1.3传算子方面的改进在使用遗传算法求解非线性方程组时，一般会使用到选择、交叉和变异3个算子。选择算子一般通过赌轮法，交叉和变异操作一般采用根据经验所得的固定概率。罗亚中等在算子设计时以联赛竞争算子为选择算子，该算子可直接通过比较个体的目标函数值完成操作，因此该文的遗传算法适应度函数直接选择为优化目标函数。文中采用了最优保存策略，即当前群体中最优个体不参与交叉运算和变异运算，而是用其来替代本代群体中经过交叉、变异操作后所产生的最差个体。胡小兵等通过设计特定的交叉概率和变异概率函数，实现了交叉概率Pc和变异概率Pm的动态改变，从而增加求解过程中算法的进化能力和收敛速度。田巧玉等采用了启发式交叉的方式，使用参数“Ratio”指定子辈离较好适应度的父辈有多远。如:父辈是parent1和parent2，而parent1有较好的适应度，则启发式交叉生成的子辈如下child=parent2+Ratio*(parent1－parent2)(4)该文中还采用了Gaussian变异算子。此变异算子在进行变异操作时，将一正态分布、具有均值的随机数加入到父向量的每一项，替换原有的基因值。该Gaussian变异算子由两个参数“Scale”和“Shrink”决定。

针对采用非线性排序，排序的结果通常易陷入局部解。徐红提出了设置参数r，将适应值差别因素以r的比例加入到选择中，能改善搜索性能。参数r的设计及由此得到的交叉概率p''''如下交叉前排序的作用使相邻个体的适应度差别最小，特性相对集中。即采用先排序后交叉可能带来两种效果:(1)加快收敛速度。(2)形成未成熟收敛。希望出现的是前一种情况，因而在搜索初期采用交叉前排序的操作以期提高搜索效率。彭灵翔等在变异算子上使用了最佳个体保留算子和灭绝与移民算子。采用最佳个体保留算子是一种常见的做法，可将有最好适应度的染色体群作为种子传到下一代。灭绝与移民算子在当交配池中的染色体几乎相同时，或最佳个体的适应度在一定代数内的增幅小于门槛值时起作用。灭绝与移民过程一般分为两部分，开始将最佳染色体之外的染色群全部灭绝。然后移民产生Np－1个新的染色体。移民过程是:从第2个到Np/2个染色体用产生初始种群的方法产生父辈染色体。其余染色体用最佳适应度的染色体通过变异产生。综上所述，对于算子的改进，主要采用动态变化来替代固定概率的方式。无论哪种改进，均以加快收敛速度和防止早熟为主要目的。从各文献提供的实验数据来看，均取得了一定的效果。

2混合遗传算法求解非线性方程组

混合遗传算法求解非线性方程组主要是通过遗传算法与其他算法相结合等手段来求解的。

与经典迭代方法的混合遗传算法中的杂交算子和变异算子能在全变量空间内搜索方程组的解，经典迭代方法能在收敛点附近局部细致地搜索解。若能将两者混合，有可能发挥好两类算法各自的优势而取得更好的求解效果。目前文献中主要提出了两类混合策略。(1)将经典迭代方法作为算法的一个遗传算子。赵明旺采用牛顿迭代算法与遗传算法结合的混合算法求解非线性方程组，其混合策略是:对子代群体中每个个体以概率Pn进行牛顿算子迭代搜索，产生的新迭代值取代父代加入子代群体。该文认为确定牛顿算子概率Pn的大小需考虑的因素为:1)所求解的非线性方程组牛顿法迭代过程的收敛性。若其迭代过程收敛较快，则相应的Pn可取较小值。否则，则取较大值。2)预定的繁殖代数。若预定的繁殖代数较大，则相应的Pn可取小一些。否则，取大一些。

进一步地，赵明旺在文献中将上述思想推广运用至求解相容非线性方程组问题，即求解方程数与变量数可能不一致的情况。罗亚中等，屈颖爽均提出了将拟牛顿法与遗传算法相结合的混合算法求解非线性方程组。文献依据自适应混合算子概率Pn对群体利用拟牛顿法进行局部搜索，此文设计了两类混合算子:拟牛顿迭代混合算子和Powell混合算子，并进行了分析比较。拟牛顿混合算子的构造方法是:以被选中个体的染色体为初始点进行拟牛顿迭代操作，若算法收敛则以收敛点作为个体新的染色体，若不收敛则不改变个体的染色体。Powell混合算子的构造方法是:以个体的染色体为初始点进行Powell寻优计算，以优化结果作为个体新的染色体。而文献的中心思想是只对每一代的最优个体利用拟牛顿法进行精细局部搜索。其文中认为自适应混合算子概率Pn应该随着进化的增加而变大，最后趋近于一个常数P0，因此提出了如下公式其中，T为遗传算法中设置的最大代数;t为当前进化代数;常数P0∈(0，1］反映了局部强搜索算子对每个个体的最大可能作用程度。P0大则混合算子对遗传算法搜索空间的局部开采愈充分，但相应的计算成本愈大，此文选择P0=0.10。屈颖爽将知名的拟牛顿法—BFGS方法与遗传算法进行混合，其混合策略与赵明旺的一致，即对子代群体中每个个体以概率Pn进行拟牛顿算子迭代搜索产生的新迭代值取代父代加入子代群体。值得注意的是此文利用有限Markov理论建立了基于基本遗传算法与BFGS算法的混合算法的全局收敛性定理，即证明了保留当前最好解的混合算法收敛到全局最优解。王鹏进一步改进了屈颖爽的工作，主要体现在两个方面:(1)拟牛顿迭代步骤中，首先计算每个体的适应值，从中选择性能好的个体按一定的概率进行拟牛顿迭代。(2)对个体的拟牛顿迭代仅进行一次，在取得良好效果的同时节省了计算量。排新颖等考虑将梯度法与遗传算法混合，其主要思想是用梯度对最优个体进行局部寻优。选择的下降方向是待优化函数负梯度方向，设置一个步长L，在当前点进行局部寻优:若寻优后的函数值小于原来函数值的λ(λ＜1)倍，则寻优成功，更新当前个体，否则L=Lμ，直到L小于一个设定的值。

曹春红等将几何约束问题转化为非线性方程组的形式，并用牛顿迭代算法与遗传算法结合的混合算法求解，取得了较好的效果，其混合策略与赵明旺一致。周丽等提出了一种混合小生境遗传算法与拟牛顿算法求解非线性方程组的新方法，其混合策略与罗亚中等一致。对于由小生境遗传算法产生的一代种群，除最优个体外以一定的概率Pn选择其中的个体采用拟牛顿法进行局部寻优，如果寻优后的个体适应度值高于寻优前的适应度值，以优化的结果替换寻优前的个体，否则说明此个体不收敛，不进行替换操作。

3采用经典迭代方法进行求解

C.L.Karr等提出了一种求解非线性方程组的混合算法，此法中遗传算法主要为牛顿迭代算法提供好的初值。此文以求取Gauss－Legendre求积公式节点与系数形成的非线性方程组为典型例子，说明了牛顿迭代算法对求解此类方程组时对迭代初始值高度敏感，而混合算法的求解效果相当不错。田巧玉等在实现遗传算法与拟牛顿法相结合的思路是:在应用遗传算法进行优化设计的基础上，采用拟牛顿法进行二次优化，将获得的结果作为最优的设计结果，即首先运行遗传算法，找到最优点附近的一个点，将它作为拟牛顿法的初始点，以找到目标函数的最小值。此文给出了遗传算法迭代终止条件有两个:一是进化到指定的最大代数;另一个是适应度限，即当前代的最佳适应度值小于或等于规定的值时就停止。吴国辉等考虑到遗传算法全局群体搜索能力及该算法在起始搜索阶段速度非常快的特点，提出先用遗传算法进行n步迭代，直至其收敛结果满足预期要求，进入拟牛顿法的收敛域之内，然后将遗传算法迭代结果作为拟牛顿法迭代初始值继续迭代至精确解。此文对遗传算法迭代的控制办法是当前群体平均适应度小于等于预先设定的精度值。

3.1与其他智能算法的混合遗传算法是模仿自然选择和遗传机制的一种智能优化算法，研究者已将其与其他智能算法如模拟退火算法等进行混合，或者融入如量子计算原理、生物免疫思想等以构造出更具优势的新的智能算法。

3.2遗传退火算法模拟退火算法是由Metropolis等基于热力学的退火机制提出来的一种对退火过程进行模拟的算法。遗传算法具有较强的全局搜索能力但容易陷入早熟，而模拟退火算法具较强的局部把握能力，但全局搜索能力不足。因此对两者取长补短的遗传退火算法应运而生，并成功用于全局优化问题的求解。付振岳等将遗传退火算法进一步加以改进并应用到含有超越函数的非线性方程组的求解。

3.3量子遗传算法

量子遗传算法由Narayanan等人最早提出的，并经Han等人发展的一种基于量子计算原理的概率优化方法，其用量子位编码来表示染色体，用量子门作用和量子门更新来完成进化搜索，具有种群规模小、全局寻优能力强的特点，已成功用于求解TSP与0－1背包等问题，获得了比传统遗传算法更好的效果。杜娟等提出了一种基于混合量子遗传算法的非线性方程组求解方法。为克服量子遗传算法的求解精度低和加强局部搜索能力，采用拟牛顿法作为一个强局部搜索算子，把量子遗传算法的寻优结果作为拟牛顿法的初值，取得了较好的效果。徐红提出了一种改进量子遗传算法求解非线性方程组的新方法，结果表明此法具有较高的收敛可靠性及较高的精度，对于非线性方程组求解问题具有良好的适应性，特别是一些很难求解的方程组，利用此方法求解更有意义。

3.3免疫遗传算法免疫遗传算法是近年来基于生物免疫机制提出的一种新的智能计算算法，其将生物免疫系统的学习、记忆和多样性的特点引入遗传算法。由于兼顾了搜索速度、全局搜索能力和局部搜索能力，免疫遗传算法正成为优化设计领域的研究热点之一。王景芳等提出了一种烃类蒸汽转化反应器物料衡算的非线性方程组的免疫遗传算法求解方法，取得了良好的效果。该算法由于在遗传算法的基础上引入了高斯变异和基于抗体浓度的更新策略调节机制，能有效地保持抗体的多样性，从而避免了遗传算法中存在的早熟收敛问题。

4并行遗传算法求解非线性方程组

遗传算法具有并行性，其按并行方式搜索一个种群数目的点，而不是单点。其的并行性表现在以下两个方面:一是内在并行性，本身适应大规模并行。最简单的并行方式是让若干台甚至是数千台计算机各自进行独立种群的演化计算，运行过程中甚至不进行任何通信，等到运算结束时才通信比较，选取最佳个体。这种并行处理方式对并行系统结构并无任何限制和要求，即遗传算法适合在目前所有的并行机或分布式系统上进行并行处理，尤其适用现在PC机多线程多进程的并行计算。二是遗传算法的内含并行性。由于遗传算法采用种群的方式组织搜索，因而可同时搜索解空间的多个区域，并相互交流信息。使用这种搜索方式，虽然每次只执行与种群规模n成比例的计算，但实质上已进行了大约O(n3)次有效搜索，这就使遗传算法能以较少的计算获得较大的收益。目前并行遗传算法的实现方案分3类:主从式模式(Master－SlaveModel)、粗粒度模型(Coarse－GrainedModel)和细粒度模型(Fine－GrainedModel)。并行遗传算法正广泛应用于各个领域，已有人将并行遗传算法用在非线性方程组求解上。刘灿文等提出一种自适应并行遗传算法:采用粗粒度模型，将初始种群分为3个子种群，并让这3个子群体按照特点互补的演化规律在并行机的3个进程上分别进化，定期移植或交换部分优秀个体。其中进程0为主进程，主要任务之一是保存自身进化而得的优秀个体并吸收另外两个进程进化而得的优秀个体，使不遭受破坏，目的在于保持优秀个体的多样性。对交叉和变异概率针对不同进程、不同阶段设置不同的值，来提高进化效率，如进程0中的子群体在进化中具有较低的交叉率和变异率，使得优秀个体不易被破坏，而对进程1和进程2用较高的交叉率和变异率，尤其在进化后期，用以探测新的超平面上的优秀个体，不断为进程0提供新的超平面上的优秀个体，防止进程0“早熟”并加快其收敛到全局最优的速度。付振岳等［35］针对一些复杂的含有三角函数或是对数的非线性方程组用遗传算法进行求解，由于该类问题涉及的求解空间大，遗传算法需要更大的初始化种群，为提高算法的性能，引入了并发机制和最大堆来提高硬件利用率和降低某些关键步骤的时间复杂度。根据CPU的利用率和计算等待时间的比率以及CPU的个数，设置合适的线程数，采用细粒度模型，将种群根据线程数分割成相应的组群，每个线程对组群先后进行堆初始化→交叉→堆初始化→变异→堆初始化→淘汰等操作，设置一个全局变量记录全体线程在执行遗传退火算法中产生的最优个体，每个线程在完成一轮遗传退火行为后，将本组群的最优值与全局最优值进行比较，若本组群最优值优于全局最优值，则用本组群最优值替换全局最优值，反之，则用全局最优值替换本组群最优值。该算法有效地提高了遗传退火算法的性能，加快了求解的速度。

5结束语

文中分析了遗传算法求解非线性方程组的研究现状。从所列的文献看，大部分的研究工作主要集中在对遗传算法求解线性方程组各个环节的改进中，也有不少学者提出了遗传算法与其他智能算法混合使用来求解的方法，比如模拟退火算法、量子计算原理等。还有众多研究者结合了计算机多处理器技术和并行运算技术，提出了并行遗传算法这一新概念。从现有遇到的问题看，对该问题的研究尚有不足，需对其进行深一步的研究。未来的工作，可包括两个方面:一在现有模型基础上，研究如何将遗传算法与局部优化方法结合，以便有效提高解的质量。另一方面朝并行模型混合化方向研究。可以预期，随着计算机技术的进步和生物学研究的深入，遗传算法求解非线性方程组将更具通用性和有效性。

作者：吴龙任红民毕惟红单位：杭州科技职业技术学院信息工程学院浙江大学数学系科学与工程计算研究所