一種加速搜索函數(shù)極值的剪枝方法

盧偉榮，張磊

（中山大學(xué)數(shù)學(xué)學(xué)院，廣州 510275）

一種加速搜索函數(shù)極值的剪枝方法

盧偉榮，張磊

（中山大學(xué)數(shù)學(xué)學(xué)院，廣州 510275）

函數(shù)的極值求解問(wèn)題是實(shí)際應(yīng)用中有許多優(yōu)化問(wèn)題的最基本的問(wèn)題，大多數(shù)模型的優(yōu)化問(wèn)題最終都轉(zhuǎn)化為目標(biāo)函數(shù)的極值問(wèn)題，如最大似然估計(jì)和最小二乘估計(jì)。在極值問(wèn)題的數(shù)值解法中，遍歷搜索可用于函數(shù)的高精度極值求解問(wèn)題，但其時(shí)間復(fù)雜度非常高；為解決遍歷搜索時(shí)間過(guò)長(zhǎng)的問(wèn)題，隨機(jī)搜索方法被引入，如遺傳算法和模擬褪火算法，而遺傳算法極不穩(wěn)定不適合大數(shù)據(jù)下智能問(wèn)題的復(fù)雜目標(biāo)函數(shù)的極值搜索。結(jié)合遍歷搜索和隨機(jī)搜索，設(shè)計(jì)一種基于二進(jìn)制編碼的搜索樹(shù)，并引入基于模擬退火思想的隨機(jī)剪枝算法，在保證模型精度的基礎(chǔ)上對(duì)搜索樹(shù)進(jìn)行剪枝。在實(shí)驗(yàn)環(huán)節(jié)使用多種形態(tài)的函數(shù)進(jìn)行效用分析，說(shuō)明其在精度和穩(wěn)定性及時(shí)間效用方面的優(yōu)勢(shì)。

極值求解；遍歷搜索；模擬退火；數(shù)值解法

0 引言

在科學(xué)技術(shù)的各個(gè)領(lǐng)域，通常會(huì)對(duì)所處理的實(shí)際問(wèn)題進(jìn)行抽象、簡(jiǎn)化，進(jìn)而建立數(shù)學(xué)模型。其中，函數(shù)的極值求解對(duì)應(yīng)了一類常見(jiàn)的實(shí)際問(wèn)題，針對(duì)處理在一定條件下，如何實(shí)現(xiàn)收益最大，或者成本最低等問(wèn)題。另外，函數(shù)的極值求解問(wèn)題是實(shí)際應(yīng)用中有許多優(yōu)化問(wèn)題的最基本的問(wèn)題，大多數(shù)模型的優(yōu)化問(wèn)題最終都轉(zhuǎn)化為目標(biāo)函數(shù)的極值問(wèn)題，如最大似然估計(jì)和最小二乘估計(jì)。

根據(jù)求解方法的不同，函數(shù)極值求解可分為以下兩類，精確解法和數(shù)值解法。極值模型的精確解一般通過(guò)基于導(dǎo)數(shù)方法得到滿足條件的約束方程，但在實(shí)際應(yīng)用中，往往需要面對(duì)目標(biāo)函數(shù)f不可微，或者其基于導(dǎo)數(shù)的約束方程難以求解到的問(wèn)題。相對(duì)而言，大部分?jǐn)?shù)值解法，如黃金分割搜索、二次插值法、各種搜索算法及各種迭代法等，僅依賴于目標(biāo)函數(shù)在某些點(diǎn)上的取值，在實(shí)際應(yīng)用中，適用范圍更加廣泛[1-2]。

遍歷搜索，是一種基本且易于理解的數(shù)值解法，可用于高精度的函數(shù)極值求解。通過(guò)對(duì)變量區(qū)間進(jìn)行不斷地迭代細(xì)分，遍歷各區(qū)間尋找函數(shù)最值的近似。該方法有以下兩個(gè)優(yōu)點(diǎn)，適用范圍廣（僅需知道函數(shù)值，無(wú)可微或連續(xù)要求）和全局性強(qiáng)（不易限于局部最優(yōu)），但運(yùn)行時(shí)間過(guò)長(zhǎng)的問(wèn)題限制了該方法在實(shí)際中的應(yīng)用。

