數(shù)學(xué)建模遺傳算法和粒子群算法

1、遺傳算法（遺傳算法（Genetic AlgorithmGA），是模擬達(dá)爾文的），是模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過(guò)程的計(jì)算模型，它是由遺傳選擇和自然淘汰的生物進(jìn)化過(guò)程的計(jì)算模型，它是由美國(guó)美國(guó)Michigan大學(xué)的大學(xué)的J.Holland教授于教授于1975年首先提出年首先提出的遺傳算法作為一種新的全局優(yōu)化搜索算法，以其簡(jiǎn)單的遺傳算法作為一種新的全局優(yōu)化搜索算法，以其簡(jiǎn)單通用、魯棒性強(qiáng)、適于并行處理及應(yīng)用范圍廣等顯著特點(diǎn)，通用、魯棒性強(qiáng)、適于并行處理及應(yīng)用范圍廣等顯著特點(diǎn)，奠定了它作為奠定了它作為21世紀(jì)關(guān)鍵智能計(jì)算之一的地位世紀(jì)關(guān)鍵智能計(jì)算之一的地位1.遺傳算法的基本原理遺傳算法的

2、基本原理 遺傳算法的基本思想正是基于模仿生物界遺傳學(xué)的遺傳過(guò)遺傳算法的基本思想正是基于模仿生物界遺傳學(xué)的遺傳過(guò)程它把問(wèn)題的參數(shù)用基因代表，把問(wèn)題的解用染色體代表程它把問(wèn)題的參數(shù)用基因代表，把問(wèn)題的解用染色體代表（在計(jì)算機(jī)里用二進(jìn)制碼表示），從而得到一個(gè)由具有不同（在計(jì)算機(jī)里用二進(jìn)制碼表示），從而得到一個(gè)由具有不同染色體的個(gè)體組成的群體這個(gè)群體在問(wèn)題特定的環(huán)境里生染色體的個(gè)體組成的群體這個(gè)群體在問(wèn)題特定的環(huán)境里生存競(jìng)爭(zhēng)，適者有最好的機(jī)會(huì)生存和產(chǎn)生后代后代隨機(jī)化地存競(jìng)爭(zhēng)，適者有最好的機(jī)會(huì)生存和產(chǎn)生后代后代隨機(jī)化地繼承了父代的最好特征，并也在生存環(huán)境的控制支配下繼續(xù)繼承了父代的最好特征，并也在生存環(huán)

3、境的控制支配下繼續(xù)這一過(guò)程群體的染色體都將逐漸適應(yīng)環(huán)境，不斷進(jìn)化，最這一過(guò)程群體的染色體都將逐漸適應(yīng)環(huán)境，不斷進(jìn)化，最后收斂到一族最適應(yīng)環(huán)境的類似個(gè)體，即得到問(wèn)題最優(yōu)的后收斂到一族最適應(yīng)環(huán)境的類似個(gè)體，即得到問(wèn)題最優(yōu)的解值得注意的一點(diǎn)是，現(xiàn)在的遺傳算法是受生物進(jìn)化論學(xué)解值得注意的一點(diǎn)是，現(xiàn)在的遺傳算法是受生物進(jìn)化論學(xué)說(shuō)的啟發(fā)提出的，這種學(xué)說(shuō)對(duì)我們用計(jì)算機(jī)解決復(fù)雜問(wèn)題很說(shuō)的啟發(fā)提出的，這種學(xué)說(shuō)對(duì)我們用計(jì)算機(jī)解決復(fù)雜問(wèn)題很有用，而它本身是否完全正確并不重要（目前生物界對(duì)此學(xué)有用，而它本身是否完全正確并不重要（目前生物界對(duì)此學(xué)說(shuō)尚有爭(zhēng)議）說(shuō)尚有爭(zhēng)議） 序號(hào)序號(hào)遺傳學(xué)概念遺傳學(xué)概念遺傳算法概念遺傳算法

