基于自适应模拟退火遗传算法的非线性方程组求解

胡斐，赵治国

0 引言

传统的求解非线性方程组的方法，如牛顿法、割线法等,都存在不足之处[1,2]。遗传算法是一种借鉴生物界自然选择和遗传机制的算法，可以用来求解高度非线性的优化问题[4]，近年来得到了广泛的应用[2,3]。然而，遗传算法存在容易早熟的不足(即很快收敛到局部最优解而不是全局最优解)[3,4]。模拟退火算法是模仿热力学中液体的冻结与结晶或金属熔液的冷却与退火过程的算法，该算法有可能从局部最优中跳出，尽可能找到全局最优解[4,5]。因此，本文采用自适应交叉比例产生交叉后代和变异后代，并将模拟退火算法融合到遗传算法中，建立了自适应模拟退火遗传算法，用于求解非线性方程组。

1 自适应模拟退火遗传算法

采用自适应交叉比例产生交叉后代和变异后代，并将模拟退火算法(SA)融合到遗传算法(GA)中，建立的自适应模拟退火遗传算法(ASAGA，Adaptive Simulated Annealing Genetic Algorithm)如图1所示，ASAGA步骤如下:

图1 自适应模拟退火遗传算法(ASAGA)原理图

(1)进行编码并产生初始种群；

(2)对种群的适应度进行评价；

(3)判断是否满足终止条件，如果满足，则得到最优个体并退出算法，否则进入步骤(4)；

(4)选择下一代种群，保留其中的若干精英个体，根据种群的多样性自适应地调整交叉比例进行交叉和变异，生成交叉后代和变异后代；

(5)将步骤(4)生成的交叉后代和变异后代中的每个个体，都作为模拟退火算法的初始点，进行模拟退火，产生新的个体，与保留的精英个体一起组成新的种群，转至步骤(2)。

1.1 编码及初始种群的产生

编码是指把问题的可行解从其解空间转化到遗传算法所能处理的搜索空间的转化方法。为了使初始种群具有普遍的代表性，采用随机方法产生初始种群。种群的大小影响算法的性能和计算量，一般取为20～100。

1.2 评价

评价即计算种群中每个个体的适应度值。某个体的适应度值越好，说明该个体越适应环境，越容易生存；某个体的适应度值越差，说明该个体越不适应环境，越容易被淘汰。

1.3 终止条件

终止条件可以是最大遗传代数、算法最长运行时间、若干代内适应度函数的累计变化值等。

1.4 选择

选择即从父辈种群中选择若干个体作为下一代种群。

1.5 精英、交叉、变异和自适应交叉比例

采用精英保留策略，即适应度值最好的若干精英个体被保留至下一代。交叉和变异对遗传算法至关重要:交叉使得遗传算法能够从不同的个体中提取出最好的基因，然后将它们重新组合，生成潜在的更优后代；变异有助于增加种群的多样性，同时也增加了遗传算法生成更优后代的可能性。在自适应模拟退火遗传算法(ASAGA)中，精英后代个数是一个固定值，交叉后代和变异后代的个数由式(1)和式(2)计算，产生的下一代种群组成示意图如图2所示，注意，这里的交叉后代和变异后代要进行模拟退火，而精英后代不进行模拟退火。

其中，nCoverKids表示由交叉产生的后代个数；nMutateKids表示由变异产生的后代个数；Population_size表示种群大小；Elite_count表示精英后代个数；Crossover_fraction表示交叉比例，需要指出的是，在一般的遗传算法中，Crossover_fraction通常取0.4～0.9之间的某一个值，而且该值在整个算法过程中保持不变。

图2 下一代种群组成示意图

前已述及，遗传算法的缺点是容易出现早熟现象，即种群中个体的多样性过早地丢失。而变异有助于增加种群的多样性[4,6]。因此，在自适应模拟退火遗传算法(ASAG)中，采用自适应交叉比例产生交叉后代和变异后代，即种群多样性较高时生成较少的变异后代，种群多样性较低时生成较多的变异后代，使得种群的多样性不会下降得太快，从而避免早熟现象的发生。另一方面，种群的多样性可以由种群中个体间的平均距离来度量[6]，即个体间的平均距离较大时，种群的多样性较高，个体间的平均距离较小时，种群的多样性较低。于是，提出了如式(3)所示的交叉比例计算公式，利用该公式，可以根据每一代种群中个体间平均距离的大小(即种群多样性的高低)自适应地改变交叉比例，从而改变变异后代的个数(如式(2)所示)，使种群的多样性得到保持，避免早熟现象的发生。

