潘允敬

（廈門(mén)海合達(dá)電子信息股份有限公司，福建 廈門(mén)361009）

0 引 言

隨著時(shí)代發(fā)展，計(jì)算理論愈發(fā)復(fù)雜化，待優(yōu)化問(wèn)題逐漸多樣化.傳統(tǒng)的優(yōu)化方法不能滿足現(xiàn)代工業(yè)科學(xué)等領(lǐng)域的需求，遇到的問(wèn)題也不只是單純的凸優(yōu)化問(wèn)題.研究者為尋求更好的優(yōu)化技術(shù)而著眼于群智能優(yōu)化方法的研究.群智能算法是一種模仿自然生命演化方式，從而進(jìn)行抽象為數(shù)學(xué)模型的一種方法，例如模仿螞蟻覓食的蟻群算法[1]和模擬鳥(niǎo)類(lèi)覓食的粒子群優(yōu)化算法[2]，借鑒神經(jīng)遺傳方面進(jìn)化知識(shí)抽象的遺傳算法[3]，簡(jiǎn)化變異方式提出的差分進(jìn)化算法[4]，以及近年來(lái)提出的比較經(jīng)典的螢火蟲(chóng)算法以及果蠅優(yōu)化算法[5-6].這類(lèi)算法具有強(qiáng)大的并行運(yùn)算與獨(dú)特的自組織信息交流方式，在一些非線性、多峰值問(wèn)題上，具有良好的分布優(yōu)化性能.

粒子群算法自提出以來(lái)得到廣泛關(guān)注，研究者從多種角度，以不同的方式對(duì)其進(jìn)行改進(jìn)以使其可以應(yīng)對(duì)更多問(wèn)題.王碧等[7]以增加粒子群迭代更新中的探索能力為主，提出一種返巢策略，在更改原始粒子群學(xué)習(xí)因子的背景下，新的更新策略有效緩解了粒子群后期開(kāi)發(fā)能力不足的劣勢(shì).群智能算法中利用混沌系統(tǒng)進(jìn)行算法位置初始化操作比較常見(jiàn)，目的是為了保證初始化種群隨機(jī)分布不會(huì)過(guò)于單一.文獻(xiàn)[8]中引入混沌系統(tǒng)操作對(duì)粒子群進(jìn)行更改，不同于傳統(tǒng)的初始化操作，該改進(jìn)算法是在算法進(jìn)化過(guò)程中以一種交替轉(zhuǎn)換的方式進(jìn)行狀態(tài)的牽引，整體種群在一種動(dòng)態(tài)序列中不斷進(jìn)行更新變化的.算法進(jìn)化后期粒子間差異逐漸降低，針對(duì)這種缺陷，文獻(xiàn)[9]中判斷進(jìn)化后期最優(yōu)解不再更新時(shí)，利用萊維飛行的操作進(jìn)行局部空間之外的搜索，發(fā)現(xiàn)這種方式可以有效避免局部最優(yōu)現(xiàn)象.生物進(jìn)化過(guò)程中個(gè)體的變異有可能變得更好也有可能變得更壞，在粒子群中如何以變異的方法控制算法向好的方向進(jìn)化？文獻(xiàn)[10]中分析粒子群收斂點(diǎn)，以迭代過(guò)程中最佳位置為基準(zhǔn)進(jìn)行高斯擾動(dòng)，文獻(xiàn)[11-12]分別給定不同的變異概率進(jìn)行變異控制.文獻(xiàn)[12-14]都用到了變異的方式，不過(guò)采用的變異方式都不同.除變異之外，利用設(shè)計(jì)的精英學(xué)習(xí)方法或者自定義搜索的空間劃分模式結(jié)合改進(jìn)算法，都取得不錯(cuò)的效果.

文章在前人的研究基礎(chǔ)之上，研究粒子群進(jìn)化過(guò)程中，如何進(jìn)行種群變異，才可更好地在進(jìn)化后期分化種群聚集性.利用分組變異的方式，在粒子群進(jìn)化過(guò)程中盡可能進(jìn)行解空間搜索.在算法后期，種群多樣性喪失難以避免，利用反向認(rèn)知與學(xué)習(xí)的方式可有效跳出循環(huán).

1 粒子群算法

現(xiàn)在采用的一般粒子群進(jìn)化公式如公式（1）、公式（2）所示，其中v表示第i個(gè)個(gè)體的速度，w為第 t代的學(xué)習(xí)權(quán)重，c1、c2表示學(xué)習(xí)因子，r1、r2都是分布在（0,1）之間的隨機(jī)數(shù).pbest與gbest分別記錄第t代粒子群算法搜索得到的個(gè)體最優(yōu)位置與全局最優(yōu)位置.根據(jù)公式求出的速度，每個(gè)粒子個(gè)體利用公式進(jìn)行位置遷移.

