現(xiàn)代優(yōu)化計(jì)算簡介課件

1、第 13章 智能優(yōu)化計(jì)算簡介 第13章 智能優(yōu)化計(jì)算簡介 本章對目前常用的幾種智能優(yōu)化計(jì)算算法作簡單介紹，以使讀者對它們有個(gè)基本認(rèn)識(shí)。內(nèi)容包括神經(jīng)網(wǎng)絡(luò)、遺傳算法、模擬退火算法和神經(jīng)網(wǎng)絡(luò)混合優(yōu)化學(xué)習(xí)策略。 13.1人工神經(jīng)網(wǎng)絡(luò)與神經(jīng)網(wǎng)絡(luò)優(yōu)化算法 人工神經(jīng)網(wǎng)絡(luò)是近年來得到迅速發(fā)展的一個(gè)前沿課題。神經(jīng)網(wǎng)絡(luò)由于其大規(guī)模并行處理、容錯(cuò)性、自組織和自適應(yīng)能力和聯(lián)想功能強(qiáng)等特點(diǎn)，已成為解決很多問題的有力工具。本節(jié)首先對神經(jīng)網(wǎng)絡(luò)作簡單介紹，然后介紹幾種常用的神經(jīng)網(wǎng)絡(luò)，包括前向神經(jīng)網(wǎng)絡(luò)、Hopfield網(wǎng)絡(luò)。 13.1人工神經(jīng)網(wǎng)絡(luò)與神經(jīng)網(wǎng)絡(luò)優(yōu)化算法 1.人工神經(jīng)網(wǎng)絡(luò)發(fā)展簡史最早的研究可以追溯到20世紀(jì)40年代。

2、1943年，心理學(xué)家McCulloch和數(shù)學(xué)家Pitts合作提出了形式神經(jīng)元的數(shù)學(xué)模型。這一模型一般被簡稱為M-P神經(jīng)網(wǎng)絡(luò)模型，至今仍在應(yīng)用，可以說，人工神經(jīng)網(wǎng)絡(luò)的研究時(shí)代，就由此開始了。1949年，心理學(xué)家Hebb提出神經(jīng)系統(tǒng)的學(xué)習(xí)規(guī)則，為神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)算法奠定了基礎(chǔ)?，F(xiàn)在，這個(gè)規(guī)則被稱為Hebb規(guī)則，許多人工神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)還遵循這一規(guī)則。 13.1人工神經(jīng)網(wǎng)絡(luò)與神經(jīng)網(wǎng)絡(luò)優(yōu)化算法1957年，F(xiàn).Rosenblatt提出“感知器”(Perceptron) 模型，第一次把神經(jīng)網(wǎng)絡(luò)的研究從純理論的探討付諸于工程實(shí)踐，掀起了人工神經(jīng)網(wǎng)絡(luò)研究的第一次高潮。20世紀(jì)60年代以后，數(shù)字計(jì)算機(jī)的發(fā)展達(dá)到全盛

3、時(shí)期，人們誤以為數(shù)字計(jì)算機(jī)可以解決人工智能、專家系統(tǒng)、模式識(shí)別問題，從而放松了對“感知器”的研究。于是，從20世紀(jì)60年代末起，人工神經(jīng)網(wǎng)絡(luò)的研究進(jìn)入了低潮。 13.1人工神經(jīng)網(wǎng)絡(luò)與神經(jīng)網(wǎng)絡(luò)優(yōu)化算法1982年，美國加州工學(xué)院物理學(xué)家Hopfield提出了離散的神經(jīng)網(wǎng)絡(luò)模型，標(biāo)志著神經(jīng)網(wǎng)絡(luò)的研究又進(jìn)入了一個(gè)新高潮。1984年，Hopfield又提出連續(xù)神經(jīng)網(wǎng)絡(luò)模型，開拓了計(jì)算機(jī)應(yīng)用神經(jīng)網(wǎng)絡(luò)的新途徑。1986年，Rumelhart和Meclelland提出多層網(wǎng)絡(luò)的誤差反傳(Back-propagation)學(xué)習(xí)算法，簡稱BP算法。BP算法是目前最為重要、應(yīng)用最廣的人工神經(jīng)網(wǎng)絡(luò)算法之一。 13.1

4、人工神經(jīng)網(wǎng)絡(luò)與神經(jīng)網(wǎng)絡(luò)優(yōu)化算法自20世紀(jì)80年代中期以來，世界上許多國家掀起了神經(jīng)網(wǎng)絡(luò)的研究熱潮，可以說神經(jīng)網(wǎng)絡(luò)已成為國際上的一個(gè)研究熱點(diǎn)。 13.1人工神經(jīng)網(wǎng)絡(luò)與神經(jīng)網(wǎng)絡(luò)優(yōu)化算法2.人工神經(jīng)元模型與人工神經(jīng)網(wǎng)絡(luò)模型人工神經(jīng)元是一個(gè)多輸入、單輸出的非線性元件，如圖11-1所示。其輸入、輸出關(guān)系可描述為 13.1人工神經(jīng)網(wǎng)絡(luò)與神經(jīng)網(wǎng)絡(luò)優(yōu)化算法 (1)式中， 是從其他神經(jīng)元傳來的輸入信號(hào)； 是閾值； 表示從神經(jīng)元到神經(jīng)元 的連接權(quán)值； 為傳遞函數(shù)。 13.1 人工神經(jīng)網(wǎng)絡(luò)與神經(jīng)網(wǎng)絡(luò)優(yōu)化算法 yjjx0=1 fnjx1x2 . . .xn2j1j 圖11-1 13.1 人工神經(jīng)網(wǎng)絡(luò)與神經(jīng)網(wǎng)絡(luò)優(yōu)化算法

