多阶段粒子群优化算法求解容量约束p-中位问题

发布时间：2021-10-14 07:43

　　容量约束p-中位问题（Capacitated P-Median Problem,CPMP）已被证明是一类计算机难以求解的具有NP-hard特性的组合优化问题.本文提出一种多阶段粒子群优化算法（Multi-Phase Particle Swarm Optimization,MPPSO）及在算法设计中应用模式有关理论和方法.所提MPPSO在标准PSO基础上,考虑CPMP结构特征信息,采用一种以字符编码为基础的结构体编码结构,重新定义粒子速度与位置更新方式.它将CPMP优化求解分为种群粒子初始化阶段及两个优化阶段.在优化求解第一阶段,分析了惯性因子对所求问题编码结构粒子搜索的局限性,设计一种保留粒子最优特征中位点信息的变异算子.以粒子全局搜索算子操作为重点,期望从整个搜索空间搜索到好的模式结构分布特性的粒子.在优化求解第二阶段,对高适应性粒子执行一种改进的迭代局部搜索操作,达成对粒子精度的进一步提升.迭代局部搜索分为基本局部搜索和深层次局部搜索.基本局部搜索侧重对粒子需求点和中位点提炼用于发现候选粒子相邻的局部最优解.在深层次局部搜索中,采用对粒子执行扰动算子操作,使得算子操作在更大邻域范围... 

【文章来源】：计算机学报. 2020,43(06)北大核心EICSCD

【文章页数】：22 页

【部分图文】：

MPPSO流程图

图2至图4所示为上述算法测试结果画出的盒线图．由图可知，对3组不同的测试集用例，PI和PB算法得到的数据值要明显优于BPSO和PG．前面已经提到，BPSO可认为是一种求解CPMP问题的标准粒子群算法．在用PSO求解CPMP问题时，惯性因子的影响难以有效建立需求点连接的中位点变化的中间状态的映射关系．这将影响粒子的全局搜索和局部提精效果，从而使算法得到所求问题解的精度不高．图3 6个sjc测试用例对比测试箱线图

6个sjc测试用例对比测试箱线图

【参考文献】：
期刊论文
[1]一种求解厌恶型p-中位问题的混合进化算法[J]. 林耿.  浙江大学学报(理学版). 2018(01)
[2]求解MinSAT问题的加强式格局检测与子句加权算法[J]. 周俊萍,任雪亮,殷茜,李睿智,殷明浩.  计算机学报. 2018(04)
[3]带投资约束p-中位问题的混合蚁群算法[J]. 李倩,张惠珍,Cesar Beltran-Royo.  计算机应用研究. 2017(06)



本文编号：3435737