混合精英學(xué)習(xí)的分組APO算法

李云仙，謝麗萍，譚 瑛

(太原科技大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，太原 030024)

啟發(fā)式算法是基于客觀世界中的自然現(xiàn)象，而人類受大自然的啟發(fā)，提出一些用于解決各種復(fù)雜問題的啟發(fā)式算法。比如，模擬生物群體智能行為的群智能算法，微粒群算法[1]、蟻群算法、人工蜂群算法等，還有一類模擬物理原理的算法，模擬退火算法[2](SA)、擬態(tài)物理學(xué)算法(APO)等。針對微粒群算法的不足，研究者進(jìn)行了大量改進(jìn)，文獻(xiàn)[3]提出反向?qū)W習(xí)PSO算法，提高了種群多樣性。文獻(xiàn)[4]一種基于動態(tài)鄰居和變異因子的粒子群算法，粒子的學(xué)習(xí)跟隨自己的歷史經(jīng)驗和所有鄰居的經(jīng)驗，引入水平混合變異，提升粒子跳出局部最優(yōu)解的能力。文獻(xiàn)[5-6]提出一種擾動的精英反向?qū)W習(xí)PSO算法，算法引入反向策略，引導(dǎo)粒子向最優(yōu)解空間靠近，采用擾動增強算法局部探索能力。

借鑒PSO算法的改進(jìn)策略，本文以擬態(tài)物理學(xué)優(yōu)化[7-9](Artificial Physics Optimization, APO)為研究對象，對APO算法改進(jìn)。該算法是最新提出的一種基于群體尋優(yōu)的隨機搜索算法，它基于萬有引力定律定義個體之間的虛擬作用力，根據(jù)個體的適應(yīng)值優(yōu)劣制定個體間的引斥力規(guī)則，并在所制定的虛擬力規(guī)則的作用下在問題的可行域內(nèi)搜索全局最優(yōu)點。由于APO算法具有較強的全局搜索能力，且算法過程涉及的參數(shù)較少，增加了算法的魯棒性。但APO算法只遵循一種運動規(guī)則，過程單一，多樣性較差，易使算法陷入局部最優(yōu)，為此，本文提出混合精英學(xué)習(xí)的分組APO算法。

1 混合精英學(xué)習(xí)的分組APO算法

1.1 分組APO算法運動規(guī)則集的構(gòu)造

制定高效的作用力規(guī)則，為算法迭代過程中不同的個體分配不同的作用力規(guī)則[10]，挖掘更多的有效信息，來引導(dǎo)個體向更好地區(qū)域搜索是增強算法多樣性，提高APO性能的關(guān)鍵。鑒于此，構(gòu)造的規(guī)則集如下：

規(guī)則一：標(biāo)準(zhǔn)APO作用力規(guī)則即對組內(nèi)任意一個個體i，適應(yīng)值較好個體吸引適應(yīng)值較差個體，適應(yīng)值較差個體排斥適應(yīng)值較好個體。同時適應(yīng)值最優(yōu)個體具有絕對吸引力，吸引組內(nèi)其他所有個體，而其本身則不受組內(nèi)其他個體吸引或排斥。公式如下，其中xi,k,vi,k分別表示個體i在第k維的位置分量和速度分量，F(xiàn)ij,k為個體j對i在第k維的作用力，mi為個體i的質(zhì)量。個體i的質(zhì)量和個體j對i在第k維的作用力公式為:

(1)

?i≠j,i≠best,i,j=1,2...m

(2)

個體i在第k維所受其他個體合力公式為

(3)

個體i在第t+1代速度和位置公式分別為

vi,k(t+1)=wvi,k(t)+αFi,k/mi

(4)

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

(5)

規(guī)則二：運用模擬退火運動規(guī)則，對較優(yōu)個體鄰域進(jìn)行搜索。按照Metropolis準(zhǔn)則，若新的解比之前的優(yōu)，則接受并更新，否則，就使個體在一定概率范圍內(nèi)接受不好的解，可以探索更多潛在的搜索空間，提高算法的全局勘探能力。Metropolis 準(zhǔn)則：

T(t+1)=p*T(t)

(6)

模擬退火運動規(guī)則的速度和位置的更新公式如下：

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

?i≠best

(7)

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

(8)

