许 骏，许晓东

（华中科技大学公共管理学院，湖北 武汉 430074)

一种群体智能融合算法及其在应急设施选址的应用＊

许 骏，许晓东

（华中科技大学公共管理学院，湖北 武汉 430074)

针对粒子群优化算法早熟及细菌觅食算法收敛慢的问题，提出了将量子粒子群优化与细菌觅食算法融合的一种群体智能融合算法。该算法将细菌觅食、量子计算理论及粒子群优化的优点进行融合，以细菌觅食算法为主体，将量子进化算法及粒子群优化算法嵌入其中，从而极大地提高了算法的性能。通过对三个标准函数求解和验证，结果表明该算法提高了收敛精度及速度。最后用该算法求解公共卫生应急服务设施点选址问题，取得了较好的效果，说明了该算法的有效性。

群体智能算法；量子粒子群优化；细菌觅食算法；应急选址

1 引言

群体智能算法［1，2］是一门新兴的优化计算方法，自20世纪80年代出现以来，引起了多个学科领域研究人员的关注，已经成为优化技术领域的一个研究热点。这类算法的主要应用对象是优化问题中的难解问题，也就是优化理论中的NP-hard问题。

群体智能算法本质上是一种概率搜索，不需要问题的梯度信息，并具有如下特点：（1)群体中的个体代表问题空间中的一个解，能感知周围的局部信息且遵循的规则非常简单，群体智能易于实现；（2)个体在解的空间是分布式的，不存在直接的中心控制，这样即使有个别个体出现故障，也不会影响群体对问题的求解，具有较强的鲁棒性。同时，个体之间可以相互作用从而表现出群体的高度智能。群体智能算法的出现，使得原来一些复杂而且难以用常规优化算法进行处理的问题得到了解决，在工程实际中得到了广泛应用。常用的群体智能算法有遗传算法、粒子群算法、细菌觅食算法、蚁群算法等。

群体智能算法的理论研究主要是研究算法特性，改进其不足，提高其性能，主要包括两个方面：一是从群体智能算法的自身特性加以研究，改进其性能；二是将群体智能算法之间或者与其它算法融合，产生性能更佳的融合智能算法。本文提出了将量子粒子群优化与细菌觅食融合的算法，该算法结合了粒子群优化和细菌觅食算法的特点，并利用有关量子计算的理论基础使之适用于离散空间。然后，通过标准函数进行验证，进而应用于求解应急服务设施点选址问题。

2 量子粒子群与细菌觅食的融合算法

2.1 量子粒子群与细菌觅食的融合策略

粒子群优化PSO（Particle Swarm Optimization)算法首先由 Kennedy J和 Eberhart R C［3］提出，由于其简洁性和快速性，一经提出便引起许多研究者的关注，主要归结为算法本身改进［4，5］、算法拓扑结构改进［6，7］、算法参数的改进［8］、混合粒子群算法［9］等方面的研究和改进。这些研究使PSO成为一种有竞争力的群体智能优化技术，并广泛应用于连续空间的寻优问题。

其中，k为迭代次数，ω为权系数，c1、c2为加速因子，r1、r2为［0，1］的随机数。

在式（1)所描述的粒子速度进化方程中，第一项是粒子先前的速度，第二项代表“认知”部分，但仅考虑了粒子自身的“经验”，第三项则代表了“社会”部分，即粒子间的社会信息共享。这样粒子在相互作用下，有能力到达新的搜索空间。不过，虽然它的收敛速度较快，但对于复杂问题，容易陷入局部最优点［10］。

细菌觅食算法BFA（Bacterial Foraging Algorithm)是由Passino K M［11］于2002年提出来的一种仿生随机搜索算法，通过模拟人类肠道中大肠杆菌的觅食行为，在搜索过程中通过营养分布函数来判断搜索算法的优劣。该算法因具有群体智能算法并行搜索、易跳出局部极值等优点，成为生物启发式计算研究领域的又一热点。

