基于種子的多種群多策略并行PSO用于原子簇結(jié)構(gòu)優(yōu)化

朱靜靜 劉 靜

(上海海事大學(xué)信息工程學(xué)院 上海 201306)

0 引 言

原子簇是由幾個(gè)乃至上千個(gè)原子通過化學(xué)結(jié)合力組成的相對(duì)穩(wěn)定的微觀和亞微觀的聚集體，它被廣泛應(yīng)用于電化學(xué)、催化反應(yīng)、航天工業(yè)等領(lǐng)域，而具有穩(wěn)定空間結(jié)構(gòu)的原子簇能夠更好地保持并發(fā)揮其優(yōu)越的性能，因此研究原子簇的結(jié)構(gòu)優(yōu)化問題具有重大的現(xiàn)實(shí)意義。迄今為止，通過實(shí)驗(yàn)和理論方法只確定了少數(shù)種類原子簇的最優(yōu)空間結(jié)構(gòu)，隨著計(jì)算機(jī)模擬技術(shù)和計(jì)算機(jī)硬件軟件的飛速發(fā)展，通過理論方法來得到大多數(shù)原子簇的空間結(jié)構(gòu)成為大勢(shì)所趨。當(dāng)今主流的理論確定原子簇空間結(jié)構(gòu)的方法為從頭預(yù)測(cè)法，該法直接從原子數(shù)目出發(fā)，首先建立一個(gè)表征原子簇的空間結(jié)構(gòu)與其勢(shì)能之間關(guān)系的函數(shù)，然后根據(jù)熱物理理論，通過搜索算法找出原子簇勢(shì)能最低時(shí)對(duì)應(yīng)的空間結(jié)構(gòu)即為該原子簇的最穩(wěn)定結(jié)構(gòu)。

目前常用于搜索原子簇最優(yōu)結(jié)構(gòu)的算法有:蒙特·卡洛(Monte-Carlo)[1]、模擬退火(SA)[2-3]、遺傳算法(GA)[4-6]和粒子群算法(PSO)[7-8]等。其中粒子群算法是由Kennedy和Eberhart提出的一種基于鳥類覓食行為的啟發(fā)式群智能優(yōu)化算法[9-10],PSO具有無需繁雜的進(jìn)化操作、易于實(shí)現(xiàn)、參數(shù)少等優(yōu)點(diǎn)，但也具有易出現(xiàn)早熟陷入局部最優(yōu)、精度較低等不足，為了改進(jìn)PSO的性能，學(xué)者們從不同的切入點(diǎn)進(jìn)行突破，包括局部版本的PSO[11-12]、協(xié)同演化PSO[13]、動(dòng)態(tài)多種群粒子群算法(Dynamic Multi-Swarm Particle Swarm Optimizer，DMS-PSO)[14]、隨機(jī)漂移粒子群算法(Random Drift Swarm Optimization，RDPSO)[15-16]和基于頻繁覆蓋策略的隨機(jī)漂移粒子群算法(FC-RDPSO)[17]等。

本文提出了一種基于種子的多種群多策略并行粒子群算法(SS-MG-MS-PPSO)，且使用LJ函數(shù)測(cè)試該算法的運(yùn)行效率。針對(duì)原子簇結(jié)構(gòu)優(yōu)化問題，隨著原子數(shù)目的增加，單純的PSO等算法的優(yōu)化性能急劇衰減的原因有兩點(diǎn)：1) 隨著原子數(shù)目的不斷增加導(dǎo)致原子簇的結(jié)構(gòu)搜索空間持續(xù)膨脹，搜索到全局最優(yōu)解的難度大大增加；2) 隨著問題規(guī)模的增加，各個(gè)決策變量之間的耦合關(guān)系增強(qiáng)，搜索到的最優(yōu)解很可能出現(xiàn)“前進(jìn)兩步，倒退一步”的現(xiàn)象，優(yōu)化問題的復(fù)雜度大大增加。針對(duì)前者，種子策略(通過較少原子數(shù)目的原子簇最優(yōu)結(jié)構(gòu)信息來引導(dǎo)尋優(yōu)方向)可以大大減小搜索空間體積從而加快算法的搜索進(jìn)程，而多種群多策略機(jī)制則可以增加種群的多樣性，顯著提高算法的優(yōu)化性能。針對(duì)后者，多種群多策略中加入的FC-RDPSO在每次迭代時(shí)只針對(duì)個(gè)別變量進(jìn)行子空間的優(yōu)化，然后將各搜索子空間的優(yōu)化結(jié)果進(jìn)行頻繁的交叉、疊加，最終覆蓋到整個(gè)搜索空間，從而降低問題的復(fù)雜度。

