生物计算启发的整数分解P系统研究及应用

作     者：薛志健 

作者单位：重庆理工大学 

学位级别：硕士

导师姓名：南海

授予年度：2024年

学科分类：0831[工学-生物医学工程（可授工学、理学、医学学位）] 0711[理学-系统科学] 07[理学] 08[工学] 

主      题：膜计算 P系统 整数分解 时间序列 回声状态网络 

摘      要：膜计算是受生物细胞膜启发的自然计算分支,旨在从自然界生物的细胞(尤其是细胞膜)和器官组织的研究中寻找新的理论计算模型,最终以建立仿生算法和生物计算机为最终目的,其理论研究中采用的数学抽象模型被称为P系统。P系统是具有非确定性和极大并行性的分布式计算系统,其设计和验证是膜计算研究的主要课题之一。罗马尼亚科学院院士、DNA计算专家Gheorghe P?un于1998年首次提出完整的膜计算理论构想,刊表后受到了广泛关注,迅速发展为了一个新兴研究领域。 整数分解问题是一个著名的NP难问题,传统计算机难以在多项式时间内完成求解。利用质数因式易于计算但难于分解的特点,诸如RSA非对称加密在内的密码学算法得到了广泛应用。本文讨论了膜计算在优化质因子计算方面的应用,用于在理论多项式时间内并行解决整数分解问题,并通过实验验证其有效性。且在仿生实验的基础上,我们讨论了算术P系统作为时序发生设备的可能性。本文主要完成的内容有: (1)基于生物细胞膜能够进行分裂和增殖的特点,设计一种能够并行计算目标整数质因子的P系统算法,其主要目标在将目标数N的分解问题,转换为对应函数周期化的寻阶问题。算法尝试将不同阶段的计算任务分治化,并通过P系统的并行性特征,将整数分解问题的求解时间约束在多项式时间内。 (2)通过采用模块化的设计模式,构建多个具有独立计算能力的算术P系统,这一系列P系统可以用于各种公式的求解和P系统执行过程的控制。算术P系统作为整体系统架构的各个模块为实现并行分解算法的流程提供算力。基于通用P系统模拟器UPSimulator开发实验代码套件,对所设计的整数分解P系统在整体上进行了仿真工程的验证,并证明了基于P系统的计算模型在多项式时间内求解整数分解问题的有效性。 (3)在生物时序化方法的启发下,本文引入了一种新的时序数据构造方法,将算术P系统执行时的内部状态时序化,并制作了对应的多种数据集。在数据集之上,采用回声状态网络构建了时序预测模型,以验证时序化P系统在构造生物模型的替代网络方面的有效性。 基于以上研究成果,本文为整数分解问题提出了一种新的解决思路,并丰富了相关领域的研究,拓展了膜计算在数学和密码学领域的应用,并且提出的时序化P系统方法为今后在构造生物替代网络的问题上提供了参考。