1 引言
約束優(yōu)化問題近年來，一些學(xué)者將PSO算法推廣到約束優(yōu)化問題，其關(guān)鍵在于如何處理好約束，即解的可行性。如果約束處理的不好，其優(yōu)化的結(jié)果往往會出現(xiàn)不能夠收斂和結(jié)果是空集的狀況。基于PSO算法的約束優(yōu)化工作主要分為兩類： （1）罰函數(shù)法。罰函數(shù)的目的是將約束優(yōu)化問題轉(zhuǎn)化成無約束優(yōu)化問題。 （2）將粒子群的搜索范圍都限制在條件約束簇內(nèi)，即在可行解范圍內(nèi)尋優(yōu)。 根據(jù)文獻(xiàn)介紹，Parsopoulos等采用罰函數(shù)法，利用非固定多段映射函數(shù)對約束優(yōu)化問題進(jìn)行轉(zhuǎn)化，再利用PSO算法求解轉(zhuǎn)化后問題，仿真結(jié)果顯示PSO算法相對遺傳算法更具有優(yōu)越性，但其罰函數(shù)的設(shè)計(jì)過于復(fù)雜，不利于求解；Hu等采用可行解保留政策處理約束，即一方面更新存儲中所有粒子時(shí)僅保留可行解，另一方面在初始化階段所有粒子均從可行解空間取值，然而初始可行解空間對于許多問題是很難確定的；Ray等提出了具有多層信息共享策略的粒子群原理來處理約束，根據(jù)約束矩陣采用多層Pareto排序機(jī)制來產(chǎn)生優(yōu)良粒子，進(jìn)而用一些優(yōu)良的粒子來決定其余個(gè)體的搜索方向。 但是，目前有關(guān)運(yùn)用PSO算法方便實(shí)用地處理多約束目標(biāo)優(yōu)化問題的理論成果還不多。處理多約束優(yōu)化問題的方法有很多，但用PSO算法處理此類問題目前技術(shù)并不成熟，這里就不介紹了。 PSO算法粒子群優(yōu)化算法(PSO)是一種進(jìn)化計(jì)算技術(shù)(evolutionary computation)，1995 年由Eberhart 博士和kennedy 博士提出，源于對鳥群捕食的行為研究 。該算法最初是受到飛鳥集群活動(dòng)的規(guī)律性啟發(fā)，進(jìn)而利用群體智能建立的一個(gè)簡化模型。粒子群算法在對動(dòng)物集群活動(dòng)行為觀察基礎(chǔ)上，利用群體中的個(gè)體對信息的共享使整個(gè)群體的運(yùn)動(dòng)在問題求解空間中產(chǎn)生從無序到有序的演化過程，從而獲得最優(yōu)解。 PSO同遺傳算法類似，是一種基于迭代的優(yōu)化算法。系統(tǒng)初始化為一組隨機(jī)解，通過迭代搜尋最優(yōu)值。但是它沒有遺傳算法用的交叉(crossover)以及變異(mutation)，而是粒子在解空間追隨最優(yōu)的粒子進(jìn)行搜索。同遺傳算法比較，PSO的優(yōu)勢在于簡單容易實(shí)現(xiàn)并且沒有許多參數(shù)需要調(diào)整。目前已廣泛應(yīng)用于函數(shù)優(yōu)化，神經(jīng)網(wǎng)絡(luò)訓(xùn)練，模糊系統(tǒng)控制以及其他遺傳算法的應(yīng)用領(lǐng)域。 2 算法介紹簡介如前所述，PSO模擬鳥群的捕食行為。設(shè)想這樣一個(gè)場景：一群鳥在隨機(jī)搜索食物。在這個(gè)區(qū)域里只有一塊食物。所有的鳥都不知道食物在那里。但是他們知道當(dāng)前的位置離食物還有多遠(yuǎn)。那么找到食物的最優(yōu)策略是什么呢。最簡單有效的就是搜尋目前離食物最近的鳥的周圍區(qū)域。 PSO從這種模型中得到啟示并用于解決優(yōu)化問題。PSO中，每個(gè)優(yōu)化問題的解都是搜索空間中的一只鳥。我們稱之為“粒子”。所有的粒子都有一個(gè)由被優(yōu)化的函數(shù)決定的適應(yīng)值(fitness value)，每個(gè)粒子還有一個(gè)速度決定他們飛翔的方向和距離。然后粒子們就追隨當(dāng)前的最優(yōu)粒子在解空間中搜索。 PSO 初始化為一群隨機(jī)粒子(隨機(jī)解)。然后通過迭代找到最優(yōu)解。在每一次迭代中，粒子通過跟蹤兩個(gè)"最優(yōu)解，這個(gè)解叫做個(gè)體極值pBest。另一個(gè)極值是整個(gè)種群目前找到的最優(yōu)解，這個(gè)極值是全局極值gBest。另外也可以不用整個(gè)種群而只是用其中一部分作為粒子的鄰居，那么在所有鄰居中的極值就是局部極值。 粒子公式在找到這兩個(gè)最優(yōu)值時(shí)，粒子根據(jù)如下的公式來更新自己的速度和新的位置： v[] = w * v[] + c1 * rand() * (pbest[] - present[]) + c2 * rand() * (gbest[] - present[]) (a) present[] = present[] + v[] (b) v[] 是粒子的速度, w是慣性權(quán)重,persent[] 是當(dāng)前粒子的位置. pbest[] and gbest[] 如前定義 rand () 是介于（0， 1）之間的隨機(jī)數(shù). c1, c2 是學(xué)習(xí)因子. 通常 c1 = c2 = 2. 程序的偽代碼如下 For each particle ____Initialize particle END Do ____For each particle ________Calculate fitness value ________If the fitness value is better than the best fitness value (pBest) in history ____________set current value as the new pBest ____End ____Choose the particle with the best fitness value of all the particles as the gBest ____For each particle ________Calculate particle velocity according equation (a) ________Update particle position according equation (b) ____End While maximum iterations or minimum error criteria is not attained 在每一維粒子的速度都會被限制在一個(gè)最大速度Vmax，如果某一維更新后的速度超過用戶設(shè)定的Vmax，那么這一維的速度就被限定為Vmax 3 人工生命"人工生命"是來研究具有某些生命基本特征的人工系統(tǒng)。 社會系統(tǒng)現(xiàn)在我們討論另一種生物系統(tǒng)- 社會系統(tǒng). 更確切的是, 在由簡單個(gè)體組成的群落與環(huán)境以及個(gè)體之間的互動(dòng)行為. 也可稱做"群智能"(swarm intelligence). 這些模擬系統(tǒng)利用局部信息從而可能產(chǎn)生不可預(yù)測的群體行為 例如floys 和birds 他們都用來模擬魚群和鳥群的運(yùn)動(dòng)規(guī)律, 主要用于計(jì)算機(jī)視覺和計(jì)算機(jī)輔助設(shè)計(jì). 在計(jì)算智能(computational intelligence)領(lǐng)域有兩種基于群智能的算法.蟻群算法(ant colony optimization)和PSO粒子群算法(particle swarm optimization). 前者是對螞蟻群落食物采集過程的模擬. 已經(jīng)成功運(yùn)用在很多離散優(yōu)化問題上. 粒子群優(yōu)化算法(PSO) 也是起源對簡單社會系統(tǒng)的模擬. 最初設(shè)想是模擬鳥群覓食的過程. 但后來發(fā)現(xiàn)PSO是一種很好的優(yōu)化工具. 4 比較演化計(jì)算技術(shù)大多數(shù)演化計(jì)算技術(shù)都是用同樣的過程 ： 1.種群隨機(jī)初始化 2. 對種群內(nèi)的每一個(gè)個(gè)體計(jì)算適應(yīng)值(fitness value).適應(yīng)值與最優(yōu)解的距離直接有關(guān) 3. 種群根據(jù)適應(yīng)值進(jìn)行復(fù)制 4. 如果終止條件滿足的話，就停止，否則轉(zhuǎn)步驟2 從以上步驟，我們可以看到PSO和GA有很多共同之處。兩者都隨機(jī)初始化種群，而且都使用適應(yīng)值來評價(jià)系統(tǒng)，而且都根據(jù)適應(yīng)值來進(jìn)行一定的隨機(jī)搜索。兩個(gè)系統(tǒng)都不是保證一定找到最優(yōu)解 。 記憶但是，PSO 沒有遺傳操作如交叉(crossover)和變異(mutation). 而是根據(jù)自己的速度來決定搜索。粒子還有一個(gè)重要的特點(diǎn)，就是有記憶。 與遺傳算法比較, PSO 的信息共享機(jī)制是很不同的. 在遺傳算法中，染色體(chromosomes) 互相共享信息，所以整個(gè)種群的移動(dòng)是比較均勻的向最優(yōu)區(qū)域移動(dòng). 在PSO中, 只有g(shù)Best (or pBest) 給出信息給其他的粒子，這是單向的信息流動(dòng). 整個(gè)搜索更新過程是跟隨當(dāng)前最優(yōu)解的過程. 與遺傳算法比較, 在大多數(shù)的情況下，所有的粒子可能更快的收斂于最優(yōu)解 5 和PSO人工神經(jīng)網(wǎng)絡(luò)人工神經(jīng)網(wǎng)絡(luò)(ANN)是模擬大腦分析過程的簡單數(shù)學(xué)模型，誤差反向傳播算法是最流行的神經(jīng)網(wǎng)絡(luò)訓(xùn)練算法。近來也有很多研究開始利用演化計(jì)算(evolutionary computation)技術(shù)來研究人工神經(jīng)網(wǎng)絡(luò)的各個(gè)方面。 演化計(jì)算可以用來研究神經(jīng)網(wǎng)絡(luò)的三個(gè)方面：網(wǎng)絡(luò)連接權(quán)重，網(wǎng)絡(luò)結(jié)構(gòu)(網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，傳遞函數(shù))，網(wǎng)絡(luò)學(xué)習(xí)算法。 不過大多數(shù)這方面的工作都集中在網(wǎng)絡(luò)連接權(quán)重，和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)上。在GA中，網(wǎng)絡(luò)權(quán)重和/或拓?fù)浣Y(jié)構(gòu)一般編碼為染色體(Chromosome)，適應(yīng)函數(shù)(fitness function)的選擇一般根據(jù)研究目的確定。例如在分類問題中，錯(cuò)誤分類的比率可以用來作為適應(yīng)值 演化計(jì)算的優(yōu)勢在于可以處理一些傳統(tǒng)方法不能處理的例子例如不可導(dǎo)的節(jié)點(diǎn)傳遞函數(shù)或者沒有梯度信息存在。但是缺點(diǎn)在于：在某些問題上性能并不是特別好。2. 網(wǎng)絡(luò)權(quán)重的編碼而且遺傳算子的選擇有時(shí)比較麻煩 最近已經(jīng)有一些利用PSO來代替反向傳播算法來訓(xùn)練神經(jīng)網(wǎng)絡(luò)的論文。研究表明PSO 是一種很有潛力的神經(jīng)網(wǎng)絡(luò)算法。PSO速度比較快而且可以得到比較好的結(jié)果。而且還沒有遺傳算法碰到的問題 PSO訓(xùn)練過程這里用一個(gè)簡單的例子說明PSO訓(xùn)練神經(jīng)網(wǎng)絡(luò)的過程。這個(gè)例子使用分類問題的基準(zhǔn)函數(shù)(Benchmark function)IRIS數(shù)據(jù)集。(Iris 是一種鳶尾屬植物) 在數(shù)據(jù)記錄中，每組數(shù)據(jù)包含Iris花的四種屬性：萼片長度，萼片寬度，花瓣長度，和花瓣寬度，三種不同的花各有50組數(shù)據(jù). 這樣總共有150組數(shù)據(jù)或模式。 我們用3層的神經(jīng)網(wǎng)絡(luò)來做分類?，F(xiàn)在有四個(gè)輸入和三個(gè)輸出。所以神經(jīng)網(wǎng)絡(luò)的輸入層有4個(gè)節(jié)點(diǎn)，輸出層有3個(gè)節(jié)點(diǎn)我們也可以動(dòng)態(tài)調(diào)節(jié)隱含層節(jié)點(diǎn)的數(shù)目，不過這里我們假定隱含層有6個(gè)節(jié)點(diǎn)。我們也可以訓(xùn)練神經(jīng)網(wǎng)絡(luò)中其他的參數(shù)。不過這里我們只是來確定網(wǎng)絡(luò)權(quán)重。粒子就表示神經(jīng)網(wǎng)絡(luò)的一組權(quán)重，應(yīng)該是4*6+6*3=42個(gè)參數(shù)。權(quán)重的范圍設(shè)定為[-100，100] (這只是一個(gè)例子，在實(shí)際情況中可能需要試驗(yàn)調(diào)整).在完成編碼以后，我們需要確定適應(yīng)函數(shù)。對于分類問題，我們把所有的數(shù)據(jù)送入神經(jīng)網(wǎng)絡(luò)，網(wǎng)絡(luò)的權(quán)重有粒子的參數(shù)決定。然后記錄所有的錯(cuò)誤分類的數(shù)目作為那個(gè)粒子的適應(yīng)值?，F(xiàn)在我們就利用PSO來訓(xùn)練神經(jīng)網(wǎng)絡(luò)來獲得盡可能低的錯(cuò)誤分類數(shù)目。PSO本身并沒有很多的參數(shù)需要調(diào)整。所以在實(shí)驗(yàn)中只需要調(diào)整隱含層的節(jié)點(diǎn)數(shù)目和權(quán)重的范圍以取得較好的分類效果。 從上面的例子我們可以看到應(yīng)用PSO解決優(yōu)化問題的過程中有兩個(gè)重要的步驟: 問題解的編碼和適應(yīng)度函數(shù) 采用實(shí)數(shù)編碼不需要像遺傳算法一樣是二進(jìn)制編碼(或者采用針對實(shí)數(shù)的遺傳操作.例如對于問題 f(x) = x1^2 + x2^2+x3^2 求解, 粒子可以直接編碼為 (x1, x2, x3), 而適應(yīng)度函數(shù)就是f(x). 接著我們就可以利用前面的過程去尋優(yōu).這個(gè)尋優(yōu)過程是一個(gè)疊代過程, 中止條件一般為設(shè)置為達(dá)到最大循環(huán)數(shù)或者最小錯(cuò)誤 PSO中并沒有許多需要調(diào)節(jié)的參數(shù),下面列出了這些參數(shù)以及經(jīng)驗(yàn)設(shè)置 粒子數(shù): 一般取 20 – 40. 其實(shí)對于大部分的問題10個(gè)粒子已經(jīng)足夠可以取得好的結(jié)果, 不過對于比較難的問題或者特定類別的問題, 粒子數(shù)可以取到100 或 200 粒子的長度: 這是由優(yōu)化問題決定, 就是問題解的長度 粒子的范圍: 由優(yōu)化問題決定,每一維可是設(shè)定不同的范圍 Vmax: 最大速度,決定粒子在一個(gè)循環(huán)中最大的移動(dòng)距離,通常設(shè)定為粒子的范圍寬度,例如上面的例子里,粒子 (x1, x2, x3) x1 屬于 [-10, 10], 那么 Vmax 的大小就是 20 學(xué)習(xí)因子: c1 和 c2 通常等于 2. 不過在文獻(xiàn)中也有其他的取值. 但是一般 c1 等于 c2 并且范圍在0和4之間 中止條件: 最大循環(huán)數(shù)以及最小錯(cuò)誤要求. 例如, 在上面的神經(jīng)網(wǎng)絡(luò)訓(xùn)練例子中, 最小錯(cuò)誤可以設(shè)定為1個(gè)錯(cuò)誤分類, 最大循環(huán)設(shè)定為2000, 這個(gè)中止條件由具體的問題確定. 全局PSO和局部PSO: 我們介紹了兩種版本的粒子群優(yōu)化算法: 全局版和局部版. 前者速度快不過有時(shí)會陷入局部最優(yōu). 后者收斂速度慢一點(diǎn)不過很難陷入局部最優(yōu). 在實(shí)際應(yīng)用中, 可以先用全局PSO找到大致的結(jié)果,再用局部PSO進(jìn)行搜索. 慣性權(quán)重另外的一個(gè)參數(shù)是慣性權(quán)重, Shi 和Eberhart指出(A modified particle swarm optimizer,1998)：當(dāng)Vmax很小時(shí)（對schaffer的f6函數(shù)，Vmax<=2),使用接近于1的慣性權(quán)重;當(dāng)Vmax不是很小時(shí)（對schaffer的f6函數(shù)，Vmax>=3),使用權(quán)重w=0.8較好.如果沒有Vmax的信息,使用0.8作為權(quán)重也是一種很好的選擇.慣性權(quán)重w很小時(shí)偏重于發(fā)揮粒子群算法的局部搜索能力；慣性權(quán)重很大時(shí)將會偏重于發(fā)揮粒子群算法的全局搜索能力。 實(shí)現(xiàn)C++代碼代碼來自2008年數(shù)學(xué)建模東北賽區(qū)B題，
|
|
|
