基于DNA 编码的多重约束目标的智能组合优化①

修建新， 范晓敏， 张 磊

(黑龙江东方学院计算机科学与电气工程学部，黑龙江哈尔滨150086)

0 引言

1994年，DNA计算理论由L．Adleman首次提出[1]．DNA编码在DNA计算过程中起到十分重要的作用，数据信息通过DNA编码以后，就具有了DNA染色体的许多的特性，可以解决现实中的很多问题．在有限的离散的数学空间中，在满足多个约束条件下，如何去求得目标函数的最优解问题就是多约束目标的组合优化问题．DNA编码和DNA计算表现出来的新特性，正好符合多重约束目标的组合优化问题的要求．所以，本文将DNA编码引入到多重约束目标的组合优化问题中，完成了基于DNA编码的多重约束目标的组合优化的全过程，并提出了相关组合优化算法，经过实验证明其求解的结果优于其他算法．

1 DNA编码

DNA编码是DNA计算中的一个非常重要的组成部分，DNA编码利用了DNA染色体特殊的双螺旋结构和碱基互补配对的特性来进行编码[2]．关于DNA编码的问题可以表述为:DNA分子的四个碱基对可以定义为字母表P(A，C，G，T)，对于一个长度为N的DNA编码的集合S，对于任意一个子集C，C⊆S，使得对于任意的Xi，Yj⊆C，F(Xi，Yj)≥k，k为任意的整数，F函数是DNA序列的评价函数，也就是编码应满足的约束条件．如果有多个约束条件，可以预先设定多个约束函数．

2 多重约束目标组合优化

某一对象要同时满足多个约束条件都会得到一个目标值，要求得目标值就必须建立相应的目标约束函数，这些约束函数的值和目标值之间的偏差达到最小就是多重约束目标的组……