從進(jìn)化公式可以看出每個(gè)粒子都具有自己的進(jìn)化軌跡，通過(guò)相互協(xié)作的方式在解空間中迭代進(jìn)行搜索.高度的自組織并行搜索方式是粒子群獨(dú)特優(yōu)勢(shì).

2 分組變異與反向進(jìn)化的粒子群算法

2.1 基本思想描述

根據(jù)粒子群算法的進(jìn)化公式可知，種群之間的粒子群通過(guò)信息共享，各個(gè)個(gè)體利用自身保留的最佳位置與當(dāng)代全局最佳位置學(xué)習(xí)，從而達(dá)到全局最優(yōu)解或者全局近似最優(yōu)解.在有限空間的計(jì)算方式下，在復(fù)雜問(wèn)題上往往沒(méi)有一個(gè)完美的方法可以保證最終得到的解是全局最優(yōu)解.因此需要在相同的實(shí)驗(yàn)環(huán)境中得到精度相對(duì)較高的近似解.

為了提升求解問(wèn)題最終解的質(zhì)量，采用分組變異的方式，這種方式不同于傳統(tǒng)的變異方式，不是單純的在種群進(jìn)化得到的解不更新時(shí)，對(duì)種群中的某一個(gè)個(gè)體或者一部分個(gè)體進(jìn)行隨機(jī)擾動(dòng)，也不是針對(duì)gbest所在位置進(jìn)行擾動(dòng).單純的對(duì)最優(yōu)位置進(jìn)行變異操作，其原理是牽引種群向當(dāng)前停滯時(shí)的全局最優(yōu)解的某一個(gè)鄰域進(jìn)行遷移，重新進(jìn)行搜索，一定程度上是可以擴(kuò)大搜索范圍，但是在本質(zhì)上沒(méi)有進(jìn)行整體空間的遍歷.種群搜索停滯，說(shuō)明其整體陷入局部環(huán)境，在多峰問(wèn)題中種群停滯很容易出現(xiàn)，進(jìn)行幾次迭代之后沒(méi)有新解的出現(xiàn)，可以認(rèn)為停滯現(xiàn)象出現(xiàn)，利用有效的方式進(jìn)行改善這種現(xiàn)象，可以增大探索到更優(yōu)解的可能.

采用反向進(jìn)化的方式，在算法更新多次沒(méi)有新解出現(xiàn)，則向最優(yōu)位置的反方位置進(jìn)化，可增大尋找全局優(yōu)化解的概率.

2.2 分組變異

將種群分為N個(gè)組，每個(gè)小組采用不同的變異算子進(jìn)行變異，其變異概率p采取遞減方式，如公式（3）所示，隨著迭代次數(shù)的增加，變異概率線性遞減.公式（4）中δ為高斯變異算子.算法執(zhí)行初，為保證盡可能的在解空間內(nèi)遍歷采用較大的變異概率，隨著迭代的進(jìn)行最終要趨于收斂，因此變異概率幅度逐漸趨于0.

根據(jù)分組的不同變異算子的取值是不同的，初始隨機(jī)生成的高斯變異數(shù)會(huì)隨著種群更新而發(fā)生變化，具體變化按公式進(jìn)行.

分組變異執(zhí)行流程如下：

step1.輸入適應(yīng)度值，種群分組數(shù)以及變異概率的最大最小值；

step2.將輸入的種群按適應(yīng)度f(wàn)itness排序；

step3.將排好序的個(gè)體劃分為N個(gè)小組；

step4.產(chǎn)生N組高斯隨機(jī)數(shù)；

step5.根據(jù)公式更新變異算子；

step6.對(duì)于每一個(gè)小組內(nèi)的個(gè)體按照公式進(jìn)行變異操作；

step7.將變異后的個(gè)體適應(yīng)值與原適應(yīng)值比較，若優(yōu)于則選擇變異后的個(gè)體，否則淘汰.

step8.返回變異后生成的種群位置.

2.3 反向進(jìn)化

由于算法進(jìn)化過(guò)程時(shí)一個(gè)整體趨向極值點(diǎn)的過(guò)程，在進(jìn)化的過(guò)程中采用反向進(jìn)化策略影響收斂速度，甚至導(dǎo)致在有限范圍內(nèi)求解精度更低.因此反向進(jìn)化不會(huì)伴隨整個(gè)算法的進(jìn)程，只在判斷種群進(jìn)化停滯時(shí)采用反向進(jìn)化方式尋找突破局部限制的位置.

