現(xiàn)代計(jì)算方法概論

現(xiàn)代計(jì)算方法專題提綱進(jìn)化計(jì)算方法（遺傳算法）人工神經(jīng)網(wǎng)絡(luò)蟻群智能計(jì)算數(shù)據(jù)挖掘技術(shù)與方法（支持向量機(jī)）背景介紹

21世紀(jì)，系統(tǒng)生物學(xué)的誕生進(jìn)一步提升了后基因組時(shí)代的生命科學(xué)研究能力。正如胡德所說：“系統(tǒng)生物學(xué)將是21世紀(jì)醫(yī)學(xué)和生物學(xué)的核心驅(qū)動(dòng)力?！?/p>

生物學(xué)世紀(jì)的兩樁令人矚目的科學(xué)事件◆1994年,美國(guó)科學(xué)家Adelman在Science上發(fā)表了第一篇用DNA分子的生化反應(yīng)進(jìn)行計(jì)算并解決人類數(shù)學(xué)問題的開創(chuàng)性文章。這個(gè)事件則向人們揭示，生命體也是計(jì)算的主體，不僅人、動(dòng)物甚至更簡(jiǎn)單的生命物質(zhì)也會(huì)進(jìn)行計(jì)算，例如細(xì)胞核DNA份子也可以是計(jì)算的主體?！?/p>

2003年,人類染色體的DNA全序列測(cè)序完成，從此人類有了自己的遺傳密碼。這件事告訴人們生命體是計(jì)算的產(chǎn)物，這種計(jì)算依賴的數(shù)據(jù)和計(jì)算程序的編碼隱藏在人類已測(cè)定的30億個(gè)堿基對(duì)中。

進(jìn)入21世紀(jì)短短的10年，向生命世界學(xué)習(xí)計(jì)算的思想悄然在科學(xué)界傳播開來，形成新的計(jì)算主義。一、進(jìn)化計(jì)算方法（遺傳算法）兩種力量導(dǎo)致了生物進(jìn)化的產(chǎn)生，構(gòu)成進(jìn)化的基本要素：變異與選擇。根據(jù)現(xiàn)代生物進(jìn)化理論，所有的生物體的特征及其變化都受到基因的控制，并將自己的基因拷貝給子女，這就是遺傳密碼。自然選擇是對(duì)生物的表現(xiàn)型的選擇遺傳變異是基因型中某個(gè)遺傳密碼形成突變，或者遺傳密碼進(jìn)行重新組合。

在模仿進(jìn)化原理而形成的仿生計(jì)算中最基礎(chǔ)與典型的算法就是遺傳算法(GeneticAlgorithm)遺傳算法是JohnHolland開發(fā)的一種進(jìn)化算法遺傳算法的基本操作：

Step1將問題求解的對(duì)象編碼成由基因組成的染色體；

Step2設(shè)計(jì)雜交和變異規(guī)則；

Step3設(shè)計(jì)適應(yīng)值函數(shù)并進(jìn)行遺傳操作。

GA的形式化定義記為抽象的個(gè)體，為所有字符長(zhǎng)度為的二進(jìn)制串的集合。種群表示為個(gè)個(gè)體的一個(gè)組，記為，定義適應(yīng)值函數(shù)(實(shí)數(shù))，稱為個(gè)體的適應(yīng)值。選擇操作的算子定義為；雜交操作的算子；變異操作的算子。定義為雜交概率，為變異概率，則一下七元組就定義了一個(gè)遺傳運(yùn)算（即為一個(gè)特定的GA）

案例實(shí)例目標(biāo)函數(shù)作圖，Matlab程序

