基于模糊粒子群算法的非線性函數優化

柳 寅， 馬 良， 黃 鈺

（上海理工大學管理學院 200093）

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

1 模糊粒子群算法

1.1 粒子群算法基本原理

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

傳統PSA的標準進化方程為

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

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

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

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

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

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

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

1.3 模糊粒子群算法流程

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

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

系統模糊規則采用的形式為

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

表1 模糊控制規則表Tab.1 Fuzzy rules table

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

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

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

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

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

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

經下式轉換為（fa，fb），其中fa，fb∈（0，1）.

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

其中，c∈［Outputmin，Outputmax］.

模糊粒子群算法流程：

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

步驟2 將粒子的pbest設置為當前位置，gbest設置為初始群體中最佳粒子的位置；

步驟3 判斷算法停止準則是否滿足，如果滿足，轉向步驟7，否則執行步驟4；

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

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

步驟5 更新所有粒子經歷過的最好位置，即全局極值gbest（如果可行粒子的目標函數值優于gbest的目標函數值，gbest設置為新位置）；

步驟6 判斷算法停止準則是否都滿足，如果滿足則轉步驟7，否則執行步驟4；

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

2 算例測試

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

算例1（Griewank函數）

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

圖3 Griewank函數圖像Fig.3 Image of function Griewank

算例2（Schaffer函數）

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

圖4 Schaffer函數圖像Fig.4 Image of function Schaffer

算例3（Hansen函數）

此函數局部極值點有760個.LINGO軟件得到的結果為12.354 7.Matlab內部函數所得到結果與初值有關，初值取得好，則可得到最優解，有不確定因素的存在［11］.遺傳算法100代內可得到最優解.

模糊粒子群算法可以得到全局最優值為176.541 793，并經多次反復運行，可找到全部最優解（－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函數圖像由圖5所示.

圖5 Hansen函數圖像Fig.5 Image of function Hansen

算例4（大海撈針問題）

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

圖6 算例4函數圖像Fig.6 Image of function 4

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

3 結束語

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

［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，Feng 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］ 李炳宇，蕭蘊詩，吳啟迪.一種基于微粒群算法求解約束優化問題的混合算法［J］.控制與決策，2004，19（7）：804－807.

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

［8］ 柳寅，馬良.模糊蟻群算法及其在TSP中的應用［J］.數學的實踐與認識，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，Fzouzi 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的模糊控制器控制規則優化研究［J］.哈爾濱工業大學學報，2004，10（3）：45－50.

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