5、人工神經(jīng)網(wǎng)絡(luò)是由大量的神經(jīng)元互聯(lián)而成的網(wǎng)絡(luò)，按其拓?fù)浣Y(jié)構(gòu)來分，可以分成兩大類：層次網(wǎng)絡(luò)模型和互聯(lián)網(wǎng)絡(luò)模型。層次網(wǎng)絡(luò)模型是神經(jīng)元分成若干層順序連接，在輸入層上加上輸入信息，通過中間各層，加權(quán)后傳遞到輸出層后輸出，其中有的在同一層中的各神經(jīng)元相互之間有連接，有的從輸出層到輸入層有反饋；互聯(lián)網(wǎng)絡(luò)模型中，任意兩個(gè)神經(jīng)元之間都有相互連接的關(guān)系，在連接中，有的神經(jīng)元之間是雙向的，有的是單向的，按實(shí)際情況決定。 13.1人工神經(jīng)網(wǎng)絡(luò)與神經(jīng)網(wǎng)絡(luò)優(yōu)化算法3 .前向神經(jīng)網(wǎng)絡(luò)(1)多層前向網(wǎng)絡(luò)一個(gè)M層的多層前向網(wǎng)絡(luò)可描述為：網(wǎng)絡(luò)包含一個(gè)輸入層（定義為第0層）和M1個(gè)隱層，最后一個(gè)隱層稱為輸出層。第 層包含 個(gè)神經(jīng)元

6、和一個(gè)閾值單元（定義為每層的第0單元），輸出層不含閾值單元。 13.1人工神經(jīng)網(wǎng)絡(luò)與神經(jīng)網(wǎng)絡(luò)優(yōu)化算法第 層第 個(gè)單元到第 個(gè)單元的權(quán)值表為 。第 層（ 0）第 個(gè)（ 0）神經(jīng)元的 輸入定義為 ，輸出定義 為 ，其中 為隱單元激勵(lì)函數(shù)，常采用Sigmoid函數(shù)，即 。輸入單元一般采用線性激勵(lì)函數(shù) ，閾值單元的輸出始終為1。 13.1人工神經(jīng)網(wǎng)絡(luò)與神經(jīng)網(wǎng)絡(luò)優(yōu)化算法 目標(biāo)函數(shù)通常采用 （2）其中，P為樣本數(shù)； 為第p個(gè)樣本的第j個(gè)輸出分量。 13.1 人工神經(jīng)網(wǎng)絡(luò)與神經(jīng)網(wǎng)絡(luò)優(yōu)化算法 BP算法 BP算法是前向神經(jīng)網(wǎng)絡(luò)經(jīng)典的有監(jiān)督學(xué)習(xí)算法，它的提出對前向神經(jīng)網(wǎng)絡(luò)的發(fā)展起過歷史性的推動(dòng)作用。對于上述的M層

7、的人工神經(jīng)網(wǎng)絡(luò)，BP算法可由下列迭代式描述，具體推導(dǎo)可參見神經(jīng)網(wǎng)絡(luò)的相關(guān)書目。 13.1人工神經(jīng)網(wǎng)絡(luò)與神經(jīng)網(wǎng)絡(luò)優(yōu)化算法 （3） 13.1人工神經(jīng)網(wǎng)絡(luò)與神經(jīng)網(wǎng)絡(luò)優(yōu)化算法 其中， 為學(xué)習(xí)率。 (4)13.1人工神經(jīng)網(wǎng)絡(luò)與神經(jīng)網(wǎng)絡(luò)優(yōu)化算法 實(shí)質(zhì)上，BP算法是一種梯度下降算法，算法性能依賴于初始條件，學(xué)習(xí)過程易于陷入局部極小。數(shù)值仿真結(jié)果表明，BP算法的學(xué)習(xí)速度、精度、初值魯棒性和網(wǎng)絡(luò)推廣性能都較差，不能滿足應(yīng)用的需要。實(shí)用中應(yīng)按照需要適當(dāng)改進(jìn)。 13.1人工神經(jīng)網(wǎng)絡(luò)與神經(jīng)網(wǎng)絡(luò)優(yōu)化算法4.Hopfield 網(wǎng)絡(luò) 1982年，Hopfield開創(chuàng)性地在物理學(xué)、神經(jīng)生物學(xué)和計(jì)算機(jī)科學(xué)等領(lǐng)域架起了橋梁，提出

8、了Hopfield 反饋神經(jīng)網(wǎng)絡(luò)模型(HNN)，證明在高強(qiáng)度連接下的神經(jīng)網(wǎng)絡(luò)依靠集體協(xié)同作用能自發(fā)產(chǎn)生計(jì)算行為。Hopfield 網(wǎng)絡(luò)是典型的全連接網(wǎng)絡(luò)，通過在網(wǎng)絡(luò)中引入能量函數(shù)以構(gòu)造動(dòng)力學(xué)系統(tǒng)，并使網(wǎng)絡(luò)的平衡態(tài)與能量函數(shù)的極小解相對應(yīng)，從而將求解能量函數(shù)極小解的過程轉(zhuǎn)化為網(wǎng)絡(luò)向平衡態(tài)的演化過程。 13.1人工神經(jīng)網(wǎng)絡(luò)與神經(jīng)網(wǎng)絡(luò)優(yōu)化算法(1) 離散型Hopfield 網(wǎng)絡(luò)離散型Hopfield 網(wǎng)絡(luò)的輸出為二值型，網(wǎng)絡(luò)采用全連接結(jié)構(gòu)。令 為各神經(jīng)元的輸出， 為各神經(jīng)元與第 個(gè)神經(jīng)元的連接權(quán)值， 為第 個(gè)神經(jīng)元的閾值，則有 13.1 人工神經(jīng)網(wǎng)絡(luò)與神經(jīng)網(wǎng)絡(luò)優(yōu)化算法 （5） 13.1 人工神經(jīng)網(wǎng)絡(luò)

