新型混沌粒子群混合優化算法

劉軍梅

摘要 為避免粒子群算法陷入局部最優、早熟收斂，提出了一種新型的混沌粒子群混合優化算法。利用混沌映射初值敏感性、遍歷性特點，隨機初始化一個粒子，并通過混沌映射得到多個粒子的初始值，改變初始粒子群的提取過程。利用混沌映射擴大初始粒子群，得到尋優粒子群，使得粒子群在搜索的過程中，種群數量變大，有利于全局尋優，而種群粒子多樣化，有利于跳出局部極值。經典的測試函數仿真表明，改進的粒子群算法極大提高了粒子群的尋優精度和尋優效率，增加了粒子的全局尋優能力，具有更為廣泛的應用場景。

關鍵詞 粒子群算法；混沌映射；初值敏感性；混合優化

DOI DOI： 10.11907/rjdk.162828

中圖分類號： TP312

文獻標識碼： A 文章編號 文章編號： 16727800（2017）002005904

0 引言

源于對鳥群捕食行為的研究，Eberhart博士和Kennedy博士于1995年提出一種新的進化計算技術，粒子群優化算法（PSO）[13]。在PSO 系統中，每個備選解被稱為一個“粒子”（Particle），多個粒子共存、合作尋優，每個粒子根據自身“經驗”和群體的最佳“經驗”在問題空間中向更好的位置“飛行”，搜索最優解[45]。在問題求解空間中使整個群體的運動實現有序演化過程，進而獲得空間最優解。

粒子群算法初期收斂速度快、規則簡單、實現容易，因此被廣泛應用于許多優化問題求解過程中，但同時后期易陷入早熟收斂、局部最優，因而有很大的改進空間。常見的粒子群優化方法有：①PSO算法參數改進，如調整慣性權重、收斂因子[6]；②拓補結構改進，如混合空間領域、環形拓補方法；③基于生物行為的改進，如Predator-Prey優化模型；④混合策略，如引入混沌技術、遺傳算法、梯度信息等。混沌是一種貌似隨機的運動，它出現在決定性動力學系統中，其本質是系統的長期行為對初始條件的敏感性，具有 遍歷性、初值敏感性、內隨機性等特點[78]。隨著混沌粒子群算法的優化，人們也越來越多地關注將二者結合在一起的改進算法[912]。本文利用混沌搜索這3個特性，在粒子群優化算法中引入混沌優化思想，能夠有效提高粒子群尋優能力，幫助其跳出局部極值，實現全局最優。

1 基本粒子群算法

在D維解空間內選取一組初始粒子群，數量為m，初始化其速度Vi=（vi1，vi2，vi3...viD）和位置Xi=（xi1，xi2，xi3...xiD），其中i代表第i個微粒，選定適應值函數FX，在粒子“飛行”過程中，通過迭代找到兩個極值：個體極值記為Pbest即Pi=（pi1，pi2，pi3...piD），全局極值記為Pgbest即式中，i=1，2，3....m；d=1，2，3...D；ω是慣性常數，可以通過調節其大小來控制算法的全局尋優能力和局部尋優能力；c1 、c2 是正常數，常被稱作是學習因子；r1、r2是rand（）介于[0，1]之間的隨機數；t為種群當前進化代數。同時，粒子速度不能過大或過小，因此設置速度上限Vmax和速度下限Vmin，可知：

粒子群在相應的解空間內，不斷地“飛行”，通過速度、位置更新公式，在迭代中更新其自身的歷史最優值和全局最優值，并通過不斷的對比與找尋，達到尋優目的[13]。

2 混沌映射

混沌現象是一種類似于隨機的過程，它在非線性動態系統中確定性出現，可以由十分簡單的確定性動力系統產生異常復雜的隨機行為，同時，具有非周期、不收斂、但有界、并對初始值極為敏感的特點，混沌序列是遍歷的，以下是幾種常見的混沌映射：

（1）Logistic映射。

