论文部分内容阅读
求解NP难度问题是计算机科学技术的一个瓶颈任务。近年来研究表明,对于NP难度问题可能根本不存在既完整严格又不太慢的求解算法。研究者们试图从生物进化过程、物理运动过程以及人类社会中等得到启发,以期得到关于该类问题的非绝对完整的,但是高效的近似的启发式求解算法。于是,一些具有高效优化性能,无需问题特殊信息等优点的现代启发式算法相继出现,如进化算法、模拟退火算法、禁忌搜索算法、蚁群算法等。这些计算方法大大丰富了现代优化技术,也为传统最优化技术难以处理的NP难度问题提供了切实可行的解决方案。本文对其中的贪心算法,局部搜索算法,模拟退火算法,禁忌搜索算法,遗传算法,蒙特卡洛算法等进行了简单的介绍,并重点研究了圆(球)形Packing问题以及模型蛋白结构预测问题的现代启发式求解算法。首先,基于拟人化思想,为势能曲面变平法提出了一种高效的构形更新策略。通过将改进的势能曲面变平法(ELP+)与基于自适应步长的梯度法相结合,得到一种求解圆形Packing问题的混合算法。其次,通过对禁忌搜索算法的邻域解,禁忌对象和当前解的接受原则进行改进,得到改进的禁忌搜索算法,并将改进的禁忌搜索算法和基于自适应步长的梯度算法相结合,提出了一种求解球形Packing问题的基于禁忌搜索的启发式算法。另外,考虑到改进的ELP (ELP+)方法的高效优化性能,本文将ELP+方法应用到HP格点模型中去进行蛋白质结构预测,提出了一种高效的启发式算法。算法首先利用贪心策略产生初始构形,然后利用牵引移动更新构形,一旦计算陷入极小值的陷阱,则采用90°旋转,平移等启发式的跳坑策略跳出局部极小点。总之,受物理运动过程、人类社会以及具体问题的启发,本文为圆(球)形Packing问题和模型蛋白结构预测问题提出了若干有效的启发式求解算法。这些方法对于研究其它NP难度问题的现实求解也具有普遍的实际意义。