4、概念數(shù)學(xué)概念數(shù)學(xué)概念1個(gè)體要處理的基本對(duì)象、結(jié)構(gòu)也就是可行解2群體個(gè)體的集合被選定的一組可行解3染色體個(gè)體的表現(xiàn)形式可行解的編碼4基因染色體中的元素編碼中的元素5基因位某一基因在染色體中的位置元素在編碼中的位置6適應(yīng)值個(gè)體對(duì)于環(huán)境的適應(yīng)程度，或在環(huán)境壓力下的生存能力可行解所對(duì)應(yīng)的適應(yīng)函數(shù)值7種群被選定的一組染色體或個(gè)體根據(jù)入選概率定出的一組可行解8選擇從群體中選擇優(yōu)勝的個(gè)體，淘汰劣質(zhì)個(gè)體的操作保留或復(fù)制適應(yīng)值大的可行解，去掉小的可行解9交叉一組染色體上對(duì)應(yīng)基因段的交換根據(jù)交叉原則產(chǎn)生的一組新解10交叉概率染色體對(duì)應(yīng)基因段交換的概率（可能性大?。╅]區(qū)間0,1上的一個(gè)值，一般為0.650.9011

5、變異染色體水平上基因變化編碼的某些元素被改變12變異概率染色體上基因變化的概率（可能性大小）開區(qū)間(0,1)內(nèi)的一個(gè)值, 一般為0.0010.0113進(jìn)化、適者生存?zhèn)€體進(jìn)行優(yōu)勝劣汰的進(jìn)化，一代又一代地優(yōu)化目標(biāo)函數(shù)取到最大值，最優(yōu)的可行解2、遺傳算法的具體步驟、遺傳算法的具體步驟： 第一步：選擇編碼策略，把參數(shù)集合（可行解集合）轉(zhuǎn)換第一步：選擇編碼策略，把參數(shù)集合（可行解集合）轉(zhuǎn)換染色體結(jié)構(gòu)空間；染色體結(jié)構(gòu)空間； 第二步：定義適應(yīng)函數(shù)，便于計(jì)算適應(yīng)值；第二步：定義適應(yīng)函數(shù)，便于計(jì)算適應(yīng)值； 第三步：確定遺傳策略，包括選擇群體大小，選擇、交叉、第三步：確定遺傳策略，包括選擇群體大小，選擇、交叉、變

6、異方法以及確定交叉概率、變異概率等遺傳參數(shù)；變異方法以及確定交叉概率、變異概率等遺傳參數(shù)； 第四步：隨機(jī)產(chǎn)生初始化群體；第四步：隨機(jī)產(chǎn)生初始化群體； 第五步：計(jì)算群體中的個(gè)體或染色體解碼后的適應(yīng)值；第五步：計(jì)算群體中的個(gè)體或染色體解碼后的適應(yīng)值； 第六步：按照遺傳策略，運(yùn)用選擇、交叉和變異算子作用第六步：按照遺傳策略，運(yùn)用選擇、交叉和變異算子作用于群體，形成下一代群體；于群體，形成下一代群體； 第七步：判斷群體性能是否滿足某一指標(biāo)、或者是否已完第七步：判斷群體性能是否滿足某一指標(biāo)、或者是否已完成預(yù)定的迭代次數(shù)，不滿足則返回第五步、或者修改遺傳策成預(yù)定的迭代次數(shù)，不滿足則返回第五步、或者修改遺傳

7、策略再返回第六步略再返回第六步產(chǎn)生初始群體是否滿足終止條件得到結(jié)果結(jié)束程序是否計(jì)算每個(gè)個(gè)體的適應(yīng)值以概率選擇遺傳算子選擇一個(gè)個(gè)體復(fù)制到新群體選擇兩個(gè)個(gè)體進(jìn)行交叉插入到新群體選擇一個(gè)個(gè)體進(jìn)行變異插入到新群體得到新群體2( )20.5,max( ) 1,2f xxxf xx 已知求，（1）編碼和產(chǎn)生初始群體）編碼和產(chǎn)生初始群體 首先第一步要確定編碼的策略，也就是說(shuō)如何把到首先第一步要確定編碼的策略，也就是說(shuō)如何把到2這個(gè)區(qū)間內(nèi)的數(shù)用計(jì)算機(jī)語(yǔ)言表示出來(lái)編碼時(shí)要注這個(gè)區(qū)間內(nèi)的數(shù)用計(jì)算機(jī)語(yǔ)言表示出來(lái)編碼時(shí)要注意以下意以下 三個(gè)原則：三個(gè)原則： 完備性：?jiǎn)栴}空間中所有點(diǎn)（潛在解）都能成為完備性：?jiǎn)栴}空間中