x=-1:0.01:2;y=x.*sin(10*pi*x)+2.0;plot(x,y);gridon;二、人工神經(jīng)網(wǎng)絡(luò)早在20世紀(jì)上半葉開始了這個(gè)領(lǐng)域的研究，在多半個(gè)世紀(jì)的發(fā)展中成為無論在理論還是應(yīng)用方面都日趨成熟的仿生計(jì)算分支。神經(jīng)網(wǎng)絡(luò)具有學(xué)習(xí)功能，其學(xué)習(xí)也稱訓(xùn)練。神經(jīng)網(wǎng)絡(luò)能夠從環(huán)境中學(xué)習(xí)，從而以新的方式對(duì)環(huán)境的變化作出反應(yīng)時(shí)神經(jīng)網(wǎng)絡(luò)最有意義的性質(zhì)。1949年Hebb提出了最著名的經(jīng)典學(xué)習(xí)規(guī)則，稱為Hebb學(xué)習(xí)規(guī)則，用于調(diào)整神經(jīng)網(wǎng)絡(luò)的突觸權(quán)值。

人工神經(jīng)網(wǎng)絡(luò)是大量模擬神經(jīng)元互連而成的網(wǎng)絡(luò)，

是人腦的抽象、簡(jiǎn)化、模擬，反映人腦的基本特征。ANN模型具有下面三個(gè)要素：◆具有一組突觸連接，用表示神經(jīng)元與的聯(lián)結(jié)強(qiáng)度，或稱為權(quán)值，但ANN的權(quán)值可取正與負(fù)值?！艟哂蟹从成锷窠?jīng)元時(shí)空整合功能的輸入信號(hào)累加器。◆具有一個(gè)激勵(lì)函數(shù)，勇于轉(zhuǎn)換神經(jīng)元的輸出。激勵(lì)函數(shù)將輸出信號(hào)壓縮(限制)形成一個(gè)范圍的有限值。

人工神經(jīng)網(wǎng)絡(luò)的基本方法Step1設(shè)計(jì)神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)，特別是學(xué)習(xí)方法；Step2利用訓(xùn)練集求解神經(jīng)網(wǎng)絡(luò)參數(shù)；Step3對(duì)已有參數(shù)進(jìn)行計(jì)算并學(xué)習(xí)修正網(wǎng)絡(luò)參數(shù)。案例人工神經(jīng)網(wǎng)絡(luò)模型中激勵(lì)函數(shù)Sigmoid圖像，Matlab程序如下：v=-10:0.1:10;a=.5;f=1./(1+exp(-a*v));plot(v,f,'red');holdon;%another'a':a=.8;f=1./(1+exp(-a*v));plot(v,f,'blue');%oncemore:a=2;f=1./(1+exp(-a*v));plot(v,f,'green');

◆1943年，神經(jīng)生物學(xué)家W.McCullch和數(shù)學(xué)家W.Pitts在著名的論文《神經(jīng)活動(dòng)內(nèi)容概念的邏輯演算》中總結(jié)生物神經(jīng)元的基本生理特征，提出了第一個(gè)神經(jīng)計(jì)算模型，即神經(jīng)元的閾值元件模型，簡(jiǎn)稱MP模型。

◆1949年，加拿大心理學(xué)家DoualdHebb在他的論著《行為的組織》一文中，對(duì)大腦神經(jīng)元的學(xué)習(xí)與條件反射做了大膽假設(shè)：如果兩個(gè)神經(jīng)元都處于興奮激活狀態(tài)，那么彼此的突出聯(lián)結(jié)權(quán)機(jī)會(huì)得到加強(qiáng)。這就是著名的Hebb學(xué)習(xí)規(guī)則。

◆Rochester,JohnHolland與IBM公司的研究人員合作以網(wǎng)絡(luò)吸收經(jīng)驗(yàn)來調(diào)節(jié)強(qiáng)度模擬了Hebb的學(xué)習(xí)規(guī)則，并在計(jì)算機(jī)上實(shí)現(xiàn)了學(xué)習(xí)，產(chǎn)生了許多涌現(xiàn)現(xiàn)象，使計(jì)算機(jī)有了類似人腦的學(xué)習(xí)功能。

三、蟻群智能計(jì)算

