基于细胞膜演化规则的仿生算法

摘要：蚁群算法、遗传算法和粒子群算法等从生物系统中得到启发，借鉴生物规则而形成的智能方法在生产实践中被广发应用，获得良好效果。细胞膜层次上的生物规则已被抽象并应用到形式化计算模型的设计中。该文的工作有别于膜计算中的形式化研究，模拟细胞膜演化规则，建立求解带约束最优化问题的细胞膜仿生算法。利用国际通用标准测试函数，验证了该方法的有效性。

关键词：膜计算；最优化问题；仿生优化算法

中图分类号：TP18文献标识码：A文章编号：1009-3044(2012)13-3146-02

Membrane Computing Based on Optimization Algorithm

CHEN Lu-sheng1, XING Jie-qing2

(1.Department of Scientific Research Equipment, Qiongtai Teachers College ,Haikou 571100, China ; 2.Department of Information Tech? nology, Qiongtai Teachers College , Haikou 571100, China)

Abstract: Intelligent methods, such as ant colony algorithm, genetic algorithm and particle swarm optimization are inspired from biological systems. These methods utilize kinds of biological rules and are applied in various practical fields. The biological rules on cellular membrane have been abstracted and applied in constructing computing models. Different form the research on membrane computing, this work simu? late membrane evolution rules and design an optimization algorithm for optimization problems with constraints. Finally, this method is vali? dated by using international standard testing functions.

Key words: membrane computing; optimization problem; optimization algorithm

仿生算法是指受生物系统的启发，模拟生物系统中的演化规则而设计的计算方法，例如蚁群算法、遗传算法、粒子群算法和人工神经网络等。这些方法被广泛地应用到各种生产实践中，获得了良好的效果。在细胞膜层次上，生物演化规则已经被形式化地抽象出来，并且得到了许多研究。抽象生物细胞结构和功能，形式化细胞膜层次上的化学物质演化规则，利用这些演化规则和细胞抽象结构而设计新的形式化计算模型，已经逐渐形成一个新的研究领域，被称为“膜计算”（Membrane Computing）。膜计算形式化研究细胞与细胞膜结构以及其上的生物演化规则，建立的仿生计算模型称为膜系统，也称为P系统。

生物系统中的演化规则应用到最优化问题求解方法的设计中产生了许多仿生算法。该文试图将细胞膜上的演化规则融入到最优化问题的求解方法的设计中。Gabriel与Daniela最早使用基于P系统的优化算法进行函数优化[2]，受P系统进化规则不确定性应用的启发，他们提出了一种新的进化算子应用策略，即选择、交叉、变异等算子不再是依次使用，而是随机使用的方式。将此策略与差分进化算子相结合，在Sphere等三个典型函数上的测试结果表明，其所提出的算法在求解问题的精度和求解效率上较传统的遗传算法有所改进。文献[4-5]讨论了基于遗传算法的嵌套结构膜算法，并用于求解单目标和多目标函数优化问题，且应用于控制器设计和过程控制优化领域。黄亮[3]基于DNA双链编码方式提出了一种基于信息冗余机制的膜函数优化算法，通过与标准遗传算法、差分进化算法、模糊自适应差分进化算法进行实验对比表明该算法具有较高的可靠性和效率。

本文基于细胞膜上的生物演化规则，借鉴P系统的膜结构，设计适用于求解带约束函数优化问题的仿生算法（Membrane Rule based Optimization Algorithm，MROA）。通过标准测试函数，验证MROA算法的有效性和可行性。

1细胞膜结构及其演化规则

首先需要对细胞膜的结构进行抽象。该文采用膜计算中的层次化结构来描述膜系统。一个细胞被膜划分成多个区域，区域内有不同对象，区域间有层次结构。然后在其上定义演化规则，而形成完整的生物膜系统，多种膜相互嵌套，形成分层嵌套抽象结构，膜包含的部分称为膜区域。每个区域内有其相应的对象和规则集。膜区域之间也可能存在通信规则。

一个完整生物膜系统包含结构、规则和物质，该文将其抽象为如下形式化表示：

其中，O是非空有限对象集；μ是膜结构，m是结构的度；wi是第i层膜中对象的集合，用多重集表示；Ri是第i层膜内的进化规则；i0是膜结构的输出区域，该区域保存最后的计算结果。上述抽象过程借鉴了膜计算中的思想，关于膜计算更加详细的描述和分析可以参见文献[1-5]。

2基于细胞膜演化规则的仿生算法MROA

模拟细胞膜的层次化嵌套结构以及其上的演化规则，建立类似随机集成学习的最优化问题方法。

2.1带约束最优化问题

