現(xiàn)代計算方法講座

1、現(xiàn)代計算方法專題現(xiàn)代計算方法專題提綱提綱 進(jìn)化計算方法（遺傳算法）進(jìn)化計算方法（遺傳算法） 人工神經(jīng)網(wǎng)絡(luò)人工神經(jīng)網(wǎng)絡(luò) 蟻群智能計算蟻群智能計算 數(shù)據(jù)挖掘技術(shù)與方法（支持向量機(jī)）數(shù)據(jù)挖掘技術(shù)與方法（支持向量機(jī)）背景介紹背景介紹 2121世紀(jì)，系統(tǒng)生物學(xué)的誕生進(jìn)一步提世紀(jì)，系統(tǒng)生物學(xué)的誕生進(jìn)一步提升了后基因組時代的生命科學(xué)研究能力。升了后基因組時代的生命科學(xué)研究能力。正如胡德所說：正如胡德所說：“系統(tǒng)生物學(xué)將是系統(tǒng)生物學(xué)將是2121世紀(jì)世紀(jì)醫(yī)學(xué)和生物學(xué)的核心驅(qū)動力。醫(yī)學(xué)和生物學(xué)的核心驅(qū)動力?！?生物學(xué)世紀(jì)的兩樁令人矚目的科學(xué)事件生物學(xué)世紀(jì)的兩樁令人矚目的科學(xué)事件 19941994年年, ,美國科學(xué)

2、家美國科學(xué)家adelmanadelman在在sciencescience上發(fā)表了第上發(fā)表了第一篇用一篇用dnadna分子的生化反應(yīng)進(jìn)行計算并解決人類數(shù)分子的生化反應(yīng)進(jìn)行計算并解決人類數(shù)學(xué)問題的開創(chuàng)性文章。這個事件則向人們揭示，生學(xué)問題的開創(chuàng)性文章。這個事件則向人們揭示，生命體也是計算的主體，不僅人、動物甚至更簡單的命體也是計算的主體，不僅人、動物甚至更簡單的生命物質(zhì)也會進(jìn)行計算，例如細(xì)胞核生命物質(zhì)也會進(jìn)行計算，例如細(xì)胞核dnadna份子也可份子也可以是計算的主體。以是計算的主體。 20032003年年, ,人類染色體的人類染色體的dnadna全序列測序完成，從此人全序列測序完成，從此人類有了自

3、己的遺傳密碼。這件事告訴人們生命體是類有了自己的遺傳密碼。這件事告訴人們生命體是計算的產(chǎn)物，這種計算依賴的數(shù)據(jù)和計算程序的編計算的產(chǎn)物，這種計算依賴的數(shù)據(jù)和計算程序的編碼隱藏在人類已測定的碼隱藏在人類已測定的3030億個堿基對中。億個堿基對中。 進(jìn)入進(jìn)入2121世紀(jì)短短的世紀(jì)短短的1010年，年，向生命世界學(xué)習(xí)計算的思想悄向生命世界學(xué)習(xí)計算的思想悄然在科學(xué)界傳播開來，形成新然在科學(xué)界傳播開來，形成新的計算主義。的計算主義。一、進(jìn)化計算方法（遺傳算法）一、進(jìn)化計算方法（遺傳算法） 兩種力量導(dǎo)致了生物進(jìn)化的產(chǎn)生，構(gòu)成進(jìn)兩種力量導(dǎo)致了生物進(jìn)化的產(chǎn)生，構(gòu)成進(jìn)化的基本要素：變異與選擇?；幕疽兀鹤儺?/p>

