基于膜系统的粒子群算法

Particle Swarm Optimization Algorithm Based on Membrane System

摘要: 由于粒子群算法具有易于理解实现等特点，受到科学与工程领域的广泛关注，但其搜索策略较为单一，使得算法很难获得Pareto前沿且容易陷入局部最优和无限迭代，在全局搜索和收敛性方面还有一定的不足。受P系统理论启发，本文提出了一种基于膜系统框架的多目标粒子群优化算法用于解决多目标优化问题。根据P系统的层次结构、对象和规则，在基本膜中采用粒子群算法实现并行搜寻策略，在表层膜中采用非支配排序和拥挤距离机制来提高算法收敛速度，并通过进化规则以保持解的多样性。仿真实验采用KUR、ZDT系列和DTLZ系列测试函数对MPSO算法进行测试，并与其他多目标优化算法进行对比，包括MOPSO、dMOPSO、SMPSO、MMOPSO、MOEA/D、SPEA2、PESA2、NSGAII。实验结果表明：新算法能够保证解的多样性，快速收敛并接近于真实的Pareto前沿。

Abstract: Due to the particle swarm algorithm has the characteristics of easy understanding and implementation, it is widely concerned in the field of science and engineering, but its search strategy is relatively simple, making it difficult for the algorithm to obtain the Pareto frontier and easy to fall into local optimal and infinite iteration. There are still some deficiencies in the aspect of global search and convergence. Inspired by the P system theory, this paper proposes a multi-objective particle swarm optimization algorithm based on the membrane system framework to solve the mul-ti-objective optimization problem. According to the hierarchical structure, objects and rules of P system, the particle swarm algorithm is used to implement the parallel search strategy in the base film. The nondominated sorting and congestion distance mechanism are used in the surface film to improve the convergence speed of the algorithm, and the evolution rule is used to maintain the diversity of solution. The simulation experiment uses the KUR, ZDT series and DTLZ series test functions to test the MPSO algorithm and compare it with other multi-objective optimization algorithms, including MOPSO, dMOPSO, SMPSO, MMOPSO, MOEA/D, SPEA2, PESA2, NSGAII. The experimental results show that the new algorithm can guarantee the diversity of the solution, is fast convergence and close to the real Pareto frontier.

1. 引言

现实中许多工程和科学问题都存在多个彼此相互冲突的问题，如：相同材料的强度和重量，商品的成本和质量。如何求得这些问题的最优解是工程和学术领域的焦点问题。和简单的单目标优化问题不同，多目标问题最大特点是在提高某些目标的性能时，会降低其它某些目标性能，同时求得所有目标的最优解是不可能的。多目标问题就是在不同目标间进行协调，使每个目标性能尽可能达到最优。但这会导致数量较多的最优解，甚至达到无穷多个 [1]。

解决多目标优化问题的原始方法通常会将问题转换成单目标优化，采用数学规划方式进行求解，每次只能得到一种权重情况下的解。但对于多目标优化的目标函数和约束函数可能是非线性、不可微或不连续的，故采用传统的数学规划方法效率较低，且对于权重和目标给定的次序较敏感 [2]。由于粒子群算法概念简单、易于实现，越来越多的学者尝试运用将粒子群算法与其它优化算法融合解决多目标优化算法问题。Li最早将粒子群优化(Particle Swarm Optimization, PSO)与NSGA2结合用于解决多目标优化问题 [3]；Coello等人在PSO中采用自适应网格的方法，提出了经典的MOPSO算法 [4]；张提出了一个基于粒子群优化膜计算理论的云计算资源调度算法 [5]；Liu等提出了将遗传机制引入到膜系统的膜算法，该求解ZDT优化问题表现出了较好的求解性能 [6]；Parsopoulos和Vrahatis提出了一种目标聚合的多目标粒子群算法，采用固定的和自适应的权重组合将多目标优化问题转换为单目标优化问题，然后采用基于粒子群算法进行求解，但每运行一次算法只能获得一个Pareto最优解 [7]；Hu和Eberhart提出了一种动态邻近法来求解多目标优化算法，采用动态邻近策略来为粒子选取最优经验，但一次只能对一个目标寻优，其本质还是用一维的方法来处理多目标 [8]；Dou在膜系统上提出了一种新的粒子群优化算法用于膜系统的特征选择，利用P系统的层次结构和消息机制，将粒子群算法作为子算法引入所有基本膜中 [9]。

