求解高維復(fù)雜連續(xù)優(yōu)化問題的粒子群算法研究

潘允敬

（廈門海合達電子信息股份有限公司，福建 廈門361009）

0 引 言

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

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

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

1 粒子群算法

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

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

2 分組變異與反向進化的粒子群算法

2.1 基本思想描述

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

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

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

2.2 分組變異

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

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

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

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

step2.將輸入的種群按適應(yīng)度fitness排序；

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

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

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

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

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

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

2.3 反向進化

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

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

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

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

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

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

3） While t＜T

4） For i＜Maxsize

5） For d＜Dim

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

7） End

8）End

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

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

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

12） Record++;

13） End

14） If Record＞=T/20

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

16） End

17）End

18） Return min（f（x））;

3 實驗分析

3.1 實驗設(shè)計

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

表1 測試函數(shù)表

3.2 實驗結(jié)果

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

表2 實驗結(jié)果對比

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

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

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

4 結(jié) 論

文章研究了粒子群算法在求解較高維優(yōu)化問題時出現(xiàn)的早熟現(xiàn)象，引入分組變異的方式，使粒子群進化過程中可以在保持種群多樣性的同時有針對性的遍歷解空間.進化后期種群共享信息不足時，采用反向進化的操作進行跳出局部環(huán)境操作.經(jīng)過對4個高維函數(shù)的測試，證明新提出的算法在收斂速度與優(yōu)化精度上都具有更高的性能.是利用最優(yōu)解連續(xù)多次不更新的方法來判斷種群停滯，然后再進行反向進化的.這種方式的靈活性較低，具體要判斷多少次最優(yōu)解不更新才合適？這里無法給出嚴(yán)格的數(shù)據(jù)，這也是文章不足之處.以后的研究重點是尋找更為精確的方法判定何時利用反向進化策略來深度優(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]苗振華，孫旭東，邵誠.一種并行變異自適應(yīng)遺傳算法及其性能分析[J].信息與控制，2016，45(2):142-150.

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

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

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

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

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

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

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

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

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

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

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