現(xiàn)實世界中的許多應(yīng)用與實值優(yōu)化問題緊密相關(guān).為了求解復(fù)雜的實值優(yōu)化問題,一些研究工作提出不同的元啟發(fā)式假設(shè)并設(shè)計相應(yīng)的搜索策略.在搜索解空間過程中,如何平衡探索解空間新區(qū)域（多樣化）與實現(xiàn)優(yōu)質(zhì)解利用（集約化）之間的關(guān)系,是提高元啟發(fā)式搜索算法性能的關(guān)鍵因素之一.特別地,負(fù)相關(guān)搜索（negatively correlated search, NCS）通過在搜索進程中引入負(fù)相關(guān)的搜索趨勢,促進了解的多樣性,有效改進了并行爬山算法的搜索性能.負(fù)相關(guān)搜索將每一個搜索進程的搜索行為建模為概率分布,在此基礎(chǔ)上,根據(jù)搜索進程的搜索范圍的相對大小,將搜索行為進一步劃分為全局搜索行為和局部搜索行為.然后提出一種新的元啟發(fā)式搜索算法,即非對稱負(fù)相關(guān)搜索（negatively correlated search with asymmetry, NSA）,它假設(shè)具有全局搜索行為的搜索進程應(yīng)盡可能遠(yuǎn)離具有局部搜索行為的搜索進程.得益于搜索進程之間非對稱的負(fù)相關(guān)的搜索趨勢,提出的算法相比負(fù)相關(guān)搜索擁有更優(yōu)的搜索效率.實驗結(jié)果表明:相比成熟的搜索方法,非對稱負(fù)相關(guān)搜索在20個多模態(tài)實值優(yōu)化問題上取得了最佳的整體性能... 

【文章來源】：計算機研究與發(fā)展. 2019,56(08)北大核心EICSCD

【文章頁數(shù)】：12 頁

【部分圖文】：

圖２二維解空間（標(biāo)注等高線）的搜索示例Ｆｉｇ．２Ｉｌｌｕｓｔｒａｔｉｏｎｏｆｓｅａｒｃｈｂｅｈａｖｉｏｒｓｉｎａｔｗｏ－ｄｉｍｅｎｓｉｏｎａｌｓｅａｒｃｈｓｐａｃｅ

過種群大小，所以對大種群更友好的元啟發(fā)式搜索并行化潛力更大，通常是更被青睞的算法．特別地，基于種群的搜索算法通常因為個體間頻繁的信息交流與現(xiàn)實中昂貴的通信代價，導(dǎo)致并行化效率較低，無法謀求以種群規(guī)模交換迭代輪數(shù)的目的［２９］，因此消除個體之間不必要的通信可以很好地釋放算法的并行潛力．這里設(shè)計實驗研究了非對稱負(fù)相關(guān)搜索在并行化方面的性能，并與負(fù)相關(guān)搜索進行比較．具體地，采用細(xì)粒度的“主－從模型”作為并行框架［３０］，如圖５所示，主機負(fù)責(zé)控制搜索流程，每個計算單元享有一個獨立的搜索進程，搜索進程之間的通信由主機轉(zhuǎn)接．實驗硬件環(huán)境為英特爾至強多核服務(wù)器集群，軟件環(huán)境為Ｍａｔｌａｂ分布式計算系統(tǒng)．設(shè)定搜索算法的種群大小從１０增大到１００，相應(yīng)地計算單元由１０個擴充到１００個，并且保持搜索算法在生成３０００００個候選解時終止，也就是說迭代輪數(shù)從３００００輪減少到３０００輪，記錄下平均函數(shù)誤差與算法運行時間的變化．Ｆｉｇ．５Ｆｉｎｅ－ｇａｉｎｅｄＭａｓｔｅｒ－Ｓｌａｖｅｓｐａｒａｌｌｅｌｆｒａｍｅｗｏｒｋ圖５細(xì)粒度的“主－從模型”并行框架在３０維基準(zhǔn)測試函數(shù)Ｆ７上的結(jié)果如圖６和圖７所示．通過觀察圖６可以得到，對于最小化基準(zhǔn)測試函數(shù)，我們保持搜索算法生成候選解的個數(shù)，在犧牲迭代輪數(shù)的同時擴大種群的規(guī)模，搜索算法的性能受到不同程度上的影響．其中，非對稱負(fù)相關(guān)搜索對于種群規(guī)模較大的情況適應(yīng)較好，負(fù)相關(guān)搜索在種群規(guī)模極大的情況搜索

Ｍａｔｌａｂ分布式計算系統(tǒng)．設(shè)定搜索算法的種群大小從１０增大到１００，相應(yīng)地計算單元由１０個擴充到１００個，并且保持搜索算法在生成３０００００個候選解時終止，也就是說迭代輪數(shù)從３００００輪減少到３０００輪，記錄下平均函數(shù)誤差與算法運行時間的變化．Ｆｉｇ．５Ｆｉｎｅ－ｇａｉｎｅｄＭａｓｔｅｒ－Ｓｌａｖｅｓｐａｒａｌｌｅｌｆｒａｍｅｗｏｒｋ圖５細(xì)粒度的“主－從模型”并行框架在３０維基準(zhǔn)測試函數(shù)Ｆ７上的結(jié)果如圖６和圖７所示．通過觀察圖６可以得到，對于最小化基準(zhǔn)測試函數(shù)，我們保持搜索算法生成候選解的個數(shù)，在犧牲迭代輪數(shù)的同時擴大種群的規(guī)模，搜索算法的性能受到不同程度上的影響．其中，非對稱負(fù)相關(guān)搜索對于種群規(guī)模較大的情況適應(yīng)較好，負(fù)相關(guān)搜索在種群規(guī)模極大的情況搜索性能急劇下降，兩者的相對差值呈多項函數(shù)趨勢．這是由于負(fù)相關(guān)搜索在種群規(guī)模極大的情況容易出現(xiàn)因負(fù)相關(guān)產(chǎn)生的擁擠現(xiàn)象，也就是說個體集中在局部極值點附近且流通性較差．非對稱負(fù)相關(guān)的元啟發(fā)式假設(shè)只關(guān)注全局搜索行為，促進了個體的流通，有效緩解了擁擠現(xiàn)象，對基于大種群的大規(guī)模并行環(huán)境更友好．通過觀察圖７可以得到，在生成候選解的個數(shù)不變的情況下，非對稱負(fù)相關(guān)搜索可以通過細(xì)粒度的并行化方法有效節(jié)約運行時間，并且種群規(guī)模越大，運行時間越短，這得益于隨著種群規(guī)模擴大時算法迭代輪數(shù)減少．同時，并行化負(fù)相關(guān)搜索的運行時間隨著種群規(guī)模的擴大反而急劇提升，這是由于種群規(guī)模擴大導(dǎo)致整體相關(guān)性的計算代價呈冪律提


本文編號：3444364