一種基于成對(duì)粒子的粒子群優(yōu)化算法

汪在榮， 張文鳳

（1.內(nèi)江師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院，四川內(nèi)江641110； 2.內(nèi)江師范學(xué)院四川省數(shù)值仿真重點(diǎn)實(shí)驗(yàn)室，四川內(nèi)江641110；3.重慶大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，重慶401331）

函數(shù)最值求解問題是一個(gè)傳統(tǒng)問題，對(duì)于函數(shù)最值求解的方法大致可以分為兩大類.第一類是傳統(tǒng)的數(shù)學(xué)分析方法，該類方法建立在數(shù)學(xué)分析和實(shí)變函數(shù)理論的基礎(chǔ)上，通過分析函數(shù)性質(zhì)求解，其解具有精確性等特征，然而對(duì)于較為復(fù)雜的函數(shù)，特別是無法顯示表達(dá)以及可微性、連續(xù)性較差的函數(shù)，分析其數(shù)學(xué)特性往往十分復(fù)雜，使用分析法求解其最值的解是十分困難甚至無法進(jìn)行的.第二種方法是在計(jì)算機(jī)技術(shù)高速發(fā)展的基礎(chǔ)上建立的通過模擬計(jì)算求解最大值的方法，該方法拋開對(duì)于函數(shù)的特殊性質(zhì)的要求，直接通過函數(shù)具體值的比較來尋找函數(shù)最大值.統(tǒng)計(jì)模擬方法求解函數(shù)最值可以解決傳統(tǒng)分析方法無法解決的問題，但是求解過程計(jì)算量大，對(duì)于較為復(fù)雜的問題如果不進(jìn)行算法的優(yōu)化，即使大型計(jì)算機(jī)也難以得到要求精度的解，所以優(yōu)化算法是現(xiàn)在最優(yōu)值問題研究中的一個(gè)重要方向.

粒子群算法［1-15］是一種較為新穎的智能優(yōu)化算法，1995年由文獻(xiàn)［1］提出，最初是一種模擬鳥群和魚群的群體智能算法，目標(biāo)為搜索連續(xù)空間中的最優(yōu)值.早期的粒子群算法存在著易發(fā)散、有趨同性等缺點(diǎn)，為了改進(jìn)這些缺點(diǎn)，很多學(xué)者對(duì)粒子群算法進(jìn)行了改進(jìn).文獻(xiàn)［2-3］在每次速度迭代時(shí)為上一代速度乘以一個(gè)因子，稱為慣性權(quán)重.由于動(dòng)態(tài)慣性在復(fù)雜問題中容易使原算法陷入局部最優(yōu)解中，又提出了模糊慣性權(quán)重法，以自適應(yīng)地改變慣性權(quán)重.不過由于參數(shù)設(shè)定困難，所以尚缺乏大量使用.Clerc等［4］提出了壓縮因子法來保證算法的收斂性，壓縮因子本質(zhì)上同慣性權(quán)重是等價(jià)的.同時(shí)，文獻(xiàn)［5］從進(jìn)化算法的角度出發(fā)，提出了結(jié)合進(jìn)化算法的粒子群算法，如選擇法、繁殖法等.同時(shí)從粒子通訊的角度，Zhao等［9］提出了基于粒子的空間位置劃分的方案，有效地提高了PSO算法的性能.而文獻(xiàn)［6］則測(cè)試了不同的鄰域拓?fù)鋵?duì)于PSO算法的影響，發(fā)現(xiàn)根據(jù)不同問題有著不同的最優(yōu)鄰域拓?fù)淠Ｊ?為了避免算法陷入早熟，文獻(xiàn)［7-8］將混沌思想引入粒子群算法，將混沌空間映射到解空間，利用混沌系統(tǒng)的遍歷性克服粒子群算法的早熟缺陷.從混合算法角度，許多學(xué)者嘗試將粒子群算法與局部搜索算法結(jié)合，以改善粒子群算法的收斂速度和搜索精度.文獻(xiàn)［9］嘗試將算法分代，在每一代中重組粒子結(jié)構(gòu)以搜索局部最優(yōu)解.文獻(xiàn)［10］則結(jié)合Nelder-Mead單純形法對(duì)粒子群算法進(jìn)行改進(jìn)，通過Nelder-Mead方法計(jì)算局部最優(yōu).過去的算法確實(shí)能夠提高粒子群算法的收斂速度與收斂精度，然而這些算法容易落入局部最優(yōu)的陷阱.

