智能計算考試

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