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