1、非線性參數(shù)估計的數(shù)值方法E-mail: 1 提 要概述神經(jīng)網(wǎng)絡(luò)算法遺傳算法模擬退火算法2一、神經(jīng)網(wǎng)絡(luò)算法人工神經(jīng)網(wǎng)絡(luò)（Artificial Neural Network，簡稱神經(jīng)網(wǎng)絡(luò)或ANN）是模擬人腦信息處理機制的信息系統(tǒng)，如自組織、自適應(yīng)、容錯性等具有自組織、自適應(yīng)、容錯性；思維、學習、記憶等能力；通過學習和記憶而不是假設(shè)，找出輸入、輸出變量之間的非線性關(guān)系（映射）31.1、神經(jīng)網(wǎng)絡(luò)的特點分布式存儲信息。自適應(yīng)性。具有自我調(diào)節(jié)的能力，包含：學習、自組織、泛化及訓練。并行性。聯(lián)想記憶功能。自動提取特征參數(shù)。容錯性。41.2、神經(jīng)元模型神經(jīng)元：生物神經(jīng)系統(tǒng)是由大量神經(jīng)細胞（神經(jīng)元）組成的一個復

2、雜的互聯(lián)網(wǎng)絡(luò)。神經(jīng)元的數(shù)學模型： 表示神經(jīng)激條件， 時，輸出元素yk 51.2、神經(jīng)元模型(續(xù))激活函數(shù)： 激活函數(shù)f (z)有以下幾種形式：1、閾值函數(shù)：2、非線性斜面函數(shù)：3、Sigmoid函數(shù)：61.2、神經(jīng)元模型(續(xù))神經(jīng)網(wǎng)絡(luò)模型兩層模型的輸出：71.3、典型的神經(jīng)網(wǎng)絡(luò)模型BP網(wǎng)絡(luò)模型：BP算法是非循環(huán)多級網(wǎng)絡(luò)的訓練算法，該算法的學習過程由正向傳播和反向傳播組成。Hopfield網(wǎng)絡(luò)模型： Hopfield網(wǎng)絡(luò)是一種簡單且應(yīng)用廣泛的反饋網(wǎng)絡(luò)模型。模糊神經(jīng)網(wǎng)絡(luò)（FNN）：神經(jīng)網(wǎng)絡(luò)與模糊邏輯有機結(jié)合，有兩類：1）神經(jīng)網(wǎng)絡(luò)中應(yīng)用模糊邏輯規(guī)則；2）模糊邏輯規(guī)則用神經(jīng)網(wǎng)絡(luò)來實現(xiàn)。81.4、神經(jīng)網(wǎng)

3、絡(luò)的學習與推理方法BP網(wǎng)絡(luò)的學習：其實質(zhì)是確定相鄰層神經(jīng)元間的連接權(quán)，有兩類學習：有教師學習和無教師學習；前者已知網(wǎng)絡(luò)的目標輸出，后者則無目標輸出。BP網(wǎng)絡(luò)的學習規(guī)則：輸入 x，網(wǎng)絡(luò)輸出y ，與目標輸出d 間存在誤差，調(diào)節(jié)連接權(quán)和閾值，使誤差減小，達到不大于目標誤差的要求。取連接權(quán) 和輸入 ，輸出為：誤差函數(shù)為：9誤差的導數(shù) ：1.4、神經(jīng)網(wǎng)絡(luò)的學習與推理方法(續(xù))其中：；因此，有代入最速下降法迭代關(guān)系，得學習規(guī)則：， 10BP網(wǎng)絡(luò)的學習過程1.4、神經(jīng)網(wǎng)絡(luò)的學習與推理方法(續(xù))1、信息的正向傳播過程：從第r1層到第r層傳播，輸入為：輸出為：，其中：從輸入層通過隱層到輸出層的傳播為：111.4

4、、神經(jīng)網(wǎng)絡(luò)的學習與推理方法(續(xù))2、誤差的反向傳播過程誤差函數(shù)：連接權(quán)和閾值的更公式 ：， ，輸出層：隱層：，誤差反向傳播過程可表示為：121.4、神經(jīng)網(wǎng)絡(luò)的學習與推理方法(續(xù))3、基本BP算法：基本BP算法的具體步驟如下：（1）輸入共有q組訓練樣本的樣本集（2）設(shè)計網(wǎng)絡(luò)層數(shù)，每層神經(jīng)元數(shù)，激活函數(shù)；權(quán)值和閾值初始化； 設(shè)置目標誤差，學習速率，最大訓練次數(shù)T。（3）初始化訓練次數(shù)t = 0。（4）p = 1，總誤差E = 0。（5）輸入網(wǎng)絡(luò)一對訓練樣本（6）通網(wǎng)絡(luò)將輸入模式的正傳播，計算網(wǎng)絡(luò)的輸出。 初值：逐層計算輸出：最后一層輸出：131.4、神經(jīng)網(wǎng)絡(luò)的學習與推理方法(續(xù))基本BP算法（7）