在BFA中，优化问题的解对应于搜索空间中的细菌的状态，即优化函数的适应度值。BFA包括趋化、复制和驱散三个步骤［12］，其主要步骤为趋化行为。细菌的趋化性操作可表示如下：

其中，θi（j，k，l)表示细菌i在第j次趋化操作、第k次复制操作和第l次驱散操作时的位置，c（i)表示趋化步长，φ（j)表示旋转后选择的一个随机前进方向。

由于BFA在趋化中采用任意方向进行翻转，没有利用历史信息，导致收敛速度较慢。2008年Dasgupta S和 Das S等人［13，14］对趋化操作分析后指出：当适应度函数形状较为平坦时，趋化在接近优化值时会产生振荡，文献［13，14］建议对趋化步长给以约束。本文利用PSO中个体极值和全局极值信息来确定细菌前进的方向，从而确定趋化的最佳方向，表达为：其中r1i、r2i分别为粒子历史最优和全局最优权系数，通过与当前粒子适应度值比较而确定其值，表达为：

趋化步长对收敛性能影响较大，步长越大算法收敛越快，但易跳过最优值，而较小步长则增加了搜索时间。本文根据迭代次数自适应地改变步长，即开始使用大的步长，接近最优值时采用小步长，即：

其中，itermax是最大迭代次数，k是当前迭代次数。改进后趋化操作的进化方程为：

但是，上述对算法的改进策略仅适用于连续解空间。为了适应于离散空间，本文利用量子计算理论基础，采用量子比特方式来表示每个细菌位置的状态。一个具有n个量子比特位的系统可以描述为［15］：

量子比特位的状态改变可由进化方程（2)通过量子旋转门计算得到［15］，即状态更新方程为：

假设第i个细菌的位置向量Xi＝ ｛xi1，…，xin｝，位置向量的更新由其存储在量子比特q中的β值确定，即：

2.2 量子粒子群优化与细菌觅食融合算法的实现

细菌位置代表一个解，解的优劣由系统适应度函数来确定。融合算法搜索最优解的步骤如下：

Step 1 初始化参数设置。其中，n为搜索空间维数；S为细菌种群数；Nc为趋化循环次数；Nre为复制循环次数；Ned为迁移循环次数；Ped为迁移概率；θmin、θmax为最小、最大旋转角；、为1/。

Step 2迁移循环：l＝l＋1。

Step 3复制循环：k＝k＋1。

Step 4趋化循环：j＝j＋1。

Step 4.1选取细菌i，计算细菌i所在位置的适应度值：J（i，j，k，l)，并保存该值到Jlast；

Step 4.2由公式（2)计算细菌i每一位的旋转值；

Step 4.3由公式（3)和公式（4)计算细菌i的新位置，并计算新位置的适应度值J（i，j，k，l)；

Step 4.4更新细菌i的局部最优值和种群全局最优值。

Step 5循环Step 4，直到趋化循环完毕。

Step 6复制：将适应度值差的细菌淘汰一半。为保证个体总数一致性，再对剩余的细菌进行复制。

Step 7重复Step 3，直至复制循环完毕。

Step 8迁移：以一定的概率Ped选取部分细菌，将其驱散到其它位置，剩余细菌的位置保持不变。

Step 9重复Step 2，直至迁移循环完毕。

Step 10结束。

2.3 算法性能测试

目前常用求解测试函数的最优值的问题来检验智能优化算法，这些测试函数有单峰，也有多峰的，函数解的分布是连续变化的。本文使用下列三个标准函数来验证群体融合智能算法的精度及收敛性能。

上述三个标准函数的维数为N。其中，Sphere函数具有单峰，最小值f（0)＝0，该函数的特点是曲面平滑，梯度信息总是能指向全局最优；Rosenbrock函数也是一个单峰函数，曲面光滑，但梯度信息经常误导算法的搜索方向，算法较难搜索到全局最优解，全局最小值f（1)＝1；而Rastrigin函数具有多峰，有许多局部最小值，很难找到全局最优解，优化算法易陷入局部最优点，全局最小值f（0)＝0。

