容量約束p-中位問題（Capacitated P-Median Problem,CPMP）已被證明是一類計算機難以求解的具有NP-hard特性的組合優(yōu)化問題.本文提出一種多階段粒子群優(yōu)化算法（Multi-Phase Particle Swarm Optimization,MPPSO）及在算法設(shè)計中應(yīng)用模式有關(guān)理論和方法.所提MPPSO在標(biāo)準(zhǔn)PSO基礎(chǔ)上,考慮CPMP結(jié)構(gòu)特征信息,采用一種以字符編碼為基礎(chǔ)的結(jié)構(gòu)體編碼結(jié)構(gòu),重新定義粒子速度與位置更新方式.它將CPMP優(yōu)化求解分為種群粒子初始化階段及兩個優(yōu)化階段.在優(yōu)化求解第一階段,分析了慣性因子對所求問題編碼結(jié)構(gòu)粒子搜索的局限性,設(shè)計一種保留粒子最優(yōu)特征中位點信息的變異算子.以粒子全局搜索算子操作為重點,期望從整個搜索空間搜索到好的模式結(jié)構(gòu)分布特性的粒子.在優(yōu)化求解第二階段,對高適應(yīng)性粒子執(zhí)行一種改進的迭代局部搜索操作,達成對粒子精度的進一步提升.迭代局部搜索分為基本局部搜索和深層次局部搜索.基本局部搜索側(cè)重對粒子需求點和中位點提煉用于發(fā)現(xiàn)候選粒子相鄰的局部最優(yōu)解.在深層次局部搜索中,采用對粒子執(zhí)行擾動算子操作,使得算子操作在更大鄰域范圍... 

【文章來源】：計算機學(xué)報. 2020,43(06)北大核心EICSCD

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

【部分圖文】：

MPPSO流程圖

圖2至圖4所示為上述算法測試結(jié)果畫出的盒線圖．由圖可知，對3組不同的測試集用例，PI和PB算法得到的數(shù)據(jù)值要明顯優(yōu)于BPSO和PG．前面已經(jīng)提到，BPSO可認(rèn)為是一種求解CPMP問題的標(biāo)準(zhǔn)粒子群算法．在用PSO求解CPMP問題時，慣性因子的影響難以有效建立需求點連接的中位點變化的中間狀態(tài)的映射關(guān)系．這將影響粒子的全局搜索和局部提精效果，從而使算法得到所求問題解的精度不高．圖3 6個sjc測試用例對比測試箱線圖

6個sjc測試用例對比測試箱線圖

【參考文獻】：
期刊論文
[1]一種求解厭惡型p-中位問題的混合進化算法[J]. 林耿.  浙江大學(xué)學(xué)報(理學(xué)版). 2018(01)
[2]求解MinSAT問題的加強式格局檢測與子句加權(quán)算法[J]. 周俊萍,任雪亮,殷茜,李睿智,殷明浩.  計算機學(xué)報. 2018(04)
[3]帶投資約束p-中位問題的混合蟻群算法[J]. 李倩,張惠珍,Cesar Beltran-Royo.  計算機應(yīng)用研究. 2017(06)



本文編號：3435737