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

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

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

目錄/Contents

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

上述隨機(jī)試驗(yàn)法中還有一些需要注意的事項(xiàng)：

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

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