9、與神經(jīng)網(wǎng)絡(luò)優(yōu)化算法能量函數(shù)定義為 (5)則其變化量為 13.1人工神經(jīng)網(wǎng)絡(luò)與神經(jīng)網(wǎng)絡(luò)優(yōu)化算法 （6）也就是說，能量函數(shù)總是隨神經(jīng)元狀態(tài)的變化而下降。 13.1人工神經(jīng)網(wǎng)絡(luò)與神經(jīng)網(wǎng)絡(luò)優(yōu)化算法(2) 連續(xù)型Hopfield 網(wǎng)絡(luò)連續(xù)型Hopfield 網(wǎng)絡(luò)的動(dòng)態(tài)方程可簡化描述如下： （7） 13.1 人工神經(jīng)網(wǎng)絡(luò)與神經(jīng)網(wǎng)絡(luò)優(yōu)化算法其中， 分別為第 個(gè)神經(jīng)元的輸入和輸出; 具有連續(xù)且單調(diào)增性質(zhì)的神經(jīng)元激勵(lì)函數(shù)； 為第i個(gè)神經(jīng)元到第j個(gè)神經(jīng)元的連接權(quán)； 為施加在第i個(gè)神經(jīng)元的偏置； 和 為相應(yīng)的電容和電阻 。13.1 人工神經(jīng)網(wǎng)絡(luò)與神經(jīng)網(wǎng)絡(luò)優(yōu)化算法定義能量函數(shù) （8）則其變化量 (9) 13.1人工神

10、經(jīng)網(wǎng)絡(luò)與神經(jīng)網(wǎng)絡(luò)優(yōu)化算法其中， 13.1人工神經(jīng)網(wǎng)絡(luò)與神經(jīng)網(wǎng)絡(luò)優(yōu)化算法于是，當(dāng) 時(shí)，有 (10) 13.1人工神經(jīng)網(wǎng)絡(luò)與神經(jīng)網(wǎng)絡(luò)優(yōu)化算法且當(dāng) 時(shí) 。因此，隨時(shí)間的增長，神經(jīng)網(wǎng)絡(luò)在狀態(tài)空間中的軌跡總是向能量函數(shù)減小的方向變化，且網(wǎng)絡(luò)的穩(wěn)定點(diǎn)就是能量函數(shù)的極小點(diǎn)。連續(xù)型Hopfield 網(wǎng)絡(luò)廣泛用于聯(lián)想記憶和優(yōu)化計(jì)算問題。 13.2遺傳算法 遺傳算法是模擬生物在自然環(huán)境中的遺傳和進(jìn)化過程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法。它最早由美國密執(zhí)安大學(xué)的Holland教授提出，起源于20世紀(jì)60年代對自然和人工自適應(yīng)系統(tǒng)的研究。20世紀(jì)70年代，De Jong基于遺傳算法的思想在計(jì)算機(jī)上進(jìn)行了大量的純

11、數(shù)值函數(shù)優(yōu)化計(jì)算實(shí)驗(yàn)。 在一系列研究工作的基礎(chǔ)上，20世紀(jì)80年代由Goldberg進(jìn)行歸納總結(jié)，形成了遺傳算法的基本框架。 13.2遺傳算法1.遺傳算法概要對于一個(gè)求函數(shù)最大值的優(yōu)化問題，一般可描述為下述數(shù)學(xué)規(guī)劃模型： (11) 式中， 為決策變量；f(X)為目標(biāo)函數(shù)；U是基本空間；R是U的一個(gè)子集。13.2遺傳算法遺傳算法中，將n維決策變量用n個(gè)記號(hào)所組成的符號(hào)串X來表示，即 把每一個(gè)Xi看做一個(gè)遺傳基因，它的所有可能取值稱為等位基因，這樣，X就可看做是由n個(gè)遺傳基因所組成的一個(gè)染色體。染色體的長度可以是固定的，也可以是變化的。等位基因可以是一組整數(shù)，也可以是某一范圍內(nèi)的實(shí)數(shù)值，或者是記號(hào)

12、。最簡單的等位基因是由0和1這兩個(gè)整數(shù)組成的，相應(yīng)的染色體就可表示為一個(gè)二進(jìn)制符號(hào)串。 13.2遺傳算法這種編碼所形成的排列形式X是個(gè)體的基因型，與它對應(yīng)的X值是個(gè)體的表現(xiàn)型。染色體X也稱為個(gè)體X，對于每一個(gè)個(gè)體X，要按照一定的規(guī)則確定出其適應(yīng)度。個(gè)體的適應(yīng)度與其對應(yīng)的個(gè)體表現(xiàn)型X的目標(biāo)函數(shù)值相關(guān)聯(lián)，X越接近于目標(biāo)函數(shù)的最優(yōu)點(diǎn)，其適應(yīng)度越大；反之，其適應(yīng)度越小。 13.2遺傳算法遺傳算法中，決策變量X組成了問題的解空間。對問題最優(yōu)解的搜索是通過對染色體X的搜索過程來進(jìn)行的，從而由所有的染色體X就組成了問題的搜索空間。 生物的進(jìn)化是以集團(tuán)為主體的。與此相對應(yīng)，遺傳算法的運(yùn)算對象是由M個(gè)個(gè)體所組成

13、的集合，稱為群體。 13.2遺傳算法與生物一代一代的自然進(jìn)化過程相似，遺傳算法的運(yùn)算過程也是一個(gè)反復(fù)迭代過程，第t代群體記作P(t),經(jīng)過一代遺傳和進(jìn)化后，得到第t+1代群體，它們也是由多個(gè)個(gè)體組成的集合，記作P(t+1)。這個(gè)群體不斷地經(jīng)過遺傳和進(jìn)化操作，并且每次都按照優(yōu)勝劣汰的規(guī)則將適應(yīng)度較高的個(gè)體更多地遺傳到下一代，這樣最終在群體中將會(huì)得到一個(gè)優(yōu)良的個(gè)體X，它所對應(yīng)的表現(xiàn)型X將達(dá)到或接近于問題的最優(yōu)解 。 13.2遺傳算法生物的進(jìn)化過程主要是通過染色體之間的交叉和染色體的變異來完成的。遺傳算法中最優(yōu)解的搜索過程也模仿生物的這個(gè)進(jìn)化過程，使用所謂的遺傳算子作用于群體中，進(jìn)行下述遺傳操作，從