4、與選擇。 根據(jù)現(xiàn)代生物進(jìn)化理論，所有的生物體的根據(jù)現(xiàn)代生物進(jìn)化理論，所有的生物體的特征及其變化都受到基因的控制，并將自特征及其變化都受到基因的控制，并將自己的基因拷貝給子女，這就是遺傳密碼。己的基因拷貝給子女，這就是遺傳密碼。 自然選擇是對生物的表現(xiàn)型的選擇遺傳變自然選擇是對生物的表現(xiàn)型的選擇遺傳變異是基因型中某個遺傳密碼形成突變，或異是基因型中某個遺傳密碼形成突變，或者遺傳密碼進(jìn)行重新組合。者遺傳密碼進(jìn)行重新組合。 在模仿進(jìn)化原理而形成的仿生計算中最基礎(chǔ)與典在模仿進(jìn)化原理而形成的仿生計算中最基礎(chǔ)與典型的算法就是型的算法就是遺傳算法遺傳算法( (genetic algorithm)geneti

5、c algorithm) 遺傳算法是遺傳算法是john hollandjohn holland開發(fā)的一種進(jìn)化算法開發(fā)的一種進(jìn)化算法 遺傳算法的基本操作：遺傳算法的基本操作： step 1step 1 將問題求解的對象編碼成由基因組成的將問題求解的對象編碼成由基因組成的染色體；染色體； step 2step 2 設(shè)計雜交和變異規(guī)則；設(shè)計雜交和變異規(guī)則； step 3step 3 設(shè)計適應(yīng)值函數(shù)并進(jìn)行遺傳操作。設(shè)計適應(yīng)值函數(shù)并進(jìn)行遺傳操作。 gaga的形式化定義的形式化定義 記記 為抽象的個體，為抽象的個體， 為所有字符長度為為所有字符長度為 的二進(jìn)制串的集合。種群的二進(jìn)制串的集合。種群 表示為表

6、示為 個個體的一個組，記為個個體的一個組，記為 ，定義適，定義適應(yīng)值函數(shù)應(yīng)值函數(shù) ( (實數(shù)實數(shù)) )， 稱為個體的適應(yīng)值。選擇操作的算子定義稱為個體的適應(yīng)值。選擇操作的算子定義為為 ；雜交操作的算子；雜交操作的算子 ；變異；變異操作的算子操作的算子 。定義。定義 為雜交概率，為雜交概率， 為變異概率，則一下七元組就定義了一個為變異概率，則一下七元組就定義了一個遺傳運算（即為一個特定的遺傳運算（即為一個特定的gaga） lpblbl12(,)npp ppnlpb:lfbr()if p:lls bb:lllc bbb:llm bb0,1cp 0,1mp ( , , ,)cmgap f s c m

7、 p p案例案例 實例目標(biāo)函數(shù)作圖，實例目標(biāo)函數(shù)作圖，matlabmatlab程序程序 x = -1: 0.01: 2;y = x .* sin(10*pi * x) + 2.0;plot(x, y);grid on; 二、人工神經(jīng)網(wǎng)絡(luò)二、人工神經(jīng)網(wǎng)絡(luò) 早在早在2020世紀(jì)上半葉開始了這個領(lǐng)域的研究，在多世紀(jì)上半葉開始了這個領(lǐng)域的研究，在多半個世紀(jì)的發(fā)展中成為無論在理論還是應(yīng)用方面半個世紀(jì)的發(fā)展中成為無論在理論還是應(yīng)用方面都日趨成熟的仿生計算分支。都日趨成熟的仿生計算分支。 神經(jīng)網(wǎng)絡(luò)具有學(xué)習(xí)功能，其學(xué)習(xí)也稱訓(xùn)練。神經(jīng)神經(jīng)網(wǎng)絡(luò)具有學(xué)習(xí)功能，其學(xué)習(xí)也稱訓(xùn)練。神經(jīng)網(wǎng)絡(luò)能夠從環(huán)境中學(xué)習(xí)，從而以新的方式

8、對環(huán)境網(wǎng)絡(luò)能夠從環(huán)境中學(xué)習(xí)，從而以新的方式對環(huán)境的變化作出反應(yīng)時神經(jīng)網(wǎng)絡(luò)最有意義的性質(zhì)。的變化作出反應(yīng)時神經(jīng)網(wǎng)絡(luò)最有意義的性質(zhì)。 19491949年年hebbhebb提出了最著名的經(jīng)典學(xué)習(xí)規(guī)則，稱為提出了最著名的經(jīng)典學(xué)習(xí)規(guī)則，稱為hebbhebb學(xué)習(xí)規(guī)則，用于調(diào)整神經(jīng)網(wǎng)絡(luò)的突觸權(quán)值。學(xué)習(xí)規(guī)則，用于調(diào)整神經(jīng)網(wǎng)絡(luò)的突觸權(quán)值。 人工神經(jīng)網(wǎng)絡(luò)是大量模擬神經(jīng)元互連而成的網(wǎng)絡(luò)，人工神經(jīng)網(wǎng)絡(luò)是大量模擬神經(jīng)元互連而成的網(wǎng)絡(luò)， 是人腦的抽象、簡化、模擬，反映人腦的基本特征。是人腦的抽象、簡化、模擬，反映人腦的基本特征。annann模型具有下面三個要素：模型具有下面三個要素：具有一組突觸連接，用表示神經(jīng)元與的聯(lián)結(jié)