与其它多目标优化算法相比，MOPSO有着收敛速度快的特点，但其在解均匀性和并行性方面表现较差。由于膜结构具有良好的并行性，并且结构简单，易于与其他进化算法相融合等特点，部分学者尝试将膜计算理论与粒子群算法相结合，但其基本应用于单目标问题，无法直接应用于多目标优化问题。本文将膜计算理论与粒子群算法相结合，提出膜粒子群算法，充分利用膜的分裂及规则，在基本膜中采用粒子群算法实现并行搜寻策略，在表层膜中采用非支配排序和拥挤距离机制来提高算法收敛速度，并通过进化规则以保持解的多样性。

为验证MPSO算法的有效性和可行性，在仿真实验中采用KUR、ZDT系列与DTLZ系列目标函数进行测试。实验结果表明：该算法所得的非支配解集不易陷入局部最优，快速收敛并接近于真实的Pareto前沿，在解集的多样性与算法的收敛性和准确性等方面优于或部分优于其他算法。

2. 相关概念

2.1. 多目标优化问题

自然界中存在着大量多个目标彼此冲突的优化问题，这类问题被称为多目标优化问题。利用目标函数可以从数学角度对其算法优化性能进行衡量，因此，一般多目标优化问题(MOP)可被描述如下：

$\begin{array}{l}\text{min}\text{f}(x)=[{{\displaystyle f}}_1(x),{{\displaystyle f}}_2(x){{\displaystyle ,\cdots ,f}}_M(x)]\\ st{.}_{h(x)=[{{\displaystyle h}}_1(x),{{\displaystyle h}}_2(x){{\displaystyle ,\cdots ,h}}_K(x)]=0}^{g(x)=[{{\displaystyle g}}_1(x),{{\displaystyle g}}_2(x){{\displaystyle ,\cdots ,g}}_J(x)]\ge 0}\\ {{\displaystyle {{\displaystyle x}}_i}}^{(L)}\le {{\displaystyle x}}_i\le {{\displaystyle x}}^{(U)},i=1,\cdots ,N\end{array}$ (1)

(1)式中 $X={{\displaystyle ({{\displaystyle x}}_1,{{\displaystyle x}}_2,\cdots ,{{\displaystyle x}}_N)}}^T$ 为 $N$ 维决策向量，且取值在 ${{\displaystyle {{\displaystyle x}}_i}}^{(L)}\le {{\displaystyle x}}_i\le {{\displaystyle x}}^{(U)}$ 之间； $f(x)$ 定义了 $M$ 个目标函数；(1)中定义包含了 $J$ 个不等式约束 $g(x)$ 与 $$ 个等式约束 $h(x)$ ，约束函数 $\text{g}(x)$ 与 $h(x)$ 共同确定决策向量中 $X$ 的可行域。

定义1可行解：对任意解向量 $x\in \theta$ ，若满足(1)式中的约束条件 $g(x)$ 与 $h(x)$ ，则称为可行解，否则为不可行解。

定义2 Pareto支配：对于决策变量和 $b={{\displaystyle [{{\displaystyle b}}_1,{{\displaystyle b}}_2,\cdots ,{{\displaystyle b}}_n]}}^T$ ，当且仅当 $\forall i\in \{1,2,\cdots ,m\}$ ， $\exists j\in \{1,2,\cdots ,m\}$ ，使得 ${{\displaystyle f}}_i(a)\le {{\displaystyle f}}_i(b)$ 成立，称a支配b，记为 $b\prec a$ 。若它们之间不存在Pareto支配关系，则称它们为非支配。