14、而得到新一代群體。選擇(selection):根據(jù)各個(gè)個(gè)體的適應(yīng)度，按照一定的規(guī)則或方法，從第t代群體P(t)中選擇出一些優(yōu)良的個(gè)體遺傳到下一代群體P(t+1)中。 交叉(crossover):將群體P(t)內(nèi)的各個(gè)個(gè)體隨機(jī)搭配成對，對每一個(gè)個(gè)體，以某個(gè)概率(稱為交叉概率，crossover rate)交換它們之間的部分染色體。變異(mutation):對群體P(t)中的每一個(gè)個(gè)體，以某一概率(稱為變異概率，mutation rate)改變某一個(gè)或一些基因座上基因值為其他的等位基因。 13.2遺傳算法2.遺傳算法的特點(diǎn)遺傳算法是一類可用于復(fù)雜系統(tǒng)優(yōu)化計(jì)算的魯棒搜索算法，主要有下述幾個(gè)特點(diǎn)：遺傳

15、算法以決策變量的編碼作為運(yùn)算對象。傳統(tǒng)的優(yōu)化算法往往直接利用決策變量的實(shí)際值本身進(jìn)行優(yōu)化計(jì)算，但遺傳算法不是直接以決策變量的值，而是以決策變量的某種形式的編碼為運(yùn)算對象，從而可以很方便地引入和應(yīng)用遺傳操作算子。 遺傳算法直接以目標(biāo)函數(shù)值作為搜索信息。傳統(tǒng)的優(yōu)化算法往往不只需要目標(biāo)函數(shù)值，還需要目標(biāo)函數(shù)的導(dǎo)數(shù)等其他信息。這樣對許多目標(biāo)函數(shù)無法求導(dǎo)或很難求導(dǎo)的函數(shù)而言，遺傳算法就比較方便。 13.2遺傳算法遺傳算法同時(shí)進(jìn)行解空間的多點(diǎn)搜索。傳統(tǒng)的優(yōu)化算法往往從解空間的一個(gè)初始點(diǎn)開始搜索，這樣容易陷入局部極值點(diǎn)。遺傳算法進(jìn)行群體搜索，而且在搜索的過程中引入遺傳運(yùn)算，使群體又可以不斷進(jìn)化。這些是遺傳算

16、法所特有的一種隱含并行性。遺傳算法使用概率搜索技術(shù)。遺傳算法屬于一種自適應(yīng)概率搜索技術(shù)，其選擇、交叉、變異等運(yùn)算都是以一種概率的方式來進(jìn)行的，從而增加了其搜索過程的靈活性。實(shí)踐和理論都已證明了在一定條件下遺傳算法總是以概率1收斂于問題的最優(yōu)解。 13.2遺傳算法3.遺傳算法的應(yīng)用遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問題的通用框架，它不依賴于問題的具體領(lǐng)域，對問題的種類有很強(qiáng)的魯棒性，所以廣泛應(yīng)用于很多學(xué)科。下面列舉一些遺傳算法的主要應(yīng)用領(lǐng)域。函數(shù)優(yōu)化函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是對遺傳算法進(jìn)行性能測試評價(jià)的常用算例。對于一些非線性、多模型、多目標(biāo)的函數(shù)優(yōu)化問題，用其他優(yōu)化方法較難求解，而

17、遺傳算法卻可以方便地得到較好的結(jié)果。 組合優(yōu)化遺傳算法是尋求組合優(yōu)化問題滿意解的最佳工具之一，實(shí)踐證明，遺傳算法對于組合優(yōu)化問題中的NP完全問題非常有效。 13.2遺傳算法生產(chǎn)調(diào)度問題生產(chǎn)調(diào)度問題在很多情況下所建立起來的數(shù)學(xué)模型難以精確求解，即使經(jīng)過一些簡化之后可以進(jìn)行求解，也會(huì)因簡化得太多而使求解結(jié)果與實(shí)際相差太遠(yuǎn)。現(xiàn)在遺傳算法已經(jīng)成為解決復(fù)雜調(diào)度問題的有效工具。 自動(dòng)控制遺傳算法已經(jīng)在自動(dòng)控制領(lǐng)域中得到了很好的應(yīng)用，例如基于遺傳算法的模糊控制器的優(yōu)化設(shè)計(jì)、基于遺傳算法的參數(shù)辨識(shí)、基于遺傳算法的模糊控制規(guī)則的學(xué)習(xí)、利用遺傳算法進(jìn)行人工神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)優(yōu)化設(shè)計(jì)和權(quán)值學(xué)習(xí)等。 13.2遺傳算法機(jī)器

18、人學(xué)機(jī)器人是一類復(fù)雜的難以精確建模的人工系統(tǒng)，而遺傳算法的起源就來自于對人工自適應(yīng)系統(tǒng)的研究，所以機(jī)器人學(xué)自然成為遺傳算法的一個(gè)重要應(yīng)用領(lǐng)域。 圖像處理圖像處理是計(jì)算機(jī)視覺中的一個(gè)重要研究領(lǐng)域。在圖像處理過程中，如掃描、特征提取、圖像分割等不可避免地存在一些誤差，這些誤差會(huì)影響圖像處理的效果。如何使這些誤差最小是使計(jì)算機(jī)視覺達(dá)到實(shí)用化的重要要求，遺傳算法在這些圖像處理中的優(yōu)化計(jì)算方面得到了很好的應(yīng)用。 13.2遺傳算法人工生命人工生命是用計(jì)算機(jī)、機(jī)械等人工媒體模擬或構(gòu)造出的具有自然生物系統(tǒng)特有行為的人造系統(tǒng)。自組織能力和自學(xué)習(xí)能力是人工生命的兩大重要特征。人工生命與遺傳算法有著密切的關(guān)系，基于

