基于改进烟花算法的资源分配

邹适宇，李复名，谢爱平，周涛，刘鹏

中国电子科技集团公司第二十九研究所，成都 610000

资源分配是指针对某个目标，遵循一定的策略将规模为N的资源映射和划分到P个个体上，是一个NP-Hard问题。作为一个典型的组合优化问题，进行合理的资源分配能够达到提高效率、节约成本、合理配置资源或总体收益最佳等系统目标[1]。其求解途径一般包括穷举法、分支定界法等确定性算法[2-5]和遗传算法、粒子群算法等智能优化算法[6-9]。

烟花算法(Firework Algorithm, FWA)作为智能优化算法的一种，由于其操作简单、性能较优，具有较强的并行性与鲁棒性，自北京大学的谭营教授于2010年提出以来便受到广泛关注[10]。但传统烟花算法在求解大规模资源分配问题时也存在计算效率偏低、易陷入局部最优等问题。

研究人员针对这些问题也做了改进工作，主要包括以下2个方面：第一，算法本身机制和算子的改进。文献[11]仅保留FWA的爆炸操作，提出一种骨架烟花算法，该算法具有简单易行、参数少等优点；文献[12]针对FWA求解精度低的问题，提出具有灰色关联算子的烟花算法；文献[13]在分析高斯变异算子不足的基础上，提出了一种基于差分变异算子的烟花算法，增强了算法的精度和收敛速度；文献[14]引入爆炸半径动态调整的策略，提出一种带有动态爆炸半径的增强型烟花算法，以增强算法跳出局部最优的能力。第二，同其他智能优化算法的融合。文献[15]将生物地理学优化方法的迁移操作引入到FWA中，以增强种群之间的信息共享文献，改善种群多样性；文献[16]在FWA的基础上，引入混合蛙跳算法的分组策略，增强了算法跳出局部最优的能力；文献[17]为了提高FWA的全局搜索能力，将模拟退火算法引入FWA中，提出了一种基于模拟退火与高斯扰动的烟花优化算法。

然而上述改进烟花算法在求解具有多约束条件多优化目标的资源分配问题时，求解效果相对不佳。本文为了改善传统烟花算法性能，以多无人机协同作业任务分配[18]为研究背景，提出一种改进烟花算法，在传统烟花算法的基础上引入遗传算法[19]的变异算子，增加模拟退火操作[20]，最后对算法性能进行了仿真验证。

1 资源分配数学模型

资源分配问题作为一个共性的数学问题具有众多应用场景，本文选取多无人机协同任务分配这一复杂、典型的资源分配问题进行研究。为了使数学模型更贴近实际应用场景，本文考虑了无人机的可侦查频段等功能指标，以最小化飞行总航程、任务执行总时间和损耗代价为优化目标构建资源分配数学模型。

根据无人机实际应用场景的需求，将多无人机协同作业任务分配场景描述为一个三元组{U,T,C}，其中U表示无人机的集合，T表示目标任务的集合，C表示约束条件的集合。本文的约束条件包括：无人机任务约束、侦查频段约束、最大航程约束和最大执行任务数量约束。

设某一无人机的侦查频段范围为[fmin,fmax]，最大执行任务数量为M，其执行任务序列为{Task1,Task2,…,Taskk}，按照任务序列执行完所有任务的航程为di，其中一目标任务Tj包含频率为fk，xi,j=1表示任务j由无人机i执行，xi,j=0表示无人机i不执行任务j，则需满足：

(1)

fmax≥fk≥fmin

(2)

di≤dmax

(3)

k≤M

(4)

为了降低无人机执行任务风险、减少资源浪费，本文设置以下3个优化目标：① 无人机飞行总航程最短；② 任务执行总时间最短；③ 无人机损耗最小。

优化目标①要求任务执行完成后，无人机飞行总航程最短，将无人机飞行总航程指标用F1表示，即

(5)

式中：di为无人机i完成任务序列飞行的总航程。

优化目标②要求无人机机群执行分配到的任务目标的总任务执行时间最短，将任务执行总时间指标用F2表示，即