定义3 Pareto最优解：如果满足 $X^{*}=\{x\in R^n|\neg \exists x\text{'}\in \prec x\}$ ，则 ${{\displaystyle X}}^{*}$ 为Pareto最优解集或非支配解集，也可写为 ${{\displaystyle PS}}^{*}$ ， ${{\displaystyle R}}^n$ 为解集的决策空间。

定义4 Pareto前沿：Pareto最优解集对应在目标函数空间上的映射集合，即 ${{\displaystyle PF}}^{*}=\{f({{\displaystyle x}}^{*})|{{\displaystyle x}}^{*}\in {{\displaystyle PS}}^{*}\}$ ，映射后的集合称为Pareto前沿。

2.2. 粒子群算法

粒子群优化算法最早源于模拟生物群体的社会行为，是一类基于群体智能的随机优化算法，由Kenney和Eberhart于1995年提出 [10]。算法将模拟鸟群中每一只鸟称为一个“粒子”，它们以一定的速度和方向飞行，根据自身和同伴的飞行经验动态调整，鸟群所寻找的食物就是我们希望求得问题的最优解。鸟群中的鸟(即粒子)第t + 1次飞行的速度和飞行后的位置根据如下公式确定：

$\begin{array}{l}{{\displaystyle V}}_{\text{t}+1}=\omega *{{\displaystyle V}}_{\text{t}}+{{\displaystyle c}}_{\text{1}}*rand()*(pBest-{{\displaystyle X}}_{\text{t}})+{{\displaystyle c}}_{\text{2}}*Rand()*(gBest-{{\displaystyle X}}_{\text{t}})\\ {{\displaystyle X}}_{\text{t+1}}\text{=}{{\displaystyle X}}_{\text{t}}\text{+}{{\displaystyle V}}_{\text{t+1}}\end{array}$ (2)

${{\displaystyle V}}_{\text{t}}$ 和 ${{\displaystyle V}}_{\text{t+1}}$ 分别是第 $t$ 和第 $t+1$ 次飞行的速度； ${{\displaystyle X}}_{\text{t}}$ 和 ${{\displaystyle X}}_{\text{t+1}}$ 分别是经过第 $t$ 和 $t+1$ 次飞行后粒子落在的位置； $\omega$ 为惯性权重(inertia weight)，描述粒子的惯性对当前速度的影响，其大小用来平衡局部和全局的搜索能力； ${{\displaystyle c}}_1$ 和 ${{\displaystyle c}}_2$ 为个体最优和全局最优的学习因子； $rand()$ 和 $Rand()$ 是 $[0,1]$ 上相互独立的随机数； $pBest$ 是该粒子历次飞行中“最好”的位置； $\text{g}Best$ 是种群中“最好”的粒子位置。经过多次迭代，种群中的粒子会逐渐向“更好”的位置飞行，最终求得最优解。

2.3. 膜系统

作为自然计算的新分支，膜计算(或称为P系统)由Păun于1998年在芬兰图尔库计算机中心的研究报告中提出，正式论文于2000年见刊发表 [11]。这类计算模型被称为膜系统或P系统，共分为三种类型：细胞型P系统 [12] 、组织型P系统 [13] 和神经型P系统 [14]。P系统由分层的膜结构，对象的多重集和规则组成，具有分布式、极大并行性、非确定性和可扩展性等特点，且易于与其他进化算法相结合 [15]。本文采用具有分层结构的细胞型P系统，其结构如图1所示。

图1中的膜结构由6层膜组成，最外层膜称为表层膜，它将细胞内部结构与外界环境隔开。不包含其他膜结构的称为基本膜，每个膜所包围的部分称为区域。多目标对象用大小写字母表示，常见的进化规则类型有多重集重写规则(例如 $d\to dy,y\to c$ )和运输规则等 [16]。

根据图1可将1) $V$ 是目标对象的字母表，其包含的元素为字符对象；

2) $T\subseteq V$ 是输出字母表；