8、所有點(diǎn)（潛在解）都能成為GA編碼空間中的點(diǎn)（染色體位串）的表現(xiàn)型；編碼空間中的點(diǎn)（染色體位串）的表現(xiàn)型； 健全性：健全性：GA編碼空間中的染色體位串必須對(duì)應(yīng)問(wèn)題編碼空間中的染色體位串必須對(duì)應(yīng)問(wèn)題空間中的某一潛在解；空間中的某一潛在解； 非冗余性：染色體和潛在解必須一一對(duì)應(yīng)非冗余性：染色體和潛在解必須一一對(duì)應(yīng)（1）編碼和產(chǎn)生初始群體）編碼和產(chǎn)生初始群體通過(guò)采用二進(jìn)制的形式來(lái)解決編碼問(wèn)題，將某個(gè)變量通過(guò)采用二進(jìn)制的形式來(lái)解決編碼問(wèn)題，將某個(gè)變量值代表的個(gè)體表示為一個(gè)值代表的個(gè)體表示為一個(gè)0，1二進(jìn)制串當(dāng)然，串二進(jìn)制串當(dāng)然，串長(zhǎng)取決于求解的精度如果要設(shè)定求解精度到六位小長(zhǎng)取決于求解的精度如果要設(shè)定求

9、解精度到六位小數(shù)，由于區(qū)間長(zhǎng)度為數(shù)，由于區(qū)間長(zhǎng)度為3，則必須將閉區(qū)間，則必須將閉區(qū)間-1,2分為分為3*10(6)等分因?yàn)榈确忠驗(yàn)?所以編碼的二進(jìn)制串至少需要所以編碼的二進(jìn)制串至少需要22位位21622209715223 1024194304 2( )20.5,max( ) 1,2f xxxf xx 已知求，將一個(gè)二進(jìn)制串（將一個(gè)二進(jìn)制串（b21b20b19b1b0）轉(zhuǎn)化為區(qū)間內(nèi)）轉(zhuǎn)化為區(qū)間內(nèi)對(duì)應(yīng)的實(shí)數(shù)值很簡(jiǎn)單，只需采取以下兩步：對(duì)應(yīng)的實(shí)數(shù)值很簡(jiǎn)單，只需采取以下兩步：1）將一個(gè)二進(jìn)制串（）將一個(gè)二進(jìn)制串（b21b20b19b1b0）代表的二）代表的二進(jìn)制數(shù)化為進(jìn)制數(shù)化為10進(jìn)制數(shù)：進(jìn)制數(shù)：2）

10、 對(duì)應(yīng)的區(qū)間內(nèi)的實(shí)數(shù)：對(duì)應(yīng)的區(qū)間內(nèi)的實(shí)數(shù)：例如，一個(gè)二進(jìn)制串例如，一個(gè)二進(jìn)制串a(chǎn)=表示實(shí)數(shù)表示實(shí)數(shù)0.637197 二進(jìn)制串二進(jìn)制串，則分別表示區(qū)間的兩個(gè)，則分別表示區(qū)間的兩個(gè)端點(diǎn)值端點(diǎn)值-1和和22121 20 191 02100()(2 )iiib b bbbbx222( 1)121xx 222=(1000101110110101000111) =22889673122889670.63719721xx 利用這種方法完成了遺傳算法的第一步利用這種方法完成了遺傳算法的第一步編碼，這種二編碼，這種二進(jìn)制編碼的方法完全符合上述的編碼的三個(gè)原則進(jìn)制編碼的方法完全符合上述的編碼的三個(gè)原則首先我們來(lái)隨

11、機(jī)的產(chǎn)生一個(gè)個(gè)體數(shù)為首先我們來(lái)隨機(jī)的產(chǎn)生一個(gè)個(gè)體數(shù)為4個(gè)的初始群體如下：個(gè)的初始群體如下：pop(1)=， % a1， % a2， % a3 % a4化成十進(jìn)制的數(shù)分別為：化成十進(jìn)制的數(shù)分別為：pop(1)= 1.523032，0.574022 ，-0.697235 ，0.247238 接下來(lái)我們就要解決每個(gè)染色體個(gè)體的適應(yīng)值問(wèn)題了接下來(lái)我們就要解決每個(gè)染色體個(gè)體的適應(yīng)值問(wèn)題了 （2）定義適應(yīng)函數(shù)和適應(yīng)值）定義適應(yīng)函數(shù)和適應(yīng)值 由于給定的目標(biāo)函數(shù)在內(nèi)的值有正有負(fù)，所以必須通過(guò)建由于給定的目標(biāo)函數(shù)在內(nèi)的值有正有負(fù)，所以必須通過(guò)建立適應(yīng)函數(shù)與目標(biāo)函數(shù)的映射關(guān)系，保證映射后的適應(yīng)值非立適應(yīng)函數(shù)與目標(biāo)