（1)算法参数分析。

本文提出算法中没有太多需要调节的参数，因此只对最大、最小旋转角、种群规模等参数进行分析。趋化操作及复制操作影响可参考文献［13］，最大迭代次数分析由下文给出。

种群规模表示算法中同时进行搜索的细菌数目，决定了目标函数达到收敛值需要进行评价的最少次数。一般而言，种群规模大有利于在状态空间内更充分搜索，同时可减少迭代次数，但是评价次数也相应增加。图1是使用Rastrigin函数在不同种群规模下迭代1 000次时，计算机所用的时间及收敛值。从图1中可以看出，种群规模选择在20～40可取得较为合理的结果。

最大、最小旋转角选用文献［15］推荐值0.05π和0.001π，图2显示的是种群分别为10和30的情况下迭代1 000次不同最大、最小旋转角的组合对收敛性能影响的结果。从图2中可知，最大、最小旋转角分别选用0.05π和0.01π最佳。

（2)算法性能分析。

Figure 1 Influence of population size on the performance of algorithm图1 种群数量对算法性能的影响

Figure 2 Influence of maximum ＆minimum rotation angle combination on the performance of algorithm图2 最大、最小旋转角组合对算法性能的影响

为了验证本文提出的群体智能融合算法的收敛精度及收敛时间，本文采用前述三个经典标准函数进行验证，并同时与其它算法进行比较。使用的参数为：迁移概率Ped＝0.25，最大、最小旋转角分别取0.05π和0.01π，细菌种群数S＝20、复制次数Nre＝4、迁移次数Ned＝5，趋化次数Nc则随函数复杂程度不同而变化。

首先，用 GA-BFO［16］、PSO-BFO［17］及本文算法分别对标准函数求解，每个函数独立执行50次，计算均值及方差，收敛精度结果见表1，收敛速度结果见表2。

表1列出了不同算法对标准函数收敛到0.001或运行到规定的最大迭代次数时的情况（表中的黑体标记为不同算法收敛的最好值，方差为0的没有标明)。从表1中可以看出，对于Sphere函数，维数为15时表中所选算法都能很快地收敛。总体来说，本文提出的融合算法收敛精度较其他算法高，特别当函数的维数比较大时。表2展示了函数收敛到规定阈值0.000 1时，算法独立运行50次的迭代次数的均值与方差。从表2可以看出，对于Sphere函数，所有算法都能收敛，但对于Rosenbrock、Rastrigin两个函数，在高维时，只有本文提出的算法能够收敛，其它算法由于早熟而不能收敛到规定值（算法迭代的最高次数不高于1010)。

3 本文提出的算法求解公共卫生应急服务设施点选址问题

3.1 建模

直接面对居民“最后一公里”的应急服务设施点的选址对保障应急资源在短时间内高效地提供给受威胁地区每个居民是至关重要的，其选择影响到卫生应急中应急资源供应最大最优，影响着整个系统的快速反应能力。对于分布宽广的“最后一公里”的应急服务设施点的选址，必须确保覆盖到所有灾区中每一户家庭，同时，为防止意外，每个行政区内至少要设置两个应急服务设施点。显然，设施点的数量与其容量及服务的人数有关，每个设施点需要的资源需要统筹规划，以确保在规定时间内完成任务。本文中假设每个设施点的资源已确定，即容量已知，服务对象到相应设施点的距离不超过设置的最远距离，在上述条件下确定应急服务设施点的数量。

Table 1 Mean and variance of the objective function after different algorithm running independently（N＝50)表1 不同算法独立运行后目标函数的均值及方差（N＝50次)

