函数最值计算的模拟退火算法设计与应用研究

贾天理，喻若舟，王思凯，秦 雯

(四川大学锦城学院 a.通识教育学院； b.计算机与软件学院，成都 611731)

1 计算机求最值的擂台思想

在高等数学学习中，关于一些幂次较高或者较为复杂的多项式函数求最值的问题，其求导、找驻点、求极值等都比较繁琐，很容易在计算中出错。因此，利用计算机辅助验证函数最大值、最小值的正确性，成为有效解决问题的方法。计算机使用的模拟退火算法程序设计，成为快速解决问题的关键。通过设计模拟退火算法程序，使用计算机运行程序，可以在较短时间内找到一个函数的最值，进而快速地辅助验证所求答案。计算机之所以如此“聪明”“快速”, 程序是它的灵魂，而程序是编写调教出来的。计算机寻找最值的过程是通过两两比较的擂台思想进行的：首先，进行相邻两个数的比较，将两者比较后的较大值记录在max变量中；其次，继续与下一个数再进行两两比较，若下一个数大，则将下一个数的值记录在max变量中，否则max保持原先值，以此进行下去。设计程序是计划通过计算机帮助我们解决现实问题，比如设计一个“成绩管理”程序求最高分，由于每次参加考试的人数不定，所以参与比较的数据个数是灵活通变的。

2 模拟退火算法概述

2.1 算法简介

退火是一种对材料的热处理工艺，包括金属材料、非金属材料，且新材料的退火目的也与传统金属退火存在异同。退火存在很多个冷却点，这和函数中的极值概念十分相似——是局部的最大值，但不一定是全局的最大值。因此，模拟退火就是让答案像金属退火一样：当温度高时，金属不稳定，随机取值的范围大，接受一个极大值成为最大值的概率小；当温度低时，金属趋于稳定，随机取值的范围小，接受一个极大值成为最大值的概率大；当多次重复进行模拟退火后，在全部答案中选取一个最优解。由于退火的规律引入了如初始温度、冷却倍率等随机因素，得到最优解的概率会大大增加。因此，可以模拟这个过程，将目标函数作为能量函数，通过求得能量函数的最大值，来求得函数的最大/最小值。

模拟退火算法是一种通用的基于概率的算法，它是基于Monte-Carlo蒙特卡罗迭代求解策略的一种随机寻优算法，该算法在理论上具有概率的全局优化性能，当一个问题是一个多峰函数时，常使用模拟退火算法求解。该算法目前已在工程计算中得到了广泛应用，如生产调度、控制工程、机器学习、神经网络、信号处理等领域。

2.2 算法程序设计

A.根据计算函数计算出一个位于当前答案的解空间。B.计算新答案与当前答案之间的差值。C.判断新答案是否被接受。如果新答案优于当前答案，那么可以无条件接受新答案，即当前答案更改为新答案；如果新答案劣于当前答案，算法仍然有一定概率接受该答案。

使用以上程序设计一次，当前答案就完成了一次迭代。实际应用中一次程序运算往往不能得到正确的解，需要通过多次重复以上步骤开始下一轮迭代，以得到最终的正确答案。

2.3 算法核心代码(C++语言)

#include

#include

#include

#include

using namespace std;

const int MAXN = 55, ATIMES = 1e3;

const double EPS = 1e-18, CD = 0.996, PRE_T = 1;

double a[MAXN], l, r, ans = -1e18, ansx;

int n;

//计算函数

inline double Cal(double x, double ans = 0) { for (int i = n; i >= 0; i--) ans = ans * x + a[i]; return ans; }

//退火函数

inline void Anneal(double& ansx, double& ans)

{

for (double t = PRE_T, sub = ansx; t > EPS; t *= CD)

{

//mov为自变量移动的范围

double mov = ((double)rand() * 2 - RAND_MAX) / RAND_MAX * (r - l), x = sub + mov * t; //第一步

if (xr) continue;//忽略掉不在定义域的解

double newans = Cal(x), delta = newans - ans;//第二步

if (newans > ans) sub = (ansx = x), ans = newans;//第三步

else if (exp(-delta / t) * RAND_MAX > rand()) sub = x;//否则根据Metropolis准则，以一定概率接受该答案

}

}

signed main(void)

{

cout << "请输入多项式函数的次数： ";

cin >> n;

cout << "请从大到小次输入n～0次的系数： ";

for (int i = n; i >= 0; i--) cin >> a[i];

cout << "请输入定义域范围L,R，即x∈[L,R] ";

cin >> l >> r;

ans = Cal(ansx = (l + r) / 2);

double st = clock(), t = (l + r) / 2, tans = Cal(t);

for (int i = 1; i <= ATIMES; i++) Anneal(ansx, ans);

double ed = clock();

cout << setprecision(18)

<< " 最大值点x=" << ansx

<< " f(x)=" << ans

<< " 计算用时：" << (ed - st) / CLOCKS_PER_SEC << " 秒 ";

return 0;

}

3 算法辅助教学应用示例

例1 求函数f(x)=-7x6-6x5+5x4-4x3+3x2-2x1+1在区间[-2，4]上的最大值。

程序运行求解：

程序提示“请输入多项式函数的次数：”，输入该函数的次数6；

程序提示“请从大到小次输入n～0次的系数：”，依次输入

-7 -6 5 -4 3 -2 1

程序提示“请输入定义域范围L,R，即x∈[L,R]”，输入定义域-2 4。

回车执行后，可以得到函数的最大值点为x=-1.31813743706443298，函数的最大值为f(x)=20.263054742178884。计算机计算函数最大值用时为1.05200000000000005s。

程序运行求解：

现在不再求一个多项式函数，所以需要修改程序：

把原来的Cal函数改为题目中的式子：

inline double Cal(double x) {return pow(cos(x/2-7*pi/8),2)-pow(cos(x/2+7*pi/8),2);}

其中pi=acos(-1)，即π=arccos(-1)。

去除所有的输入语句，赋值l=-pi，r=pi，以免手动输入丢失精度，计算机执行程序，得到函数的最大值点为x=-1.57079627680778944，函数的最大值为f(x)=0.707106781186546796，整个计算用时2.004s。

使用模拟退火算法计算时，要根据实际函数的特征：如含有三角函数、根号、多项式除多项式等形式，需要进行Cal函数的简单修改来达到目的。模拟退火算法也可以用于其他类型的函数，例如包含开根号、含有对数函数等的函数计算，非常方便。模拟退火算法的短板是不能找出函数所有的最值点，操作中可以通过遍历定义域取值，通过已经找到的最值去寻找精度较低的其他最值点，用以弥补短板。在许多求最值的应用问题中，当数据量增多时，计算机的高速运算优势得到充分体现，它能在瞬间找到最大(小)值的结果，说明程序算法在现实应用中会产生不可估量的效果。

4 结语

模拟退火算法作为一个随机化算法，在计算多峰函数的最优解上表现突出。使用模拟退火算法设计，通过计算机运行减少计算工作量，在经济、商业、医学、市场预测、信号估计、社会科学等一系列实际应用领域中具有重要价值。模拟退火算法的核心在于其参数，其参数决定了模拟退火算法计算的速度、精度、正确性。在合适的参数下，可以保证接近100%的正确率，快速计算出高精度的答案。相反，如果参数设置随意，可能会使正确率、速度、精度大打折扣。因此，参数优化过程对于计算效果的影响很大，如何利用人工智能进行全局最优化，将是进一步研究的方向。