規(guī)則三：擴展APO作用力規(guī)則即對組內(nèi)任意一個個體i，受比它適應(yīng)值好的歷史最優(yōu)個體的吸引，比它適應(yīng)值差的歷史最優(yōu)個體的排斥。

該規(guī)則有效地利用了其他個體的歷史最優(yōu)位置信息，提高了個體找到最優(yōu)值的概率。

如下公式：

其中pj,k表示個體歷史最優(yōu)位置。個體j對個體i在第k維的作用力和合力公式：

?i≠j,i≠best,i,j=1,2...m

(9)

(10)

1.2 種群多樣性策略

種群多樣性[11-14]的變化對算法性能有著重要的影響，因此，引入種群多樣性的概念，動態(tài)調(diào)整組內(nèi)個體的運動情況，使個體保持持續(xù)的進(jìn)化活力。

前期實時監(jiān)控組內(nèi)種群多樣性，以一定概率對適應(yīng)值較差個體反向?qū)W習(xí)，改善種群多樣性，后期種群多樣性變小，各組個體較為密集，相似性高，各組個體融合為一組進(jìn)行全局精細(xì)搜索，提高個體間的差異性，使種群多樣性回升，進(jìn)而搜索得到全局最優(yōu)點。計算種群多樣性的公式參考文獻(xiàn)[15]，N為種群大小，D為維度L為搜索空間對角線長度。

1.3 分組精英學(xué)習(xí)APO算法思想過程

APO算法具有很強的全局搜索能力，但是必須同時具有全局搜索能力和局部搜索能力才能使算法表現(xiàn)出良好的性能，此外，種群多樣性也是衡量算法好壞的重要標(biāo)準(zhǔn)，在算法過程中起著重要的作用。

因此，為了在整個進(jìn)化過程中兼顧全局和局部搜索，本文提出分組精英學(xué)習(xí)策略，各組在進(jìn)化前期運用規(guī)則一進(jìn)行若干代的局部搜索，保證前期有效的局部搜索，可以使個體在當(dāng)前較優(yōu)解附近的區(qū)域搜索充分，更好地尋找潛在的較優(yōu)解。后期由于各組間缺乏有效信息的交流，使得整個種群多樣性難以提高。為了保證種群多樣性，選出所有不在同一小鄰域范圍的最好個體組成精英個體進(jìn)行精英搜索，精英個體是匯聚種群中所有粒子優(yōu)秀信息的個體，精英個體所形成的搜索區(qū)域會收斂到全局最優(yōu)所形成的搜索區(qū)域，因此采用規(guī)則二進(jìn)行全局搜索，精英個體間共享各自的優(yōu)秀信息，同時也可作為其他個體溝通的中介，指導(dǎo)其他個體的學(xué)習(xí)，改善全局搜索能力，促進(jìn)算法快速收斂。精英個體的引入，能夠保證組內(nèi)組間協(xié)同搜索，防止種群個體受單一最優(yōu)個體的影響，迅速收斂聚集到某一局部最優(yōu)，在一定程度上提高了個體學(xué)習(xí)的靈活性。同時各組個體按照規(guī)則一圍繞各自的精英個體附近精細(xì)搜索若干代，提高最優(yōu)解的精度，改善算法的局部精細(xì)搜索能力。

該算法在前期組內(nèi)若干代的局部搜索，可能會使粒子間相似度較高，種群多樣性喪失，引入種群多樣性動態(tài)監(jiān)控各組運動趨勢，并運用反向?qū)W習(xí)策略反向搜索，給定一定的反向?qū)W習(xí)概率p，滿足如下公式(11)對較差個體評估其當(dāng)前解和反向解，從而更好地發(fā)掘潛在的較好解。后期收斂階段，各組融合為一組采用規(guī)則三(EAPO)進(jìn)行全局精細(xì)搜索，刺激種群多樣性回升，避免了局部最優(yōu)，使得較好的解進(jìn)入下一代搜索中，從而提高算法的尋優(yōu)能力。

(11)

1.4 算法實現(xiàn)

綜上所述，本文算法實現(xiàn)步驟如下

Step1：初始化種群，種群規(guī)模為N,分組個數(shù)d，每組粒子數(shù)m，種群多樣性闕值D0，鄰域半徑r，組內(nèi)迭代t1代，最大迭代代數(shù)tmax，令t=0，分別計算各組粒子的適應(yīng)值，保留各組最優(yōu)個體。