該算法首先通過種子策略初始化種群，然后將初始化的種群劃分為多個(gè)子種群，各子群按照RDPSO和FC-RDPSO兩種不同的規(guī)則進(jìn)化，同時(shí)為了增強(qiáng)算法的全局和局部搜索能力，不同的子群設(shè)置的速度限制項(xiàng)不同，以充分發(fā)揮多種群獨(dú)立進(jìn)化的優(yōu)勢(shì)。在單獨(dú)進(jìn)化達(dá)到一定的迭代次數(shù)后，進(jìn)行種群間的通信交流，最終得到原子簇的最優(yōu)結(jié)構(gòu)或近似最優(yōu)結(jié)構(gòu)。此外，通過并行化操作進(jìn)一步提高算法的運(yùn)行性能及效率。

在原子簇的勢(shì)能函數(shù)上對(duì)SS-MG-MS-PPSO進(jìn)行優(yōu)化測(cè)試，并進(jìn)行算法的有效性論證，分別對(duì)原子數(shù)為2～35的原子簇結(jié)構(gòu)進(jìn)行優(yōu)化。分別將DMS-RDPSO、DMS-FC-RDPSO和MG-MS-PSO與SS-MG-MS-PPSO進(jìn)行比較，實(shí)驗(yàn)結(jié)果表明，SS-MG-MS-PPSO對(duì)于原子數(shù)在2到35之間的原子能搜索到其最優(yōu)或近似最優(yōu)結(jié)構(gòu)，且在各性能上均具有較大優(yōu)勢(shì)。

1 計(jì)算原理

從頭預(yù)測(cè)法確定原子簇的最優(yōu)結(jié)構(gòu)主要有兩個(gè)步驟：找到一個(gè)表征原子簇各原子的空間三維坐標(biāo)與其勢(shì)能之間關(guān)系的函數(shù)；通過搜索算法找到能量最低時(shí)對(duì)應(yīng)的原子簇的空間結(jié)構(gòu)即為該原子簇的最穩(wěn)定結(jié)構(gòu)。本文使用的能量函數(shù)是L-J勢(shì)能函數(shù)，該函數(shù)能用來模擬兩分子或兩原子間的作用勢(shì)能，原子簇中所有原子間的相互作用勢(shì)能之和即為該原子簇所具有的能量，包含N個(gè)原子的原子簇的勢(shì)能用公式表示如下：

(1)

式中：ε表示二聚體的勢(shì)能阱深度；σ表示二聚體的核心距；rij為原子簇中任意兩個(gè)原子i與原子j間的歐氏距離。

(2)

2 算法描述

2.1 動(dòng)態(tài)多種群粒子群算法

動(dòng)態(tài)多種群粒子群算法(DMS-PSO)結(jié)合了局部PSO和基本全局PSO的優(yōu)點(diǎn)，首先產(chǎn)生多個(gè)有效的初始解形成初始種群，再將初始種群劃分為多個(gè)小種群(子群)，各子群在局部PSO下獨(dú)立進(jìn)化后，重新組合形成新的種群，反復(fù)迭代、進(jìn)化。這樣的優(yōu)化規(guī)律增加了種群的多樣性，當(dāng)?shù)_(dá)到一定次數(shù)后，使用全局版本的PSO對(duì)所有粒子進(jìn)行更新，得到最終的結(jié)果[18]。

2.2 隨機(jī)漂移粒子群算法