Table 2 Comparison of iteration number to the convergence of different algorithm running to the provisions threshold（N＝50)表2 收敛到规定阈值0.000 1时不同算法运行的迭代次数比较（N＝50次)

选址问题本身是一个非常经典的问题，有成熟的解决模型，然而应急服务设施点选址问题与传统选址问题具有不同的优化约束与目标，前者时效性可能非常重要，而后者则更加关注成本。选址问题已被证明是一类极难优化的问题集，即NP-hard问题，至今未能有效精确求解［18］。已有的精确式算法都是指数级的，无法解决现实问题（中、大规模)。在实际应用时，近似算法特别是智能优化算法是求解NP-hard问题的有效方法之一［19］。本文通过对公共卫生应急服务设施点选址进行了建模，并用本文提出的算法求解应急服务设施点选址问题。

为了确定应急服务设施点的数量及服务的范围，本文首先对要服务的目标区域离散化，即将目标区域划分成大小为一平方公里的网格。每个网格与所服务的人口联系起来，可认为是一个候选的应急服务设施点。对给定的目标区域，可以使用如下参数来描述与设施点有关的变量：

kem：事件发生地行政区的数目；

Gi：在行政区i内所有网格的集合，i≤kem；

cl：网格l内的应急服务设施点容量；

pr：网格r内的人口数量；

d（r，l)：网格r、l之间的距离；

dmax：服务对象到相应的应急服务设施点允许的最远距离。

决策变量设为：

yl：如果网格l内设置了应急服务设施点，则为1，否则为0；

xrl：如果网格l内的应急点为网格r内的公民服务，则为1，否则为0。

则应急服务设施点的选址可用如下数学模型来描述：

目标函数在满足需求的条件下，使应急服务设施点的数目最小。其中，约束条件（5)保证在每个行政区内至少要设置两个应急服务设施点，以防在意外灾难发生而必须关闭设施点时，另一个应急设施点还能正常运行；约束条件（6)限制了每个用户到达应急服务设施点的距离需小于最远行驶距离；约束条件（7)保证每户都能得到服务；约束条件（8)则要求设施点所能提供的服务量不能大于其容量；约束条件（9)限定决策变量是0/1变量。约束条件

3.2 实现

为了求解公共卫生应急资源选址问题，必须先确定问题空间的编码方式、粒子适应度函数、种群的初始化等。

（1)问题的编码方式。

当采用本文提出的算法求解问题时，首先必须在目标问题实际表示与种群个体之间建立联系，即采用某种编码方式将解空间映射到编码空间。本文将应急区域用网格进行划分，对网格进行编号，然后采用二进制编码，码的位数与网格的编号一一对应。比如，现有编号为0、1、2、3、4、5的网格，则对应的二进制编码为110010，位0对应于0号网格，位1对应于1号网格，依次类推。二进制相应位如果是“0”表示在此网格中没有应急服务设施点，是“1”则表示网格中设置有应急服务设施点，上述例子中，1、4、5号网格中应设置设施点。网格排列的值的变化构成了问题的状态空间，显然，一个排列代表了一个解。

（2)确定适应度函数。

适应度函数是由问题的目标函数变化而成的。对应急服务设施点选址问题，还必须满足约束条件。为此，适应度函数包括三部分：第一部分与目标函数有关，本文应急服务设施点采用了二进制编码方式，因此，解的二进制中“1”的个数即为设施点的数量，此部分设为fem1；对于不满足约束条件（5)的行政区的数量设为fem2，这一部分必须加入到适应度函数中，为第二部分；第三部分与服务对象有关，涉及到约束条件（6)～约束条件（8)。依据最近法则，确定可为每个服务对象提供服务的设施点，当超过其容量时，到次近的设施点，直到无设施点可用或者到设施点的距离超过设定的最远距离为止。此时对剩余的服务对象进行聚类统计，相互之间的距离小于最远距离的归为一类，分类的数量即为fem3，则适应度函数f＝fem1＋fem2＋fem3，在fem2、fem3都为零的情况下适应度函数越小越优。