本文給出一種基于成對(duì)粒子的混合粒子群算法，該算法通過調(diào)整拓?fù)浣Y(jié)構(gòu)改善粒子群算法的遍歷性，同時(shí)通過構(gòu)建和原粒子對(duì)應(yīng)的具有隨機(jī)梯度運(yùn)動(dòng)性質(zhì)的成對(duì)粒子，在全局搜索的同時(shí)，較精確地搜索局部最優(yōu)值，一方面加強(qiáng)了粒子群算法的全局收斂速度和精度，另一方面克服了粒子群算法容易陷入局部最優(yōu)的缺陷，并以算例證明了該算法的優(yōu)越性.

1 粒子群算法簡(jiǎn)介

1.1 粒子群算法原理與標(biāo)準(zhǔn)PSO 粒子群算法基本思想是在參數(shù)空間中隨機(jī)播下一定量的點(diǎn)作為粒子，每個(gè)點(diǎn)根據(jù)函數(shù)取值由適應(yīng)函數(shù)映射得到一個(gè)適應(yīng)值，粒子在空間中根據(jù)自己和其他粒子的適應(yīng)值按照一定方向運(yùn)動(dòng).通過整個(gè)空間中粒子運(yùn)動(dòng)的迭代，求出空間中最優(yōu)值.

最早提出的標(biāo)準(zhǔn)PSO算法，其數(shù)學(xué)表達(dá)如下：在一個(gè)n維搜索空間中，初始化m個(gè)粒子組成的點(diǎn)集｛x1，x2，…，xm｝，其中第 i個(gè)粒子的位置為（xi1，xi2，…，xin），其初始速度為0.計(jì)算出每個(gè)粒子的函數(shù)取值，設(shè)為向量p，并得到極值pg.根據(jù)p和pg以及第t代的速度通過迭代得到第t+1代粒子速度，并計(jì)算出粒子當(dāng)前位置，其中

m 為種群規(guī)模，t為當(dāng)代進(jìn)化代數(shù)，r1、r2為［0，1］的實(shí)數(shù)，c1、c2為加速常數(shù).為使速度不致過大，設(shè)置速度上限 Vmax，當(dāng)｜v｜＞ Vmax時(shí)，令

1.2 改進(jìn)粒子群算法PSON

1.2.1 慣性權(quán)重與收縮因子 為了加強(qiáng)對(duì)于PSO算法尋優(yōu)軌跡的控制以優(yōu)化PSO算法，在速度迭代式中加入一個(gè)慣性權(quán)重，即將速度迭代公式變?yōu)?/p>

此處的權(quán)重w（t）可以控制上一代速度對(duì)當(dāng)前速度的影響，根據(jù)試驗(yàn)發(fā)現(xiàn)w（t）為動(dòng)態(tài)時(shí)能夠取得較好的尋優(yōu)效果.一個(gè)常用的準(zhǔn)則為線性遞減權(quán)值，即

其中的參數(shù)常用取值為 wini＝0.9，wend＝0.4.

為保證PSO算法的收斂性，引入了收縮因子.設(shè)χ（·）為一個(gè)壓縮算子，在不考慮慣性權(quán)重的基礎(chǔ)上，迭代公式為

1.2.2 粒子通訊結(jié)構(gòu) 上述的粒子群算法，每個(gè)粒子都與其他所有粒子建立通訊，并向自身最優(yōu)值以及全局最優(yōu)值加速，因而該方法存在易陷入局部最優(yōu)解的問題，導(dǎo)致算法過早收斂，因此很多學(xué)者提出了局部粒子通訊方式與速度迭代公式.

對(duì)于第i個(gè)粒子，假設(shè)它只與周圍的mi個(gè)粒子通訊為第i個(gè)粒子的第k個(gè)通訊鄰居的第t步時(shí)的最優(yōu)值位置表示粒子i自己在前t步時(shí)的最優(yōu)位置，令

