現(xiàn)代優(yōu)化算法-wenkub
2022-08-29 13:08:53 本頁面
【正文】 找到全局最小點。降低成本、提高效益是問題的關(guān)鍵。 39 3 優(yōu)化算法簡介 ——概念、基本形式 ? 什么是優(yōu)化？就是從各種方案中選取一個最好的?，F(xiàn)代優(yōu)化算法 李金屏 濟南大學信息科學與工程學院 模式識別與智能系統(tǒng)研究所 (1st version in ) 39 2 內(nèi)容概要 ? 優(yōu)化算法簡介 ——運籌學 ? 正交試驗法 ? TABU禁忌搜索算法 ? 模擬退火算法 ? 遺傳算法 amp。 從數(shù)學角度看，優(yōu)化理論就是研究如何在狀態(tài)空間中尋找到全局最優(yōu)點 。 ? 一般的優(yōu)化具有下面形式： minf (x1, x2, …, xn) . g(x) ? 0， x?D 其中 x1, x2, …, xn?Ω（即問題的可行域，代表問題參數(shù)的選擇范圍），即 minf (X)，其中 X?Ω（矢量形式）。 注：求問題的最大和最小是同一個問題，算法完全一樣。 ? 這是一個全局尋優(yōu)問題。前者可以稱為 經(jīng)典優(yōu)化算法 ，已經(jīng)得到了人們廣泛深入的研究。 ? 全局性優(yōu)化算法主要用于求解非凸問題或 多峰問題 ，通常使用 概率性搜索策略 ，即 狀態(tài)轉(zhuǎn)移規(guī)則 ，這是由于實際的全局性優(yōu)化問題通常沒有解析表達式或者解析表達式非常復雜難以進行理論分析。這是全局搜索算法和局部搜索算法之間的 固有矛盾 。又可以稱為 雜和優(yōu)化算法 (Hybrid Optimization Algorithm)。正交試驗法就是一種實際中廣泛使用的部分試驗法，又叫 正交設(shè)計法 或 正交優(yōu)化法 ，即通過少數(shù)次試驗找到最好的或者較好的實驗條件。正交設(shè)計法能夠確保決策變量具有最佳的散布性和代表性，因此獲得的最佳水平應(yīng)該具有相當高的滿意度。 39 10 內(nèi)容概要 ? 優(yōu)化算法簡介 ——運籌學 ? 正交試驗法 ? TABU禁忌搜索算法 ? 模擬退火算法 ? 遺傳算法 ? 現(xiàn)代優(yōu)化算法再述 ? 課題組的工作 39 11 TABU禁忌搜索算法 ? 禁忌搜索算法 （ tabu search） 是局部鄰域搜索算法的推廣 ， 是人工智能在組合優(yōu)化算法中的一個成功應(yīng)用 。 ? Tabu算法由幾個基本要素的組合：鄰域 ， Tabu表及評價函數(shù) 。 如參數(shù)的選擇問題 ， 該問題包括禁忌對象及其長度 、 候選集合的確定等 。 變鄰域結(jié)構(gòu) Tabu搜索算法及其在 Job Shop調(diào)度問題上的應(yīng)用 。 ? 在利用 Monte Carlo方法模擬恒定溫度下固體達到熱平衡態(tài)過程的研究中， 1953年 Metropolis提出了重要性采樣準則，即對于處在微觀狀態(tài) i 的固體系統(tǒng)施加一個隨機擾動，使其狀態(tài)變?yōu)?j。引入一個溫度參數(shù) T。 1 Ej ≤ Ei. else 即 39 16 模擬退火算法 ? 我國第一部系統(tǒng)討論模擬退火算法的中文專著 《 非數(shù)值并行算算法 ——模擬退火算法 》 比較詳細地討論了模擬退火算法的數(shù)學和物理背景、理論基礎(chǔ)以及實現(xiàn)形式，介紹了 1994年以前國內(nèi)外一些學者在理論和應(yīng)用上的研究成果。 ? 近些年來，不少學者對于模擬退火算法進行了深入的研究和改進 。 k:=0。 CALCULATELENGTH(Lk)。非數(shù)值并行算法 ——模擬退火算法。系統(tǒng)工程理論與實踐， 1999， (2): 73–76。 楊若黎，顧基發(fā)。生物通過競爭來進化，以適應(yīng)環(huán)境?；蛑斜Ａ糁z傳物質(zhì)。對于具有下面數(shù)學結(jié)構(gòu)的研究對象 min（或 max） f (x)， . g(x) ? 0， x?D 遺傳算法可以具有較好的搜索效果。 39 23 遺傳算法 ? 基本思路 ： 第四步：設(shè)計遺傳算子，包括選擇算子、交叉算子、變異算子等的具體操作方法。 第七步：設(shè)計遺傳算法程序，其中使用了最優(yōu)保留策略。如采用十進制編碼，多維實數(shù)編碼，或根據(jù)模式定理將二進制編碼的低階、高平均適應(yīng)度的長定義距模式轉(zhuǎn)換為短定義距模式等。 39 26 遺傳算法 ? 編碼串長度 l直接決定問題的求解精度。 這種研究對于深刻理解遺傳算法非常有益。 原碼編碼 采用決策變量本身作為狀態(tài)參量，也是一種編碼方式，只不過我們已經(jīng)習以為常了。 單點法是一種 串行方式 ，即從一個初始狀態(tài)（單個個體）出發(fā)，按照某種方式轉(zhuǎn)移狀態(tài)進行全局優(yōu)化，這種方式通常要 消耗較多機時 ； 多點法是一種 并行方式 ，即從可行域的多個初始狀態(tài)（多個個體）同時進行搜索尋找全局最優(yōu)解，但是 空間開銷大 。 由于許多實際問題的 決策變量不連續(xù) ，或者沒有解析表達式或者解析表達式比較復雜致使無法進行理論分析，而且大多數(shù)問題的極值數(shù)目未知，無法提供全局性搜索的 確定性信息 ，因此通常采用概率性搜索策略，包括： 1. 狀態(tài)轉(zhuǎn)移規(guī)則 ， 2. 狀態(tài)接受規(guī)則 。 39 31 現(xiàn)代優(yōu)化算法 ——一般性描述 ——全局性優(yōu)化理論的一般性描述 ? 狀態(tài)接受規(guī)則 研究如何接受按照狀態(tài)轉(zhuǎn)移規(guī)則獲得的新狀態(tài)，即 確定性 接受還是 概率性 接受。由于狀態(tài)接受規(guī)則 體現(xiàn)優(yōu)勝劣汰的思想 ，全局優(yōu)化也會陷入局部極優(yōu)解，因此
試題試卷相關(guān)推薦
鄂ICP備17016276號-1