12、函數(shù)的映射關(guān)系，保證映射后的適應(yīng)值非負(fù)，而且目標(biāo)函數(shù)的優(yōu)化方向應(yīng)對(duì)應(yīng)于適應(yīng)值增大的方向，負(fù)，而且目標(biāo)函數(shù)的優(yōu)化方向應(yīng)對(duì)應(yīng)于適應(yīng)值增大的方向，也為以后計(jì)算各個(gè)體的入選概率打下基礎(chǔ)也為以后計(jì)算各個(gè)體的入選概率打下基礎(chǔ) 對(duì)于本題中的最大化問(wèn)題，定義適應(yīng)函數(shù)，采用下述方法：對(duì)于本題中的最大化問(wèn)題，定義適應(yīng)函數(shù)，采用下述方法：式中既可以是特定的輸入值，也可以是當(dāng)前所有代或最近式中既可以是特定的輸入值，也可以是當(dāng)前所有代或最近K代代中的最小值，這里為了便于計(jì)算，將采用了一個(gè)特定的輸入中的最小值，這里為了便于計(jì)算，將采用了一個(gè)特定的輸入值值minmin( ), ( )0( )0,f xFf xFg x若其他

13、 若取若取Fmin=-1，則當(dāng)，則當(dāng) 時(shí)適應(yīng)函數(shù)時(shí)適應(yīng)函數(shù) ；當(dāng)；當(dāng)時(shí)適應(yīng)函數(shù)時(shí)適應(yīng)函數(shù) 由上述所隨機(jī)產(chǎn)生的初始群體，我們可以先計(jì)算出目標(biāo)函由上述所隨機(jī)產(chǎn)生的初始群體，我們可以先計(jì)算出目標(biāo)函數(shù)值分別如下數(shù)值分別如下f pop(1)= 1.226437 , 1.318543 , -1.380607 , 0.933350 然后通過(guò)適應(yīng)函數(shù)計(jì)算出適應(yīng)值分別如下然后通過(guò)適應(yīng)函數(shù)計(jì)算出適應(yīng)值分別如下gpop(1)= 2.226437 , 2.318543 , 0 , 1.933350 ( )1f x ( )2g x ( )1.1f x ( )0.g x （3）確定選擇標(biāo)準(zhǔn)）確定選擇標(biāo)準(zhǔn)這里用到了適應(yīng)值的

14、比例來(lái)作為選擇的標(biāo)準(zhǔn)，得到的每個(gè)個(gè)這里用到了適應(yīng)值的比例來(lái)作為選擇的標(biāo)準(zhǔn)，得到的每個(gè)個(gè)體的適應(yīng)值比例叫作入選概率其計(jì)算公式如下：體的適應(yīng)值比例叫作入選概率其計(jì)算公式如下：對(duì)于給定的規(guī)模為對(duì)于給定的規(guī)模為n的群體的群體pop= ，個(gè)體的適應(yīng)值，個(gè)體的適應(yīng)值為為 ，則其入選概率為，則其入選概率為 由上述給出的群體，計(jì)算出各個(gè)個(gè)體的入選概率首先由上述給出的群體，計(jì)算出各個(gè)個(gè)體的入選概率首先然后分別用四個(gè)個(gè)體的適應(yīng)值去除以然后分別用四個(gè)個(gè)體的適應(yīng)值去除以 得：得：P(a1)=2.226437 / 6.478330 = 0.343675 % a1P(a2)=2.318543 / 6.478330 = 0

15、.357892 % a2P(a3)= 0 / 6.478330 = 0 % a3P(a4)=1.933350 / 6.478330 = 0.298433 % a4123,naa aa1( )( ),1,2,3,( )isiniig aP aing a41()6.478330iig a41()6.478330iig a( )ig a （4）產(chǎn)生種群）產(chǎn)生種群 計(jì)算完了入選概率后，就將入選概率大的個(gè)體選入種計(jì)算完了入選概率后，就將入選概率大的個(gè)體選入種群，淘汰概率小的個(gè)體，并用入選概率最大的個(gè)體補(bǔ)入種群，淘汰概率小的個(gè)體，并用入選概率最大的個(gè)體補(bǔ)入種群，得到與原群體大小同樣的種群群，得到與原群體大

