智能優(yōu)化算法筆試考試試題智能優(yōu)化算法筆試考試試題II一、寫出遺傳算法中的兩種交叉運(yùn)算方法，并分別舉例說(shuō)明。解：雙親雙子法(兩父代交叉位之后的全部基因互換)、變化交叉法(從不相同的基因開始選取交叉位，之后的方法同雙親雙子法)、多交叉位法(間隔交換)、雙親單子法(2選1)、顯性遺傳法(按位或)、單親遺傳法(2-opt)等，例子見課本175-179<>二、什么是P問題，什么是NP問題？智能優(yōu)化算法主要是針對(duì)什么問題而提出的？解：(1)P問題記問題的實(shí)例為I,實(shí)例規(guī)模為/(I)，算法人在求解1時(shí)的計(jì)算量〔基本計(jì)算總次數(shù))為G(I).?若存在多項(xiàng)式函數(shù)g(x)和一個(gè)常數(shù)。使得對(duì)給定問題的所有實(shí)例1成立，記cxi)=o<g<qi)))「則稱算法人為解決對(duì)應(yīng)問題的多項(xiàng)式時(shí)間算法，P類問題指具有多項(xiàng)武時(shí)間算法的問題類NP問題若存在一個(gè)多項(xiàng)式函數(shù)g(X)和一亍驗(yàn)證算法幾對(duì)一類判定問題的任何一個(gè)“是”的判定實(shí)例I都存在一個(gè)字符串S是1的“是“回答，其規(guī)模滿足/(S)=0(外(1)幾且算法。驗(yàn)證5為實(shí)例1白勺」是“答案的計(jì)算時(shí)間為0(g(/(I))),則稱這個(gè)判定問題是非確定多項(xiàng)式的'簡(jiǎn)記為NPNP-C問題和NP-Hard問題?如果判定問題QeNP且AP中的任何一個(gè)問題都可在多朗島內(nèi)歸約為Q,則稱Q為NP完全(簡(jiǎn)記為NP-C).?若NP中的任何一個(gè)問題都可在多項(xiàng)式時(shí)間歸約為判定問題Q,則稱Q為NP難(簡(jiǎn)記為NP-hard).智能優(yōu)化算法主要是針對(duì)組合優(yōu)化問題而提出的。三、描述組合優(yōu)化問題中的一個(gè)典型例子，并建立其數(shù)學(xué)模型。解：(1)旅行商問題(TravelingSalesmanProblemTSP)設(shè)有n個(gè)城市1.2.9nT城市f勻城市J間的距離為％一售貨商要去這些城市推銷貨物，他希望從一城市出發(fā)后走遍所有的城市且旅途中每個(gè)城市只經(jīng)過一次，最后回到起點(diǎn).選擇一條路經(jīng)使得售貨商所走路線總長(zhǎng)唐最短，這就是旅行商問題引進(jìn)決策變量切，若商人從城市，岀來(lái)后緊接著到城市八則旳-1.否則勺=。(/.;=1.2. ./)).那么TSP的數(shù)學(xué)模型可表示為*nnmin內(nèi)￡Xy=J=1*f旳二/=/￡旳<|5|-1,S^(lt2..J}的非空真子筑Jjes,X(/e(0l}7/；j-E知其中|S|表示集合s中元素的亍數(shù)背包問題設(shè)有一個(gè)容量為動(dòng)的背包n個(gè)容積分別為旳，價(jià)值分別為q_(；=12.,〃的物品，選擇那些物品放入背包中以使裝入的物品總價(jià)值最大，這就是背包問題一引入決策變量坨，若第；個(gè)物品被放入包中，則x;=b否則片=o(r-i_2—那么背包問題的數(shù)學(xué)模型為max刀c/x/*S.t.SWfXi<bi=l、x/e{0,1), /= ,n.并行機(jī)排序問題設(shè)有m臺(tái)同型機(jī)器隔陋、….般沖n個(gè)相互獨(dú)立的工件J丄…人現(xiàn)在要安排這些工灌U機(jī)器上進(jìn)行加工，設(shè)每個(gè)工件只需在任一臺(tái)機(jī)器上加工，工件d的如工時(shí)間為口(/=12■-n).如何安攜這些工件的加工方案，以使機(jī)器完成所有工作的時(shí)間最少一這就是井行機(jī)排序問題一引入決策變量冷，若工件丿」在機(jī)器明上加工，則勺=1,否則駕=0.那么井行機(jī)排序問題的數(shù)學(xué)模型為mintm^?52^=h#=XN...m?7=1r>￡j=h2：…沖;=i靭E{°1}： /=1,2.A-.nJ=1,2,-Tm.智能優(yōu)化算法筆試考試試題智能優(yōu)化算法筆試考試試題/4四、描述模擬退火算法中的接收準(zhǔn)則。解：在一給定溫度下，由一個(gè)狀態(tài)變到另一個(gè)狀態(tài)，每一個(gè)狀態(tài)到達(dá)的次數(shù)服從一個(gè)概率分布，即基于Metropolis接受準(zhǔn)則的過程，該過程達(dá)到平衡時(shí)停止。在狀態(tài)s時(shí)，產(chǎn)生的狀態(tài)s被接受的概率為：1 iff(S)”(Sj)W為iff(S)vfd這里，3訃心.五、 解釋蟻群智能優(yōu)化算法中信息素的一種更新方法。解：在t時(shí)刻「設(shè)專是目前為止的最好可行解「而$是當(dāng)前t時(shí)刻的最好可行解?設(shè)f(s)和f(s「)是對(duì)應(yīng)的目標(biāo)函數(shù)值一如果f(sjvf(s"則S—?jiǎng)蛟赟的弧上増強(qiáng)信息素，而在其它弧上揮發(fā)信息素一評(píng)(jj評(píng)(jj)e=J(1-pt-i)坊(匸一1)+otherwise,$IIotherwise,1(1一一1),其中g(shù)o<fr<1是揮發(fā)因子，且滿足9=g9=gt=iPt<l- .z.八ln(t+1)六、 描述Hopfiled人工神經(jīng)網(wǎng)絡(luò)的函數(shù)逼近一連續(xù)函數(shù)的方法。解：假設(shè)f(x)是一個(gè)連續(xù)函數(shù).我們希望訓(xùn)練一個(gè)NN去逼近函數(shù)fg對(duì)于一個(gè)固定神經(jīng)元和網(wǎng)絡(luò)結(jié)構(gòu)的nn,網(wǎng)絡(luò)權(quán)可作成一個(gè)向量w.設(shè)F(x.w)是由NN所得出的輸出訓(xùn)練過程是尋找權(quán)向量W以最好地逼近函數(shù)f(x).設(shè)｛(*占；)卩二12N｝是訓(xùn)練數(shù)據(jù)集'我們希望選擇權(quán)向量w使得F(x\w)對(duì)于愉入x；來(lái)說(shuō)最接近要求的輸出聽.即，訓(xùn)練過程是找權(quán)向量w以極小化以下的誤差函數(shù)1“Frr(w)=-J2||F(x*tw)-y；||2.z*=iStepl.構(gòu)造函數(shù)逼近的能量函數(shù)，使得能量函數(shù)有好的穩(wěn)定性，如 Err(w);Step2,由能量函數(shù)Err(w),根據(jù)-dZ「=-Err(*)求解出動(dòng)力系統(tǒng)方程dtcy.( 孚二一A石+K呦乃41*Step3.用數(shù)值計(jì)算的方法求解動(dòng)力系統(tǒng)方程的平衡點(diǎn)，用定理判斷平衡點(diǎn)是否為穩(wěn)定點(diǎn)或漸近穩(wěn)定點(diǎn)，網(wǎng)絡(luò)達(dá)到穩(wěn)定狀態(tài)即達(dá)到極小值。七、 用遺傳算法解決實(shí)數(shù)編碼求連續(xù)函數(shù)優(yōu)化問題，寫出一種變異的運(yùn)算方法。解：連續(xù)的實(shí)數(shù)變量在一定精度下也可以采用二進(jìn)制編碼一對(duì)給定的區(qū)間[a.fe],設(shè)二進(jìn)制編碼的長(zhǎng)為m則變量b—ab-a b-aX—a+3j I、32 …+3“2打與二進(jìn)制碼巧電…咼相對(duì)應(yīng).二進(jìn)制碼與實(shí)際變量