论文部分内容阅读
求解NP难度问题一直是计算机科学技术的一个瓶颈任务。近年来的研究表明,对于NP难度问题可能根本不存在既完整严格又不太慢的求解算法。因此,这类问题的求解方法多为启发式方法。蛋白质结构预测问题和矩形packing问题都是NP难度问题。设计求解它们的快速而有效的算法具有深刻的理论意义和普遍的实用价值。受自然界和人类社会中智慧的启发,提出了求解这两类NP难度问题的有效的启发式算法,所做的主要工作有:
⑴对于一个具有两种氨基酸(疏水氨基酸和亲水氨基酸)的三维非格点的蛋白质AB模型,受物理世界物体间相互作用的规律的启发,提出了该模型的蛋白质结构预测问题的拟物算法。结合本问题的一些启发式知识,获得了高效的启发式策略,包括初始构形的产生和跳坑策略,使得搜索过程尽量避免过早陷入局部极小点,即使到了局部极小点,能够使搜索过程跳出,将其引向前景更好的区域。结合这些启发式策略以及拟物算法得到了启发式拟物算法。该算法对文献中的氨基酸序列进行了实算,所得构形的最低能量比PERM+算法(即非格点的PERM(Pruned-Enriched Rosenbluth method)结合共轭梯度法)所得构形的最低能量更低。
⑵提出了AB模型的蛋白质结构预测问题的启发式共轭梯度(HCG)算法。算法在三维欧氏空间中利用启发式的方法产生初始构形,然后用共轭梯度法优化低能状态,一旦计算陷入极小值的陷阱,则采用启发式的跳坑策略跳出局部极小点。将HCG算法应用到蛋白质AB模型中去预测和发现蛋白质结构。计算结果表明,对于链长为55的序列,HCG算法所得结果比当今国际文献中最先进的几个算法所得结果更好。受PERM+算法的启发,给出了AB模型的基于面心立方体(FCC)格点的PERM++算法。该算法利用基于FCC格点的PERM算法产生初始构形,然后用共轭梯度法进一步优化低能状态。数值实验表明,PERM++算法的计算结果优于PERM+算法。
⑶提出了基于拟物策略的局部搜索方法,将此方法同ELP方法相结合得到了改进的ELP算法(ELP+)。计算结果表明,对于部分氨基酸序列,ELP+算法找到了比PERM+算法、多正则(MUCA)Monte Carlo方法、势能曲面变平(ELP)方法、构形空间退火(CSA)算法等国际上最先进的一些算法给出的最低能量状态具有更低能量的构形。使用拟人的策略,提出了基于欧氏距离的占角最大穴度优先的放置方法,为矩形packing问题的快速求解提供了一种高性能的启发式算法。算法的高效性通过应用于标准电路MCNC和GSRC得到了验证,其计算结果优于当今国际上已公开发表了的最先进的几个算法的结果。基于拟人的思想,提出了带有预放置模块的布局问题的穴度算法及其改进的穴度算法。用标准电路MCNC对算法性能进行了测试,实算结果表明,改进的穴度算法比基于角模块表(CBL)和B*树型结构(B*-tree)表示的随机优化算法的计算结果都要好。
⑷对两类NP难度问题——蛋白质结构预测问题和矩形packing问题进行了分析和研究。受自然界、人类社会和具体问题的启发,为它们提出了一系列的有效求解算法。实践证明,这种模仿自然界物质运动和人类行为的方法是一个寻求高效算法的有效途径。这些方法对于研究其它NP难度问题的现实求解具有普遍的实际意义。然而求解蛋白质结构预测问题和矩形packing问题是复杂的开放性课题,其中还有很多问题有待于进一步研究和讨论。