16、小同樣的種群由初始群體的入選概率我們淘汰掉由初始群體的入選概率我們淘汰掉a3，再加入，再加入a2補(bǔ)足成與補(bǔ)足成與群體同樣大小的種群得到群體同樣大小的種群得到newpop(1)如下：如下：newpop(1)=， % a1， % a2， % a2 % a4 （5）交叉）交叉交叉也就是將一組染色體上對(duì)應(yīng)基因段的交換得到新的染色交叉也就是將一組染色體上對(duì)應(yīng)基因段的交換得到新的染色體，然后得到新的染色體組，組成新的群體體，然后得到新的染色體組，組成新的群體 我們把之前得到的我們把之前得到的newpop(1)的四個(gè)個(gè)體兩兩組成一對(duì)，的四個(gè)個(gè)體兩兩組成一對(duì)，重復(fù)的不配對(duì)，進(jìn)行交叉（可以在任一位進(jìn)行交叉）重復(fù)

17、的不配對(duì)，進(jìn)行交叉（可以在任一位進(jìn)行交叉） 通過(guò)交叉得到了四個(gè)新個(gè)體，得到新的群體通過(guò)交叉得到了四個(gè)新個(gè)體，得到新的群體jchpop (1)如如下：下：jchpop(1)=，1101011101001100011110，1000011001010001000010，1000011001010001000010 0110101001101110010101 這里采用的是單點(diǎn)交叉的方法，當(dāng)然還有多點(diǎn)交叉的方法，這里采用的是單點(diǎn)交叉的方法，當(dāng)然還有多點(diǎn)交叉的方法，這里就不著重介紹了這里就不著重介紹了 （6）變異）變異變異也就是通過(guò)一個(gè)小概率改變?nèi)旧w位串上的某個(gè)基變異也就是通過(guò)一個(gè)小概率改變?nèi)旧w位

18、串上的某個(gè)基因現(xiàn)把剛得到的因現(xiàn)把剛得到的jchpop(1)中第中第3個(gè)個(gè)體中的第個(gè)個(gè)體中的第9位改變，就位改變，就產(chǎn)生了變異，得到了新的群體產(chǎn)生了變異，得到了新的群體pop(2)如下：如下：pop(2)= ， 然后重復(fù)上述的選擇、交叉、變異直到滿足終止條件為止然后重復(fù)上述的選擇、交叉、變異直到滿足終止條件為止 （7）終止條件）終止條件 遺傳算法的終止條件有兩類常見條件：（遺傳算法的終止條件有兩類常見條件：（1）采用設(shè)定最）采用設(shè)定最大（遺傳）代數(shù)的方法，一般可設(shè)定為大（遺傳）代數(shù)的方法，一般可設(shè)定為50代，此時(shí)就可能得代，此時(shí)就可能得出最優(yōu)解此種方法簡(jiǎn)單易行，但可能不是很精確（出最優(yōu)解此種方法

19、簡(jiǎn)單易行，但可能不是很精確（Matlab程序參見附錄程序參見附錄1）；（）；（2）根據(jù)個(gè)體的差異來(lái)判斷，通過(guò)計(jì)算）根據(jù)個(gè)體的差異來(lái)判斷，通過(guò)計(jì)算種群中基因多樣性測(cè)度，即所有基因位相似程度來(lái)進(jìn)行控種群中基因多樣性測(cè)度，即所有基因位相似程度來(lái)進(jìn)行控制制 粒子群算法粒子群算法(particle swarm optimization(particle swarm optimization，PSO)PSO)由由KennedyKennedy和和EberhartEberhart在在19951995年提出，該算法模年提出，該算法模擬鳥集群飛行覓食的行為，鳥之間通過(guò)集體的協(xié)作擬鳥集群飛行覓食的行為，鳥之間通過(guò)集

