多物態(tài)擬態(tài)物理學(xué)優(yōu)化算法

安澤曄，謝麗萍

(太原科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，太原 030014)

求解最優(yōu)化問題的啟發(fā)式算法[1-3]中，包含受生物群體行為啟發(fā)的微粒群算法[4]，模擬自然進(jìn)化規(guī)律的遺傳算法[5]，還有受物理學(xué)原理啟發(fā)的類電磁機(jī)制算法[6]，中心力算法[7]，模擬退火算法[8]和擬態(tài)物理學(xué)算法[9]等。其中，擬態(tài)物理學(xué)算法(APO)是從自然物理規(guī)律中得到啟發(fā)，模擬兩個物體之間虛擬的作用力，然后仿照牛頓第二力學(xué)定律進(jìn)行算法尋優(yōu)的過程，該算法作用于種群個體之間，建立起算法中的尋優(yōu)個體與物理學(xué)中的個體之間的對應(yīng)關(guān)系。

近年來，對擬態(tài)物理學(xué)優(yōu)化算法的研究有很多。有對其算法框架的研究[10-11]，對算法性能的研究[12]，對收斂性分析及對參數(shù)G的設(shè)置的研究[13]，對其在實(shí)際中的應(yīng)用的研究[14-18]。但 APO算法在迭代過程中只遵循一種運(yùn)動規(guī)則，使所有尋優(yōu)個體體現(xiàn)相同的運(yùn)動特征，不能有效的平衡全局搜索和局部搜索能力，而單一的搜索策略往往不能得到更好的解，也不能更好的貼合實(shí)際，解決問題。由此為了增加種群的多樣性，引入多物態(tài)的概念，并對物態(tài)劃分的方法進(jìn)行了研究。

物理學(xué)中的宏觀物質(zhì)狀態(tài)包含了三種基本的狀態(tài)，即固態(tài)，液態(tài)和氣態(tài)，而這三種基本狀態(tài)在微觀世界中由于分子間的布朗運(yùn)動又可以相互轉(zhuǎn)化，不同物態(tài)分子的熱運(yùn)動隨分子之間的結(jié)構(gòu)不同而運(yùn)動方式不同。將個體映射到物理學(xué)中具有物態(tài)特性的個體，不同“物態(tài)”的個體采用不同的搜索策略，并且由于物理環(huán)境中溫度變化而導(dǎo)致的狀態(tài)轉(zhuǎn)化行為，算法同樣映射了不同物態(tài)個體的行為方式。個體的運(yùn)動規(guī)則融合了不同的物理學(xué)運(yùn)動規(guī)律，包括萬有引力中的引斥力機(jī)制，模擬退火算法的單點(diǎn)運(yùn)動規(guī)則以及宇宙大爆炸算法中的質(zhì)心爆炸過程。這三種運(yùn)動規(guī)律近似地模擬了固態(tài)，液態(tài)，氣態(tài)的運(yùn)動特性，在本文中，固態(tài)集合的運(yùn)動規(guī)則采用APO算法的運(yùn)動規(guī)則，液態(tài)個體的運(yùn)動仿照模擬退火算法的單點(diǎn)運(yùn)動規(guī)則，氣態(tài)個體運(yùn)動仿照宇宙大爆炸算法每代從質(zhì)心位置向外爆炸的過程，使個體盡可能遍歷更多的點(diǎn)。本文利用這三種物態(tài)的粒子運(yùn)動為解決算法中單一的搜索策略易于早熟的狀況。

1 標(biāo)準(zhǔn)APO算法

APO算法[9]主要包括三個部分，首先初始化種群。設(shè)種群規(guī)模為N，維數(shù)為D，個體位置xi和運(yùn)動速度vi在可行域內(nèi)均勻取值。其次計(jì)算個體質(zhì)量，質(zhì)量公式為

(1)

在t時刻個體i受到的作用力合力表示為：

