柳 寅， 馬 良， 黃 鈺

（上海理工大學(xué)管理學(xué)院 200093）

粒子群算法（particle swarm algorithm，PSA）是一種新型智能優(yōu)化群體算法［1－2］，這種算法起源于人們對鳥類覓食行為的研究.同遺傳算法類似PSA也是一種基于迭代的優(yōu)化算法.目前PSA已在函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡(luò)優(yōu)化［3］、系統(tǒng)識別［4］等領(lǐng)域有了較廣泛的應(yīng)用.但傳統(tǒng)PSA經(jīng)常在解決實際問題［5－8］時，尤其在解決大規(guī)模的問題時容易出現(xiàn)算法過早停滯的缺點，其導(dǎo)致算法陷入局部最優(yōu)解.本文針對傳統(tǒng)PSA的上述缺點提出了改進的算法：使用模糊規(guī)則［9－11］引進新的擾動因子改進粒子群算法，簡稱模糊粒子群算法（fuzzy particle swarm algorithm，F(xiàn)PSA），并通過在典型函數(shù)上的測試表明該算法有比較好的全局優(yōu)化能力.

1 模糊粒子群算法

1.1 粒子群算法基本原理

在傳統(tǒng)PSA中，每個優(yōu)化問題的解都好比是搜索空間中的一只“鳥”，稱其為“粒子”.而被優(yōu)化的函數(shù)決定各粒子的適應(yīng)值，每個粒子同樣還有一個決定它們飛翔的方向和距離的速度因素，這決定粒子追隨當(dāng)前的最優(yōu)粒子在解空間中搜索.

傳統(tǒng)PSA的標(biāo)準(zhǔn)進化方程為

式中，v為粒子的速度；ω為慣性權(quán)重；rand為［0，1］之間的隨機數(shù)；c1，c2為學(xué)習(xí)因子；x（t）為第t次迭代時粒子的方向.

在每次的迭代過程中，各粒子都通過兩個“極值”來更新自己：其一是粒子自身當(dāng)前迭代過程的最優(yōu)位置，記為pbest；其二是群體當(dāng)前迭代過程的最優(yōu)位置，記為gbest.其中，第i個粒子表示為n維的向量xi＝（xi1，xi2，…，xin），即第i個粒子的位置為xi，每個粒子代表一個可能的解.

1.2 模糊粒子群算法的基本思路

因為傳統(tǒng)PSA在全局極值gbest或個體極值pbest得到局部最優(yōu)解時，粒子群不會在解空間中再次進行搜索，而且其它粒子將迅速向局部最優(yōu)解靠攏，所以使算法容易出現(xiàn)過早收斂導(dǎo)致不能得到最優(yōu)解.又因為傳統(tǒng)PSA的全局搜索模式相對單一（PSA中僅僅使用全局極值點的信息，而沒有加入其它的參考信息，所以使得粒子產(chǎn)生的方式比較單一），這樣不利于種群多樣性且阻礙算法擴大搜索的范圍.

針對上述問題，利用模糊控制器中所使用的模糊規(guī)則對傳統(tǒng)粒子群算加入了新的擾動因子.在粒子群算法迭代的早期（即迭代計數(shù)器NC較小的時候），因為此時算法正處于大面積尋優(yōu)的初步階段，所以這個時候不應(yīng)該讓每次迭代更新后的v過大；而伴隨著迭代次數(shù)的增加，后面逐步加大v.到了粒子群算法迭代的后期（即NC＞3／4 NCmax），大幅度增加v，其v的顯著改變對粒子的搜索方向產(chǎn)生較大的影響，這使算法更容易跳出局部最優(yōu)解，從而更容易獲得最優(yōu)的解.

此外，模糊粒子群算法還利用每次各個粒子所求得的解的質(zhì)量價值Value，結(jié)合NC的大小綜合得出干擾因子的大小，而不是每次都僅僅根據(jù)NC的大小來決定干擾因子.

對于各個粒子所獲得的解的Value，綜合NC，以這兩個值作為模糊控制器的模糊輸入Output.對這兩個量進行模糊化劃分和模糊量化，然后，確定生成擾動因子的模糊控制規(guī)則，最后對輸出的模糊量進行反模糊化，最終作用于每個粒子此次的速度更新量.

1.3 模糊粒子群算法流程

