智能計算綜述

1、1 遺傳算法1.遺傳算法的一般步驟（1）對問題的解進行編碼（二進制編碼、十進制編碼、實數(shù)編碼、Gary編碼）（2）形成編碼后的初始種群 方法：完全隨機產(chǎn)生 根據(jù)已知的先驗知識進行隨機選?。?）適應度函數(shù)的設計與計算 目標函數(shù)： 適應度函數(shù)： （4）遺傳操作 選擇算子 作用：判斷個體是否優(yōu)良 判斷標準：個體適應度函數(shù)值的大小 方法：比例選擇方法、精英選擇方法、排序選擇方法、聯(lián)賽選擇方法、期望值方法等 交叉算子 兩個相互配對的個體按照某種方法相互交換各自的部分基因形成新個體 方法：單點交叉、兩點交叉、多點交叉、一直交叉 變異算子 類型：基本變異算子、逆轉(zhuǎn)變異算子、自適應變異算子（5）算法終止 一般

2、設定最大迭代次數(shù)作為算法的終止條件，簡單但不準確 根據(jù)種群的收斂程度來判定算法是否停止 2.算法特點（1）與傳統(tǒng)相比 將問題參數(shù)編碼成染色體后進行進化操作使算法不受函數(shù)約束條件的限制； 采用群體搜索方法，具有隱含并行搜索特性； 隨機操作； 具有全局搜索能力，多用于復雜問題和非線性問題（2）優(yōu)越性 算法進行全空間并行搜索，很大概率找到全局最優(yōu)解 算法具有固定的并行性（3）多用于維數(shù)較高、環(huán)境復雜、問題結(jié)構(gòu)不十分清楚的場合3.遺傳算法的應用（1）加工中心組成問題（2）0-1背包問題2 蟻群優(yōu)化算法<一>算法基礎1. 一群螞蟻隨機從出發(fā)點出發(fā)將在蟻巢和食物之間建立通路，當在覓食路上出現(xiàn)障

3、礙時，蟻群會等概率地選擇沿著障礙物向左或向右移動；2. 螞蟻會在路徑上留下信息素以指導后面的蟻群移動；3. 信息素隨時間逐漸蒸發(fā)；4. 由蟻巢出發(fā)的螞蟻，其選擇路徑的概率與各路徑上的信息素成正比，最終所有螞蟻會選擇同一條較短的路徑；<二>算法模型1. 所需的基本變量和常數(shù)令：為蟻群中螞蟻的總數(shù)為旅行商問題中的城市個數(shù)為到之間的距離，其中為第次迭代（或時刻）弧上的信息素量初始時刻各弧上的信息素量相等，即（為常數(shù)）2. 狀態(tài)轉(zhuǎn)移概率 （2.1）值越大，螞蟻選擇以前經(jīng)過路徑的可能性就越大值越大，螞蟻選擇離開它最近的城市的可能性就越大3. 信息素的更新采用參數(shù)表示信息素揮發(fā)系數(shù)，而表示信息

4、素的殘留系數(shù)設：再經(jīng)過個時刻，螞蟻完成一次循環(huán) （2.2）其中4. 基本蟻群算法求解旅行商問題的主要步驟（1）初始化參數(shù)，將只螞蟻置于n個頂點上；（2）將初始出發(fā)點置于當前解路徑集合中；對螞蟻計算選擇城市的概率且為螞蟻未走過的城市，選擇概率最大的城市，并將螞蟻移動到該城市，記入，將該城市置于當前解路勁集合中；（3）分別計算只螞蟻找到的解所對應的目標函數(shù)值，并記錄當前最優(yōu)值；（4）按（2.2）來修改各個弧上的信息素量；（5）令；（6）若小于預定且無退化行為，則轉(zhuǎn)（2）5.蟻群算法的本質(zhì)選擇機制、更新機制、協(xié)調(diào)機制6. 蟻群算法的特點（1） 具有正反饋機制 （2）較強的魯棒性 （3）分布式計算（4

5、） 通用型隨機優(yōu)化方法 （5）易于其他方法結(jié)合7. 蟻群算法的缺點（1）搜索時間較長 （2）易出現(xiàn)停滯現(xiàn)象3 模擬退火算法1. 模擬退火算法數(shù)學模型的組成：（1） 解空間：關(guān)于一個問題所有可能的解的集合，它限定了初始解選取的范圍和新解產(chǎn)生的范圍（2） 目標函數(shù)：若干優(yōu)化目標的一個和式，其選取必須正確體現(xiàn)對問題的整體優(yōu)化要求（3） 初始解：開始迭代的起點2. 模擬退火算法的基本思想從一個初始解出發(fā)，不斷反復迭代產(chǎn)生新解，對新解進行判定、舍棄，最終取得令人滿意的全局最優(yōu)解3.運作流程（1）初始化：給定溫度的變化范圍并對其初始化，對解進行初始化，并計算初始化解所對應的當前目標函數(shù)起點；注：初始值要求

6、足夠大，但也不宜過大；對每一溫度下迭代的次數(shù)進行初始化（2） 設一個整數(shù)用來記錄每一溫度下迭代已進行的次數(shù)，在每一溫度下，循環(huán)次第（3）至（6）步；（3） 產(chǎn)生一個新解，根據(jù)目標函數(shù)分別計算當前解和新解所對應的和，并計算增量（4） 如果，則新解代替當前解作為新的當前解，新解所對應的作為新的當前目標函數(shù)值；（5） 如果，則需計算新解的接受率，若，則可以接受作為新的當前解；（6） 如果迭代滿足終止條件，則輸出當前解作為最優(yōu)解，結(jié)束程序；（7） 逐漸降低溫度控制參數(shù)，如依然大于0，轉(zhuǎn)步（2） 對數(shù)降溫策略： 快速降溫策略： 直線降溫策略： 指數(shù)降溫策略：，4. 模擬退火算法的特點（1） 優(yōu)點：具有漸

7、近收斂性，而且計算過程簡單、通用、魯棒性強，適用于并行處理，可用于求解復雜的非線性優(yōu)化問題；（2） 缺點：返回一個高質(zhì)量的近似解的時間花費較多，當問題規(guī)模不可避免的增大時，難以承受的運作時間將使算法喪失可行性。5. 模擬退火算法的改進途徑（1） 改變算法進行過程中的各種變異方法，如在算法中加入記憶器，記住算法進行過程中曾出現(xiàn)過的最優(yōu)近似解；（2） 對算法進行大規(guī)模的并行計算，真正縮短計算時間；（3）將模擬退火算法與其他智能搜索機制的算法相融合，取長補短。4、 粒子群優(yōu)化算法1. 基本思想:粒子群優(yōu)化算法就是對生物群體中的信息共享這種社會行為的模擬，即利用信息共享機制，使得個體之間可以相互借鑒經(jīng)驗，從而促進整個群體的發(fā)展。2. 算法流程：（1） 初始化粒子群，即隨機設定各個粒子的初始位置和初始速度；（2） 計算每個粒子的適應度；（3） 對每個粒子，將它的適應度和它經(jīng)歷過的最好位置所對應的適應度做比較，如果好于后者，則更新，否則，保持不變；（4） 將本次迭代中的每個粒子的適應度分別和群體所經(jīng)歷最好位置所對應的適應度作比較，如果好于后者，則更新，否則，保持不變；（5） 根據(jù)式 和式重新計算每個粒子的速度和位置；（6） 如果算法滿足結(jié)束條件（產(chǎn)生足夠好的位置或達到預先設置的最大迭代次數(shù)），則算法終止，否則轉(zhuǎn)步驟（2）。