[科普中國(guó)]-爬山法

概念

解多變量無(wú)約束最優(yōu)化問(wèn)題的一類方法。有的書(shū)上稱直接法或直接搜索法，是通過(guò)點(diǎn)的直接移動(dòng)產(chǎn)生的目標(biāo)值有所改善的點(diǎn)，經(jīng)過(guò)這樣的移動(dòng)，逐步到達(dá)使目標(biāo)函數(shù)最優(yōu)的點(diǎn)。如果我們把目標(biāo)函數(shù)的幾何圖形看成一個(gè)山峰，那么點(diǎn)的直接移動(dòng)就像人在爬山，選擇方向，逐步向山頂移動(dòng)。目前有軸向搜索法、單純形調(diào)優(yōu)法、Powell法等。軸向搜索法是以沿坐標(biāo)軸方向移動(dòng)為基礎(chǔ)的搜索方法，在進(jìn)行每一輪沿坐標(biāo)軸方向搜索時(shí)，是從一參考點(diǎn)出發(fā)，依次沿平行于各個(gè)坐標(biāo)軸方向連續(xù)作對(duì)應(yīng)的目標(biāo)函數(shù)值改進(jìn)的搜索移動(dòng)，并以最后獲得的點(diǎn)作為下一輪迭代點(diǎn)。同時(shí)，為提高求解的效率．還要采取某些加快收斂的措施。1

問(wèn)題求解的過(guò)程就是努力溝通問(wèn)題的起始狀態(tài)和目標(biāo)狀態(tài)之間的聯(lián)系鏈條，由起始狀態(tài)出發(fā)，逐步向目標(biāo)推移、逼近的過(guò)程。在思維課題的求解活動(dòng)中，人們幾乎總是一直關(guān)注著所要達(dá)到的最終目標(biāo)，試圖不斷地向目標(biāo)逼近。這就像在登山活動(dòng)中運(yùn)動(dòng)員時(shí)刻把頂峰放在心目之中，力圖接近它、占領(lǐng)它一樣。在解決思維課題時(shí)，我們經(jīng)常自覺(jué)或不自覺(jué)地運(yùn)用著能夠盡量向目標(biāo)靠攏的方法。這也就是通常所說(shuō)的爬山法。2

步驟簡(jiǎn)單地說(shuō)，爬山法就是按照下述原則進(jìn)行試探的方法。這就是在每一狀態(tài)下都選取這樣的步驟進(jìn)行試探：由這個(gè)步驟所達(dá)到的終結(jié)狀態(tài)是所有可容許步驟所能達(dá)到的終結(jié)狀態(tài)中，最接近最終目標(biāo)的一個(gè)。這樣的步驟稱為最優(yōu)步驟。按照這樣的原則依次選取步驟，順序試探下去，直到最終目標(biāo)為止。如果達(dá)不到最終目標(biāo)，可以回過(guò)頭來(lái)，從已經(jīng)經(jīng)歷過(guò)的某一中間狀態(tài)開(kāi)始，改用直接效果稍差一點(diǎn)的次優(yōu)步驟，沿著另一條分支途徑再行試探下去。當(dāng)然，也可以一下子回轉(zhuǎn)到整個(gè)問(wèn)題的起始狀態(tài)，沿著另一條全新的途徑進(jìn)行試探。到底應(yīng)當(dāng)返回到什么狀態(tài)開(kāi)始另行試探，這要由解題者根據(jù)具體情況作出自己的判斷。2

與中途法關(guān)系爬山法與中途點(diǎn)法是彼此接近的方法。中途點(diǎn)法在實(shí)質(zhì)上也就是通過(guò)一個(gè)個(gè)的中途點(diǎn)而向最終目標(biāo)逼近的方法。同時(shí)，在問(wèn)題求解活動(dòng)中，這兩種方法也是緊密相聯(lián)．可以配合使用的。比如，有一個(gè)數(shù)學(xué)問(wèn)題，要求決定兩個(gè)量v，u之間的關(guān)系。我們可以把求出包含v，u的關(guān)系式(其中可以含有其他未知量)和求出只包含v，u和已知量的關(guān)系式作為兩個(gè)中途點(diǎn)，把整個(gè)求解過(guò)程區(qū)分為三個(gè)小階段。在每個(gè)小階段中又可分別應(yīng)用爬山法來(lái)進(jìn)行試探。在第一階段中，那些能夠得出同時(shí)把v，u包括進(jìn)去的關(guān)系式的步驟將被看做是較優(yōu)的步驟；而能夠得出既把v，u同時(shí)包含在內(nèi)，又含有最少的其他未知量，并且顯得比較簡(jiǎn)單．對(duì)其他未知量容易加以分離、代換和消除的關(guān)系式的步驟就是最優(yōu)步驟。在第二階段中，那些能夠消除其他未知量個(gè)數(shù)最多的步驟將是最優(yōu)步驟。把爬山法同中途點(diǎn)法結(jié)合起來(lái)運(yùn)用，可以更好地發(fā)揮它們的作用。2

