摘要
容量约束p-中位问题(Capacitated P-Median Problem,CPMP)已被证明是一类计算机难以求解的具有NP-hard特性的组合优化问题.本文提出一种多阶段粒子群优化算法(Multi-Phase Particle Swarm Optimization,MPPSO)及在算法设计中应用模式有关理论和方法.所提MPPSO在标准PSO基础上,考虑CPMP结构特征信息,采用一种以字符编码为基础的结构体编码结构,重新定义粒子速度与位置更新方式.它将CPMP优化求解分为种群粒子初始化阶段及两个优化阶段.在优化求解第一阶段,分析了惯性因子对所求问题编码结构粒子搜索的局限性,设计一种保留粒子最优特征中位点信息的变异算子.以粒子全局搜索算子操作为重点,期望从整个搜索空间搜索到好的模式结构分布特性的粒子.在优化求解第二阶段,对高适应性粒子执行一种改进的迭代局部搜索操作,达成对粒子精度的进一步提升.迭代局部搜索分为基本局部搜索和深层次局部搜索.基本局部搜索侧重对粒子需求点和中位点提炼用于发现候选粒子相邻的局部最优解.在深层次局部搜索中,采用对粒子执行扰动算子操作,使得算子操作在更大邻域范围内搜索粒子新的模式结构,从而发现蕴含高适应性模式结构的潜在更好解.文中提出模式范数及模式结构距离等概念,并将它们用于扰动算子设计.实验测试表明:MPPSO对4大类CPMP用例问题进行求解得到的实验数据,与4种文献对比算法提供的数据相比有一定优势,且能发现3个大数据集用例新的最好解.
The capacitated p-median problem(CPMP)is a combinatorial optimization problem.The CPMP can be described as a directed graph G=(V,A)where V is the demand points set and A is the arcs set,and the cost of each arc represents the distance between two demand points.Let M be the set of candidate median points which are selected form the set V.Each demand point needs a demand capacity q and each candidate median point provides a service capacity Q.The optimization goal is to find a set M with its each median belonging to the set V and to assign each demand point to only one median point so that the sum of the distances between the demand points and the median points is minimized.It can be seen that the CPMP is a type of center location problem,and it is also called a clustering problem.It has been proved a NP-hard problem which is unable to solve in polynomial time.A multi-phase particle swarm optimization(MPPSO)is proposed for solving CPMP,the relative schema theory and method are applied in MPPSO.In MPPSO,the update mode of velocity and position is redefined according to the structural feature information of CPMP.The proposed MPPSO is divided into an initialization phase and two optimization phases while solving in the CPMP.In the initialization phase,a initial solution distribution is obtained by a random initialization method.In the first optimization phase,a mutation operator with keeping on good gene features is designed on account of the limiting on inertia effect.Global search operations on the candidate particles are conducted to obtain good distribution characteristic of schema structure for the whole search areas.In the second optimization phase,an improved iterated local search procedure is performed on the particle with high adaptability to further improve the particle precision.Iterated local search procedure includes basic local search and deep-level local search.The basic local search focuses on performing several basic move operators on demand points and the median points of the particle to extract the optimal solution around the candidate particle.In the process of deep-level local search,the perturbation operators are used in a larger neighborhood to find the potentially better particle containing high adaptive schema structure.Furthermore,the schema theory is developed,structure norm and schema structure distance are proposed to measure the effectiveness of the operators’operation,and the time complexity of MPPSO is analyzed.To determine the performance of the algorithm,extensive experiments are carried out and four kinds of test instances of CPMP are shown.The proposed algorithm is compared with several state-of-the-art algorithms.The experimental results show that the proposed MPPSO which solves four kinds of CPMP has the better performance than four compared algorithms in literatures.Meanwhile,three new best solutions are found by the proposed MPPSO.In the future,we will improve the algorithm with respect to the principles and methods of the schema,and then introduce the algorithm to real application.
作者
王竹荣
薛伟
黑新宏
费蓉
伊珍珍
WANG Zhu-Rong;XUE Wei;HEI Xin-Hong;FEI Rong;YI Zhen-Zhen(School of Computer Science and Engineering,Xi’an University of Technology,Xi’an 710048;Shaanxi Key Laboratory for Network Computing and Security Technology,Xi’an 710048)
出处
《计算机学报》
EI
CSCD
北大核心
2020年第6期1139-1160,共22页
Chinese Journal of Computers
基金
国家重点研发计划(2018YFB1201500)
国家自然科学基金(61773313)
陕西省重点研发计划(2017ZDXM-GY-098)
陕西省教育厅重点实验室项目(17JS100)资助.