隨機(jī)漂移粒子群算法(RDPSO)的中心思想來源于磁場(chǎng)中金屬導(dǎo)體內(nèi)的自由電子存在兩種形式的運(yùn)動(dòng)：無規(guī)則的隨機(jī)熱運(yùn)動(dòng)和定向漂移運(yùn)動(dòng)。這兩種運(yùn)動(dòng)方式使得金屬導(dǎo)體內(nèi)的勢(shì)能逐漸變小，這與PSO搜索優(yōu)化問題全局最優(yōu)解的過程如出一轍。自由電子所做的隨機(jī)熱運(yùn)動(dòng)相當(dāng)于優(yōu)化搜索過程中粒子的全局搜索，受磁場(chǎng)環(huán)境影響而產(chǎn)生的定向漂移運(yùn)動(dòng)則類似于粒子的局部搜索，這兩種搜索方式相輔相成，使得優(yōu)化問題的目標(biāo)函數(shù)值不斷地接近于全局最優(yōu)解。

在RDPSO中，粒子速度更新公式由定向漂移運(yùn)動(dòng)項(xiàng)和隨機(jī)熱運(yùn)動(dòng)項(xiàng)構(gòu)成，速度更新公式如下：

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

綜合1)、2)兩項(xiàng)，RDPSO中的粒子速度更新公式可表示如下：

(12)

該算法中的粒子位置更新公式為：

(13)

綜上，RDPSO通過粒子的速度和位置的不斷更新，逐步地逼近目標(biāo)函數(shù)的最優(yōu)值，具有較強(qiáng)的優(yōu)化能力。

2.3 基于頻繁覆蓋集策略的隨機(jī)漂移粒子群算法

為了進(jìn)一步提高RDPSO搜索到全局最優(yōu)解的概率，文獻(xiàn)[17]提出將頻繁覆蓋策略引入到RDPSO中。即在每次的迭代過程中僅優(yōu)化一部分隨機(jī)選取的決策變量，而保持其余變量不變，由此構(gòu)成一個(gè)個(gè)的搜索子空間，利用RDPSO搜索粒子在各個(gè)子空間上的最優(yōu)位置。由于每次迭代過程中優(yōu)化的決策變量是隨機(jī)選取的，經(jīng)過多次迭代后，這些子空間中的變量相互重疊、交叉或互異，能夠覆蓋到整個(gè)搜索空間，從而子優(yōu)化算法RDPSO能夠搜索到全局最優(yōu)值。這樣的策略大大減小了子空間搜索的難度，這也是高維度復(fù)雜優(yōu)化問題的有效解決方案之一。

2.4 基于種子的多種群多策略并行粒子群算法

2.4.1種子策略

本文采用種子策略(Seed Strategy，SS)，即參考已求得的具有較少原子數(shù)的原子簇最優(yōu)空間結(jié)構(gòu)，初始化原子數(shù)相對(duì)多的團(tuán)簇空間結(jié)構(gòu)的初始解產(chǎn)生方式。假設(shè)已求得含有N個(gè)原子的原子簇W的穩(wěn)定結(jié)構(gòu)，設(shè)此時(shí)原子簇W中N個(gè)原子的空間坐標(biāo)為(X1，X2，…,Xi，…,XN)，若此時(shí)需要求解含有N+1個(gè)原子的原子簇的最優(yōu)結(jié)構(gòu),如果在W的基礎(chǔ)上增加一個(gè)隨機(jī)生成坐標(biāo)的原子XN+1作為該原子簇的初始解W’，雖然W’未必是該原子簇的最優(yōu)結(jié)構(gòu)，但通常會(huì)比隨機(jī)初始化N+1個(gè)原子的三維坐標(biāo)得到的初始解要更接近于該原子簇的最優(yōu)結(jié)構(gòu)。

因此，本文在求解含有較多原子的原子簇最優(yōu)結(jié)構(gòu)時(shí)，選擇使用種子策略來初始化初始解，而對(duì)于所含原子數(shù)較少的原子簇最優(yōu)結(jié)構(gòu)的求解，初始解的生產(chǎn)方式依據(jù)求解的難度來選擇。

2.4.2多種群多策略機(jī)制