特點(diǎn)爬山法要求人們?cè)谕蒲莸拿恳徊缴献鞒鼍植啃缘暮侠磉x擇．為進(jìn)行試探提供了作出衡量、判別的一種原則，使試探工作能具有更明顯的條理性和某種程度上的程序性與可操作性。在問(wèn)題求解活動(dòng)中．人們也往往是自覺(jué)或不自覺(jué)地運(yùn)用著爬山法的原則。不過(guò)，盡管爬山法有著相當(dāng)廣泛的應(yīng)用，但卻并非是總能奏效的，因?yàn)樗灿兄黠@的弱點(diǎn)和局限性。

首先，在許多思維課題的求解活動(dòng)中，我們既無(wú)法具體地開(kāi)列出從某一狀態(tài)出發(fā)的所有容許推演步驟，更難以判定在這些步驟所得出的各種終結(jié)狀態(tài)中哪一個(gè)同最終目標(biāo)最為接近。例如，在求證某一幾何命題時(shí)，一般情況下，我們并不清楚可以運(yùn)用哪些幾何定理，能夠作出哪些輔助圖形，更難以從各種推演步驟所可能得出的結(jié)果中把最接近于最終目標(biāo)的結(jié)果選取出來(lái)。這種狀況的存在，給爬山法的運(yùn)用帶來(lái)了原則性的困難。

其次，解決問(wèn)題的有效思路大多是迂回曲折的。“曲徑通幽處。禪房花木深”。對(duì)于需要充分發(fā)揮思維的創(chuàng)造性功能的問(wèn)題求解來(lái)說(shuō)．幾乎總是需要?dú)v經(jīng)曲折才能找到通向目標(biāo)的路徑。在某些情況下，甚至還需要暫時(shí)沿著同目標(biāo)正相背離的途徑進(jìn)行一段路程，才能夠達(dá)到探隱索幽，揭示事物底蘊(yùn)，覓得待求結(jié)果的目的。與此相反，那些一開(kāi)始就直接向目標(biāo)逼近，能夠帶來(lái)明顯進(jìn)展的路徑，卻有可能把我們引入無(wú)法達(dá)到目標(biāo)的死胡同之中。對(duì)于不少問(wèn)題來(lái)說(shuō)，甚至完全有可能“在解題過(guò)程的末尾困難成堆”?！斑@就像有許許多多小路，你可以沿著這些小路爬到很接近頂峰的地方，卻只有少數(shù)幾條路可以直接通到最高峰。所以爬山法(在解題的意義上)雖然能大大縮小嘗試范圍，卻仍然不是解這類問(wèn)題的好方法。你能用爬山法走完解這類問(wèn)題的大半路程，卻往往在最后時(shí)刻功虧一簣?！?/p>

應(yīng)當(dāng)指出，對(duì)于爬山法同推演路徑的迂回曲折不相適應(yīng)的弱點(diǎn)，我們是可以在一定程度上設(shè)法加以補(bǔ)救的。只要把目光放遠(yuǎn)一些，不是只看到當(dāng)前的一步，而是看到接續(xù)下去的兩步、三步乃至更多的步數(shù)，也就能夠跨越局部存在的迂回曲折，看清楚在較大范圍內(nèi)真正能向上攀登的道路。

人們?cè)谇蠼鈫?wèn)題時(shí)總是要力圖達(dá)到目標(biāo)；但經(jīng)驗(yàn)豐富、眼界開(kāi)闊的人可以看得更遠(yuǎn)一點(diǎn)，審度出欲進(jìn)先退、欲取姑與的曲折關(guān)系。雖然在某一步上遠(yuǎn)離了目標(biāo)，但在第二步、第三步上卻可以前進(jìn)得更多，使先前的損失得到加倍的補(bǔ)償；而不是像沒(méi)有經(jīng)驗(yàn)的人那樣，只能看到眼前的一步。雖然從所采取的那一步來(lái)說(shuō)是前進(jìn)了。但接著下去卻會(huì)很快地面對(duì)絕壁懸崖，陷入走投無(wú)路的困境之中。這就如同下象棋一樣．初學(xué)的人大多老是盯著對(duì)方的棋子，總想多“吃掉”一個(gè)，哪怕是“吃掉”一個(gè)無(wú)足輕重的小卒，也會(huì)一陣沾沾自喜．而無(wú)力認(rèn)識(shí)這一步著法對(duì)以后的著法和整個(gè)棋局帶來(lái)的不良后果。高明的棋手看到的就不止一步。他會(huì)對(duì)兩三步、乃至更多步以后的情況作出判斷。如果接下去幾步之后確實(shí)能夠把對(duì)方置于死地，即使在要著的一步上會(huì)引起車的丟失，也是樂(lè)意為之的。至于在思維課題的求解活動(dòng)中怎樣才能看得更遠(yuǎn)一點(diǎn)，認(rèn)清真正取得進(jìn)展的標(biāo)志，卻并不存在普遍有效的標(biāo)
準(zhǔn)與原則，只能主要憑借自己的經(jīng)驗(yàn)和進(jìn)行洞察與鑒別的能力來(lái)作出判斷。2

應(yīng)用（1）建立一個(gè)描述數(shù)據(jù)庫(kù)變化的單極值函數(shù)，且使極值對(duì)應(yīng)目標(biāo)狀態(tài)；

（2）選取使函數(shù)值增長(zhǎng)最大的那條規(guī)則作用于數(shù)據(jù)庫(kù)；

（3）重復(fù)上步，直到?jīng)]有規(guī)則使函數(shù)值繼續(xù)增長(zhǎng)。