19、遺傳算法的進(jìn)化模型是研究人工生命現(xiàn)象的重要理論基礎(chǔ)。 13.2遺傳算法遺傳編程Koza發(fā)展了遺傳編程的概念，他使用了以LISP語言所表示的編碼方法，基于對一種樹形結(jié)構(gòu)所進(jìn)行的遺傳操作來自動(dòng)生成計(jì)算機(jī)程序。 機(jī)器學(xué)習(xí)基于遺傳算法的機(jī)器學(xué)習(xí)，在很多領(lǐng)域中都得到了應(yīng)用。例如，基于遺傳算法的機(jī)器學(xué)習(xí)可用來調(diào)整人工神經(jīng)網(wǎng)絡(luò)的連接權(quán)，也可以用于人工神經(jīng)網(wǎng)絡(luò)的網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化設(shè)計(jì)。 13.2遺傳算法4.基本遺傳算法基本遺傳算法（Simple Genetic Algorithms,簡稱SGA）是一種統(tǒng)一的最基本的遺傳算法，它只使用選擇、交叉、變異這三種基本遺傳算子，其遺傳進(jìn)化操作過程簡單，容易理解，是其他一些遺傳

20、算法的雛形和基礎(chǔ)，它不僅給各種遺傳算法提供了一個(gè)基本框架，同時(shí)也具有一定的應(yīng)用價(jià)值。 13.2遺傳算法 基本遺傳算法的構(gòu)成要素 染色體編碼方法?；具z傳算法使用固定長度的二進(jìn)制符號(hào)串來表示群體中的個(gè)體，其等位基因是由二值符號(hào)集0，1所組成的。初始群體中各個(gè)個(gè)體的基因值可用均勻分布的隨機(jī)數(shù)來生成。 13.2 遺傳算法個(gè)體適應(yīng)度評價(jià)?；具z傳算法按與個(gè)體適應(yīng)度成正比的概率來決定當(dāng)前群體中每個(gè)個(gè)體遺傳到下一代群體中的機(jī)會(huì)多少。為正確計(jì)算這個(gè)概率，這里要求所有個(gè)體的適應(yīng)度必須為正數(shù)或零。遺傳算子。基本遺傳算法使用下述三種遺傳算子：選擇運(yùn)算使用比例選擇算子，交叉運(yùn)算使用單點(diǎn)交叉算子，變異運(yùn)算使用基本位變

21、異算子或均勻變異算子。 13.2遺傳算法基本遺傳算法的運(yùn)行參數(shù)?；具z傳算法有下述4個(gè)運(yùn)行參數(shù)需要提前設(shè)定：群體大小M，即群體中所含個(gè)體數(shù)目，一般取為20100；遺傳運(yùn)算的終止進(jìn)化代數(shù)T，一般取為100500； 交叉概率pc，一般取為0.40.99； 變異概率pm，一般取為0.00010.1。 13.2 遺傳算法基本遺傳算法的形式化定義基本遺傳算法可定義為一個(gè)8元組： (12) 13.2 遺傳算法式中 C個(gè)體的編碼方法； E個(gè)體適應(yīng)度評價(jià)函數(shù)； P0 初始群體； M 群體大小； 選擇算子； 交叉算子； 變異算子； T 遺傳運(yùn)算終止條件。 13.2遺傳算法 基本遺傳算法的實(shí)現(xiàn)個(gè)體適應(yīng)度評價(jià)在遺傳

22、算法中，以個(gè)體適應(yīng)度的大小來確定該個(gè)體被遺傳到下一代群體中的概率。個(gè)體適應(yīng)度越大，該個(gè)體被遺傳到下一代的概率也越大；反之，個(gè)體的適應(yīng)度越小，該個(gè)體被遺傳到下一代的概率也越小。基本遺傳算法使用比例選擇算子來確定群體中各個(gè)個(gè)體遺傳到下一代群體中的數(shù)量。為正確計(jì)算不同情況下各個(gè)個(gè)體的遺傳概率，要求所有個(gè)體的適應(yīng)度必須為正數(shù)或零，不能是負(fù)數(shù)。 13.2遺傳算法為滿足適應(yīng)度取非負(fù)值的要求，基本遺傳算法一般采用下面兩種方法之一將目標(biāo)函數(shù)值變換為個(gè)體的適應(yīng)度。方法一：對于目標(biāo)函數(shù)是求極大化，其為 (13) 13.2遺傳算法式中，Cmin 為一個(gè)適當(dāng)?shù)叵鄬Ρ容^小的數(shù)，它可用下面幾種方法之一來選取:預(yù)先指定的一

23、個(gè)較小的數(shù)；進(jìn)化到當(dāng)前代為止的最小目標(biāo)函數(shù)值；當(dāng)前代或最近幾代群體中的最小目標(biāo)值。 13.2 遺傳算法比例選擇算子比例選擇實(shí)際上是一種有退還隨機(jī)選擇,也叫做賭盤(Roulette Wheel)選擇，因?yàn)檫@種選擇方式與賭博中的賭盤操作原理非常相似。比例選擇算子的具體執(zhí)行過程是：先計(jì)算出群體中所有個(gè)體的適應(yīng)度之和；其次計(jì)算出每個(gè)個(gè)體的相對適應(yīng)度的大小，此值即為各個(gè)個(gè)體被遺傳到下一代群體中的概率；最后再使用模擬賭盤操作（即0到1之間的隨機(jī)數(shù)）來確定各個(gè)個(gè)體被選中的次數(shù)。 13.2遺傳算法單點(diǎn)交叉算子單點(diǎn)交叉算子是最常用和最基本的交叉操作算子。單點(diǎn)交叉算子的具體執(zhí)行過程如下：對群體中的個(gè)體進(jìn)行兩兩隨機(jī)

