膜计算框架下的多目标烟花爆炸算法

毛宗杨，陈韬伟，余益民，赵 昆

(云南财经大学 信息学院, 昆明 650221)

优化问题是科研和工程实践中常见的问题之一，按照目标函数的个数，可分为单目标优化和多目标优化。多目标优化问题(multi-objective optimization problems，MOPs)需要同时计算多个目标函数，这些目标函数之间通常是相互矛盾的，因此，存在一个折衷解的集合，称为Pareto最优解集或非支配解集。

最初，多目标优化问题的解决方法是将多个目标函数加权转化为单目标问题，采用数学规划方法进行求解，但效率较低，且它们对于权值或目标次序难以科学地确定[1]。

膜计算也称P系统，由Paun在1998年提出，并于2000年发表了第1篇相关论文[2]。 主要有以下几种类型的P系统：细胞型P系统[3]、组织型P系统[4]和神经型P系统[5]。目前，膜计算理论框架已广泛应用于计算机科学、语言学、经济学和生物学等众多领域。由于膜计算框架理论具有分布性、并行性、非确定性和可拓展性等特点[6]，它可引入上述的各种算法中实现进化计算、群智能计算与膜计算结合算法的新应用。Guo[7]利用膜系统的并行计算和分布式模型解决了SAT问题。Zhang等[8]将膜系统应用到GPU中，将GPU的串行方式改为并行方式。张群慧等[9]将粒子群算法引入膜系统中，并将其应用在云资源调度中从而提高了任务的处理效率。Sun等[10]将膜计算与PSO算法结合提出新算法MCBPSO,并用于处理复杂的优化问题。刘春秀等[11]将P系统与量子进化算法结合，并用于收集雷达辐射源信号。Lefticaru等[12]将膜系统与进化方法结合，拓展了膜计算的应用。Wang等[13]在膜计算的基础上提出单阈值图像分割技术，即利用膜计算的进化规则选取最优阈值。Pavel等[14]提出Enzymatic Numerical P系统，这是数值P系统的扩展。Song等[15]将信道状态和反向运输及通向转移引入膜系统中。Pan等[16]用扁平膜系统最大并行度处理了SAT问题。Singh等[17]将粒子群优化规则与膜系统结合来处理Blasius微分方程。

总之，采用P系统与进化计算、群智能算法相结合求解近似优化算法是目前研究的一个方向。从研究的成果来看，与P系统结合的算法多数是针对单目标优化算法的求解，对于高维度的多目标优化问题的研究较少，仍需要进一步的研究。本文在前期研究的基础上，将膜系统与烟花爆炸算法结合，提出了一种膜框架下的烟花爆炸算法。算法充分利用膜的分裂、合并等操作与基于烟花爆炸的寻优搜索方式相结合，能更好地平衡算法的局部开采和全局勘探的能力。在仿真实验中，采用标准函数ZDT和DTLZ系列对提出的算法进行测试。结果表明：该算法所得的非支配解集更接近真实Pareto前沿，在多样性、收敛性、准确性等方面优于或部分优于其他算法。

1 相关概念

1.1 多目标优化问题

多目标数学模型包括两个部分：两个及两个以上的目标函数、约束条件。多目标优化的最小化描述为式(1)：

F(x)=min{f1(x),f2(x),…,fm(x)}

s.thj(x)≥0,j=1,2,…,p

gi(x)=0,i=1,2,…,q

(1)

式(1)中有n个决策变量；x=(x1,x2,…,xn)⊆Rn，Rn为n维决策空间；F(x)=Rm表示m维目标空间，目标函数F(x)定义了决策变量与目标空间的映射关系；gi(x)表示q个等式约束；hj(x)表示p个不等式约束。

定义1(可行解) 对任意x∈Rm，并满足上式(1)中的约束条件，则称x为可行解。

定义2(Pareto占优) 对满足定义1的所有可行解组成的集合称为可行解集合，并用X表示，则X⊆Rn；若存在两个可行解分别为xa,xb∈X，xa与xb进行相比较，xa是Pareto占优的则满足下面条件：

∃i=1,2,…,m;fi(xa)

∀j=1,2,…,m;fj(xa)≤fj(xb)

(2)

记作xa