Step2：組內(nèi)學(xué)習(xí)。當(dāng)t≤t1代時，各組獨自進(jìn)化，根據(jù)文獻(xiàn)[15]公式計算各組種群多樣性D,若D>D0，根據(jù)公式(1)-(3)計算各組每個個體所受合力，根據(jù)適應(yīng)值函數(shù)，評價個體的適應(yīng)值，選出最優(yōu)個體和m/2較差個體，對各組較差個體根據(jù)公式(11)進(jìn)行反向?qū)W習(xí)，根據(jù)公式(4)、(5)更新各組個體的速度位置，對于各組每代產(chǎn)生的最優(yōu)個體，進(jìn)行最優(yōu)保留，t=t+1.若各組D

Step3：組間學(xué)習(xí)。當(dāng)t1+1≤t≤tmax時，對所有個體按照適應(yīng)值大小排序，選出不在同一小鄰域r的d個最優(yōu)個體(即精英個體)，以精英個體為中心，剩余個體隨機均分成d組。精英個體組成組間個體，按規(guī)則二運動，根據(jù)公式(6)(7)(8)更新精英個體的速度和位置，并保留歷史最優(yōu)和全局最優(yōu)。

Step4：對于組內(nèi)個體，按照step2各組分別在各自的精英個體周圍搜索k代，對每代產(chǎn)生的歷史最優(yōu)和全局最優(yōu)個體，進(jìn)行最優(yōu)保留。

Step5:若各組D

Step6：若t≤tmax，轉(zhuǎn)step3，直到滿足結(jié)束條件，終止算法并輸出所求的全局最優(yōu)值。

2 仿真結(jié)果及分析

為了測試該算法的性能，利用28個標(biāo)準(zhǔn)測試函數(shù)中14個函數(shù)(2個單峰函數(shù)(f1,f2)，9個多峰函數(shù)(f3-f11)，3個復(fù)雜函數(shù)(f12-f14))進(jìn)行仿真。

單峰函數(shù)Sphere, Different Powers.多峰函數(shù)RotatedRosenbrock’s,RotatedSchaffersF7,RotatedAckley’s ,RotatedGriewank’s,Rastrigin’s,RotatedRastrigin’s ,Non-ContinuousRotatedRastrigin’s,RotatedKatsuura,LunacekBi_Rastrigin.復(fù)雜函數(shù)CompositionFunction5(Rotated),CompositionFunction6 (Rotated) ,Composition Function8 (Rotated) .

算法的評價結(jié)果以搜索函數(shù)的最小值為目標(biāo)，函數(shù)最小值即為最優(yōu)值。其中best表示最優(yōu)(小)值，mean_best表示平均最優(yōu)(小)值，std表示標(biāo)準(zhǔn)方差。GEAPO與APO算法性能比較如下表(1)

表1 GEAPO與APO算法性能的比較
Tab.1 The performance comparison results of the algorithms GHAPO and APO

函數(shù)編號最優(yōu)值bestAPOmean_beststdbestGEAPOmean_beststdF1-1400-1.4000E+03-1.4000E+039.7019E-08-1.4000E+03-1.4000E+037.5791E-14F2-1000-7.2734E+02-5.2512E+022.1891E+02-1.0000E+03-1.0000E+039.2825e-14F3-900-8.8355E+02-8.5805E+022.6578E+01-8.9475E+02-8.9207E+021.5795E+00F4-800-6.4900E+02-6.1893E+022.1656E+01-7.9949E+02-7.9768E+021.4821E+00F5-700-6.7909E+02-6.7905E+023.0563E-02-6.7919E+02-6.7915E+023.4966E-02F6-500-4.9985E+02-4.9900E+027.0865E-01-4.9997E+02-4.9994E+022.6085E-02F7-400-3.7612E+02-3.6896E+027.6754E+00-3.9005e+02-3.8580e+023.3127E+00F8-300-2.7214E+02-2.5870E+021.2565E+01-2.8906E+02-2.8358E+024.0687E+00F9-200-1.4866e+02-9.5064e+014.3479e+01-1.6987e+02-1.5566e+029.2279e+00F102002.0189E+022.0259E+022.6584E-012.0131E+022.0187E+022.7758E-01F11 3003.4559E+023.6298E+027.7611E+003.3934E+023.4455E+023.1175E+00F1211001.3452E+031.3616E+031.1833E+011.3446E+031.3532E+037.7375E+00F1312001.4006E+031.4012E+035.1302E-011.4000E+031.4000E+034.5383E-03F1414003.7017E+033.9774E+031.6955E+021.7000E+031.7000E+033.9382E-13

