基于多策略离散粒子群算法的容量约束P中位问题研究

发布时间：2020-05-21 00:37

【摘要】：容量约束P-中位问题(Capacitated P-Median Problem,CPMP)是一类由图演变的组合优化问题。CPMP在实际生产中有着广泛的应用背景,且已被证明是具有NP-hard特征的难解问题,随着问题规模增加,其时间计算复杂性呈指数级增长,精确的数学方法只能求解较小规模CPMP,而基于群搜索的启发式算法在求解大规模CPMP具有优势。粒子群优化算法(Particle Swarm Optimization,PSO)算法是一种模拟自然界鸟群活动及群体智能的随机搜索算法。该算法具有操作简单、易于实现、收敛速度快等优点。本文对CPMP及其特征进行分析,在标准粒子群优化算法基础上进行离散化改进,并在算法中增加不同的启发式策略,形成两种新的离散粒子群优化算法。为验证所提算法的性能,将算法用于求解一些公开CPMP数据集,并与一些知名算法测试结果进行对比分析。本文主要工作包括:(1)提出一种改进的离散粒子群优化算法(Improved Discrete Particle Swarm Optimization Algorithm,IDPSO)求解CPMP。在所提算法中,考虑CPMP的求解可分解为中位点选取和需求点分配两阶段。在算法中去掉速度更新操作,引进遗传算法的交叉、变异算子操作,增加粒子中位点在全局范围内的重组。在算法中加入变邻域局部搜索过程提升粒子质量,并设计了模拟退火接受机制用于保持种群多样性。最后将所提算法应用到20个公开CPMP测试用例中测试,并将实验数据与几种文献启发式算法得到的结果进行对比分析。(2)提出一种基于多启发式离散粒子群优化算法(Multiheuristics Discrete Particle Swarm Optimization,MDPSO)。在所提算法中,重新定义了粒子速度和位置更新方式。考虑CPMP的求解困难在于中位点的调整和变化,在算法中对中位点搜索采用了全局中位点选择,局部中位点调整以及深层次中位点调整方式,在算法中加入聚类思想对中位点择优选择操作、对需求点分配与调整局部搜索算子操作,使算法从多个维度达到对粒子中位点和需求点的选择和分配进行优化。最后,将所提算法应用于求解公开的20个小规模测试用例和6个较大规模测试用例,并与文献知名算法测试结果进行对比。综上,通过分析CPMP在求解中所表现的特征,设计了两种基于不同启发式信息的离散粒子群算法,理论分析和实验测试验证了所提算法的正确性和有效性。
【学位授予单位】：西安理工大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP18

【参考文献】

相关期刊论文 前10条

1 孙文彬;闫志远;赵学胜;;基于网络分割的P-中位问题求解方法[J];中国矿业大学学报;2016年06期

2 李倩;张惠珍;Cesar Beltran-Royo;;带投资约束p-中位问题的混合蚁群算法[J];计算机应用研究;2017年06期

3 黄利;杜伟伟;丁立新;;基于Sigmoid惯性权重自适应调整的粒子群优化算法[J];计算机应用研究;2012年01期

4 徐先瑞;李响;李小杰;;改进的求解约束P-Median问题的分散搜索算法[J];计算机工程与应用;2011年20期

5 迟玉红;孙富春;王维军;喻春明;;基于空间缩放和吸引子的粒子群优化算法[J];计算机学报;2011年01期

6 李芬;徐国虎;;基于遗传算法的配送中心选址问题求解[J];商品储运与养护;2007年03期

7 李有梅,陈晔;一种新的求解约束P-中位问题的启发式算法[J];计算机工程;2005年19期

8 窦全胜,周春光,马铭;粒子群优化的两种改进策略[J];计算机研究与发展;2005年05期

9 李宁,刘飞,孙德宝;基于带变异算子粒子群优化算法的约束布局优化研究[J];计算机学报;2004年07期

10 高鹰,谢胜利;免疫粒子群优化算法[J];计算机工程与应用;2004年06期

相关硕士学位论文 前2条

1 路凤敏;几种离散选址模型的算法研究[D];南京航空航天大学;2010年

2 吴仆;设施选址中的一些模型与算法[D];南京航空航天大学;2010年

，

本文编号：2673455