9、強(qiáng)具有一組突觸連接，用表示神經(jīng)元與的聯(lián)結(jié)強(qiáng)度，或稱為權(quán)值，但度，或稱為權(quán)值，但annann的權(quán)值可取正與負(fù)值。的權(quán)值可取正與負(fù)值。具有反映生物神經(jīng)元時空整合功能的輸入信號具有反映生物神經(jīng)元時空整合功能的輸入信號累加器。累加器。具有一個激勵函數(shù)，勇于轉(zhuǎn)換神經(jīng)元的輸出。具有一個激勵函數(shù)，勇于轉(zhuǎn)換神經(jīng)元的輸出。激勵函數(shù)將輸出信號壓縮激勵函數(shù)將輸出信號壓縮( (限制限制) )形成一個范圍形成一個范圍的有限值。的有限值。 人工神經(jīng)網(wǎng)絡(luò)的基本方法人工神經(jīng)網(wǎng)絡(luò)的基本方法step 1 step 1 設(shè)計神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)，特別是學(xué)習(xí)方法；設(shè)計神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)，特別是學(xué)習(xí)方法；step 2 step 2 利用訓(xùn)練集求解神

10、經(jīng)網(wǎng)絡(luò)參數(shù)；利用訓(xùn)練集求解神經(jīng)網(wǎng)絡(luò)參數(shù)；step 3 step 3 對已有參數(shù)進(jìn)行計算并學(xué)習(xí)修正網(wǎng)絡(luò)參對已有參數(shù)進(jìn)行計算并學(xué)習(xí)修正網(wǎng)絡(luò)參數(shù)。數(shù)。案例案例人工神經(jīng)網(wǎng)絡(luò)模型中激勵函數(shù)人工神經(jīng)網(wǎng)絡(luò)模型中激勵函數(shù)sigmoidsigmoid圖像圖像 ，matlabmatlab程序如下程序如下 ：v = -10: 0.1: 10;a = .5;f = 1./(1 + exp(-a * v);plot(v, f, red);hold on;% another a:a = .8;f = 1./(1 + exp(-a * v);plot(v, f, blue);% once more:a = 2;f = 1.

11、/(1 + exp(-a * v);plot(v, f, green); 19431943年，神經(jīng)生物學(xué)家年，神經(jīng)生物學(xué)家w.mccullchw.mccullch和數(shù)學(xué)家和數(shù)學(xué)家w.pittsw.pitts在著名的論文在著名的論文神經(jīng)活動內(nèi)容概念的邏輯神經(jīng)活動內(nèi)容概念的邏輯演算演算中總結(jié)生物神經(jīng)元的基本生理特征，提出了中總結(jié)生物神經(jīng)元的基本生理特征，提出了第一個神經(jīng)計算模型，即神經(jīng)元的閾值元件模型，第一個神經(jīng)計算模型，即神經(jīng)元的閾值元件模型，簡稱簡稱mpmp模型。模型。 19491949年，加拿大心理學(xué)家年，加拿大心理學(xué)家douald hebbdouald hebb在他的論在他的論著著行為的組

12、織行為的組織一文中，對大腦神經(jīng)元的學(xué)習(xí)與一文中，對大腦神經(jīng)元的學(xué)習(xí)與條件反射做了大膽假設(shè)：如果兩個神經(jīng)元都處于興條件反射做了大膽假設(shè)：如果兩個神經(jīng)元都處于興奮激活狀態(tài)，那么彼此的突出聯(lián)結(jié)權(quán)機(jī)會得到加強(qiáng)。奮激活狀態(tài)，那么彼此的突出聯(lián)結(jié)權(quán)機(jī)會得到加強(qiáng)。這就是著名的這就是著名的hebbhebb學(xué)習(xí)規(guī)則。學(xué)習(xí)規(guī)則。 rochester, john hollandrochester, john holland與與ibmibm公司的研究人員公司的研究人員合作以網(wǎng)絡(luò)吸收經(jīng)驗來調(diào)節(jié)強(qiáng)度模擬了合作以網(wǎng)絡(luò)吸收經(jīng)驗來調(diào)節(jié)強(qiáng)度模擬了hebbhebb的學(xué)習(xí)的學(xué)習(xí)規(guī)則，并在計算機(jī)上實現(xiàn)了學(xué)習(xí)，產(chǎn)生了許多涌現(xiàn)規(guī)則，并在計算

13、機(jī)上實現(xiàn)了學(xué)習(xí)，產(chǎn)生了許多涌現(xiàn)現(xiàn)象，使計算機(jī)有了類似人腦的學(xué)習(xí)功能?，F(xiàn)象，使計算機(jī)有了類似人腦的學(xué)習(xí)功能。 三、蟻群智能計算三、蟻群智能計算 生物群體的行為反應(yīng)了生物的集群智生物群體的行為反應(yīng)了生物的集群智能，例如鳥群飛行的自動隊列、魚群在游能，例如鳥群飛行的自動隊列、魚群在游動中交換位置、細(xì)胞群有序地傳播信息等，動中交換位置、細(xì)胞群有序地傳播信息等，表現(xiàn)出十分有效的群體決策能力。各種不表現(xiàn)出十分有效的群體決策能力。各種不同的集群智能現(xiàn)象啟發(fā)人們產(chǎn)生不同的模同的集群智能現(xiàn)象啟發(fā)人們產(chǎn)生不同的模仿集群智能的算法，例如蟻群算法、粒子仿集群智能的算法，例如蟻群算法、粒子群算法、元胞自動機(jī)算法等。群算

14、法、元胞自動機(jī)算法等。 蟻群算法的基本假設(shè)蟻群算法的基本假設(shè) 螞蟻之間通過信息素和環(huán)境進(jìn)行通信，每只螞蟻螞蟻之間通過信息素和環(huán)境進(jìn)行通信，每只螞蟻只根據(jù)其鄰近的局部環(huán)境做出反應(yīng)，并發(fā)生影響。只根據(jù)其鄰近的局部環(huán)境做出反應(yīng)，并發(fā)生影響。 螞蟻對環(huán)境的反應(yīng)由其自身原因決定。由于生物螞蟻對環(huán)境的反應(yīng)由其自身原因決定。由于生物的基因?qū)W說，可以認(rèn)為實際上是其基因的適應(yīng)性的基因?qū)W說，可以認(rèn)為實際上是其基因的適應(yīng)性表現(xiàn)，即螞蟻是對環(huán)境反應(yīng)的表現(xiàn)型主體。表現(xiàn)，即螞蟻是對環(huán)境反應(yīng)的表現(xiàn)型主體。 在個體水平上每只螞蟻僅根據(jù)環(huán)境作獨立選擇，在個體水平上每只螞蟻僅根據(jù)環(huán)境作獨立選擇，而在群體水平上單只螞蟻的行為是隨機(jī)

15、的，但是而在群體水平上單只螞蟻的行為是隨機(jī)的，但是螞蟻可通過關(guān)聯(lián)性，自組織地形成高度有序的群螞蟻可通過關(guān)聯(lián)性，自組織地形成高度有序的群體行為。體行為。蟻群算法的基本模型設(shè)計蟻群算法的基本模型設(shè)計step 1 step 1 將問題求解的目標(biāo)編譯成空間將問題求解的目標(biāo)編譯成空間路徑的圖問題；路徑的圖問題；step 2 step 2 設(shè)計抽象螞蟻的行為規(guī)則、狀設(shè)計抽象螞蟻的行為規(guī)則、狀態(tài)轉(zhuǎn)移規(guī)則、信息更新規(guī)則；態(tài)轉(zhuǎn)移規(guī)則、信息更新規(guī)則；step 3 step 3 迭代終止條件設(shè)定。迭代終止條件設(shè)定。 案例案例 問題描述：設(shè)有問題描述：設(shè)有n n個城市，坐標(biāo)已知，個城市，坐標(biāo)已知，n n個個城市構(gòu)成一

16、個完全圖，利用蟻群算法找出城市構(gòu)成一個完全圖，利用蟻群算法找出從一個城市出發(fā)走遍每個城市，并且不重從一個城市出發(fā)走遍每個城市，并且不重復(fù)到達(dá)任一個城市的最短路徑。復(fù)到達(dá)任一個城市的最短路徑。 實現(xiàn)該問題的程序?qū)崿F(xiàn)該問題的程序function r_best, l_best, l_ave, shortest_route, shortest_length =. acatsp(c, nc_max, m, alpha, beta, rho,q) %=% acatsp.m% ant colony algorithm for traveling salesman problem%-% 主要符號說明：主要符號