首先確定隸屬度函數(shù)的形狀，這里為了方便計算，兩個模糊輸入變量的隸屬度函數(shù)都取等腰三角形，輸出變量的隸屬度函數(shù)為棒形單數(shù)值函數(shù)，模糊語言數(shù)目設(shè)定5個，即將模糊輸入輸出空間平均分割成5個模糊集：S（小）、M－（較?。?、M（中）、M＋（較大）、B（大），具體見圖1.

圖1 模糊輸入輸出隸屬度函數(shù)Fig.1 Member functions of fuzzy input and output

系統(tǒng)模糊規(guī)則采用的形式為

經(jīng)過大量的實驗比較后，具體決定擾動因子生成的模糊規(guī)則如表1所示.

表1 模糊控制規(guī)則表Tab.1 Fuzzy rules table

系統(tǒng)有兩個輸入，有5個模糊值，因此最大的規(guī)則基中有5×5＝25條規(guī)則.由于后件也有5個模糊值，則前件對后件的規(guī)則空間為25×5矩陣.

推理和模糊化方法采用Mamdani推理，重心法.由于輸出的隸屬度函數(shù)是棒形函數(shù)，所以重心法在這里就變成了簡單的加權(quán)平均，由此進一步簡化了算法的運算量.

根據(jù)模糊規(guī)則表中的模糊規(guī)則定義，輸入的模糊化就是將實際的輸入變量從基本論域（［Input1min，Input1max］，［Input2min，Input2max］），轉(zhuǎn)換到模糊輸入論域（0，1）.

同理，輸出的去模糊化就是將模糊輸出論域（0，1）轉(zhuǎn)換到實際的輸出基本論域（［Outputmin，Outputmax］），模糊控制規(guī)則表圖形如圖2所示.

圖2 模糊控制規(guī)則表圖形Fig.2 Image of fuzzy rules table

對于具體的輸入（a，b）

經(jīng)下式轉(zhuǎn)換為（fa，fb），其中fa，fb∈（0，1）.

對于輸出具體的模糊輸出fc，fc∈（0，1），可轉(zhuǎn)換為

其中，c∈［Outputmin，Outputmax］.

模糊粒子群算法流程：

步驟1 隨機初始化粒子群中粒子的位置與速度；

步驟2 將粒子的pbest設(shè)置為當(dāng)前位置，gbest設(shè)置為初始群體中最佳粒子的位置；

步驟3 判斷算法停止準(zhǔn)則是否滿足，如果滿足，轉(zhuǎn)向步驟7，否則執(zhí)行步驟4；

步驟4 按照模糊粒子群算法的更新機制更新各粒子的速度和移動方向，更新方程為

其中，λ為反模糊化后的模糊輸出值（擾動因子）.

步驟5 更新所有粒子經(jīng)歷過的最好位置，即全局極值gbest（如果可行粒子的目標(biāo)函數(shù)值優(yōu)于gbest的目標(biāo)函數(shù)值，gbest設(shè)置為新位置）；

步驟6 判斷算法停止準(zhǔn)則是否都滿足，如果滿足則轉(zhuǎn)步驟7，否則執(zhí)行步驟4；

步驟7 輸出gbest，算法停止.

2 算例測試

為了驗證算法的可行性和有效性，選取了一系列經(jīng)典函數(shù)進行測試實驗.參數(shù)設(shè)置：種群規(guī)模設(shè)定為20～80個、c1＝c2＝2、ω＝0.8、最大迭代次數(shù)為100.實驗所用硬件為AMD 2.0GHz，2GB RAM，軟件為Windows XP和Matlab 2008.

算例1（Griewank函數(shù)）

此函數(shù)為漏斗形狀，最小極值點位于圖像最中央.采用遺傳算法遺傳200代后的結(jié)果為0.093 22.LINGO軟件所得到的目標(biāo)值為0.623 42，Matlab優(yōu)化工具箱得到的結(jié)果為0.060 31，模糊粒子群算法得到的最優(yōu)解為0，（x，y）＝（0，0）.Griewank函數(shù)圖像由圖3所示.

圖3 Griewank函數(shù)圖像Fig.3 Image of function Griewank

算例2（Schaffer函數(shù)）

混沌優(yōu)化方法所需計算次數(shù)為1 092，混沌遺傳算法所需計算次數(shù)為458.LINGO軟件所得到的目標(biāo)值為0.646 848 8［11］，Matlab優(yōu)化工具箱得到的結(jié)果為0.990 3，模糊粒子群算法得到的最優(yōu)解為1，（x，y）＝（0，0）.Schaffer函數(shù)圖像由圖4所示.

圖4 Schaffer函數(shù)圖像Fig.4 Image of function Schaffer