本文除了在初始解的生成方式上進(jìn)行改進(jìn)外，還將多種群動(dòng)態(tài)尋優(yōu)機(jī)制加入到搜索算法中。為了最大程度地加強(qiáng)優(yōu)化算法的搜索能力，將粒子群劃分為多個(gè)小種群，各小種群分別在擁有不同參數(shù)的RDPSO和FC-RDPSO下并行尋優(yōu)。由于RDPSO具有較強(qiáng)的全局搜索能力而FC-RDPSO能在較少的計(jì)算時(shí)間內(nèi)具有較快的收斂速度和更高的尋優(yōu)精度，而不同的參數(shù)控制著算法全局搜索和局部搜索的能力，因此該機(jī)制能夠在高維度的優(yōu)化問題上發(fā)揮出其明顯的尋優(yōu)和效率優(yōu)勢(shì)。

2.4.3并行化原理

本文提出的基于種子的多種群多策略并行粒子群算法(SS-MG-MS-PPSO)以較高效率解決高維度的優(yōu)化問題，利用多種群機(jī)制將初始化的種群分配給擁有不同搜索能力的子群，這些子群在隨機(jī)漂移粒子群算法(RDPSO)和基于頻繁覆蓋策略的隨機(jī)漂移粒子群算法(FC-RDPSO)兩種不同的規(guī)則下并行進(jìn)化，大大增加了種群的多樣性。由于RDPSO具有較強(qiáng)的全局搜索能力，F(xiàn)C-RDPSO可以產(chǎn)生許多搜索子空間，子空間使用RDPSO進(jìn)行并行優(yōu)化，從而能夠以更大的概率覆蓋到整個(gè)搜索空間，RDPSO和FC-RDPSO相結(jié)合再配合速度限制項(xiàng)的變化，所以該算法能夠在原子簇的結(jié)構(gòu)優(yōu)化方面表現(xiàn)出優(yōu)越的性能。除了算法內(nèi)部的多種群機(jī)制并行策略和FC-RDPSO中的搜索子空間的并行進(jìn)化以外，本文在此基礎(chǔ)上加入了外部的并行機(jī)制，即利用MATLAB并行工具箱(Parallel Computing Tool，PCT)將算法放到一個(gè)計(jì)算機(jī)集群上并行計(jì)算，這大大地加快了算法的計(jì)算效率。

SS-MG-MS-PPSO通過內(nèi)部和外部的同步并行運(yùn)算，增強(qiáng)該算法在尋優(yōu)性能和求解效率上的優(yōu)勢(shì)。

2.4.4算法流程

將本文提出的SS-MG-MS-PPSO應(yīng)用于包含n個(gè)原子的原子簇結(jié)構(gòu)優(yōu)化，其優(yōu)化求解的步驟如下：

(1) 設(shè)定算法的最大迭代次數(shù)maxiter和種群中的粒子數(shù)popsize，在可行域內(nèi)選用適當(dāng)?shù)某跏蓟绞?隨機(jī)初始化方式或種子策略)構(gòu)造popsize個(gè)3行n列的向量作為初始種群pop，每一個(gè)3行n列的向量代表一個(gè)包含n個(gè)原子的原子簇初始空間結(jié)構(gòu)，并初始化總迭代次數(shù)i=1。

(2) 將種群pop隨機(jī)劃分為s個(gè)包含粒子數(shù)目相等的子群。

(3) 設(shè)定子群?jiǎn)为?dú)進(jìn)化的總次數(shù)R，初始化子群?jiǎn)为?dú)進(jìn)化次數(shù)r=1。

(4) 每個(gè)子群都在具有不同搜索能力的FC-RDPSO或RDPSO算子下單獨(dú)進(jìn)化，每單獨(dú)進(jìn)化一次r=r+1，當(dāng)r

(5) 將單獨(dú)進(jìn)化R次后的s個(gè)子群合并，組成新的pop種群，并使得i=i+1，當(dāng)i

3 參數(shù)設(shè)置和實(shí)驗(yàn)環(huán)境