(2)

最后更新個體運(yùn)動的速度和位置。

?i≠best

(3)

xi,k(t+1)=xi,k(t)+vi,k(t)

(4)

其算法流程如下：

Step1：初始化種群的個體位置和速度，并計(jì)算適應(yīng)值，保留算法的最優(yōu)適應(yīng)值及最優(yōu)個體；

Step2：計(jì)算個體質(zhì)量及個體所受合力；

Step3：更新個體速度和位置；

Step4：計(jì)算個體適應(yīng)值，更新最優(yōu)個體及其適應(yīng)值；

Step5：判斷是否滿足程序結(jié)束條件，若滿足，則輸出最優(yōu)結(jié)果并結(jié)束程序，否則返回Step2，繼續(xù)迭代。

2 多物態(tài)擬態(tài)物理學(xué)算法的融合

多物態(tài)物理學(xué)算法的融合主要包括三個部分：初始化種群，物態(tài)劃分，計(jì)算不同物態(tài)的個體運(yùn)動。初始化種群后，按一定的劃分標(biāo)準(zhǔn)劃分固態(tài)，液態(tài)和氣態(tài)個體，首先分離出氣態(tài)個體，然后根據(jù)其他個體與選出的中心點(diǎn)個體間的距離設(shè)定固態(tài)和液態(tài)的鄰域集合，集合內(nèi)含兩個或兩個以上的個體歸為固態(tài)集合，只有一個個體的歸為液態(tài)集合。物態(tài)劃分后，個體按不同的運(yùn)動規(guī)則更新速度和位置，計(jì)算每個個體的適應(yīng)值，然后根據(jù)個體的適應(yīng)值及環(huán)境，判斷某些個體的物態(tài)是否需要發(fā)生變化，若需要，則重新劃分物態(tài)，并按相應(yīng)的運(yùn)動規(guī)則進(jìn)行運(yùn)動。

2.1 運(yùn)動規(guī)則

本文根據(jù)不同物態(tài)的個體運(yùn)動規(guī)律不同，選用了三種不同的運(yùn)動規(guī)則。

規(guī)則一：標(biāo)準(zhǔn)APO算法的運(yùn)動規(guī)則

規(guī)則二：仿照模擬退火算法的單點(diǎn)運(yùn)動規(guī)則。

速度和位置計(jì)算公式如下

?i≠best

xi,k(t+1)=xi,k(t)+(2*rand-1)L

(5)

vi,k(t+1)=vi,k(t)+xi,k(t+1)

(6)

規(guī)則三：仿照宇宙大爆炸算法，每代從質(zhì)心位置向外爆炸，個體運(yùn)動方向和運(yùn)動步長隨機(jī)，其中質(zhì)量m計(jì)算如公式(1)。

(7)

(8)

vi,k(t+1)=xi,k(t+1)-xi,k(t)

(9)

2.2 物態(tài)劃分方法

APO算法只遵循一種作用力規(guī)則，個體運(yùn)動方式較為單一，算法的種群多樣性相對較差。在物理學(xué)中，固態(tài)和液態(tài)物質(zhì)的運(yùn)動比較局限，而氣態(tài)物質(zhì)擴(kuò)散性好，映射到算法中，適應(yīng)值較好且被劃分為固態(tài)和液態(tài)的個體適于做局部搜索，而適應(yīng)值較差的個體則對應(yīng)于氣體的擴(kuò)散性質(zhì)，適于做全局搜索。這種劃分方法增加了種群的多樣性，簡單易操作。但若是直接通過將適應(yīng)值大小進(jìn)行排序，挑選前K個較好個體作為固態(tài)或液態(tài)個體，那么K的選擇至關(guān)重要，有可能出現(xiàn)第k個和k+1個個體適應(yīng)值相同或相似的情況，從而導(dǎo)致物態(tài)的劃分不合理。當(dāng)k值過大，可能導(dǎo)致全局搜索能力較弱，k值過小，又可能導(dǎo)致算法收斂過慢的情況。由此，這里引入了一種物態(tài)(包括固態(tài)、液態(tài)和氣態(tài)等)的劃分標(biāo)準(zhǔn)Cls，如公式(10).該公式將個體的適應(yīng)值映射到(0,1)的區(qū)間內(nèi)，避免具有相同適應(yīng)值的不同個體被劃分為不同的物態(tài)，增加了劃分的合理性。