带约束最优化问题是工程实践中经常遇到的实际问题，可以抽象成如下的数学模型：满足的约束条件，在MROA膜系统中用膜间的通信规则体现。

2.2仿生膜系统

仿生算法MROA中使用的抽象膜系统仍然沿用膜计算中建立的多膜嵌套层次结构，该结构分两层——表层膜和内部膜，如图1所示。表层膜内分布m个内部膜，每个内部膜都是优化问题的完整求解算法，MROA通过模拟细胞膜上的演化规则把这些内部膜整合在一起，共同完成最优化问题的求解。图1 MROA膜结构

MROA的求解过程是各层膜之间通信交互的过程，约束条件也在膜之间的交互中实现。每个膜内的对象集就是最优化问题的可行解集合，采用实数编码。每个内部膜内的求解过程并不考虑得到的结果是否满足约束条件。每个内部膜都独立地求解最优化问题，经过若干次迭代后，得到初步的结果。同时，每个内部膜都能与表层膜通信，将内部膜中满足约束条件的结果输出到表层膜。

2.3 MROA算法步骤

MROA在内部膜中借鉴遗传算法，求解无约束的最优化问题，然后将满足约束的可行解输出，在表层膜中参与通信并演化，再进入内部膜中重新演化，直到终止，其详细过程如下：

1）在每个内部膜中产生一组随机初始解，各内部膜独立演化。

2）内部膜的演化规则是：对初始解交叉、变异，变异过程中采用基于最速下降法的差分进化算子。以目标函数为适应度函数，估计每个解的适应性。演化停止后，输出当前所得的对象到表层膜。

3）在表层膜内依次进行交叉与变异，继续演化。

4）表层膜演化过程停止后，如果终止条件达到（如给定迭代次数），则膜系统演化结束，得到最终优化解；否则，将所得对象复制m份，向每个内部膜输入一份。

5）跳至步骤（2），表层输入的对象为初始解，重新开始内部膜的演化。

2.4仿真实验

本节利用国际通用的标准测试函数来验证MROA算法。这些测试函数由多元目标函数和多维约束条件组成，目标函数的类型包括线性、非线性，约束条件有非线性等式约束、线性不等式约束和非线性不等式约束。选择如下标准测试函数[7]：

G: Minimize:

0≤x1≤1200, 0≤x2≤1200，-0.55≤x3≤0.55, -0.55≤x4≤0.55

相关参数设置如下：对每个内部膜，随机初始解规模是100，内部膜迭代次数50，表层膜迭代次数也是50，内部膜与表层膜通信次数为50。对每个测试函数进行50次独立实验。表1给出了MROA算法使用所设定参数得到的实验结果，包括20次独立运行得到的目标函数值最好结果(Best)、平均结果(Mean)、最差结果(Worst)和目标函数值的标准方差(St.dev.)。从表1可知MROA算法对于测试函数G找到了非常近似的全局最优解。

（下转第3150页）

3结论

受膜计算仿生思想的启发，该文建立细胞膜的层次化嵌入套抽象结构的层次嵌套结构，模拟细胞膜层次的演化规则，设计了用于解决函数最优化问题的算法MROA。通过在国际通用标准测试函数上的测试实验验证了该算法的有效性。在MROA算法中，m个约束条件对应m个内部膜，通过对象输出膜时的校验而实现约束条件，故当约束条件数增加时，输出空集的内膜数随之增加，使得表层膜的进化能力降低。因此，改进约束条件的实现方式将有助于提高MROA仿生算法的性能，是本文的进一步工作。

参考文献：

[1] Pǎun G H. Computing with membranes [J]. Journal of Computer and System Science, 2000, 61 (1): 108-143.

[2] Zaharie D, Ciobanu G. Distributed evolutionary algorithms inspired by membranes in solving continuous optimization problems [C]. Work? shop on Membrane Computing, LNCS,Springer-Verlag, Berlin, 2006, 4361: 536-553.

[3] Zhang Y, Huang L. A variant of P systems for optimization [J]. Neurocomputing, 2009, 72 :1355-1360.

[4] Huang L, Suh I H , Abraham A. Dynamic multi-objective optimization based on membrane computing for control of time-varying unsta? ble plants [J]. Information Sciences, 2011, 181: 2370-2391.

[5] Huang L, Suh I H. Controller design for a marine diesel engine using membrane computing [J]. International Journal of Innovative Comput? ing Information and Control, 2009, 5(4): 899-912.

[6] Mezura-Montes E, Coello C A C. A numerical comparison of some multi-objective-based techniques to handle constraints in genetic algo? rithms [P]. Technical Report, EVOCINV-01-2003, México, 2003: 1-34.