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

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