016先進算法講義

《016先進算法講義》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、先進算法講義在本講義中，我們將著重講述一些數(shù)學(xué)建模中常用的算法，包括神經(jīng)網(wǎng)絡(luò)算法、遺傳算法、模擬退火算法和模糊數(shù)學(xué)方法。用這些算法可以較容易地解決一些很復(fù)雜的，常規(guī)算法很難解決的問題。由于這些算法都有著很深的理論背景，因此，本講義中不可能也沒有必要詳細地討論這些算法的理論，我們的目標(biāo)在于應(yīng)用，大家只需大概了解這些算法的原理，知道能用這些算法解決一類什么樣的問題，并能應(yīng)用這些算法解決數(shù)學(xué)建模中的一些問題即可。因為著眼于應(yīng)用，所以我們還提供了一些程序代碼，使用者只需套用這些程序，便可使問題得到很好的解決。第一節(jié)神經(jīng)網(wǎng)絡(luò)1．神經(jīng)網(wǎng)絡(luò)的簡單原理人工神經(jīng)網(wǎng)絡(luò)是根據(jù)人的認識過

2、程而開發(fā)出的一種算法。假如我們現(xiàn)在只有一些輸入和相應(yīng)的輸出，而對如何由輸入得到輸出的機理并不清楚，那么我們可以把輸入與輸出之間的未知過程看成是一個“網(wǎng)絡(luò)”，通過不斷地給這個網(wǎng)絡(luò)輸入和相應(yīng)的輸出來“訓(xùn)練”這個網(wǎng)絡(luò)，網(wǎng)絡(luò)根據(jù)輸入和輸出不斷地調(diào)節(jié)自己的各節(jié)點之間的權(quán)值來滿足輸入和輸出。這樣，當(dāng)訓(xùn)練結(jié)束后，我們給定一個輸入，網(wǎng)絡(luò)便會根據(jù)自己已調(diào)節(jié)好的權(quán)值計算出一個輸出。這就是神經(jīng)網(wǎng)絡(luò)的簡單原理。2．神經(jīng)元和神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)如上所述，神經(jīng)網(wǎng)絡(luò)的基本結(jié)構(gòu)如下圖所示：神經(jīng)網(wǎng)絡(luò)一般都有多層，分為輸入層，輸出層和隱含層，層數(shù)越多，計算結(jié)果越精確，但所需的時間也就越長，所以實際應(yīng)用中要

3、根據(jù)要求設(shè)計網(wǎng)絡(luò)層數(shù)。神經(jīng)網(wǎng)絡(luò)中每一個節(jié)點叫做一個人工神經(jīng)元，他對應(yīng)于人腦中的神經(jīng)元，兩者的結(jié)構(gòu)比較如下圖：一個人工神經(jīng)元一般有多個輸入和一個輸出，另外有一個激發(fā)函數(shù)，不同的激發(fā)函數(shù)對應(yīng)了不同的網(wǎng)絡(luò)，也決定了網(wǎng)絡(luò)的用途。3．神經(jīng)網(wǎng)絡(luò)的分類神經(jīng)網(wǎng)絡(luò)按照網(wǎng)絡(luò)結(jié)構(gòu)和激發(fā)函數(shù)的不同可分為許多種，我們在此只是對感知器和BP網(wǎng)絡(luò)進行簡介。感知器：最早也是最簡單的一種神經(jīng)網(wǎng)絡(luò)，它的神經(jīng)元激發(fā)函數(shù)為階躍函數(shù)，其神經(jīng)元結(jié)構(gòu)如下圖：感知器主要用于分類。BP網(wǎng)絡(luò)：應(yīng)用得最為廣泛，最為重要的一種神經(jīng)網(wǎng)絡(luò)。這種網(wǎng)絡(luò)一般有多層，網(wǎng)絡(luò)結(jié)構(gòu)如下：BP網(wǎng)絡(luò)的激發(fā)函數(shù)一般采用S型函數(shù)，如正切或?qū)?shù)函