定义3(Pareto最优解) 如果存在一个X*满足：X*={x∈Rn|﹁ ∃x′∈

定义4(Pareto前沿) 最优解集X*在目标函数空间上的映射，即：

PF=F(x*)=min{f1(x*),f2(x*),…,

fm(x*)|x*∈X*}

(3)

映射后的集合称为Pareto前沿。

1.2 膜计算

膜计算(membrane computing)是从细胞的结构和功能以及组织或神经元中细胞的相互作用中抽象出来[18]。膜系统指由多个膜组成并且每层膜都是一个计算单元，所以膜系统有并行计算和分布式的特性。

膜系统由以下3部分组成：膜结构、对象多重集和反应规则[6]。用字符对象和多重集表示所求优化问题的可行解和可行解集。反应规则既有对膜结构的操作又有对字符对象的操作。本文采用细胞型的膜系统进行研究。细胞型膜系统的模型介绍如下：

∏={V,T,u,w1,w2,…,wn,R}

(4)

根据式(4)知：V为字母表，其中的元素为字符对象。细胞中分子和化学物质抽象为字符对象。T⊆V,T表示输出字母表；u表示含有n个膜的膜结构，n为膜系统Π的度；wi∈V*，i=1,2,…,m，wi表示u中第i个膜内包含字符对象的多重集，V*为V中字符对象组成的字符多重集；R为进化规则的有限集合，Ri,i=1,2,…,m,为膜结构u中第i区域的进化规则。

细胞型膜系统的结构如图1所示，图中最外层的膜为表层膜，用于将细胞外和细胞膜的内部结构分隔开。每个膜都有一个确定的区域，每个区域中反映规则和多重集。若某个区域中不包含膜，称为基本膜。

图1 细胞型的膜系统结构

1.3 精英反向学习

反向学习(opposition based learning)由Tizhoosh提出，在全局最优的问题上反向解比当前解更接近最优解。反向学习是在个体当前所在的区域产生反向个体，同时将当前个体与反向个体一同竞争，竞争后产生的个体进入下一代。

定义6(反向解优化) 假设优化问题为公式(1)中最小化优化问题，假设存在一个当前解X，设X′为其反向解，则更新机制如下：如果XX′，则保留X′。如果X和X′彼此间非支配，则随机选择X或X′进行保留。

在多目标优化问题中一般将非支配解称为精英个体，精英个体中包含许多将种群向最优Pareto前沿收敛的信息。加强对精英个体所在区域的搜索会使算法的收敛速度和全局搜索能力得到改善。

1.4 烟花爆炸算法

1.4.1 烟花爆炸算法的优化机制

烟花爆炸算法(fireworks algorithm，FWA)是模拟现实生活中烟花爆炸的现象，将烟花爆炸的空间看成优化问题的搜索空间，用爆炸点和爆炸点爆炸产生火花的位置来表示优化问题的解。根据已有的火花和爆炸点进行选择，使相对较理想的火花位置保留下来，不停迭代直至得到满意结果。

烟花爆炸算法具有全局搜索和局部搜索能力。每个火星产生的爆炸半径和火星的个数是不同的，如果烟花的适应度值较好(适应度值较小)则在较小的范围内产生较多的火星因此具有开采性，反之在较大的范围内产生较少的火花因此具有勘探性。

*(rinit-rend)+rend

(5)

(6)

如果搜索空间是低维度，选择坐标轴为爆炸方向，假设为n维(n<10)，那么爆炸的方向为2n个。如果搜索空间是高维度，继续用2n个爆炸方向，此时会消耗大量的空间，所以每层爆炸方向采用从2n个方向中随机选n/3个方向同时再加上这n/3个方向的相反方向。以二维的搜索空间为例，如图2所示，其中圆心处黑点表示爆炸点，坐标轴上的圆圈表示火星。

图2 二维空间爆炸点的方式

对火星和爆炸点的边界进行限制设xi(i=1,2,…,n)为搜索空间中的决策变量，并且xi属于[ai,bi]，如果有火星xj超出边界[ai,bj]，则要将xj在第i维上的值重置，火星的重置有利于火星多样性的提高，重置方式如(7)所示。

(7)

rand( )是[ai,bj]中的均匀随机数。

1.4.2 选择火星

从第二代开始将会产生大量火星，将火星和爆炸点一起进行选择，选出较优的火星进行下一次爆炸。为保持火星多样性和种群的规模采用基于距离的方式进行筛选。设xi属于m,m是爆炸点和火星的集合，xi与m中其他元素的距离之和如式(8)所示。

(8)

选中xi的概率为P(xi),如式(9)所示。

(9)

对p(x)进行降序排序，选择排序较前的个体。

综上所述，因为膜系统是由多个膜组成，每层膜都是一个计算单元，所以膜系统有并行计算和分布式的特性。而烟花爆炸算法在求解优化问题时具有随机性、局部性、爆发性、隐并行性、多样性和瞬时性等特点，满足在某一范围内的解和其邻域解拥有相似的性质。因此，将膜框架与烟花爆炸算法结合对求解优化问题是可行的。在基本膜中，烟花的种群中所有的烟花根据适应度值进行信息的交互和资源的分配，增加了种群的多样性，克服算法早熟收敛。最后，在表层膜中的精英反向学习的应用，反向解比当前的解更接近全局最优，有利于多目标优化问题的求解。

2 膜计算框架下的烟花爆炸算法

用外部档案来存放最优字符对象，为确保外部档案内字符对象的多样性和整体数量的稳定，引入精英反向学习和NSGA-Ⅱ算法中的拥挤距离与非支配排序。

拥挤距离指在相同的非支配等级中两字符对象的距离，如式(10)所示。

(10)

通过式(10)计算完拥挤距离之后对字符对象进行拥挤距离排序，即将字符对象通过拥挤距离进行降序排序。

基于膜框架下的烟花爆炸算法的具体步骤如图3所示。

图3 算法执行流程

设搜索空间为m维，目标数目为n，字符对象规模为N，外部档案的容量为M。则烟花爆炸算法的时间复杂度如下：

步骤1 在优化问题的约束条件得到满足的基础上，对字符对象进行初始化(初始化时间复杂度为O(mN))，即在表层膜内随机生成N个字符对象，并且用十进制对字符对象进行编码，描述形式如(式11)所示。

(11)

步骤2 对目标算法的每个字符对象进行计算，求出适应度值并根据适应度值确定火星质量的好坏。适应度值好的获取的资源相对多；相反，适应度值差的获取资源少。

步骤3 初始化操作后，在表膜的内部使用分裂规则，分裂出M个基本膜，将初始化后的M个多重集发送到M个基本膜内。使用并行膜结构的形式如式(12)所示。

[ ]0→[ [ ]1, [ ]2, …, [ ]m]

(12)

其中：M为基本膜层数；[ ]0为表膜；[ ]m为第m个基本膜。

为使每个基本膜都有与其对应的多重集，需要对多重集对象进行划分，首先需求出各字符对象的适应度，并进行非支配排序，然后将排序好的多重集分成等大小的子集。具体操作见式(13)。

w*=sort(w)

w*={w1,w2,…,wm}

n=sizeof(w)/m

(13)

式中：w为多重集；sort( )为对w进行非支配排序；wi为多重集的第i个子集；sizeof(w)为多重集内字符对象的个数；n为每个基本膜内字符对象的个数。

步骤4 利用通信规则将表层膜内的多重集发送给基本膜。利用选择规则依据拥挤距离选择字符对象，拥挤距离与非支配排序的引入提高了算法的局部搜索能力。

步骤5 在基本膜内执行烟花爆炸算法实现字符对象的重写规则。通过爆炸半径计算方式(5)，爆炸点i产生火星的迭代公式(6)等对基本膜内的字符对象进行操作(一个爆炸点爆炸产生火星的时间复杂度为O(8n2/3),N个爆炸点产生火星的时间复杂度为O(8Nn2/3))。

步骤6 以上操作完成后调用溶解规则，当m个基本膜溶解后基本膜中的多重集全部进入表层膜中。并将字符对象放入外部档案中，然后将字符对象进行精英反向学习(运行精英反向学习的时间复杂度为O(nM))，最后将表层膜和外部档案中的字符对象进行非支配排序(外部档案多样性维护的时间复杂度为O(n(N+M)2log(N+M))，将非支配等级小的字符对象重新组合作为下一代多重集(产生下一代字符对象的时间复杂度为O(mN2))。

步骤7 外部档案使算法能快速地收敛到真实的目标前沿，外部档案中引入精英反向学习增强了算法全局搜索能力，因此该算法跳出局部极值的能力得到了提高。外部档案实现如下：① 对字符对象进行拥挤距离和非支配排序操作；② 根据结果选取非支配等级相对较低的字符对象，若存在两字符对象非支配等级相等，则比较两字符对象的拥挤距离，选择拥挤距离相对较大的对象；③ 通过以上操作，将选取的字符对象放入外部档案内，然后将字符对象进行精英反向学习，最后删除档案中受支配的字符对象将外部档案中剩余的字符对象作为下一代多重集。

步骤8 若不满足终止条件，从步骤2开始继续执行；若满足条件，算法结束，将表层膜内的多重集输出。

3 仿真实验

3.1 实验设置

1) 多目标优化算法及测试函数

为测试膜框架下烟花爆炸算法的性能选取6个多目标优化函数与其进行对比，分别为：GrEA、IBEA、MOMB-Ⅲ、NSGA-Ⅱ、NSGA-Ⅲ和SPEA-Ⅱ。测试函数采用ZDT和DTLZ系列的函数，ZDT系列的函数为：ZDT1、ZDT2和ZDT3，DTLZ系列的函数为：DTLZ1、DTLZ3和DTLZ7。

2) 参数设置

