基于离散粒子群的DNA编码序列组合优化方法

J4 ›› 2011, Vol. 33 ›› Issue (3): 179-184.

基于离散粒子群的DNA编码序列组合优化方法

任晓娜1，张大方1,2，向旭宇2

（1.湖南大学软件学院，湖南长沙 410082;2.湖南大学计算机与通信学院,湖南长沙 410082）

收稿日期:2009-12-15 修回日期:2010-03-15 出版日期:2011-03-25 发布日期:2011-03-25
作者简介:任晓娜（1984），女，山西定襄人，硕士，研究方向为DNA计算和生物信息。张大方（1959），男，上海人，博士，教授，博士生导师，研究方向为可信网络、容错计算和生物信息等。向旭宇(1972)，男，湖南益阳人，博士生，研究方向为网络安全和生物信息。
基金资助:
国家自然科学基金重大研究计划资助项目（90718008）;湖南省科技计划重点项目（2009JT1018）

A Combinational Model to Optimize DNA Encoding Based on Discrete Particle Swarm Optimization

REN Xiaona1,ZHANG Dafang1,2,XIANG Xuyu2

(1.School of Software,Hunan University,Changsha 410082；
2.School of Computer and Communications,Hunan University,Changsha 410082,China)

Received:2009-12-15 Revised:2010-03-15 Online:2011-03-25 Published:2011-03-25

摘要/Abstract

摘要：

本文分析了DNA编码序列设计的目标及需要满足的约束条件Hmeasure、连续性、相似度、发夹结构、GC含量等约束，建立一种组合优化评价模型，通过引入基于权重的适应度函数来评价DNA序列集合的优劣，最后提出基于该模型的离散粒子群优化算法(DPSO)生成有效的DNA编码序列。根据优化问题的约束条件及离散量的特点，对粒子的位置、速度等量及运算规则进行了重新定义。实验结果对比表明，本文所述DPSO算法生成的DNA编码序列具有较高的质量。

关键词: DNA计算, DNA编码, 组合优化, 离散粒子群优化算

Abstract:

We analyze the objective and several constraints of DNA encoding, build a combinational optimization model. Based on this model, a discrete particle swarm optimization (DPSO) algorithm is proposed to produce DNA encoding sequences. According to the special constraints and the characteristics of discrete parameters, we redefine the computation rules of particle’s position and velocity. The result shows that the DNA sequences produced by DPSO have better quality than that produced by the genetic algorithm.

Key words: DNA computing;DNA encoding;combinational optimization;discrete particle swarm optimization

任晓娜1，张大方1,2，向旭宇2. 基于离散粒子群的DNA编码序列组合优化方法[J]. J4, 2011, 33(3): 179-184.

REN Xiaona1,ZHANG Dafang1,2,XIANG Xuyu2. A Combinational Model to Optimize DNA Encoding Based on Discrete Particle Swarm Optimization[J]. J4, 2011, 33(3): 179-184.

[1]	邓文博, 刘帅, 刘福才, 黄茹楠. 基于压缩感知和DNA编码的图像加密算法[J]. 计算机工程与科学, 2022, 44(09): 1574-1582.
[2]	李进生，蒙江，童名文. 基于分布式遗传算法的水质传感器布置优化研究[J]. 计算机工程与科学, 2019, 41(03): 545-550.
[3]	覃远年，梁仲华. 蚁群算法研究与应用的新进展[J]. 计算机工程与科学, 2019, 41(01): 173-184.
[4]	周忠宝1,刘悦悦1,2,金倩颖1,肖和录1,程旭曼3. 基于FDH的分区域多目标遗传算法[J]. 计算机工程与科学, 2018, 40(07): 1295-1302.
[5]	李锋刚1,2，骆林1,2，陈亚波1,2,蒋祥飞1,2. 求解均值-CVaR投资组合模型的改进粒子群算法[J]. 计算机工程与科学, 2016, 38(09): 1870-1877.
[6]	张映玉1，付樟华2. 绝热量子优化算法研究进展[J]. J4, 2015, 37(03): 429-433.
[7]	王志刚，夏慧明. 求解车辆路径问题的人工蜂群算法[J]. J4, 2014, 36(06): 1088-1094.
[8]	徐京雷，赵洪超，刘希玉. 旅行商问题的闭环DNA算法[J]. J4, 2014, 36(01): 111-114.
[9]	张晓强1，王蒙蒙2，朱贵良2. 图像加密算法研究新进展[J]. J4, 2012, 34(5): 1-6.
[10]	童科,毛力. 基于蚁群优化算法求解矩形件排样问题[J]. J4, 2011, 33(7): 158-162.
[11]	袁利永1,倪应华2,金炳尧3,马永进1. PBIL算法在组合优化问题中的应用研究[J]. J4, 2011, 33(3): 141-145.
[12]	殷人昆[1] 吴阳[2,3] 张晶炜[3,4]. 蚁群算法解决指派问题的研究和应用[J]. J4, 2008, 30(4): 43-45.
[13]	朱雅莉李肯立. DNA计算机中堆栈数据结构的设计[J]. J4, 2008, 30(4): 121-123.
[14]	虞成诚[1] 钟声[1] 胡绍华[2]. 基于深度优先搜索的一般图匹配算法[J]. J4, 2008, 30(12): 45-48.
[15]	刘毅[1,2] 宋玉阶[1]. 收缩背包问题的DNA算法[J]. J4, 2007, 29(8): 55-57.