4、數(shù)，其神經(jīng)元結(jié)構(gòu)如下：BP網(wǎng)絡(luò)的用途十分廣泛，可用于以下方面：函數(shù)逼近：用輸入矢量和相應(yīng)的輸出矢量訓(xùn)練一個網(wǎng)絡(luò)逼近一個函數(shù)模式識別：用一個特定的輸出矢量將它與輸入矢量聯(lián)系起來分類：把輸入矢量以所定義的合適方式進行分類數(shù)據(jù)壓縮：減少輸出矢量維數(shù)以便于傳輸或存儲4．神經(jīng)網(wǎng)絡(luò)在數(shù)學(xué)建模中的應(yīng)用數(shù)學(xué)建模中有很多題目都可以用神經(jīng)網(wǎng)絡(luò)加以解決，比較典型的題目有：DNA序列分類題（2000年全國賽A題），癌癥判斷題（2001年北京大學(xué)數(shù)學(xué)建模競賽），乳房癌的診斷題（2001年全國大學(xué)生數(shù)學(xué)建模夏令營C題）。下面我們使用神經(jīng)網(wǎng)絡(luò)的方法解決癌癥判斷題（2001年北京大學(xué)數(shù)學(xué)建模競賽

5、），題目如下：附件中的文件給出了一個114個基因,60個人的基因表達水平的樣本.其中前20個是癌癥病人的基因表達水平的樣本(其中還可能有子類),其后的是20個正常人的基因表達信息樣本,其余的20個是待檢測的樣本(未知它們是否正常).(1).試設(shè)法找出描述癌癥與正常樣本在基因表達水平上的區(qū)別,建立數(shù)學(xué)模型,及識別方法,去預(yù)測待檢測樣本是癌癥還是正常樣本.(2).設(shè)計圖示(可視化)方法,使得在你的數(shù)學(xué)模型下,盡量清楚地表現(xiàn)癌癥與正常樣本在基因表達水平上的區(qū)別,以及癌癥樣本中是否有子類.這道題是很典型的用神經(jīng)網(wǎng)絡(luò)的分類問題，只需用感知器神經(jīng)網(wǎng)絡(luò)便能完成此分類工作，我們用

6、前40組數(shù)據(jù)對網(wǎng)絡(luò)進行訓(xùn)練，再用訓(xùn)練號的網(wǎng)絡(luò)來計算后20組數(shù)據(jù)，便能得到分類的結(jié)果。詳細的程序可參見本講義附帶的Matlab程序。5．神經(jīng)網(wǎng)絡(luò)的程序設(shè)計該講義附帶了如下程序資源：Matlab神經(jīng)網(wǎng)絡(luò)工具箱函數(shù)簡介癌癥判斷題（2001年北京大學(xué)數(shù)學(xué)建模競賽）的Matlab程序第二節(jié)遺傳算法1．遺傳算法的簡單原理遺傳算法(GeneticAlgorithm,GA)是一種基于自然群體遺傳演化機制的高效探索算法，它摒棄了傳統(tǒng)的搜索方式，模擬自然界生物進化過程，采用人工進化的方式對目標(biāo)空間進行隨機化搜索。它將問題域中的可能解看作是群體的一個個體或染色體，并將每一個體編碼成符號

7、串形式，模擬達爾文的遺傳選擇和自然淘汰的生物進化過程，對群體反復(fù)進行基于遺傳學(xué)的操作（遺傳，交叉和變異），根據(jù)預(yù)定的目標(biāo)適應(yīng)度函數(shù)對每個個體進行評價，依據(jù)適者生存，優(yōu)勝劣汰的進化規(guī)則，不斷得到更優(yōu)的群體，同時以全局并行搜索方式來搜索優(yōu)化群體中的最優(yōu)個體，求得滿足要求的最優(yōu)解。我們先通過一個例子來了解遺傳算法的原理：2假定我們要求函數(shù)f(x)=x的極大值，其中x為自然數(shù)，0≤x≤31?，F(xiàn)在，我們將每一個數(shù)看成一個生命體，通過進化，我們看誰能最后生存下來，誰就是我們所尋找的數(shù)。①．編碼我們將每一個數(shù)作為一個生命體，那么必須給其賦予一定的基因，這個過程叫做編碼。我們可以

8、把變量x編