基于闭环DNA的边着色问题DNA算法

提出一种新的DNA计算模型——闭环DNA计算模型。引进了批删除实验。讨论了其实现过程；提出并证明了边着色问题的基本定理，设计并实现了闭环DNA计算算法．该算法将边的DNA编码分为两部分，一部分存储边和色位置的二维数据，另一部分存储色号值；在DNA计算的主体部分用批删除实验得到全部正常的边着色，并通过电泳实验和检测实验获得χ′^-正常边着色．举例说明了算法的有效性和可行性．     

基于DNA计算的指派问题

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

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

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

集合覆盖问题闭环DNA算法

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

基于批分离实验的最大独立集问题DNA算法

根据解决最大独立集问题的需要,讨论了简化的粘贴模型,该模型只由单链DNA的存储链和分离板组成.以分离实验为基础提出了批分离实验和生化操作过程,该实验可以快速分离存储链.基于批分离实验设计了最大独立集问题的DNA算法,并给出其生化实现过程:先形成所有顶点子集的初始解空间;接着用批分离实验对每个顶点进行检测,筛选全部满足不相邻要求的顶点子集,从而得到全部独立集;然后通过电泳实验得到全部最大独立集;最后通过检测实验输出实验结果.讨论并证明了算法的正确性和复杂性,算法的操作次数是线性的,通过仿真实验说明了算法的有效性和可行性.     

基于清晰有理数均值的新匹配聚类算法

通过改进清晰有理数均值的方法, 提出一种新匹配聚类算法. 首先计算每条数据的清晰有理数均值, 然后与匹配项比较, 得出聚类结果, 解决了人工标注型数据的聚类问题. 将该方法在反欺诈网页领域中进行了检测和验证, 并与使用同一名称但不同类型数据集的K最近邻算法进行比较, 实验结果表明, 该方法在反欺诈网页领域中比K最近邻算法更有效, 同时也证明了新匹配聚类算法在人工标注型数据上聚类具有合理性.     

DNA计算在电路设计中的应用

讨论了DNA计算的机理,给出了DNA计算的基本生化实验.对电路布线问题,提出了DNA算法,即首先对导线的顺序进行DNA编码,其次通过杂交反应产生所有可行解,最后通过电泳实验得到最优解.对所得结果进行检测时采用了DNA芯片和分子信标技术,对探针进行生物素标记解读出最优解.该算法的核心运算是杂交反应,算法总的操作次数为n 3,其中n为电路布线问题的规模.最后,通过6对接线柱的例子说明了DNA算法的有效性和正确性.     

ATM交换中的随机赋权匹配算法

ATM交换中的赋权匹配有吞吐率高、性能好的优点 ,但是算法复杂度高 ,难以实时实现 .该文提出随机赋权匹配算法以解决实时实现的问题 ,同时 ,使匹配的总权值依旧很大 ,保持了赋权匹配的优点 .     

基于粘贴和删除系统求解旅行商问题的DNA算法

旅行商问题（Traveling Salesman Problem,TSP）是一个典型的NP完全问题.粘贴和删除模型是DNA计算的两个基本计算模型.结合上述两个模型的优点,构造粘贴-删除模型,并利用该模型给出求解旅行商问题一种新的DNA算法.     

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

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

最小生成树DNA算法

为了改进粘贴模型,提出了用生化实验实现求解割集的计算方法,并基于该方法给出了最小生成树DNA算法.首次将分离实验扩展为基于分离板的分离实验和基于电泳技术的分离实验,所提出的最小生成树DNA算法打破了DNA计算的计算模式——用求解割集的最小边的方法逐步产生最小生成树.用该方法求解割集利用了分离实验运算的高度并行性,最小生成树DNA算法的时间复杂度是线性的,从而降低了算法的时间复杂度.     

基于网络优化的交通网络设计研究

针对交通网络设计问题,首先定义了赋权二分图的单边控制集问题,给出了相应的算法;然后将上述算法和割集遍历算法相结合,构建了基于网络优化思想的两个启发式算法,并对两个算法进行了比较分析,证明了算法Ⅱ可在有限步终止.最后通过算例验证了两个算法的有效性.     