24、配對；對每一對相互配對的個(gè)體，隨機(jī)設(shè)置某一基因座之后的位置為交叉點(diǎn)；對每一對相互配對的個(gè)體，依設(shè)定的交叉概率 在其交叉點(diǎn)處相互交換兩個(gè)個(gè)體的部分染色體，從而產(chǎn)生出兩個(gè)新個(gè)體。 13.2遺傳算法基本位變異算子基本位變異算子的具體執(zhí)行過程為：對個(gè)體的每一個(gè)基因座，依變異概率 指定其為變異點(diǎn)；對每一個(gè)指定的變異點(diǎn)，對其基因值作取反運(yùn)算或用其他等位基因值來代替，從而產(chǎn)生出一個(gè)新的個(gè)體。 13.2遺傳算法 遺傳算法的應(yīng)用步驟確定決策變量及其各種約束條件，即確定出個(gè)體的表現(xiàn)型X和問題的解空間；建立優(yōu)化模型，即描述出目標(biāo)函數(shù)的類型及其數(shù)學(xué)描述形式或量化方法； 確定表示可行解的染色體編碼方法，即確定出個(gè)體的基

25、因型X及遺傳算法的搜索空間；確定解碼方法，即確定出由個(gè)體基因型X到個(gè)體表現(xiàn)型X的對應(yīng)關(guān)系或轉(zhuǎn)換方法；確定個(gè)體適應(yīng)度的量化評價(jià)方法，即確定出由目標(biāo)函數(shù)值 到個(gè)體適應(yīng)度的轉(zhuǎn)換規(guī)則； 設(shè)計(jì)遺傳算子，即確定出選擇運(yùn)算、交叉運(yùn)算、變異運(yùn)算等遺傳算子的具體操作方法；確定遺傳算法的有關(guān)運(yùn)行參數(shù)，即確定出遺傳算法的 等參數(shù)。 13.2遺傳算法5.遺傳算法的模式定理Holland提出的模式定理（schema theorem），是遺傳算法的基本原理，從進(jìn)化動(dòng)力學(xué)的角度提供了能夠較好地解釋遺傳算法機(jī)理的一種數(shù)學(xué)工具，同時(shí)也是編碼策略、遺傳策略等分析的基礎(chǔ)。模式定理：在選擇、交叉、變異算子的作用下，那些低階、定義長度

26、短、超過群體平均適應(yīng)值的模式的生存數(shù)量，將隨著迭代次數(shù)的增加以指數(shù)規(guī)律增長。 13.2遺傳算法6. Genetic Algorithm ToolboxMATLAB提供了遺傳算法與直接搜索（ Genetic Algorithm And Direct Search Toolbox ）工具箱。GAT計(jì)算的標(biāo)準(zhǔn)形式：13.2遺傳算法6. Genetic Algorithm Toolbox例：求解如下優(yōu)化問題：13.3 模擬退火算法 模擬退火算法(simulated annealing,簡稱SA)的思想最早是由Metropolis等(1953)提出的，1983年Kirkpatrick等將其用于組合優(yōu)化。

27、SA算法是基于Monte Carlo迭代求解策略的一種隨機(jī)尋優(yōu)算法，其出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過程與一般組合優(yōu)化問題之間的相似性。 13.3 模擬退火算法 模擬退火算法在某一初溫下，伴隨溫度參數(shù)的不斷下降，結(jié)合概率突跳特性在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解，即在局部最優(yōu)解能概率性地跳出并最終趨于全局最優(yōu)解。模擬退火算法是一種通用的優(yōu)化算法，目前已在工程中得到了廣泛應(yīng)用。 13.3 模擬退火算法1.物理退火過程和Metropolis準(zhǔn)則簡單而言，物理退火過程由以下三部分組成：加溫過程。其目的是增強(qiáng)粒子的熱運(yùn)動(dòng)，使其偏離平衡位置。當(dāng)溫度足夠高時(shí)，固體將溶解為液體，從而消除系統(tǒng)原先可能存

28、在的非均勻態(tài)，使隨后進(jìn)行的冷卻過程以某一平衡態(tài)為起點(diǎn)。溶解過程與系統(tǒng)的熵增過程聯(lián)系，系統(tǒng)能量也隨溫度的升高而增大。 13.3 模擬退火算法等溫過程。物理學(xué)的知識(shí)告訴我們，對于與周圍環(huán)境交換熱量而溫度不變的封閉系統(tǒng)，系統(tǒng)狀態(tài)的自發(fā)變化總是朝自由能減少的方向進(jìn)行，當(dāng)自由能達(dá)到最小時(shí)，系統(tǒng)達(dá)到平衡態(tài)。冷卻過程。目的是使粒子的熱運(yùn)動(dòng)減弱并漸趨有序，系統(tǒng)能量逐漸下降，從而得到低能的晶體結(jié)構(gòu)。 13.3 模擬退火算法 Metropolis等在1953年提出了重要性采樣法，即以概率接受新狀態(tài)。具體而言，在溫度t，由當(dāng)前狀態(tài)i產(chǎn)生新狀態(tài)j，兩者的能量分別為 ，若 ，則接受新狀態(tài)j為當(dāng)前狀態(tài)；否則，若概率 大于