生物群體的行為反應(yīng)了生物的集群智能，例如鳥群飛行的自動(dòng)隊(duì)列、魚群在游動(dòng)中交換位置、細(xì)胞群有序地傳播信息等，表現(xiàn)出十分有效的群體決策能力。各種不同的集群智能現(xiàn)象啟發(fā)人們產(chǎn)生不同的模仿集群智能的算法，例如蟻群算法、粒子群算法、元胞自動(dòng)機(jī)算法等。蟻群算法的基本假設(shè)◆螞蟻之間通過信息素和環(huán)境進(jìn)行通信，每只螞蟻只根據(jù)其鄰近的局部環(huán)境做出反應(yīng)，并發(fā)生影響?！粑浵亴?duì)環(huán)境的反應(yīng)由其自身原因決定。由于生物的基因?qū)W說，可以認(rèn)為實(shí)際上是其基因的適應(yīng)性表現(xiàn)，即螞蟻是對(duì)環(huán)境反應(yīng)的表現(xiàn)型主體。◆

在個(gè)體水平上每只螞蟻僅根據(jù)環(huán)境作獨(dú)立選擇，而在群體水平上單只螞蟻的行為是隨機(jī)的，但是螞蟻可通過關(guān)聯(lián)性，自組織地形成高度有序的群體行為。蟻群算法的基本模型設(shè)計(jì)Step1將問題求解的目標(biāo)編譯成空間路徑的圖問題；Step2設(shè)計(jì)抽象螞蟻的行為規(guī)則、狀態(tài)轉(zhuǎn)移規(guī)則、信息更新規(guī)則；Step3迭代終止條件設(shè)定。案例

問題描述：設(shè)有n個(gè)城市，坐標(biāo)已知，n個(gè)城市構(gòu)成一個(gè)完全圖，利用蟻群算法找出從一個(gè)城市出發(fā)走遍每個(gè)城市，并且不重復(fù)到達(dá)任一個(gè)城市的最短路徑。

實(shí)現(xiàn)該問題的程序function[R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=...ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q)%%=====================================================================%ACATSP.m%AntColonyAlgorithmforTravelingSalesmanProblem%%---------------------------------------------------------------------%主要符號(hào)說明：%C n個(gè)城市的坐標(biāo)，n×2的矩陣%NC_max 最大迭代次數(shù)%m 螞蟻個(gè)數(shù)%Alpha 表征信息素重要程度的參數(shù)%Beta 表征啟發(fā)式因子重要程度的參數(shù)%Rho 信息素蒸發(fā)系數(shù)%Q 信息素增加強(qiáng)度系數(shù)%R_best 各代最佳路線%L_best 各代最佳路線的長(zhǎng)度%%=================================================%第一步：參數(shù)初始化：n=size(C,1);%n表示問題的規(guī)模（城市個(gè)數(shù)）D=zeros(n,n);%D表示完全圖的賦權(quán)鄰接矩陣fori=1:nforj=1:nifi~=j%計(jì)算距離D(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5;elseD(i,j)=eps;endD(j,i)=D(i,j);end%jend%uEta=1./D;%Eta為啟發(fā)因子，這里設(shè)為距離的倒數(shù)Tau=ones(n,n);%Tau為信息素矩陣Tabu=zeros(m,n);%存儲(chǔ)并記錄路徑的生成R_best=zeros(NC_max,n);%各代最佳路線L_best=inf.*ones(NC_max,1);%各代最佳路線的長(zhǎng)度L_ave=zeros(NC_max,1);%各代路線的平均長(zhǎng)度forNC=1:NC_max%第二步：循環(huán)變量迭代。停止條件之一：達(dá)到最大迭代次數(shù)%將m只螞蟻放到n個(gè)城市上Randpos=[];fori=1:(ceil(m/n))Randpos=[Randpos,randperm(n)];endTabu(:,1)=(Randpos(1,1:m))';forj=2:nfori=1:m%第三、四步：螞蟻標(biāo)號(hào)迭代

visited=Tabu(i,1:(j-1));%已訪問的城市J=zeros(1,(n-j+1));%待訪問的城市P=J;%待訪問