根据文献[19]将烟花爆炸算法的半径递减指数α设为5，算法的初始爆炸半径rinit=a*(xi,max-xi,min)，a∈[0.05,0.3]，rend的值为10-6。论文的膜系统由5层膜组成。

进行比较实验时各多目标优化算法在两个目标的测试函数中将外部档案的容量M=100,字符对象设置为N=100，算法的迭代次数为1 000；3个目标的测试函数外部档案的容量M=100,字符对象设置为N=100，算法的最大迭代次数为10 000。

仿真实验在联想天逸310笔记本上运行，使用Windows 10 X64 操作系统，4 G内存，2.4 GHz双核CPU，算法用Matlab实现。

3) 性能指标

本文用反转世代距离(inverted generational distance，IGD)的方法对算法性能进行评估。IGD是度量算法获取的近似Pareto前沿与真实Pareto前沿之间的距离。IGD的值越低，说明算法的多样性和收敛性越好。IGD的表达式如式(14)所示：

(14)

3.2 实验结果分析

多目标优化算法在两个目标的测试函数(ZDT1、ZDT2和ZDT3)下运行的结果分别如图4～6所示。

图4 基于ZDT1测试函数分布

图5 基于ZDT2测试函数分布

图6 基于ZDT3测试函数分布

图4为各多目标优化函数在测试函数ZDT1下的运行结果，图中黑线为真实Pareto前沿，从图4可以看出FWA算法更接近真实Pareto前沿，其他算法的效果相对比较差。图5为ZDT2测试函数下不同算法的测试结果，相对于NSGAⅢ算法，其他算法比较逼近真实Pareto前沿，效果最好的是FWA算法。图6为ZDT3测试函数下不同算法的分布情况效果，比较理想的是FWA算法。