(10)

當(dāng)xi適應(yīng)值較大，clsi較小，將該個體設(shè)為氣態(tài)個體，用于全局搜索；當(dāng)xi適應(yīng)值較小，clsi較大，將該個體設(shè)為固態(tài)或液態(tài)個體，用于局部搜索。

該算法中取cls_standard為劃分的標(biāo)準(zhǔn)參數(shù)，當(dāng)個體的clsi>cls_standard時，劃分為固態(tài)或液態(tài)個體，相反劃分為氣態(tài)個體。該標(biāo)準(zhǔn)基于每一代適應(yīng)值的最大值和最小值，用較為相對的標(biāo)準(zhǔn)劃分物態(tài)，增加了物態(tài)劃分的合理性。

算法描述

該方案在APO的基礎(chǔ)上引入物態(tài)劃分的概念，以公式(10)的cls作為物態(tài)劃分的標(biāo)準(zhǔn)，在初始化種群后，便進(jìn)行物態(tài)的劃分，以期提高種群的多樣性。劃分之后，各物態(tài)集合的個體按照不同的運(yùn)動規(guī)則運(yùn)動，之后保留最優(yōu)值并判斷是否達(dá)到結(jié)束條件，達(dá)到則結(jié)束程序，未達(dá)到則重新劃分物態(tài)，進(jìn)行運(yùn)動。在此算法中，劃分為固態(tài)集合的個體按照APO算法中的引斥力規(guī)則運(yùn)動，劃分為液態(tài)集合的個體按照模擬退火運(yùn)動，劃分為氣態(tài)集合的個體按照宇宙大爆炸的方法運(yùn)動。該算法的算法步驟如下：

Step1：初始化。在可行域內(nèi)均勻產(chǎn)生個體的位置與速度，并計(jì)算相應(yīng)的適應(yīng)值，保留最優(yōu)個體及其適應(yīng)值。

Step2：物態(tài)劃分。按照公式(10)計(jì)算每個個體的cls值，clsir的個體作為液態(tài)個體。

Step3：各集合按相應(yīng)的運(yùn)動規(guī)則運(yùn)動一次。每個固態(tài)集合都按照規(guī)則一運(yùn)動，液態(tài)個體按照規(guī)則二運(yùn)動，氣態(tài)個體按照規(guī)則三運(yùn)動。

Step4：計(jì)算適應(yīng)值，保留最優(yōu)個體及適應(yīng)值。判斷是否達(dá)到結(jié)束條件，是則結(jié)束運(yùn)行并輸出結(jié)果，否則返回步驟2.

3 實(shí)例仿真

為了測試上述方案的可行性，選用CEC2013 Benchmark 測試集中的Sphere Function, Rotated Rosenbrock’s Function, Rotated Schaffers F7 Function, Rotated Ackley’s Function, Rotated Griewank’s Function, Composition Function 1(n=5,Rotated)六個測試函數(shù)。這些測試函數(shù)的參數(shù)如表1所示，其中問題維數(shù)(n)、函數(shù)的搜索空間(Search range)、函數(shù)的已知最有值(Known optimum)、算法使用的種群規(guī)模(Npop)以及算法迭代的最大代數(shù)(MAX-ITER)已列出。

表1 測試函數(shù)參數(shù)列表
Tab.1 The parameter list of test function

