新颖的离散差分演化算法求解无容量设施选址问题

Novel Discrete Differential Evolution Algorithm for Uncapacitated Facility Location Problem

无容量设施选址问题(UFLP)是定位理论中最重要的NP-hard问题之一,在公共设施选址和物流资源分配方面有重要的应用价值和理论意义。为了利用差分演化(DE)高效求解UFLP问题,本文首先提出了一个新型转换函数(Ntf),通过Ntf将DE中个体的实向量映射为一个二进制向量。然后,基于新型转换函数给出了一种新的离散差分演化算法(记为N-DisDE),并利用N-DisDE提出了求解UFLP的一个新的高效方法。本文利用N-DisDE求解来自OR-Library中的15个不同规模的UFLP实例,并将计算结果与具有混合编码的二进制差分演化算法(HBDE)和二进制粒子群优化(BPSO)的计算结果进行比较,计算结果表明:N-DisDE在求解质量和鲁棒性等方面均优于其它方法。

The uncapacitated facility location problem(UFLP)is one of the most important NP-hard problems in location theory.It has important application value and theoretical significance in public facilities location and logistics resource allocation.In order to efficiently solve the UFLP by using differential evolution algorithm,a novel transfer function(Ntf)is proposed firstly.The real vector of an individual is mapped to a binary vector by Ntf.Then,a new discrete differential evolution algorithm(named N-DisDE)is given by using the novel transfer function.And a new and efficient method for solving UFLP is proposed by using N-DisDE.In this paper,N-DisDE is used to solve 15 UFLP instances of different sizes from OR-Library,and the calculated results are compared with those of binary differential evolution algorithm with hybrid coding(HBDE)and binary particle swarm optimization(BPSO).The results show that N-DisDE is superior to other algorithms in solution quality and robustness.