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

张发展，张 潼

(河北地质大学 信息工程学院，河北 石家庄 050031)

0 引言

无容量设施选址问题（UFLP）[1]是由Kuehn和Hamburger于1963年首次提出的一个重要的组合优化问题。UFLP不仅对于学校、工厂、仓库、消防站、医院等基础设施的选址具有重要的应用价值[2-3]，而且在资源配置、资金预算、物流运输、计算机网络和计算机视觉等领域具有重要的理论意义[4-7]。

近年来，国内外学者对 UFLP的求解算法进行了广泛的研究。Galvão和Raggi[8]提出了一种求解UFLP一般0-1公式的三阶段精确方法。Conn和 CornuéJols[9]提出了一种基于凝聚对偶的正交精确解求解超线性规划的新方法投影，并用于求解UFLP问题。Charikar和Guha[10]提出了一种简单的贪婪局部搜索算法，在 (2/ )O n∊时间内达到了2.414+∊的近似比。Takaya等人[11]和Atta[12]等人先后提出了利用萤火虫算法（FA）和猴群算法（MA）求解UFLP的方法，但是他们都没有给出大规模UFLP实例的计算结果。通过上述文献可以看出，精确算法在求解大规模UFLP实例时是非常耗费时间的，而非精确算法尤其是演化算法的求解速度远远快于精确算法。目前，如何利用演化算法快速高效地求解UFLP已经成为一个热点问题。因此，本文研究如何利用DE求解UFLP问题，本文首先提出了一个新型传递函数Ntf，将DE中的个体的实向量转换为二进制向量，以适用于直接求解二元优化问题。然后基于 Ntf给出了一种新的离散差分演化算法（N-DisDE），并利用N-DisDE提出了求解UFLP的一个新的高效方法。

1 UFLP 问题的定义和数学模型

UFLP的定义一般描述为：给定客户的集合K= {k1,k2,… ,kn}，其中m为客户的数量，ki表示第i个客户。给定可以开放的设施集合S={s1,s2,… ,sn}，其中n为设施数量，sj表示第j个设施。……