3) $C\subseteq V$ 是催化剂；

4) $\mu$ 是一个由 $m$ 个膜组成的膜结构，各个膜及其所围的区域用标号集 $H$ 表示， $H=\{1,2,3,\cdots ,m\}$ ，其中 $m$ 称为膜系统 $\prod$ 的度；

5)表示膜结构 $\mu$ 中区域 $\text{i}$ 包含的对象多重集；

6) $R_{\text{i}}(1\le \text{i}\le m)$ 是关于膜系统 $\prod$ 和区域 $\mu$ 的进化规则的有限集；

7) 膜结构可等价表示为： ${\displaystyle \prod \text{=}}\{V,T,C,\mu ,{{\displaystyle \omega }}_1,{{\displaystyle \omega }}_2{{\displaystyle ,\cdots ,\omega }}_m,{{\displaystyle R}}_1,{{\displaystyle R}}_1,\cdots ,{{\displaystyle R}}_m\}$ 。

P系统是从活细胞在内部结构处理化合物的方式中抽象出来的一种计算模型 [17]。在膜结构所定义的区域中，目标对象用字符表示，根据给定的规则实现进化。因此膜系统作为一个建模框架可以很好的与其他进化算法相结合，用来构建一个用于求解近似优化的多目标进化算法，具有易于理解、可扩展性和可编程性、固定分块性和处理离散数据的能力等优点 [18]。

Figure 1. Cell type P system structure

图1. 细胞型P系统结构

3. MPSO

受膜系统功能和在分层结构中处理化合物的方式启发，结合粒子群算法本文提出了一种基于膜系统框架的多目标粒子群算法(a multi-object particle swarm optimization algorithm based on the framework of membrane system, MPSO)。MPSO中采用具有层次结构的细胞型P系统，用字符对象表示优化问题的可行解，由字符对象组成的解集构成多重集。利用类细胞P系统理论，规则包括受PSO启发的进化规则、P系统的进化规则和置换规则。根据膜系统的分层结构，利用粒子群优化的个体最优和全局最优概念，在基本膜中采用粒子群算法实现多搜寻策略并行更新解，通过进化规则保持搜索解的多样性。在表层膜中，利用外部档案使用非支配解集和拥挤距离机制提高非支配解的多样性和算法收敛速度，使解集近似于Pareto前沿。

拥挤距离是判断外部档案中粒子(字符对象)与相邻个体间远近的指标，如式(3)所示。拥挤距离越大说明该个体与其他个体越分散。

${{\displaystyle \text{d}}}_i={\displaystyle {\sum }_{m=1}^n\frac{{{\displaystyle f}}_m^{i+1}-{{\displaystyle f}}_m^{i-1}}{{{\displaystyle f}}_m^{\max }-{{\displaystyle f}}_m^{\min }}}$ (3)

式(4)中， $n$ 表示目标函数的个数， ${{\displaystyle d}}_i$ 表示第 $i$ 个字符对象在种群中的拥挤距离， ${{\displaystyle f}}_m^{\max }$ 和 ${{\displaystyle f}}_m^{\min }$ 分别表示种群中第 $m$ 个目标取得的最大值和最小值， ${{\displaystyle f}}_m^{i+1}$ 和 ${{\displaystyle f}}_m^{i-1}$ 个字符对象在第 $$ 维两侧最临近点的目标函数值，其中 ${{\displaystyle f}}_m^{i-1}\le {{\displaystyle f}}_m^{i+1}$ 。

基于膜系统的粒子群算法的具体步骤如图2所示。

Figure 2. Algorithm flowchart

图2. 算法流程图

步骤1. 初始化及适应度评估。在表层膜内生成 $N$ 个字符，每个字符包含 $D$ 维变量，并在满足多目标优化问题约束的前提下，采用10进制的编码方式依次对 $N$ 个字符进行初始化，其描述公式如公式(4)所示。