由（3）式可以看出，第i個(gè)粒子在第t+1步的速度取決于第t步時(shí)本身和其鄰域內(nèi)所有粒子的歷史最優(yōu)位置.該算法稱為PSON算法.

1.2.3 粒子群算法的收斂性 本文采取的壓縮因子粒子群算法中（w+1-φ）2-4w等價(jià)于（χ+1-χφ）2-4x，而本文中使用的參數(shù) φ ＝ 4.2，χ＝，滿足 Δ ＝ （χ+1- χφ）2-4χ＞0，故而本文使用的算法在全局通訊模式下是收斂的.

2 隨機(jī)梯度粒子群算法

隨機(jī)梯度搜索法能夠有力地克服全局PSO算法易于過早陷入局部最優(yōu)值的缺點(diǎn)，以及局部PSO局部收斂速度慢的缺點(diǎn)，在參數(shù)設(shè)置得當(dāng)?shù)那闆r，隨機(jī)梯度搜索能夠在局部收斂.同時(shí)，與粒子群算法內(nèi)核易于結(jié)合，隨機(jī)梯度算法可以看作單個(gè)粒子的一種隨機(jī)搜索運(yùn)動(dòng)，而粒子群算法則是根據(jù)粒子間的通訊實(shí)現(xiàn)群智能來進(jìn)行搜索，粒子群中的單個(gè)粒子沒有搜索能力.如果將若干個(gè)這樣運(yùn)動(dòng)的隨機(jī)粒子加入群智能，賦予粒子群算法中的單個(gè)粒子搜索能力，則既可以防止粒子群算法的早熟，增強(qiáng)粒子群算法后期的收斂能力，又能有效利用群智能使搜索速度優(yōu)于常規(guī)隨機(jī)梯度算法.

2.1 PSON與隨機(jī)梯度搜索的伴生粒子 PSON算法的本質(zhì)是服從（3）式給出的速度迭代公式的粒子群算法，令

令其中加速權(quán)重ck與 k無關(guān)，均相等為 c，則 φk～ U［0，c］.

由（4）式不難發(fā)現(xiàn)，粒子對(duì)于自身最優(yōu)值附近的局部最優(yōu)的搜索較為缺乏，于是在此提出伴生粒子的概念.對(duì)初始化的粒子i，引入一個(gè)與之對(duì)應(yīng)的伴生粒子i′，i′具有隨機(jī)梯度粒子的行為模式，具體數(shù)學(xué)描述為：設(shè)伴生粒子i′的位置為，其中t*表示i′的迭代代數(shù)，產(chǎn)生一個(gè)隨機(jī)的n維單位向量ζ（t*），則在方向 ζ（t*）上的梯度可以表示為

選擇合適的參數(shù)序列α（t*）和β（t*），可以使伴生粒子在一個(gè)小區(qū)域內(nèi)快速收斂到局部最優(yōu)值.在粒子運(yùn)動(dòng)中，每次迭代均考慮粒子與伴生粒子的運(yùn)動(dòng)，粒子i在前t步的最優(yōu)值取值為其本身與伴生粒子前t步的最優(yōu)值中的較大值，最優(yōu)位置為最優(yōu)值的對(duì)應(yīng)位置.

2.2 伴生粒子的跳躍條件 伴生粒子i′的目的是找出粒子i某個(gè)位置附近的局部最大值，故而當(dāng)粒子i的隨機(jī)化初始位置給定后，i′也在同一位置被初始化.之后隨著粒子的不斷運(yùn)動(dòng)，伴生粒子在一定情況下應(yīng)當(dāng)能夠移動(dòng)到粒子所在的新的位置進(jìn)行搜索，并且重新初始化伴生粒子的相關(guān)參數(shù).本文稱伴生粒子的該行為為跳躍，并給出伴生粒子的跳躍條件.

設(shè)h為x的適應(yīng)函數(shù)，它的值表示粒子在位置x的尋優(yōu)表現(xiàn)，在一個(gè)求函數(shù)f最大值問題中，可以簡(jiǎn)單定義h?f.

