現(xiàn)代優(yōu)化算法-在線瀏覽
2024-09-11 13:08本頁面
【正文】 域中從給定的一個或多個隨機初始點出發(fā)進行搜索，利用適當?shù)臓顟B(tài)轉(zhuǎn)移規(guī)則和合理的 概率性狀態(tài)接收規(guī)則 搜索新的更優(yōu)點，在確定的時間或搜索次數(shù)之內(nèi)停止算法。 ? 通常，局部優(yōu)化算法能夠快速地收斂到局部極優(yōu)解，而全局性優(yōu)化算法通過概率搜索可以獲得在概率意義上盡可能好的全局性最優(yōu)解區(qū)域，但是其局部極優(yōu)點搜索能力較低。對此人們進行了多種研究。 ? Memetic算法 就是全局性搜索和局部性搜索相結(jié)合的算法的總稱。 39 7 內(nèi)容概要 ? 優(yōu)化算法簡介 ——運籌學 ? 正交試驗法 ? TABU禁忌搜索算法 ? 模擬退火算法 ? 遺傳算法 ? 現(xiàn)代優(yōu)化算法再述 ? 課題組的工作 39 8 正交試驗法 ? 在工農(nóng)業(yè)生產(chǎn)及科學實驗中，為了試制新產(chǎn)品，改革工藝，尋找優(yōu)良的生產(chǎn)條件，需要安排一系列的實驗。因此，需要進行部分試驗。其中的決策變量和取值分別叫做因素 和 水平 。 39 9 正交試驗法 ? 正交表的形式為 Ln(t1?t2?… ?tm)，簡記為 Ln(tm)，其中 n為 試驗數(shù) ， m為因素數(shù) ， ti為 水平數(shù) 。 ? 實際上，正交試驗法獲得的最佳結(jié)果 優(yōu)于總體試驗結(jié)果 的 n/(n+1)，劣于總體試驗結(jié)果 的 1/(n+1)，具有良好的全局最優(yōu)性。其難點在于 特定正交表的構造 ，人們正深入研究各種特殊正交表的構造方法。 Glover在 1986年首次提出這一概念 ， 進而形成一套完整算法 。 為了回避局部鄰域搜索陷入局部最優(yōu)的主要不足 ， 采用一個禁忌表記錄已經(jīng)達到過的局部最優(yōu)點 ， 在下一次搜索中 ， 利用禁忌表中的信息不再或者有選擇地搜索這些點 ， 以此來跳出局部最優(yōu)點 。 鄰域與一般優(yōu)化技術中的定義一致； Tabu表 是一個或數(shù)個數(shù)據(jù)序列 ， 是對先前的數(shù)步搜索所作的記錄 ， 記錄的方式有很多 ， 記錄的長度也是可變的 ， 選取的好壞直接影響算法的效率； 評價函數(shù) 通常就是問題的目標函數(shù)或它的某種變換形式 ， 用于對一個移動作出評價 。 39 12 TABU禁忌搜索算法 ? Tabu算法被認為是人工智能在組合優(yōu)化中的成功應用 ， 但是仍有很多技術的細節(jié)問題有待討論 。 另外還涉及到評價函數(shù) 、 特赫規(guī)則 、終止規(guī)則等的合理確定 。 [*]孫元凱 ， 劉民 ， 吳澄 。 電子學報 ， 2022,29(5),622625。 ? 歷史上，兩個人物對于 SAA的發(fā)展起了關鍵性的作用，他們分別是 N. Metropolis和 S. Kirkpatrick。 設與狀態(tài) i、 j對應的固體系統(tǒng)能量分別為 Ei、 Ej。 ? 1982年， Kirkpatrick將退火思想首先引入求解組合優(yōu)化問題，提出了SAA。開始時，取 T為一個較大的數(shù)值，此時狀態(tài)轉(zhuǎn)移比較自由。 ? 目前，模擬退火算法已經(jīng)廣泛地用于求解 TSP、 VLSI電路設計等 NP–完全問題。 這些成果主要是針對模擬退火算法性能的提高，如怎樣控制冷卻進度表（ cooling schedule）參數(shù)（即初始溫度、降溫策略、溫度終值準則、Markov鏈長），怎樣實現(xiàn)模擬退火算法的并行運算，怎樣進一步改進模擬退火算法等。需要說明，文獻中的局部搜索法實質(zhì)上仍然是隨機搜索，只是僅接受優(yōu)化解，不接受惡化解。 包括：討論模擬退火與傳統(tǒng)局部優(yōu)化算法如單純形法、 Powell方法等的結(jié)合 [7]，研究鄰域結(jié)構與選取狀態(tài)轉(zhuǎn)移隨機步長方法以及相應的降溫方案，如何采取合適的退火終止條件等。 begin INITIALIZE (i0, T0, L0)。 i:=i0。 k:=k+1。 CALCULATECONTROL(Tk)。 計算 冷卻進度表 Markov鏈長 Metropolis規(guī)則 39 18 模擬退火算法 最初路徑 算法結(jié)果 目前最好結(jié)果 39 19 模擬退火算法 ? 一些文獻： 康立山，謝云，尤矢勇等。北京：科學出版社， 1998年。一種改進的快速模擬退火組合優(yōu)化法。 趙玉清，余志軍。電子學報， 1998， 26(9): 75–77。一種高效的模擬退火全局優(yōu)化算法。 39 20 內(nèi)容概要 ? 優(yōu)化算法簡介 ——運籌學 ? 正交試驗法 ? TABU禁忌搜索算法 ? 模擬退火算法 ? 遺傳算法 ? 現(xiàn)代優(yōu)化算法再述 ? 課題組的工作 39 21 遺傳算法 ? Darwin 的物種進化的主要思想是自然選擇 (Natural selection)。生物通過遺傳 (Heredity)、變異 (Mutation)等過程實現(xiàn)進化。染色體又是由 DNA 和蛋白質(zhì)組成的。通過基因的復制(production)、交叉 (crossover)和變異 (mutation)實現(xiàn)生物的性狀的變異和遺傳。這是一類模擬生物進化過程的全局性優(yōu)化算法，其搜索效率取決于搜索策略或狀態(tài)轉(zhuǎn)移策略、編碼策略、運行參數(shù)的合理配置等方面。 39 22 遺傳算法 ? 基本思路 ： 第一步：建立研究對
試題試卷相關推薦
鄂ICP備17016276號-1