（3)种群的初始化。

种群个体数量一般在20～40，与解空间的状态有关，本文数量选为30。个体的初始位置采用贪婪算法选取，使之满足所有约束条件。

3.3 算例

以武汉市为例，总人口978万人，有13个行政区，用一平方公里网格对区域作划分，每个行政区网格数量在34～2 261，每个网格人口数量在321～20 711。模型的问题规模约束条件和0/1变量数量从最小1 225＊1 190到最大5 116 644＊5 114 382。

为了说明本算法性能，本文分别用LINGO 10、GA-BFO和本文算法求解，迭代次数1 000次，计算结果如表3所示。

Table 3 Calculating results of running time and facilities point number of different algorithm表3 不同算法的运行时间及设施点数量计算结果

从表3中可以看出，当应急设施点容量为2 000人/h时，采用LINGO 10的运算时间最短，但当问题的规模变大，如设施点容量为500人/h时，则不能求解，而本文提出的算法仅用90分钟就可以完成。因此，求解问题规模越大，本文提出的算法优势越明显。

表4的结果显示了当应急服务设施点容量不同时，限制的最远距离与应急服务设施点数量之间的关系。图3则显示在设施点容量和最远距离一定时，实际旅行距离下到应急设施点接受服务的居民数量分布的概率。

Table 4 Numbers of facility points needed in different capacity under different maximum distances表4 不同容量下不同最远距离所需设施点的数目

Figure 3 Relationship between the actual driving distance and the residents distribution proportion（parametric assumption：capacity＝1 500person/hour，maximum distance＝10km)图3 实际行驶距离与居民分布比例的关系

4 结束语

本文基于细菌觅食算法、粒子群优化及量子计算的特点提出的群体智能融合算法，是将粒子群优化的思想融入细菌觅食算法中，充分利用了个体的信息，使收敛速度大大加快，解决了由于随机的搜索方向导致细菌觅食算法收敛时间增加的问题，从而极大地提高了算法的性能。同时，采用量子比特位来存储细菌的状态，从而使算法适用于离散空间。本文通过对三个标准函数在不同维数下的求解，验证该算法在收敛性能方面的提高。最后用该算法求解公共卫生应急选址的问题，得到了较好的效果，表明该算法是一种有效的方法。

［1］ Bonabeau E，Dorigo M，Theraulaz G.Swarm intelligence：From natural to artificial systems［M］.1st edition.New York：Oxford University Press，1999.

［2］ Bonabeau E，Dorigo M，Theraulaz G.Inspiration for optimization from social insect behaviour［J］.Nature，2002，406（6)：39-42.

［3］ Kennedy J，Eberhart R C.Particle swarm optimization［C］∥Proc of IEEE International Conference on Neural Networks，1995：1942-1948.

［4］ Clerc M，Kennedy J.The particle swarm-explosion，stability，and convergence in a multidimensional complex space［J］.IEEE Transactions on Evolutionary Computation，2002，6（1)：58-73.

［5］ Ratnaweera A，Halgamuge S，Watson H.Self-organizing hierarchical particle swarm optimizer with time-varying accelerating coefficients［J］.IEEE Transactions on Evolutionary Computation，2004，8（3)：240-255.

［6］ Hu X H，Eberhart R C.Multi-objective optimization using dynamic neighborhood particle swarm optimization［C］∥Proc of the Congress on Evolutionary Computation，2002：606-607.

［7］ Mendes R，Kennedy J，Neves J.The fully informed particle swarm：Simpler，maybe better［J］.IEEE Transactions on Evolutionary Computation，2004，8（3)：204-210.

［8］ Eberhart R C，Yu S.Guest editorial special issue on particle swarm optimization［J］.IEEE Transactions on Evolutionary Computation，2004，8（3)：201-203.

［9］ Higashi N，Iba H.Particle swarm optimization with Gaussian mutation［C］∥ Proc of the Congress on Evolutionary Computation，2003：72-79.