17、說明：% cn個城市的坐標(biāo)，個城市的坐標(biāo)，n2的矩陣的矩陣% nc_max 最大迭代次數(shù)最大迭代次數(shù)% m螞蟻個數(shù)螞蟻個數(shù)% alpha表征信息素重要程度的參數(shù)表征信息素重要程度的參數(shù)% beta表征啟發(fā)式因子重要程度的參數(shù)表征啟發(fā)式因子重要程度的參數(shù)% rho信息素蒸發(fā)系數(shù)信息素蒸發(fā)系數(shù)% q信息素增加強(qiáng)度系數(shù)信息素增加強(qiáng)度系數(shù)% r_best各代最佳路線各代最佳路線% l_best各代最佳路線的長度各代最佳路線的長度%=% 第一步：參數(shù)初始化：第一步：參數(shù)初始化：n = size(c, 1); % n表示問題的規(guī)模（城市個數(shù)）表示問題的規(guī)模（城市個數(shù)）d = zeros(n, n); %

18、d表示完全圖的賦權(quán)鄰接矩陣表示完全圖的賦權(quán)鄰接矩陣for i = 1: n for j = 1: n if i = j % 計算距離計算距離 d(i, j) = ( (c(i,1)-c(j,1)2 + (c(i,2)-c(j,2)2 )0.5; else d(i, j) = eps; end d(j, i) = d(i, j); end % jend % ueta = 1 ./ d; % eta為啟發(fā)因子，這里設(shè)為距離的倒數(shù)為啟發(fā)因子，這里設(shè)為距離的倒數(shù)tau = ones(n, n); % tau為信息素矩陣為信息素矩陣tabu = zeros(m, n); % 存儲并記錄路徑的生成存儲并記

19、錄路徑的生成r_best = zeros(nc_max, n); % 各代最佳路線各代最佳路線l_best = inf .* ones(nc_max, 1); % 各代最佳路線的長度各代最佳路線的長度l_ave = zeros(nc_max, 1); % 各代路線的平均長度各代路線的平均長度for nc = 1: nc_max %第二步：循環(huán)變量迭代。停止條件之一：達(dá)到第二步：循環(huán)變量迭代。停止條件之一：達(dá)到最大迭代次數(shù)最大迭代次數(shù) % 將將m只螞蟻放到只螞蟻放到n個城市上個城市上 randpos = ; for i = 1: ( ceil(m/n) ) randpos = randpos,

20、randperm(n); end tabu(:, 1) = (randpos(1, 1: m); for j = 2: n for i = 1: m % 第三、四步：螞蟻標(biāo)號迭代第三、四步：螞蟻標(biāo)號迭代 visited = tabu(i, 1: (j-1); % 已訪問的城市已訪問的城市 j = zeros(1, (n-j+1); % 待訪問的城市待訪問的城市 p = j; % 待訪問城市的選擇概率分布待訪問城市的選擇概率分布 jc = 1; for k = 1: n if length( find(visited = k) ) = 0 j(jc) = k; jc = jc + 1; end

21、end % 第五步：計算可選節(jié)點的選擇概率第五步：計算可選節(jié)點的選擇概率 for k = 1: length(j) p(k) = ( tau(visited(end), j(k)alpha ). *( eta(visited(end), j(k)beta ); end p = p / (sum(p); % 第五步續(xù)：按最大概率選取節(jié)點第五步續(xù)：按最大概率選取節(jié)點 pcum = cumsum(p); select = find(pcum = rand); to_visit = j( select(1) ); % 第六步：更新禁忌表第六步：更新禁忌表 tabu(i, j) = to_visit;

22、end % i end % j % 第七步：第七步：i, j循環(huán)循環(huán) if nc = 2 tabu(1, :) = r_best(nc-1, :); end % 記錄本次迭代最佳路線記錄本次迭代最佳路線 l = zeros(m, 1); for i = 1: m r = tabu(i, :); for j = 1: (n-1) l(i) = l(i) + d(r(j), r(j+1); end l(i) = l(i) + d(r(1), r(n); end l_best(nc) = min(l); pos = find(l = l_best(nc); r_best(nc, :) = tabu(

23、pos(1), :); l_ave(nc) = mean(l); % 第八步：更新信息素第八步：更新信息素 delta_tau = zeros(n, n); for i = 1: m for j = 1: (n-1) delta_tau(tabu(i, j), tabu(i, j+1). =delta_tau(tabu(i, j), tabu(i, j+1) + q/l(i); end delta_tau(tabu(i, n), tabu(i, 1). =delta_tau(tabu(i, n), tabu(i, 1) + q/l(i); end tau = (1-rho) .* tau +

24、delta_tau; % 第九步：禁忌表清零第九步：禁忌表清零 tabu = zeros(m, n);end % 第九步續(xù)：完成，輸出結(jié)果第九步續(xù)：完成，輸出結(jié)果 pos = find(l_best = min(l_best); shortest_route = r_best(pos(1), :); shortest_length = l_best(pos(1); subplot(1, 2, 1); drawroute(c, shortest_route); subplot(1, 2, 2); plot(l_best); hold on; plot(l_ave);說明：圖中左圖是找出的最短路徑

25、，其中圓點表示城市，橫縱軸表示坐說明：圖中左圖是找出的最短路徑，其中圓點表示城市，橫縱軸表示坐標(biāo)。圖中右圖橫坐標(biāo)表示迭代次數(shù)標(biāo)。圖中右圖橫坐標(biāo)表示迭代次數(shù)( (算法一共執(zhí)行的次數(shù)算法一共執(zhí)行的次數(shù)) )，縱軸表示路，縱軸表示路徑長度。其中圖中下面線是表示在蟻群算法中，分別迭代徑長度。其中圖中下面線是表示在蟻群算法中，分別迭代k k次，在次，在m m條路條路徑中最短的一條路徑長度，上面線是表示在徑中最短的一條路徑長度，上面線是表示在m m調(diào)路徑中平均路徑的長度。調(diào)路徑中平均路徑的長度。 四、數(shù)據(jù)挖掘技術(shù)（支持向量機(jī)算法）四、數(shù)據(jù)挖掘技術(shù)（支持向量機(jī)算法） 數(shù)據(jù)挖掘是從大量的、不完全的、有噪聲的、模糊的、隨數(shù)據(jù)挖掘是從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的數(shù)據(jù)集中識別新穎的、潛在有用的以及最終可理解的機(jī)的數(shù)據(jù)集中識別新穎的、潛在有用的以及最終可理解的非平凡模式和知識的過程。它是一門涉及面很廣的交叉學(xué)非平凡模式和知識的過程。它是一門涉及面很廣的交叉學(xué)科，包括機(jī)器學(xué)習(xí)、數(shù)理統(tǒng)計、神經(jīng)網(wǎng)絡(luò)、數(shù)據(jù)庫、模式科，包括機(jī)器學(xué)習(xí)、數(shù)理統(tǒng)計、神經(jīng)網(wǎng)絡(luò)、數(shù)據(jù)庫、模式識別、粗糙集、模糊數(shù)學(xué)等相關(guān)技術(shù)。識別、粗糙集、模糊數(shù)學(xué)等相關(guān)技術(shù)。 v. vapn