(6)

优化目标③要求无人机机群在完成所有任务后，所有无人机的损耗代价最小，将损耗代价指标用F3表示，即

(7)

式中：price(Xi)和damage(Xi)分别表示无人机i的价格和损伤概率。

基于以上优化目标，设由N架无人机执行M个目标任务，无人机i的任务集为Xi，执行任务的效能为F(Xi)，得到多无人机协同任务分配模型：

(8)

式中：效能函数F(Xi)=R(Xi)-C(Xi)，R(Xi)和C(Xi)分别代表无人机i执行任务获得的收益以及付出的代价。具体定义为

R(Xi)=nT(Xi)S(Xi)

(9)

C(Xi)=a1b1F1+a2b2F2+a3b3F3

(10)

式中：n为一个常数，T(Xi)∈[0,1]为目标任务威胁等级，S(Xi)∈[0,1]为目标任务执行成功概率。a1、a2和a3分别为航程代价函数F1、时间代价函数F2和损耗代价函数F3的权重系数，a1+a2+a3=1，b1、b2和b3为F1、F2和F3的归一化系数。

2 传统烟花算法

烟花算法启发于烟花爆炸的过程，主要由爆炸算子、变异算子、映射规则和选择策略4个部分组成[21]。其基本原则是：若一个烟花的适应度值比较好，则该烟花爆炸幅度比较小且产生的火星数比较多，目的是加快当前最优值附近局部搜索能力；相反，若某个烟花适应度值比较差，则该烟花爆炸幅度大且产生火星数较少，目的主要是为了增强种群多样性。

基于此，烟花算法伪代码如算法1所示：

算法1 传统烟花算法输入:烟花数目n,爆炸火花数nE,爆炸半径rE,爆炸数目限制因子a、b,变异火花数M输出:种群中最优个体p初始化烟花种群 for 每一个迭代周期:计算种群内各火花粒子的适应度f(xi)。将适应度排序,保留适应度最高的个体p到下一代。按照爆炸公式生成nE个爆炸火花。按高斯变异公式,随机选取M个火花进行高斯变异。对可行域范围外的火花按照映射规则映射到可行域内按照概率p(xi)=∑Nj=1xi-xj∑Nk=1∑Nj=1xk-xj选取n-1个烟花粒子进入下一代。end forreturn p

3 改进烟花算法

由于在传统烟花算法中，爆炸和变异操作均是对粒子进行的整体变换，因此，在迭代过程中会丢失很多烟花粒子内部所包含的可行解信息，进而导致陷入局部最优、收敛速度慢等问题。

针对本文的多无人机协同任务分配这一数学模型，传统烟花算法由于爆点范围大、爆炸以及变异产生的新一代烟花粒子发生聚集而产生不相关搜索等问题。

为了改善这种情况，提升算法效率，增强算法精度，本文提出一种改进烟花算法(SAGAFWA)，在传统烟花算法的基础上舍弃高斯变异操作，对每次迭代的最优个体引入遗传算法的变异算子，加强最优个体粒子内部的信息交流，增强算法的局部寻优能力，提高算法寻找最优解的效率。此外，增加模拟退火操作，增强算法的全局搜索能力，以跳出局部最优。

算法流程如图1所示。可以看出，改进后的烟花算法具体包括如下步骤：

图1 改进烟花算法流程图

步骤1初始化解空间并进行符号编码。基于本文的多无人机协同任务分配问题，首先根据无人机任务约束条件，采用符号编码的方式对问题进行编码，设置染色体P的长度为M以保证每个任务都有无人机分配并不会多次分配；然后确定种群内部烟花粒子的数目以及维数，初始化解空间，并计算所有解空间内烟花粒子的适应度函数值。

如图2所示，该烟花粒子表示有3架无人机执行5项任务。0号无人机执行1、4号任务，1号无人机执行2号任务，2号无人机执行3、5号任务。

图2 编码方式

(11)

步骤3爆炸。根据爆炸公式，得到初始种群中每一个个体爆炸产生的火花位置，并进行越界检查，对于越界的火花粒子，根据映射规则映射到可行域内。

