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

1、一、什么是P問(wèn)題，什么是NP問(wèn)題？智能優(yōu)化算法主要是針對(duì)什么問(wèn)題而提出 的？解：1P問(wèn)題記間題的實(shí)例為1.實(shí)例規(guī)模為/（I）,算法在求解1時(shí)的計(jì)算量（基本計(jì)算總次數(shù)）為C卜若存在多項(xiàng)式函數(shù)莒彼）和一個(gè)常數(shù)e使得頃） 0,xD.典型的組合優(yōu)化問(wèn)題有旅行商問(wèn)題，背包問(wèn)題，并行排序問(wèn)題等，二、描述組合優(yōu)化問(wèn)題中的一個(gè)典型例子，并建立其數(shù)學(xué)模型。解：1旅行商問(wèn)題Traveling Salesman Problem, TSP設(shè)有計(jì)個(gè)城市城市i與城市j間的距離為一售 貨商要去這些城市推銷貨物，他希望從一城市出發(fā)后走遍所有的 城市且旅途中每個(gè)城市只經(jīng)過(guò)一次，最后回到起點(diǎn).選擇一條路 經(jīng)使得售貨商所走路線總長(zhǎng)

2、度最短，這就是旅行商問(wèn)題 引進(jìn)決策變量勺.，若商人從城市i出來(lái)后緊接著到城市土 則 有=L否則聽=0 (i.j = L2一.少那么TSP的數(shù)學(xué)模型可 表示為rn nmin 由裕f=ij=ins.t. = Lj=iJ n丈冷=It J = L2,Mt=lE Xij |S| - 1, 5為L(zhǎng) 2，日的非空真子集, ues、 珂 e0,1,/J 手，其中|S|表示集合S中元素的個(gè)數(shù)2背包問(wèn)題設(shè)有一個(gè)容量為b的背包，口個(gè)容積分別為蛔，價(jià)值分別為c； (12. n)的物品，選擇那些物品放入背包中以使裝入的物 品總價(jià)值最大這就是背包問(wèn)題引入決策變量志，若第i個(gè)物品被放入包中，則芯=1,否則 用=。=1.2

3、一皿 那么背包問(wèn)題的數(shù)學(xué)模型為max QXr s,t. 52 Ml ； t淘,y = 1,2, . m,地 6 (04, i = L2,nj = 1,2, 齊.三、描述模擬退火算法中的接收準(zhǔn)則。步驟：1、初始化可行解和溫度；2,根據(jù)Boltzmann概念退火；3,重復(fù)第二步 直到穩(wěn)定狀態(tài)；4,降溫；5,重復(fù)第二步至第四步直到滿足終止條件或直到給定 步數(shù)。6,輸出最好的解作為最優(yōu)解。退火接收準(zhǔn)則：在一給定溫度下，由一個(gè)狀態(tài)變到另一個(gè)狀態(tài)，每一個(gè)狀態(tài)到達(dá) 的次數(shù)服從一個(gè)概率分布，即基于Metropolis接受準(zhǔn)則的過(guò)程，該過(guò)程到達(dá)平衡時(shí)停止。在狀態(tài)七時(shí)，產(chǎn)生的狀態(tài)Sj被接受的概率為：A (t) J

4、盾 即 2 氣這里 g = f (s )- f (s ).lJexp(-), iff (s) f (sjj j 降溫：A 種方法為tk+1 = d(tk)另一種方法為其中 d(tk) = atkM-ktk= M 場(chǎng)其中M為溫度下降的總次數(shù).四、寫出遺傳算法中的兩種交叉運(yùn)算方法，并分別舉例說(shuō)明。步驟：1、隨機(jī)初始化pop size個(gè)染色體；2、用交叉算法更新染色體；3、用變 異算法更新染色體；4,計(jì)算所有染色體的目標(biāo)值；5,根據(jù)目標(biāo)值計(jì)算每個(gè)染色 體的適應(yīng)度；6,通過(guò)輪盤賭的方法選擇染色體。7、重復(fù)第二至第六步直到終止 條件滿足；8、輸出最好的染色體作為最優(yōu)解。評(píng)價(jià)函數(shù)：Eval（V）是根據(jù)每個(gè)

5、染色體V的適應(yīng)函數(shù)fitness（V）而得到與其他染色體 的比例關(guān)系，可用它來(lái)決定該染色體被選為種群的概率如:M）=輪盤賭選擇過(guò)程：算法（輪盤賭的選擇過(guò)程）Step 1.計(jì)算所有染色體匕的累積概率qif如=0. % = Ev/Vj） .，=1. 2.pop size,j=iStep 2.在（O.qpops屁中產(chǎn)生一個(gè)隨機(jī)數(shù)r.Step 3.若 r 為，則選擇染色體*Step 4,重復(fù)第二至第三步pop size次以獲得pop size個(gè)染色體.交叉運(yùn)算方法：雙親雙子法兩父代交叉位之后的全部基因互換、變化交叉法 從不相同的基因開始選取交叉位，之后的方法同雙親雙子法、多交叉位法間 隔交換、雙親單子

6、法2選1、顯性遺傳法按位或、單親遺傳法2-opt 等。雙親雙子交叉方法例子：父代是以交叉概率Pc在種群中選取的.實(shí)現(xiàn)的方法從種群/ = 1到種群pop size逐個(gè)地 如下操作：從0.1中隨機(jī)產(chǎn)生如r Pc,則染色體 峪被選為父代.記父代為峪,巧巧,，將他們配成對(duì):（峪M），04嶗）,（*嶗）,對(duì)于實(shí)數(shù)碼，可按以下方法實(shí)現(xiàn)交叉運(yùn)算：隨機(jī)產(chǎn)生一 個(gè)數(shù)ce (0.1),由父代峪,峻產(chǎn)生子代X. 丫X = cM + (l _ c)My =(i c).g + c 巧變異運(yùn)算：?jiǎn)吸c(diǎn)、多點(diǎn)變異法；2-opt法；對(duì)實(shí)數(shù)碼，可如下進(jìn)行變異操作.設(shè)，為選為變異 的染色體，取肋0適當(dāng)大，隨機(jī)選個(gè)變異方向 d,如V

7、 + Md不可行，置肋為0到肋間的隨 機(jī)數(shù)直到可行為止；若該過(guò)程在規(guī)定的代數(shù)還不能 找到可行解，則置M = 0.由，變異產(chǎn)生的后代為X=V + M-d.用遺傳算法解決實(shí)數(shù)編碼求連續(xù)函數(shù)優(yōu)化問(wèn)題，寫出一種變異的運(yùn)算方法。解：連續(xù)的實(shí)數(shù)變量在一定精度下也可以采用二進(jìn)制編碼.對(duì)給定的區(qū)間何ML設(shè)二進(jìn)制編碼的長(zhǎng)為m則變量b 3 b 3b _ ax = m + 日 i - F 邊 bF L x與二進(jìn)制詞a詞 尋相對(duì)應(yīng)一二進(jìn)制碼與實(shí)際變量的誤差為穿再用單點(diǎn)變異法或多點(diǎn)變異法即可完成實(shí)數(shù)碼的變異方法。隨機(jī)選一個(gè)或 幾個(gè)變異位取反五、解釋蟻群智能優(yōu)化算法中信息素的一種更新方法。步驟：1、初始化所有的信息素具有

8、同樣的量；2、根據(jù)信息素構(gòu)造人工螞蟻行為 路線解；3、重復(fù)第二步直到所有人工螞蟻完成一次行動(dòng)；4、根據(jù)當(dāng)前最好 解更新路徑上的信息素；5、重復(fù)第二步至第四步直到終止條件滿足；6、輸出最 好解作為最優(yōu)解。信息素的一種更新方法：在t時(shí)刻，設(shè)是目前為止的最好可行解，而殳是當(dāng)前t時(shí)刻的最好可行解,設(shè)f(s)和f(S.)是對(duì)應(yīng)的目標(biāo)函數(shù)直如果f(st) f(s)t則會(huì)一成在s的孤上增強(qiáng)信息素，而在其它弧上揮發(fā)信息素.方法一：(1 - 1) + if (，J) G 5 11(I pr_i)Ty(t - 1),otherwise,其中p” 0 1是揮發(fā)因子，且滿足心-器時(shí))，事=皿方法二：max(l - p

9、)Tjj(t 1) + Tmin(t - 1) if (M) e3 max(l -1), rmfn(t - 1),otherwise,其中p,0 p 1是揮發(fā)因子而rmin(t - 1)為一個(gè)實(shí) 數(shù).方法三:gx(l p)9(r 1)十如(), 丁村 n, if(3 偵，)=max(l - p)珂(r 一 1),而n, otherwise,其中p, 0 p 1是揮發(fā)因子，Em是一個(gè)參數(shù)，而 g(S), 0 g(5) X是一個(gè)函數(shù)滿足f(s) g(5) g(s)如可取 施= 1/(胴 l + i)人工螞蟻路線的構(gòu)造：在第t步構(gòu)造了序列用= 以如下概率選擇下一個(gè)頂點(diǎn)q_ 矽+可如果9) e 4佝

