賈天理，喻若舟，王思凱，秦 雯

(四川大學(xué)錦城學(xué)院 a.通識(shí)教育學(xué)院； b.計(jì)算機(jī)與軟件學(xué)院，成都 611731)

1 計(jì)算機(jī)求最值的擂臺(tái)思想

在高等數(shù)學(xué)學(xué)習(xí)中，關(guān)于一些冪次較高或者較為復(fù)雜的多項(xiàng)式函數(shù)求最值的問(wèn)題，其求導(dǎo)、找駐點(diǎn)、求極值等都比較繁瑣，很容易在計(jì)算中出錯(cuò)。因此，利用計(jì)算機(jī)輔助驗(yàn)證函數(shù)最大值、最小值的正確性，成為有效解決問(wèn)題的方法。計(jì)算機(jī)使用的模擬退火算法程序設(shè)計(jì)，成為快速解決問(wèn)題的關(guān)鍵。通過(guò)設(shè)計(jì)模擬退火算法程序，使用計(jì)算機(jī)運(yùn)行程序，可以在較短時(shí)間內(nèi)找到一個(gè)函數(shù)的最值，進(jìn)而快速地輔助驗(yàn)證所求答案。計(jì)算機(jī)之所以如此“聰明”“快速”, 程序是它的靈魂，而程序是編寫調(diào)教出來(lái)的。計(jì)算機(jī)尋找最值的過(guò)程是通過(guò)兩兩比較的擂臺(tái)思想進(jìn)行的：首先，進(jìn)行相鄰兩個(gè)數(shù)的比較，將兩者比較后的較大值記錄在max變量中；其次，繼續(xù)與下一個(gè)數(shù)再進(jìn)行兩兩比較，若下一個(gè)數(shù)大，則將下一個(gè)數(shù)的值記錄在max變量中，否則max保持原先值，以此進(jìn)行下去。設(shè)計(jì)程序是計(jì)劃通過(guò)計(jì)算機(jī)幫助我們解決現(xiàn)實(shí)問(wèn)題，比如設(shè)計(jì)一個(gè)“成績(jī)管理”程序求最高分，由于每次參加考試的人數(shù)不定，所以參與比較的數(shù)據(jù)個(gè)數(shù)是靈活通變的。

2 模擬退火算法概述

2.1 算法簡(jiǎn)介

退火是一種對(duì)材料的熱處理工藝，包括金屬材料、非金屬材料，且新材料的退火目的也與傳統(tǒng)金屬退火存在異同。退火存在很多個(gè)冷卻點(diǎn)，這和函數(shù)中的極值概念十分相似——是局部的最大值，但不一定是全局的最大值。因此，模擬退火就是讓答案像金屬退火一樣：當(dāng)溫度高時(shí)，金屬不穩(wěn)定，隨機(jī)取值的范圍大，接受一個(gè)極大值成為最大值的概率?。划?dāng)溫度低時(shí)，金屬趨于穩(wěn)定，隨機(jī)取值的范圍小，接受一個(gè)極大值成為最大值的概率大；當(dāng)多次重復(fù)進(jìn)行模擬退火后，在全部答案中選取一個(gè)最優(yōu)解。由于退火的規(guī)律引入了如初始溫度、冷卻倍率等隨機(jī)因素，得到最優(yōu)解的概率會(huì)大大增加。因此，可以模擬這個(gè)過(guò)程，將目標(biāo)函數(shù)作為能量函數(shù)，通過(guò)求得能量函數(shù)的最大值，來(lái)求得函數(shù)的最大/最小值。

模擬退火算法是一種通用的基于概率的算法，它是基于Monte-Carlo蒙特卡羅迭代求解策略的一種隨機(jī)尋優(yōu)算法，該算法在理論上具有概率的全局優(yōu)化性能，當(dāng)一個(gè)問(wèn)題是一個(gè)多峰函數(shù)時(shí)，常使用模擬退火算法求解。該算法目前已在工程計(jì)算中得到了廣泛應(yīng)用，如生產(chǎn)調(diào)度、控制工程、機(jī)器學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)、信號(hào)處理等領(lǐng)域。

2.2 算法程序設(shè)計(jì)

A.根據(jù)計(jì)算函數(shù)計(jì)算出一個(gè)位于當(dāng)前答案的解空間。B.計(jì)算新答案與當(dāng)前答案之間的差值。C.判斷新答案是否被接受。如果新答案優(yōu)于當(dāng)前答案，那么可以無(wú)條件接受新答案，即當(dāng)前答案更改為新答案；如果新答案劣于當(dāng)前答案，算法仍然有一定概率接受該答案。

使用以上程序設(shè)計(jì)一次，當(dāng)前答案就完成了一次迭代。實(shí)際應(yīng)用中一次程序運(yùn)算往往不能得到正確的解，需要通過(guò)多次重復(fù)以上步驟開始下一輪迭代，以得到最終的正確答案。