${{\displaystyle S}}_{i,j}=({{\displaystyle S}}_{\max ,j}-{{\displaystyle S}}_{\min ,j})*rand()+{{\displaystyle S}}_{\max ,j}$ (4)

其中 ${{\displaystyle S}}_{i,j}$ 表示第 $i$ 个的第 $j$ 维目标对象 $(N\ge i\ge 1,D\ge j\ge 1)$ ， $N$ 为目标对象数目(粒子的数目)， ${{\displaystyle S}}_{\min ,j}$ 与 ${{\displaystyle S}}_{\max ,j}$ 分别表示矩阵 $S$ 中的最小值和最大值，利用函数 $rand()$ 随机生成0至1之间的数字。

步骤2. 根据适应度求出当前字符中Pareto前沿点，时间复杂度为 $O({{\displaystyle N}}^2)$ 。

步骤3. 初始化外部档案， ${{\displaystyle []}}_0\to {{\displaystyle [{{\displaystyle []}}_1,{{\displaystyle []}}_2,\cdots ,{{\displaystyle []}}_m]}}_0$ 操作是在表层膜内调用分裂规则创建 $m$ 个基本膜，利用NSGA-II中的非支配排序机制，将字符对象根据公式(5)分派给 $m$ 个基本膜。

$\begin{array}{l}\omega =sort(\omega )\\ \omega =\{{{\displaystyle \omega }}_1,{{\displaystyle \omega }}_2,\cdots ,{{\displaystyle \omega }}_m\}\\ n=\frac{sizeof(\omega )}{m}\end{array}$ (5)

$\omega$ 为字符对象解集，函数 $sort()$ 利用非支配排序返回一系列解 $\omega$ 并在解集 $\omega$ 中使用通信规则 $(w,in)$ ， $n$ 表示每个基本膜中字符对象的数量。

步骤4. 在基本膜内独立执行粒子群算法。各个基本膜内以最先存入外部档案内的Pareto前沿点为种群“最优”个体，运用公式(2)和(3)计算并更新个体速度和位置，再重新计算适应度。

步骤5. 溶解。完成各自的粒子群算法后，调用基本膜内的溶解规则从而使各个基本膜破裂，将新产生的字符(个体)重新释放到另一基本膜内。直至所有基本膜都被溶解，并根据通信规则 $(w,\text{out})$ 将新产生的字符放入表层膜内。

步骤6. 计算前沿点，存入外部档案。若Pareto前沿点数量小于预设数值 $R$ ，则直接将所有点存入外部档案中。若Pareto前沿点数量大于预设数值，根据公式(4)计算所有Pareto前沿点的拥挤距离，从拥挤距离最小的点开始逐一删除，直至备选存入外部档案的Pareto前沿点数量与预设数值相等，在将这些前沿点存放在外部档案中。

步骤7. 计算非支配排序，更新外部档案。判断外部档案字符数量是否超出限制，若超出限制，重新计算档案内所有字符的拥挤距离和非支配的等级，找出非支配等级小的字符。若存在两个字符对象非支配等级相等，需比较两个字符对象的拥挤距离，并选取拥挤距离大的一方，重复操作直至外部档案内字符数量与预设值相等。在表层膜中使用公式(5)并利用重写规则 $u\to v$ 更新外部档案中的字符对象。

步骤8. 迭代。设置最大迭代次数作为终止条件，判断当前状态是否满足结束循环条件，若不满足，则继续执行。

步骤9. 输出外部档案内的所有字符，即Pareto前沿点。

4. 仿真实验

4.1. 实验设置

为验证算法性能，采用ZDT系列与DTLZ系列函数进行测试，并与其他代表性几个最具代表性的多目标优化算法(包括MOPSO、SPEA2、PESA2)进行对比。MPSO算法中的学习因子(或加速度系数) $c_1$ 与 $c_2$ 设定为2，二维目标的测试函数KUR、ZDT中的外部档案容量为100，三维目标的测试函数DTLZ中的外部档案容量为200；不同的多目标优化算法对二维目标测试函数迭代10,000次，对三维目标测试函数DTLZ迭代100,000次；独立运行各个算法30次，计算IGD的均值；基本膜的数量为10个。

