李云仙，謝麗萍，譚 瑛

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

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

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

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

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

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

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

(1)

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

(2)

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

(3)

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

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

(6)

模擬退火運(yùn)動(dòng)規(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ī)則三：擴(kuò)展APO作用力規(guī)則即對(duì)組內(nèi)任意一個(gè)個(gè)體i，受比它適應(yīng)值好的歷史最優(yōu)個(gè)體的吸引，比它適應(yīng)值差的歷史最優(yōu)個(gè)體的排斥。

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

如下公式：

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

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

(9)

(10)

1.2 種群多樣性策略

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

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

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

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

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

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

(11)

1.4 算法實(shí)現(xiàn)

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

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

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

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

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

Step5:若各組D

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

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

為了測(cè)試該算法的性能，利用28個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)中14個(gè)函數(shù)(2個(gè)單峰函數(shù)(f1,f2)，9個(gè)多峰函數(shù)(f3-f11)，3個(gè)復(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) .

算法的評(píng)價(jià)結(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ù)編號(hào)最優(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

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

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

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

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

3 結(jié) 論

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

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