5、計算 的網(wǎng)誤差 （8）通過網(wǎng)絡(luò)將反向傳播。 最后一層： 逐層計算：（9）修正網(wǎng)絡(luò)的權(quán)值和閾值。（10）如果p q，那么p = p1，轉(zhuǎn)到（5）；否則，轉(zhuǎn)到（11）。 。 （11）（12）如果E ，那么訓練成功，轉(zhuǎn)到（14）；否則，轉(zhuǎn)到（13）。（13）如果t T，那么t = t1，轉(zhuǎn)到（4）；否則，訓練未成功，轉(zhuǎn)到（14）。（14）結(jié)束。14二、遺傳算法原理遺傳算法（Genetic Algorithm，GA）：起源于應(yīng)用計算機模擬生物進化系統(tǒng)?；驹恚?）將優(yōu)化問題離散后的各個可行解“編碼”成“個體”（或染色體），一群個體組成“種群”；2）將參數(shù)編碼個體（如二進制字符串），各個字符（二進制碼

6、0或1）稱為“基因”；3）父代初始種群隨機產(chǎn)生；4）模擬生物進化，選擇“適應(yīng)度”（如優(yōu)化問題的目標函數(shù)）高的個體，進行“交叉”和“變異”操作，生成子代種群。“選擇”、“交叉”和“變異”是遺傳算法的三個基本操作算子；5）對子代種群，再進行選擇、交叉和變異操作，直至收斂；6）收斂的最優(yōu)個體，對應(yīng)于問題的最優(yōu)或次優(yōu)解。152.1 遺傳算法計算步驟遺傳算法的計算步驟：對參數(shù)離散化，確定編碼方案，隨機給定一組初始解，確定初始化種群；用適應(yīng)度評價這組解的性能；根據(jù)評價結(jié)果，選擇一定數(shù)量性能優(yōu)異的解，進行交叉、變異操作，得到一組新的解；返回到第2步，對該組新的解進行評價；若評價結(jié)果滿足要求或進化過程達到設(shè)定

7、的代數(shù)，計算結(jié)束；否則轉(zhuǎn)向第3步，繼續(xù)進行交叉、變異操作。16遺傳算法原理框圖172.2 介紹遺傳算法結(jié)合的簡單算例【例7.2】對某兩點的距離用不同的方法丈量了5次，相應(yīng)的觀測值和觀測權(quán)如表7.7所示，用遺傳算法求解該段距離的最優(yōu)估值。182.3 遺傳編碼與譯碼參數(shù)空間到GA編碼空間的映射稱為編碼；從編碼空間到參數(shù)空間的映射為解碼。參數(shù)空間中所有的點（潛在解）必須與GA編碼空間中的個體必須一一對應(yīng)，稱為編碼條件。192.3 遺傳編碼與譯碼個體位串編碼空間到參數(shù)空間的映射為譯碼，譯碼函數(shù)為：20算例的編碼長度為L=5的二進制編碼。編碼精度為序號位串實參數(shù)適應(yīng)值序號位串實參數(shù)適應(yīng)值00000020

8、.10009.99178161000020.15169.9965810000120.10329.99329171000120.15489.9955220001020.1065 9.99463181001020.15819.9943030001120.10979.99581191001120.16139.9929240010020.11299.99683201010020.16459.9913750010120.11619.99769211010120.16779.9896760011020.11949.99839221011020.17109.9878170011120.12269.99893

9、231011120.17429.9857880100020.12589.99931241100020.17749.9836090100120.12909.99953251100120.18069.98125100101020.13239.99959261101020.18399.97875110101120.13559.99949271101120.18719.97609120110020.13879.99923281110020.19039.97326130110120.14199.99881291110120.19359.97028140111020.14529.9982330111102

10、0.19689.96713150111120.14849.99749311111120.20009.96382212.4 適應(yīng)度函數(shù)222.5 遺傳算子選擇算子：輪盤賭式選擇法規(guī)模為n的種群若個體適應(yīng)值為 該個體被選擇的概率為被選擇到的期望數(shù)目：排序選擇法：各個體的適應(yīng)值滿足降序排列，即：各個體被選擇的期望數(shù)量按等差序列排列：232.5 遺傳算子交叉算子：交叉操作的主要步驟如下：1、從交配池中隨機取出交叉操作的一對個體；2、位串長度L，交叉點數(shù)K，在0, L-1中隨機選擇K個基因位作交叉位置；3、根據(jù)交叉位置，按交叉概率交換配對個體部分內(nèi)容，形成一對新的個體。單點交叉:交叉后:多點交叉(3點)