20、體的協(xié)作使群體達(dá)到最優(yōu)目的，是一種基于群智能的優(yōu)化方使群體達(dá)到最優(yōu)目的，是一種基于群智能的優(yōu)化方法。法。 PSOPSO的優(yōu)勢(shì)在于簡(jiǎn)單容易實(shí)現(xiàn)同時(shí)又有深刻的智的優(yōu)勢(shì)在于簡(jiǎn)單容易實(shí)現(xiàn)同時(shí)又有深刻的智能背景，既適合科學(xué)研究，又特別適合工程應(yīng)用，能背景，既適合科學(xué)研究，又特別適合工程應(yīng)用，并且沒(méi)有許多參數(shù)需要調(diào)整。并且沒(méi)有許多參數(shù)需要調(diào)整。 1 PSO算法簡(jiǎn)介 James Kennedy received the Ph.D. degree from the University of North Carolina, Chapel Hill, in 1992. He is with the U.S. D

21、epartment of Labor, Washington, DC. He is a Social Psychologist who has been working with the particle swarm algorithm since 1994. Russell C. Eberhart (M88SM89F01) received the Ph.D. degree in electrical engineering from Kansas State University, Manhattan. He is the Chair and Professor of Electrical

22、 and Computer Engineering, Purdue School of Engineering and Technology, Indiana UniversityPurdue University Indianapolis (IUPUI),Indianapolis, IN. 2 PSO產(chǎn)生背景之一：復(fù)雜適應(yīng)系統(tǒng)產(chǎn)生背景之一：復(fù)雜適應(yīng)系統(tǒng) CAS CAS理論的最基本的思想可以概述如下理論的最基本的思想可以概述如下： 我們把系統(tǒng)中的成員稱為具有適應(yīng)性的主體，我們把系統(tǒng)中的成員稱為具有適應(yīng)性的主體，簡(jiǎn)稱為主體。所謂具有適應(yīng)性，就是指它能夠與簡(jiǎn)稱為主體。所謂具有適應(yīng)性，就是指它能夠與

23、環(huán)境以及其它主體進(jìn)行環(huán)境以及其它主體進(jìn)行交流交流，在這種交流的過(guò)程，在這種交流的過(guò)程中中“學(xué)習(xí)學(xué)習(xí)”或或“積累經(jīng)驗(yàn)積累經(jīng)驗(yàn)”，并且根據(jù)學(xué)到的經(jīng)，并且根據(jù)學(xué)到的經(jīng)驗(yàn)改變自身的結(jié)構(gòu)和行為方式。整個(gè)系統(tǒng)的演變驗(yàn)改變自身的結(jié)構(gòu)和行為方式。整個(gè)系統(tǒng)的演變或進(jìn)化，包括新層次的產(chǎn)生，分化和多樣性的出或進(jìn)化，包括新層次的產(chǎn)生，分化和多樣性的出現(xiàn)，新的、聚合而成的、更大的主體的出現(xiàn)等等，現(xiàn)，新的、聚合而成的、更大的主體的出現(xiàn)等等，都是在這個(gè)基礎(chǔ)上出現(xiàn)的。都是在這個(gè)基礎(chǔ)上出現(xiàn)的。 CASCAS的四個(gè)基本特點(diǎn)：的四個(gè)基本特點(diǎn)：n首先，主體首先，主體(Adaptive Agent)(Adaptive Agent)是主

24、動(dòng)的、活的實(shí)體；是主動(dòng)的、活的實(shí)體； n其次，個(gè)體與環(huán)境其次，個(gè)體與環(huán)境( (包括個(gè)體之間包括個(gè)體之間) )的相互影響，相互的相互影響，相互作用，是系統(tǒng)演變和進(jìn)化的主要?jiǎng)恿?；作用，是系統(tǒng)演變和進(jìn)化的主要?jiǎng)恿Γ籲再次，這種方法不象許多其他的方法那樣，把宏觀和再次，這種方法不象許多其他的方法那樣，把宏觀和微觀截然分開，而是把它們有機(jī)地聯(lián)系起來(lái)；微觀截然分開，而是把它們有機(jī)地聯(lián)系起來(lái)；n最后，這種建模方法還引進(jìn)了隨機(jī)因素的作用，使它最后，這種建模方法還引進(jìn)了隨機(jī)因素的作用，使它具有更強(qiáng)的描述和表達(dá)能力。具有更強(qiáng)的描述和表達(dá)能力。 2 PSO產(chǎn)生背景之二產(chǎn)生背景之二:人工生命人工生命 人工生命人工生命

