·680 智能系统学报 第12卷 2P-GA算法 为了使每个基本膜的内部区域都有对应的多 重集，利用NSGA-Ⅱ的非支配排序机制对表层膜区 P系统由字符对象多重集、反应规则和膜结构 域中的所有字符对象进行排序，排序标准参照2)完 三部分组成[)。在P系统中，字符对象与多重集分 成适应值大小，排序结束以后再将其按照等数量划 别对应所求多目标优化问题的解和解集，且每一个 分为多个子字符多重集。具体划分的形式化表述 字符对象都会通过适应度函数得到一个适应度值： 如式(7)所示： 反应规则既是算法具体的执行，也有对细胞膜的操 20=sort(0) 作，比如分裂、溶解等：膜结构的运用使算法具有了 ={01,102,…,0m} (7) 分布式和并行计算的能力[1]。在每一次的迭代，将 n sizeof(w)/m 随机产生的字符对象放入表层膜区域中，利用表层 式中：w表示字符多重集；sort(w)表示对表层膜区 膜区域中的反应规则和通信规则进行操作：最后通 域中的多重集进行非支配排序：心：表示第i个子字 过膜的溶解将多重集释放到表层膜区域中交流信 符多重集：sizeof(w)表示多重集中字符对象个数；m 息。为了降低仿真实验难度，所提算法采用的细胞 表示基本膜的个数：n表示每个基本膜取得字符对 型膜结构只有表层膜与基本膜，这种二层结构相较 象个数，具体放入规则对n进行取模。 于原结构复杂度较低。 4)对前m个基本膜用GA算法中的交叉规则进 为了使算法得出的多重集有较好的多样性，故 行多线程并行计算，以获得新的字符对象，而并行 引入NSGA-Ⅱ算法，利用其非支配排序和拥挤距离 计算可以极大地加快求解速度，具体交叉操作为 两种机制来获得。 遗传算法(genetic algorithm,GA)是模拟达尔文 S+=a·S+(1-a)·S (8) 进化论（适者生存、优胜劣汰遗传机制），借鉴生物 S,=a·S+(1-a)·S 界的进化规律演化而来的随机化搜索方法。该方 式中：S表示字符对象S第t代的值：S?表示字符 法具有并行性和更好的全局寻优能力[5-16)。 对象S2第t代的值；S+,表示字符对像S第t+1代 P-GA算法基于膜计算理论，包含了遗传机制， 的值；S?,表示字符对象S2第t+1代的值；a表示 利用NSGA-Ⅱ算法的非支配排序和拥挤距离两种机 交叉系数，经过多次实验测试，当选取a=0.5~0.7 制来设计算法，详细步骤如下。 时能获得最好的结果，故本文提出P-GA算法采用 1)根据优化问题的约束条件，在表层膜的区域 这一数值。 内随机生成N个字符对象(N≥i≥1)，所有字符对 5)利用通信规则将前m个基本膜中产生的交 象均为十进制编码，具体形式为 叉结果复制一份发送到第+1个基本膜中，对第 sd=(s-miad）×rand()+smrJ(5) m+1个基本膜中的多重集进行变异操作。由于自 式中：：，表示第i个字符对象的第j维：广的范围为 然进化中种群变异率往往比较低，因此在一次迭代 D≥j≥1，D表示维数；Sm表示第j维的最小值， 中，只有利用足够多的字符对象进行变异操作才能 sa表示第j维的最大值；rand()为随机数函数，产 产生更多的新个体，具体变异操作如式(9)所示： 生从0~1的随机数。 Su+i)=S)+0.1×(S(a)-S(mim）×rand() 2)根据所要优化问题的目标函数计算出每个 (9) 字符对象的适应度值，从而完成对所有字符对象的 式中：SD表示字符对象S的第t代j维的值； 评价。 S(m)表示第j维的最小值；Sm表示第j维的最 3)在初始化完成以后，利用表层膜的分裂规 大值；rand()为随机数函数，产生从0~1的随 则，在表层膜内部区域分裂出m+1个基本膜，且分 机数。 裂出的基本膜具有求解多目标优化问题的能力。 6)当每个基本膜中的规则和操作都结束以 首先，将初始化完成的m个多重集复制一份发送到 后，调用基本膜区域内的溶解规则，当m+1个基本 第m+1个基本膜的区域中：然后，将m个多重集发 膜全部溶解后，表层膜区域中就会有来自于不同 送到前m个基本膜的区域中，逐一对应。具体表层 基本膜中的字符对象；本文引入外部档案集，将从 膜分裂规则如式(6)： 基本膜中溶解出的字符对象插入到外部档案集 []。→[[]1，[]2，…，[]m,[]m](6) 中，而后将表层膜区域中的字符对象与归入外部 式中：[]。表示表层膜，[]：表示第i个基本膜。 档案的字符对象进行非支配排序操作。外部档案２ Ｐ⁃ＧＡ 算法 Ｐ 系统由字符对象多重集、反应规则和膜结构 三部分组成［１３］ 。 在 Ｐ 系统中，字符对象与多重集分 别对应所求多目标优化问题的解和解集，且每一个 字符对象都会通过适应度函数得到一个适应度值； 反应规则既是算法具体的执行，也有对细胞膜的操 作，比如分裂、溶解等；膜结构的运用使算法具有了 分布式和并行计算的能力［１４］ 。 在每一次的迭代，将 随机产生的字符对象放入表层膜区域中，利用表层 膜区域中的反应规则和通信规则进行操作；最后通 过膜的溶解将多重集释放到表层膜区域中交流信 息。 为了降低仿真实验难度，所提算法采用的细胞 型膜结构只有表层膜与基本膜，这种二层结构相较 于原结构复杂度较低。 为了使算法得出的多重集有较好的多样性，故 引入 ＮＳＧＡ⁃Ⅱ算法，利用其非支配排序和拥挤距离 两种机制来获得。 遗传算法（ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ，ＧＡ）是模拟达尔文 进化论（适者生存、优胜劣汰遗传机制），借鉴生物 界的进化规律演化而来的随机化搜索方法。 该方 法具有并行性和更好的全局寻优能力［１５－１６］ 。 Ｐ⁃ＧＡ 算法基于膜计算理论，包含了遗传机制， 利用 ＮＳＧＡ⁃Ⅱ算法的非支配排序和拥挤距离两种机 制来设计算法，详细步骤如下。 １）根据优化问题的约束条件，在表层膜的区域 内随机生成 Ｎ 个字符对象（Ｎ≥ｉ≥１），所有字符对 象均为十进制编码，具体形式为 ｓｉ，ｊ ＝ （ｓｍａｘ，ｊ － ｓｍｉｎ，ｊ） × ｒａｎｄ（） ＋ ｓｍａｘ，ｊ （５） 式中：ｓｉ，ｊ表示第 ｉ 个字符对象的第 ｊ 维； ｊ 的范围为 Ｄ≥ｊ≥１，Ｄ 表示维数； ｓｍｉｎ，ｊ 表示第 ｊ 维的最小值， ｓｍａｘ，ｊ 表示第 ｊ 维的最大值； ｒａｎｄ（） 为随机数函数，产 生从 ０～１ 的随机数。 ２）根据所要优化问题的目标函数计算出每个 字符对象的适应度值，从而完成对所有字符对象的 评价。 ３）在初始化完成以后，利用表层膜的分裂规 则，在表层膜内部区域分裂出 ｍ＋１ 个基本膜，且分 裂出的基本膜具有求解多目标优化问题的能力。 首先，将初始化完成的 ｍ 个多重集复制一份发送到 第 ｍ＋１ 个基本膜的区域中；然后，将 ｍ 个多重集发 送到前 ｍ 个基本膜的区域中，逐一对应。 具体表层 膜分裂规则如式（６）： [ ] ０ → [ ] １， [ ] ２，…， [ ] ｍ， [ ] [ ｍ＋１ ] （６） 式中： [ ] ０ 表示表层膜， [ ] ｉ 表示第 ｉ 个基本膜。 为了使每个基本膜的内部区域都有对应的多 重集，利用 ＮＳＧＡ⁃Ⅱ的非支配排序机制对表层膜区 域中的所有字符对象进行排序，排序标准参照 ２）完 成适应值大小，排序结束以后再将其按照等数量划 分为多个子字符多重集。 具体划分的形式化表述 如式（７）所示： ｗ · ＝ ｓｏｒｔ（ｗ） ｗ · ＝ ｗ１ ，ｗ２ ，…，ｗｍ { } ｎ ＝ ｓｉｚｅｏｆ（ｗ） ／ ｍ ì î í ï ï ï ï （７） 式中： ｗ 表示字符多重集； ｓｏｒｔ（ｗ） 表示对表层膜区 域中的多重集进行非支配排序； ｗｉ 表示第 ｉ 个子字 符多重集；ｓｉｚｅｏｆ（ｗ）表示多重集中字符对象个数； ｍ 表示基本膜的个数； ｎ 表示每个基本膜取得字符对 象个数，具体放入规则对 ｎ 进行取模。 ４）对前 ｍ 个基本膜用 ＧＡ 算法中的交叉规则进 行多线程并行计算，以获得新的字符对象，而并行 计算可以极大地加快求解速度，具体交叉操作为 Ｓ １ ｔ＋１ ＝ α·Ｓ １ ｔ ＋ （１ － α）·Ｓ ２ ｔ Ｓ ２ ｔ＋１ ＝ α·Ｓ ２ ｔ ＋ （１ － α）·Ｓ １ ｔ { （８） 式中： Ｓ １ ｔ 表示字符对象 Ｓ １ 第 ｔ 代的值； Ｓ ２ ｔ 表示字符 对象 Ｓ ２ 第 ｔ 代的值； Ｓ １ ｔ＋１ 表示字符对像 Ｓ １ 第 ｔ ＋ １ 代 的值； Ｓ ２ ｔ＋１ 表示字符对象 Ｓ ２ 第 ｔ ＋ １ 代的值； α 表示 交叉系数，经过多次实验测试，当选取 α ＝ ０．５ ～ ０．７ 时能获得最好的结果，故本文提出 Ｐ⁃ＧＡ 算法采用 这一数值。 ５）利用通信规则将前 ｍ 个基本膜中产生的交 叉结果复制一份发送到第 ｍ＋１ 个基本膜中，对第 ｍ＋１ 个基本膜中的多重集进行变异操作。 由于自 然进化中种群变异率往往比较低，因此在一次迭代 中，只有利用足够多的字符对象进行变异操作才能 产生更多的新个体，具体变异操作如式（９）所示： Ｓ（ｔ＋１，ｊ） ＝ Ｓ（ｔ，ｊ） ＋ ０．１ × （Ｓ（ｍａｘ，ｊ） － Ｓ（ｍｉｎ，ｊ） ） × ｒａｎｄ（ ） （９） 式中： Ｓ（ｔ，ｊ） 表示字符对象 Ｓ 的第 ｔ 代 ｊ 维的值； Ｓ（ｍｉｎ，ｊ） 表示第 ｊ 维的最小值； Ｓ（ｍａｘ，ｊ） 表示第 ｊ 维的最 大值； ｒａｎｄ（ ） 为随机数函数，产生从 ０ ～ １ 的随 机数。 ６）当每个基本膜中的规则和操作都结束以 后，调用基本膜区域内的溶解规则，当 ｍ＋１ 个基本 膜全部溶解后，表层膜区域中就会有来自于不同 基本膜中的字符对象；本文引入外部档案集，将从 基本膜中溶解出的字符对象插入到外部档案集 中，而后将表层膜区域中的字符对象与归入外部 档案的字符对象进行非支配排序操作。 外部档案 ·６８０· 智 能 系 统 学 报 第 １２ 卷