針對(duì)上述情況，本文設(shè)計(jì)了一種獨(dú)特的搜索流程，即一種基于二進(jìn)制編碼樹(shù)的搜索方法，可設(shè)計(jì)出深度搜索和廣度搜索流程，還可以靈活地進(jìn)行剪枝以加速尋優(yōu)進(jìn)程。本文將基于模擬退火的思想，對(duì)搜索樹(shù)進(jìn)行剪枝，在保證模型精度的基礎(chǔ)上，實(shí)現(xiàn)算法時(shí)間的優(yōu)化。最后，將介紹該模型在多元函數(shù)上的推廣。

1 方法設(shè)計(jì)和相關(guān)理論

1.1 數(shù)軸的區(qū)間劃分與數(shù)的二進(jìn)制表示

假設(shè)已通過(guò)變換x=（b-a）*x'+a將函數(shù)的定義域從[a，b]映射到[0，1]，其中a〈b且a，b∈R，不失一般性將函數(shù)記為：

令a0=0，b0=1，對(duì)?r∈[0，1]，下面將不斷二等分r所在的區(qū)間：二等分區(qū)間[a0，b0]，則必有一子區(qū)間包含實(shí)數(shù)r，記該區(qū)間為[a1，b1]；二等分區(qū)間[a1，b1]，則必有一子區(qū)間包含實(shí)數(shù)r，記該區(qū)間為[a1，b1]，…，如圖1所示，繼續(xù)下去，可得到一個(gè)區(qū)間長(zhǎng)度不斷減半的閉區(qū)間序列{[an，bn]}。

圖1 區(qū)間套{[an，bn]}的構(gòu)建

因?yàn)椋?/p>

下面追蹤區(qū)間套的構(gòu)建過(guò)程產(chǎn)生一串與實(shí)數(shù)r相關(guān)的二進(jìn)制數(shù)x[1]…x[k]：第i次二等分區(qū)間時(shí)，若實(shí)數(shù)r落入左子區(qū)間，則取x[i]=0；若實(shí)數(shù)r落入右子區(qū)間，則取x[i]=1，i=1～k。

可見(jiàn)對(duì)?x∈[0，1]，都可按上述方法產(chǎn)生一串二進(jìn)制數(shù)x[1]…x[k]，其中k為細(xì)分步數(shù)。定義實(shí)數(shù)x的逼近公式為：

可證明，通過(guò)上述方法可產(chǎn)生逼近函數(shù)定義域內(nèi)的任意實(shí)數(shù)的二進(jìn)制表示0．x[1]x[2]x[k]2，其中k為細(xì)分步數(shù)，且其誤差不大于w[k]=。這里之所以通過(guò)追蹤區(qū)間套的構(gòu)建過(guò)程產(chǎn)生一串與實(shí)數(shù)r相關(guān)的二進(jìn)制數(shù)x[1]…x[k]，是為了下一節(jié)能夠直觀分析搜索樹(shù)的構(gòu)造。

1.2 搜索樹(shù)的設(shè)計(jì)

搜索算法搜索最優(yōu)解的本質(zhì)是由初始并非極值點(diǎn)的數(shù)產(chǎn)生一個(gè)點(diǎn)列，使該點(diǎn)列能夠逼近極值點(diǎn)，如下山法將沿函數(shù)的負(fù)梯度方向產(chǎn)生點(diǎn)列，順序搜索算法則通過(guò)按一定的步長(zhǎng)來(lái)產(chǎn)生點(diǎn)列，隨機(jī)搜索算法則通過(guò)隨機(jī)方式來(lái)產(chǎn)生點(diǎn)列，不同的搜索算法決定了如何由一個(gè)初始點(diǎn)產(chǎn)生下一個(gè)點(diǎn)。本文的搜索算法的搜索流程將采用基于解空間樹(shù)的回溯法，使用回溯法的核心問(wèn)題是如何將問(wèn)題的解表示成解空間樹(shù)，以及如何通過(guò)剪枝來(lái)提高效率。