式中，cf表示交叉比例Crossover_fraction；cf_max表示交叉比例的最大值，这里取为0.8；cf_min表示交叉比例的最小值，这里取为0.6；ad表示种群中个体间的平均距离；ad_up表示种群中个体间平均距离的上门限值；ad_low表示种群中个体间平均距离的下门限值。

1.6 模拟退火算法的融入

如果退火过程足够缓慢，模拟退火(Simulated Annealing,SA)可以保证收敛到全局最优解。虽然在很多实际应用场合很难满足这种冷却速率的条件，但是模拟退火在冷却速率较快的情况下，也经常能够获得较好的结果[7]。模拟退火算法的思想是Metropolis提出的,该算法保持“产生新解-判断-接收/舍弃”迭代过程,对应固体某一恒定温度下趋于热平衡的过程,也即执行了一次Metropolis准则[5]:

在应用模拟退火算法时，需要确定一组控制算法进程的参数，包括初始点、初始温度、温度更新函数和迭代停止条件。在自适应模拟退火遗传算法(ASAGA)中，初始点即如图2所示由GA产生的下一代种群中交叉后代和变异后代的每个个体；初始温度需要综合考虑优化质量和优化效率来确定；按指数函数降温，温度更新函数如式(5)所示；迭代停止条件可以是若干代内目标函数的平均变化值、最大迭代次数、算法最长运行时间等。

其中，T为当前温度；To为初始温度；i为迭代次数。

对于每个初始点，运行SA后，输出各自的最佳点，这些最佳点与保留的精英后代一起组成了一个新的种群，再被ASAGA评价。这样，我们就把SA融入到了GA之中。

2 自适应模拟退火遗传算法求解非线性方程组

2.1 非线性方程组的求解问题转化为函数优化问题

非线性方程组的一般形式为:

方程求根问题f(x)=0可以等价地看成求极小值问题min|f(x)|[1]。根据这样的思想，我们可以把式(6)所示的非线性方程组求解问题转化为式(7)所示目标函数的优化问题，而且是取最小值优化。显然，若方程组(6)有解，则目标函数(7)的最小值为零。求得的目标函数(7)的值越接近于零，那么对应的方程组(6)的解就越精确。

2.2 数值实验

选取了5个测试题[8,9]进行数值实验:

采用浮点数编码，初始种群随机产生，适应度函数即式(7)，选择函数为随机一致函数(Stochastic uniform)，种群大小(Population_size)为100，精英个数(Elite_count)为10，交叉函数为分散交叉函数(Scattered crossover)，变异函数为高斯变异函数(Gaussian mutation)，个体间平均距离的上门限值(ad_up)为1，下门限值(ad_low)为0.5，初始温度为100，最大迭代次数为1000，最大遗传代数为300。寻优过程如图3所示(限于篇幅，这里只给出了方程组(1)的寻优过程)，实验结果如表1所示，可以看出，ASAGA的结果比参考文献的结果要好。

图3 方程组(1)的寻优过程

表1 数值实验结果与对比

3 结论

针对传统遗传算法容易早熟的不足,本文对其进行了两方面的改进,建立了自适应模拟退火遗传算法(ASAGA)，根据种群多样性自适应地调整交叉后代和变异后代的比例，并融合了模拟退火算法的思想,维持了种群的多样性，提高了算法的全局搜索能力。数值实验结果表明，将ASAGA用于求解非线性方程组，达到了很高的精度。

[1]同济大学计算数学教研室.现代数值数学和计算[M].上海:同济大学出版社,2004.

[2]史永宏,张茜.基于遗传算法优化的智能控制器[J].微型电脑应用,2010,26(2):33–34.

[3]吴勇,郝矿荣,丁永生,等.基于遗传算法的机器人动态视觉检测系统[J].微型电脑应用,2009,25(9):17–20.

[4]刘勇,康立山,陈毓屏.非数值并行算法(第二册)-遗传算法[M].北京:科学出版社.1995.

[5]康立山,谢云,尤矢勇,等.非数值并行算法(第一册)-模拟退火算法[M].北京:科学出版社,1994.

[6]The MathWorks Inc.Genetic Algorithm and Direct Search Toolbox—User’s guide,2009.

[7]崔逊学.多目标进化算法及其应用[M].北京:国防工业出版社,2006.

[8]FLOUDAS Christodoulos.Handbook of test problems in local and global optimization[M].Dordrecht:Kluwer academic,1999.