發(fā)布時(shí)間：2021-10-14 07:43

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

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

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

【部分圖文】：

MPPSO流程圖

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

6個(gè)sjc測(cè)試用例對(duì)比測(cè)試箱線圖

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



本文編號(hào)：3435737