Domatic Partition问题的DNA计算方法研究

Domatic partition问题是一类经典的NP完全问题,在诸多领域中有着广泛的应用,但是至今仍没有多项式时间内的解决方案.DNA计算是一种并行计算能力极强的计算方式,粘贴模型是DNA计算中一种基于粘贴运算的计算模型,基于该模型提出了一种求解domatic partition问题的DNA算法,该算法在多项式的时间内通过两步筛选过程即可以在初始解空间中找出问题的解.为证明该算法的可行性,用java程序对算法进行了仿真模拟,程序在计算机上运行的结果证明此算法是正确且有效的.     

基于自组装的N皇后问题DNA计算算法

N皇后问题是理论计算机科学中一个经典的NP难问题.自Adleman首次运用DNA计算来解决NP问题以来,DNA计算已成为计算机科学的研究热点之一,现有N皇后问题的DNA计算机算法多基于粘贴和剪接模型,存在生化操作复杂度和实验误差较高等问题.本文提出了一种基于DNA自组装模型来求解N皇后问题的DNA计算方法.算法通过减少实验操作步骤数,降低了生化解的错误率.算法使用的tiles分子块种类为O（n²）,生化操作复杂性为O（1）,其中n为皇后的个数.与求解N皇后问题的其它DNA算法的对比分析表明,本算法可提高生化解的准确性,降低算法生化实验的复杂度,具有良好的易操作性.     

0-1规划问题的DNA计算

DNA计算是解决一类难以计算问题的一种新方法,这种计算随着问题的增大可以呈指数增长。迄今为止,许多研究成果已经成功地提高了它的性能和增加了它的可行性,该文提出了在基于表面的DNA计算中采用了荧光标记策略,解决简单的0-1规划问题的一种理论方案,尝试了DNA计算在规划问题中的应用。这种方法具有编码简单、耗材底、操作时间短、技术先进等优点。     

高阶非线性非自治系统分析研究

为了更有效的解决高阶非线性非自治系统的求解问题,提出基于等效小参数法的高阶非线性非自治系统的求解方法,应用分解法原理,通过引入谐波平衡和同阶小量相等,建立一类非线性动态系统周期解的逆算符表达的递推算法,将高阶非线性非自治系统转化成一个通用方程,然后利用Matlab开发出相应的软件系统,实现计算机自动求解。对包含sin（t）或cos（t）的非线性非自治GENESIO系统和非线性非自治COULLET系统使用等效小参数法进行详细推导,分别求解非自治GENESIO系统和非自治COULLET系统的周期解,该算法具有较高的计算精度和较大的普适性,是求解一类非线性非自治系统周期解的有效方法。     

采用种群迁移策略的战场频率动态分配

给出了战场频率分配问题的形式化定义,并提出了一类标准问题测试集。针对问题特点,指出了现有频率分配策略的局限性,提出了一种基于种群迁移策略的战场频率动态分配新算法。新策略中,算法每一次迭代结束前,都以随机候选解和基于上一代最优解生成的候选解作为迁移种群来替换当前种群中较差的解,其中,迁移种群的生成过程受当前可用频率资源的限制。仿真结果表明,新提出的算法能够有效求解战场频率动态分配问题。     

DNA-纳米颗粒共聚体在最大匹配问题中的应用

该文提出一种DNA计算模型,利用DNA-纳米金颗粒共聚体的自组装来解决图论中的一个NP完全问题——最大匹配问题。根据模型该文设计了能够基于一个具体的图进行自组装的特殊的DNA-纳米金颗粒共聚体,然后利用一系列的实验方法来获得最终的解。这种生物化学算法可以极大地降低求解最大匹配问题的复杂度,这将为DNA自组装计算模型提供一种切实可行的方法。     

DNA-纳米颗粒共聚体在最大匹配问题中的应用

该文提出一种DNA计算模型,利用DNA-纳米金颗粒共聚体的自组装来解决图论中的一个NP完全问题——最大匹配问题.根据模型该文设计了能够基于一个具体的图进行自组装的特殊的DNA-纳米金颗粒共聚体,然后利用一系列的实验方法来获得最终的解.这种生物化学算法可以极大地降低求解最大匹配问题的复杂度,这将为DNA自组装计算模型提供一种切实可行的方法.     

