新型混沌粒子群混合優(yōu)化算法

劉軍梅

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

關(guān)鍵詞 粒子群算法；混沌映射；初值敏感性；混合優(yōu)化

DOI DOI： 10.11907/rjdk.162828

中圖分類號： TP312

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

0 引言

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

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

1 基本粒子群算法

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

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

2 混沌映射

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

（1）Logistic映射。

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

（2）Tent映射。

Tent 映射結(jié)構(gòu)簡單，具有很好的遍歷均勻性。

（3）Sinusoidal映射。

3 混沌粒子群混合優(yōu)化算法

3.1 優(yōu)化方法

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

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

3.2 優(yōu)化算法流程

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

（1）任意取一個粒子i，在解空間內(nè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次，得到尋優(yōu)粒子群p，p=m×n，同時可得到它們的速度向量V=（v1，v2，v3...vp），位置向量X=（x1，x2，x3...xp）。

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

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

（6）重復（5）達到最大迭代次數(shù)時轉(zhuǎn)（7）。

（7） 尋優(yōu)停止，輸出全局歷史最優(yōu)值和相應(yīng)的最優(yōu)位置。

4 算法仿真結(jié)果

4.1 經(jīng)典測試函數(shù)

為了驗證混合優(yōu)化算法的有效性，采用了4個經(jīng)典的測試函數(shù)Griewank、Rastrigrin、Sphere和Schwefel，它們的表達式如下：

4.2 仿真結(jié)果

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

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

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

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

5 結(jié)語

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

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

參考文獻：

[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].計算機工程與應(yīng)用，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] 高尚，楊靜宇.混沌粒子群優(yōu)化算法研究[J].模式識別與人工智能，2006，19（2）：266270.

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

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

[12] 尤勇，王孫安，盛萬興.新型混沌優(yōu)化方法的研究及應(yīng)用[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.

（責任編輯：孫 娟）