FunNNpopSearch rangeKnown optimumMAX-ITERSphere Function3030[-100,100]n-140010000Rotated Rosenbrock’s Function3030[-100,100]n-90010000RotatedSchaffers F7 Function3030[-100,100]n-80010000Rotated Ackley’s Function3030[-100,100]n-70010000Rotated Griewank’s Function3030[-100,100]n-50010000Composition Function 1(n=5,Rotated)3030[-100,100]n70010000

3.1 MSAPO與APO算法性能分析

在仿真實(shí)驗(yàn)中，為了方便算法的比較和分析，將引入cls參數(shù)的多物態(tài)物理學(xué)算法命名為MSAPO.MSAPO中模擬退火運(yùn)動規(guī)則的溫度初始值T=100，衰減系數(shù)k=0.5，并按照經(jīng)驗(yàn)值，鄰域半徑r=30，引斥力運(yùn)動規(guī)則中的G值為0.1，物態(tài)劃分標(biāo)準(zhǔn)cls_standard=0.5.原APO算法中G值取0.1.在相同的實(shí)驗(yàn)條件下，表1的測試函數(shù)在APO算法和MSAPO算法下的對比實(shí)驗(yàn)結(jié)果如表2所示。每個實(shí)驗(yàn)重復(fù)執(zhí)行10次，統(tǒng)計(jì)最好適應(yīng)值(Best)，平均最好適應(yīng)值(Mean)，標(biāo)準(zhǔn)方差(STD)和平均誤差(Mean_error).

表2 APO、MSAPO算法性能比較結(jié)果
Tab.2The performance comparison results of algorithm APO and MSAPO

FuncDimAlgorithmBestMeanSTDMean_errorSphere Function30APO-1.4000E+03-1.4000E+039.7019E-086.3109E-08MSAPO-1.4000E+03-1.4000E+038.3226E-114.7066E-11Rotated Rosenbrock’sFunction30APO-8.8355E+02-8.5805E+022.6578E+014.1950E+01MSAPO-8.8492E+02-8.5874E+022.5519E+014.1264E+01Rotated Schaffers F7 Function30APO-6.4900E+02-6.1893E+022.1656E+011.8107E+02MSAPO-7.8956E+02-7.5823E+023.5565E+014.1766E+01Rotated Ackley’s Function30APO-6.7909E+02-6.7905E+023.0563E-022.0949E+01MSAPO-6.7910E+02-6.7905E+023.0341E-022.0950E+01Rotated Griewank’s Function30APO-4.9985E+02-4.9900E+027.0865E-011.0045E+00MSAPO-4.9995E+02-4.9984E+025.9681E-021.5627E-01Composition Function 1(n=5,Rotated)30APO9.0000E+021.7743E+036.7707E+021.0743E+03MSAPO1.0000E+031.0287E+036.0524E+013.2871E+02

表2給出了相同代數(shù)下所測函數(shù)在APO與MSAPO算法下的對比實(shí)驗(yàn)結(jié)果。MSAPO算法在以上六個測試函數(shù)中找到的最優(yōu)適應(yīng)值均比APO算法好或者相等，其性能整體上也優(yōu)于APO算法。其中，復(fù)雜函數(shù)Composition在MSAPO算法下的最優(yōu)值比APO算法要差一些，但平均值和標(biāo)準(zhǔn)方差均優(yōu)于APO算法。其他基本多峰函數(shù)在MSAPO算法下的性能都相對較好，除了Rotated Schaffers F7 函數(shù)，其在MSAPO算法下的標(biāo)準(zhǔn)方差和平均誤差值較APO差。