以第i个烟花粒子xi为例进行说明：基于适应度函数公式，则可根据以下公式得到第i个烟花粒子爆炸生成的火花数量Ni和爆炸半径Ri，即

(12)

(13)

式中：fmax和fmin分别表示所有烟花粒子中适应度的最大值和最小值；ε为一个很小的常数，用来避免分子分母为0。

为了限制烟花爆炸产生火花的数量过多或过少，为每个烟花设定了产生火花数量的限制公式，即

(14)

爆炸产生的火花将在爆炸半径范围内随机产生位移，即

(15)

式中：xi,j表示烟花粒子xi爆炸生成的第j(1≤j≤Ni)个火花，k表示烟花粒子的第k维。

步骤4变异。由于传统烟花算法中的变异算子爆点范围大且是对粒子整体进行的变换，会导致新产生的变异粒子丢失原本烟花粒子内部包含的可行解信息，从而导致算法搜索效率低、搜索精度低等问题。因此，引入遗传算法的思想，生成变异火花，增强算法的局部寻优能力。以概率pm选取所有烟花粒子中的最优个体，然后进行随机位置的基因段变异生成新个体p′，如图3所示。

图3 变异操作

步骤5映射。为避免模拟退火、爆炸或变异产生火花的第k维度的值超出可行域，需要构建映射规则将其映射到可行域内。采用模运算的映射规则，其公式为

(16)

步骤6选择。将修正后的火花粒子，作为下一代的备选个体。根据选择策略公式计算出每个个体被选择的概率，采用轮盘赌的方式，优先选择被选概率高的个体作为下一代。为了保证下一代种群的多样性，选用欧氏距离来度量任意2个个体之间的距离，利用基于距离的选择算子选择剩下的n-1个个体，每个体被选中的概率为

(17)

基于上述步骤，改进烟花算法的伪代码如算法2所示。

算法2 改进烟花算法输入:烟花数目n,爆炸火花数nE,爆炸半径rE,爆炸数目限制因子a、b,模拟退火常数α,初始温度T,遗传变异概率pm。输出:种群中最优个体p。初始化烟花种群for每一个迭代周期: 计算种群内各火花粒子的适应度f(xi)。将适应度排序,保留适应度最高的个体p到下一代。do while T>Tmin: for 每一个温度迭代周期: 对最优个体p引入高斯扰动算子g,p′=pg,根据映射规则映射到可行域内 Δf=f(p′)-f(p)。 if Δf >0: 最优个体p=p′。 else: 按照Metropolis准则以一定概率接受新的最优解p′。 T=Tα end do按照爆炸式(12)生成nE个爆炸火花。按变异概率pm选取最优个体进行随机位置的基因段变异。对爆炸和变异产生的可行域范围外的火花按照映射式(16)映射到可行域内。按照概率式(17)选取n-1个烟花粒子进入下一代。end forreturn p

4 实验仿真

4.1 仿真环境

基于本文第1节构建的多无人机协同作业任务分配数学模型，绘制出400 km×400 km的区域仿真地图，如图4所示。

图4 仿真环境图

由仿真环境图可以看出，地图中有{a,b,c,d,e}共5架无人机，10个目标任务散布于400 km×400 km的仿真环境中，需要将图中的5架无人机分配给区域内的10个目标任务。其中，无人机和目标任务的具体属性如表1和表2所示。

表1 无人机属性信息

表2 目标任务属性信息

4.2 仿真结果与分析

设置初始烟花数目为100，爆炸火花数目nE=10，爆炸半径rE=2，爆炸数目限制因子a=0.5，b=0.6，模拟退火常数α=0.98，遗传变异概率pm=0.5。将迭代次数设置为N=100，并在N= 25，50，75，100时对分配结果进行采样，取其中一次实验结果，如图5和图6所示。

图5 改进烟花算法收敛曲线

图6 改进烟花算法分配方案