［10］ Kennedy J，Mendes R.Neighborhood topologies in fully-informed and best-of-neighborhood particle swarms［J］.IEEE Transactions on Systems，Man，and Cybernetics，2006，36（4)：515-519.

［11］ Passino K M.Biomimicry of bacterial foraging for distributed optimization and control［J］.IEEE Control Systems Magazine，2002，22（3)：52-67.

［12］ Das S，Biswas A，Dasgupta S.Bacterial foraging optimization algorithm：Theoretical foundations，analysis，and applications［M］.Heidelberg：Springer-Verlag，2009：23-55.

［13］ Dasgupta S，Das S，Abraham A，et al.Adaptive computational chemotaxis in bacterial foraging algorithm［C］∥Proc of the 2nd International Conference on Complex，Intelligent and Software Intensive Systems，2008：64-71.

［14］ Das S，Dasgupta S，Biswas A，et al.On stability of the chemotactic dynamics in bacterial foraging［C］∥ Proc of International Conference on Soft Computing as Transdisciplinary Science and Technology，2008：245-251.

［15］ Han K H，Kim J H.Quantum-inspired evolutionary algorithm for a class of combinatorial optimization［J］.IEEE Transactions on Evolutionary Computation，2002，6（6)：580-593.

［16］ Kim D H，Abraham A，Cho J H.A hybrid genetic algorithm and bacterial foraging approach for global optimization［J］.Information Sciences，2007，177（18)：3918-3937.

［17］ Biswas A，Dasgupta S，Das S，et al.Synergy of PSO and bacterial foraging optimization：A comparative study on numerical benchmarks［M］∥Innovations in Hybrid Intelligent Systems，2007：255-263.

［18］ Yang Feng-mei，Hua Guo-wei，Deng Meng，et al.Some advances of the researches on location problems［J］.Operations Research and Management Science，2005，14（6)：1-7.（in Chinese)

［19］ Edson L F S，Luiz A N L，Marcos A P.A decomposition heuristic for the maximal covering location problem［J］.Advances in Operations Research，2010，2010：1-12.

附中文参考文献：

［18］ 杨丰梅，华国伟，邓猛，等.选址问题研究的若干进展［J］.运筹与管理，2005，14（6)：1-7.

A fusion algorithm of swarm intelligence and its application in emergency services facility location

XU Jun，XU Xiao-dong
（School of Public Administration，Huazhong University of Science and Technology，Wuhan 430074，China)

In order to solve the problem of prematurity of swarm intelligence algorithm and slow speed of convergence of bacterial forging algorithm，an algorithm is proposed，which fuses quantum particle swarm together with bacteria foraging optimization.After considering the advantages of bacteria foraging optimization，quantum computing theory and particle swarm optimization，the proposed fusion algorithm takes the bacterial foraging algorithm as the main body and embedded quantum evolutionary algorithm and particle swarm optimization algorithm into it，thus improving the performance of the algorithm greatly.Through solving and validating the three criteria functions，the results show that the proposed fusion algorithm improves convergence precision and speed.Finally，the proposed algorithm is used to solve public health emergency service facility location problem and achieves good results，proving its effectiveness.

swarm intelligence algorithm；quantum particle swarm optimization；bacterial foraging algorithm；emergency service facilities point location

TP399；X43

A

10.3969/j.issn.1007-130X.2014.04.017

2012-10-08；

2013-03-05

通讯地址：430015湖北省武汉市江岸区江汉北路24号

Address：24Jianghan Rd North，Jiang’an District，Wuhan 430015，Hubei，P.R.China

1007-130X（2014)04-0667-07

许骏（1971-)，女，湖北随州人，博士生，研究方向为公共安全预警与应急管理。E-mail：xujun＠whcdc.org

XU Jun，born in 1971，PhD candidate，her research interests include public safety early warning，and emergency management.