25、“是來(lái)研究具有某些生命基本特征的是來(lái)研究具有某些生命基本特征的人工系統(tǒng)。人工生命包括兩方面的內(nèi)容：人工系統(tǒng)。人工生命包括兩方面的內(nèi)容： 研究如何利用計(jì)算技術(shù)研究生物現(xiàn)象；研究如何利用計(jì)算技術(shù)研究生物現(xiàn)象； 研究如何利用生物技術(shù)研究計(jì)算問(wèn)題。研究如何利用生物技術(shù)研究計(jì)算問(wèn)題。 現(xiàn)在我們討論另一種生物系統(tǒng)：社會(huì)系統(tǒng)，更確切現(xiàn)在我們討論另一種生物系統(tǒng)：社會(huì)系統(tǒng)，更確切地說(shuō)，是由簡(jiǎn)單個(gè)體組成的群落與環(huán)境以及個(gè)體之間地說(shuō)，是由簡(jiǎn)單個(gè)體組成的群落與環(huán)境以及個(gè)體之間的互動(dòng)行為，也可稱做的互動(dòng)行為，也可稱做 群智能群智能 。 3 基本基本PSO算法算法 粒子群優(yōu)化算法源于粒子群優(yōu)化算法源于19871987年年

26、ReynoldsReynolds對(duì)鳥群社會(huì)系對(duì)鳥群社會(huì)系統(tǒng)的仿真研究。在鳥群中，一群鳥在空中飛行，每個(gè)鳥遵統(tǒng)的仿真研究。在鳥群中，一群鳥在空中飛行，每個(gè)鳥遵守以下三條規(guī)則：守以下三條規(guī)則： 1 1）避免與相鄰的鳥發(fā)生碰撞沖突；）避免與相鄰的鳥發(fā)生碰撞沖突； 2 2）盡量與自己周圍的鳥在速度上保持協(xié)調(diào)和一致；）盡量與自己周圍的鳥在速度上保持協(xié)調(diào)和一致； 3 3）盡量試圖向自己所認(rèn)為的群體中靠近。）盡量試圖向自己所認(rèn)為的群體中靠近。 僅通過(guò)使用這三條規(guī)則，鳥群系統(tǒng)就出現(xiàn)非常逼真的僅通過(guò)使用這三條規(guī)則，鳥群系統(tǒng)就出現(xiàn)非常逼真的群體聚集行為，鳥成群地在空中飛行，當(dāng)遇到障礙時(shí)它們?nèi)后w聚集行為，鳥成群地在

27、空中飛行，當(dāng)遇到障礙時(shí)它們會(huì)分開繞行而過(guò)，隨后又會(huì)重新形成群體。會(huì)分開繞行而過(guò)，隨后又會(huì)重新形成群體。 ReynoldsReynolds僅僅將其作為僅僅將其作為CASCAS的一個(gè)實(shí)例作仿真的一個(gè)實(shí)例作仿真研究，而并未將它用于優(yōu)化計(jì)算中。研究，而并未將它用于優(yōu)化計(jì)算中。 KennedyKennedy和和EberhartEberhart在中加入了一個(gè)特定點(diǎn)，在中加入了一個(gè)特定點(diǎn)，定義為食物，鳥根據(jù)周圍鳥的覓食行為來(lái)尋找食定義為食物，鳥根據(jù)周圍鳥的覓食行為來(lái)尋找食物。他們的初衷是希望通過(guò)這種模型來(lái)模擬鳥群物。他們的初衷是希望通過(guò)這種模型來(lái)模擬鳥群尋找食源的現(xiàn)象，然而實(shí)驗(yàn)結(jié)果卻揭示這個(gè)仿真尋找食源的現(xiàn)