Rotated Schaffers F7函數(shù)是復(fù)雜非線性多模態(tài)函數(shù)，擁有廣泛的搜索空間和大量的局部極小點(diǎn)，MSAPO算法在該函數(shù)上平均值和最優(yōu)值都得到明顯的提升，這是因?yàn)锳PO算法具有較好的全局搜索能力，但算法的搜索方式較為單一，算法種群多樣性差，局部搜索能力較弱，而MSAPO算法加入了物態(tài)劃分和多種運(yùn)動規(guī)則，使算法的搜索方式多樣化，可以根據(jù)個體當(dāng)前的狀態(tài)選擇相應(yīng)的運(yùn)動規(guī)則，增加了APO算法的種群多樣性，相對于運(yùn)動規(guī)則單一的APO算法而言，更容易找到測試函數(shù)的最優(yōu)值。但SchaffersF7與compodition1函數(shù)表現(xiàn)不佳之處說明了該算法種群多樣性雖然好，但是在局部極小值較多的復(fù)雜函數(shù)上的精細(xì)搜索不夠，較不穩(wěn)定。

3.2 物態(tài)劃分標(biāo)準(zhǔn)參數(shù)對算法的影響

在引入物態(tài)劃分的APO算法中，物態(tài)劃分的標(biāo)準(zhǔn)參數(shù)為種群中各物態(tài)的個體個數(shù)分布比例情況提供了重要信息，其選擇的好壞能夠影響APO算法的性能。實(shí)驗(yàn)通過研究該物態(tài)劃分標(biāo)準(zhǔn)參數(shù)的選擇策略判斷對算法性能的影響。

本算法取cls_standard為劃分物態(tài)的標(biāo)準(zhǔn)參數(shù)，當(dāng)個體的Clsi達(dá)到標(biāo)準(zhǔn)參數(shù)cls_standard時，劃分為氣態(tài)個體，相反則劃分為固態(tài)或液態(tài)個體。該標(biāo)準(zhǔn)參數(shù)基于公式(10)給出，Clsi的取值范圍為(0,1).當(dāng)種群中劃分為固態(tài)或液態(tài)的個體個數(shù)較多時，由于算法中固態(tài)或液態(tài)個體的運(yùn)動規(guī)則偏向于精細(xì)搜索，可能使得整個算法的局部搜索能力隨之增強(qiáng)，而全局搜索能力也就相應(yīng)減弱，這樣不利于遍歷搜索空間中盡可能多的點(diǎn)。當(dāng)種群中劃分為氣態(tài)的個體個數(shù)較多時，算法中氣態(tài)個體的運(yùn)動偏向于全局搜索，可能使得算法的全局搜索能力增強(qiáng)，但是容易丟失潛在較好解，且在較好解附近的精細(xì)搜索能力不足。本算法中Clsi基于當(dāng)前最差和最好的適應(yīng)值，cls_standard的選擇對算法整體性能有一定的影響，實(shí)驗(yàn)選取幾個不同的值，測試表1中函數(shù)的最優(yōu)值，平均值，平均方差和平均誤差值。

表3 MSAPO算法在不同參數(shù)下性能比較結(jié)果
Tab.3 The performance comparison results of MSAPO under different parameters

FuncCls_standardBestMeanSTDMean_errorSphere Function0.3-1.4000e+03-1.4000e+034.2298e-101.9463e-100.5-1.4000E+03-1.4000E+038.3226E-114.7066E-110.7-1.4000E+03-1.3907E+032.2787E+019.2907E+00Rotated Rosenbrock’s Function0.3-8.8469e+02-8.5381e+022.4726e+014.6187e+010.5-8.8492E+02-8.5874E+022.5519E+014.1264E+010.7-8.8510E+02-8.7796E+024.3128E+002.2035E+01Rotated Schaffers F7Function0.3-7.8512e+02-7.5826e+022.5490e+014.1737e+010.5-7.8956E+02-7.5823E+023.5565E+014.1766E+010.7-7.8872E+02-7.7323E+021.3612E+012.6773E+01Rotated Ackley’sFunction0.3-6.7916e+02-6.7906e+025.2205e-022.0936e+010.5-6.7910E+02-6.7905E+023.0341E-022.0950E+010.7-6.7911E+02-6.7903E+024.8177E-022.0970E+01Rotated Griewank’sFunction0.3-4.9994e+02-4.9984e+025.1473e-021.5896e-010.5-4.9995E+02-4.9984E+025.9681E-021.5627E-010.7-4.9995E+02-4.9988E+027.6477E-021.1633E-01Composition Function 1(n=5,Rotated)0.31.0000e+031.0431e+036.9338e+013.4306e+020.51.0000E+031.0287E+036.0524E+013.2871E+020.79.0000E+021.0474E+038.8151E+013.4742E+02

