數(shù)值分析方法 課件 8.1 最優(yōu)化問題和隨機算法

數(shù)值分析方法主編

李冬果李林高磊首都醫(yī)科大學生物醫(yī)學工程學院智能醫(yī)學工程學學系面向“四新”人才培養(yǎng)普通高等教育系列教材第八章智能優(yōu)化算法基礎第一節(jié)最優(yōu)化問題和隨機算法第二節(jié)禁忌搜索算法第三節(jié)模擬退火方法第四節(jié)遺傳算法第五節(jié)粒子群算法

目錄/Contents

8.1最優(yōu)化問題和隨機算法8.1.1最優(yōu)化問題

8.1.2局部最優(yōu)和全局最優(yōu)

8.1.3局部最優(yōu)搜索算法

8.1.4組合優(yōu)化問題

在此類問題中，有一種比較經(jīng)典的策略叫做貪心算法（greedyalgorithm），將搜索過程分解成若干個步驟，在每一步里都選擇當前的最優(yōu)選擇，從而當完成搜索時，就會獲得一個較優(yōu)的可行解。例如，在旅行商問題中，可以每次都選擇當前所在城市到尚未訪問城市中距離最短的城市作為下一步訪問的對象。貪心算法的優(yōu)點是思路簡單，技術上也容易實現(xiàn)，但對較為復雜的組合優(yōu)化問題，這一算法一般不能得到全局最優(yōu)解。8.1.5隨機試驗法不同于經(jīng)典的解析方法，隨機仿真為解決復雜的優(yōu)化問題提供了簡單有效的實現(xiàn)方法。所謂的隨機試驗首先使用隨機方法生成試驗點，再從中篩選出符合約束條件的可行點，最后由可行點中篩選出最優(yōu)點。隨機試驗法有很多種實現(xiàn)方式，其中最簡單的是基于均勻分布的隨機仿真方法，其基本操作步驟如下：

上述隨機試驗法中還有一些需要注意的事項：

（1）在計算機科學中，偽隨機數(shù)的生成方法有很多，如經(jīng)典的乘法同余生成器(multiplicativecongruentialgenerator)，梅森旋轉(zhuǎn)法(Mersennetwister)等，這些算法通過數(shù)學工具模擬產(chǎn)生服從均勻分布的近似隨機數(shù)。這些生成器產(chǎn)生的數(shù)據(jù)流都能通過分布檢驗，但本質(zhì)上這些數(shù)據(jù)都是按照算法規(guī)律固定產(chǎn)生的，因此被稱為偽隨機數(shù)。在應用隨機算法解決實際問題時，有時需要注意偽隨機數(shù)與自然隨機數(shù)之間的差別。

（3）隨機試驗法不同用于搜索算法，一般不能利用已經(jīng)發(fā)現(xiàn)的結(jié)果修正搜索方向從而提高效率，但根據(jù)概率論中經(jīng)典的大數(shù)定律，當算法重復次數(shù)足夠多時，模擬數(shù)據(jù)的樣本統(tǒng)計量將趨近于它的期望。因此在很多條件下，隨機算法是能夠在重復次數(shù)足夠多的前提下獲得問題近似的全局最優(yōu)解。目前，在經(jīng)典的算法中加入隨機因素以便于避免局部最小值，是將原本用