论文部分内容阅读
作为计算机科学的重要新兴研究领域,膜计算已成为一个新的研究热点。膜计算模型通常被称作膜系统或P系统,这种特殊的计算模型是由膜计算的提出者Gheorghe Paun在多年研究自然计算与DNA计算的基础上提出来的。由于该模型很好地借鉴了生物细胞内并行发生生化反应这一机制,所以膜系统是一类具有分布式和极大并行性的计算模型,这也是膜计算具有较高研究价值的重要原因。现阶段,众多膜计算领域的研究者都将主要精力放在建立完善的膜计算理论体系,从计算复杂性和计算效率角度探讨各类膜系统的计算能力。经过十几年的研究发展,膜计算的理论研究成果较为丰富。但是另一方面,膜计算的应用研究成果却相对较少。这是由于不同的实际问题需要设计不同的膜系统来解决,而设计膜系统则是一项很复杂的工作。因此,研究如何完成膜系统的自动设计就显得格外有意义。此外,由于很多复杂的实际问题都可以由相应的数学模型描述,因此,算术运算在解决实际问题时必将起到很重要的作用。所以,本文将研究目标选为算术运算膜系统的自动设计,探讨自动设计各类算术运算膜系统的方法,从而为将来膜计算广泛的应用研究提供有力的支撑。论文的主要工作和研究成果可概括如下:1.针对基本算术运算膜系统,提出了一种在相同膜结构、对象集和冗余规则集的条件下完成五种基本算术运算膜系统的自动设计的方法。设计过程中,根据问题模型的特点,通过对规则集进行0-1编码描述各个膜系统,并结合量子进化算法进行设计。此外,对量子进化算法的部分参数进行了讨论。最后,针对设计结果中可能会出现冗余规则这个问题,提出了将膜系统规则集冗余度作为度量指标,并改进了评价函数,有效地消除了设计结果中的冗余规则。2.提出了一种设计利用基本算术运算膜系统作为基本模块设计混合算术运算膜系统的模块化方法,并分别采用十进制和二进制基本算术运算膜系统作为基本模块,设计了十进制和二进制混合算术运算膜系统。同时,对两种设计方法下的设计结果进行了简单的分析和比较。3.针对任意自然数平方膜系统和幂指数求和膜系统两种特殊算术运算膜系统,根据其各自规则集的不同特点,分别提出了两种不同的设计方法,完成了两种特殊算术运算膜系统的自动设计。同时对设计方法中的部分参数进行了讨论,并对设计结果进行了分析验证,验证了设计结果的正确性。本文工作得到了国家自然科学基金(61170016)、教育部新世纪优秀人才支持计划项目(NCET-11-0715)。