現(xiàn)代優(yōu)化算法(編輯修改稿)
2025-08-28 13:08 本頁面
【文章內(nèi)容簡介】 第一部系統(tǒng)討論模擬退火算法的中文專著 《 非數(shù)值并行算算法 ——模擬退火算法 》 比較詳細地討論了模擬退火算法的數(shù)學和物理背景、理論基礎以及實現(xiàn)形式，介紹了 1994年以前國內(nèi)外一些學者在理論和應用上的研究成果。 這些成果主要是針對模擬退火算法性能的提高，如怎樣控制冷卻進度表（ cooling schedule）參數(shù)（即初始溫度、降溫策略、溫度終值準則、Markov鏈長），怎樣實現(xiàn)模擬退火算法的并行運算，怎樣進一步改進模擬退火算法等。 ? 這些改進主要包括：選取合適的初始溫度、最優(yōu)保留策略、與局部搜索相結合、回火退火法等。需要說明，文獻中的局部搜索法實質上仍然是隨機搜索，只是僅接受優(yōu)化解，不接受惡化解。 ? 近些年來，不少學者對于模擬退火算法進行了深入的研究和改進 。 包括：討論模擬退火與傳統(tǒng)局部優(yōu)化算法如單純形法、 Powell方法等的結合 [7]，研究鄰域結構與選取狀態(tài)轉移隨機步長方法以及相應的降溫方案，如何采取合適的退火終止條件等。 39 17 模擬退火算法 ? 基本算法（ PASCAL偽碼）： Procedure SIMULATED ANNEALING。 begin INITIALIZE (i0, T0, L0)。 k:=0。 i:=i0。 repeat for l:=1 to Lk do begin GENERATE (j from Si) if f(j) ≤ f(i) then i:=j else if exp[(f(i)—f(j))/Tk] random[0,1] then i:=j end。 k:=k+1。 CALCULATELENGTH(Lk)。 CALCULATECONTROL(Tk)。 until stopcriterion end。 計算 冷卻進度表 Markov鏈長 Metropolis規(guī)則 39 18 模擬退火算法 最初路徑 算法結果 目前最好結果 39 19 模擬退火算法 ? 一些文獻： 康立山，謝云，尤矢勇等。非數(shù)值并行算法 ——模擬退火算法。北京：科學出版社， 1998年。 王卓鵬，高國成，楊為平。一種改進的快速模擬退火組合優(yōu)化法。系統(tǒng)工程理論與實踐， 1999， (2): 73–76。 趙玉清，余志軍。加速全局優(yōu)化 –鮑威爾法和模擬退火法的組合。電子學報， 1998， 26(9): 75–77。 楊若黎，顧基發(fā)。一種高效的模擬退火全局優(yōu)化算法。系統(tǒng)工程理論與實踐， 1997， (5): 29–35。 39 20 內(nèi)容概要 ? 優(yōu)化算法簡介 ——運籌學 ? 正交試驗法 ? TABU禁忌搜索算法 ? 模擬退火算法 ? 遺傳算法 ? 現(xiàn)代優(yōu)化算法再述 ? 課題組的工作 39 21 遺傳算法 ? Darwin 的物種進化的主要思想是自然選擇 (Natural selection)。生物通過競爭來進化，以適應環(huán)境。生物通過遺傳 (Heredity)、變異 (Mutation)等過程實現(xiàn)進化。遺傳和變異的物質基礎是染色體 (Chromosome)。染色體又是由 DNA 和蛋白質組成的?；蛑斜Ａ糁z傳物質。通過基因的復制(production)、交叉 (crossover)和變異 (mutation)實現(xiàn)生物的性狀的變異和遺傳。 ? 標準遺傳算法的基本框架是由 Holland于 20世紀 60年代提出的，它使用二進制編碼，采用賭輪選擇和隨機配對， 關鍵是 編碼 。這是一類模擬生物進化過程的全局性優(yōu)化算法，其搜索效率取決于搜索策略或狀態(tài)轉移策略、編碼策略、運行參數(shù)的合理配置等方面。對于具有下面數(shù)學結構的研究對象 min（或 max） f (x)， . g(x) ? 0， x?D 遺傳算法可以具有較好的搜索效果。 39 22 遺傳算法 ? 基本思路 ： 第一步：建立研究對象的數(shù)學結構模型，確定目標函數(shù)類型（即求目標函數(shù)的最大值還是最小值 ?）。 第二步：確定表示可行解的染色體編碼方法，即確定個體基因型 X及遺傳算法的搜索空間。 第三步：確定解碼方法，即確定由個體基因型 X到相應表現(xiàn)型的對應關系或轉換關系。 39 23 遺傳算法 ? 基本思路 ： 第四步：設計遺傳算子，包括選擇算子、交叉算子、變異算子等的具體操作方法。 第五步：確定個體適應度的量化評價方法，即制定由目標函數(shù) f(x) 到個體適應度的轉換規(guī)則。 第六步：確定遺傳算法的有關運行參數(shù)。包括編碼串長度 l（對于二進制編碼）、交叉概率 Pc、變異概率 Pm、種群規(guī)模 M、終止代數(shù) T等運行參數(shù)的設置。 第七步：設計遺傳算法程序，其中使用了最優(yōu)保留策略。 39 24 遺傳算法 ? 為了提高其搜索效率，可以在三個方面提出改進措施： 1) 采用更好的搜索策略。 主要包括：精英策略（ elitist strate
試題試卷相關推薦
鄂ICP備17016276號-1