0-1规划问题的DNA计算算法研究

1994年,Adleman在Science杂志上发表文章,利用DNA分子求解了有向Hamilton路径问题,开辟了一个新的研究领域——DNA计算。DNA计算从生物技术角度为解决NP-完全问题提供了一种全新的途径。0-1规划问题作为运筹学的重要问题之一,求解0-1规划问题是DNA计算研究的一个热点。 本文主要研究了系数取整数的0-1规划问题的DNA计算算法。研究的内容及主要成果包括: ①探讨了DNA计算的产生背景、研究现状、DNA计算的基本知识,分析了目前DNA求解0-1规划问题存在的问题。 ②研究和设计了系数取整数的0-1规划问题的DNA计算算法,提出了基于表面的0-1规划问题的DNA计算算法Ⅰ、算法Ⅱ、算法Ⅲ,算法Ⅱ、算法Ⅲ直接运用DNA计算求解了系数取整数的0-1规划问题。 ③给出了算法Ⅰ、算法Ⅱ、算法Ⅲ的实例验证,对比分析了算法Ⅰ、算法Ⅱ、算法Ⅲ。 ④研究了DNA计算算法的计算机模拟,设计与实现了算法Ⅲ的计算机模拟,验证了算法Ⅲ的有效性和可行性。 本文的研究提供了系数取整数的0-1规划问题的3种DNA计算算法,丰富和扩展了DNA计算求解0-1规划问题的方法。运用DNA计算求解系数取整数的0-1规划问题,对于解决现实中的许多经典问题具有重要的意义。