論文模擬退火算法-展示頁
2025-06-16 23:44本頁面
【正文】 的變化就是目標函數(shù)，要得到的最優(yōu)解就是能量最低態(tài)， Metropolis 準則是 SA算法收斂于全局最優(yōu)解的關鍵， Metropolis 準則以一定的概率接受惡化解，這樣就 使算法跳離局部最優(yōu)的情況 。人們在努力尋找大維數(shù)最優(yōu)化算法的同時，構造出 了許多近似求解法， 如遺傳算法、貪婪法、粒子群算法、蟻群算法等 ，特別是提出了如模擬退火等用統(tǒng)計方法近似求解背包問題的隨機算法，為人們求解背包問題開辟了新的途徑。 對于用模擬退火算法對求解背包組合優(yōu)化問題來做在滿足模擬退火算法全局收斂性的情況下， 對求解 NP 完全問題是非常有效的。同時，背包問題也是諸多領域內出現(xiàn)的多種復雜問題的集中概括和簡化形式。 十九世紀九十年代以后，隨著生物仿生技術和網(wǎng)絡技術的飛速發(fā)展，各種模擬生物物理規(guī)律的并行近似算法不斷涌現(xiàn)， 就如遺傳算法已經(jīng)在背包問題上得到較好的應用，而蟻群算法等仿生算法也在組合優(yōu)化問題上得到了不錯的應用。 1974 年， horowitz 和 salmi 利用分支界限法解答背包問題，并提出了背包問題的可分性，指出了求解該問題的一條新途徑。這就需要我們如何在多個目標中尋找一個合理的解 去解決一個比較復雜的問題。在我們的現(xiàn)實生活中存在著大量的多目標優(yōu)化問題，對于背包問題（ Knapsack Problem） ：在實際中經(jīng)常要同時考慮多個目標，如價值最大、容量最大等多方面的因素。 背包問題（ Knapsack Problem） 是 指 假定某人擁有大量的物品，重量各不相同，此人通過秘密的選擇一部分物品并將它們放到背包中來加密消息，例如 給定n 種物品和 1 個背包，知道某物品的重量和價值，并且背包的最大容量也是已知的，要求選擇物品裝入背包中，是選中的物品的總重量不超過背包的最大容量 ，但裝入背包的物品的總價值最大。退火過程由冷卻進度表（ Cooling Schedule）控制，包括參數(shù)的初值 t及衰減因子 t? 、每個 t 值時的迭代次數(shù) L 和停止條件 S。 1 引言 模擬退火算法的背景 模擬退火算法來源于對固體退火過程的模擬，將固體加熱到足夠高的溫度，使分子成隨機排列狀態(tài)，然后逐步降溫使之冷卻，最后分子以低能狀態(tài)排列，固體達到某種穩(wěn)定狀態(tài)。 根據(jù) Metropolis 準則 ,粒子在溫度 T 時趨于平衡的概率為/( )E kTe?? ，其中 E 為溫度 T是的內能 ， E? 為內能的改變量 ， k為 Boltzman 常數(shù)， 用固體退火模擬組合優(yōu)化問題，將內能 E 模擬為目標函數(shù)值 f，溫度 T演化成控制參數(shù) t，及可得到解組合優(yōu)化問題的模擬退火算法：由初始解 i 的控制參數(shù)初始值 t開始，對當前解重復“產(chǎn)生新解 → 計算目標函數(shù)差 → 接受或舍棄”的迭代，并逐步衰減 t 的值， 算法終止時的當前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機搜索過程。 背包問題的基
畢業(yè)設計相關推薦
鄂ICP備17016276號-1