基于切分模板的实时跟踪算法

相关匹配算法是一种经典的匹配算法 ,通过计算模板图像和待匹配图像的互相关值来确定匹配的程度 ,具有很高的准确性和适应性 ,在目标跟踪中得到了广泛应用。但是相关匹配算法计算耗时过于庞大 ,难以达到实时要求 ,并且当目标在模板中所占比例很小时 ,很难确定模板的准确位置 ,使得此算法在实时目标跟踪中难以得到应用。文中在相关匹配的基础上提出了一种基于切分模板的实时跟踪算法。匹配的模板被分为几个部分 ,每个部分均有不同的加权值 ,最后的相关匹配度为各部分匹配度的加权和。算法中还设置了一个不是实时更新的加权模板 ,以提高算法的抗干扰能力 ,并采用金字塔搜索算法进行加速。实验结果显示 ,此算法有效地克服了相关匹配算法的缺点 ,具有较好的匹配精度和实时性     

基于线图Q-谱的点模式匹配算法

针对大多数谱方法不能够较好地处理不同大小点集匹配的问题,提出了一种基于线图Q-谱的点模式匹配算法.首先,对相关点集构造赋权完全图,再对每个点利用与其关联的前k条最短边来构造线图;然后,根据线图构造无符号Laplacian矩阵,对其进行谱分解,并利用谱分解所获得的特征值(Q-谱)来表示点的特征,通过这些特征计算点之间的匹...     

DNA编码的模型分析

提出了适应DNA计算的DNA编码问题.对等码长的DNA编码问题的数学模型进行分析.以优化码长作为目标,分析了约束条件.以杂交反应为核心将约束条件分为基本约束和控制生化实验的约束,而控制生化实验的约束包含组合约束和热力学约束.控制移动不匹配的下值才能控制杂交反应,由此改进了移动距离.引入窗口距离解决了错配总量和分布的控制问题.     

求解约束最小二乘半正定规划问题的L-BFGS方法

对带等式和不等式约束的最小二乘半正定规划问题的求解进行了研究。在Slater约束规范条件下,对偶问题的最优解与原问题最优解相等。因此,考虑将最小二乘半正定规划问题转化为相应的对偶问题,通过求解对偶问题达到求解原问题的目的。针对最小二乘半正定规划问题的对偶问题,首先构造相应的二次模型,沿负梯度方向最小化该二次模型得到柯西点,在此基础上,利用积极约束技巧,划分积极约束集与非积极约束集,然后应用L-BFGS技巧对自由变量进行加速,从而求得对偶问题的最优解。最后,从理论上证明了算法的全局收敛性,并进行了初步的数值实验,将该算法与光滑化牛顿法作对比,结果表明该算法在计算时间上有一定的优势。     

归纳环及归纳域

提出了归纳环的概念(即:含1且适合1阶Peano归纳公理的环),指出其意义并提出下列关于确定归纳环代数结构的问题:是否每一归纳环都与由整数环的一族剩余类环及特征数0的代数闭域所作的一个超积初等等价?首先给出了有关归纳环及归纳域的一些基本事实.然后着重在代数范围内进行讨论,得到下列的结果:每个有限次实代数数域都不是归纳域;代数整数环的每个子环都不是归纳环.还证明了很多有限次代数数域不与上述的超积初等等价.     

基于掩码匹配的报文双抽样方法

基于掩码匹配的报文抽样算法是一种实用性较强的分布式流量抽样算法,但是该算法在测量报文到达时间间隔的分布这一重要网络流量特征时性能较差。首先根据误差理论分析了产生这一问题的原因,为了降低测量的系统误差,在原算法中引入了双抽样的改进方案。考虑到改进后的算法会给测量系统带来额外的负担,提出了增加了抽样掩码位数的解决办法,并且论证了其可行性。最后基于实际的网络流量数据进行了实验验证,结果表明：改进后的算法测得的报文到达时间间隔的分布符合真实的分布情况,并且对其它网络性能指标的测量精度影响较小。