2）收斂跳躍.設(shè)伴生粒子i′在經(jīng)過t*次迭代后，已經(jīng)滿足收斂條件在位置xi′附近收斂，而此時(shí)全局算法尚未收斂，則令伴生粒子跳躍至粒子i所處位置，即令，并初始化t*＝0，使伴生粒子在附近搜索局部最適值，以規(guī)避伴生粒子在某個(gè)局部收斂點(diǎn)進(jìn)行無意義的迭代.

3）偶然跳躍.即使在1）和2）的條件都不滿足的情況，也設(shè)伴生粒子i′有小概率p跳躍至粒子i的附近搜索粒子i的局部最適值，以增大搜索空間，避免整個(gè)算法落入一個(gè)局部最優(yōu)陷阱.概率p可以是一個(gè)給定的參數(shù)，也可以是根據(jù)前t-1步最適值h（t-1）imax和粒子i在第t步適應(yīng)值進(jìn)行加權(quán)的參數(shù)，本文因?yàn)槭菍?duì)該算法的初探研究，主要研究概率p為一個(gè)定值的情況.

本文經(jīng)過實(shí)驗(yàn)證明，使用常規(guī)跳躍策略容易使算法落入早熟陷阱，本文程序采用的是結(jié)合收斂跳躍和偶然跳躍兩種策略原則的跳躍，同時(shí)經(jīng)過實(shí)驗(yàn)發(fā)現(xiàn)，跳躍時(shí)伴生粒子i′直接跳躍至粒子i的策略并不是最優(yōu)，而是跳躍至粒子i附近一個(gè)隨機(jī)地點(diǎn)的策略較優(yōu).

在后續(xù)算例中，伴生粒子i′跳躍的隨機(jī)性由一個(gè)正態(tài)分布給出，正態(tài)分布的方差由對(duì)應(yīng)粒子i附近的粒子數(shù)加權(quán)，粒子i附近的粒子數(shù)越多，則說明粒子對(duì)該區(qū)域的搜索越密集，則伴生粒子跳躍隨機(jī)項(xiàng)的方差越大，伴生粒子有更大的可能在相對(duì)遠(yuǎn)一些的區(qū)域進(jìn)行搜索.

2.3 算法流程

3 算例分析與測(cè)試

3.1 Ackley函數(shù)的極大值 Ackley函數(shù)由圖1所示，其最大值在（0，0）處取得.由圖1易見該函數(shù)有很多局部最大值.

圖1 Ackley函數(shù)圖Fig.1 The image of Ackley function

使用隨機(jī)梯度粒子群算法進(jìn)行91次迭代，就找到了位于（0，0）的最優(yōu)值，誤差范圍不超過1 ×10-17.

3.2 Rastrigin函數(shù)最小值搜索 為將最小值問題轉(zhuǎn)化為最大值問題，將Rastrigin函數(shù)的函數(shù)值取相反數(shù)得到一個(gè)新的函數(shù)，在下文中為求簡(jiǎn)潔，在不引起混淆的情況下將新得的這個(gè)函數(shù)也稱為Rastrigin函數(shù)，表達(dá)式為

其中n為x的維數(shù)，該函數(shù)的全局最大值在（0，0）處取得.

二維Rastrigin函數(shù)的圖像如圖2所示，已知其最大值在（0，0）處取得.Rastrigin由于具有非常多的局部最大值，所以對(duì)模擬退火算法等具有很強(qiáng)的欺詐性.隨機(jī)梯度粒子群算法通過597次迭代求解出了Rastrigin函數(shù)的最大值點(diǎn)（0，0），誤差不超過1 ×10-10.

3.3 Schaffer函數(shù)最大值搜索 Schaffer是一個(gè)檢測(cè)搜索算法常用的函數(shù)：

其中χ是一個(gè)向量.

圖2 二維Rastrigin函數(shù)圖像Fig.2 The image of two-dimensional Rastrigin function