29、 區(qū)間內(nèi)的隨機(jī)數(shù)，則仍舊接受新狀態(tài)j為當(dāng)前狀態(tài)，若不成立則保留i為當(dāng)前狀態(tài)，其中k為Boltzmann常數(shù)。 13.3 模擬退火算法 這種重要性采樣過程在高溫下可接受與當(dāng)前狀態(tài)能量差較大的新狀態(tài)，而在低溫下基本只接受與當(dāng)前能量差較小的新狀態(tài)，而且當(dāng)溫度趨于零時(shí)，就不能接受比當(dāng)前狀態(tài)能量高的新狀態(tài)。這種接受準(zhǔn)則通常稱為Metropolis準(zhǔn)則。 13.3 模擬退火算法2.模擬退火算法的基本思想和步驟 1983年Kirkpatrick等意識(shí)到組合優(yōu)化與物理退火的相似性，并受到Metropolis準(zhǔn)則的啟迪，提出了模擬退火算法。模擬退火算法是基于Monte Carlo 迭代求解策略的一種隨機(jī)尋優(yōu)算法

30、，其出發(fā)點(diǎn)是基于物理退火過程與組合優(yōu)化之間的相似性，SA由某一較高初溫開始，利用具有概率突跳特性的Metropolis抽樣策略在解空間中進(jìn)行隨機(jī)搜索，伴隨溫度的不斷下降重復(fù)抽樣過程，最終得到問題的全局最優(yōu)解。 13.3 模擬退火算法標(biāo)準(zhǔn)模擬退火算法的一般步驟可描述如下： 給定初溫 ，隨機(jī)產(chǎn)生初始狀態(tài) ，令 ； Repeat: Repeat 產(chǎn)生新狀態(tài) ； 13.3 模擬退火算法 Until 抽樣穩(wěn)定準(zhǔn)則滿足； 退溫 ，并令 ； Until 算法終止準(zhǔn)則滿足； 輸出算法搜索結(jié)果。 13.3 模擬退火算法3.模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)定從算法流程上看，模擬退火算法包括三函數(shù)兩準(zhǔn)則，即狀態(tài)產(chǎn)生函

31、數(shù)、狀態(tài)接受函數(shù)、溫度更新函數(shù)、內(nèi)循環(huán)終止準(zhǔn)則和外循環(huán)終止準(zhǔn)則，這些環(huán)節(jié)的設(shè)計(jì)將決定SA算法的優(yōu)化性能。此外，初溫的選擇對SA算法性能也有很大影響。 13.3 模擬退火算法狀態(tài)產(chǎn)生函數(shù) 設(shè)計(jì)狀態(tài)產(chǎn)生函數(shù)（鄰域函數(shù)）的出發(fā)點(diǎn)應(yīng)該是盡可能保證產(chǎn)生的候選解遍布全部的解空間。通常，狀態(tài)產(chǎn)生函數(shù)由兩部分組成，即產(chǎn)生候選解的方式和候選解產(chǎn)生的概率分布。 13.3 模擬退火算法狀態(tài)接受函數(shù) 狀態(tài)接受函數(shù)一般以概率的方式給出，不同接受函數(shù)的差別主要在于接受概率的形式不同。設(shè)計(jì)狀態(tài)接受概率，應(yīng)該遵循以下原則：在固定溫度下，接受使目標(biāo)函數(shù)值下降的候選解的概率要大于使目標(biāo)值上升的候選解的概率； 13.3 模擬退火算

32、法隨溫度的下降，接受使目標(biāo)函數(shù)值上升的解的概率要逐漸減?。划?dāng)溫度趨于零時(shí)，只能接受目標(biāo)函數(shù)值下降的解。 狀態(tài)接受函數(shù)的引入是SA算法實(shí)現(xiàn)全局搜索的最關(guān)鍵的因素，SA算法中通常采用min1,exp(-C/t)作為狀態(tài)接受函數(shù)。 13.3 模擬退火算法初溫 初始溫度、溫度更新函數(shù)、內(nèi)循環(huán)終止準(zhǔn)則和外循環(huán)終止準(zhǔn)則通常被稱為退火歷程(annealing schedule)。實(shí)驗(yàn)表明，初溫越大，獲得高質(zhì)量解的幾率越大，但花費(fèi)的計(jì)算時(shí)間將增加。因此，初溫的確定應(yīng)折中考慮優(yōu)化質(zhì)量和優(yōu)化效率，常用方法包括： 13.3 模擬退火算法均勻抽樣一組狀態(tài)，以各狀態(tài)目標(biāo)值的方差為初溫。隨機(jī)產(chǎn)生一組狀態(tài)，確定兩兩狀態(tài)間的

33、最大目標(biāo)值差 ，然后依據(jù)差值，利用一定的函數(shù)確定初溫。譬如 ，其中 為初始接受概率。利用經(jīng)驗(yàn)公式給出。 13.3 模擬退火算法溫度更新函數(shù) 溫度更新函數(shù)，即溫度的下降方式，用于在外循環(huán)中修改溫度值。 目前，最常用的溫度更新函數(shù)為指數(shù)退溫函數(shù)，即其中且其大小可以不斷變化。 13.3 模擬退火算法內(nèi)循環(huán)終止準(zhǔn)則 內(nèi)循環(huán)終止準(zhǔn)則，或稱Metropolis抽樣穩(wěn)定準(zhǔn)則，用于決定在各溫度下產(chǎn)生候選解的數(shù)目。在非時(shí)齊SA算法理論中，由于在每個(gè)溫度下只產(chǎn)生一個(gè)或少量候選解，所以不存在選擇內(nèi)循環(huán)終止準(zhǔn)則的問題。 13.3 模擬退火算法 而在時(shí)齊SA算法理論中，收斂條件要求在每個(gè)溫度下產(chǎn)生候選解的數(shù)目趨于無窮大