下面給出解空間樹(shù)的構(gòu)造方法：前一節(jié)給出了通過(guò)追蹤區(qū)間套的構(gòu)建過(guò)程產(chǎn)生一串與實(shí)數(shù)r相關(guān)的二進(jìn)制數(shù)x[1]…x[k]，第i次二等分區(qū)間時(shí)，若實(shí)數(shù)r落入左子區(qū)間，則取x[i]=0；若實(shí)數(shù)r落入右子區(qū)間，則取x [i]=1；若我們用左子樹(shù)追蹤左半?yún)^(qū)間的細(xì)分過(guò)程，用右子樹(shù)追蹤右半?yún)^(qū)間的細(xì)分過(guò)程，則追蹤區(qū)間套的構(gòu)建過(guò)程產(chǎn)生一棵二叉樹(shù)，每個(gè)點(diǎn)唯一落入一個(gè)節(jié)點(diǎn)中，而且搜索路徑的分枝值將得到由（2）式確定的一個(gè)與結(jié)點(diǎn)對(duì)應(yīng)的值值，所有這些值構(gòu)成了侯選的最值，當(dāng)K足夠大時(shí)這些侯選值可以逼近定義域中的任意點(diǎn)，因此這種二叉樹(shù)可以做為解空間樹(shù)。

由公式（2）的定義可知，x[i]，i=1，2，…，k可能的取值為0或者1，因此解空間樹(shù)是圖2所示的滿二叉樹(shù)，在特定精度下可以對(duì)每個(gè)可能的取值進(jìn)行試探。如圖2所示，對(duì)于第i層的結(jié)點(diǎn)，x[i]的取值為0時(shí)搜索其左子樹(shù)，相當(dāng)于搜索左半?yún)^(qū)間；x[i]的取值為1時(shí)則搜索其右子樹(shù)，相當(dāng)于搜索左半?yún)^(qū)間；可見(jiàn)隨著樹(shù)的逐層展開(kāi)將對(duì)定義域進(jìn)行了更精細(xì)的劃分[4]。