式（5）中，μ為控制參數，當μ=4時，Logistic 映射將會處于完全混沌狀態。

（2）Tent映射。

Tent 映射結構簡單，具有很好的遍歷均勻性。

（3）Sinusoidal映射。

3 混沌粒子群混合優化算法

3.1 優化方法

在粒子群算法中引入混沌映射，提出一種新的混沌粒子群混合優化算法，以混沌序列初始化粒子群，改變粒子群的提取方法，同時利用混沌映射擴大種群數量，得到尋優粒子群，由混沌映射遍歷性和初始值敏感性可知，尋優粒子群盡可能地遍歷解空間內的所有狀態，粒子群的多樣性也會增加，可達到避免粒子群局部聚集狀態，幫助粒子群跳出局部極值，從而提高粒子群全局尋優能力，提升粒子群的尋優精度和尋優效率，使得粒子可以在短時間內收斂到全局最優；同時與慣性權重線性遞減策略相結合，使得粒子開始時在全局內進行尋優，找到目標范圍。隨著ω的減小，有利于局部尋優，加快了粒子群的尋優速度，提高了整體收斂精度。

將3種混沌映射即Logistic映射、Tent映射、Sinusoidal映射分別與粒子群算法相結合得出3種優化方法，即NLPSO、NTPSO、NSPSO方法。

3.2 優化算法流程

i代表第i個粒子（i=1，2，3...p）， j 代表維度（j=1，2，3...D），粒子最大速度為Vmax，最小速度為Vmin，Pbest、Pgbest分別代表粒子群個體歷史最優解和全局歷史最優解，以NLPSO為例：

（1）任意取一個粒子i，在解空間內其位置為x（i，j），速度為v（i，j）。隨機初始化i，使得x（i，j）=rand（1，1），v（i，j）=rand（1，1）。

（2）將粒子i的位置和速度，按照式（6）迭代m次，即得到m個初始粒子的位置向量和速度向量，其中速度大小要滿足式（3）、式（4）。

（3）將（2）選出的m個初始粒子，利用混沌變量的遍歷性，依舊按照式（6）進行迭代n次，得到尋優粒子群p，p=m×n，同時可得到它們的速度向量V=（v1，v2，v3...vp），位置向量X=（x1，x2，x3...xp）。

（4）設置優化過程中迭代的最大次數、優化精度、PSO算法和混沌映射的初始參數。本文中c1 =c2=2，μ= 4 ，計算粒子群初始適應度值，并保存得到的值和位置。

（5）將粒子群按照式（1）、式（2）進行更新，產生新的位置并計算適應值，將新的適應值與之前得到的值進行比較更新，保留其中粒子自身的歷史最優值Pbest和全局最優值Pgbest以及它們的位置。

（6）重復（5）達到最大迭代次數時轉（7）。

（7） 尋優停止，輸出全局歷史最優值和相應的最優位置。

4 算法仿真結果

4.1 經典測試函數

為了驗證混合優化算法的有效性，采用了4個經典的測試函數Griewank、Rastrigrin、Sphere和Schwefel，它們的表達式如下：

4.2 仿真結果

在本次仿真中，初始粒子群m=50，尋優粒子群p=500，迭代次數是500，解空間為D=10維，尋優精度Griewank是10-3、Rastrigin是100、Sphere是10-2、Schwefel是10-1，PSO代表基本粒子群算法，NLPSO代表優化的混沌粒子群算法。優化粒子群算法（NLPSO）和基本粒子群算法（PSO）測試結果如圖1所示。

由圖1可知，在4個經典函數的測試中，優化的混沌粒子群算法在收斂速度和收斂精度上都要明顯優于基本粒子群算法。為進一步驗證優化算法的有效性，對3種改進算法（NLPSO、NTPSO、NSPSO）分別進行實驗。3種算法在測試函數上運行50次，3種算法尋優的成功率、平均精度、平均迭代次數和基本粒子群算法（PSO）對比數據如表1所示。

