智能計(jì)算考試

優(yōu)化技術(shù)：以數(shù)學(xué)為基礎(chǔ)，解決各種工程問題優(yōu)化解。用途：系統(tǒng)控制、人工智能、模式識(shí)別、生產(chǎn)調(diào)度；傳統(tǒng)優(yōu)化方法：待解決的問題是連續(xù)性問題，以微積分為基礎(chǔ)，規(guī)模較小；理論上的準(zhǔn)確與完美，主要方法：線性與非線性規(guī)劃、動(dòng)態(tài)規(guī)劃、多目標(biāo)規(guī)劃、整數(shù)規(guī)劃等，排隊(duì)論、庫存論、對(duì)策論、決策論等；傳統(tǒng)的評(píng)價(jià)方法：算法收斂性、收斂速度;現(xiàn)代優(yōu)化方法：待解決的問題離散性、不確定性、大規(guī)模；有啟發(fā)式算法、追求滿意、實(shí)用性強(qiáng)；現(xiàn)在的評(píng)價(jià)方法：算法復(fù)雜性。最優(yōu)化問題及其分類：函數(shù)優(yōu)化問題：令S為Rn上的有界子集，f：S->R為n維實(shí)值函數(shù)，所謂函數(shù)f在S域上全局最小化就是尋求點(diǎn)Xmin€S使得f(Xmin)在S域上全局最小。組合優(yōu)化問題：令Q={s1，s2，…，％}為所有狀態(tài)構(gòu)成的解的空間，C(si)為狀態(tài)si對(duì)應(yīng)的目標(biāo)函數(shù)值，要求尋找最優(yōu)解s*，，使得對(duì)于所有的Si€Q，C(S*)=minC(S「 ’啟發(fā)式算法：一個(gè)基于直觀或經(jīng)驗(yàn)構(gòu)造的算法，在可接受的花費(fèi)下給出待解決優(yōu)化問題每一個(gè)實(shí)例的一個(gè)可行解，該可行解與最優(yōu)解的偏離程度不一定事先可以預(yù)計(jì)。它是以一種技術(shù)、不能保證所得解的最優(yōu)性。優(yōu)點(diǎn)：1.模型誤差、數(shù)據(jù)不精確性、參數(shù)估計(jì)誤差等可能造成最優(yōu)算法的解比啟發(fā)式算法的解更差；2.復(fù)雜問題無法求得最優(yōu)算法或最優(yōu)算法太復(fù)雜；簡單易行，直觀，程序簡單。缺點(diǎn)：不能保證最優(yōu)、不穩(wěn)定、依賴于實(shí)際問題和設(shè)計(jì)者的經(jīng)驗(yàn)。分類：簡單直觀的算法、數(shù)學(xué)規(guī)劃算法、現(xiàn)代優(yōu)化算法。評(píng)價(jià)算法優(yōu)劣的指標(biāo)：算法的復(fù)雜性、解的偏離程度、算法的穩(wěn)健性。評(píng)價(jià)算法優(yōu)劣的手段：最壞情況分析、概率分析、計(jì)算模擬分析。NP類問題：算法的時(shí)間復(fù)雜性：算法對(duì)時(shí)間的需要量(加、減、乘、除、比較、讀、寫等操作的總次數(shù))。算法的空間復(fù)雜性：算法對(duì)空間的需要量(存儲(chǔ)空間的大小，二進(jìn)制位數(shù))。問題的時(shí)間復(fù)雜性：所有算法中時(shí)間復(fù)雜性最小的算法時(shí)間復(fù)雜性。問題的空間復(fù)雜性：所有算法中空間復(fù)雜性最小的算法空間復(fù)雜性。定義：若一個(gè)問題的每個(gè)實(shí)例只有“是”或“否”兩種回答，則稱該問題為判定問題。若存在一個(gè)多項(xiàng)式g(x)和一個(gè)驗(yàn)證算法H，對(duì)一類判定問題A的任何一個(gè)“是”的判定實(shí)例I都存在一個(gè)字符串S是I的“是”回答，滿足其輸入長度d(S)不超過g(d(I))(其中d(I)為I的輸入長度)，且驗(yàn)證算法驗(yàn)證S為I的“是”回答的計(jì)算時(shí)間不超過g(d(I))，則稱判定問題A為非多項(xiàng)式確定問題，簡稱NP問題。模擬退火算法：模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。根據(jù)Metropolis準(zhǔn)則，粒子在溫度T時(shí)趨于平衡的概率為e-AE/(kT)，其中E為溫度T時(shí)的內(nèi)能，AE為其改變量，k為Boltzmann常數(shù)。用固體退火模擬組合優(yōu)化問題，將內(nèi)能E模擬為目標(biāo)函數(shù)值f，溫度T演化成控制參數(shù)t，即得到解組合優(yōu)化問題的模擬退火算法：由初始解 i和控制參數(shù)初值t開始，對(duì)當(dāng)前解重復(fù)“產(chǎn)生新解9計(jì)算目標(biāo)函數(shù)差9接受或舍棄”的迭代，并逐步衰減t值，算法終止時(shí)的當(dāng)前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機(jī)搜索過程。退火過程由冷卻進(jìn)度表 (CoolingSchedule)控制，包括控制參數(shù)的初值t及其衰減因子&、每個(gè)t值時(shí)的迭代次數(shù)L和停止條件S。給定初溫t=t0，隨機(jī)產(chǎn)生初始狀態(tài)s=s0，令k=0；RepeatRepeat產(chǎn)生新狀態(tài)sj=Genete(s)；ifmin{1,exp[-(C(sj)-C(s))/tk]}>=randrom[0,1]s=sj;Until抽樣穩(wěn)定準(zhǔn)則滿足；退溫tk+1=update(tk)并令k=k+1；Until算法終止準(zhǔn)則滿足；輸出算法搜索結(jié)果。1)從可行解空間中任選一初始狀態(tài)x0，計(jì)算其目標(biāo)函數(shù)值f(x0)，并選擇初始控制溫度T0和馬爾可夫鏈的長度；2)在可行解空間中產(chǎn)生一個(gè)隨機(jī)擾動(dòng)，用狀態(tài)產(chǎn)生函數(shù)產(chǎn)生一個(gè)新狀態(tài)x0，計(jì)算其目標(biāo)函數(shù)值f(x1)；3)根據(jù)狀態(tài)接受函數(shù)判斷是否接受：如果f(x1)<f(x0)，則接受新狀態(tài)x1為當(dāng)前狀態(tài)，否則按Metropolis準(zhǔn)則判決是否接受x1，若接受，則令當(dāng)前狀態(tài)等于x1，若不接受，則令當(dāng)前狀態(tài)等于x0；4)跟據(jù)某個(gè)收斂準(zhǔn)則，判斷抽樣過程是否終止，是則轉(zhuǎn)5,否則轉(zhuǎn)2；5)按照某個(gè)溫度冷卻方案降低控制溫度T；6)根據(jù)某個(gè)收斂準(zhǔn)則，判斷退火過程是否終止，是則轉(zhuǎn)7,否則轉(zhuǎn)2；7)當(dāng)前解作為最優(yōu)解輸出Metropolis準(zhǔn)則(1953)——以概率接受新狀態(tài)：若在溫度T，當(dāng)前狀態(tài)if新狀態(tài)j。若Ej<Ei，則接受j為當(dāng)前狀態(tài)；否則，若概率p=exp[-(Ej-Ei)/kBT]大于[0,1)區(qū)間的隨機(jī)數(shù)，則仍接受狀態(tài)j為當(dāng)前狀態(tài)；若不成立則保留狀態(tài)i為當(dāng)前狀態(tài)。在高溫下，可接受與當(dāng)前狀態(tài)能量差較大的新狀態(tài)；在低溫下，只接受與當(dāng)前狀態(tài)能量差較小的新狀態(tài)優(yōu)點(diǎn)：質(zhì)量高、初值魯棒性強(qiáng)、簡單通用，容易實(shí)現(xiàn)。缺點(diǎn)：由于要求較高的初始溫度、較慢的降溫速率、較低的終止溫度，以及各溫度下足夠多次的抽樣，因此優(yōu)化過程較長。改進(jìn)的模擬退火算法：改進(jìn)的可行方案：(1)設(shè)計(jì)合適的狀態(tài)產(chǎn)生函數(shù)；(2)設(shè)計(jì)高效的退火歷程；(3)避免狀態(tài)的迂回搜索；(4)采用并行搜索結(jié)構(gòu)；(5)避免陷入局部極小，改進(jìn)對(duì)溫度的控制方式；(6)選擇合適的初始狀態(tài)；(7)設(shè)計(jì)合適的算法終止準(zhǔn)則。改進(jìn)的方式：(1)增加升溫或重升溫過程，避免陷入局部極?。?2)增加記憶功能(記憶“Bestsofar”狀態(tài))；(3)增加補(bǔ)充搜索過程(以最優(yōu)結(jié)果為初始解)(4)對(duì)每一當(dāng)前狀態(tài)，采用多次搜索策略，以概率接受區(qū)域內(nèi)的最優(yōu)狀態(tài)；(5)結(jié)合其它搜索機(jī)制的算法；(6)上述各方法的綜合。改進(jìn)的退火過程：(1)給定初溫t0，隨機(jī)產(chǎn)生初始狀態(tài)s，令初始最優(yōu)解s*=s，當(dāng)前狀態(tài)為s(0)=s，i=p=0；(2)令t=ti，以t，s*和s(i)調(diào)用改進(jìn)的抽樣過程，返回其所得最優(yōu)解s*'和當(dāng)前狀態(tài)s’(k)，令當(dāng)前狀態(tài)s(i)=s'(k)；(3)判斷C(s*)<C(s*’)？若是，則令p=p+1；否則，令s*=s*'，p=0；(4)退溫ti+1=update(ti)，令i=i+1；(5)判斷p>m2?若是，則轉(zhuǎn)第(6)步；否則，返回第(2)步；(6)以最優(yōu)解s*作為最終解輸出，停止算法。改進(jìn)的抽樣過程：(1)令k=0時(shí)的初始當(dāng)前狀態(tài)為s'(0)=s(i)，q=0；(2)由狀態(tài)s通過狀態(tài)產(chǎn)生函數(shù)產(chǎn)生新狀態(tài)s'，計(jì)算增量△C'=C(s')-C(s)；(3)若巡'<0，則接受s'作為當(dāng)前解，并判斷C(s*')>C(s')?若是，則令s*'=s'，q=0；否則，令q=q+1。若△C'〉0，則以概率exp(-△C'/t)接受s'作為下一當(dāng)前狀態(tài)；(4)令k=k+1，判斷q>m1?若是，則轉(zhuǎn)第(5)步；否則，返回第(2)步；(5)將當(dāng)前最優(yōu)解s*'和當(dāng)前狀態(tài)s'(k)返回改進(jìn)退火過程。遺傳算法:mm孑■［尋mm孑■［尋遺傳算法GA把問題的解表示成“染色體”，在算法中也即是以二進(jìn)制編碼的串。并且，在執(zhí)行遺傳算法之前，給出一群“染色體”，也即是假設(shè)解。然后，把這些假設(shè)解置于問題的“環(huán)境”中，并按適者生存的原則，從中選擇出較適應(yīng)環(huán)境的“染色體”進(jìn)行復(fù)制，再通過交叉，變異過程產(chǎn)生更適應(yīng)環(huán)境的新一代“染色體”群。這樣，一代一代地進(jìn)化，最后就會(huì)收斂到最適應(yīng)環(huán)境的一個(gè)“染色體”上，它就是問題的最優(yōu)解。初始化:選擇一個(gè)群體，問題的最優(yōu)解將通過這些初始假設(shè)解進(jìn)化而求出。選擇:根據(jù)適者生存原則選擇下一代的個(gè)體。在選擇時(shí)，以適應(yīng)度為選擇原則。適應(yīng)度準(zhǔn)則體現(xiàn)了適者生存，不適應(yīng)者淘汰的自然法則。交叉:對(duì)于選中用于繁殖下一代的個(gè)體，隨機(jī)地選擇兩個(gè)個(gè)體的相同位置，按交叉概率P。在選中的位置實(shí)行交換。變異:根據(jù)生物遺傳中基因變異的原理，以變異概率Pm對(duì)某些個(gè)體的某些位執(zhí)行變異。在變異時(shí)，對(duì)執(zhí)行變異的串的對(duì)應(yīng)位求反，即把1變?yōu)?，把0變?yōu)?。全局最優(yōu)收斂:當(dāng)最優(yōu)個(gè)體的適應(yīng)度達(dá)到給定的閥值，或者最優(yōu)個(gè)體的適應(yīng)度和群體適應(yīng)度不再上升時(shí)，則算法的迭代過程收斂、算法結(jié)束。否則，用經(jīng)過選擇、交叉、變異所得到的新一代群體取代上一代群體，并返回到第2步即選擇操作處繼續(xù)循環(huán)執(zhí)行。神經(jīng)網(wǎng)絡(luò)：它是一個(gè)數(shù)學(xué)模型，可以用電子線路來實(shí)現(xiàn)，也可以用計(jì)算機(jī)程序來模擬，是人工智能研究的一種方法。優(yōu)越性：具有自學(xué)習(xí)功能、具有聯(lián)想存儲(chǔ)功能、具有高速尋找優(yōu)化解的能力。應(yīng)用領(lǐng)域：模式識(shí)別、信號(hào)處理、知識(shí)工程、專家系統(tǒng)、優(yōu)化組合、機(jī)器人控制。學(xué)習(xí)(訓(xùn)練)：有監(jiān)督的學(xué)習(xí)：已知一組正確的輸入輸出結(jié)果的條件下，神經(jīng)網(wǎng)絡(luò)依據(jù)這些數(shù)據(jù)，調(diào)整并確定權(quán)值；無監(jiān)督的學(xué)習(xí)：只有輸入數(shù)據(jù)，沒有正確的輸出結(jié)果情況下，確定權(quán)值。M-P模型:y=M-P模型:y=f(z-8)=其中，sgn(x)=sgn(Uwx—8)i=1J1,x>0、0,x<0Hebb算法：當(dāng)兩個(gè)神經(jīng)元同時(shí)處于激發(fā)狀態(tài)時(shí)被加強(qiáng)，否則被減弱；數(shù)學(xué)表達(dá)式表示：Wij(t+1)=Wij(t)+aVi(t)Vj(t)；如果兩個(gè)神經(jīng)元同時(shí)興奮(即同時(shí)被激活)，則它們之間的突觸連接加強(qiáng) '■■-aJ為學(xué)習(xí)速率，Vi,Vj為神經(jīng)元i和j的輸出感知器的學(xué)習(xí)規(guī)則：輸入矢量X,輸出矢量Y,目標(biāo)矢量為O的感知器網(wǎng)絡(luò)，其學(xué)習(xí)規(guī)則為：如果第i個(gè)神經(jīng)元的輸出是正確的，即有：yi=oi，那么與第i個(gè)神經(jīng)元聯(lián)接的權(quán)值wij和偏差值bi保持不變；如果第i個(gè)神經(jīng)元的輸出是0,但期望輸出為1,即有yi=0,而oi=1,此時(shí)權(quán)值修正算法為：新的權(quán)值wij為舊的權(quán)值wij加上輸入矢量xj；類似的，新的偏差bi為舊偏差bi加上它的輸入1；如果第i個(gè)神經(jīng)元的輸出為1，但期望輸出為0，即有yi=1，而oi=0，此時(shí)權(quán)值修正算法為：新的權(quán)值wij等于舊的權(quán)值wij減去輸入矢量xj；類似的，新的偏差bi為舊偏差bi減去1。訓(xùn)練的步驟：1)對(duì)于所要解決的問題，確定輸入矢量X，目標(biāo)矢量0,并由此確定各矢量的維數(shù)以及確定網(wǎng)絡(luò)結(jié)構(gòu)大小的神經(jīng)元數(shù)目：r,s和q；2)參數(shù)初始化：a)賦給權(quán)矢量w在(-1,1)的隨機(jī)非零初始值；b)給出最大訓(xùn)練循環(huán)次數(shù)max_epoch；3)網(wǎng)絡(luò)表達(dá)式：根據(jù)輸入矢量X以及最新權(quán)矢量W,計(jì)算網(wǎng)絡(luò)輸出矢量X；4)檢查：檢查輸出矢量X與目標(biāo)矢量O是否相同，如果是，或已達(dá)最大循環(huán)次數(shù)，訓(xùn)練結(jié)束，否則轉(zhuǎn)入5)；5)學(xué)習(xí)：根據(jù)(3-1)式感知器的學(xué)習(xí)規(guī)則調(diào)整權(quán)矢量，并返回3)。自適應(yīng)的結(jié)構(gòu):步驟：1)表達(dá)：計(jì)算訓(xùn)練的輸出矢量A=W*P+B，以及與期望輸出之間的誤差E=T—A；2)檢查：將網(wǎng)絡(luò)輸出誤差的平方和與期望誤差相比較，如果其值小于期望誤差，或訓(xùn)練已達(dá)到事先設(shè)定的最大訓(xùn)練次數(shù)，則停止訓(xùn)練；否則繼續(xù)；3)學(xué)習(xí)：采用W—H學(xué)習(xí)規(guī)則計(jì)算新的權(quán)值和偏差，并返回到1)BP算法：弱點(diǎn)：訓(xùn)練速度非常慢、局部極小點(diǎn)的逃離問題、算法不一定收斂。缺點(diǎn)：廣泛的適應(yīng)性和有效性。訓(xùn)練步驟：初始化：用小的隨機(jī)數(shù)初始化每一層的權(quán)值W和偏差B,保證網(wǎng)絡(luò)不被大的加權(quán)輸入飽和。期望誤差最小值error_goal最大循環(huán)次數(shù)max_epoch修正權(quán)值的學(xué)習(xí)速率1r,一般情況下k=0.0l,0.7；變量表達(dá)：計(jì)算網(wǎng)絡(luò)各層輸出矢量A1和A2以及網(wǎng)絡(luò)誤差E。A1=tansig(W1*P,B1)、A2=purelin(W2*A1,B2)、E=T-A；權(quán)值修正：計(jì)算各層反傳的誤差變化D2和D1并計(jì)算各層權(quán)值的修正值以及新權(quán)值。D2=deltalin(A2,E)、D1=deltatan(A1,D2,W2)、[dlWl,dBl]=learnbp(P,D1,lr)、[dW2,dB2]=1earnbp(A1,D2,1r)、W1=W1十dW1；B1=B1十dBl、W2=W2十dW2；B2=B2十dB2；計(jì)算權(quán)值修正后誤差平方和SSE=sumsqr(T-purelin(W2*tansig(W1*P,B1),B2))；檢查：SSE是否小于err_goal。若是，訓(xùn)練結(jié)束；否則繼續(xù)。蟻群算法：蟻群算法是對(duì)自然界螞蟻的尋徑方式進(jìn)行模似而得出的一種仿生算法。螞蟻在運(yùn)動(dòng)過程中，能夠在它所經(jīng)過的路徑上留下一種稱之為外激素(pheromone)的物質(zhì)進(jìn)行信息傳遞，而且螞蟻在運(yùn)動(dòng)過程中能夠感知這種物質(zhì)，并以此指導(dǎo)自己的運(yùn)動(dòng)方向，因此由大量螞蟻組成的蟻群集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。粒子群算法：Initial:將群族做初始化，以隨機(jī)的方式求出每一Particle之