2024年3月9日发(作者：蔡悦可)
求解无容量设施选址问题的混合蚁群算法
李倩;张惠珍;Cesar Beltran-Royo
【摘 要】无容量设施选址(UFL)问题是经典的优化问题,属于NP难题,易于描述却
难于求解.首先,介绍了UFL问题的数学模型,并对UFL问题的特点进行深入分析,得
到其最优解所具有的基本特征;其次,针对UFL问题的最优解所具有的基本特征,设
计了两种局部搜索策略,并将其与基本蚁群算法相结合,提出了一种用于求解UFL问
题的混合蚁群搜索算法;最后,为了测试该算法的性能,分别利用混合蚁群算法和基本
蚁群算法求解UFL问题基准问题库中的16个测试算例.计算结果表明,混合蚁群算
法有效改进了基本蚁群算法求解UFL问题时易陷入局部最优、收敛速度慢等不足,
该算法对求解UFL问题具有明显的可行性和有效性.
【期刊名称】《上海理工大学学报》
【年(卷),期】2016(038)004
【总页数】6页(P367-372)
【关键词】无容量设施选址问题;蚁群算法;局部搜索
【作 者】李倩;张惠珍;Cesar Beltran-Royo
【作者单位】上海理工大学管理学院,上海200093;上海理工大学管理学院,上海
200093;西班牙胡安卡洛斯大学统计与运筹系,马德里
【正文语种】中 文
【中图分类】TP183
无容量设施选址问题(uncapacitated facility location,UFL)是从没有限定容量大小
的设施位置集合中选择要开放的设施,使其以最小的代价服务于给定的所有客户.无
容量设施选址问题具有广泛的实际应用背景,生活中许多实际的问题均可被抽象为
UFL问题进行求解,如银行选址、网络设计、聚类分析、证券投资管理等.
目前,用于求解UFL问题的算法大致可以分为3类:近似算法、精确算法和智能优化
算法.在多项式时间内能够求得问题的一个解,并且其目标函数值与最优解的目标函
数值之比不超过一个常数的算法被称为近似算法[1].1997年,Williamson等[2]给
出了求解设施选址问题的第一个常数近似度算法;2013年,Li[3]提出了求解UFL问
题的1.488-近似算法.求解UFL问题的精确算法主要有:割平面算法、列生成算法、
Erlenkotters算法[4]、分支定界法[5-6]等.这些算法能够求得问题的最优解,但适用
于规模较小的问题,且计算速度慢.虽然智能优化算法搜索效率高,适用于求解大规模
的问题,但是这些算法容易陷入局部最优,一般情况下只能求得问题的满意解,不一定
是最优解.为了克服单一智能优化算法易陷入局部最优、收敛速度慢等不足之处,近
年来求解UFL问题的混合智能优化算法得到了长足的发展,如:混合多层启发式算法
[7]、并行多粒子群优化算法[8]、优化启发式算法[9]、启发式并行局部搜索算法
[10]等.
蚁群算法(ant colony algorithm,ACA)具有鲁棒性强、可以进行分布式计算、易与
其他算法有效结合等优点,但其容易陷入局部最优[11].针对UFL问题的具体特点,将
两种局部搜索策略与基本蚁群算法相融合[12-13],提出了一种求解UFL问题的混合
蚁群算法,并通过求解系列经典UFL问题验证该算法的求解性能.
给定建造无容量限制的设施位置集M={1,…,m},客户集N={1,…,n},对于任意给定的
i∈N和j∈M,cij表示客户i与设施j之间的运输费用,fj>0表示设施j的开放费用.
要求每个客户必须选择一个且只能选择一个设施来满足其需求,同时使总费用最
少.UFL问题的数学模型可被描述为
式中:z为目标函数值,即总费用;yj表示设施j是否开放,如果设施j选择开放,则yj=1,
否则yj=0;xij表示客户i是否选择设施j为其提供服务,如果客户i选择设施j为其
提供服务,则xij=1,否则xij=0.
记X*为UFL问题(1)～(5)的最优解集,分析UFL问题的具体特点,可以得到定理1.
定理1 设(x*,y*)∈X*为最优解集中的一个解,记,对于∀j∈J,记,则存在:
a.
b. 给定∀i∈Ij,则.
证明 a. 假定存在,使得下式成立:
则可定义给定的UFL问题的解)为
计算使下式成立的j″:
并令和,可得
这与(x*,y*)∈X*相矛盾.
b. 对于给定的j0∈J,假定存在i0∈Ij0,使得.计算使下式成立的j″:
并定义给定的UFL问题的解)为
显然,ci0j0xi0j0>ci0j″xi0j″⟹,这与(x*,y*)∈X*相矛盾.
(x*,y*)为所求UFL问题的任一最优解,Ij为该最优解中设施j所服务的客户集合,定
理1说明了UFL问题的最优解所具有的两个特点:a.设施j为集合Ij中所有客户的
服务费用之和小于或等于其他任一设施j′(j′∈M)为集合Ij中的客户提供服务的费
用之和;b.任一客户始终选择与其运输费用最小的已开放设施.
根据定理1,可将给定UFL问题的任一可行解(x,y)进行如下改进:a.该解中,若已开放
的设施j为集合Ij中所有客户的服务费用之和大于设施j′(j′∈M)为集合Ij中的客户
提供服务的费用之和,则可关闭设施j,而开放设施j′,并令j′服务Ij中的所有客户;b.设
施j和j′均为开放设施,且设施j服务客户i,即xij=1,若cij>cij′,则可将客户i的服务
设施j改变为设施j′,即令xij=0,xij′=1.记将(x,y)经过这两种改进后的可行解为),显
然,)所对应的目标函数值小于(x,y)所对应的目标函数值.
2.1 基本蚁群算法
蚁群算法是一种源于大自然中生物世界的新的仿生类算法,属于随机型搜索算法.其
基本原理来自于昆虫学家们对生物界中蚂蚁搜索食物源的过程的观察:蚂蚁在搜索
食物时,能在其经过的路径上释放一种蚂蚁特有的分泌物——信息素,使得其他蚂蚁
可以感知并且影响其行为.当选择某些路径的蚂蚁越来越多时,该路径上累积的信息
素就越多,以致后来蚂蚁选择该路径的概率也越高,也就增加了该路径的吸引强度,依
靠这种生物机制,蚂蚁最终可以找到一条到达食物源的最短路线.本文将这种蚂蚁群
体寻优思想作一些修改和引申,以便符合所要求解的UFL问题.
将目标函数值作为每只蚂蚁k的评价值.对于客户1,将[1,m]区间内产生的一个随机
整数作为蚂蚁k为客户1所选择的设施.对于其他客户i(1 随机数q,若q≤q0(0 否则,利用式(7)计算蚂蚁k选择设施j的概率及其累积概率,并采用轮盘赌法确定所 选设施. 式中:M={1,…,m}为设施位置集合为启发函数,表示蚂蚁k在客户i处选择设施j的 期望程度,通过蚂蚁k给前(i-1)个客户提供服务所开放的设施费用及配送费用之和 来计算;τij为客户i与设施j之间的信息素;α为信息素重要程度因子,其值越大,表示 信息素的浓度在选择过程中所起的作用越大;β为启发函数重要程度因子,其值越大, 表示启发函数在选择过程中所起的作用越大. 表1表示了蚂蚁k为客户i选择设施时,10个设施处的概率和累积概率.当q>q0时, 将随机数q作为选择指针来确定蚂蚁k在客户i处的被选设施.如:q0=0.15和 q=0.63时,蚂蚁k在客户i处的被选设施为5. 随着时间的推移,蚂蚁在路径上留下的信息素逐渐衰减.记信息素衰减系数为 ρ(0<ρ<1),蚂蚁完成一次循环后,利用式(8)更新信息素为 式中,表示蚂蚁k在本次循环过程中留在客户i和设施j之间的信息素.选择应用 Ant-Cycle模型计算为 式中:Q为常数;zk为蚂蚁k在本次循环中的目标函数值. 2.2 局部搜索 在定理1的基础上,设计了两种求解UFL问题的局部搜索策略,并将其嵌入蚁群优化 算法,以有效改进由蚁群算法所求得的UFL问题的可行解.下面通过一个例子来对两 种局部搜索策略进行简要介绍. 例 给定一个m=5和n=5的UFL问题,该问题中客户与设施之间的运输费用矩阵 C和设施安装费用向量F分别为 F=[130,199,139,127,103] 该问题的最优目标函数值为1 034.假设蚂蚁算法中l只蚂蚁搜索一次所得的满意解 为:x14=1,x23=1,x32=1,x42=1,x55=1,y1=0,y2=1,y3=1,y4=1,y5=1.即:开放的 设施集合为{2,3,4,5};客户1选择设施4;客户2选择设施3;客户3和4选择设施2; 客户5选择设施5;总费用为199+139+127+103+1 224+1 749+1 227+1 783+1 149=7 700. 利用两种局部搜索策略对上述蚂蚁算法的求解结果改进如下: 策略1 以设施2所服务的客户3和4为例,客户集{3,4}分别被各个设施服务的费 用为 设施1 c31+c41+f1=1 488+1 235+130=2 853; 设施2 c32+c42+f2=1 227+1 783+199=3 209; 设施3 c33+c43+f3=1 240+1 831+139=3 210; 设施4 c34+c44+f4=121+1 340+127=1 588; 设施5 c35+c45+f5=1 375+112+103=1 590. 由上述计算结果及定理1可知,若客户3和4选择为其服务费用最小的设施4,则可 使蚂蚁算法的求解结果得以改进,则令x32=0,x42=0,x34=1,x44=1,y2=0,y4=1.改 进后的结果为x14=1,x23=1,x34=1,x44=1,x55=1,y1=0,y2=0,y3=1,y4=1,y5=1, 目标函数值计算结果为v=5 952. 策略2 蚂蚁算法的求解结果经策略1改进后,开放的设施集合为{3,4,5}.由定理1 知:给定开放的设施集合,每个客户应选择运输费用最小的开放设施为其服务. 客户1 由min {c13,c14,c15}=min {1 354,1 224,192}=192得设施5应为客户 1提供服务,则令x14=0,x15=1; 客户2 由min (c23,c24,c25)=min (1 749,132,1 439)=132得设施4应为客户 2提供服务,则令x23=0,x24=1; 客户3 由min (c33,c34,c35)=min (1 240,121,1 375)=121得客户3的服务设 施保持不变,仍为设施4,即x34=1; 客户4 由min (c43,c44,c45)=min (1 831,1 340,112)=112得设施5应为客户 4提供服务,则令x44=0,x45=1; 客户5 由min (c53,c54,c55)=min (108,1 004,1 149)=108得设施3应为客户 5提供服务,则令x55=0,x53=1. 经策略2改进后的结果为 x15=1,x24=1,x34=1,x45=1,x53=1,y1=0,y2=0,y3=1,y4=1,y5=1,v=1 034.显然, 蚂蚁算法的计算结果经策略1和策略2得到了明显改进. 2.3 混合蚁群算法 将基本蚁群算法和两种局部搜索策略相结合,提出了求解UFL问题的混合蚁群算法. 算法具体步骤为: Step 1 初始化蚂蚁个数b、反映信息素重要程度的因子α、反映启发函数重要程 度的因子β、信息素衰减因子ρ、常数q0和Q、最大迭代次数N和信息素矩阵 T=(τij)N×M,令迭代次数nc=1,蚂蚁编号k=1和满意解的目标函数值v=+; Step 2 将[1,m]区间内产生的一个随机整数作为蚂蚁k为客户1所选择的设施,根 据式(6)和式(7)为蚂蚁k的其他客户选择一个设施; Step 3 若k Step 4 运用两种局部搜索方法对蚂蚁的本次搜索结果进行改进; Step 5 更新当前满意解及其所对应的目标函数值v; Step 6 根据式(8)更新信息素矩阵; Step 7 令Δτij=0(i∈N,j∈M)和nc=nc+1; Step 8 若nc≤N,则转Step 2;否则,结束搜索,并输出结果. 为验证混合蚁群算法的可行性及其求解性能,采用两组UFL基准问题库中的16个 算例(每个算例的设施数等于其客户数,即m=n)进行求解测试,并对基本蚁群算法和 混合蚁群算法的计算结果进行对比分析. 实验环境:Intel(R)Core(TM)******************,3.41GB内存,操作系统为 Windows 7,数据处理由Matlab 2010完成. 表2给出了基本蚁群算法和混合蚁群算法中的相关参数.表3给出了所求算例的规 模、文献[14]所给的(已知)最优目标函数值、基本蚁群算法和混合蚁群算法的计算 结果.计算结果包括:迭代200次的运行总时间、找到所输出的满意解时的迭代时间 (迭代时间)、满意解的目标函数值(目标函数值)、满意解的目标函数值与文献[14] 所给的(已知)最优目标函数值之间的差距(Gap).其中,所有时间均以s为单位,Gap 的计算公式如下: 由表3可知:混合蚁群算法和基本蚁群算法求解16个算例的平均运行总时间分别为 1 740 s和1 773 s.虽然混合蚁群算法中加入两种局部搜索策略,致使其运行总时间 略高于基本蚁群算法的运行总时间,但是混合蚁群算法的求解结果明显优于基本蚁 群算法的求解结果,混合蚁群算法求解16个算例的平均目标函数值为537 948,其 明显小于由基本蚁群算法计算得到的平均目标函数值2 365 374.对于一半以上的 算例而言,利用混合蚁群算法求解的Gap值均小于8%,表明利用混合蚁群算法求解 的满意解非常接近于文献[14]给出的已知最优解.然而,这些算例利用基本蚁群算法 计算的最小Gap值为47.54%,最大的Gap值竟达2 381.79%. 此外,表3的计算结果表明,相对于基本蚁群算法而言,混合蚁群算法的收敛性能明显 得到改善.如:利用基本蚁群算法和混合蚁群算法求解算例ga00250a1的运行总时 间分别为153.47 s和168.76 s,并且混合蚁群算法在迭代时间为159.20 s时求得 所输出的满意解,但基本蚁群算法在迭代时间为8.55 s时就已求得所输出的满意解, 剩余144.92 s的搜索迭代对所求得的满意解没有任何改进. 首先,深入分析了UFL问题的最优解所具有的特点,并在此基础上提出了两种适用于 UFL问题求解的局部搜索策略,然后将这两种局部搜索策略和基本蚁群算法相结合, 设计了求解UFL问题的混合蚁群算法.求解UFL基本问题库中的16个测试算例的 结果表明,这两种局部搜索策略明显改进了基本蚁群算法的计算性能和求解结果. 结合模型特点,给出的这两种求解UFL问题的局部搜索策略,不仅可以与基本蚁群算 法相结合,而且可与其他智能优化算法相结合构成求解UFL问题的混合智能优化算 法,这对改进求解UFL问题的智能优化算法的求解性能是非常有益的. 【相关文献】 [1] 堵丁柱,葛可一,胡晓东.近似算法的设计与分析[M].北京:高等教育出版社,2011. [2] WILLIAMSON D P,HALL L A,HOOGEVEEN J A,et shop schedules[J].Operations Research,1997,45(2):288-294.[3] LI S.A 1.488 approximation algorithm for the uncapacitated facility location problem [J].Information and Computation,2013,222:45-58. BUZNA acceleration of Erlenkotter-Körkel’s algorithms for the uncapacitated facility location problem [J].Annals of Operations Research,2008,164(1):97-109. [5] CAPRARA A,GONZLEZ S.A branch-and-cut algorithm for a generalization of the uncapacitated facility location problem [J].Top,1996,4(1):135-163. [6] 李翼,赵茂先,李岳佳.无容量限制设施选址问题的分支定界法[J].山东理工大学学报(自然科学 版),2012,26(1):70-73. [7] RESENDE M G C,WERNECK R F.A hybrid multistart heuristic for the uncapacitated facility location problem [J].European Journal of Operational Research,2006,174(1):54-68. [8] 王大志,闫杨,汪定伟,等.基于OpenMP求解无容量设施选址问题的并行PSO算法[J].东北大学 学报(自然科学版),2008,29(12):1681-1684.[9] KLINCEWICZ J G,LUSS H,ROSENBERG l and heuristic algorithms for multiproduct uncapacitated facility location [J].European Journal of Operational Research,1986,26(2):251-258. [10] CURA T.A parallel local search approach to solving the uncapacitated warehouse location problem [J].Computers & Industrial Engineering,2010,59(4):1000-1009. [11] 王欣盛,马良.工件排序的改进蚁群算法优化[J].上海理工大学学报,2011,33(4):362-366. [12] 李煜,马良.用量子蚁群算法求解大规模旅行商问题[J].上海理工大学学报,2012,34(4):355-358. [13] 李俊青,潘全科,王法涛.求解混合流水线调度问题的离散人工蜂群算法[J].运筹与管 理,2015,24(1):157-163.[14] BELTRAN-ROYO C,VIAL J P,ALONSO-AYUSO - Lagrangian relaxation applied to the uncapacitated facility location problem [J].Computational Optimization and Applications,2012,51(1):387-409. 2024年3月9日发(作者：蔡悦可)
求解无容量设施选址问题的混合蚁群算法
李倩;张惠珍;Cesar Beltran-Royo
【摘 要】无容量设施选址(UFL)问题是经典的优化问题,属于NP难题,易于描述却
难于求解.首先,介绍了UFL问题的数学模型,并对UFL问题的特点进行深入分析,得
到其最优解所具有的基本特征;其次,针对UFL问题的最优解所具有的基本特征,设
计了两种局部搜索策略,并将其与基本蚁群算法相结合,提出了一种用于求解UFL问
题的混合蚁群搜索算法;最后,为了测试该算法的性能,分别利用混合蚁群算法和基本
蚁群算法求解UFL问题基准问题库中的16个测试算例.计算结果表明,混合蚁群算
法有效改进了基本蚁群算法求解UFL问题时易陷入局部最优、收敛速度慢等不足,
该算法对求解UFL问题具有明显的可行性和有效性.
【期刊名称】《上海理工大学学报》
【年(卷),期】2016(038)004
【总页数】6页(P367-372)
【关键词】无容量设施选址问题;蚁群算法;局部搜索
【作 者】李倩;张惠珍;Cesar Beltran-Royo
【作者单位】上海理工大学管理学院,上海200093;上海理工大学管理学院,上海
200093;西班牙胡安卡洛斯大学统计与运筹系,马德里
【正文语种】中 文
【中图分类】TP183
无容量设施选址问题(uncapacitated facility location,UFL)是从没有限定容量大小
的设施位置集合中选择要开放的设施,使其以最小的代价服务于给定的所有客户.无
容量设施选址问题具有广泛的实际应用背景,生活中许多实际的问题均可被抽象为
UFL问题进行求解,如银行选址、网络设计、聚类分析、证券投资管理等.
目前,用于求解UFL问题的算法大致可以分为3类:近似算法、精确算法和智能优化
算法.在多项式时间内能够求得问题的一个解,并且其目标函数值与最优解的目标函
数值之比不超过一个常数的算法被称为近似算法[1].1997年,Williamson等[2]给
出了求解设施选址问题的第一个常数近似度算法;2013年,Li[3]提出了求解UFL问
题的1.488-近似算法.求解UFL问题的精确算法主要有:割平面算法、列生成算法、
Erlenkotters算法[4]、分支定界法[5-6]等.这些算法能够求得问题的最优解,但适用
于规模较小的问题,且计算速度慢.虽然智能优化算法搜索效率高,适用于求解大规模
的问题,但是这些算法容易陷入局部最优,一般情况下只能求得问题的满意解,不一定
是最优解.为了克服单一智能优化算法易陷入局部最优、收敛速度慢等不足之处,近
年来求解UFL问题的混合智能优化算法得到了长足的发展,如:混合多层启发式算法
[7]、并行多粒子群优化算法[8]、优化启发式算法[9]、启发式并行局部搜索算法
[10]等.
蚁群算法(ant colony algorithm,ACA)具有鲁棒性强、可以进行分布式计算、易与
其他算法有效结合等优点,但其容易陷入局部最优[11].针对UFL问题的具体特点,将
两种局部搜索策略与基本蚁群算法相融合[12-13],提出了一种求解UFL问题的混合
蚁群算法,并通过求解系列经典UFL问题验证该算法的求解性能.
给定建造无容量限制的设施位置集M={1,…,m},客户集N={1,…,n},对于任意给定的
i∈N和j∈M,cij表示客户i与设施j之间的运输费用,fj>0表示设施j的开放费用.
要求每个客户必须选择一个且只能选择一个设施来满足其需求,同时使总费用最
少.UFL问题的数学模型可被描述为
式中:z为目标函数值,即总费用;yj表示设施j是否开放,如果设施j选择开放,则yj=1,
否则yj=0;xij表示客户i是否选择设施j为其提供服务,如果客户i选择设施j为其
提供服务,则xij=1,否则xij=0.
记X*为UFL问题(1)～(5)的最优解集,分析UFL问题的具体特点,可以得到定理1.
定理1 设(x*,y*)∈X*为最优解集中的一个解,记,对于∀j∈J,记,则存在:
a.
b. 给定∀i∈Ij,则.
证明 a. 假定存在,使得下式成立:
则可定义给定的UFL问题的解)为
计算使下式成立的j″:
并令和,可得
这与(x*,y*)∈X*相矛盾.
b. 对于给定的j0∈J,假定存在i0∈Ij0,使得.计算使下式成立的j″:
并定义给定的UFL问题的解)为
显然,ci0j0xi0j0>ci0j″xi0j″⟹,这与(x*,y*)∈X*相矛盾.
(x*,y*)为所求UFL问题的任一最优解,Ij为该最优解中设施j所服务的客户集合,定
理1说明了UFL问题的最优解所具有的两个特点:a.设施j为集合Ij中所有客户的
服务费用之和小于或等于其他任一设施j′(j′∈M)为集合Ij中的客户提供服务的费
用之和;b.任一客户始终选择与其运输费用最小的已开放设施.
根据定理1,可将给定UFL问题的任一可行解(x,y)进行如下改进:a.该解中,若已开放
的设施j为集合Ij中所有客户的服务费用之和大于设施j′(j′∈M)为集合Ij中的客户
提供服务的费用之和,则可关闭设施j,而开放设施j′,并令j′服务Ij中的所有客户;b.设
施j和j′均为开放设施,且设施j服务客户i,即xij=1,若cij>cij′,则可将客户i的服务
设施j改变为设施j′,即令xij=0,xij′=1.记将(x,y)经过这两种改进后的可行解为),显
然,)所对应的目标函数值小于(x,y)所对应的目标函数值.
2.1 基本蚁群算法
蚁群算法是一种源于大自然中生物世界的新的仿生类算法,属于随机型搜索算法.其
基本原理来自于昆虫学家们对生物界中蚂蚁搜索食物源的过程的观察:蚂蚁在搜索
食物时,能在其经过的路径上释放一种蚂蚁特有的分泌物——信息素,使得其他蚂蚁
可以感知并且影响其行为.当选择某些路径的蚂蚁越来越多时,该路径上累积的信息
素就越多,以致后来蚂蚁选择该路径的概率也越高,也就增加了该路径的吸引强度,依
靠这种生物机制,蚂蚁最终可以找到一条到达食物源的最短路线.本文将这种蚂蚁群
体寻优思想作一些修改和引申,以便符合所要求解的UFL问题.
将目标函数值作为每只蚂蚁k的评价值.对于客户1,将[1,m]区间内产生的一个随机
整数作为蚂蚁k为客户1所选择的设施.对于其他客户i(1 随机数q,若q≤q0(0 否则,利用式(7)计算蚂蚁k选择设施j的概率及其累积概率,并采用轮盘赌法确定所 选设施. 式中:M={1,…,m}为设施位置集合为启发函数,表示蚂蚁k在客户i处选择设施j的 期望程度,通过蚂蚁k给前(i-1)个客户提供服务所开放的设施费用及配送费用之和 来计算;τij为客户i与设施j之间的信息素;α为信息素重要程度因子,其值越大,表示 信息素的浓度在选择过程中所起的作用越大;β为启发函数重要程度因子,其值越大, 表示启发函数在选择过程中所起的作用越大. 表1表示了蚂蚁k为客户i选择设施时,10个设施处的概率和累积概率.当q>q0时, 将随机数q作为选择指针来确定蚂蚁k在客户i处的被选设施.如:q0=0.15和 q=0.63时,蚂蚁k在客户i处的被选设施为5. 随着时间的推移,蚂蚁在路径上留下的信息素逐渐衰减.记信息素衰减系数为 ρ(0<ρ<1),蚂蚁完成一次循环后,利用式(8)更新信息素为 式中,表示蚂蚁k在本次循环过程中留在客户i和设施j之间的信息素.选择应用 Ant-Cycle模型计算为 式中:Q为常数;zk为蚂蚁k在本次循环中的目标函数值. 2.2 局部搜索 在定理1的基础上,设计了两种求解UFL问题的局部搜索策略,并将其嵌入蚁群优化 算法,以有效改进由蚁群算法所求得的UFL问题的可行解.下面通过一个例子来对两 种局部搜索策略进行简要介绍. 例 给定一个m=5和n=5的UFL问题,该问题中客户与设施之间的运输费用矩阵 C和设施安装费用向量F分别为 F=[130,199,139,127,103] 该问题的最优目标函数值为1 034.假设蚂蚁算法中l只蚂蚁搜索一次所得的满意解 为:x14=1,x23=1,x32=1,x42=1,x55=1,y1=0,y2=1,y3=1,y4=1,y5=1.即:开放的 设施集合为{2,3,4,5};客户1选择设施4;客户2选择设施3;客户3和4选择设施2; 客户5选择设施5;总费用为199+139+127+103+1 224+1 749+1 227+1 783+1 149=7 700. 利用两种局部搜索策略对上述蚂蚁算法的求解结果改进如下: 策略1 以设施2所服务的客户3和4为例,客户集{3,4}分别被各个设施服务的费 用为 设施1 c31+c41+f1=1 488+1 235+130=2 853; 设施2 c32+c42+f2=1 227+1 783+199=3 209; 设施3 c33+c43+f3=1 240+1 831+139=3 210; 设施4 c34+c44+f4=121+1 340+127=1 588; 设施5 c35+c45+f5=1 375+112+103=1 590. 由上述计算结果及定理1可知,若客户3和4选择为其服务费用最小的设施4,则可 使蚂蚁算法的求解结果得以改进,则令x32=0,x42=0,x34=1,x44=1,y2=0,y4=1.改 进后的结果为x14=1,x23=1,x34=1,x44=1,x55=1,y1=0,y2=0,y3=1,y4=1,y5=1, 目标函数值计算结果为v=5 952. 策略2 蚂蚁算法的求解结果经策略1改进后,开放的设施集合为{3,4,5}.由定理1 知:给定开放的设施集合,每个客户应选择运输费用最小的开放设施为其服务. 客户1 由min {c13,c14,c15}=min {1 354,1 224,192}=192得设施5应为客户 1提供服务,则令x14=0,x15=1; 客户2 由min (c23,c24,c25)=min (1 749,132,1 439)=132得设施4应为客户 2提供服务,则令x23=0,x24=1; 客户3 由min (c33,c34,c35)=min (1 240,121,1 375)=121得客户3的服务设 施保持不变,仍为设施4,即x34=1; 客户4 由min (c43,c44,c45)=min (1 831,1 340,112)=112得设施5应为客户 4提供服务,则令x44=0,x45=1; 客户5 由min (c53,c54,c55)=min (108,1 004,1 149)=108得设施3应为客户 5提供服务,则令x55=0,x53=1. 经策略2改进后的结果为 x15=1,x24=1,x34=1,x45=1,x53=1,y1=0,y2=0,y3=1,y4=1,y5=1,v=1 034.显然, 蚂蚁算法的计算结果经策略1和策略2得到了明显改进. 2.3 混合蚁群算法 将基本蚁群算法和两种局部搜索策略相结合,提出了求解UFL问题的混合蚁群算法. 算法具体步骤为: Step 1 初始化蚂蚁个数b、反映信息素重要程度的因子α、反映启发函数重要程 度的因子β、信息素衰减因子ρ、常数q0和Q、最大迭代次数N和信息素矩阵 T=(τij)N×M,令迭代次数nc=1,蚂蚁编号k=1和满意解的目标函数值v=+; Step 2 将[1,m]区间内产生的一个随机整数作为蚂蚁k为客户1所选择的设施,根 据式(6)和式(7)为蚂蚁k的其他客户选择一个设施; Step 3 若k Step 4 运用两种局部搜索方法对蚂蚁的本次搜索结果进行改进; Step 5 更新当前满意解及其所对应的目标函数值v; Step 6 根据式(8)更新信息素矩阵; Step 7 令Δτij=0(i∈N,j∈M)和nc=nc+1; Step 8 若nc≤N,则转Step 2;否则,结束搜索,并输出结果. 为验证混合蚁群算法的可行性及其求解性能,采用两组UFL基准问题库中的16个 算例(每个算例的设施数等于其客户数,即m=n)进行求解测试,并对基本蚁群算法和 混合蚁群算法的计算结果进行对比分析. 实验环境:Intel(R)Core(TM)******************,3.41GB内存,操作系统为 Windows 7,数据处理由Matlab 2010完成. 表2给出了基本蚁群算法和混合蚁群算法中的相关参数.表3给出了所求算例的规 模、文献[14]所给的(已知)最优目标函数值、基本蚁群算法和混合蚁群算法的计算 结果.计算结果包括:迭代200次的运行总时间、找到所输出的满意解时的迭代时间 (迭代时间)、满意解的目标函数值(目标函数值)、满意解的目标函数值与文献[14] 所给的(已知)最优目标函数值之间的差距(Gap).其中,所有时间均以s为单位,Gap 的计算公式如下: 由表3可知:混合蚁群算法和基本蚁群算法求解16个算例的平均运行总时间分别为 1 740 s和1 773 s.虽然混合蚁群算法中加入两种局部搜索策略,致使其运行总时间 略高于基本蚁群算法的运行总时间,但是混合蚁群算法的求解结果明显优于基本蚁 群算法的求解结果,混合蚁群算法求解16个算例的平均目标函数值为537 948,其 明显小于由基本蚁群算法计算得到的平均目标函数值2 365 374.对于一半以上的 算例而言,利用混合蚁群算法求解的Gap值均小于8%,表明利用混合蚁群算法求解 的满意解非常接近于文献[14]给出的已知最优解.然而,这些算例利用基本蚁群算法 计算的最小Gap值为47.54%,最大的Gap值竟达2 381.79%. 此外,表3的计算结果表明,相对于基本蚁群算法而言,混合蚁群算法的收敛性能明显 得到改善.如:利用基本蚁群算法和混合蚁群算法求解算例ga00250a1的运行总时 间分别为153.47 s和168.76 s,并且混合蚁群算法在迭代时间为159.20 s时求得 所输出的满意解,但基本蚁群算法在迭代时间为8.55 s时就已求得所输出的满意解, 剩余144.92 s的搜索迭代对所求得的满意解没有任何改进. 首先,深入分析了UFL问题的最优解所具有的特点,并在此基础上提出了两种适用于 UFL问题求解的局部搜索策略,然后将这两种局部搜索策略和基本蚁群算法相结合, 设计了求解UFL问题的混合蚁群算法.求解UFL基本问题库中的16个测试算例的 结果表明,这两种局部搜索策略明显改进了基本蚁群算法的计算性能和求解结果. 结合模型特点,给出的这两种求解UFL问题的局部搜索策略,不仅可以与基本蚁群算 法相结合,而且可与其他智能优化算法相结合构成求解UFL问题的混合智能优化算 法,这对改进求解UFL问题的智能优化算法的求解性能是非常有益的. 【相关文献】 [1] 堵丁柱,葛可一,胡晓东.近似算法的设计与分析[M].北京:高等教育出版社,2011. [2] WILLIAMSON D P,HALL L A,HOOGEVEEN J A,et shop schedules[J].Operations Research,1997,45(2):288-294.[3] LI S.A 1.488 approximation algorithm for the uncapacitated facility location problem [J].Information and Computation,2013,222:45-58. BUZNA acceleration of Erlenkotter-Körkel’s algorithms for the uncapacitated facility location problem [J].Annals of Operations Research,2008,164(1):97-109. [5] CAPRARA A,GONZLEZ S.A branch-and-cut algorithm for a generalization of the uncapacitated facility location problem [J].Top,1996,4(1):135-163. [6] 李翼,赵茂先,李岳佳.无容量限制设施选址问题的分支定界法[J].山东理工大学学报(自然科学 版),2012,26(1):70-73. [7] RESENDE M G C,WERNECK R F.A hybrid multistart heuristic for the uncapacitated facility location problem [J].European Journal of Operational Research,2006,174(1):54-68. [8] 王大志,闫杨,汪定伟,等.基于OpenMP求解无容量设施选址问题的并行PSO算法[J].东北大学 学报(自然科学版),2008,29(12):1681-1684.[9] KLINCEWICZ J G,LUSS H,ROSENBERG l and heuristic algorithms for multiproduct uncapacitated facility location [J].European Journal of Operational Research,1986,26(2):251-258. [10] CURA T.A parallel local search approach to solving the uncapacitated warehouse location problem [J].Computers & Industrial Engineering,2010,59(4):1000-1009. [11] 王欣盛,马良.工件排序的改进蚁群算法优化[J].上海理工大学学报,2011,33(4):362-366. [12] 李煜,马良.用量子蚁群算法求解大规模旅行商问题[J].上海理工大学学报,2012,34(4):355-358. [13] 李俊青,潘全科,王法涛.求解混合流水线调度问题的离散人工蜂群算法[J].运筹与管 理,2015,24(1):157-163.[14] BELTRAN-ROYO C,VIAL J P,ALONSO-AYUSO - Lagrangian relaxation applied to the uncapacitated facility location problem [J].Computational Optimization and Applications,2012,51(1):387-409.