基于DNA计算的指派问题

给出了推广的闭环DNA计算模型及其生化实验.用闭环DNA计算模型设计出了指派问题的DNA算法.对决策变量进行4组DNA编码来存放决策变量和效益值;通过有目的的终止技术和删除实验得到指派问题的全部可行解;通过批接入实验、电泳实验和检测实验获得最优指派问题的最优解.举例说明了算法的可行性.最后讨论了推广的闭环DNA计算模型的应用前景和不足之处.     

集合覆盖问题闭环DNA算法

介绍了闭环DNA计算模型及其生化实验,分析了集合覆盖问题及其数学模型.根据任何一个元素至少属于一个集合构成可行集合覆盖的原理,设计了集合覆盖问题闭环DNA算法,该算法首先对集合的0-1决策变量按照0和1的取值、对应的价值系数进行两组DNA编码并形成所有可能解;再用接入实验和删除实验筛选出全部可行解;然后用接入实验得到这些可行解的目标函数值,并用电泳实验得到全部最优解;最后通过检测实验输出所有最优解.首次提出基于电泳技术检测实验以"接入-电泳-删除"为实验顺序,可以检测多种DNA编码.算例说明了算法的有效性.     

基于DNA计算的图像模板匹配算法

针对已有的图像匹配算法都是在小规模基础上的统计识别方法,均是串行运算,对样本的训练和目标识别都须进行大量复杂的运算,难以适应大规模图像比对的问题,利用DNA计算强大的并行性,提出了一种基于DNA计算的图像模板匹配算法.首先,将二进制的图像信号编码为满足一系列约束并允许一定非特异性杂交的DNA序列;然后,通过DNA退火反应得到匹配问题的解;最后,利用这一算法得出的128个单链DNA编码进行了数字图像模板匹配的仿真实验.仿真结果表明DNA计算应用于大规模图像匹配问题是可行的.     

最大权匹配问题的闭环DNA算法

给出并证明了在DNA计算中处理实数问题的策略,即首先在误差限范围内用有理数集合代替实数集合;再取出与有理数集合一一对应的最小的整数集合.针对赋权匹配问题,给出了基于闭环DNA计算模型的赋权匹配问题算法.该算法首先按边进行三组编码并合成初始闭环DNA;再以相邻两条边为约束条件用删除实验获得所有匹配,并用电泳实验得到所有最大权匹配,最后用检测实验输出最优解.证明了算法的正确性,讨论了算法复杂度,并以一个例子说明了算法的有效性.     

基于杂交链式反应工序问题的DNA计算模型

杂交链式反应是一种无酶参与的自主组装反应.文章利用杂交链式反应和折纸术给出工序问题的求解过程.首先,将工序问题映射为一个有向图,将调整时间之和t+(Ji)最小的点作为根节点,将问题映射为一个有向树.然后,将有向树锚定在矩形的折纸基底上,利用杂交链式反应来求解问题的最优解.此模型在试管中进行,只有加入了启动链以后,反应才可进行.当发夹结构打开后,反应是不可逆的,最终生成的都是以根节点为起点,以叶子为终点的有向路径.最后,利用荧光光谱仪检测每条有向路上的荧光个数,从而确定问题的最优解.通过仿真可得该模型的复杂度为Θ(depth(T))+Θ(n).     

改进混沌优化算法在水电站水库优化调度中的应用

为提高多维目标函数全局最优解的计算精度,提出了一种改进的混沌优化算法(MCOA).利用混沌运动的随机性、遍历性和规律性进行全局寻优;通过引入解向量的优选,将解向量定位到最优解的附近,从而找出全局最优解.最后将该算法应用于水电站水库优化调度问题,并进行仿真计算,计算结果验证了算法的有效性.MCOA原理简单,易于编程实现,具有较大的实用价值,为求解水电站水库优化调度问题提供了一种有效方法.     

树状网络中最短接通时间的快速算法

针对文件分配问题,提出了一种求解树状网络中最短接通时间的快速算法.基于边着色和标号的思想,结合网络拓扑,将原来的网络分解为一系列更小规模的子网络进行处理.子网络对应的最优解逼近原始网络的最优解.理论分析和实验结果表明,在最短接通时间的计算精度略微降低的情况下,本文算法的计算复杂度为O(n).     

中继网络中基于能量效率的动态用户接入算法

为了解决中继网络中基于能量效率的用户接入问题,将用户数据需求严格受限下基于能量效率最优的动态用户接入问题建模为一个整数优化问题,该问题类似于一个NP-hard的多维背包问题.首先,采用穷搜法分析了该问题最优解的复杂度.然后,提出了一种低复杂度、高效的基于能量效率的动态用户接入算法(UAEEM).该算法在保证用户数据需求严格受限的前提下,按照系统射频端和电路端的能量效率最大原则,动态调整用户归属和中继的工作状态,以实现网络能量效率最大化.最后,通过仿真实验验证所提算法性能.结果表明,UAEEM算法能显著提高系统的能量效率、降低系统的计算复杂度,且其性能接近最优解.     

移动Ad Hoc网络QoS路由的闭环DNA计算模型

提出针对移动Ad Hoc网络QoS路由问题的闭环DNA计算模型.对每条路径进行弧、费用、探针的3组编码,再采用有目的的终止技术合成所有从起点到终点的弧首尾相连路径,然后通过接入实验和电泳实验得到费用最小路径,并通过检测实验输出所有费用最小路径,同时给出了算法的生化实现过程.实验结果表明:在不增加算法复杂度情况下获得了QoS路由问题的最优解.     

基于模拟植物生长算法的构造通讯网络Steiner最优树方法

通讯网络作为现代社会信息系统不可或缺的重要枢纽,其设计问题直接影响总消耗成本的高低.本文提出了基于模拟植物生长算法求解通信网络设计问题的新方法.对于给定原始通讯节点的通讯网络,利用模拟植物生长算法来构造网络的Steiner最优树使得网络总布线耗费达到最小.通过对实例计算,结果表明,本算法不仅可获得问题的最优解,计算所需时间也有减少,明显优于其他方法.