10、_ %I 0,其它螞蚊轉(zhuǎn)移概率P，,更一般的規(guī)則為Pij =痙尚，如果J go, 如果jr其中T是從/可以到達(dá)的節(jié)點(diǎn)集合，A(f-1) = W _ 1) I (；j) e A取決于三部分因素， 第一部分為信息素邛(t - 1)和預(yù)見度響U _ 1)；第二部 分為每個(gè)螞蟻?zhàn)陨淼臍v史信息；第三部分為問(wèn)題的約束 條件常見的蟻群路由表由下式求得(a . t如果i丁再瑞1)或(t-i)其中，心為殘留信息的相對(duì)重要程度，3為預(yù)見值的 相對(duì)重要程度一六、描述Hopfiled人工神經(jīng)網(wǎng)絡(luò)的函數(shù)逼近一連續(xù)函數(shù)的方法。解：假設(shè)代)是一個(gè)連續(xù)函數(shù) 我們希望訓(xùn)練一個(gè)NN去逼 近函數(shù)f(x).對(duì)于一個(gè)固定神經(jīng)元和網(wǎng)絡(luò)結(jié)

11、構(gòu)的NK.網(wǎng)絡(luò)權(quán)可作成一 個(gè)向量w設(shè)F(x,w)是由NN所得出的輸出 訓(xùn)練過(guò)程是尋找權(quán)向量w以最好地逼近函數(shù)f(x),設(shè) (xLy；)|，=是訓(xùn)練數(shù)據(jù)集.我們希望選擇權(quán)向量w使得F(xw)對(duì)于輸入x；來(lái)說(shuō)最接近要求的 輸出y；.即，訓(xùn)練過(guò)程是找權(quán)向量w以極小化以下的誤 差函數(shù)1 N&r(w) = 5El|F(x；.w) y；|2 1=1Step 1.構(gòu)造函數(shù)逼近的能量函數(shù)，使得能量函數(shù)有好的穩(wěn)定性，如Err(w);Step 2.由能量函數(shù)Err(w)，根據(jù)-冬=*(初 求解出動(dòng)力系統(tǒng)方程 dtdyif 岑 +I用=機(jī)耳)、f = 1.2.m；Step 3.用數(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á)極小值。Hop