基于多级抽取的0-1整数规划问题的DNA算法.pdfVIP

总第224期 计算机与数字工程 V01．36 No．6 2008年第6期 ComputerDigital Engineering 47 基于多级抽取的O一1整数规划问题的DNA算法 李 红 马季兰 (太原理工大学计算机与软件学院计算机科学与技术系 太原 030024) 摘 要 DNA计算是一种借助于分子生物技术进行计算的新方法，在解决一类困难问题特别是NP一完全问题上具有 硅计算机无法比拟的优势，利用DNA计算求解0—1整数规划问题的研究具有重大的意义。基于多级分离模型解决0—1 整数规划问题，且给出DNA算法。通过一个实例给出了操作的步骤。 关键词 DNA计算 0—1整数规划问题 多级抽取 最优解 中图分类号 TP301．6 DNA Computation for a Category of Specicial Integer Planning Problem (College of Computer and Software，Taiyuan University of Technology，Taiyuan 030024) Abstract DNA computing is a new computation method by means of molecular biology technology．It is of much better performance in solving a class of intractable computational problems such as NP—complete problems，SO it is important to study 0—1 integer programming problem based on DNA computation．In the paper based on a multi—extraction equipment model， 0—1 integer programming problem is solved and a DNA algorithm is shown．The operating steps are given through an instance． Key words DNA computation，0—1 integer planning problem，multi—extraction，optimal solution Class Number TP301．6 最优解的求解算法。以上是利用表面技术来求解 1 引言 0—1规划问题，受到荧光素种类的限制。本文采 由于电子计算机的存贮量小，运算速度慢，智 用在溶液中反应的方式来求解0—1规划问题，操 能化低，特别是制造工艺趋于极限等特点，因而采 作中采用了多级抽取装置 ，提高了反应的速度。 用DNA计算的可能性引起了人们的广泛关注，尤 2 粘贴模型基本操作及多级抽取模型 其是它的良好的并行性。基于生化反应原理的 DNA计算由于在解决一类困难问题，特别是NP一 粘贴模型在位串上定义了四种基本操作：合 完全问题上具有硅计算机无法比拟的优势，因此对 并、分离、设置和清除。 DNA计算的研究具有重要的意义。 · 合并(Merge)：定义存储合成物的集合 1 0—1规划问题是运筹学中的一个重要问题， 与72的合并为 ，其中，T=T1 u72。 其应用非常广泛。关于它的算法很多，如穷举法， · 分离(Separation)：根据存储合成物中第 隐枚举法等，文献[1]给出了一种基于荧光标记的 个位元 的状态将存储合成物的集合 分解为两 策略，将DNA计算应用于0—1规划，即