論文模擬退火算法

《論文模擬退火算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、1引言1.1模擬退火算法的背景模擬退火算法來(lái)源于對(duì)固體退火過(guò)程的模擬，將固體加熱到足夠高的溫度，使分子成隨機(jī)排列狀態(tài)，然后逐步降溫使之冷卻，最后分子以低能狀態(tài)排列，固體達(dá)到某種穩(wěn)定狀態(tài)。根據(jù)Metropolis準(zhǔn)則,粒子在溫度T時(shí)趨于平衡的概率為，其中E為溫度T是的內(nèi)能，為內(nèi)能的改變量，k為Boltzman常數(shù)，用固體退火模擬組合優(yōu)化問(wèn)題，將內(nèi)能E模擬為目標(biāo)函數(shù)值f，溫度T演化成控制參數(shù)t，及可得到解組合優(yōu)化問(wèn)題的模擬退火算法：由初始解的控制參數(shù)初始值t開(kāi)始，對(duì)當(dāng)前解重復(fù)“產(chǎn)生新解→計(jì)算目標(biāo)函數(shù)差→接受或舍棄”的迭代，并逐步衰減t的值，算法終止時(shí)的當(dāng)前解即為所得近似最

2、優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機(jī)搜索過(guò)程。退火過(guò)程由冷卻進(jìn)度表（CoolingSchedule）控制，包括參數(shù)的初值t及衰減因子、每個(gè)t值時(shí)的迭代次數(shù)L和停止條件S。1.2背包問(wèn)題的基本概念背包問(wèn)題（KnapsackProblem）是一個(gè)NP完全問(wèn)題，在實(shí)際的工程中有著廣泛的應(yīng)用，目前求解背包問(wèn)題的主要方法有模擬退火算法、貪婪算法、遺傳算法等，還包括許多算法。背包問(wèn)題（KnapsackProblem）是指假定某人擁有大量的物品，重量各不相同，此人通過(guò)秘密的選擇一部分物品并將它們放到背包中來(lái)加密消息，例如給定種物品和1個(gè)背包，知道某物品的重量和價(jià)值，并且

3、背包的最大容量也是已知的，要求選擇物品裝入背包中，是選中的物品的總重量不超過(guò)背包的最大容量，但裝入背包的物品的總價(jià)值最大。它是一種典型的組合優(yōu)化問(wèn)題，已證明背包問(wèn)題是一個(gè)NP-hard問(wèn)題，基于智能優(yōu)化算法求解背包問(wèn)題，是近年來(lái)剛剛興起的熱門(mén)問(wèn)題。在我們的現(xiàn)實(shí)生活中存在著大量的多目標(biāo)優(yōu)化問(wèn)題，對(duì)于背包問(wèn)題（KnapsackProblem）：在實(shí)際中經(jīng)常要同時(shí)考慮多個(gè)目標(biāo)，如價(jià)值最大、容量最大等多方面的因素。目標(biāo)之間往往出現(xiàn)沖突性。這就需要我們?nèi)绾卧诙鄠€(gè)目標(biāo)中尋找一個(gè)合理的解去解決一個(gè)比較復(fù)雜的問(wèn)題。1.3發(fā)展趨勢(shì)背包問(wèn)題在國(guó)外研究得比較早，范圍也比較廣,Dantzin

4、g在20世紀(jì)50年代第一個(gè)進(jìn)行了開(kāi)放性研究，利用貪婪算法求得了背包問(wèn)題最優(yōu)解的上界。1974年，horowitz和salmi利用分支界限法解答背包問(wèn)題，并提出了背包問(wèn)題的可分性，指出了求解該問(wèn)題的一條新途徑。接著，balas和zemel提出了背包問(wèn)題的“核”思想，是背包問(wèn)題的研究有了較大的進(jìn)展。十九世紀(jì)九十年代以后，隨著生物仿生技術(shù)和網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，各種模擬生物物理規(guī)律的并行近似算法不斷涌現(xiàn)，就如遺傳算法已經(jīng)在背包問(wèn)題上得到較好的應(yīng)用，而蟻群算法等仿生算法也在組合優(yōu)化問(wèn)題上得到了不錯(cuò)的應(yīng)用。背包問(wèn)題（KnapsackProblem）是運(yùn)籌學(xué)中的一個(gè)經(jīng)典組合優(yōu)化問(wèn)題