11、:交叉后:242.5 遺傳算子均勻交叉: 每一位基因按交叉概率1/2，進行交叉操作。個體位串：交叉生成：其中：252.5 遺傳算子變異算子按小概率 改變個體基因的值，其作用：1）改變遺傳算法的局部搜索能力。 2）維持種群的多樣性，防止出現(xiàn)早熟現(xiàn)象。經(jīng)變異生成：則有：26遺傳算例選擇操作：根據(jù)例7.2的數(shù)據(jù)，適應(yīng)度函數(shù)（7.4.12）式，在 采用L=5的二進制編碼。若種群規(guī)模為n=4，隨機抽樣初始種群；根據(jù)適應(yīng)值排序選擇個數(shù)為（2，1，1，0）27遺傳算例交叉操作：按交叉概率0.8進行交叉操作得交叉操作的基因位：確定交叉操作的概率：28遺傳算例變異操作：按變異概率0.05實施變異操作 在此基礎(chǔ)上

12、，再用排序選擇結(jié)合精英選擇確定進入交配池的種群，再實施交叉和變異操作，直到適應(yīng)值指標或最大進化代數(shù)達到設(shè)定的要求。事實上，表7.11中的最優(yōu)個體位串01011的實參數(shù)20.1355已經(jīng)接近(7.4.2)式給出的最優(yōu)解20.1318。292.6、終止判斷與控制參數(shù)的選擇終止判斷 預先設(shè)定的遺傳代數(shù)則終止遺傳算法 前后兩代的最優(yōu)目標函數(shù)值和平均目標函數(shù)值相同時控制參數(shù)的選擇 編碼長度： 種群規(guī)模n 種群進化代數(shù) 選擇交叉概率 變異概率等。302.7 遺傳算法的特點遺傳算法適合求解多參數(shù)、多變量、多目標和多區(qū)域且連通性較差的優(yōu)化問題。遺傳算法從一個種群即多個點而不是一個點開始搜索。遺傳算法僅用適應(yīng)值

13、來評價個體的性能，基本上不需要搜索空間知識或其它輔助信息。遺傳算法與神經(jīng)網(wǎng)絡(luò)等算法有較好的兼容性。遺傳算法不是采用確定性轉(zhuǎn)移規(guī)則，而是采用隨機轉(zhuǎn)移規(guī)則來引導搜索過程朝著更優(yōu)的解區(qū)域移動。31三、模擬退火關(guān)于模擬退火的發(fā)展: 1953年，Metropolis E., Rosenbluth A., Rosenbluth M., Teller A., and Teller E., 發(fā)表在 J Chem Phys.1983 年，Kirkpatrick, Gelatt and Vecchi 發(fā)表在Science .現(xiàn)在廣泛用于科學與工程的各種領(lǐng)域。1985 應(yīng)用于地球物理, 2001應(yīng)用于大地測量 ？這

14、部份摘自徐培亮的講稿32模擬退火的物理背景: 將固體加熱成液體，使其原子自由排列; 將液體冷卻，使其結(jié)晶，變成為理想結(jié)晶態(tài). 理想結(jié)晶態(tài)： 物理上能量最小的狀態(tài)； 數(shù)學上全局最優(yōu).3.1 模擬退火的物理背景33Basic elements of Simulated annealingHow to translate the physical process of annealing into a mathematical algorithm?Problems to Solve:How to connect it with optimization? the energy state = cos

15、t functionHow to cool mathematically? evolving the state = searching3.2 模擬退火的物理背景343.3 模擬退火算法步驟1 Starting with an initial state (point);2 Perturbing the current state (point);3 Deciding whether the perturbed state can be accepted;4 Repeating the above procedure.2 Perturbing the current state (point)

16、Original Metropolis algorithm random sampling with a uniform distribution to move from one point to the next;3 Deciding whether the perturbed state can be accepted (i) If an improved solution is obtained, accepted; (ii) Otherwise, use a probability to decide its fate.35Example: SA Algorithm is the o

17、bjectivefunction.after Aarts and Korst (1989)Here to decide whether a worse move should be accepted, with a probability a kind of perturbation This parameter plays the role of temperature.36Example: A very fast SA AlgorithmMain points from basic:Draw random numbers by using 1D Cauchy for each compon

18、ent to count for different scalings;(2) Use different cooling schedules during iterations, depending on the ratio of maximum function derivative to its current derivative value.(Inger 1989)can be a problem itself37Example: SA Algorithmwith Cauchy distributionto randomly move to the next point. (after Sen & Stoffa 1995)Obviously, if T is small, only points near the current state will have a chance to select. 38Example: SA Algorithm with different cooling schedules (after Sen & Stoffa 1995)39Example: Liu et al. (1995) reported the failure of SA to find the gl