2.3 算法核心代碼(C++語(yǔ)言)

#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;

//計(jì)算函數(shù)

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

//退火函數(shù)

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

{

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

{

//mov為自變量移動(dòng)的范圍

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;//否則根據(jù)Metropolis準(zhǔn)則，以一定概率接受該答案

}

}

signed main(void)

{

cout << "請(qǐng)輸入多項(xiàng)式函數(shù)的次數(shù)： ";

cin >> n;

cout << "請(qǐng)從大到小次輸入n～0次的系數(shù)： ";

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

cout << "請(qǐng)輸入定義域范圍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)

<< " 最大值點(diǎn)x=" << ansx

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

<< " 計(jì)算用時(shí)：" << (ed - st) / CLOCKS_PER_SEC << " 秒 ";

return 0;

}

3 算法輔助教學(xué)應(yīng)用示例

例1 求函數(shù)f(x)=-7x6-6x5+5x4-4x3+3x2-2x1+1在區(qū)間[-2，4]上的最大值。

程序運(yùn)行求解：

程序提示“請(qǐng)輸入多項(xiàng)式函數(shù)的次數(shù)：”，輸入該函數(shù)的次數(shù)6；

程序提示“請(qǐng)從大到小次輸入n～0次的系數(shù)：”，依次輸入

-7 -6 5 -4 3 -2 1

程序提示“請(qǐng)輸入定義域范圍L,R，即x∈[L,R]”，輸入定義域-2 4。

回車執(zhí)行后，可以得到函數(shù)的最大值點(diǎn)為x=-1.31813743706443298，函數(shù)的最大值為f(x)=20.263054742178884。計(jì)算機(jī)計(jì)算函數(shù)最大值用時(shí)為1.05200000000000005s。

程序運(yùn)行求解：

現(xiàn)在不再求一個(gè)多項(xiàng)式函數(shù)，所以需要修改程序：

把原來(lái)的Cal函數(shù)改為題目中的式子：

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)。

去除所有的輸入語(yǔ)句，賦值l=-pi，r=pi，以免手動(dòng)輸入丟失精度，計(jì)算機(jī)執(zhí)行程序，得到函數(shù)的最大值點(diǎn)為x=-1.57079627680778944，函數(shù)的最大值為f(x)=0.707106781186546796，整個(gè)計(jì)算用時(shí)2.004s。

使用模擬退火算法計(jì)算時(shí)，要根據(jù)實(shí)際函數(shù)的特征：如含有三角函數(shù)、根號(hào)、多項(xiàng)式除多項(xiàng)式等形式，需要進(jìn)行Cal函數(shù)的簡(jiǎn)單修改來(lái)達(dá)到目的。模擬退火算法也可以用于其他類型的函數(shù)，例如包含開根號(hào)、含有對(duì)數(shù)函數(shù)等的函數(shù)計(jì)算，非常方便。模擬退火算法的短板是不能找出函數(shù)所有的最值點(diǎn)，操作中可以通過(guò)遍歷定義域取值，通過(guò)已經(jīng)找到的最值去尋找精度較低的其他最值點(diǎn)，用以彌補(bǔ)短板。在許多求最值的應(yīng)用問(wèn)題中，當(dāng)數(shù)據(jù)量增多時(shí)，計(jì)算機(jī)的高速運(yùn)算優(yōu)勢(shì)得到充分體現(xiàn)，它能在瞬間找到最大(小)值的結(jié)果，說(shuō)明程序算法在現(xiàn)實(shí)應(yīng)用中會(huì)產(chǎn)生不可估量的效果。

4 結(jié)語(yǔ)

模擬退火算法作為一個(gè)隨機(jī)化算法，在計(jì)算多峰函數(shù)的最優(yōu)解上表現(xiàn)突出。使用模擬退火算法設(shè)計(jì)，通過(guò)計(jì)算機(jī)運(yùn)行減少計(jì)算工作量，在經(jīng)濟(jì)、商業(yè)、醫(yī)學(xué)、市場(chǎng)預(yù)測(cè)、信號(hào)估計(jì)、社會(huì)科學(xué)等一系列實(shí)際應(yīng)用領(lǐng)域中具有重要價(jià)值。模擬退火算法的核心在于其參數(shù)，其參數(shù)決定了模擬退火算法計(jì)算的速度、精度、正確性。在合適的參數(shù)下，可以保證接近100%的正確率，快速計(jì)算出高精度的答案。相反，如果參數(shù)設(shè)置隨意，可能會(huì)使正確率、速度、精度大打折扣。因此，參數(shù)優(yōu)化過(guò)程對(duì)于計(jì)算效果的影響很大，如何利用人工智能進(jìn)行全局最優(yōu)化，將是進(jìn)一步研究的方向。