劉軍梅

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

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

DOI DOI： 10.11907/rjdk.162828

中圖分類號(hào)： TP312

文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào) 文章編號(hào)： 16727800（2017）002005904

0 引言

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

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

1 基本粒子群算法

在D維解空間內(nèi)選取一組初始粒子群，數(shù)量為m，初始化其速度Vi=（vi1，vi2，vi3...viD）和位置Xi=（xi1，xi2，xi3...xiD），其中i代表第i個(gè)微粒，選定適應(yīng)值函數(shù)FX，在粒子“飛行”過程中，通過迭代找到兩個(gè)極值：個(gè)體極值記為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ù)，常被稱作是學(xué)習(xí)因子；r1、r2是rand（）介于[0，1]之間的隨機(jī)數(shù)；t為種群當(dāng)前進(jìn)化代數(shù)。同時(shí)，粒子速度不能過大或過小，因此設(shè)置速度上限Vmax和速度下限Vmin，可知：

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

2 混沌映射

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

（1）Logistic映射。

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

（2）Tent映射。

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

（3）Sinusoidal映射。

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

3.1 優(yōu)化方法

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

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

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

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

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

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

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

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

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

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

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

4 算法仿真結(jié)果

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

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

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）測(cè)試結(jié)果如圖1所示。

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

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

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

5 結(jié)語

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

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

參考文獻(xiàn)：

[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].計(jì)算機(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].模式識(shí)別與人工智能，2006，19（2）：266270.

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

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

[12] 尤勇，王孫安，盛萬興.新型混沌優(yōu)化方法的研究及應(yīng)用[J].西安交通大學(xué)學(xué)報(bào)，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.

（責(zé)任編輯：孫 娟）