4.2. 二维目标实验结果分析

对每种算法分别进行30次近似Pareto前沿计算，使用IGD (inverted generational distance，反转世代距离)度量算法获取的近似Pareto前沿与真实Pareto前沿之间的距离，评估算法性能。实验结果如图3所示。

对比观察KUR测试函数下各算法求得的近似Pareto前沿点，可以看出新算法与SPEA2、PESA2结果基本相近，前沿点分布较均匀，不管是收敛速度还是质量都优于传统MOPSO算法。

对比观察ZDT1和ZDT2测试函数下各算法求得的近似Pareto前沿点(图4与图5)，可以看出新算法和MOPSO算法的收敛情况明显优于SPEA2和PESA2算法。但与MOPSO相比，新算法的近似Pareto前沿点分布更加均匀。

Figure 3. The approximate Pareto frontier distribution point map under KUR

图3. 在KUR下求得近似Pareto前沿分布点图

Figure 4. The approximate Pareto frontier distribution point map under ZDT1

图4. 在ZDT1下求得近似Pareto前沿分布点图

对比观察ZDT3和ZDT6测试函数下各算法求得的近似Pareto前沿点(图6与图7)，可以看出各算法结果基本相近。在ZDT3测试函数下，近似Pareto前沿点在段新算法要稍优于其他三种算法。

IGD数值的高低能够反映算法的收敛性与多样性，故根据表1所示的IGD性能数据，可以看出MPSO对比于其他优化算法在KUR、ZDT3、ZDT6测试函数上相对占优，说明MPSO具有较好的收敛性、多样性以及稳定性。

4.3. 三维目标实验结果分析

为进一步检验算法对多目标优化的能力，将MPSO与其他五种基于PSO的多目标优化算在测试函数上进行对比分析，实验结果如表2所示。IGD数值的方差(Std.)和均值(Mean)反映了算法的稳定性与准确性，根据表2所示，MOEA/D在ZDT1、ZDT5、ZDT5、ZDT6测试函数上IGD数值最小。总体而言，MPSO相对于dMOPSO、SMPSO、MMOPSO、NSGAII具有较好的稳定性与准确性，尤其是在ZDT1、

Figure 5. The approximate Pareto frontier distribution point map under ZDT2

图5. 在ZDT2下求得近似Pareto前沿分布点图

Figure 6. The approximate Pareto frontier distribution point map under ZDT3

图6. 在ZDT3下求得近似Pareto前沿分布点图

Figure 7. The approximate Pareto frontier distribution point map under ZDT6

图7. 在ZDT6下求得近似Pareto前沿分布点图

Table 1. IGD performance statistics of different algorithms on five test functions

表1. 不同算法在5个测试函数上的IGD性能统计

Table 2. IGD performance statistics of different algorithms on 7 test functions

表2. 不同算法在7个测试函数上的IGD性能统计

ZDT2、ZDT3、ZDT6测试函数上。因此说明，PSO算法具有较好的平衡全局和局部搜索能力。

5. 结论

为解决实际生活中的多目标优化问题，本文提出了一种基于膜系统框架的多目标粒子群优化算法。根据膜系统的分层结构，利用粒子群优化的个体最优和全局最优概念，在基本膜上并行更新解，在表层膜中，利用外部档案使用非支配解集和拥挤距离机制提高非支配解的多样性。本文将该算法与其他几种优化算法在KUR、ZDT系列和DTLZ系列测试函数进行测试，实验结果表明：基于膜系统的粒子群算法具备收敛速度快、近似Pareto前沿点分布均匀等特点。因此说明新算法在求解多目标优化问题方面是可行且有效的。