智能計(jì)算綜述

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

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

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

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

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

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

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