由牛顿算法求解Pao-Sah电压方程的一个初始值

目前集约建模的趋势是由基于阈值电压的模型转向基于表面势的模型,而后者需要一个对非线性Pao-Sah电压方程的精确解,作为隐含数方程,Pao-Sah电压方程必须数值求解以求得表面势。牛顿算法是一个收敛较快而常用的算法,但却易收敛到错误的根,提出一个能保证牛顿算法收敛到正确的表面势解、且具有可控的高精度及运算速度的初始值,由该初始值计算并分析了数值计算结果。高精度的数值解可作为其它近似解的检验。     

图3-着色问题的O链数DNA计算机算法

随着DNA计算的不断发展,如何克服穷举算法带来的指数爆炸问题已成为DNA计算领域的重要研究目标之一.为减少图3-着色问题DNA计算机算法中的DNA链数,本文将Adleman-Lipton模型生物操作与粘贴模型解空间相结合的DNA计算模型进行扩展,通过设计顶点着色器、稀疏图/稠密图搜索器,提出一种用于求解图3-着色问题的DNA计算模型与算法.将本算法与同类算法对比分析表明:本算法在保持多项式操作时间的条件下,将求解n个顶点的图3-着色问题所需DNA分子链数从O(3ⁿ)减少至O(2ⁿ),改进了3-着色问题同类文献的研究结果.     

图的顶点着色问题的DNA算法

图的顶点着色问题是指无向图中任意两个相邻顶点都分配到不同的颜色,这个问题是著名的NP-完全问题,没有非常有效的算法.但在1994年Adleman^[1]首次提出用DNA计算解决NP-完全问题,设计出一种全新的计算模式—模拟生物分子DNA的结构并借助于分子生物技术进行计算,使得NP-完全问题的求解可能得到解决.本文首先提出了基于分子生物技术的图的顶点着色问题的DNA算法,算法的关键是对图中的顶点和顶点的颜色进行恰当的编码,以便于使用常规的生物操作及生物酶完成解的产生及最终解的分离,依据分子生物学的实验方法,本文提出的算法是有效和可行的;其次指出了该算法的优点、存在的问题及将来进一步的研究方向.     

最小顶点覆盖问题的改进粘贴模型

DNA计算是一种模拟生物分子DNA的结构并借助于分子生物技术进行计算的新方法。它开创了以化学反应作为计算工具的先例,具有广阔的应用前景。本文简单回顾了DNA计算的发展,并简要介绍了分子计算的一种模型粘贴模型。最后我们利用粘贴模型的基本原理,运用荧光标记技术,提出了最小顶点覆盖问题的表面技术解决方案。     

一种基于波束空间的单次快拍MUSIC算法

针对MUSIC算法在工程应用中存在的计算量大、快拍需求数多等问题,详细研究了一种单次快拍MUSIC算法。针对这种算法存在的分辨力差、估计偏差大等缺陷,提出了一种新的基于波束空间的单次快拍MUSIC算法,该方法首先利用单次快拍来估计阵列数据的协方差矩阵,再将常规波束形成方法和MUSIC超分辨方法相结合,实现对空间谱的估计。仿真结果表明,这种新方法提高了分辨力,降低了估计偏差,进一步减少了运算量。     

一种约束最小模方估计的图像迭代重建算法

较少投影重建问题一直是成像领域研究的重点，传统的卷积反投影(CBP)不能产生满意的重建图像——伪影严重、误差大，而迭代算法却具有一些较好的特性。本文以CT成像为基础，以最小模方为目标函数提出了一种约束迭代重建算法，本算法与无约束迭代算法相比，在花费相同时间的情况下，可以重建出误差更小，拟合度更高的图像。以扇束扫描投影数据重建的结果验证了本文的结论。     

High-level synthesis for low power based on network flow method

