現(xiàn)代優(yōu)化算法-展示頁
2024-08-16 13:08本頁面
【正文】 面的工作 。 39 10 內(nèi)容概要 ? 優(yōu)化算法簡介 ——運籌學 ? 正交試驗法 ? TABU禁忌搜索算法 ? 模擬退火算法 ? 遺傳算法 ? 現(xiàn)代優(yōu)化算法再述 ? 課題組的工作 39 11 TABU禁忌搜索算法 ? 禁忌搜索算法 （ tabu search） 是局部鄰域搜索算法的推廣 ， 是人工智能在組合優(yōu)化算法中的一個成功應用 。該算法的另外一個最大優(yōu)勢在于 簡單易學 ，一般文化水平的人（比如初中以上）經(jīng)過幾天時間就可以掌握，因此該算法具有極其廣泛的使用范圍。正交設(shè)計法能夠確保決策變量具有最佳的散布性和代表性，因此獲得的最佳水平應該具有相當高的滿意度。尋優(yōu)時，先確定影響決策目標的因素和水平，再選擇適當?shù)?正交表 ，即可按正交表安排試驗，最后分析試驗的結(jié)果和發(fā)現(xiàn)最佳的水平。正交試驗法就是一種實際中廣泛使用的部分試驗法，又叫 正交設(shè)計法 或 正交優(yōu)化法 ，即通過少數(shù)次試驗找到最好的或者較好的實驗條件。全面實驗成本很高，而且往往做不到。又可以稱為 雜和優(yōu)化算法 (Hybrid Optimization Algorithm)。 基本解決方法 在于二者的結(jié)合，即利用全局性優(yōu)化算法在整個可行域中搜索最優(yōu)區(qū)域，利用局部搜索算法搜索最優(yōu)區(qū)域中的最優(yōu)解。這是全局搜索算法和局部搜索算法之間的 固有矛盾 。 39 6 優(yōu)化算法簡介 ——二者需要結(jié)合 ? 局部優(yōu)化算法由于 易于陷入局部極優(yōu)解 而無法用于解決多峰問題；同時，全局性優(yōu)化算法采用適當?shù)臓顟B(tài)轉(zhuǎn)移規(guī)則和概率性狀態(tài)接受規(guī)則，能夠 避免過早地陷入局部極優(yōu)解 從而搜索到全局性最優(yōu)解。 ? 全局性優(yōu)化算法主要用于求解非凸問題或 多峰問題 ，通常使用 概率性搜索策略 ，即 狀態(tài)轉(zhuǎn)移規(guī)則 ，這是由于實際的全局性優(yōu)化問題通常沒有解析表達式或者解析表達式非常復雜難以進行理論分析。 后者習慣上稱為 現(xiàn)代優(yōu)化算法 ，是 20世紀 80年代興起的新型全局性優(yōu)化算法，主要包括 禁忌搜索 、 模擬退火 、 遺傳算法 等，其主要應用對象是優(yōu)化問題中的 難解問題 ，即 NP–hard問題 優(yōu)化算法簡介 ——優(yōu)化算法分類 39 5 優(yōu)化算法簡介 ——局部優(yōu)化、全局優(yōu)化 ? 有文獻將 神經(jīng)網(wǎng)絡 也列入現(xiàn)代優(yōu)化算法的范疇，從全局優(yōu)化的角度看，這并不適宜，因為神經(jīng)網(wǎng)絡的優(yōu)化算法 本質(zhì)上 是局部優(yōu)化算法和全局優(yōu)化算法的 綜合應用 。前者可以稱為 經(jīng)典優(yōu)化算法 ，已經(jīng)得到了人們廣泛深入的研究。一般情況下，利用窮舉的方法是不可能的。 ? 這是一個全局尋優(yōu)問題。然而大量的實際問題是 非凸問題 ，需要在大量的局部極優(yōu)解中尋找全局最優(yōu)解。 注：求問題的最大和最小是同一個問題，算法完全一樣。 問題歸結(jié)為求極值。 ? 一般的優(yōu)化具有下面形式： minf (x1, x2, …, xn) . g(x) ? 0， x?D 其中 x1, x2, …, xn?Ω（即問題的可行域，代表問題參數(shù)的選擇范圍），即 minf (X)，其中 X?Ω（矢量形式）。學校課程表排課問題、售票員上崗問題、公司內(nèi)部人員安排出效益等。 從數(shù)學角度看，優(yōu)化理論就是研究如何在狀態(tài)空間中尋找到全局最優(yōu)點 。 其它問題?，F(xiàn)代優(yōu)化算法 李金屏 濟南大學信息科學與工程學院 模式識別與智能系統(tǒng)研究所 (1st version in ) 39 2 內(nèi)容概要 ? 優(yōu)化算法簡介 ——運籌學 ? 正交試驗法 ? TABU禁忌搜索算法 ? 模擬退火算法 ? 遺傳算法 amp。進化計算 ? 現(xiàn)代優(yōu)化算法再述 ? 課題組的工作 其它問題： 計算復雜性； 鄰域概念； NP, NPC 和 NPhard； Markov過程； 人工生命，螞蟻算法，免疫算法，混沌優(yōu)化算法， memetic算法等。 39 3 優(yōu)化算法簡介 ——概念、基本形式 ? 什么是優(yōu)化？就是從各種方案中選取一個最好的。 ? 比如水泥混凝土的性能，涉及到水、沙、石子、水泥和其他摻雜物比例。降低成本、提高效益是問題的關(guān)鍵。 f(x)是決策問題的數(shù)學模型，也是決策問題的 目標函數(shù) ， g(x) ?0是決策問題的 約束條件 ， D是決策問題的定義域 （ 可行域 ） 。極值點非常多，需要找到全局最小點。 39 4 ? 如果決策問題是一個 凸問題 ，可以利用 線性規(guī)劃 、 非線性規(guī)劃 等求解。此時，決策變量 x是否連續(xù)，數(shù)學模型 f(x)是否具有 解析表達式 ，對于求解難度會有不同的影響。很多方法討論的是如何在一個極值點附近搜索極值點。 ? 習慣上，將優(yōu)化算法分為兩類： 局部優(yōu)化算法 和 全局性優(yōu)化算法 。目前，運籌學（確定論方法）主要包括這些方面的內(nèi)容，線性規(guī)劃、整數(shù)規(guī)劃、 0–1規(guī)劃、非線性規(guī)劃、排隊論、決策論。 ? 局部優(yōu)化算法主要用于解決 凸問題 或 單峰問題 ，通常使用 確定性搜索策略 ，比如 單純形法 、 梯度下降法 、 爬山法 、 貪心法 等，其基本思想是在狀態(tài)轉(zhuǎn)移過程中，只接受更好的狀態(tài)，拒絕 惡化 的狀態(tài)。其基本思想是在可行
試題試卷相關(guān)推薦
鄂ICP備17016276號-1