二維Schaffer函數(shù)圖像如圖3所示，其最大值在（0，0）處取得，最大值為1.而在其最大值外圍一周的峰值上，局部最大值接近0.99，同時(shí)其最大值附近峰值區(qū)域較小，而局部最大值的環(huán)形區(qū)域較大，普通PSO和進(jìn)化算法非常容易落入環(huán)形區(qū)域陷阱，得到一個(gè)局部最大值而錯(cuò)過全局最大值.使用本文提出的隨機(jī)梯度粒子群算法通過978次迭代得到了正確的最大值，誤差不超過1×10-9.

圖3 二維Schaffer函數(shù)圖像Fig.3 The image of two-dimensional Schaffer function

圖4 為在搜索Schaffer函數(shù)最大值過程中，某個(gè)伴生粒子的運(yùn)動(dòng)軌跡.圖4（a）為該伴生粒子運(yùn)動(dòng)的完全軌跡，為了更清晰地看出伴生粒子的運(yùn)動(dòng)軌跡與作用，圖4（b）表示該伴生粒子最后200次運(yùn)動(dòng)的軌跡，圖4（c）為該伴生粒子的運(yùn)動(dòng)趨勢(shì).

由圖4可以看出，伴生粒子不容易陷于局部最大值處，觀察圖4（b）可以看到，當(dāng)伴生粒子陷入環(huán)狀極大值陷阱后，它能夠跳出局部最大值在附近進(jìn)行搜索，從而搜索到全局最大值.

圖4 Schaffer函數(shù)搜索伴生粒子運(yùn)動(dòng)圖像Fig.4 The motion image of associated particles searched by Schaffer function

3.4 Griewank函數(shù)最大值搜索 Griewank函數(shù)是一種連續(xù)的復(fù)雜函數(shù)，二維Griewank函數(shù)表達(dá)式為

其中x是一個(gè)向量.

二維Griewank函數(shù)圖像如圖5所示，其最大值在（0，0）處取得.可以看出Griewank函數(shù)有多個(gè)局部最大值，一般搜索算法容易陷入局部最大值中.使用隨機(jī)梯度粒子群算法在第577次迭代時(shí)已經(jīng)收斂到（0，0）處的最大值，誤差不超過1×10-9.

4 算法對(duì)比研究

本文通過重復(fù)模擬試驗(yàn)三維Schaffer函數(shù)試驗(yàn)，得到各算法性能（見表1），其中隨機(jī)梯度粒子群算法模擬試驗(yàn)8次，27個(gè)粒子的PSON算法模擬試驗(yàn)12次，54個(gè)粒子的PSON算法模擬試驗(yàn)8次，PSO算法模擬試驗(yàn)10次，隨機(jī)梯度算法模擬試驗(yàn)2 000次.各個(gè)算法的粒子初始位置均隨機(jī)設(shè)置為｛（x，y，z）｜-10 ＜ x＜10，-10 ＜ y＜10，-10 ＜ z＜10｝，服從均勻分布的隨機(jī)數(shù).

圖5 二維Griewank函數(shù)圖像Fig.5 The image of two-dimensional Griewank function

表1 三維Schaffer函數(shù)各算法搜索性能表Tab.1 Search performance tables for each algorithm of three dimensional Schaffer function

表1表明，隨機(jī)梯度粒子群算法在各項(xiàng)性能上大幅優(yōu)于PSON算法、標(biāo)準(zhǔn)PSO算法以及較為簡(jiǎn)單的隨機(jī)梯度算法.對(duì)于復(fù)雜問題，單純?cè)黾恿Ｗ尤核惴ǖ牧Ｗ訑?shù)并不能提升算法的尋優(yōu)效果，反而會(huì)增加搜索時(shí)間成本，同時(shí)，對(duì)于一些復(fù)雜問題局部型PSO算法難以收斂，這不僅影響搜索的正確率，更會(huì)導(dǎo)致實(shí)踐中整個(gè)系統(tǒng)問題處理的延誤.如表1所示，如果加上算法未收斂時(shí)的時(shí)間進(jìn)行平均，則其他算法的平均用時(shí)會(huì)大大超過隨機(jī)梯度粒子群算法.

試驗(yàn)表明，隨機(jī)梯度粒子群算法是一種效果良好的算法，有很好的應(yīng)用前景.