反向進(jìn)化策略具體執(zhí)行公式（6），其中l(wèi)ow與up分別是預(yù)求解問(wèn)題的空間下界與上界.執(zhí)行過(guò)程中越界的粒子群一般采用上下限賦值的方法，這種方法易出現(xiàn)多個(gè)個(gè)體聚攏于邊界的問(wèn)題，新算法處理越界粒子采用空間映射的方式.

假設(shè)粒子越界執(zhí)行公式（7）.這種方式在一定程度上也保持了搜索過(guò)程中種群的靈活性.對(duì)于反向?qū)W習(xí)執(zhí)行選擇是：當(dāng)算法連續(xù)達(dá)到總迭代次數(shù)的1/20次沒(méi)有更新最優(yōu)解，則認(rèn)定算法陷入局部最優(yōu)解范圍，采用反向?qū)W習(xí)，一直搜索到更新新解或者算法執(zhí)行終止為止.

綜上所述，新算法的偽代碼如下：

1）初始化種群規(guī)模：Maxsize、維度Dim、迭代次數(shù)T;

2）求出初始各個(gè)個(gè)體的適應(yīng)度；

3） While t＜T

4） For i＜Maxsize

5） For d＜Dim

6） 執(zhí)行公式（1）（2）;

7） End

8）End

9）根據(jù)變異概率，進(jìn)行分組變異；

10）記錄全局最優(yōu)解gbest的值;

11） If gbest（t+1）=gbest（t）

12） Record++;

13） End

14） If Record＞=T/20

15） 利用反向進(jìn)化中公式生成反向解；搜索的新解更優(yōu)則進(jìn)行位置替換；

16） End

17）End

18） Return min（f（x））;

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)設(shè)計(jì)

設(shè)置新改進(jìn)的算法與原算法分別在4組測(cè)試函數(shù)上進(jìn)行性能比較，具體測(cè)試函數(shù)信息如表1所示，分別在30維與50維的條件下進(jìn)行算法對(duì)比.算法參數(shù)設(shè)定為：最大迭代次數(shù)：1000、種群規(guī)模：20.

表1 測(cè)試函數(shù)表

3.2 實(shí)驗(yàn)結(jié)果

通過(guò)在30維與50維的條件下，對(duì)粒子群算法與改進(jìn)后的分組變異與反向進(jìn)化的粒子群算法進(jìn)行橫向比較，算法的迭代過(guò)程見(jiàn)圖1（其中為方便觀察進(jìn)化曲線，對(duì)數(shù)據(jù)用LOG10進(jìn)行處理）.由圖1可以看出新的改進(jìn)算法在4種測(cè)試函數(shù)上都具有更好的尋優(yōu)精度.50維度的時(shí)候算法的搜索精度明顯更低，這是因?yàn)殡S著維度上升，局部陷阱越來(lái)越多.進(jìn)化曲線變化說(shuō)明，在算法迭代后期新算法可以一定程度保證算法跳離局部最優(yōu)值點(diǎn)，開(kāi)辟新的搜索空間.

表2 實(shí)驗(yàn)結(jié)果對(duì)比

表2中是新算法與粒子群算法在30維的條件下，進(jìn)行優(yōu)化4個(gè)函數(shù)的是實(shí)驗(yàn)結(jié)果，給出獨(dú)立運(yùn)行100次的平均數(shù)據(jù).表2中的各項(xiàng)評(píng)定指標(biāo)Min、Max、Mean、Std、Time 分別表示獨(dú)立運(yùn)行算法100次后取得的最小值、最大值、均值和標(biāo)準(zhǔn)差以及算法平均運(yùn)行1次花費(fèi)的時(shí)間.算法對(duì)比的指標(biāo)分別用：迭代范圍內(nèi)的最小值、最大值、均值以及判斷算法穩(wěn)定程度的標(biāo)準(zhǔn)差，后面列出平均運(yùn)行時(shí)間.

從表2中得出，新算法在平均運(yùn)行時(shí)間上比原來(lái)的粒子群算法都要高，這是因?yàn)?，新算法中增加的變異機(jī)制與反向生成解方法，在進(jìn)行判斷運(yùn)行時(shí)需要花費(fèi)運(yùn)行時(shí)間，雖然運(yùn)行時(shí)間有所增加，但都在一個(gè)數(shù)量級(jí)上，是可以接受的.

