現(xiàn)代優(yōu)化算法-文庫吧
2025-07-17 13:08 本頁面
【正文】 找到最好的或者較好的實驗條件。其中的決策變量和取值分別叫做因素 和 水平 。尋優(yōu)時，先確定影響決策目標的因素和水平，再選擇適當?shù)?正交表 ，即可按正交表安排試驗，最后分析試驗的結(jié)果和發(fā)現(xiàn)最佳的水平。 39 9 正交試驗法 ? 正交表的形式為 Ln(t1?t2?… ?tm)，簡記為 Ln(tm)，其中 n為 試驗數(shù) ， m為因素數(shù) ， ti為 水平數(shù) 。正交設(shè)計法能夠確保決策變量具有最佳的散布性和代表性，因此獲得的最佳水平應(yīng)該具有相當高的滿意度。 ? 實際上，正交試驗法獲得的最佳結(jié)果 優(yōu)于總體試驗結(jié)果 的 n/(n+1)，劣于總體試驗結(jié)果 的 1/(n+1)，具有良好的全局最優(yōu)性。該算法的另外一個最大優(yōu)勢在于 簡單易學(xué) ，一般文化水平的人（比如初中以上）經(jīng)過幾天時間就可以掌握，因此該算法具有極其廣泛的使用范圍。其難點在于 特定正交表的構(gòu)造 ，人們正深入研究各種特殊正交表的構(gòu)造方法。 39 10 內(nèi)容概要 ? 優(yōu)化算法簡介 ——運籌學(xué) ? 正交試驗法 ? TABU禁忌搜索算法 ? 模擬退火算法 ? 遺傳算法 ? 現(xiàn)代優(yōu)化算法再述 ? 課題組的工作 39 11 TABU禁忌搜索算法 ? 禁忌搜索算法 （ tabu search） 是局部鄰域搜索算法的推廣 ， 是人工智能在組合優(yōu)化算法中的一個成功應(yīng)用 。 Glover在 1986年首次提出這一概念 ， 進而形成一套完整算法 。 ? 禁忌 ， 就是禁止重復(fù)前面的工作 。 為了回避局部鄰域搜索陷入局部最優(yōu)的主要不足 ， 采用一個禁忌表記錄已經(jīng)達到過的局部最優(yōu)點 ， 在下一次搜索中 ， 利用禁忌表中的信息不再或者有選擇地搜索這些點 ， 以此來跳出局部最優(yōu)點 。 ? Tabu算法由幾個基本要素的組合：鄰域 ， Tabu表及評價函數(shù) 。 鄰域與一般優(yōu)化技術(shù)中的定義一致； Tabu表 是一個或數(shù)個數(shù)據(jù)序列 ， 是對先前的數(shù)步搜索所作的記錄 ， 記錄的方式有很多 ， 記錄的長度也是可變的 ， 選取的好壞直接影響算法的效率； 評價函數(shù) 通常就是問題的目標函數(shù)或它的某種變換形式 ， 用于對一個移動作出評價 。 由 Tabu表和評價函數(shù)可以構(gòu)造一種 Tabu條件 ， 若新點滿足 Tabu條件則接受 ， 否則拒絕 ， 直至迭代終止 。 39 12 TABU禁忌搜索算法 ? Tabu算法被認為是人工智能在組合優(yōu)化中的成功應(yīng)用 ， 但是仍有很多技術(shù)的細節(jié)問題有待討論 。 如參數(shù)的選擇問題 ， 該問題包括禁忌對象及其長度 、 候選集合的確定等 。 另外還涉及到評價函數(shù) 、 特赫規(guī)則 、終止規(guī)則等的合理確定 。 ? 在提高搜索效率方面 ， 文獻 [*]針對調(diào)度問題提出一種變鄰域結(jié)構(gòu)的禁忌搜索算法 ， 使鄰域結(jié)構(gòu)隨算法的進程改變 ， 鄰域規(guī)模小 ， 并且保持了可達性；在算法的結(jié)合方面 ， 有將禁忌搜索和遺傳算法相結(jié)合 ， 構(gòu)造禁忌遺傳算法 ， 主要是利用禁忌搜索的以下特點來改善遺傳算法：即 Tabu搜索能有效利用全局信息 、 搜索過程中的獲得信息和能夠跳出局部最優(yōu)點 。 [*]孫元凱 ， 劉民 ， 吳澄 。 變鄰域結(jié)構(gòu) Tabu搜索算法及其在 Job Shop調(diào)度問題上的應(yīng)用 。 電子學(xué)報 ， 2022,29(5),622625。 39 13 內(nèi)容概要 ? 優(yōu)化算法簡介 ——運籌學(xué) ? 正交試驗法 ? TABU禁忌搜索算法 ? 模擬退火算法 ? 遺傳算法 ? 現(xiàn)代優(yōu)化算法再述 ? 課題組的工作 39 14 模擬退火算法 ? 模擬退火算法（ simulated annealing algorithm, SAA）是一種重要的全局性啟發(fā)式概率搜索算法，其物理背景是固體的退火過程。 ? 歷史上，兩個人物對于 SAA的發(fā)展起了關(guān)鍵性的作用，他們分別是 N. Metropolis和 S. Kirkpatrick。 ? 在利用 Monte Carlo方法模擬恒定溫度下固體達到熱平衡態(tài)過程的研究中， 1953年 Metropolis提出了重要性采樣準則，即對于處在微觀狀態(tài) i 的固體系統(tǒng)施加一個隨機擾動，使其狀態(tài)變?yōu)?j。 設(shè)與狀態(tài) i、 j對應(yīng)的固體系統(tǒng)能量分別為 Ei、 Ej。 則固體系統(tǒng)能否由狀態(tài) i 遷移到新的狀態(tài) j取決于 Ei、 Ej之間的關(guān)系：當 Ej≤ Ei時，系統(tǒng)遷移到新的狀態(tài)；當 EjEi時，系統(tǒng)將以如下概率遷移到新的狀態(tài) 39 15 模擬退火算法 在大量遷移之后，系統(tǒng)趨于能量較低的平衡態(tài)，其微觀狀態(tài)的概率密度分布趨于 Gibbs正則分布。 ? 1982年， Kirkpatrick將退火思想首先引入求解組合優(yōu)化問題，提出了SAA。引入一個溫度參數(shù) T。開始時，取 T為一個較大的數(shù)值，此時狀態(tài)轉(zhuǎn)移比較自由。隨著溫度降低，狀態(tài)轉(zhuǎn)移逐漸困難，最后原則上應(yīng)該收斂到全局最優(yōu)點。 ? 目前，模擬退火算法已經(jīng)廣泛地用于求解 TSP、 VLSI電路設(shè)計等 NP–完全問題。 1 Ej ≤ Ei. else 即 39 16 模擬退火算法 ? 我國
試題試卷相關(guān)推薦
鄂ICP備17016276號-1