28、象，然而實(shí)驗(yàn)結(jié)果卻揭示這個(gè)仿真模型中蘊(yùn)涵著很強(qiáng)的優(yōu)化能力，尤其是在多維空模型中蘊(yùn)涵著很強(qiáng)的優(yōu)化能力，尤其是在多維空間尋優(yōu)中。間尋優(yōu)中。 PSOPSO中，每個(gè)優(yōu)化問(wèn)題的解都是搜索空間中的一中，每個(gè)優(yōu)化問(wèn)題的解都是搜索空間中的一只鳥。稱之為只鳥。稱之為“粒子粒子”。所有的粒子都有一個(gè)由被優(yōu)。所有的粒子都有一個(gè)由被優(yōu)化的函數(shù)決定的適應(yīng)值，每個(gè)粒子還有一個(gè)速度決定化的函數(shù)決定的適應(yīng)值，每個(gè)粒子還有一個(gè)速度決定他們飛翔的方向和距離。然后粒子們就追隨當(dāng)前的最他們飛翔的方向和距離。然后粒子們就追隨當(dāng)前的最優(yōu)粒子在解空間中搜索優(yōu)粒子在解空間中搜索. . PSO PSO 初始化為一群隨機(jī)粒子。然后通過(guò)迭代找到最

29、初始化為一群隨機(jī)粒子。然后通過(guò)迭代找到最優(yōu)解。在每一次疊代中，粒子通過(guò)跟蹤兩個(gè)優(yōu)解。在每一次疊代中，粒子通過(guò)跟蹤兩個(gè) 極值極值 來(lái)來(lái)更新自己。第一個(gè)就是粒子本身所找到的最優(yōu)解。這更新自己。第一個(gè)就是粒子本身所找到的最優(yōu)解。這個(gè)解叫做個(gè)體極值個(gè)解叫做個(gè)體極值pBestpBest. . 另一個(gè)極值是整個(gè)種群目前另一個(gè)極值是整個(gè)種群目前找到的最優(yōu)解。這個(gè)極值是全局極值找到的最優(yōu)解。這個(gè)極值是全局極值gBestgBest。 PSOPSO算法數(shù)學(xué)表示如下：算法數(shù)學(xué)表示如下： 設(shè)搜索空間為設(shè)搜索空間為D D維，總粒子數(shù)為維，總粒子數(shù)為n n。第。第i i個(gè)粒子位個(gè)粒子位置表示為向量置表示為向量X Xi i

30、= =( ( x xi1i1, x, xi2i2, x, xiDiD ) )；第；第i i個(gè)粒子個(gè)粒子 “飛行飛行”歷史中的過(guò)去最優(yōu)位置為歷史中的過(guò)去最優(yōu)位置為P Pi i= =( ( p pi1i1,p,pi2i2,p,piDiD ) )，其中第，其中第g g個(gè)粒子的過(guò)去最優(yōu)位個(gè)粒子的過(guò)去最優(yōu)位置置P Pg g為所有為所有P Pi i ( ( i=1, ,n i=1, ,n) )中的最優(yōu)；第中的最優(yōu)；第i i個(gè)粒子的個(gè)粒子的位置變化率（速度）為向量位置變化率（速度）為向量V Vi i= =( (v vi1i1, v, vi2i2, v, viDiD) )。每個(gè)粒子的位置按如下公式進(jìn)行變化（每

31、個(gè)粒子的位置按如下公式進(jìn)行變化（“飛行飛行”）：）：(1)( )(1)11idididxtxtvtindD（1）（2）其中，其中，C C1,C21,C2為正常數(shù)，稱為加速因子；為正常數(shù)，稱為加速因子；randrand( )( )為為00，11之間的隨機(jī)數(shù)；之間的隨機(jī)數(shù)；w w稱慣性因子，稱慣性因子，w w較大適于對(duì)解較大適于對(duì)解空間進(jìn)行大范圍探查，空間進(jìn)行大范圍探查，w w較小適于進(jìn)行小范圍開挖。較小適于進(jìn)行小范圍開挖。第第d d（1 1ddD D）維的位置變化范圍為）維的位置變化范圍為-XMAXd , -XMAXd , XMAXdXMAXd，速度變化范圍為，速度變化范圍為-VMAXd , VMAXd-VMAXd , VMAXd，迭代中，迭代中若位置和速度超過(guò)邊界范圍則取邊界值。若位置和速度超過(guò)邊界范圍則取邊界值。 12(1)( )( )( )( )( )( )( )ididididg didvtwvtcra n dptxtcra n dptxt 粒子群初始位置和速度隨機(jī)產(chǎn)生，然后按公粒子群初始位置和速度隨機(jī)產(chǎn)生，然后按公式式(1)(2)(1)(2)進(jìn)行迭代，直至找到滿意的解。目前，進(jìn)行迭代，直至找到滿意的解。目前，常用的粒子群算法將全體粒子群常用的粒子群算法將全體粒子群(Global)(Glob