模擬退火算法_第1頁
模擬退火算法_第2頁
模擬退火算法_第3頁
模擬退火算法_第4頁
模擬退火算法_第5頁
已閱讀5頁,還剩21頁未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

第十章模擬退火算法在管理科學(xué)、計(jì)算機(jī)科學(xué)、分子物理學(xué)、生物學(xué)、超大規(guī)模集成電路設(shè)計(jì)、代碼設(shè)計(jì)、圖像處理和電子工程等領(lǐng)域中,存在著大量的組合優(yōu)化問題。例如,貨郎擔(dān)問題、最大截問題、0—1背包問題、圖著色問題、設(shè)備布局問題以及布線問題等,這些問題至今仍未找到多項(xiàng)式時(shí)間算法。這些問題已被證明是NP完全問題。根據(jù)NP完全性理論,除非P=NP,否則所有的NP難問題都不存在多項(xiàng)式時(shí)間算法。但是,這并不意味著問題的終結(jié)。相反,由于這類問題廣泛應(yīng)用性,反而刺激人們以更大的熱情對NP完全問題進(jìn)行研究。為解決這類問題,人們提出了許多近似算法,但這些算法或過于注意個別問題的特征而缺乏通用性,或因所得解強(qiáng)烈地依賴初始解的選擇而缺乏實(shí)用性。模擬退火算法是近年提出的一種適合解大規(guī)模組合優(yōu)化問題,特別是解NP完全問題的通用有效的近似算法,它與以往的近似算法相比,具有描述簡單、使用靈活、運(yùn)用廣泛、運(yùn)行效率高和較少受初始條件限制的優(yōu)點(diǎn),而且特別適合并行計(jì)算,因此具有很大的使用價(jià)值。同時(shí)由于其討論涉及隨機(jī)分析、馬爾可夫鏈理論、漸進(jìn)收斂性等學(xué)科,所以其研究還具有重要的理論意義。10.1模擬退火算法的基本思想10.1.1模擬退火算法的物理背景固體退火過程的物理圖像和統(tǒng)計(jì)性質(zhì)是模擬退火算法的物理背景。在熱力學(xué)與統(tǒng)計(jì)物理學(xué)的研究領(lǐng)域中,固體退火是其重要的研究對象。固體退火是指先將固體加熱至熔化,再徐徐冷卻使之凝固成規(guī)整晶體的熱力學(xué)過程。在高溫狀態(tài)下,液體的分子彼此之間可以自由的移動。如果液體徐徐冷卻,它的分子就會喪失由于溫度而引起的流動性。這時(shí)原子就會自己排列起來而形成一種純晶體,它們依次地朝各個方向幾十億倍于單個原子大小的距離,這個純晶體狀態(tài)就是該系統(tǒng)的最小能量狀態(tài)。有趣的是,對于一個徐徐冷卻的系統(tǒng),當(dāng)這些原子在逐漸失去活力的同時(shí),它們自己就同時(shí)地排列而形成一個純晶體,使這個系統(tǒng)的能量達(dá)到其最小值。這里我們特別強(qiáng)調(diào)在這個物理系統(tǒng)的冷卻過程中,這些原子就“同時(shí)的”把它們自己排列成一個純晶體的。如果一種金屬熔液是被快速的冷卻,則它不能達(dá)到純晶體狀態(tài),而是變成一種多晶體或非晶體狀態(tài),系統(tǒng)處在這種狀態(tài)時(shí)具有較高的能量。模擬退火算法就是模仿上述物理系統(tǒng)徐徐退火過程的一種通用隨機(jī)搜索技術(shù),人們可用馬爾可夫鏈的遍歷理論來給它以數(shù)學(xué)上的描述。在搜索最優(yōu)解的過程中,模擬退火除了可以接受優(yōu)化解外,還用一個隨機(jī)接受準(zhǔn)則(Metropolis準(zhǔn)則)有限地接受惡化解,并使接受惡化解的概率慢慢地趨于零,這使得算法有可能從局部最優(yōu)解中跳出,盡可能找到全局最優(yōu)解,并保證了算法的收斂性。1982年Kirkpatrick等人首次把固體退火與組合極小化聯(lián)系在一起,他們分別用目標(biāo)函數(shù)和組合極小化問題的解替代物理系統(tǒng)的能量和狀態(tài),從而物理系統(tǒng)內(nèi)粒子的攝動等價(jià)于組合極小化問題中解的試探。極小化過程就是:首先在一個高溫(溫度現(xiàn)在就成為一個參數(shù)控制)狀態(tài)下有效的“溶化”解空間,然后慢慢地降低溫度直到系統(tǒng)“晶體”到一個穩(wěn)定解。通過以下示例,我們可以將組合優(yōu)化問題與固體退火進(jìn)行類比:組合優(yōu)化問題固體退火解狀態(tài)最優(yōu)解能量最低狀態(tài)費(fèi)用函數(shù)能量10.1.2模擬退火算法結(jié)構(gòu)模擬退火算法的求解過程如下:隨機(jī)產(chǎn)生初始解,給定初始溫度,令;隨機(jī)產(chǎn)生新解,并計(jì)算函數(shù)增量;若,則接受新解,=,轉(zhuǎn)(2),否則以概率決定是否接受新解。具體方法是:產(chǎn)生0和1之間的一個隨機(jī)數(shù),若,接受新解,否則拒絕新解;重復(fù)第(2)、(3)步若干次,使解接近當(dāng)前溫度下的最優(yōu)解,這相當(dāng)于用足夠慢的速度降溫,以保證在每個溫度時(shí)系統(tǒng)都能處于當(dāng)前溫度下的能量最低狀態(tài);按一定的方式降低溫度,例如=,其中(0,1);若滿足收斂條件,退火過程結(jié)束,否則,轉(zhuǎn)(2)。通常,收斂條件為。理論已證明:只要初始溫度足夠高,退火過程足夠慢,模擬退火算法以概率1收斂到全局最優(yōu)解。10.2模擬退火算法的漸近收斂性10.2.1馬爾可夫鏈理論定義10.1設(shè)為隨機(jī)變量序列,稱在時(shí)刻k處于狀態(tài)i,,S稱為狀態(tài)空間。當(dāng)S中的狀態(tài)數(shù)有限時(shí),稱為有限狀態(tài)空間。若對任意的正整數(shù)n,滿足則稱{X(k)}(k=1,2,…)為馬爾可夫鏈,簡稱馬氏鏈。馬氏鏈具有一種記憶功能,它只記憶前一時(shí)刻的狀態(tài)。上式可以簡單地記成稱為一步轉(zhuǎn)移概率。當(dāng)狀態(tài)空間有限時(shí),稱為有限馬氏鏈,一步轉(zhuǎn)移概率矩陣記為當(dāng)成立時(shí),即從狀態(tài)i移到狀態(tài)j的概率與時(shí)刻n無關(guān),稱馬氏鏈為齊次馬氏鏈。反之,若轉(zhuǎn)移矩陣與時(shí)刻有關(guān),則稱此馬氏鏈為非齊次馬氏鏈。切普曼—柯爾莫哥洛夫方程式:其中表示m步轉(zhuǎn)移概率,即在時(shí)刻n狀態(tài)為i的條件下,經(jīng)過m步轉(zhuǎn)移到達(dá)狀態(tài)j的概率。特別當(dāng)馬爾可夫過程為齊次時(shí)切普曼—柯爾莫哥洛夫方程變成定義10.2如果對狀態(tài)i和j存在某個,使得,既由狀態(tài)i出發(fā),經(jīng)過n次轉(zhuǎn)移以正的概率到達(dá)狀態(tài)j,則稱自狀態(tài)i可達(dá)到狀態(tài)j,并記為。反之若狀態(tài)i不能達(dá)到j(luò),即對于一切,。定義10.3若且,則稱狀態(tài)i和j相通,記為定義10.4設(shè)C為狀態(tài)空間的一個子集,如果從C內(nèi)任一狀態(tài)i不能到達(dá)C外的任何狀態(tài)j,即對則稱C是閉集。定義10.5稱轉(zhuǎn)移矩陣為P的馬爾可夫鏈為不可約的,若,即除了整個狀態(tài)空間構(gòu)成一個閉集外沒有別的閉集,這時(shí)馬氏鏈中的所有狀態(tài)都是相通的。定義10.6稱轉(zhuǎn)移矩陣為p的馬爾可夫鏈為非周期的,若對,集合的最大公約數(shù)為,其中由所有滿足式的整數(shù)n>0組成,且整數(shù)稱為解i的周期。故非周期即指出所有解的周期為1。定理10.1轉(zhuǎn)移矩陣為P的不可約馬氏鏈?zhǔn)欠侵芷诘囊粋€充分條件是:證明:由不可約性可知,對滿足上式的j和有且故其中n=k+l,又由于因而n,n+1均屬于,故由于,故結(jié)論正確。在討論模擬退火算法收斂性的過程中用到的一個重要的分布是平穩(wěn)分布。定義10.7稱轉(zhuǎn)移矩陣為P的有限齊次馬爾可夫鏈的平穩(wěn)分布為向量q,其第i個分量為,其中且。若這樣的平穩(wěn)分布q存在,則該平穩(wěn)分布就是時(shí)解的概率分布。作者不加證明的給出以下重要定理:定理10.2:設(shè)P為有限齊次馬爾可夫鏈的相伴轉(zhuǎn)移矩陣,若該馬氏鏈?zhǔn)遣豢杉s的和非周期的,則其平穩(wěn)分布q存在且由下式唯一確定:(1)其中。根據(jù)模擬退火算法的特點(diǎn),模擬退火算法的數(shù)學(xué)模型可以描述為:在給定鄰域結(jié)構(gòu)后,模擬退火過程是從一個狀態(tài)到另一個狀態(tài)不斷的隨機(jī)游動。我們可以用馬爾可夫鏈描述這一過程。當(dāng)溫度t為一確定值時(shí),兩個狀態(tài)的轉(zhuǎn)移概率定義為(2)其中,表示狀態(tài)集合(解集合)中狀態(tài)的個數(shù)。稱為從i到j(luò)的產(chǎn)生概率。表示在狀態(tài)i時(shí),j狀態(tài)被選取的概率。比較容易理解的是j是i的鄰域,如果在鄰域中等概率選取,則j被選取的概率是(3)稱為接受概率,表示在狀態(tài)i時(shí)產(chǎn)生狀態(tài)j后,接受j的概率,如在模擬退火算法中接受概率是:(4),和分別稱為產(chǎn)生矩陣、接受矩陣和一步轉(zhuǎn)移概率矩陣。上述為模擬退火算法的主要模型。模擬退火算法主要分為兩類。第一類為齊次算法,在(1)中對每一個固定的t,計(jì)算對應(yīng)的馬爾可夫鏈變化,直到一個穩(wěn)定狀態(tài),然后在使溫度下降。第二類是非齊次算法,由一個馬爾可夫鏈組成,要求在兩個相鄰的轉(zhuǎn)移中,溫度t是下降的。無論從實(shí)際和直觀,描述模擬退火過程的馬爾可夫鏈應(yīng)滿足下列條件:(1)可達(dá)性。無論起點(diǎn)如何,任何一個狀態(tài)都可以到達(dá),這樣使我們有達(dá)到最優(yōu)解的可能。(2)漸進(jìn)不依賴起點(diǎn)。由于起點(diǎn)的選擇有非常大的隨機(jī)性,我們的目標(biāo)是達(dá)到全局最優(yōu)解,因此,應(yīng)漸進(jìn)地不依賴起點(diǎn)。(3)分布穩(wěn)定性。包含兩個內(nèi)容:一是當(dāng)溫度不大時(shí),其馬爾可夫鏈的極限分布存在;二是當(dāng)溫度漸進(jìn)0時(shí),其馬爾可夫鏈也存在極限分布。(4)收斂到最優(yōu)解。當(dāng)溫度漸進(jìn)0時(shí),最優(yōu)狀態(tài)的極限分布和為1。下面將從理論上討論這些要求能否達(dá)到。模擬退火算法可以分為齊次和非齊次的,由以上馬氏鏈性質(zhì)的討論,收斂證明沿用下面的過程。10.2.2齊次算法的收斂性(1)在每一個溫度t給出(2)的一步轉(zhuǎn)移概率的一些限定條件,使得轉(zhuǎn)移概率所對應(yīng)的馬氏鏈滿足不可約和非周期。根據(jù)定理4.2,此馬氏鏈在每一溫度t存在平穩(wěn)分布。(2)給出平穩(wěn)分布應(yīng)該滿足的條件,使得當(dāng)溫度漸進(jìn)達(dá)到零度時(shí),平穩(wěn)分布的極限存在,即存在。(3)進(jìn)一步要求平穩(wěn)分布的極限具有全局最優(yōu)解的其中表示最優(yōu)狀態(tài)集合。綜上所述,得到全局性收斂的表達(dá)式對非齊次算法,也需要下面的條件保證其全局收斂性。(1)因?yàn)榉驱R次算法的每一步溫度在變化,因此需要給出一步轉(zhuǎn)移概率的一些限定條件,即需要給出和的限定條件,使得非齊次馬氏鏈能收斂到一個分布。(2)溫度是漸進(jìn)到零度的,即,給出保證達(dá)到全局最優(yōu)解的溫度變化關(guān)系。最終要求。由于組合優(yōu)化問題的狀態(tài)空間是有限的,齊次性是由算法保證的。要達(dá)到定理4.2的條件,需要討論模擬退火算法對應(yīng)的馬氏鏈的不可約性與非周期性,即可先證明模擬退火算法對應(yīng)的馬氏鏈?zhǔn)遣豢杉s和非周期判定定理。定理10.3若對于使得(5)則與模擬退火算法相伴的馬爾可夫鏈?zhǔn)遣豢杉s的。證:由(5)式可得使>0由不可約定義,知定理正確。定理10.4若則與模擬退火算法相伴的馬爾可夫鏈為非周期的。證:因?yàn)橛缮鲜娇傻靡淼米C。定理10.5設(shè)P為有限齊次不可約、非周期馬氏鏈的相伴矩陣,且其分量滿足(6)則該馬氏鏈的平穩(wěn)分布是一給定分布q。證:由定理4.2可知,要證明該馬氏鏈的平穩(wěn)分布存在且由(1)式唯一確定。故只需證明q滿足(1)式即可。由(6)式,有即。證畢。由于在模擬退火算法中,P依賴于控制參數(shù)t,q也取決于t,故常表示成q=q(t)。由于組合優(yōu)化問題的狀態(tài)空間是有限的,齊次性是由算法保證的。要達(dá)到定理4.2的條件,需要討論模擬退火算法對應(yīng)的馬氏鏈的不可約性與非周期性即可,為了進(jìn)一步確定平穩(wěn)分布的形式,還需驗(yàn)證其是否滿足(6)式。(6)稱為細(xì)節(jié)平衡方程,而(1)稱為整體平衡方程。定理10.6設(shè)是組合優(yōu)化問題的某個實(shí)例,P(t)表示由(2)、(3)和(4)式定義的模擬退火算法相伴的轉(zhuǎn)移矩陣。又設(shè)產(chǎn)生矩陣G(t)滿足(5)式,則與模擬退火算法相伴的馬氏鏈具有平穩(wěn)分布q(t),其分量為其中并且(7)特別地,當(dāng)成立時(shí),有(8)證:為了證明本定理,只需證明馬氏鏈的不可約性與非周期性,并且滿足(6)式的細(xì)節(jié)平衡方程即可。先證不可約性。由定理10.3直接得證。再證非周期性。設(shè)由本定理滿足(5)的條件,只要,這樣的i,j,對一定存在。對這樣的i,j,對。于是由定理4.4,該馬氏鏈?zhǔn)欠侵芷诘摹S啥ɡ?.2可知,該馬氏鏈存在唯一的平穩(wěn)分布且由(1)式確定。由定理4.5,我們只需再證q(t)為隨機(jī)的且滿足(6)式的細(xì)節(jié)平衡方程即可。q(t)顯然是隨機(jī)的,而因此q(t)為該馬氏鏈的平穩(wěn)分布。記為整體最優(yōu)解集,。則特別地,當(dāng)成立時(shí),有證畢。此外,由(7)式和(8)式,可得因而這個結(jié)論反映了模擬退火算法的基本性質(zhì),即漸進(jìn)不依賴起點(diǎn)與全局收斂性。對于模擬退火算法中一般的產(chǎn)生概率和接受概率,只要滿足某些條件必能保證算法的漸進(jìn)收斂性,根據(jù)以上的引理和定理,不難得出下列的結(jié)論。定理10.7:設(shè)(S,f)表示組合優(yōu)化問題的某個實(shí)例。并設(shè)與模擬退火算法相伴的轉(zhuǎn)移矩陣由式(2)定義,產(chǎn)生概率和接受概率滿足以下條件:則模擬退火算法所對應(yīng)的馬氏鏈存在平穩(wěn)分布q(t),其分量為且10.2.3非齊次算法的收斂性非齊次算法一步轉(zhuǎn)移概率的形式為:其中,。一步轉(zhuǎn)移概率矩陣為:多步轉(zhuǎn)移概率表示時(shí)刻m在狀態(tài)i,時(shí)刻k在狀態(tài)j的轉(zhuǎn)移概率。齊次算法實(shí)際執(zhí)行時(shí)是有限的,稍作修改,模擬退火算法執(zhí)行的全過程可定義為一個非齊次馬而可夫鏈,從而運(yùn)用非齊次馬而可夫過程的遍歷理論導(dǎo)出更精確的收斂定理。設(shè)是第l個齊次馬而可夫鏈的控制參數(shù),表示該馬氏鏈的長度,表示第k次試驗(yàn)的控制參數(shù),序列定義為即控制參數(shù)取分段常數(shù)。又序列滿足以下條件:于是,與試驗(yàn)次數(shù)k相對的非齊次馬而可夫鏈由無限個長度有限的齊次馬氏鏈拼接而成。這些齊次馬氏鏈的長度可以取得不同,甚至與控制參數(shù)相關(guān)。此時(shí),如何選取控制參數(shù)才能使該非齊次馬氏鏈具有平穩(wěn)分步呢?定義10.8若非齊次馬氏鏈滿足下列條件,則稱為弱遍歷。定義4.8說明,無論起點(diǎn)如何,當(dāng)轉(zhuǎn)移步數(shù)增加時(shí),到達(dá)同一狀態(tài)的概率漸進(jìn)相同。即馬氏鏈的弱遍歷性意味著馬氏鏈的漸進(jìn)收斂性與初始解無關(guān)。這是一種失去記憶的功能。定義10.9若存在向量q,滿足且有則稱非齊次馬氏鏈為強(qiáng)遍歷。定義10.9的意義是馬氏鏈的漸進(jìn)穩(wěn)定性,即具有強(qiáng)遍歷性的馬氏鏈可以收斂到一個隨機(jī)分布。下面給出非齊次馬氏鏈為強(qiáng)遍歷的一個充分條件。定理10.8在溫度t時(shí),一步轉(zhuǎn)移概率按(2)定義,G(t)為且存在,使得,其中,則馬氏鏈為強(qiáng)遍歷,且該馬氏鏈?zhǔn)諗康降碾S機(jī)分布為。其中。類似于定理10.6后半部分的證明,不難得出:非齊次的模擬退火算法在上述的條件下,以概率1收斂到全局最優(yōu)解。即另外,溫度下降的最快速度為10.3冷卻進(jìn)度表10.3.1冷卻進(jìn)度表的概念模擬退火算法的漸進(jìn)收斂性意味著:對于多數(shù)組合優(yōu)問來說算法的執(zhí)行過程只有進(jìn)行無限多次變換后,才能返回一個整體最優(yōu)解。因而作為最優(yōu)化算法,模擬退火算法的執(zhí)行過程不能囿于多項(xiàng)式時(shí)間,而是一種指數(shù)時(shí)間算法,因而無法應(yīng)用于實(shí)際。冷卻進(jìn)度表是一組控制算法進(jìn)程的參數(shù),用于逼近模擬退火算法的漸進(jìn)性態(tài),使算法在執(zhí)行多項(xiàng)式時(shí)間內(nèi)返回一個近似最優(yōu)解。冷卻進(jìn)度表是影響模擬退火算法實(shí)驗(yàn)性能的重要因素,其合理選取是算法應(yīng)用的關(guān)鍵。模擬退火算法漸進(jìn)收斂性的有限時(shí)間通常采用下述方法來實(shí)現(xiàn):用控制參數(shù)的一個遞減有限序列以及與之對應(yīng)鏈長的有限齊次馬爾可夫鏈序列去控制算法進(jìn)程。為此必須確定一個確保算法收斂的參數(shù)集,這個參數(shù)集稱為冷卻進(jìn)度表。組成冷卻進(jìn)度表的參數(shù)集應(yīng)當(dāng)包括:初始溫度、降溫策略、馬爾可夫鏈長度以及停止準(zhǔn)則四個方面。構(gòu)造冷卻進(jìn)度表的核心概念是準(zhǔn)平衡,設(shè)是第k個馬爾可夫鏈的長度,是相應(yīng)的第k個控制參數(shù)。稱模擬退火算法達(dá)到準(zhǔn)平衡,若在第k個馬爾可夫鏈的次抽樣后,解的概率分布充分逼近時(shí)的平穩(wěn)分布。亦即對某些確定的正數(shù)成立。10.3.2冷卻進(jìn)度表的選擇原則任一有效的冷卻進(jìn)度表都必須妥善地解決兩個問題。首先是算法的收斂性問題。根據(jù)熱物理學(xué)平衡態(tài)統(tǒng)計(jì)理論與隨機(jī)過程馬爾可夫鏈理論,模擬退火算法在一定條件下是漸進(jìn)收斂的。但這并不意味著任一冷卻進(jìn)度表都能確保算法的收斂性,不合理的的冷卻進(jìn)度表會使算法在某些解之間“振蕩”而不能收斂于最優(yōu)解。這個問題可以通過以及停止準(zhǔn)則的合理解決加以實(shí)現(xiàn),算法的收斂性顯然取決于和的選擇。其次是模擬退火算法的實(shí)驗(yàn)性能問題。算法的實(shí)驗(yàn)性能一般用兩個指標(biāo)——平均情況下最終解的質(zhì)量和CPU運(yùn)行時(shí)間——來衡量。顯然,模擬退火算法最終解的質(zhì)量與運(yùn)行時(shí)間成反向關(guān)系,很難兩全其美。這個結(jié)論的直觀解釋是:準(zhǔn)平衡量化標(biāo)準(zhǔn)越高,算法進(jìn)程搜索的解空間范圍越大,因而最終解的質(zhì)量也越高,其時(shí)間花費(fèi)理所當(dāng)然也越多。因此算法實(shí)驗(yàn)性能問題的妥善解決只有一種辦法:折中,即在合理的運(yùn)算時(shí)間內(nèi)盡量提高解的質(zhì)量。這種選擇涉及冷卻進(jìn)度表所有參數(shù)的合理選擇。冷卻進(jìn)度表可以根據(jù)經(jīng)驗(yàn)法則(基于上述的折中原則)或理論分析(基于準(zhǔn)平衡概念)選取。經(jīng)驗(yàn)法則從合理的運(yùn)行時(shí)間出發(fā),探索提高最終解的質(zhì)量的途徑,簡單直觀而有賴豐富的實(shí)踐;理論分析由最終解的質(zhì)量入手,尋求縮減運(yùn)行時(shí)間的方法,精細(xì)透徹卻難免繁瑣的推證。只有綜合兩者的優(yōu)勢才能構(gòu)造出較好的冷卻進(jìn)度表。下面就這兩種方法作簡單的介紹。10.3.3經(jīng)驗(yàn)法則(折中原則)①初始溫度的選取基于“值只要充分大,就會立即達(dá)到準(zhǔn)平衡”的論證,為使算法進(jìn)程一開始就達(dá)到準(zhǔn)平衡,應(yīng)讓初始接受率由Metropolis準(zhǔn)則,可推知值很大。例如取,則在時(shí)>949。經(jīng)驗(yàn)法則要求算法進(jìn)程在合理時(shí)間里搜索盡可能大的解空間范圍,只有足夠大的值才能滿足這個要求:Kirkpatrick等在1982年提出的確定值的經(jīng)驗(yàn)法則是:選定一個大值作為的當(dāng)前值并進(jìn)行若干次變換,若接受率小于預(yù)定的初始接受率(Kirkpatrick等取),則當(dāng)前值加倍。以新的當(dāng)前值重復(fù)上述過程,直至得到使的值。這個經(jīng)驗(yàn)法則被許多研究者進(jìn)一步深化。Johnson等建議通過計(jì)算若干次隨機(jī)變換目標(biāo)函數(shù)平均增量的方法來確定值提出由求解,其中表示上述平均增量。因此綜上所述,為使算法進(jìn)程返回一個高質(zhì)量最終解,必須滿足選取“足夠大”的值,而過大的又可能導(dǎo)致較長的運(yùn)行時(shí)間,同時(shí)使模擬退火算法喪失可行性。故要綜合考慮兩方面的因素。②降溫策略降溫策略主要解決溫度的下降速度問題。溫度下降既不能太快也不能太慢。太快會導(dǎo)致解的質(zhì)量下降,類似于固體降溫太快會出現(xiàn)的瑕疵,降溫太慢會導(dǎo)致太長的運(yùn)行時(shí)間,尤其對于問題規(guī)模較大時(shí)。第一種方法是以ln(k)的速率下降,該方法優(yōu)點(diǎn)是有可能使算法收斂到全局最優(yōu)點(diǎn),缺點(diǎn)是下降速率太慢而變的不實(shí)用。第二種方法是根據(jù)費(fèi)用函數(shù)的分布來自動確定的下降速率。這種方法的優(yōu)點(diǎn)是冷卻進(jìn)度僅由問題費(fèi)用函數(shù)的統(tǒng)計(jì)量來確定,擔(dān)這種方法的缺點(diǎn)也是不容忽視的,它假定了的分布是正態(tài)分布,這在實(shí)際應(yīng)用中也不一定成立。第三種是常系數(shù)法,即,其中在0.80和0.99之間,該方法形式簡單,而且對只要求尋找近似最優(yōu)解的問題也足夠有效,因而成為目前最常用的一種方法。③馬爾可夫鏈長度馬爾可夫鏈長度的選擇原則是:在控制參數(shù)t的衰減函數(shù)已選定的前提下,應(yīng)選得在控制參數(shù)的每一取值上都能恢復(fù)準(zhǔn)平衡。在控制參數(shù)的每一次取值的恢復(fù)準(zhǔn)平衡需要進(jìn)行的抽樣次數(shù)可通過恢復(fù)準(zhǔn)平衡至少接受的抽樣次數(shù)來推算。擔(dān)由于抽樣的接受概率隨控制參數(shù)值的遞減而減少,接受固定數(shù)量的變化需進(jìn)行的抽樣次數(shù)隨之增多,最終在時(shí),。為此可用某些常量限定的值,以免在小值時(shí)產(chǎn)生過長的馬爾可夫鏈。表示算法進(jìn)程在第k個馬爾可夫鏈中進(jìn)行的抽樣次數(shù),有限序列{}則規(guī)定了算法進(jìn)程搜索的接空間范圍。由于多數(shù)組合優(yōu)化問題的解空間規(guī)模隨問題規(guī)模n呈指數(shù)增長,為使模擬退火算法最終解的質(zhì)量有所保證,應(yīng)建立與n間的某種關(guān)系。指數(shù)型的關(guān)系是不切合實(shí)際的,因而通常取為問題規(guī)模n的一個多項(xiàng)式函數(shù)。這樣一個多項(xiàng)式函數(shù)可以依據(jù)組合優(yōu)化問題實(shí)例的性質(zhì)、規(guī)模以及處理這些問題的實(shí)踐經(jīng)驗(yàn)加以確定,或直接指定為n的一個多項(xiàng)式函數(shù)例如,或由領(lǐng)域結(jié)構(gòu)間接確定例如(領(lǐng)域規(guī)模)上面已提及,的選取與控制參數(shù)的衰減量密切相關(guān),通常選取的小衰減量而避免過長的馬爾可夫鏈。大量的模擬實(shí)驗(yàn)也表明,過長的馬爾可夫鏈無助于最終解質(zhì)量的提高,而只會導(dǎo)致運(yùn)行時(shí)間的無謂的增加,因此值只應(yīng)選的“適當(dāng)大”。④停止準(zhǔn)則合理的停止準(zhǔn)則既要保證算法的收斂性,又要是最終解具有一定的質(zhì)量。從最終解的質(zhì)量考慮,若能用最終解目標(biāo)函數(shù)的相對誤差(和分別是最終解和最優(yōu)解的目標(biāo)函數(shù)值)作為停止準(zhǔn)則判據(jù)最理想的。但組合優(yōu)化問題的最優(yōu)解往往未知或不可知的,這種理想往難以成真。因此,只有另辟蹊徑。模擬退火算法的漸進(jìn)收斂性給人們以新的啟示:算法收斂于最優(yōu)解集是隨控制參數(shù)t值緩緩減漸進(jìn)的進(jìn)行的。只有在控制參數(shù)終值充分小”時(shí),才有可能得出高質(zhì)量的最終解。故“充分小”在某種程度上可以替代“最終解質(zhì)量”判據(jù),為停止準(zhǔn)則所用。一是讓控制參數(shù)的值小于某個充分小的正數(shù),直接構(gòu)成停止準(zhǔn)則的判斷式;二是算法進(jìn)程的接受率的控制參數(shù)遞減而減小的性態(tài),確定一個終止參數(shù),若算法進(jìn)程的當(dāng)前接受率,就終止算法。從最終解質(zhì)量角度選取停止準(zhǔn)則的另一條途徑是:以算法進(jìn)程所得到的某些近似解為衡量標(biāo)準(zhǔn),判斷算法當(dāng)前的質(zhì)量是否持續(xù)得到明顯的提高,從而確定是否終止算法。譬如,在若干個相繼的馬爾可夫鏈中解無任何變化(含優(yōu)化和惡化)就終止。10.3.4理論分析法上面討論的冷卻進(jìn)度表基于準(zhǔn)平衡概念的直觀近似,稱之為簡單的冷卻進(jìn)度表。對許多組合優(yōu)化問題來說,采用簡單的冷卻進(jìn)度表的模擬退火算法基本可以返回一個符合要求的近似最優(yōu)解。只要冷卻進(jìn)度表的選擇合理,模擬退火算法的實(shí)驗(yàn)性能就會優(yōu)于某些近似算法。但是為了改進(jìn)模擬退火算法對大規(guī)模組合優(yōu)化問題的實(shí)驗(yàn)性能,他們提出了理論分析的方法,采用了一個更精細(xì)的冷卻進(jìn)度表。所謂“精細(xì)”是指與準(zhǔn)平衡量化聯(lián)系的緊密程度。準(zhǔn)平衡概念的恰當(dāng)量化是一項(xiàng)困難的任務(wù),問題在于還沒有掌握準(zhǔn)確確定解的概率分布的充分的統(tǒng)計(jì)資料。下面對精細(xì)的冷卻進(jìn)度表作一簡介。①初始溫度Aarts等人也提出了另一種計(jì)算式,他們的做法是:假定對控制參數(shù)的某個確定值t產(chǎn)生一個m嘗試的序列,并設(shè)和分別是其中目標(biāo)函數(shù)減小和增大的變換數(shù),是次目標(biāo)函數(shù)增大的平均增量。則接受率可用下式近似:由上式可得:只要將設(shè)定為初始接受率,就能求出相應(yīng)的值。需要指出的是Aarts等人的冷卻進(jìn)度表中的位置被初始接受率所取代。②降溫策略Aarts等人首先把準(zhǔn)平衡條件用來替代.上式對某些正數(shù)成立,并假定準(zhǔn)平衡在處達(dá)到且算法進(jìn)程中始終保持。則控制參數(shù)兩個相鄰值上的平穩(wěn)分布相互逼近,且可量化為上式對某些小正數(shù)成立(與準(zhǔn)平衡式中的相關(guān))。然后證明了上式成立的一個充分條件其中,再把上式改寫成最后經(jīng)化簡得的衰減函數(shù)。小的值導(dǎo)致控制參數(shù)t的小的衰減量,反之亦然。在Aarts等人的冷卻進(jìn)度表中參數(shù)稱為距離參數(shù)。③馬爾可夫鏈長度Aarts等人猜想由于上述控制參數(shù)的衰減函數(shù)導(dǎo)致控制參數(shù)兩個相鄰值上的平穩(wěn)分布相互逼近,因此只要在值上達(dá)到準(zhǔn)平衡,那么控制參數(shù)下一取值上的準(zhǔn)平衡只須進(jìn)行少量的抽樣就可迅速逼近。他們假設(shè)這個“少量抽樣”可以指定為,算法能以一個充分大的概率至少訪問給定解大部分領(lǐng)域所需進(jìn)行抽樣的次數(shù)。然后,Aarts等人證明,對基數(shù)為的集合S進(jìn)行N次重復(fù)抽樣,S中不同元素被選中的概率在N和為大值時(shí),可近似為如果模擬退火算法對給定解i產(chǎn)生鏈長為L的馬爾可夫鏈,并假設(shè)在馬爾可夫鏈產(chǎn)生期間沒有接受任一變換,則由上式可知,在馬爾可夫鏈產(chǎn)生過程中解i的不同領(lǐng)域近似解被訪問的概率是其中是領(lǐng)域規(guī)模()。若取,則上述概率近似等于2/3。對于三個相繼的鏈長為的馬爾可夫鏈,這個概率近似等于1,表明解i的整個領(lǐng)域幾乎全被訪問到。于是,Aarts等人在其冷卻進(jìn)度表中,把選定為領(lǐng)域規(guī)模,即④停止準(zhǔn)則在溫度t,定義平衡時(shí)目標(biāo)函數(shù)的期望值為:Aarts等人對控制參數(shù)終值的選取基于期望目標(biāo)函數(shù)在時(shí)的外推。設(shè)則當(dāng)小于處的期望目標(biāo)函數(shù)值時(shí),就終止算法。而對于充分大的值,有而。因此對t《1,可近似為于是能夠可靠地終止算法,若對某些成立,其中是某些小正數(shù)。Aarts等人把上式稱為停止準(zhǔn)則。10.4模擬退火算法的應(yīng)用模擬退火算法具有廣泛的應(yīng)用性,可用于求解許多組合優(yōu)化問題。根據(jù)模擬退火算法的過程(產(chǎn)生新解——計(jì)算目標(biāo)函數(shù)差——判別是否接受新解——接受或舍棄新解),在算法的實(shí)際應(yīng)用中必須解決好三個問題:第一,問題的數(shù)學(xué)描述;第二,新解的產(chǎn)生和接受機(jī)制;第三,冷卻進(jìn)度表的選取。其中第三個問題在上面已經(jīng)討論過了,此處不再贅述。此外,還必須有一個隨機(jī)數(shù)產(chǎn)生器。問題的描述主要包括解空間和目標(biāo)函數(shù)兩部分。解空間為所有可行解(有時(shí)也包含不可行解)的集合它限定了初始解選取和新解產(chǎn)生的范圍。對于無約束優(yōu)化問題,任一可能解即為可行解;對于有約束優(yōu)化問題,解集中還可以包含一些不可行解,同時(shí)在目標(biāo)函數(shù)中加上懲函數(shù),以懲罰出現(xiàn)的不可行解。新解的產(chǎn)生和接受可分為四個步驟:第一,給出新解的變換方法,得到一個產(chǎn)生裝置,以從當(dāng)前解產(chǎn)生一個新解;第二,計(jì)算新解和當(dāng)前解的目標(biāo)函數(shù)差,由于目標(biāo)函數(shù)差僅由變換部分產(chǎn)生,因此,通常按增量計(jì)算目標(biāo)函數(shù)差;第三,判斷新解是否被接受,判斷的依據(jù)是米特羅波利斯準(zhǔn)則,對于有約束優(yōu)化問題往往還伴隨有新解可行性的判斷;第四,接受或舍棄新解,若接受,用新解代替當(dāng)前解,同時(shí)修正目標(biāo)函數(shù)值,否則當(dāng)前解與目標(biāo)函數(shù)值保持不變。下面僅對幾個典型的組合優(yōu)化問題給出實(shí)現(xiàn)的算法描述,以揭示其建立數(shù)學(xué)模型和新解產(chǎn)生裝置的基本方法。10.4.1旅行商問題(TSP)設(shè)有n個城市和距離矩陣D=[],其中表示城市i到城市j的距離,i,j=1,…,n,尋找遍訪每個城市恰好一次的一條回路,且其路徑長度為最短。求解的模擬退火算法描述如下:①解空間解空間S可表為{1,2,…,n}的所有循環(huán)排列的集合,即S={(,…,)|(,…,)為(1,2,…,n)的循環(huán)排列},其中每一循環(huán)排列表示遍訪n個城市的一條回路,=j表示在第i個次序訪問城市j,并約定=。初始解可選為(1,2,…,n)。②目標(biāo)函數(shù)此時(shí)的目標(biāo)函數(shù)即為訪問所有城市的路徑長度或稱為代價(jià)函數(shù),須求其最小值,選為f(,…,)=其中=。③新解的產(chǎn)生(2變換法)任選訪問的序號u和v,逆轉(zhuǎn)u和v及其之間的訪問順序,此時(shí)新路徑為(設(shè)u<v)……④代價(jià)函數(shù)差伴隨新解的代價(jià)函數(shù)差可由公式f=(+)-(++)計(jì)算。特別地,當(dāng)問題為對稱的,即距離矩陣D=[]為對稱矩陣時(shí),因?yàn)?上式可簡化為10.4.20-1背包問題(ZKP)給定一個可裝重量M的背包n件物品,物品i的重量和價(jià)值分別為和,i=1,,n。要選若干件物品裝人背包,使其價(jià)值之和最大。求解的模擬退火算法描述如下:①解空間ZKP是一個有約束的優(yōu)化問題。為此,我們限定解空間為所有可行解的集合,即S={()|}其中表示物品i被選擇裝入背包。初始解選為(0,…,0)。②目標(biāo)函數(shù)為一需求最大值的代價(jià)函數(shù)但必須滿足約束,i=1,…,n.③新解的產(chǎn)生隨機(jī)選取物品i。若i不在背包中,則將其直接裝入背包,或同時(shí)從背包中隨機(jī)取出另一件物品j。若i已在背包中,則將其取出,同時(shí)隨機(jī)裝入另一件物品j。即④背包價(jià)值差及重量差根據(jù)產(chǎn)生新解的三種可能,伴隨的背包代價(jià)差為為判定解的可行性,還需要求出對應(yīng)的背包重量差為其中為當(dāng)前背包重量m的增重⑤接受準(zhǔn)則是擴(kuò)充了可行性測定的馬爾可夫鏈準(zhǔn)則其中和分別由四中的兩式計(jì)算。10.4.3最大截問題(MCP)給定帶權(quán)圖G={V,E},其中為頂點(diǎn)集合,E為邊集,權(quán)矩陣為。要將V劃分為子集和,使E中所有頂點(diǎn)分屬和的權(quán)之和最大。①解空間可表為V的所有劃分為兩子集和分劃的集合,即其中分劃表示頂點(diǎn)。初始解選為。②目標(biāo)函數(shù)直接取為分劃所得得到的截量的相反數(shù)需求其最小值。即相應(yīng)截量的最大值。③新解的產(chǎn)生任選頂點(diǎn),將其從目前所在的子集移到另一個子集中去,即:。④目標(biāo)函數(shù)差根據(jù)目標(biāo)函數(shù)和產(chǎn)生新解的方法可知,相應(yīng)于目標(biāo)函數(shù)差為10.4.4獨(dú)立集問題(ISP)設(shè)有圖G=(V,E),為頂點(diǎn)集。要找V的最大獨(dú)立集,即找最大的,滿足時(shí)必有。模擬退火算法的求解形式為:①解空間取V的冪集,即V的所有子集的集合注意到解空間S中可能含有不可行解,即可能存在V的子集,但并非獨(dú)立集,初始解為。如此構(gòu)造解空間可以使得產(chǎn)生新解的方法簡便,同時(shí)使算法可以從一個局部最優(yōu)的可行解變換為稍差的不可行解,以增大“逃離”局部最優(yōu)“陷阱”的概率。當(dāng)然,這會使目標(biāo)函數(shù)的構(gòu)造變的復(fù)雜一些。②目標(biāo)函數(shù)為“懲罰”可能出現(xiàn)的不可行解,將目標(biāo)函數(shù)選為其中表示點(diǎn)集的元素個數(shù),表示邊集的元素個數(shù)。是一個大于1的懲罰因子,用于“懲罰”在中存在的邊。注意到時(shí),恰好是獨(dú)立集的元素個數(shù)。③新解的產(chǎn)生通過任選頂點(diǎn),當(dāng)時(shí)將其移出,而時(shí)則將其移入來產(chǎn)生,即其中為集特征函數(shù),定義為:④目標(biāo)函數(shù)差設(shè)表示圖G的鄰接矩陣,表示頂點(diǎn)與鄰接,即,且。則伴隨新解的目標(biāo)函數(shù)差為即10.4.5調(diào)度問題(SCP)有n個相互獨(dú)立的任務(wù),所需時(shí)間分別為,均可由m臺機(jī)器中的一臺完成,且每臺機(jī)器一次僅可完成一項(xiàng)任務(wù),要找一個最小調(diào)度,即找對n個任務(wù)的一個調(diào)度,使完成所有任務(wù)的時(shí)間最短。求解的模擬退火算法為①解空間一個調(diào)度可看成對正數(shù)集的一個分劃因此解空間可由所有可能的分劃組成,即初始解可選為。②目標(biāo)函數(shù)SCP是要使分劃的誅子集中的各正數(shù)的和的最大值為最小,即需求的最小值,易證其最小值對應(yīng)于的最小值。所以劃分的目標(biāo)函數(shù)可定義為但此時(shí)求出的最小值并非所得調(diào)度的實(shí)際需要時(shí)間。③新解的產(chǎn)生任選,將其移到任選的另一個子集中去,即它對應(yīng)于將所需時(shí)間為t的任務(wù)從機(jī)器調(diào)到機(jī)器上去完成。④目標(biāo)函數(shù)差由目標(biāo)函數(shù)可得,伴隨于新解的目標(biāo)函數(shù)差為⑤停止準(zhǔn)則的擴(kuò)充與前述問題不同,SCP的目標(biāo)函數(shù)有一個確定且有時(shí)可以達(dá)到的下界它對應(yīng)于所有臺機(jī)器所需時(shí)間均為的情況,即的最小值。此時(shí)的調(diào)度必為一個最小調(diào)度。因此可在停止準(zhǔn)則中加一個形如iff=then停止算法運(yùn)行的判斷。10.4.6圖著色問題(GCP)給定圖G=(G,V),為頂點(diǎn)集,E為邊集。要找G的一個最小著色,即找一個最小的正整數(shù)k和映射,使得,當(dāng)時(shí)有。為了用模擬退火算法求解,首先注意到,若圖G的頂點(diǎn)個數(shù)為n,則圖G的最小著色的上界為n。此外,GCP也是一個有約束的優(yōu)化問題,我們同樣使用懲函數(shù)將其轉(zhuǎn)化為無約束問題。①解空間記將頂點(diǎn)集V劃分為n個子集的任一分劃為則解空間的表為注意到可能存在,且有些分劃可能并非可行解。初始解就選為。②目標(biāo)函數(shù)選為其中表示分劃中非空集合的個數(shù)。為懲函數(shù)因子。顯然的最小值即為最小著色的顏色數(shù)。③新解的產(chǎn)生任選頂點(diǎn),將其從當(dāng)前所在子集移到任選的另一個子集中去。即但限定時(shí)。④目標(biāo)函數(shù)差仍設(shè)為G的鄰接矩陣,則相應(yīng)于新解的目標(biāo)函數(shù)差為其中sgn(x)定義為10.4.7關(guān)于模擬退火算法應(yīng)用的說明上面給出了6個典型的組合優(yōu)化問題的模擬退火算法描述。為了更好的應(yīng)用模擬退火算法,需要作以下幾點(diǎn)說明:(1)上面6個問題都是所謂的NP完全問題,根據(jù)的著名猜測,它們均不存在可行的精確算法。因此,對這類問題尋找高效可行的近似算法有著重要的實(shí)際意義和理論價(jià)值,模擬退火算法就是這樣的近似算法之一。(2)目前人們已發(fā)現(xiàn)千余個NP完全問題,這些NP完全問題中有許多可以用模擬退火算法求解,以上給出的僅僅是其中很小的一個子集。(3)上述算法只是說明模擬退火算法應(yīng)用的基本方法,如解空間的構(gòu)造、目標(biāo)函數(shù)的定義、新解的產(chǎn)生方法、目標(biāo)函數(shù)差的計(jì)算以及接受準(zhǔn)則的應(yīng)用等,其描述較為粗略,在實(shí)際應(yīng)用時(shí)還需作一些技術(shù)上的處理。(4)以上這些算法具有一定的典型性,有些可以推廣使用。如調(diào)度問題(SCP)的算法可以直接求解劃分問題(PAP);0-1背包問題(ZKP)的算法可略加修改后用于解一般的整數(shù)背包問題、多約束的0-1背包問題、最小化的0-1規(guī)劃問題乃至于一般的整數(shù)規(guī)劃問題。再如鑒于圖的獨(dú)立集和覆蓋集的互補(bǔ)性,可根據(jù)解獨(dú)立集問題(ISP)的算法求出的最大獨(dú)立集直接得到最小覆

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論