扩展膜计算系统及其在聚类分析中的研究与应用

Membrane computing, as a new method of natural computing, has the characteristics of non-determinism and maximal parallelism. Its computational ability is equivalent to the Turing machine. Membrane computing is an important way to develop non-silicon based computing. Two important problems in the field of membrane computing are the construction of membrane computing models based on biological mechanism and the expansion of membrane computing application scopes. In this project, the extended membrane computing systems based on the mechanism of biological cell with applications to cluster analysis are investigated. The research content is as follows. Four extended membrane computing systems are designed based on the structure and function of biological cells, and their computational power and efficiency are analyzed. Four membrane clustering algorithms are then constructed. The rules of the algorithm are designed. The algorithm process and complexity are analyzed. The algorithm validity is verified through contrast experiments. The membrane clustering algorithm to solve the text clustering practical problem is constructed finally. The research results will extend the variety of the membrane computing systems and the application scopes of membrane computing, and provide new ideas for the improvement of cluster analysis.

膜计算作为一种自然计算新方法，具有非确定性、极大并行特征，计算能力与图灵机等价，是发展非硅基计算的重要途径。基于生物学机理构建膜计算系统及拓展膜计算应用范围是膜计算领域的两个重要科学问题。本项目拟通过研究细胞运行机制，构建扩展膜计算系统、提出基于膜计算的聚类算法，具体研究内容如下：研究生物细胞的结构及功能，从中抽象出四种膜计算系统，并分析其计算能力和计算效率；构建四种基于膜计算的聚类算法，设计算法规则、分析算法流程及算法复杂度，通过对比实验验证算法有效性；构建求解文本聚类问题的基于膜计算的聚类算法。本项目能够扩展膜计算系统类型及应用范围、为优化聚类算法提供新的思路。

本项目构建了基于生物细胞机制的膜计算系统以及基于膜计算的聚类算法，具体研究内容如下：从生物细胞的结构和功能出发，抽象出七种膜计算系统，并分析其计算能力和计算效率；构建七种基于膜计算的聚类算法，设计算法规则、分析算法流程及算法复杂度，通过实验验证算法有效性，对比分析算法优缺点；构建求解文本聚类问题的以及图像分割问题的基于膜计算的聚类算法。本项目基本按照项目计划书执行，在以下几方面取得了阶段性的研究成果：. （1）构建了带有多促进剂/抑制剂的时间无关类细胞膜系统以及带有协同规则的类组织膜系统，通过模拟矩阵文法，证明其计算通用性。构建了带有请求规则和规则产生/移除的类细胞膜系统，通过模拟注册机证明其作为数字产生和函数生成设备的通用性。构建了基于超图的交流类细胞膜系统，通过模拟注册机证明其作为数字产生设备的通用性。构建了内稳态类组织膜系统，讨论了其在标准时间以及时间无关条件下的计算效率，在标准时间条件下，该系统可以求解3着色问题，在时间无关条件下，该系统可以求解SAT问题。构建了突触上有时滞和权重的非线性脉冲神经膜系统，通过模拟注册机证明了其作为数字产生和接受设备的通用性，构造了由47个神经元组成的小型通用函数计算设备以及由43个神经元组成的小型通用数字生成设备，并求解了子集和问题，证明了该系统的计算效率。构建了具有不应期和传播延迟的自适应脉冲神经膜系统，通过模拟注册机证明了其作为数字产生和接受设备的通用性，并求解了SAT问题，证明了该系统的计算效率。. （2）发展了基于膜计算的聚类算法。构建了基于膜计算的集成聚类算法、K中心点算法、FP-growth算法、DBSCAN算法以及粒子群聚类算法、模糊C均值算法、密度峰值算法，设计算法规则、分析算法流程及复杂度，并将其应用于鸢尾花、蘑菇、乳腺癌、大肠杆菌、皮肤病、红酒等数据集的聚类分析，以验证算法有效性，比较和分析其优缺点。. （3）构建了基于膜系统的文本聚类算法以及图像分割算法，将膜计算应用于实际问题。. 以上成果能够提升膜计算系统的智能化水平、扩展膜计算的应用领域、为优化聚类算法、提升算法效率和精度提供新的思路。对提高我国计算技术水平、推动非硅基高性能计算的理论发展及推广应用、促进聚类分析相关行业发展具有一定的理论和实际意义。