函數最值計算的模擬退火算法設計與應用研究

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

(四川大學錦城學院 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%的正確率，快速計算出高精度的答案。相反，如果參數設置隨意，可能會使正確率、速度、精度大打折扣。因此，參數優化過程對于計算效果的影響很大，如何利用人工智能進行全局最優化，將是進一步研究的方向。