浙江大學(xué)秋季期末考試智能算法考試重點總結(jié)

浙江大學(xué)秋季期末考試智能算法考試重點總結(jié)什么是多項式問題(P問題)？記問題的一個實例為I，實力規(guī)模為1(1)，算法A在求解I時的計算量(基本計算總次數(shù))為CaQ)。對于給定的一個優(yōu)化問題，若存在一個求最優(yōu)解的算法、一個多項式函數(shù) g(x)和常數(shù)「，使得Ca(I)豈：7(1(1))對所有的實例成立，則給定的優(yōu)化問題是多項式時間可解問題，或簡稱多項式問題。所有多項式問題的集合記為 P。簡要敘述模擬退火算法中溫度 t，接受概率Rk，局部最優(yōu)或全局最優(yōu)解的關(guān)系；由此，在應(yīng)用模擬退火算法時齊算法到具體問題時，我們在選取初始溫度，確定同一溫度的迭代步數(shù)等方面應(yīng)注意什么？溫度t是重要的參數(shù)，其大小控制了隨機(jī)過程向局部或全局最優(yōu)解移動的快慢。溫度 t升高，接受概率Rk，有利于全局搜索，但收斂速度慢。溫度 t降低，接受概率Rk減小，收斂速度快，可能陷入局部最優(yōu)。確定同一溫度的迭代步數(shù)等方面應(yīng)注意： 1?當(dāng)溫度很高時，每一個狀態(tài)都接受的頻率基本相同， 而且?guī)缀跛械臓顟B(tài)都能被接受，此時， 在同一溫度應(yīng)使迭代的步數(shù)盡量少； 2?當(dāng)溫度漸漸更低時，越來越多的狀態(tài)被拒絕。如果在此溫度的迭代太少，則可能造成過早的陷入局部最優(yōu)狀態(tài)，比較直觀和有效的方法隨著溫度的下降，將同一溫度的迭代步增加。簡述BP網(wǎng)絡(luò)和Hopfield網(wǎng)絡(luò)有何異同？兩者都可以取離散或連續(xù)變量，但 Hopfield網(wǎng)絡(luò)考慮輸入與輸出在時間上的滯后效應(yīng)，要用動態(tài)方程描述；BP網(wǎng)絡(luò)采用梯度算法，收斂速度慢， Hopfield網(wǎng)絡(luò)采用Hebb規(guī)則，收斂速度很快；Hopfield網(wǎng)絡(luò)有類似BP網(wǎng)絡(luò)的應(yīng)用，但在優(yōu)化計算方面應(yīng)用更加突出。遺傳算法的特點是什么？處理的對象不是參數(shù)本身，是對參數(shù)集進(jìn)行了編碼的個體；同時對搜索空間的多個解進(jìn)行評估后搜索GA基本不應(yīng)搜索空間的知識或輔助信息，僅用適應(yīng)度函數(shù)來評估個體；GA不是采用編碼性規(guī)則，用概率變遷來指導(dǎo)搜索方向；或者，遺傳算法以有限的代價解決搜索和優(yōu)化，其與傳統(tǒng)搜索方法的區(qū)別主要在于：遺傳算法直接處理問題參數(shù)的適當(dāng)編碼而不是參數(shù)集本身。遺傳算法的本質(zhì)的并行性，遺傳算法按并行方式搜索一個種群數(shù)目的點，而不是單點。遺傳算法不需要求導(dǎo)或其他輔助知識，只需要適應(yīng)度函數(shù)值。遺傳算法使用概率轉(zhuǎn)換規(guī)則，而非確定的轉(zhuǎn)換規(guī)則知道搜索。遺傳算法在搜索過程中不易陷入局部最優(yōu)，有較好的全局優(yōu)化能力。模式理論的實質(zhì)是什么？模式理論是奇偶基于簡單遺傳算法，主要從一種結(jié)構(gòu)的角度介紹遺傳算法的收斂性。 (模板理論)假設(shè)群體在t時刻含有模板H樣本數(shù)為N(H,t),經(jīng)選擇、交叉、變異后，在t+1時刻，群體中具有H的N(H,^1)>N(H,t)f(H)^-P^(H)(^P(H,t)^^-Pm0(H)}f、n—1樣本數(shù)為： . /—E(H)(1—p(H,t))—PmO(H)[f.n—1 ,說明具有低階、短定義矩，以及平均適應(yīng)度高于群體適應(yīng)度的模板在子代中將得到指數(shù)級增長。說明SGA搜索尋優(yōu)的過程。如何體現(xiàn)遺傳、進(jìn)化和適應(yīng)性？為什么是有效的？ SGA的參數(shù)有哪SGA的一般流程：隨機(jī)產(chǎn)生一定數(shù)目的初始種群，每個個體表示為染色體的基因編碼;

計算每個個體的適應(yīng)度，并判斷是否符合優(yōu)化準(zhǔn)則，若符合，輸出最佳個體及其代表的最優(yōu)解并結(jié)束計算，否則轉(zhuǎn)向第3步；依據(jù)適應(yīng)度選擇再生個體，適應(yīng)度高的個體被選中的概率高，適應(yīng)度底的個體可能被淘汰；執(zhí)行交叉和變異操作，生成新的個體；得到新一代的種群，返回第2步。遺傳：通過交配產(chǎn)生一組新解的過程。進(jìn)化：變異編碼的某一分量發(fā)生變化的過程使解有更大的遍歷性。適應(yīng)性：適應(yīng)函數(shù)值交配使得算法能夠搜到更好的解，但受基因的限制，只能搜索已有的所有基因的組合，變異是擴(kuò)大染色體選擇范圍的一個手段，可以得到一些新的基因。SGA的參數(shù)：群體規(guī)模、迭代次數(shù)及各種遺傳概率（交叉概率、變異概率）等。7.標(biāo)準(zhǔn)遺傳算法SGA（standardgeneticalgorithm）有哪些不足？交叉率Pc，變異率Pm，自適應(yīng)調(diào)整的算法和解決問題是什么？SGA有哪些不足：（一） 編碼問題：對于不同的問題，編碼選擇不當(dāng)，可能導(dǎo)致積木塊假設(shè)不成立而使 GA很難收斂到最優(yōu)解。編碼不規(guī)范及編碼表示的不正確性，單一的遺傳編碼不能全面地將優(yōu)解問題的約束表示出來。（二） 早熟收斂：指群體過早失去多樣性而收斂到局部最優(yōu)解。（三） 進(jìn)化時間長：進(jìn)化過程中產(chǎn)生大量數(shù)據(jù)，計算大，時間長。（四） 參數(shù)選擇問題：目前參數(shù)選擇是根據(jù)經(jīng)驗來確定，缺乏理論依據(jù)。Kc(fmaxKc(fmax-fc)，fc—favgPc=' fmax—favgKc,fcVfavg1_Km(fPm?^max-fm),fm-fTjKm,maxavgm：-favgavgfm是變異個體的適其中Kc，Km為小于1的常數(shù)，ffm是變異個體的適應(yīng)值，fmax-favg體現(xiàn)了群體的收斂性，此值小，說明群體趨向收斂應(yīng)加大 Pc,Pn。Srinvias提出自適應(yīng)遺傳算法： P^Pm能夠隨適應(yīng)度自動改變。思想：當(dāng)種群各個體適應(yīng)度趨向于局部最優(yōu)解時，使Pc,Pm增加，當(dāng)群體適應(yīng)度分散時Pc,Pm減小。同時，對于適應(yīng)度高于群體平均適應(yīng)度的個體，取較低的P>,Pm，而低于群體平均適應(yīng)度的個體，取較高的 Pc,Pm，使該解淘汰。適應(yīng)度函數(shù)解決的問題：遺傳進(jìn)化初期，通常會產(chǎn)生一些超群個體，若按比例選擇，超群個體因競爭力突出而控制選擇過程，影響算法的全局最優(yōu)；遺傳進(jìn)化后期，算法接近收斂，由于種群個體適應(yīng)度差異較小，繼續(xù)優(yōu)化的潛能低，不能獲得局部最優(yōu)。支持向量機(jī)有哪些特點？（一） 專門針對有限樣本的情況，目標(biāo)是得到現(xiàn)有信息下的最優(yōu)解而不是樣本數(shù)趨于無窮大的最優(yōu)解。（二） 算法最終轉(zhuǎn)化為一個二次尋優(yōu)問題，從理論上說將得到的是全局最優(yōu)點。（三） 算法將實際問題通過非線性變換轉(zhuǎn)化到高維的特征空間，在高維的空間中構(gòu)造線性判別函數(shù)來實現(xiàn)原空間中非線性問題，巧妙解決了維數(shù)問題，算法復(fù)雜度與樣本維數(shù)無關(guān)。粒子群（PSO）算法的特點？（一） 粒子群算法是一種基于迭代的優(yōu)化工具；（二） 隨機(jī)初始化種群；（三） 使用適應(yīng)值來評價系統(tǒng)；（四） 根據(jù)適應(yīng)值進(jìn)行一定的隨機(jī)搜索；（五） 不能保證能夠找到最優(yōu)解；（六） 根據(jù)自己的速度來決定搜索；（七） 粒子群算法還有一個重要的特點，就是有記憶功能；

信息的單向流動，整個搜索更新過程是跟隨當(dāng)前最優(yōu)解的過程，可能會列出轉(zhuǎn)移概率和信息素更新公式。10.蟻群算法求解TSP問題的步驟。要求會列出轉(zhuǎn)移概率和信息素更新公式。蟻群算法求解TSP問題的步驟：(一)對n個城市的TSP問題，N={1,2,…，n},A={(i,j)i,jwN}，城市間的距離D=(djj)ng為TSP圖中每一條弧(i,j)賦信息素痕跡初值可(0)=力?，假設(shè)有m只螞蟻在工作，所有的螞蟻從同一個城市io出發(fā)，i>1。當(dāng)前最好解W=(1,2,…，n)。(二)(外循環(huán))如果滿足算法的停止規(guī)則，停止計算并輸出計算得到的最好解，否則，讓螞蟻s從起點io出發(fā)，用L(s)表示螞蟻s行走的城市集合，初始 L(s)為空集，1_s_m。(三)(內(nèi)循環(huán))按螞蟻1乞s^m的順序分別計算。當(dāng)螞蟻在城市i,若L(s)=N或i(i,jrA,L-L(s)> ，完成第s只螞蟻的計算。否則，若L(s)=N且T(i,j)?A,lFL(s)?—”io心'則以概率R=茗可(k一1)ie ?謠丁、0, j更T到達(dá)j,L(s)=L(s)_,j[i匕j；若L(s)=N且t—l(i,j)A,k'L(s)?「i0,，則到達(dá)io,L(s)二L(s)di*;重復(fù)步驟三(四)對1<m，若L(s)二N，按L(s)中城市的順序計算路徑長度；若L(s)=N，路徑長度是一個充分大的數(shù)。比較 m只螞蟻中的路