多物態擬態物理學優化算法

安澤曄，謝麗萍

(太原科技大學計算機科學與技術學院，太原 030014)

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

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

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

1 標準APO算法

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

(1)

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

(2)

最后更新個體運動的速度和位置。

?i≠best

(3)

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

(4)

其算法流程如下：

Step1：初始化種群的個體位置和速度，并計算適應值，保留算法的最優適應值及最優個體；

Step2：計算個體質量及個體所受合力；

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

Step4：計算個體適應值，更新最優個體及其適應值；

Step5：判斷是否滿足程序結束條件，若滿足，則輸出最優結果并結束程序，否則返回Step2，繼續迭代。

2 多物態擬態物理學算法的融合

多物態物理學算法的融合主要包括三個部分：初始化種群，物態劃分，計算不同物態的個體運動。初始化種群后，按一定的劃分標準劃分固態，液態和氣態個體，首先分離出氣態個體，然后根據其他個體與選出的中心點個體間的距離設定固態和液態的鄰域集合，集合內含兩個或兩個以上的個體歸為固態集合，只有一個個體的歸為液態集合。物態劃分后，個體按不同的運動規則更新速度和位置，計算每個個體的適應值，然后根據個體的適應值及環境，判斷某些個體的物態是否需要發生變化，若需要，則重新劃分物態，并按相應的運動規則進行運動。

2.1 運動規則

本文根據不同物態的個體運動規律不同，選用了三種不同的運動規則。

規則一：標準APO算法的運動規則

規則二：仿照模擬退火算法的單點運動規則。

速度和位置計算公式如下

?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)

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

(7)

(8)

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

(9)

2.2 物態劃分方法

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

(10)

當xi適應值較大，clsi較小，將該個體設為氣態個體，用于全局搜索；當xi適應值較小，clsi較大，將該個體設為固態或液態個體，用于局部搜索。

該算法中取cls_standard為劃分的標準參數，當個體的clsi>cls_standard時，劃分為固態或液態個體，相反劃分為氣態個體。該標準基于每一代適應值的最大值和最小值，用較為相對的標準劃分物態，增加了物態劃分的合理性。

算法描述

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

Step1：初始化。在可行域內均勻產生個體的位置與速度，并計算相應的適應值，保留最優個體及其適應值。

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

Step3：各集合按相應的運動規則運動一次。每個固態集合都按照規則一運動，液態個體按照規則二運動，氣態個體按照規則三運動。

Step4：計算適應值，保留最優個體及適應值。判斷是否達到結束條件，是則結束運行并輸出結果，否則返回步驟2.

3 實例仿真

為了測試上述方案的可行性，選用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)六個測試函數。這些測試函數的參數如表1所示，其中問題維數(n)、函數的搜索空間(Search range)、函數的已知最有值(Known optimum)、算法使用的種群規模(Npop)以及算法迭代的最大代數(MAX-ITER)已列出。

表1 測試函數參數列表
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算法性能分析

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

表2 APO、MSAPO算法性能比較結果
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給出了相同代數下所測函數在APO與MSAPO算法下的對比實驗結果。MSAPO算法在以上六個測試函數中找到的最優適應值均比APO算法好或者相等，其性能整體上也優于APO算法。其中，復雜函數Composition在MSAPO算法下的最優值比APO算法要差一些，但平均值和標準方差均優于APO算法。其他基本多峰函數在MSAPO算法下的性能都相對較好，除了Rotated Schaffers F7 函數，其在MSAPO算法下的標準方差和平均誤差值較APO差。

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

3.2 物態劃分標準參數對算法的影響

在引入物態劃分的APO算法中，物態劃分的標準參數為種群中各物態的個體個數分布比例情況提供了重要信息，其選擇的好壞能夠影響APO算法的性能。實驗通過研究該物態劃分標準參數的選擇策略判斷對算法性能的影響。

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

表3 MSAPO算法在不同參數下性能比較結果
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的實驗結果可得，對于簡單函數和復雜函數而言，隨著cls_standard的取值越大，算法性能變化不同。Cls_standard的取值關系到算法中不同運動規則的個體個數，當cls_standard的取值從0.3到0.5，簡單函數sphere的平均值有所下降，而對于基本多峰函數和復雜函數而言，除了Ackley函數，其他函數的平均值均有變差趨勢，但最優適應值都變好。這是因為當cls_standard的值越大，算法中被劃分為固態和液態的個體隨之減少，氣態個體隨之增加，算法越趨向于按照氣態個體的運動規則進行全局搜索，對多峰函數和復雜函數的尋優影響較好，但可能會導致在潛在較好解附近的精細搜索不足，由此產生平均值結果變差的問題。當cls_standard的取值從0.5到0.7變化時，尤其對于Rosenbrock和Schaffers F7這兩個典型的多峰函數，平均方差和平均誤差值均變小，說明較大的cls_standard值對于多峰函數的影響較好。

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

4 結論

本文在原擬態物理學優化算法的基礎上引入多物態的概念，對不同的個體劃分不同的物態，并采用符合各物態運動規律的運動規則進行尋優。仿真實驗表明該算法的有效性，后續工作將對MSAPO算法在求解最優化問題時的平均最優值精度進行進一步研究，通過引入環境因素，更合理地模擬物理學中分子的熱運動現象，實現部分物態個體因環境變化而實現的狀態轉化，提高尋優結果的精度，改善算法的時間復雜度。