圖2給出了解空間的搜索樹(shù)結(jié)構(gòu)：其中標(biāo)注了任何一個(gè)節(jié)點(diǎn)所對(duì)應(yīng)區(qū)間的左端點(diǎn)值的二進(jìn)制表示，當(dāng)我們用區(qū)間端點(diǎn)值近似表示區(qū)間中的任意值時(shí)其誤差為，i=1～k為節(jié)點(diǎn)所在的深度，當(dāng)我們搜索的深度足夠大時(shí)，該誤差可以控制到任意??；因此當(dāng)我們用這些值做為搜索最值的侯選點(diǎn)時(shí)，不失一般性可以保證結(jié)果的有效性。由此可得我們可以通過(guò)所要求的精度來(lái)控制樹(shù)的深度：關(guān)于k的取值問(wèn)題，在給定模型截?cái)嗾`差ε的基礎(chǔ)上，k通過(guò)以下方式定義：

圖2 解空間的搜索樹(shù)結(jié)構(gòu)

1.3 引入模擬退火思想的剪枝算法

回溯法在問(wèn)題的解空間樹(shù)中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹(shù)。算法搜索至解空間樹(shù)的任意一點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)是否包含問(wèn)題的解。如果肯定不包含，則跳過(guò)對(duì)該結(jié)點(diǎn)為根的子樹(shù)的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹(shù)，繼續(xù)按深度優(yōu)先策略搜索，其用于求最小值遞歸實(shí)現(xiàn)的偽代碼如下：

上述代碼中if（constraint（t）&&bound（t））backtrack（t+1）表示在遞歸搜索各棵子樹(shù)之前要有解的可行性測(cè)試和界限測(cè)試，它們構(gòu)成了剪枝條件，針對(duì)不同的應(yīng)用設(shè)計(jì)剪枝條件是用好回溯法的極大挑戰(zhàn)。在本文探討的搜索函數(shù)極大（小）值的應(yīng)用中，可行性測(cè)試比較容易表達(dá)，因?yàn)橐粋€(gè)特定的值是否被選擇是個(gè)簡(jiǎn)單測(cè)試問(wèn)題；界限測(cè)試則非常核心和難以刻畫，因?yàn)榻缦逌y(cè)試要回答當(dāng)前子樹(shù)是否存在潛在最優(yōu)解的問(wèn)題，相當(dāng)于要回答最優(yōu)解是否會(huì)落入某個(gè)區(qū)間之中，這肯定是沒(méi)有一般表達(dá)的。本文引入模擬退火算法來(lái)設(shè)計(jì)一種依概率剪枝條件。

模擬退火算法（Simulated Annealing，SA）是一種模擬物理學(xué)中固體退火過(guò)程的隨機(jī)優(yōu)化算法，于1983年由Kirkpatrick S，Jr G C，Vecchi M P等人[5]設(shè)計(jì)提出并應(yīng)用于組合優(yōu)化領(lǐng)域。該算法在搜索最優(yōu)解的過(guò)程中引入隨機(jī)因素，以一定概率接受一個(gè)不優(yōu)于當(dāng)前解的解，通過(guò)這種隨時(shí)間而變化并且最終趨于零的概率突變性，能一定程度地避免陷入局部最優(yōu)，具有漸進(jìn)收斂性[6]。

在模擬退火算法中，判斷是否接受新解的依據(jù)是Metropolis準(zhǔn)則。不失一般性，假設(shè)我們要求最小值，假定問(wèn)題的當(dāng)前解為S0，新解為S1，C（S）為目標(biāo)函數(shù)。若C（S1）〈C（S0），則接受S1作為新的當(dāng)前解；若C（S1）≥C（S0），則以概率p接受S1作為新的當(dāng)前解。概率p的定義如下：

其中，T代表當(dāng)前溫度，每個(gè)溫度在進(jìn)行若干次判斷迭代后會(huì)逐漸減少，并最終趨于零。

在本文的函數(shù)求解模型中，將基于模擬退火算法的思想，對(duì)上小節(jié)的遍歷搜索進(jìn)行改進(jìn)。引入模擬退火算法思想的剪枝，是指搜索當(dāng)前區(qū)間對(duì)應(yīng)的子樹(shù)時(shí)，新產(chǎn)生的分點(diǎn)作為新解與當(dāng)前解進(jìn)行Metropolis準(zhǔn)則測(cè)試，拒絕了新解則被拒絕的分點(diǎn)所在子區(qū)間對(duì)應(yīng)的子樹(shù)不用搜索，即對(duì)子樹(shù)進(jìn)行了剪枝，從而節(jié)省了用于搜索一個(gè)子區(qū)間的時(shí)間，這也是為何剪枝條件設(shè)計(jì)是提高搜索效率的原因。由于模擬退火算法具有隨機(jī)性，為保證模型結(jié)果的穩(wěn)定性，我們將從第k0+1層開(kāi)始，對(duì)滿二叉樹(shù)進(jìn)行剪枝，經(jīng)過(guò)大量實(shí)驗(yàn)得到k0=×k可滿足大多數(shù)應(yīng)用。k由公式（3）確定，這樣保證了我們所拒絕搜索的子區(qū)間是可以控制它們的長(zhǎng)度的。

關(guān)于k0的確定問(wèn)題的探討：當(dāng)k0=1時(shí)算法退化為模擬退火算法，過(guò)于強(qiáng)調(diào)隨機(jī)機(jī)制從而造成求解的不穩(wěn)定性；當(dāng)k0=k時(shí)算法退化為窮舉搜索算法，從而增加了時(shí)間復(fù)雜度。k0的選取主要考慮以下兩個(gè)方面。一方面，為保證模型結(jié)果的穩(wěn)定性，k0的取值不宜過(guò)小，若選取了一個(gè)較小的k0值，則模型則會(huì)很快進(jìn)入剪枝階段，對(duì)于高頻震蕩型函數(shù)易陷入局部最小值。另一方面，k0的取值不宜過(guò)大，若選取了一個(gè)較大的k0值，將面臨模型運(yùn)行時(shí)間過(guò)長(zhǎng)的問(wèn)題。

可見(jiàn)本文的算法是先進(jìn)性不剪枝的確定搜索，保證搜索不會(huì)遺漏地進(jìn)入每一個(gè)長(zhǎng)度為，i=1～k0的區(qū)間，在進(jìn)入到長(zhǎng)度為（i大于等于k0）的區(qū)間進(jìn)行更精細(xì)搜索時(shí)才進(jìn)行隨機(jī)剪枝，以一定的概率跳過(guò)對(duì)更小區(qū)間的搜索，能夠兼顧精度和效率。

2 用本文方法求函數(shù)極值的算法實(shí)現(xiàn)流程

經(jīng)過(guò)前面的準(zhǔn)備工作之后，下面開(kāi)始介紹函數(shù)極值求解模型的構(gòu)建流程。本小節(jié)將主要介紹一元函數(shù)的極值求解，該問(wèn)題在多元函數(shù)上的推廣將在后面介紹。現(xiàn)假定實(shí)際問(wèn)題抽象得到的模型函數(shù)記為：

本文算法主要由以下兩個(gè)階段構(gòu)成：定位階段和剪枝階段。

定位階段是指在深度小于k0時(shí)所進(jìn)行的不剪枝的確定性搜索。圖3展示了該算法在定位階段的操作流程，二叉樹(shù)的根結(jié)點(diǎn)代表全區(qū)間，每次二分一個(gè)區(qū)間，左半?yún)^(qū)間對(duì)應(yīng)左子樹(shù)，右半?yún)^(qū)間對(duì)應(yīng)右子樹(shù)，其中括號(hào)中給出了區(qū)間左端點(diǎn)的值的二進(jìn)制表示和十進(jìn)制表示，因此搜尋每個(gè)數(shù)的過(guò)程對(duì)應(yīng)該二叉樹(shù)中的一條路徑，而回索法則通過(guò)深度優(yōu)先的方式遍歷各路經(jīng)從而實(shí)現(xiàn)解的搜索。

圖3 函數(shù)極值求解模型的定位階段

在定位階段進(jìn)行深度為k0的深度優(yōu)先搜索，為降低時(shí)間復(fù)雜度僅對(duì)各結(jié)點(diǎn)的右孩子函數(shù)值的更新操作，因?yàn)樽蠛⒆铀a(chǎn)生的區(qū)間端點(diǎn)并非新的值。在圖3中，方型結(jié)點(diǎn)將與當(dāng)前解作函數(shù)值大小的比較判斷，圓形結(jié)點(diǎn)則不進(jìn)行該操作。

定位操作發(fā)生在搜索樹(shù)的第1至k0層，從第k0+1至k層進(jìn)行剪枝操作，其中k0=×k，k由公式（3）確定。也就是說(shuō)在定位階段是對(duì)深度為k0的搜索樹(shù)進(jìn)行的深度優(yōu)先搜索，在這個(gè)過(guò)程中不進(jìn)行隨機(jī)剪枝可有效保證解的精度。但是，如果整棵樹(shù)的搜索過(guò)程中都不進(jìn)行剪枝，則算法復(fù)雜度太高，因此從第k0+1至k層進(jìn)行剪枝操作，也就是說(shuō)在深度大于k0子樹(shù)中搜索時(shí)則引入1．3節(jié)介紹的剪枝操作，因此下面的過(guò)程針對(duì)當(dāng)前要進(jìn)行剪枝操作的任意一棵深度大于k0子樹(shù)。

在剪枝階段，同樣的道理僅對(duì)各結(jié)點(diǎn)的右孩子進(jìn)行操作。剪枝規(guī)則定義如下：

（1）若f（x1）〈f（xmin），則接受x1為新的極小值點(diǎn)，不進(jìn)行剪枝操作，繼續(xù)對(duì)子樹(shù)的深度優(yōu)先搜索。

①若p＞ξ，則不進(jìn)行剪枝操作；

②若p≤ξ，則進(jìn)行剪枝操作。

其中，xmin為當(dāng)前極小值點(diǎn)，x1為待判斷的新點(diǎn)，f為目標(biāo)函數(shù)，i為x1對(duì)應(yīng)結(jié)點(diǎn)在滿二叉樹(shù)中的層數(shù)，用w[i]=作為模擬退火算法的溫度值，這也是本文經(jīng)大量實(shí)驗(yàn)得出的有效選擇。ξ∈[0，1]為隨機(jī)數(shù)。圖4展示了該模型在剪枝階段的操作流程。

圖4 函數(shù)極值求解模型的剪枝階段

上面的流程是針對(duì)一元函數(shù)設(shè)計(jì)的，下面的探討將針對(duì)多元函數(shù)極值求解進(jìn)行推廣。為便于理解，以下將以二元函數(shù)為例，對(duì)于三元或以上的函數(shù)，可以通過(guò)相似的步驟實(shí)現(xiàn)?，F(xiàn)假定實(shí)際問(wèn)題抽象得到的模型函數(shù)記為

其中，D={（x1，x2）∈R2|0≤x1≤1，0≤x2≤1}。

為達(dá)到模型精度要求，由公式（3）求得k值后，將構(gòu)建一棵層數(shù)為2k的滿二叉樹(shù)。模型同樣由兩個(gè)階段構(gòu)成：定位階段和剪枝階段。

在定位階段，先對(duì)定義域各端點(diǎn)作比較，取其最小者作為初始極小值點(diǎn)，在二元函數(shù)中，有以下四個(gè)端點(diǎn)（0，0）、（0，1）、（1，0）和（1，1）。然后，在對(duì)滿二叉樹(shù)搜索的過(guò)程中，以兩層為單位，在奇數(shù)層對(duì)x1的取值進(jìn)行試探，在偶數(shù)層對(duì)x2的取值進(jìn)行試探，如圖5所示，結(jié)點(diǎn)下括號(hào)內(nèi)左數(shù)值代表變量x1的取值（二進(jìn)制表示）；右數(shù)值代表變量x2的取值（二進(jìn)制表示）。同樣的，僅各層結(jié)點(diǎn)的右孩子進(jìn)行比較判斷。

定位操作發(fā)生在搜索樹(shù)的第1至k0層，從第k0+1至k層進(jìn)行剪枝操作，其中k0=×2×k。在剪枝階段，剪枝規(guī)則與一元函數(shù)相似，這里不再贅述。

3 實(shí)證分析

3.1 實(shí)驗(yàn)所選函數(shù)簡(jiǎn)介

在該小節(jié)，主要介紹用于測(cè)試本文算法效果的各個(gè)實(shí)驗(yàn)函數(shù)。為確保算法的泛化能力，實(shí)驗(yàn)函數(shù)將盡可能地涵蓋不同的類型。如表1所示，在一元函數(shù)極值求解模型中，有六個(gè)函數(shù)用于測(cè)試，函數(shù)類型與函數(shù)特點(diǎn)不盡相同，圖6為各函數(shù)對(duì)應(yīng)圖像。

對(duì)于多元函數(shù)的實(shí)驗(yàn)測(cè)試，這里選用了一個(gè)二元函數(shù)，其定義如下：

統(tǒng)計(jì)并記錄兩組患者的血糖水平，包括空腹血糖、餐后2 h血糖水平、不良妊娠結(jié)果。其中不良妊娠結(jié)果包括早產(chǎn)、死產(chǎn)、感染、剖宮產(chǎn)。

其對(duì)于函數(shù)圖像如下：

圖5 二元函數(shù)極值求解模型的定位階段

3.2 算法效用分析

在一元函數(shù)極值求解的實(shí)驗(yàn)中，取精度ε1= 0.0000001，根據(jù)公式（3）計(jì)算可知，k1=24。在二元函數(shù)的實(shí)驗(yàn)中，ε2=0.0001，k2=14。

（1）穩(wěn)定性分析

前面分析中提到隨機(jī)搜索是一種不穩(wěn)定的算法，因此下面的實(shí)驗(yàn)對(duì)比本文方法和模擬退火算法的穩(wěn)定性在實(shí)驗(yàn)環(huán)節(jié)，各算法將在不同函數(shù)上各運(yùn)行10次，觀測(cè)各次求解得到的極小值是否一致，以本文算法在y=sinx+cos函數(shù)上的運(yùn)行結(jié)果為例，通過(guò)表2可知，10次運(yùn)行求得的極小值點(diǎn)相同，具有較強(qiáng)的穩(wěn)定性。在其余5個(gè)一元函數(shù)上，該算法均表現(xiàn)十分穩(wěn)定。

表1 實(shí)驗(yàn)所選一元函數(shù)的簡(jiǎn)要介紹

圖6 本實(shí)驗(yàn)涉及的一元函數(shù)圖像

圖7 本實(shí)驗(yàn)涉及的二元函數(shù)圖像

需要注意的是，穩(wěn)定性與k0的選取有關(guān)，若k0的值過(guò)小，則有可能出現(xiàn)極小值點(diǎn)不同的情況，影響模型精度。

表2 本文模型在y=sinx+cos函數(shù)上的運(yùn)行結(jié)果

表2 本文模型在y=sinx+cos函數(shù)上的運(yùn)行結(jié)果

（2）精度分析與運(yùn)行時(shí)間分析

搜索算法的時(shí)間復(fù)雜度取決于其侯選搜索空間的設(shè)定，為了能對(duì)比不同搜索算法的時(shí)間復(fù)雜度，我們約定用各算法完成對(duì)相同搜索空間的搜索時(shí)間，本實(shí)驗(yàn)中對(duì)一元函數(shù)取精度ε1=0.0000001，根據(jù)公式（3）計(jì)算可知，樹(shù)的深度k1=24。在二元函數(shù)的實(shí)驗(yàn)中，取ε1= 0.0001，樹(shù)的深度k1=14。

在該環(huán)節(jié)，將取10次實(shí)驗(yàn)的眾數(shù)用于精度的考察，實(shí)驗(yàn)時(shí)間均數(shù)用于運(yùn)行時(shí)間的考察。對(duì)于一元函數(shù)，在減低實(shí)驗(yàn)耗時(shí)上，本文算法優(yōu)于遍歷搜索算法，僅需其約10%的運(yùn)行時(shí)間，六個(gè)函數(shù)中，最短為后者的7.87%，最長(zhǎng)為13.14%，與模擬退火算法相比則兩者相近，本文算法依然有一定優(yōu)勢(shì)。在精度上，本文算法均有很好的表現(xiàn)。表3給出了對(duì)比結(jié)果。

可見(jiàn)本文算法能用更短的時(shí)間找到搜索空間中的最小值，本文設(shè)計(jì)的剪枝策略能夠在不影響精度的情行下降低時(shí)間復(fù)雜度，是一種能兼顧精度穩(wěn)定性和效率的有效方法。

4 結(jié)語(yǔ)

本文在遍歷搜索算法的基礎(chǔ)上，基于模擬退火的思想，通過(guò)對(duì)搜索樹(shù)進(jìn)行剪枝，在保證模型精度的同時(shí)，解決其運(yùn)行時(shí)間過(guò)長(zhǎng)的問(wèn)題。本文結(jié)合遍歷搜索和隨機(jī)搜索，設(shè)計(jì)了一種基于二進(jìn)制編碼的搜索樹(shù)，并引入了基于模擬退火思想的隨機(jī)剪枝算法，在保證精度的基礎(chǔ)上對(duì)搜索樹(shù)進(jìn)行剪枝，從而可以兼顧精度和效率。該算法適用范圍廣，全局性強(qiáng)，能有效處理高精度函數(shù)極值求解問(wèn)題，能有效推廣至多元函數(shù)。算法的改進(jìn)方向?yàn)槿绾问沟迷撃Ｐ湍芨玫靥幚砀哳l震蕩函數(shù)，進(jìn)一步地，考慮實(shí)現(xiàn)模型的并行化，更大程度地優(yōu)化運(yùn)行時(shí)間。

表3 三種方法在精度與耗時(shí)上的比較

[1]Brent，Richard.P.，Algorithms for Minimization Without Derivatives，Prentice-Hall，Englewood Cliffs，New Jersey，1973.

[2]Forsythe，G.E.，M.A.Malcolm，C.B.Moler.Computer Methods for Mathematical Computations，Prentice-Hall，1976.

[3]鄧東皋，尹小玲.數(shù)學(xué)分析簡(jiǎn)明教程.上冊(cè)[M].高等教育出版社，1999.

[4]王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析[M].電子工業(yè)出版社，2012.

[5]Kirkpatrick S，Jr G C，Vecchi M P.Optimization by Simulated Annealing[J].Science，1983，220（4598）:671-80.

[6]Van Laarhoven P J M，Aarts E H L.Simulated Annealing:Theory and Applications[J]，1987，37（1）:108-111.

A Pruning Method for Accelerating to Search Function Extremum

LU Wei-rong，ZHANG Lei

（School of Mathematics，Sun Yat-sen University，Guangzhou 510275）

There are many optimization problems in practical applications that can be abstracted and simplified to search the function extremum. However，the problem that the function is not differentiable or its derivative is difficult to compute limits the use of exact methods.The traversal search，one of the numerical methods，can be used to search the high-precision extremum.To solve its problem of running too long，the search tree will be pruned based on the idea of simulated annealing in the case of ensuring the model accuracy.The model can be extended to multivariate function，which has the advantages of wide applicability and strong global character.To ensure the practical significance of the model，various types of functions will be used to test in the experimental part.

Function Extremum Search;Traversal Search;Simulated Annealing;Numerical Methods

1007-1423（2017）11-0003-07

10.3969/j.issn.1007-1423.2017.11.001

盧偉榮（1993-），男，廣東東莞人，碩士生，研究方向?yàn)槿斯ぶ悄?/p>

2017-01-10

2017-03-10

張磊（1964-），女，湖北羅田人，副教授，研究方向?yàn)閿?shù)據(jù)分析