為了檢驗(yàn)本文提出的SS-MG-MS-PPSO算法解決原子簇結(jié)構(gòu)優(yōu)化問題的性能,選擇原子數(shù)在2到35之間原子簇的L-J勢(shì)能函數(shù)作為測(cè)試函數(shù),選擇DMS-RDPSO、DMS-FC-RDPSO和MG-MS-PSO三個(gè)算法作為對(duì)比算法，驗(yàn)證算法的有效性。根據(jù)相關(guān)參考文獻(xiàn)，采用的算法參數(shù)設(shè)置見表1。其中，popsize表示種群規(guī)模，s表示多種群機(jī)制下的子群數(shù)目，α和β分別表示RDPSO中的熱敏系數(shù)和漂移系數(shù)，M表示在FC-RDPSO每次迭代過程中選擇優(yōu)化的決策變量個(gè)數(shù)。

表1 各算法的參數(shù)設(shè)置

特別地，本文提出多種群多策略，在得到初始化種群后將其平均劃分為12個(gè)子群，每個(gè)子群設(shè)置不同的速度限制項(xiàng)，速度限制項(xiàng)是用來限制粒子的飛行速度，若粒子飛行速度過快，很可能直接飛過最優(yōu)解位置，但若飛行速度過慢，會(huì)使得收斂速度變慢，因此設(shè)置合理的速度限制項(xiàng)很有必要。各算法中每6個(gè)子群為一組，每組子群速度限制項(xiàng)vmax設(shè)為0至1的不同分節(jié)點(diǎn)。

本文實(shí)驗(yàn)所用的計(jì)算機(jī)配置如下：Intel Core i5-6500 CPU，3.20 GHz，8 GB內(nèi)存，Windows 10專業(yè)版，64位操作系統(tǒng)。

4 結(jié)果分析

本文提出的SS-MG-MS-PPSO及對(duì)比算法(DMS-RDPSO、DMS-FC-RDPSO和MG-MS-PSO)在原子數(shù)為2到35的原子簇結(jié)構(gòu)優(yōu)化測(cè)試的結(jié)果如表2所示(原子數(shù)不同的原子簇對(duì)應(yīng)蘭納瓊斯勢(shì)能各指標(biāo)的理想值參考文獻(xiàn)[19])。原子個(gè)數(shù)不同的原子簇優(yōu)化結(jié)果的優(yōu)劣由三個(gè)指標(biāo)來評(píng)判，分別是各算法在此測(cè)試函數(shù)上獨(dú)立運(yùn)行30次所得目標(biāo)函數(shù)值的最優(yōu)值(Opt)、平均值(Ave)和標(biāo)準(zhǔn)差(Sta)。

表2 各算法在原子簇的L-J勢(shì)能函數(shù)上的測(cè)試結(jié)果

續(xù)表2

續(xù)表2

為了更加直觀地比較DMS-RDPSO、DMS-FC-RDPSO、MG-MS-PSO和SS-MG-MS-PPSO的實(shí)驗(yàn)結(jié)果，本文將各算法優(yōu)化原子簇結(jié)構(gòu)的結(jié)果用折線圖表示。圖1表示各算法求得的原子簇最低能量值與理想能量值的差值曲線；圖2表示各算法獨(dú)立運(yùn)行30次求得的原子簇平均能量值與理想能量值的差值曲線；圖3表示各算法獨(dú)立運(yùn)行30次求得的原子簇能量值標(biāo)準(zhǔn)差變化曲線。

圖1 各算法求得的原子簇最低能量值 與理想能量值的差值曲線

圖2 各算法獨(dú)立運(yùn)行30次求得的原子簇平均 能量值與理想能量值的差值曲線

圖3 各算法獨(dú)立運(yùn)行30次求得的原子簇 能量值標(biāo)準(zhǔn)差變化曲線