從表分析可知，通過GEAPO算法與APO算法的比較發(fā)現(xiàn)，GEAPO算法中函數(shù)的最優(yōu)值，平均值和方差都優(yōu)于APO算法。該算法中單峰函數(shù)能精確收斂到全局最優(yōu)解，函數(shù)Rosenbrock ,Schaffers F7,Griewank,Rastrigin是典型的多峰函數(shù)，具有多個局部極值，很難找到全局最優(yōu)，但從表中均值結(jié)果來看，改進(jìn)算法能收斂到全局最優(yōu)解附近，搜索精度較高，說明本文算法具有很強的全局尋優(yōu)能力。對于復(fù)雜函數(shù)而言，由于函數(shù)圖像比較復(fù)雜，沒有特定的規(guī)律，解的精度提高變得相當(dāng)困難，因此，相對于單峰和多峰函數(shù)，復(fù)雜函數(shù)在求解的精度上較差一些。從方差對比來看，算法的穩(wěn)定性較好。所以，本文算法在整體性能上較優(yōu)，大部分函數(shù)在收斂精度上有較好的優(yōu)勢。

從算法的時間復(fù)雜度分析，APO 算法在每一代都會評價一次所有個體的適應(yīng)值，GEAPO算法對個體進(jìn)行了分組，對組間個體加入了模擬退火規(guī)則，在每一代中除了要評價每一個個體的適應(yīng)值，還要根據(jù)Metropolis準(zhǔn)則評價組間個體的適應(yīng)值，雖然時間頻度不同，但算法的時間復(fù)雜度相同。精英個體和反向?qū)W習(xí)的個體只是改變了學(xué)習(xí)方式，未增加額外的時間消耗和空間消耗，因此，改進(jìn)的算法在時間復(fù)雜度和空間復(fù)雜度方面是有效的,并未增加原APO的復(fù)雜度。

在大規(guī)模環(huán)境下，采用單一種群進(jìn)化，會耗費大量時間，而GEAPO算法采用分組策略，將種群分為若干個子種群，各子群獨自并行進(jìn)化，在分布式環(huán)境下運行會縮短所耗時間，增加種群多樣性。因此，從整體看，改進(jìn)算法在大規(guī)模數(shù)據(jù)優(yōu)化上，具有一定的應(yīng)用前景。

由此可知，分組反向?qū)W習(xí)，組間精英學(xué)習(xí)，引入種群多樣性指標(biāo)，確實增加了種群多樣性，平衡了全局和局部搜索能力，并且由于其運動規(guī)則的變化性，在整體性能上，優(yōu)于遵循單一規(guī)則的APO算法，改善了算法陷入局部最優(yōu)的缺點，提高了收斂精度。仿真實驗表明本文算法是有效的。

3 結(jié) 論

提出了分組精英學(xué)習(xí)的APO算法，通過分組策略，各組獨自進(jìn)化，組內(nèi)組間采用不同的作用力規(guī)則來達(dá)到尋優(yōu)的目的。引入精英個體進(jìn)行組間全局搜索更為優(yōu)秀的解，加強優(yōu)秀信息的共享，同時各個精英個體引導(dǎo)種群個體向全局最優(yōu)位置運動，防止個體受單一全局最優(yōu)影響迅速早熟收斂。組內(nèi)局部搜索采用反向?qū)W習(xí)策略和種群多樣性動態(tài)監(jiān)控個體的運動，避免個體緊密聚合，陷入早熟收斂，提高了種群多樣性，激活了個體的搜索活力。

仿真實驗表明，該算法整體性能上具有一定的優(yōu)勢，且穩(wěn)定性較好。算法的改進(jìn)是有效的。當(dāng)然，針對G的取值對算法性能影響較大的問題，可對參數(shù)G的設(shè)置進(jìn)行進(jìn)一步的研究探討，后期還需在并行環(huán)境下對大規(guī)模問題進(jìn)行研究，并將該算法用于求解有約束優(yōu)化問題，解決實際的工程問題