鑒于r1、r2對粒子速度更新公式的影響，可以對其作出假設，在r1、r2引入混沌映射，使速度盡可能地遍歷到所有的值，可提高粒子的搜索范圍，從而提高搜索精度，即對r1、r2同樣施以混沌映射，可得出新的粒子群算法（NLRPSO）。這種粒子群算法（NLRPSO）和基本粒子群算法（PSO）測試結果如圖2所示。

由圖2可知，對r1、r2施以混沌映射時，其尋優效果尚不如基本粒子群算法，故這種方法將不再考慮，即改進的粒子群算法中將不再考慮將混沌映射引入到r1、r2中。

5 結語

本文針對粒子群算法易陷入局部極值、早熟收斂的問題，提出了改進的混沌粒子群混合優化算法。由仿真結果可知，改進的粒子群算法極大提高了收斂精度和尋優效率，但在收斂速度上影響不大，這是未來需要努力的方向。

改進的粒子群算法由于尋優粒子群的擴大，在資源調配中可以有效解決資源匱乏的問題，在發生地震、飛機墜落等災害時可以發揮極大作用。例如在發生地震時，需要尋找失蹤人口，此時，可用較少的尋人飛機，通過混沌映射得出多個虛擬飛機的位置，即本文中提出的尋優粒子群，進而達到利用較少的資源盡可能準確找到目標的目的，同時也極大提高了尋優精度和尋優效率，為災難中的人們爭取到更大的生存幾率。

參考文獻：

[1] KENNEDY J，EBERHART R C.Particle swarm optimization [C].Proc.IEEE Int.Conf.on Neural Networks.Perth，WA，Australia：IEEEService Center，1995：19421948.

[2] EBERHART R C，KENNEDY J.A new optimizer using particle swarm theory[C].Proceedings of the Sixth International Sjmposium on Micro Machine and Human Science.Nagoya，Japan，1995：3943，

[3] LOVBJERG M，RASMUSSEN T K，KRINK T.Hybrid particle swarm optimization with breeding and subpopulations[C].Proc.Genetic and Evolutionary Computation Conf.San Francisco：Morgan Kaufmann Publishers，2001：469476.

[4] 劉華鎣，林玉娥，張君施.基于混沌搜索解決早熟收斂的混合粒子群算法[J].計算機工程與應用，2006，42（13）：7779.

[5] S SURESH，P B SUJIT，A K RAO.Particle swarm optimization approach for multiobjective composite boxbeam design [J].Composite Structures （S02638223），2007，81（4）：598605.

[6] MAURICE CLERC.The swarm and the queen：towards a deterministic and adaptive particle swarm optimization [C].Proc.Congress on Evolutionary Computation.Washington DC：Springer，1999：19271930.

[7] AWAD ELGOHARY，A S ALRUZAIZA.Chaos and adaptive control in two prey，one predator system with nonlinear feedback[J].Chaos，Solitons and Fractals （S09600779），2007，34（2）：443453.

[8] B LIU，L WANG，YH JIN，et al.Improved particle swarm optimization combined with chaos[J].Chaos Solitons&Fractals （S09600779），2005，25（21）：12611271.

[9] 高尚，楊靜宇.混沌粒子群優化算法研究[J].模式識別與人工智能，2006，19（2）：266270.

[10] 孟紅記，鄭鵬，梅國暉，等.基于混沌序列的粒子群優化算法[J].控制與決策，2006，21（3）：263266.

[11] 陳國初，俞金壽，郭偉.兩群替代微粒群優化算法及其應用[J].華東理工大學學報：自然科學版，2005，31（6）：787791.

[12] 尤勇，王孫安，盛萬興.新型混沌優化方法的研究及應用[J].西安交通大學學報，2003，37（1）：6972.

[13] R KATHIRAVAN，R GANGULI.Strength design of composite beam using gradient and particle swarm optimization[J].Composite Structures，（S02638223），2007，81（4）：471479.

（責任編輯：孫 娟）