從表2中可看出：對(duì)于原子數(shù)N=2,3,4,5的原子簇，各算法皆可求得原子簇的穩(wěn)定結(jié)構(gòu)，且均達(dá)到理想效果；對(duì)于原子數(shù)N=6，…，16的原子簇，各算法均能求得其最優(yōu)結(jié)構(gòu)，但SS-MG-MS-PPSO有更高的穩(wěn)定性；當(dāng)原子數(shù)N=17,…,25時(shí)，另外三個(gè)算法在個(gè)別原子數(shù)上所能求得的最優(yōu)值與理想最優(yōu)值均已存在差距，均值、標(biāo)準(zhǔn)差與理想值差距也較大，而此時(shí)SS-MG-MS-PPSO能求得其最優(yōu)結(jié)構(gòu)且標(biāo)準(zhǔn)差也相對(duì)較??；當(dāng)原子數(shù)N=26,…,31時(shí)，三個(gè)對(duì)比算法能求得的最優(yōu)值與理想最優(yōu)值之間存在較大差距，而SS-MG-MS-PPSO能求得的最優(yōu)值與理想最優(yōu)值差距較小，整體上保持著算法的穩(wěn)定性；當(dāng)原子數(shù)N=32,33時(shí)，SS-MG-MS-PPSO求得的最優(yōu)結(jié)構(gòu)與理想最優(yōu)值有一定差距，但與其他三個(gè)算法相比，差距已經(jīng)大大地縮小，且均值與方差也在一定的波動(dòng)范圍之內(nèi)；當(dāng)原子數(shù)N=34,35時(shí)，SS-MG-MS-PPSO求得的最優(yōu)結(jié)構(gòu)與理想最優(yōu)值有差距，相對(duì)于DMS-FC-RDPSO和MG-MS-PSO而言，稍顯遜色，但更穩(wěn)定，原因可能是“種子策略”限制了原子簇結(jié)構(gòu)的自由“生長(zhǎng)”，使其極易陷入局部極優(yōu)，所以相對(duì)其他算法不易跳出局部極優(yōu)，更顯穩(wěn)定。從整體來看，當(dāng)原子數(shù)N=2,3,...,33時(shí)，SS-MG-MS-PPSO明顯優(yōu)于其他三個(gè)算法，并且能以較高的效率求得原子簇的最優(yōu)結(jié)構(gòu)或近似最優(yōu)結(jié)構(gòu)。

從圖1和圖2也可以發(fā)現(xiàn)，SS-MG-MS-PPSO30次獨(dú)立運(yùn)行求得的最優(yōu)值、平均值與理想值之間的差距明顯小于三個(gè)對(duì)比算法。圖3充分展現(xiàn)了SS-MG-MS-PPSO較其他算法都更為穩(wěn)定。綜上所述，本文提出的SS-MG-MS-PPSO在原子數(shù)為N=2,…,35的原子簇結(jié)構(gòu)優(yōu)化上，有著更高的尋優(yōu)效率和更好的穩(wěn)定性。

此外，本文算法使用的并行機(jī)制將串行運(yùn)行僅25%的CPU利用率提高到了95%以上，運(yùn)行時(shí)間顯著減少，大大加快了算法的運(yùn)行效率。

5 結(jié) 語(yǔ)

本文針對(duì)原子簇結(jié)構(gòu)優(yōu)化問題，提出了一種基于種子的多種群多策略并行粒子群算法(SS-MG-MS-PPSO)。該算法使用種子策略初始化種群，然后將種群劃分為多個(gè)子群且各子群在不同的規(guī)則下單獨(dú)進(jìn)化，只需定期進(jìn)行通信交流，通過發(fā)揮不同搜索策略的優(yōu)勢(shì)從而找到原子簇的最優(yōu)結(jié)構(gòu)或近似最優(yōu)結(jié)構(gòu)。實(shí)驗(yàn)結(jié)果表明，SS-MG-MS-PPSO對(duì)于原子數(shù)在2到35之間的原子簇搜索到其最優(yōu)或近似最優(yōu)結(jié)構(gòu)，且相比其他算法更為穩(wěn)定、高效，證明種子策略(SS)和多種群多策略并行進(jìn)化機(jī)制可有效增強(qiáng)算法的搜索效率和能力，為原子簇的結(jié)構(gòu)優(yōu)化提供了一種新的解決思路。當(dāng)然，該算法存在一定的缺陷，隨著原子數(shù)的增加，該算法尋求原子簇最優(yōu)結(jié)構(gòu)的能力稍顯力不從心，這也是該課題未來的主要研究方向。