由SAGAFWA的收敛曲线以及分配方案的变化可以看出，SAGAFWA在迭代25次时的分配方案为{[a:10,6,5],[c:7,1],[d:3,2],[e:4,8,9]}，即无人机a依次执行任务10、6、5，无人机c执行任务7和1，无人机d执行任务3和2，无人机e依次执行任务4、8、9。算法迭代至50次期间一直陷入局部最优，分配结果保持不变，直到迭代75次后，因其算法性能的优势，成功跳出局部最优，分配方案变成{[a:6,5],[b:7,1],[c:4,10],[d:2,3],[e:8,9]}，迭代100次后，分配方案最终收敛为{[a:6,5],[b:7,1],[c:10],[d:2,3],[e:4,8,9]}。

4.3 算法对比

为了评估SAGAFWA在求解资源分配问题上的性能，以求解第1节构建的资源分配模型为例，即将5台无人机分配给10个任务目标，对遗传算法(Genetic Algorithm, GA)、FWA、和SAGAFWA进行对比实验，参数设置如表3所示。

表3 算法参数设置

基于上述参数设置，在上述3种智能优化算法的基础上，增加2组消融实验，即遗传烟花算法(GAFWA)和模拟退火烟花算法(SAFWA)，将迭代次数均设置为100，各执行10次，把最后输出最优解集中的3个优化目标飞行总航程F1、任务执行总时间F2、损耗代价F3以及目标函数值F的最优值和平均值进行比较，实验结果如表4所示。

表4 算法优化结果对比

可以看出，就优化目标无人机飞行总航程F1而言，2种传统智能优化算法均无法获得最优解；在对任务执行总时间F2的优化求解中，5种算法都可以得到最优值；以无人机损耗最小F3为优化目标时，FWA、GAFWA、SAFWA和SAGAFWA都具有寻得最优解的能力；而SAGAFWA对各优化指标都能寻得最优，且平均求解精度均优于其他4种算法。

为了对比5种算法的收敛速度，增加迭代次数至N=300后，其迭代收敛情况如图7所示。

如图7所示，GA收敛速度最快，但是最终在迭代20次后收敛于局部最优；FWA在迭代过程中不断跳出局部最优，迭代240次后逐渐收敛，可见FWA拥有比GA更强的全局搜索能力；相较于FWA，GAFWA和SAFWA在算法性能上有一定提升；而本文提出的改进烟花算法则综合了GA和SA的优势，拥有比FWA、GAFWA和SAFWA更快的收敛速度，5种算法中最高的求解精度，在迭代100次后收敛于最优解。

图7 算法收敛情况对比

由表5可以看出，GA存在的问题为：随着种群间个体的信息交互，受到最优个体的影响，每个个体会朝着最优个体的方向变化，导致算法收敛速度变快，但是失去了算法的多样性，容易陷入局部最优；FWA存在的问题是：传统烟花算法对每一代的烟花粒子做了爆炸、高斯变异等大量的个体变化操作，虽然增强了算法的全局搜索能力，但是算法花费大量时间，导致收敛速度变慢，搜索效率变低；SAGAFWA则借鉴了GA的优点，增强了算法的局部搜索能力并提高了收敛速度，此外，增加的模拟退火操作也增强了算法跳出局部最优的能力，从而获得了3种算法中最优的求解精度。

表5 算法性能对比

最后，选取3种公开测试函数(Rastrigin、Ackley、Beale)对算法性能进行测试验证。设置每类算法迭代次数为20，初始种群数为50，实验结果如表6所示。

表6 算法准确度对比

可以看出，GA在所有算法中性能最差，SAGAFWA在上述3类测试函数中均得到了5种算法中的最高求解精度，验证了算法的鲁棒性。

5 结 论

本文对资源分配问题的最优化求解进行了研究，提出了一种改进烟花算法，用遗传算法的变异算子替换传统烟花算法的高斯变异操作，增强算法局部寻优能力，并增加模拟退火步骤，提高算法跳出局部最优的能力。最后在对多无人机协同任务分配数学模型以及3种测试函数的求解上进行了仿真实验，结果表明改进烟花算法在收敛速度和求解精度上均优于其他3种烟花算法，并且具有较强鲁棒性。