函數(shù)最值計算的模擬退火算法設(shè)計與應(yīng)用研究

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

(四川大學錦城學院 a.通識教育學院； b.計算機與軟件學院，成都 611731)

1 計算機求最值的擂臺思想

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

2 模擬退火算法概述

2.1 算法簡介

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

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

2.2 算法程序設(shè)計

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

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

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;

//計算函數(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為自變量移動的范圍

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準則，以一定概率接受該答案

}

}

signed main(void)

{

cout << "請輸入多項式函數(shù)的次數(shù)： ";

cin >> n;

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

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 算法輔助教學應(yīng)用示例

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

程序運行求解：

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

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

-7 -6 5 -4 3 -2 1

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

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

程序運行求解：

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

把原來的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)。

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

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

4 結(jié)語

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