最大集团问题的DNA计算机进化算法

被引:20
作者
李源
方辰
欧阳颀
机构
[1] 北京大学理论生物中心
[2] 北京大学理论生物中心 北京大学物理系
[3] 北京
[4] 北京大学物理系
关键词
DNA计算机; 进化算法; NP完全问题;
D O I
暂无
中图分类号
TP301.6 [算法理论];
学科分类号
081202 ;
摘要
进化算法是克服DNA计算中穷举法极限的可能途径之一,借用生物进化的概念,设计了可用于DNA计算的进化算法来求解最大集团问题,算法中所有的操作都可以在今天的分子生物技术水平上实现。计算机模拟实验表明使用这种进化算法有可能由一个小的样本空间得到问题的解,而不必穷举所有可能情况。对于随机生成的问题,这种进化算法能以高概率在很少的进化循环数内正确地给出问题的解。结果显示这种进化算法所需的时间随问题的规模呈多项式增长,这可能使DNA计算机在求解复杂问题时比传统电子计算机拥有更多的优势。
引用
收藏
页码:439 / 443
页数:5
相关论文
共 1 条
[1]   Parallel overlap assembly for the construction of computational DNA libraries [J].
Kaplan, PD ;
Qi, OY ;
Thaler, DS ;
Libchaber, A .
JOURNAL OF THEORETICAL BIOLOGY, 1997, 188 (03) :333-341