智能優(yōu)化算法地部分精華筆試試題

1、一、什么是P問題，什么是叩問題？智能優(yōu)化算法主要是針對什么問題而提出 的？解：(1) P問題記問題的實例為I,實例規(guī)模為/(I),算法4在求解I時的計算量 (基本計算總次數(shù))為.A若存在多項式函數(shù)g(x)和一個常數(shù)Q,使得頃1) Qg(/(I)對給定問題的所有實例I成立，記Q(i) = O(g(/(i),則稱算 法4為解決對應(yīng)問題的多項式時間算法.P類問題指具有多項式時間算法的問題類NP問題若存在一個多項式函數(shù)g(x)和一個驗證算法A對一類判定 問題的任何一個是”的判定實例I都存在一個字符串S是I 的“是”回答,其規(guī)模滿足/(S) = 0(g(/),且算法4驗證S 為實例I的是”答案的計算時間

2、為O(g(/(I),則稱這個判定 問題是非確定多項式的，簡記為NP.NP-C問題和NP-Hard問題a如果判定問題Q eNP且NP中的任何一個問題都可在多晶 間內(nèi)歸約為Q,則稱Q為NP完全(簡記為NP-C).a若NP中的任何一個問題都可在多項式時間歸約為判定問題 Q,則稱Q為NP難(簡記為NP-hard).智能優(yōu)化算法主要是針對組合優(yōu)化問題而提出的。當最優(yōu)化問題中的可行 域D是一個由有限個元素組成的集合時，該最優(yōu)化問題稱為組合優(yōu)化問題。通常 組合優(yōu)化問題可表示為min f(x)s.t. g(x) N0,xED.典型的組合優(yōu)化問題有旅行商問題，背包問題，并行排序問題等，二、描述組合優(yōu)化問題中的一

3、個典型例子，并建立其數(shù)學(xué)模型。解：(1)旅行商問題(Traveling Salesman Problem， TSP)設(shè)有n個城市L2： . 城市i與城市J間的距離為dij.售 貨商要去這些城市推銷貨物，他希望從一城市出發(fā)后走遍所有的 城市且旅途中每個城市只經(jīng)過一次，最后回到起點.選擇一條路 經(jīng)使得售貨商所走路線總長度最短，這就是旅行商問題.引進決策變量易，若商人從城市/出來后緊接著到城市j,則 乂日=1,否則XiJ = 0 (/ = L 2： ,).那么TSP的數(shù)學(xué)模型可 表示為fn nmin E E dijXijj=i等=L / = .n,箏=L J= L2,gS|T, $為 1,2,/的非

4、空真子集，ijes、x泮但以其中|5|表示集合S中元素的個數(shù).背包問題設(shè)有一個容量為b的背包，n個容積分別為叫，價值分別為q(j = L2：-.如)的物品，選擇那些物品放入背包中以使裝入的物 品總價值最大，這就是背包問題.引入決策變量為，若第，個物品被放入包中，則X, = 1,否則X/ = 0 (/ = L 2： - Z7).那么背包問題的數(shù)學(xué)模型為max CfXj s.t. wixi 6、x,e0, / = 1,2r , n.并行機排序問題設(shè)有m臺同型機器M,-. M，n個相互獨立的工件 九&，現(xiàn)在要安排這些工件到機器上進行加工，設(shè)每個工 件只需在任一臺機器上加工，工件J,的加工時間為t,(

5、，=L 2, . . . , n).如何安排這些工件的加工方案，以使機器完成 所有工作的時間最少.這就是并行機排序問題.引入決策變量易，若工件J,在機器的上加工，則X,j=l,否 則Xij = 0.那么并行機排序問題的數(shù)學(xué)模型為min T ms.t. E x加=L，= L 2： , , f (s )fexp(-j),t，這里，iff (s i) v f (s?降溫:種方法為。+1 = d(tk)另一種方法為其中 d(tk) = atkM-kM扉其中M為溫度下降的總次數(shù).四、寫出遺傳算法中的兩種交叉運算方法，并分別舉例說明。步驟：1、隨機初始化pop size個染色體；2、用交叉算法更新染色體；

6、3、用變 異算法更新染色體；4,計算所有染色體的目標值；5,根據(jù)目標值計算每個染色 體的適應(yīng)度；6,通過輪盤賭的方法選擇染色體。7、重復(fù)第二至第六步直到終止 條件滿足；8、輸出最好的染色體作為最優(yōu)解。評價函數(shù)：Eval（V）是根據(jù)每個染色體V的適應(yīng)函數(shù)fitness（V）而得到與其他染色 體的比例關(guān)系，可用它來決定該染色體被選為種群的概率如：5)=輪盤賭選擇過程:算法（輪盤賭的選擇過程）Step 1.計算所有染色體匕的累積概率如=0. qi = Eval（Vj） .，=1. 2. . pop size, j=iStep 2.在（0. qpop size中產(chǎn)生一個隨機數(shù)r.Step 3.若 r

7、則選擇染色體V；.Step 4.重復(fù)第二至第三步pop size次以獲得pop size個染色體.交叉運算方法：雙親雙子法（兩父代交叉位之后的全部基因互換）、變化交叉法 （從不相同的基因開始選取交叉位，之后的方法同雙親雙子法）、多交叉位法（間 隔交換）、雙親單子法（2選1）、顯性遺傳法（按位或）、單親遺傳法（2-opt） 等。雙親雙子交叉方法例子：父代是以交叉概率Pc在種群中選取的.實現(xiàn)的方法從種群/ = 1到種群pop size逐個地 如下操作：從0.1中隨機產(chǎn)生r,如r Pc,則染色體 峪被選為父代.記父代為峪,巧巧,，將他們配成對:（必巧），（巧M）牌W對于實數(shù)碼，可按以下方法實現(xiàn)交叉運

8、算：隨機產(chǎn)生一 個數(shù)ce (0.1),由父代峪,峻產(chǎn)生子代X. 丫X = cM + (l _ c)My =(i c).g + c 巧變異運算：單點、多點變異法；2-opt法；對實數(shù)碼，可如下進行變異操作.設(shè)，為選為變異 的染色體，取肋0適當大，隨機選個變異方向 d,如V + Md不可行，置肋為0到肋間的隨 機數(shù)直到可行為止；若該過程在規(guī)定的代數(shù)還不能 找到可行解，則置M = 0.由，變異產(chǎn)生的后代為X=V+M-d.用遺傳算法解決實數(shù)編碼求連續(xù)函數(shù)優(yōu)化問題，寫出一種變異的運算方法。解：連續(xù)的實數(shù)變量在一定精度下也可以采用二進制編碼.I對給定的區(qū)間何M,設(shè)二進制編碼的長為幾則變量b ab ab a

9、x = m + 邊一- F 22 I2n與二進制碼Mg , a相對應(yīng).二進制碼與實際變量的誤差為穿.再用單點變異法或多點變異法即可完成實數(shù)碼的變異方法。(隨機選一個或 幾個變異位取反)五、解釋蟻群智能優(yōu)化算法中信息素的一種更新方法。步驟：1、初始化所有的信息素具有同樣的量；2、根據(jù)信息素構(gòu)造人工螞蟻行為 路線(解)；3、重復(fù)第二步直到所有人工螞蟻完成一次行動；4、根據(jù)當前最好 解更新路徑上的信息素；5、重復(fù)第二步至第四步直到終止條件滿足；6、輸出最 好解作為最優(yōu)解。信息素的一種更新方法：在時刻，設(shè)M是目前為止的最好可行解，而st是當前t時刻的最好可行解 設(shè)f(s)和f(sj是對應(yīng)的目標函 數(shù)值

10、.如果 f(st) f(s)r 則 & 金在S的弧上增強信息素，而在其它弧上揮發(fā)信息素.方法一：r(t) ( (1 1) +if (提) s(1 - Pt-i)Ty(t 一 1),otherwise,其中Ptl 0PtA是揮發(fā)因子，且滿足方法二：max(l - p)Tij(t - 1) + L Tmin(f - l)tIif (M) e 3max(l -1), Tm)n(t - 1),otherwise,其中小0 p 1是揮發(fā)因子而Tmin(f - 1)為一個實 數(shù).方法三：max(l p)邛(r 1)十使，做J,if(，J)3 偵。=，max(l - p)珂(r 一 1),而n, other

11、wise,其中p, 0 p 1是揮發(fā)因子，是一個參數(shù)，而 g(5)0 W(S) X是一個函數(shù)滿足f(s) g(5) gsf)r 如可取 施=u(胴 1 + 1)人工螞蟻路線的構(gòu)造：在第i步構(gòu)造了序列X/ =后，以如下概 率選擇下一個頂點9如果(。.烏Pij =其它.aeJq0,螞蟻轉(zhuǎn)移概率Pij更一般的規(guī)則為Pij =必招)如果J 6 T /T0, 如果j.T其中T是從i可以到達的節(jié)點集合，A(t-1) = 列(t 1) I (/,；) e A取決于三部分因素， 第一部分為信息素丁jj(t 1)和預(yù)見度7/y(t - 1)；第二部 分為每個螞蟻自身的歷史信息；第三部分為問題的約束 條件常見的蟻

12、群路由表由下式求得( I)如果心 1)= 咨球 J 1)就(LI)0,如果jT其中，a為殘留信息的相對重要程度，月為預(yù)見值的 相對重要程度.六、描述Hopfiled人工神經(jīng)網(wǎng)絡(luò)的函數(shù)遇近一連續(xù)函數(shù)的方法。解：假設(shè)f(x)是一個連續(xù)函數(shù),我們希望訓(xùn)練一個NN去逼 近函數(shù)f(x).對于一個固定神經(jīng)元和網(wǎng)絡(luò)結(jié)構(gòu)的NN.網(wǎng)絡(luò)權(quán)可作成一 個向量w.設(shè)F(x：w)是由NN所得出的輸出.訓(xùn)練過程是尋找權(quán)向量w以最好地逼近函數(shù)f(x),設(shè) (xy；)|，= L2：./V是訓(xùn)練數(shù)據(jù)集,我們希望選擇 權(quán)向量w使得F(xLw)對于輸入x；來說最接近要求的 輸出y；.艮L訓(xùn)練過程是找權(quán)向量w以極小化以下的誤 差函數(shù)(w) = j|F(x*,w)-y*|2.Step 1.構(gòu)造函數(shù)逼近的能量函數(shù)，使得能量函數(shù)有好的穩(wěn)定性，如Err(w);Step 2.由能量函數(shù)Err(w)，根據(jù)-竺=竺也 求解出動力系統(tǒng)方程 dtdyi1亨=一孔 +丈網(wǎng)必+1/I義=機電，=L2l .叫Step 3.用數(shù)值計算的方法求解動力系統(tǒng)方程的平衡點，用定理判斷平衡點是否 為穩(wěn)定點或漸