5、，也是數(shù)學(xué)與計(jì)算機(jī)學(xué)界公認(rèn)的一個(gè)NP問(wèn)題。同時(shí)，背包問(wèn)題也是諸多領(lǐng)域內(nèi)出現(xiàn)的多種復(fù)雜問(wèn)題的集中概括和簡(jiǎn)化形式。目前求解背包問(wèn)題的主要方法有模擬退火算法、遞歸法、動(dòng)態(tài)規(guī)劃法、分支定界法、等指數(shù)級(jí)方法。對(duì)于用模擬退火算法對(duì)求解背包組合優(yōu)化問(wèn)題來(lái)做在滿足模擬退火算法全局收斂性的情況下，對(duì)求解NP完全問(wèn)題是非常有效的。在實(shí)際生活中，很多問(wèn)題經(jīng)過(guò)簡(jiǎn)化處理后均可轉(zhuǎn)化為背包問(wèn)題，對(duì)背包問(wèn)題求解方法的研究具有重要的應(yīng)用價(jià)值。人們?cè)谂ふ掖缶S數(shù)最優(yōu)化算法的同時(shí)，構(gòu)造出了許多近似求解法，如遺傳算法、貪婪法、粒子群算法、蟻群算法等，特別是提出了如模擬退火等用統(tǒng)計(jì)方法近似求解背包問(wèn)題的隨機(jī)

6、算法，為人們求解背包問(wèn)題開(kāi)辟了新的途徑。2理論基礎(chǔ)2.1模擬退火算法基本原理模擬退火（simulatedannealing,SA）算法的思想最早是由Metropolis等提出的，其出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過(guò)程與一般的組合優(yōu)化問(wèn)題之間的相似性，模擬退火算法是一種通用的優(yōu)化算法，其物理退火過(guò)程主要由加溫過(guò)程、等溫過(guò)程、冷卻過(guò)程這三部分組成，其中，加溫過(guò)程對(duì)應(yīng)算法的設(shè)定初溫，等溫過(guò)程對(duì)應(yīng)算法的Metropolis抽樣過(guò)程，冷卻過(guò)程對(duì)應(yīng)控制參數(shù)的下降。這里能量的變化就是目標(biāo)函數(shù)，要得到的最優(yōu)解就是能量最低態(tài)，Metropolis準(zhǔn)則是SA算法收斂于全局最優(yōu)解的關(guān)鍵，M

7、etropolis準(zhǔn)則以一定的概率接受惡化解，這樣就使算法跳離局部最優(yōu)的情況。模擬退火算法可以用以求接不同的非線性問(wèn)題，對(duì)不可微且不連續(xù)的函數(shù)優(yōu)化，能以較大概率球的全局優(yōu)化解，該算法具有較強(qiáng)的全局收斂性、隱含并行性及廣泛的適應(yīng)性，并且能處理不同類(lèi)型的優(yōu)化設(shè)計(jì)變量，他不需要任何的輔助信息，對(duì)目標(biāo)函數(shù)和約束函數(shù)沒(méi)有任何的要求，用Metropolis算法并適當(dāng)?shù)乜刂茰囟认陆档倪^(guò)程，在優(yōu)化問(wèn)題中競(jìng)爭(zhēng)力較強(qiáng)，本文研究的是基于模擬退火算法的背包問(wèn)題算法。模擬退火算法可以分解為解空間、目標(biāo)函數(shù)和初始解三部分。2.1.1模擬退火的基本思想模擬退火是一種通用的概率算法