第5期 屠传运，等：膜系统下的一种多目标优化算法 679. 初相继被提出：Zitzler等4)于1999年提出加强 定义1（可行解）对于任意一个x∈Rm,且满 Pareto进化算法(strength pareto evolutionary 足式(1)中所给出的约束条件，则称x为可行解。 algorithm,SPEA),3年之后，他们提出了SPEA改进 定义2(Pareto占优)对所有满足定义1的可 版本SPEA2:Erichson等)于2001年提出了NPGA 行解组成的集合称为可行解集合，用X表示，则X二 的改进版本NPGA2:经典且效率极高的NSGA-Ⅱ算 R”:假设有两个可行解x。,x∈X,若x。与x。相比 法于2002年由Deb等6]通过对NSGA进行改进而 较，x。是Pareto占优的，则条件当且仅当满足： 提出。 (Hi=1,2,…,m,f(xa)≤f(x6)N (2) 膜计算(membrane computing)是自然计算的新 3j=1,2,…,m,f(xa)<fx) 分支，旨在从生命细胞的结构与功能以及组织和器 记作x。<x6,也称为x.支配x6。若x。和x。之间 官等细胞群的协作中抽象出计算模型]。膜计算 不存在相互支配关系，则称它们之间非支配。 又被称为膜系统或P系统，膜计算由欧洲科学院院 定义3(Pareto最优解X·)如果存在一个X 士Paun于1998年提出，由于其具有分布式和并行 满足3x∈R",x<x,则X·为Pareto最优解，也叫 计算的能力，目前在将膜计算理论应用于多目标优 作非支配解；Pareto最优解集定义为所有Pareto最 化问题上获得了一些研究成果。Zaharie等[劉于 优解组成的集合，记作P。 2009年通过对比分布式演化算法和膜算法的异同， 定义4(Pareto前沿)最优解集P在目标函数 受膜算法的启发提出了运用于求解连续优化问题 空间上的映射，记作P℉，表示为 的分布式演化算法：Li山等[)提出将遗传算法引入 P℉={F(x)=minf(x),f(x),,f(x)}x∈P 到膜算法，利用遗传算法的交叉与变异机制，该算 (3) 法求解ZDT系列优化问题表现出了较好的求解能 1.2膜计算理论 力：Zhang等o提出了将差分演化与P系统相结合 目前，对膜的研究主要包括细胞型、组织型和 的算法，并将其运用于多目标优化问题上。 神经型3种模型[]。本文所提出的算法是建立在 受到膜计算理论启发，本文提出了一种结合膜 细胞型膜系统上，下面介绍细胞型膜系统理论的主 系统理论的多目标优化算法，即基于P系统的遗传 要内容： 算法(P-genetic algorithm,P-GA)。本文采用的膜系 Π={V,T,,101,02,…,0。,R) (4) 统只具有表层膜和基本膜，将一定数量的种群放入 根据式(4)的多元组，其中：V是字母表，V中的 表层膜中，然后经过非支配排序后分配到基本膜 元素称为字符对象；TCV,T为输出的字母表；u是 中。并在基本膜中运用遗传机制来求解多目标优 化问题的非支配解集，在表层膜中引入NSGA-Ⅱ算 包含m个膜的膜结构，其中m表示的度；w:∈ 法，以此来维持非支配解集的多样性，采用KUR和 V',且i=1,2,…,m,表示膜结构μ中第i个膜所包 DT系列多目标测试函数来进行仿真实验，得出的 含的字符多重集，V~表示由V中的字符对象组成的 非支配解集能够较好地逼近真实的Pareto前沿。本 任意多重集：R是进化规则的有限集合，进化规则是 文参考了文献[11]的设计思路，不同点在于，基本 二元组：R(i=1,2,…,m)对应的是膜结构μ中的区 膜中利用通信规则并将交叉与变异的操作进行了 域i的进化规则集合。 改变。 细胞型膜结构如图1所示，最外层把细胞膜结 构与外界环境隔开的膜称为表层膜：每一个膜都确 1多目标优化问题和膜计算理论 定一个区域，区域中包含了反应规则和多重集：对 1.1多目标优化问题的数学描述 任意一个膜，若该膜区域内不包含其他的膜，即膜 多目标优化问题有很多种表示方式，用数学方 中无膜，则称为基本膜。 表层膜 基本膜 式描述比较直观，便于理解。不失一般性的描述为 (F(x)=min(f(x)f(x),.f (x) s.tg(x)=0,i=1,2,…,9 (1) 区域 h,(x)≥0，j=1,2,…,p 式(1)中有n个决策变量，x={x1,x2,xn}∈ R",R"为n维决策空间；F(x)∈Rm,Rm为m维的目 标空间：目标函数F(x)定义了m个由决策空间向 目标空间映射的关系；g:(x)=0,i=(1,2,…,9)描 基本膜 基本膜 基本膜 述了q个等式约束条件；h,(x)≥0j=(1,2,…,p) 定义了p个不等式约束条件。在以上的描述基础 图1膜系统与其简化结构 上，给出以下几个定义。 Fig.1 Membrane system with its simplified structure初相 继 被 提 出： Ｚｉｔｚｌｅｒ 等［４］ 于 １９９９ 年 提 出 加 强 Ｐａｒｅｔｏ 进 化 算 法 （ ｓｔｒｅｎｇｔｈ ｐａｒｅｔｏ ｅｖｏｌｕｔｉｏｎａｒｙ ａｌｇｏｒｉｔｈｍ，ＳＰＥＡ ），３ 年之后，他们提出了 ＳＰＥＡ 改进 版本 ＳＰＥＡ２；Ｅｒｉｃｈｓｏｎ 等［５］ 于 ２００１ 年提出了 ＮＰＧＡ 的改进版本 ＮＰＧＡ２； 经典且效率极高的 ＮＳＧＡ⁃ＩＩ 算 法于 ２００２ 年由 Ｄｅｂ 等［６］通过对 ＮＳＧＡ 进行改进而 提出。 膜计算（ｍｅｍｂｒａｎｅ ｃｏｍｐｕｔｉｎｇ）是自然计算的新 分支，旨在从生命细胞的结构与功能以及组织和器 官等细胞群的协作中抽象出计算模型［７］ 。 膜计算 又被称为膜系统或 Ｐ 系统，膜计算由欧洲科学院院 士 Ｐａｕｎ 于 １９９８ 年提出，由于其具有分布式和并行 计算的能力，目前在将膜计算理论应用于多目标优 化问题上获得了一些研究成果。 Ｚａｈａｒｉｅ 等［８］ 于 ２００９ 年通过对比分布式演化算法和膜算法的异同， 受膜算法的启发提出了运用于求解连续优化问题 的分布式演化算法；Ｌｉｕ 等［９］ 提出将遗传算法引入 到膜算法，利用遗传算法的交叉与变异机制，该算 法求解 ＺＤＴ 系列优化问题表现出了较好的求解能 力；Ｚｈａｎｇ 等［１０］提出了将差分演化与 Ｐ 系统相结合 的算法，并将其运用于多目标优化问题上。 受到膜计算理论启发，本文提出了一种结合膜 系统理论的多目标优化算法，即基于 Ｐ 系统的遗传 算法（Ｐ⁃ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ，Ｐ⁃ＧＡ）。 本文采用的膜系 统只具有表层膜和基本膜，将一定数量的种群放入 表层膜中，然后经过非支配排序后分配到基本膜 中。 并在基本膜中运用遗传机制来求解多目标优 化问题的非支配解集，在表层膜中引入 ＮＳＧＡ⁃Ⅱ算 法，以此来维持非支配解集的多样性，采用 ＫＵＲ 和 ＺＤＴ 系列多目标测试函数来进行仿真实验，得出的 非支配解集能够较好地逼近真实的 Ｐａｒｅｔｏ 前沿。 本 文参考了文献［１１］的设计思路，不同点在于，基本 膜中利用通信规则并将交叉与变异的操作进行了 改变。 １ 多目标优化问题和膜计算理论 １．１ 多目标优化问题的数学描述 多目标优化问题有很多种表示方式，用数学方 式描述比较直观，便于理解。 不失一般性的描述为 Ｆ（ｘ） ＝ ｍｉｎ ｆ １（ｘ），ｆ ２（ｘ），…，ｆ { ｍ（ｘ）} ｓ．ｔ ｇｉ（ｘ） ＝ ０， ｉ ＝ １，２，…，ｑ ｈｊ（ｘ） ≥ ０， ｊ ＝ １，２，…，ｐ ì î í ï ï ïï （１） 式（１）中有 ｎ 个决策变量， ｘ ＝ ｘ１ ，ｘ２ ，…ｘｎ { } ∈ Ｒ ｎ ，Ｒ ｎ 为 ｎ 维决策空间；Ｆ（ｘ） ∈ Ｒ ｍ ，Ｒ ｍ 为 ｍ 维的目 标空间；目标函数 Ｆ（ｘ） 定义了 ｍ 个由决策空间向 目标空间映射的关系；ｇｉ（ｘ） ＝ ０，ｉ ＝ （１，２，…，ｑ） 描 述了 ｑ 个等式约束条件；ｈｊ（ｘ） ≥ ０，ｊ ＝ （１，２，…，ｐ） 定义了 ｐ 个不等式约束条件。 在以上的描述基础 上，给出以下几个定义。 定义 １ （可行解）对于任意一个 ｘ∈Ｒ ｍ ，且满 足式（１）中所给出的约束条件，则称 ｘ 为可行解。 定义 ２ （Ｐａｒｅｔｏ 占优）对所有满足定义 １ 的可 行解组成的集合称为可行解集合，用 Ｘ 表示，则 Ｘ⊆ Ｒ ｎ ；假设有两个可行解 ｘａ ，ｘｂ ∈Ｘ，若 ｘａ 与 ｘｂ 相比 较，ｘａ 是 Ｐａｒｅｔｏ 占优的，则条件当且仅当满足： ∀ｉ ＝ １，２，…，ｍ， ｆ ｉ（ｘａ ） ≤ ｆ ｉ（ｘｂ） ∧ ∃ｊ ＝ １，２，…，ｍ， ｆ ｊ（ｘａ ） ＜ ｆ ｊ（ｘｂ） { （２） 记作 ｘａ＜ｘｂ，也称为 ｘａ 支配 ｘｂ。 若 ｘａ 和 ｘｂ 之间 不存在相互支配关系，则称它们之间非支配。 定义 ３ （Ｐａｒｅｔｏ 最优解 Ｘ ∗ ）如果存在一个 Ｘ ∗ 满足¬∃ｘ∈Ｒ ｎ ，ｘ＜ｘ ∗ ，则 Ｘ ∗ 为 Ｐａｒｅｔｏ 最优解，也叫 作非支配解；Ｐａｒｅｔｏ 最优解集定义为所有 Ｐａｒｅｔｏ 最 优解组成的集合，记作 Ｐ。 定义 ４ （Ｐａｒｅｔｏ 前沿）最优解集 Ｐ 在目标函数 空间上的映射，记作 ＰＦ，表示为 ＰＦ ＝ ｛Ｆ（ｘ ∗ ）＝ ｍｉｎ｛ｆ １（ｘ ∗ ）， ｆ ２（ｘ ∗ ），…， ｆｍ（ｘ ∗ ）｝ ｘ ∗∈Ｐ｝ （３） １．２ 膜计算理论 目前，对膜的研究主要包括细胞型、组织型和 神经型 ３ 种模型［１２］ 。 本文所提出的算法是建立在 细胞型膜系统上，下面介绍细胞型膜系统理论的主 要内容： ∏ ＝ {Ｖ，Ｔ，μ，ｗ１ ，ｗ２ ，…，ｗｍ ，Ｒ} （４） 根据式（４）的多元组，其中： Ｖ 是字母表，Ｖ 中的 元素称为字符对象； Ｔ⊆Ｖ，Ｔ 为输出的字母表； μ 是 包含 ｍ 个膜的膜结构，其中 ｍ 表示 ∏ 的度； ｗｉ ∈ Ｖ ∗ ，且 ｉ ＝ １，２，…，ｍ，表示膜结构 μ 中第 ｉ 个膜所包 含的字符多重集，Ｖ ∗ 表示由 Ｖ 中的字符对象组成的 任意多重集；Ｒ 是进化规则的有限集合，进化规则是 二元组；Ｒｉ（ｉ ＝ １，２，…，ｍ） 对应的是膜结构μ 中的区 域 ｉ 的进化规则集合。 细胞型膜结构如图 １ 所示，最外层把细胞膜结 构与外界环境隔开的膜称为表层膜；每一个膜都确 定一个区域，区域中包含了反应规则和多重集；对 任意一个膜，若该膜区域内不包含其他的膜，即膜 中无膜，则称为基本膜。 图 １ 膜系统与其简化结构 Ｆｉｇ．１ Ｍｅｍｂｒａｎｅ ｓｙｓｔｅｍ ｗｉｔｈ ｉｔｓ ｓｉｍｐｌｉｆｉｅｄ ｓｔｒｕｃｔｕｒｅ 第 ５ 期 屠传运，等：膜系统下的一种多目标优化算法 ·６７９·