烟花爆炸算法在3个目标的测试函数DTLZ1、DTLZ3和DTLZ7下的测试结果如图7所示。

对7个多目标优化算法在6个测试函数下IGD的平均值(mean)、标准差(std.)的比较如表1所示，图中粗体字表示在相同测试函数下IGD最小的值。

由表1可以得出：在相同测试函数下膜框架下的烟花爆炸算法比其他算法的IGD值都小，因此该算法比其他算法更占优。

因为IGD能同时反映一个算法的多样性和收敛性，本文提出算法与其他算法对比显示出较好的多样性和收敛性，说明烟花爆炸算法与膜系统结合较好地平衡了烟花算法的开采和勘探过程。

图7 基于3个目标测试函数分布

测试函数GrEAMeanStd.IBEAMeanStd.MOMB-IIIMeanStd.NSGA-IIMeanStd.NSGA-IIIMeanStd.SPEA-IIMeanStd.FWAMeanStd.ZDT12.32×10-18.63×10-13.37×10-11.24×10-12.86×10-19.14×10-22.88×10-13.40×10-15.49×10-11.50×10-12.32×10-14.08×10-12.87×10-23.97×10-2ZDT22.75×10-11.22×10-14.52×10-12.57×10-23.40×10-11.33×10-13.23×10-18.21×10-15.71×10-19.98×10-23.07×10-18.20×10-23.01×10-23.08×10-2ZDT31.02×10-13.01×10-24.12×10-11.47×10-11.99×10-11.15×10-11.45×10-11.06×10-13.90×10-11.08×10-11.35×10-18.70×10-28.03×10-28.44×10-2DTLZ12.63×10-11.29×10-12.12×10-18.33×10-21.94×10-11.54×10-14.02×10-17.88×10-34.58×10-13.16×10-12.30×10-12.94×10-17.80×10-28.92×10-2DTLZ35.61×10-02.12×10-04.50×10-01.76×10-06.16×10-02.06×10-04.26×10-03.06×10-08.19×10-02.55×10-04.18×10-02.64×10-03.54×10-14.19×10-1DTLZ72.26×10-24.77×10-42.79×10-22.56×10-32.54×10-21.98×10-25.94×10-33.20×10-41.87×10-26.68×10-34.15×10-21.38×10-31.53×10-33.32×10-4

论文给出7种多目标优化算法在6种测试函数下的均值和方差排名情况，如图8所示。

图8 IGD均值和方差

图8显示结果可以看出：膜框架下的烟花爆炸算法在方差排名及均值排名相对于其他优化算法比较占优。这表明膜框架下的烟花爆炸算法相对于其他优化算法有较好的稳定性和准确性。

因为IGD能反映一个算法的多样性和收敛性，故采用IGD排名的方差和均值来比较各算法的稳定性与准确性。因此，由表1和图8可以得出：膜框架下烟花爆炸算法的多样性、收敛性、稳定性和准确性均优于其他多目标优化算法。

4 结束语

为了更好地解决生活中复杂的多目标优化问题，本文将膜系统与烟花爆炸算法结合，同时在外部档案中应用精英反向学习的方法。文中将该算法与其他6种多目标优化算法在6种测试函数上进行测试并得出IGD的值。实验表明：膜框架下的烟花爆炸算法相对于其他优化算法有显著的稳定性、准确性和收敛性，说明烟花爆炸算法与膜系统结合能有效地解决多目标优化问题。