針對(duì)單峰函數(shù)F1，保證較快的收斂速度的同時(shí)，新算法平均精度高于粒子群8個(gè)量度點(diǎn).F2雖然是一種單峰函數(shù)，但該函數(shù)求解精度一直不高，文中提出算法雖沒(méi)有以倍數(shù)級(jí)提升求解精度，但在最終的解質(zhì)量上還是優(yōu)于原算法.F3與F4都是多峰問(wèn)題，新算法在求解精度上分別提高5、6個(gè)精度點(diǎn).這可以很好論證新改進(jìn)的算法在解空間內(nèi)具有好的搜索性能，可以一定程度上避免局部最優(yōu).

4 結(jié) 論

文章研究了粒子群算法在求解較高維優(yōu)化問(wèn)題時(shí)出現(xiàn)的早熟現(xiàn)象，引入分組變異的方式，使粒子群進(jìn)化過(guò)程中可以在保持種群多樣性的同時(shí)有針對(duì)性的遍歷解空間.進(jìn)化后期種群共享信息不足時(shí)，采用反向進(jìn)化的操作進(jìn)行跳出局部環(huán)境操作.經(jīng)過(guò)對(duì)4個(gè)高維函數(shù)的測(cè)試，證明新提出的算法在收斂速度與優(yōu)化精度上都具有更高的性能.是利用最優(yōu)解連續(xù)多次不更新的方法來(lái)判斷種群停滯，然后再進(jìn)行反向進(jìn)化的.這種方式的靈活性較低，具體要判斷多少次最優(yōu)解不更新才合適？這里無(wú)法給出嚴(yán)格的數(shù)據(jù)，這也是文章不足之處.以后的研究重點(diǎn)是尋找更為精確的方法判定何時(shí)利用反向進(jìn)化策略來(lái)深度優(yōu)化.

[1]Dorigo M,Gambardella L M.Ant colony system:a cooperative learning approach to the traveling salesman problem[J].IEEE Transactions on evolutionary computation,1997,1(1):53-66.

[2]Kennedy J,Eberhart R.Particle swarm optimization[C]//IEEE International Conference on Neural Networks,1995.Proceedings.IEEE,2002:1942-1948.

[3]苗振華，孫旭東，邵誠(chéng).一種并行變異自適應(yīng)遺傳算法及其性能分析[J].信息與控制，2016，45(2):142-150.

[4]李牧東，趙輝，翁興偉，等.基于最優(yōu)高斯隨機(jī)游走和個(gè)體篩選策略的差分進(jìn)化算法[J].控制與決策，2016，31(8):1379-1386.

[5]陸克中，孫俊.螢火蟲(chóng)算法收斂分析[J].計(jì)算機(jī)科學(xué)與探索，2016，10(2):293-300.

[6]張水平，陳陽(yáng)，丁小軍.動(dòng)態(tài)搜索協(xié)同進(jìn)化的果蠅優(yōu)化算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2018(1):48-52.

[7]王碧，羅瀟，張水平.一種返巢模式下的粒子群優(yōu)化策略[J].江西理工大學(xué)學(xué)報(bào)，2015，36(3):95-100.

[8]胥小波，鄭康鋒，李丹，等.新的混沌粒子群優(yōu)化算法[J].通信學(xué)報(bào)，2012，33(1):24-30.

[9]王慶喜，郭曉波.基于萊維飛行的粒子群優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用研究，2016，33(9):2588-2591.

[10]劉志剛，曾嘉俊，韓志偉.基于個(gè)體最優(yōu)位置的自適應(yīng)變異擾動(dòng)粒子群算法[J].西南交通大學(xué)學(xué)報(bào)，2012，47(5):761-768.

[11]周利軍，彭衛(wèi)，鄒芳，等.自適應(yīng)變異粒子群算法[J].計(jì)算機(jī)工程與應(yīng)用，2016，52(7):50-55.

[12]黃松，田娜，紀(jì)志成.基于自適應(yīng)變異概率粒子群優(yōu)化算法的研究[J].系統(tǒng)仿真學(xué)報(bào)，2016，28(4):874-879.

[13]韓敏，何泳.基于高斯混沌變異和精英學(xué)習(xí)的自適應(yīng)多目標(biāo)粒子群算法[J].控制與決策，2016，31(8):1372-1378.

[14]陳侃松，阮玉龍，戴磊，等.區(qū)域分割的自適應(yīng)變異粒子群算法[J].電子學(xué)報(bào)，2017，45(8):1849-1855.