34、，以使相應(yīng)的馬氏鏈達(dá)到平穩(wěn)概率分布，顯然在實(shí)際應(yīng)用算法時(shí)這是無法實(shí)現(xiàn)的。常用的抽樣準(zhǔn)則包括： 檢驗(yàn)?zāi)繕?biāo)函數(shù)的均值是否穩(wěn)定； 連續(xù)若干步的目標(biāo)值變化較??； 按一定的步數(shù)抽樣。 13.3 模擬退火算法外循環(huán)終止準(zhǔn)則 外循環(huán)終止準(zhǔn)則，即算法終止準(zhǔn)則，用于決定算法何時(shí)結(jié)束。設(shè)置溫度終值是一種簡單的方法。SA算法的收斂性理論中要求溫度終值趨于零，這顯然不合實(shí)際。通常的做法是： 13.3 模擬退火算法 設(shè)置終止溫度的閾值； 設(shè)置外循環(huán)迭代次數(shù)； 算法收斂到的最優(yōu)值連續(xù)若干步保持不變； 檢驗(yàn)系統(tǒng)熵是否穩(wěn)定。 13.4 神經(jīng)網(wǎng)絡(luò)權(quán)值的混合優(yōu)化學(xué)習(xí)策略 鑒于GA、SA的全局優(yōu)化特性和通用性，即優(yōu)化過程無需導(dǎo)數(shù)信

35、息，我們可以基于實(shí)數(shù)編碼構(gòu)造BPSA、BPGA混合優(yōu)化學(xué)習(xí)策略，以提高前向網(wǎng)絡(luò)學(xué)習(xí)的速度、精度，特別是避免陷入局部極小的能力。 13.4 神經(jīng)網(wǎng)絡(luò)權(quán)值的混合優(yōu)化學(xué)習(xí)策略1.BPSA混合學(xué)習(xí)策略 在BPSA混合學(xué)習(xí)策略中，采用以BP為主框架，并在學(xué)習(xí)過程中引入SA策略。這樣做，既利用了基于梯度下降的有指導(dǎo)學(xué)習(xí)來提高局部搜索性能，也利用了SA的概率突跳性來實(shí)現(xiàn)最終的全局收斂，從而可提高學(xué)習(xí)速度和精度。BPSA混合學(xué)習(xí)策略的算法步驟如下： 13.4 神經(jīng)網(wǎng)絡(luò)權(quán)值的混合優(yōu)化學(xué)習(xí)策略隨機(jī)產(chǎn)生初始權(quán)值 ，確定初溫 ，令 利用BP計(jì)算 。利用SA進(jìn)行搜索： 利用SA狀態(tài)產(chǎn)生函數(shù)產(chǎn)生新權(quán)值 ， ，其中 為隨機(jī)

36、擾動(dòng)。 13.4 神經(jīng)網(wǎng)絡(luò)權(quán)值的混合優(yōu)化學(xué)習(xí)策略 計(jì)算 的目標(biāo)函數(shù)值與 的目標(biāo)函數(shù)值之差 。 計(jì)算接受概率 。 若 ，則取 ；否則 保持不變。 13.4 神經(jīng)網(wǎng)絡(luò)權(quán)值的混合優(yōu)化學(xué)習(xí)策略(4) 利用退溫函數(shù) 進(jìn)行退溫，其中 為退溫速率。若 對應(yīng)的目標(biāo)函數(shù)滿足要求精度 ，則終止算法并輸出結(jié)果；否則，令 ，轉(zhuǎn)步驟。 13.4 神經(jīng)網(wǎng)絡(luò)權(quán)值的混合優(yōu)化學(xué)習(xí)策略2.BPGA混合學(xué)習(xí)策略 神經(jīng)網(wǎng)絡(luò)的連接權(quán)包含著神經(jīng)網(wǎng)絡(luò)系統(tǒng)的全部知識(shí)。反向傳播的BP神經(jīng)網(wǎng)絡(luò)(back propagation network)的學(xué)習(xí)算法是基于梯度下降的，因而具有以下缺點(diǎn)：網(wǎng)絡(luò)訓(xùn)練速度慢、容易陷入局部極小值、全局搜索能力差等。而

37、遺傳算法的搜索遍及整個(gè)解空間，因此容易得到全局最優(yōu)解，而且遺傳算法不要求目標(biāo)函數(shù)連續(xù)、可微，甚至不要求目標(biāo)函數(shù)有顯函數(shù)的形式，只要求問題可計(jì)算。13.4 神經(jīng)網(wǎng)絡(luò)權(quán)值的混合優(yōu)化學(xué)習(xí)策略 因此，將擅長全局搜索的遺傳算法和局部尋優(yōu)能力較強(qiáng)的BP算法結(jié)合起來，可以避免陷入局部極小值，提高算法收斂速度，很快找到問題的全局最優(yōu)解。 BP算法和遺傳算法結(jié)合訓(xùn)練神經(jīng)網(wǎng)絡(luò)權(quán)重的主要步驟為： 13.4 神經(jīng)網(wǎng)絡(luò)權(quán)值的混合優(yōu)化學(xué)習(xí)策略(1) 以神經(jīng)網(wǎng)絡(luò)節(jié)點(diǎn)之間的連接權(quán)重和節(jié)點(diǎn)的閾值為參數(shù)，采用實(shí)數(shù)編碼。采用三層神經(jīng)網(wǎng)絡(luò)，設(shè)輸入節(jié)點(diǎn)數(shù)為p，輸出節(jié)點(diǎn)數(shù)為q，隱層節(jié)點(diǎn)數(shù)為r，則編碼長度n為 （14） 13.4 神經(jīng)網(wǎng)絡(luò)權(quán)值的混合優(yōu)化學(xué)習(xí)策略 (2)設(shè)定神經(jīng)網(wǎng)絡(luò)節(jié)點(diǎn)連接權(quán)重的取值范圍 ,產(chǎn)生相應(yīng)范圍的均勻分布隨機(jī)數(shù)賦給基因值，產(chǎn)生初始群體； (3)對群體中個(gè)體進(jìn)行評價(jià)。將