算例3（Hansen函數(shù)）

此函數(shù)局部極值點有760個.LINGO軟件得到的結(jié)果為12.354 7.Matlab內(nèi)部函數(shù)所得到結(jié)果與初值有關(guān)，初值取得好，則可得到最優(yōu)解，有不確定因素的存在［11］.遺傳算法100代內(nèi)可得到最優(yōu)解.

模糊粒子群算法可以得到全局最優(yōu)值為176.541 793，并經(jīng)多次反復(fù)運行，可找到全部最優(yōu)解（－7.589 893，－7.708 314），（－7.589 893，－1.425 128），（－7.589 893，4.858 057），（－1.306 708，－7.708 314），（－1.306 708，－1.425 128），（－1.306 708，4.858 057），（4.976 478，－7.708 314），（4.976 478，－1.425 128），（4.976 478，4.858 057）.Hansen函數(shù)圖像由圖5所示.

圖5 Hansen函數(shù)圖像Fig.5 Image of function Hansen

算例4（大海撈針問題）

該問題的全局最優(yōu)解被最差解包圍，4個局部極值點為：（－5.12，5.12），（－5.12，－5.12），（5.12，－5.12），（5.12，5.12），函數(shù)值為2748.78.LINGO和Matlab內(nèi)部函數(shù)，都會落入上述4個局部極值點中.采用有一定技巧的遺傳算法在遺傳300代后才能以90%的幾率獲得最優(yōu)解，運行模糊粒子群算法可得到最優(yōu)解：3 600，（x，y）＝（0，0）.算例4函數(shù)圖像由圖6所示.

圖6 算例4函數(shù)圖像Fig.6 Image of function 4

從以上的算例可以看出，模糊粒子群算法具有更有效地獲取全局最優(yōu)解的能力.

3 結(jié)束語

通過運用模糊控制器中的模糊規(guī)則為傳統(tǒng)粒子群算法加入了新的擾動因子，改進了粒子群進化的更新方程，利用該方程更新粒子的速度與位置，不僅避免了過早收斂問題，而且還擴大了群體的搜索范圍.通過實例驗證表明了該算法的有效性.對此方法中涉及參數(shù)地指導(dǎo)性調(diào)整將是進一步研究的課題.

［1］ Kennedy I，Eberhart R C.Particle swarm optimization［C］／／Proc IEEE Int Conf On Neural Networks.Perth，1995：1942－1948.

［2］ Shi Y，Eberhart R C.A modified swarm optimizer［C］／／IEEE international conference of Evolutionary Computation.Anchorag，1998：125－129.

［3］ Bergh F，Engelbrecht A P.Cooperative learning in neural networks using particle swarm optimizers［J］.South African Computer Journal，2000，11（6）：84－90.

［4］ Voss M S，F(xiàn)eng X.A RMA model selection using particle swarm optimization and AIC criteria［C］／／15th Triennial World Congress.Barcelona：IFAC，2002：41－45.

［5］ Andrews P S.An investigation into mutation operators for particle swarm optimization［C］／／Proceeding of the 2006IEEE Congress on Evolutionary Compu－tation.Toronto，2006：1044－1051.

［6］ 李炳宇，蕭蘊詩，吳啟迪.一種基于微粒群算法求解約束優(yōu)化問題的混合算法［J］.控制與決策，2004，19（7）：804－807.

［7］ 于繁華，楊威，張利彪.基于模糊的多目標(biāo)粒子群優(yōu)化算法及應(yīng)用［J］.計算機仿真，2007，24（2）：53－156.

［8］ 柳寅，馬良.模糊蟻群算法及其在TSP中的應(yīng)用［J］.數(shù)學(xué)的實踐與認(rèn)識，2011，41（6）：150－154.

［9］ Takagi T，Sugeno M.Fuzzy identification of systems and its applications to modeling and control［J］.IEEE Trans Sys Man：Cybernetics，1985，15（10）：116－132.

［10］ Khaled B，F(xiàn)zouzi T.Genetic algorithm for the design of a class of fuzzy controllers：an alternative approach［J］.IEEE Trans：Fuzzy Systems，2000，8（4）：398－405.

［11］ 丁建梅，王可崇.基于MATLAB的模糊控制器控制規(guī)則優(yōu)化研究［J］.哈爾濱工業(yè)大學(xué)學(xué)報，2004，10（3）：45－50.

［12］ 馬良，朱剛，寧愛兵.螞蟻優(yōu)化算法［M］.北京：科學(xué)出版社，2008，190－194.