形式化多维结构膜计算模型研究与应用

Membrane computing is a new computing model based on cell structures. It is a new and fast evolving branch of biological computing while it is the most important biological computing model since the founding and development of DNA computing. Up to now there are three categories of membrane computing models, that is, the cell-like P systems, the tissue-like P systems, and the neural-like P systems. The common feature of these P systems is that the formal topological structure, or its information exchange structure, is a one dimensional data structure. This data structure is mainly a tree, or a graph. The purpose of this research is to propose a multi-dimensional formal membrane computing model based on simplex. The topological structure, or data structure, of this model is a simplex, or simplicial complex. In the one-dimensional case, this structure coincides with the traditional model, i.e., the graph model. With the help of this new model it is expected to better describe the spatial structure of cells and complicated multi-modal information exchange therein. In the sense of topological structure we extend the one dimensional data structure of traditional P systems to multi-dimensional structures. In this project we will propose new membrane models with rules. Computation completeness will be proved. We will also propose a hybrid abstract chain membrane model with chain rules. Comparison with traditional P systems will be made. Research on cluster analysis of membrane computing will also be a focus of this research. Specific membrane models for cluster analysis as well as other optimization problems will be designated. Experimental simulation and complex analysis will be performed to show the effects of the new algorithms.

膜计算是近年来提出的基于细胞结构的新型计算模型，是生物计算中新的和快速发展的分支，也是继DNA计算后最重要的生物计算模型。目前为止常见的膜计算模型大致有三类：类细胞P系统、类组织P系统、类神经P系统，这些膜计算模型的共同特点是其形式化拓扑结构（链接结构）为图类结构，其链接关系为一维。本研究的目的是研究提出一种多维结构形式化膜计算模型，其链接结构建立在单纯复合型之上，这种结构的一维情形即为图。多维结构期望可更好的描述生物细胞的立体结构和复杂多向信息交互关系，在形式化意义上也将拓扑结构从一位拓展到了高维。项目将研究单纯复合型P系统的模型构造和规则设计，证明代表其计算能力的计算完备性，并与其它膜系统进行一定对比。我们还将研究一种符合膜计算模型，即基于链式结构的抽象膜模型。项目还将研究膜计算在聚类分析中的应用，描述可用于聚类分析这种优化问题的P系统模型，设计仿真实验并进行时间和空间复杂度分析。

本项目提出了一种基于多维结构的形式化膜计算模型，其数据结构是建立在单纯复合形基础上，从而在形式化意义上将P系统的拓扑结构从一维拓展到了多维。项目提出并构建了基于多维结构的新型P系统，设计了相应的膜结构、膜规则和膜对象，并利用计算机仿真模拟的方式验证了部分P系统的可行性。本项目另一个内容是关于聚类问题的膜计算实现方法研究，对一些聚类问题设计了膜计算模型，改善了聚类效果，进行了算法分析，扩展了膜计算模型的应用领域。本项目的具体研究内容主要包括：.1）.多维结构新型膜计算模型研究。主要包括单纯复形P系统和链式P系统的研究，通过构建基于单形和链式结构的膜结构、膜规则和膜对象来完成新型P系统的构造，给出了两类新型P系统的形式化定义，证明了其计算完备性。.2）.基于扩展规则的新型膜计算模型研究。主要包括基于扩展规则的类组织和类神经P系统，设计了相应的进化和通信规则，构造了具有新计算特性的类神经和类组织P系统。.3）.聚类问题应用研究。主要分为直接膜聚类和耦合膜聚类。直接膜聚类通过设计适当的膜结构和膜规则来完成聚类过程。耦合膜聚类利用P系统的极大并行性，构造具有膜计算特性的框架，通过进化和通信规则实现聚类分析计算过程，改善了传统聚类分析计算时间长的问题。.4）.频繁项集挖掘研究。利用P系统时间换空间的特点，通过构建P系统计算模型实现频繁项集挖掘，系统具有较低的时间复杂度。.5）.医学图像处理应用研究。将一些医学图像处理问题转化为聚类分析，结合聚类方法和P系统的计算特性，改善传统显著性方法易受血液流动影响而造成聚类结果不准确的问题。