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

一、什么是P問題，什么是NP問題？智能優(yōu)化算法主要是針對(duì)什么問題而提出的？解：（1）P問題（2）NP問題（3）NP-C問題和NP-Hard問題（4）智能優(yōu)化算法主要是針對(duì)組合優(yōu)化問題而提出的。當(dāng)最優(yōu)化問題中的可行域D是一個(gè)由有限個(gè)元素組成的集合時(shí)，該最優(yōu)化問題稱為組合優(yōu)化問題。通常組合優(yōu)化問題可表示為 min f(x)s.t. g(x) 0, xD.典型的組合優(yōu)化問題有旅行商問題，背包問題，并行排序問題等，二、描述組合優(yōu)化問題中的一個(gè)典型例子，并建立其數(shù)學(xué)模型。解：（1）旅行商問題（Traveling Salesman Problem，TSP）（2）背包問題（3）并行機(jī)排序問題三、描述模擬退火算法中的接收準(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)則的過程，該過程達(dá)到平衡時(shí)停止。在狀態(tài)si時(shí)，產(chǎn)生的狀態(tài)sj被接受的概率為：，這里，.降溫：四、寫出遺傳算法中的兩種交叉運(yùn)算方法，并分別舉例說明。步驟：1、隨機(jī)初始化pop size個(gè)染色體；2、用交叉算法更新染色體；3、用變異算法更新染色體；4，計(jì)算所有染色體的目標(biāo)值；5，根據(jù)目標(biāo)值計(jì)算每個(gè)染色體的適應(yīng)度；6，通過輪盤賭的方法選擇染色體。7、重復(fù)第二至第六步直到終止條件滿足；8、輸出最好的染色體作為最優(yōu)解。評(píng)價(jià)函數(shù)：Eval(V)是根據(jù)每個(gè)染色體V的適應(yīng)函數(shù)fitness(V)而得到與其他染色體的比例關(guān)系，可用它來決定該染色體被選為種群的概率如：輪盤賭選擇過程：交叉運(yùn)算方法：雙親雙子法（兩父代交叉位之后的全部基因互換）、變化交叉法（從不相同的基因開始選取交叉位，之后的方法同雙親雙子法）、多交叉位法（間隔交換）、雙親單子法（2選1）、顯性遺傳法（按位或）、單親遺傳法（2-opt）等。雙親雙子交叉方法例子：變異運(yùn)算：單點(diǎn)、多點(diǎn)變異法；2-opt法；用遺傳算法解決實(shí)數(shù)編碼求連續(xù)函數(shù)優(yōu)化問題，寫出一種變異的運(yùn)算方法。解：再用單點(diǎn)變異法或多點(diǎn)變異法即可完成實(shí)數(shù)碼的變異方法。（隨機(jī)選一個(gè)或幾個(gè)變異位取反）五、解釋蟻群智能優(yōu)化算法中信息素的一種更新方法。步驟：1、初始化所有的信息素具有同樣的量；2、根據(jù)信息素構(gòu)造人工螞蟻行為路線（解）；3、重復(fù)第二步直到所有人工螞蟻完成一次行動(dòng)；4、根據(jù)當(dāng)前最好解更新路徑上的信息素；5、重復(fù)第二步至第四步直到終止條件滿足；6、輸出最好解作為最優(yōu)解。信息素的一種更新方法：方法一：方法二：方法三：人工螞蟻路線的構(gòu)造：六、描述Hopfiled人工神經(jīng)網(wǎng)絡(luò)的函數(shù)逼近一連續(xù)函數(shù)的方法。解：Step 1. 構(gòu)造函數(shù)逼近的能量函數(shù)，使得能量函數(shù)有好的穩(wěn)定性，如Err(w)；Step 2. 由能量函數(shù)Err(w)，根據(jù)求解出動(dòng)力系統(tǒng)方程；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)