We propose an effective algorithm for power optimization in behavioral synthesis. In previous work, it has been shown that several hardware allocation/binding problems for power optimization can be formulated as network flow problems and cand be solved optimally. However, in these formulations, a fixed schedule was assumed. In such a context, one key problem is that given an optimal network flow solution to a hardware allocation/binding problem for a given schedule, how to generate a new optimal network-flow solution rapidly for a local change of the given schedule. To this end, from a comprehensive analysis of the relation between network structure and flow computation, we devise a two-step procedure: Step 1) a max-flow computation step which finds a valid (maximum) flow solution while retaining the previous (maximum flow of minimum cost) solution as much as possible and Step 2) a min-cost computation step which incrementally refines the flow solution obtained in Step 1, using the concept of finding a negative cost cycle in the residual graph for the flow. The proposed algorithm can be applied effectively to several important high-level optimization problems (e.g., allocations/bindings of functional units, registers, buses, and memory ports) when we have the freedom to choose a schedule that will minimize power consumption. Experimental results (for bus synthesis) on benchmark problems show that our designs are 4%-40% more power-efficient over the designs produced by a random-move based solution and a clock-step based optimal solution, which is due to a) exploitation of the effect of scheduling and b) optimal binding for every schedule instance. Furthermore, our algorithm is about 2.6 times faster in run time over the full network flow based (optimal) algorithm, which is due to c) our novel (two-step) mechanism which utilizes the previous flow solution to reduce redundant flow computations.     

基于InSAR的三维地形匹配导航技术的研究与实现

研究了一种以干涉合成孔径雷达(InSAR)信息为基础的三维地形匹配导航系统,该系统采用基于3-D Zernike矩的三维地形匹配算法,同时针对3-D Zernike矩在地形匹配中计算实时性差的问题进行了改进。为验证系统的有效性和算法性能,搭建了基于VC++和OpenSceneGraph的三维可视化软件仿真平台。仿真结果表明,基于3-D Zernike矩的三维地形匹配算法定位精确度高,对地形的适应能力强,算法的实时性问题得到了良好解决,系统具有较高的工程实用价值。     

Ménage问题的一种粘贴DNA算法

 解决图论与排列组合难题是DNA计算领域的研究目标之一.为了使用分子生物方法解决Ménage问题,本文给出了Ménage问题的数学模型;并对解决该问题的难点进行了分析,提出一种解决方案,改进了该问题的数学模型;提出一种解决Ménage问题的粘贴DNA算法并简要分析了该算法的复杂度.为了提高效率,引入广义分离和广义多级分离操作;通过一个实例给出了实验操作步骤,对实验进行了模拟.     

求解TSP问题的离散型萤火虫群优化算法

基于求解TSP问题,提出一种离散型萤火虫群优化(DGSO)算法,该算法结合TSP问题特点,给出一种有效编码和解码方法,并定义适合编码的个体间距离计算公式和编码更新公式.同时,为增强算法求解TSP问题的局部搜索能力,加快算法的收敛速度,算法使用了操作简单的2-Opt优化算子.最后,通过对10个TSP问题进行仿真实验,实验结果表明本文提出的算法是在种群规模较小,迭代次数较少的情况下就可以收敛到已知最优解.在大规模TSP算例中算法获得的最优值与理论最优值的误差也在1%以下.     

High Definition Image Encryption Algorithm Based on AES Modification

In this article, a high-speed and highly restricted encryption algorithm is proposed to cipher high-definition (HD) images based on the modified advanced encryption standard (AES) algorithm. AES is a well-known block cipher algorithm and has several advantages, such as high-level security and implementation ability. However, AES has some drawbacks, including high computation costs, pattern appearance, and high hardware requirements. The aforementioned problems become more complex when the AES algorithm ciphers an image, especially HD images. Three modifications are proposed in this paper to improve AES algorithm performance through, decreasing the computation costs, decreasing the hardware requirements, and increasing the security level. First, modification was conducted using MixColumn transformation in 5 rounds instead of 10 rounds in the original AES-128 to decrease the encryption time. Security is enhanced by improving the key schedule operation by adding MixColumn transformation to this operation as second modification. In addition, to decrease the hardware requirements, S-box and Inv. S-box in the original AES are replaced by one simple S-box used for encryption and decryption in the proposed method. The proposed AES version conducts one of the ciphering modes to solve the appearance pattern problem. Experimental results indicate that the proposed modifications to the AES algorithm made the algorithm more compatible with HD image encryption.