由表3的實(shí)驗(yàn)結(jié)果可得，對于簡單函數(shù)和復(fù)雜函數(shù)而言，隨著cls_standard的取值越大，算法性能變化不同。Cls_standard的取值關(guān)系到算法中不同運(yùn)動規(guī)則的個體個數(shù)，當(dāng)cls_standard的取值從0.3到0.5，簡單函數(shù)sphere的平均值有所下降，而對于基本多峰函數(shù)和復(fù)雜函數(shù)而言，除了Ackley函數(shù)，其他函數(shù)的平均值均有變差趨勢，但最優(yōu)適應(yīng)值都變好。這是因?yàn)楫?dāng)cls_standard的值越大，算法中被劃分為固態(tài)和液態(tài)的個體隨之減少，氣態(tài)個體隨之增加，算法越趨向于按照氣態(tài)個體的運(yùn)動規(guī)則進(jìn)行全局搜索，對多峰函數(shù)和復(fù)雜函數(shù)的尋優(yōu)影響較好，但可能會導(dǎo)致在潛在較好解附近的精細(xì)搜索不足，由此產(chǎn)生平均值結(jié)果變差的問題。當(dāng)cls_standard的取值從0.5到0.7變化時，尤其對于Rosenbrock和Schaffers F7這兩個典型的多峰函數(shù)，平均方差和平均誤差值均變小，說明較大的cls_standard值對于多峰函數(shù)的影響較好。

實(shí)驗(yàn)結(jié)果表明該算法在選取cls_standard的值時，需要選取適當(dāng)才能有效提高算法性能。這是由于MSAPO算法采用了多種運(yùn)動規(guī)則，對不同狀態(tài)的粒子采用不同的運(yùn)動規(guī)則，而cls_standard值的選取能有效平衡算法的全局搜索能力和局部搜索能力。當(dāng)cls_standard很小時，算法中做全局搜索的粒子較少，相反，當(dāng)cls_standard很大時，算法中做局部搜索的粒子較少。對于簡單函數(shù)而言，局部極小值較少，cls_standard值較小時容易找到最優(yōu)值且收斂較快，對于多峰函數(shù)局部極小值較多，過小或過大的cls_standard值都不利于提高算法的性能。在實(shí)際應(yīng)用中可以根據(jù)問題模型的復(fù)雜程度選擇cls_standard的值。

4 結(jié)論

本文在原擬態(tài)物理學(xué)優(yōu)化算法的基礎(chǔ)上引入多物態(tài)的概念，對不同的個體劃分不同的物態(tài)，并采用符合各物態(tài)運(yùn)動規(guī)律的運(yùn)動規(guī)則進(jìn)行尋優(yōu)。仿真實(shí)驗(yàn)表明該算法的有效性，后續(xù)工作將對MSAPO算法在求解最優(yōu)化問題時的平均最優(yōu)值精度進(jìn)行進(jìn)一步研究，通過引入環(huán)境因素，更合理地模擬物理學(xué)中分子的熱運(yùn)動現(xiàn)象，實(shí)現(xiàn)部分物態(tài)個體因環(huán)境變化而實(shí)現(xiàn)的狀態(tài)轉(zhuǎn)化，提高尋優(yōu)結(jié)果的精度，改善算法的時間復(fù)雜度。