因子分解问题的DNA计算机算法探究

对分子生物技术的因子分解问题的DNA计算机算法进行探讨,并提出了以Pollard-1算法为因子分解的DNA计算机算法,通过DNA分子生物操作,实现加、减、乘、除的运算,完成了平方-乘DNA子算法与欧几里得DNA子算法,最终求得结果。通过Pollard p-1算法,降低DNA链数,提高DAN计算机容量,经分子生物学实验证明,Pollard p-1算法在解决因子分解问题中是可行且有效的。     

满秩分解最小二乘法船舶航向模型辨识

为了解决标准遗忘因子最小二乘法在线辨识船舶航向模型参数漂移和发散问题,考虑到船舶在实际航行中存在海洋环境扰动和数据欠激励的情况,提出并验证了一种基于满秩分解的递推最小二乘法.用实船数据进行船舶航向模型参数辨识,将辨识结果与标准遗忘因子最小二乘算法、多新息最小二乘法、最小二乘支持向量机的辨识结果进行对比,验证了满秩分解有...     

损失数据线性参数系统的递推最小二乘辨识方法

针对损失数据线性参数系统的参数辨识问题, 借助辅助模型辨识思想推导出其变递推间隔辅助模型递 推最小二乘算法.为了提高该算法的计算效率, 利用分解技术得到变递推间隔分解递推最小二乘算法 估计系统参数.此外, 在变递推间隔分解递推最小二乘算法中引入遗忘因子, 从而提高参数估计精度和收敛速度.仿真结果表明, 所提出的算法能有效估计系统参数.     

基于Fisher判别分析的增量式非负矩阵分解算法

增量式非负矩阵分解算法是基于子空间降维技术的无监督增量学习方法.文中将Fisher判别分析思想引入增量式非负矩阵分解中,提出基于Fisher判别分析的增量式非负矩阵分解算法.首先,利用初始样本训练的先验信息,通过索引矩阵对新增系数矩阵进行初始化赋值.然后,将增量式非负矩阵分解算法的目标函数改进为批量式的增量学习算法,在此基础上施加类间散度最大和类内散度最小的约束.最后,采用乘性迭代的方法计算分解后的因子矩阵.在ORL、Yale B和PIE等3个不同规模人脸数据库上的实验验证文中算法的有效性.     

基于多级抽取的0-1整数规划问题的DNA算法

DNA计算是一种借助于分子生物技术进行计算的新方法,在解决一类困难问题特别是NP-完全问题上具有硅计算机无法比拟的优势,利用DNA计算求解0-1整数规划问题的研究具有重大的意义.基于多级分离模型解决0-1整数规划问题,且给出DNA算法.通过一个实例给出了操作的步骤.     

多变量系统的耦合梯度辨识算法与性能分析

针对多变量系统维数大、参数多、一般的辨识算法计算量大的问题, 基于耦合辨识概念, 推导多变量系统的耦合随机梯度算法, 利用鞅收敛定理分析算法的收敛性能. 算法的主要思想是将系统模型分解为多个单输出子系统,在子系统的递推辨识过程中, 将每个子系统的参数估计值耦合起来. 所提出算法与最小二乘算法和耦合最小二乘算法相比, 具有较少的计算量, 收敛速度可以通过引入遗忘因子得到改善. 性能分析表明了所提出算法收敛, 仿真实例验证了算法的有效性.

     

图论中的DNA计算

DNA计算是一种模拟生物分子DNA结构并借助分子生物技术进行计算的新方法,其高度并行性和巨大的信息存储量为解决NP-完全问题提供全新的途径.介绍DNA计算的基本原理,详细介绍哈密顿图的DNA算法以及图着色问题的表面DNA计算,最后介绍DNA计算在图论中的进展以及DNA计算存在的问题.     

一种加权增强的欠定盲辨识方法

针对欠定盲源分离混合矩阵问题,提出了一种基于二阶统计量平行因子分解,加权增强最小二乘法的欠定混合盲辨识方法。该算法不需要源信号满足稀疏性要求,仅在源信号满足相互独立和最多一个高斯信号的条件下,将独立源信号的空间协方差矩阵构建三阶张量,采用加权增强最小二乘法实现张量的标准分解,完成混合矩阵的估计。由于平行因子分解的唯一性在欠定条件下依然成立,该算法可以解决欠定盲源分离问题。仿真实验结果表明:提出的算法在计算欠定混合时具有很好的辨识效果,而且实现简单,可满足实际应用的要求。     

双容错数据布局构造方法研究

总结了磁盘阵列双容错编码的图表示法和双容错数据布局构造问题的研究成果,详细讨论分析了几种双容错数据布局构造方法:基于完全图的完全1-因子分解的方法、基于完全二部图的完全1-因子分解的方法和基于搜索、优化算法的方法.性能分析表明,基于完全图的完全1-因子分解的BG-HEDP布局,是一种综合性能非常好的布局.     

收缩背包问题的DNA算法

收缩背包问题是标准背包问题的一个扩展，其中背包的容量为所装物品数量的非增函数。本文提出了基于分子生物技术的求解收缩背包问题的DNA算法，首先将其约束条件进行分解；然后设计一系列与物品重量相对应的寡聚核苷酸片断及其链接模板，在链接酶的作用下将它们进行链接反应，生成代表任意物品组合的DNA链；再通过基本的生物操
作筛选出可行解；最后比较各个可行解对应的目标函数值，进而得到最优解。     

DNA计算机中图的深度优先搜索遍历算法

提出DNA计算机中图数据结构的一种设计方法,给出具体的存储结构以及深度优先搜索遍历的算法。该算法实现了在DNA计算机下图元素的遍历。为证明其可行性,给出一个具体的算法实例,描述了DNA计算机上的运行机制。依据分子生物学的理论,证明算法是有效且可行的。     

基于单纯形方法的建筑钢筋配料算法

文章以单纯形方法为基础求解建筑钢筋配料问题。运用单纯形方法的一个问题是解为小数值，作者用一个简单的方法进行取整。运用单纯形方法的另一个更重要的问题是决策变量数过大。为在有限的内存空间和时间内运用单纯形法，文中提出了五个用于减少决策变量数（备选方案数）的方法，并综合运用了这五个方法，既将空间和时间复杂度减少到合适的程度，又保证了配料结果经济有效。     

不确定环境下基于鲁棒粒子群优化的物流射频识别网络优化

针对电子标签位置不确定的物流射频识别(radio frequency identification,RFID)网络优化问题,综合考虑覆盖率、负载平衡程度、成本,建立了鲁棒优化模型.为求解负载平衡程度,采用基于Korobov点阵的蒙特卡洛方法.为减少计算量,提高算法寻优能力,提出一种基于不对称时变S–形(Sigmoid)函数的鲁棒粒子群算法(PSO).样本规模仅取部分较小整数、部分较大整数.仅在算法迭代后期,样本规模期望值大,保证算法开发精度;在较多迭代次数中,样本规模期望值小,加快算法探索速度.仿真实验表明,该方法具有较佳的搜索性能.     

How efficiently can room at the bottom be traded away for speed at the top?

Given exponential 2 ⁿ space, we know that an Adleman-Lipton computation can decide many hard problems – such as boolean formula and boolean circuit evaluation – in a number of steps that is linear in the problem size n. We wish to better understand the process of designing and comparing bio-molecular algorithms that trade away weakly exponential space to achieve as low a running time as possible, and to analyze the efficiency of their space and time utilization relative to those of their best extant classical/bio-molecular counterparts. We propose a randomized framework which augments that of the sticker model of Roweis et al. to provide an abstract setting for analyzing the space-time efficiency of both deterministic and randomized bio-molecular algorithms. We explore its power by developing and analyzing such algorithms for theCovering Code Creation (CCC) and k-SAT problems. In the process, we uncover new classical algorithms for CCC andk-SAT that, while exploiting the same space-time trade-off as the best previously known classical algorithms, are exponentially more efficient than them in terms of space-time product utilization. This work indicates that the proposed abstract bio-molecular setting for randomized algorithm design provides a logical tool of independent interest. This revised version was published online in June 2006 with corrections to the Cover Date.     

Maximum gap labelings of graphs

Given a graph, we define a base set to be a set of integers of size equal to the number of vertices in the graph. Given a graph and a base set, a labeling of the graph from the base set is an assignment of distinct integers from the base set to the vertices of the graph. The gap of an edge in a labeled graph is the absolute value of the difference between the labels of its endpoints. The gap of a labeled graph is the sum of the gaps of its edges.The maximum gap graph labeling problem takes as input a graph and a base set and maximizes the gap of the graph over all possible labelings from the base set. We show that this problem is NP-complete even when the base set is restricted to consecutive integers. We also show that this restricted case has polynomial time approximations that achieve a factor of 2/3 for trees, of 1/2 for bipartite graphs, and of 1/4 for general graphs, with a deterministic algorithm, while an expected factor of 1/3 for general graphs is achieved with a randomized algorithm. The case of general base sets is approximated within an expected factor of 1/16 for general graphs with a randomized polynomial time algorithm. We finally give a polynomial time algorithm that solves the maximum gap graph labeling problem for a graph that has bounded degree and bounded treewidth. The maximum graph labeling problem shows connections with the graceful tree conjecture.     

基于协同过滤的连续黑箱优化问题元启发算法选择

算法选择(AS)问题旨在为给定问题在算法集合中选择最佳算法.随着优化算法的不断提出,算法选择问题是优化领域亟待解决的问题.提出基于聚类的元启发算法五星评价体系,将算法性能指标映射至整数评价以减小评价空间.通过测试24种常见优化算法与4种最新CEC大赛优胜算法在219种、3000多个标准测试问题上的性能,得到评价矩阵.将评价矩阵作为训练数据,使用协同过滤(CF)算法建立算法评价的预测模型.使用该模型预测算法集内的所有算法在新问题上的评价,结果显示所提出方法预测精度较高,超过90%的预测最佳算法为最终可行算法.敏感性分析显示,该方法在先验信息有限的情况下仍可以保持较高的预测精度.     

基于Java 3D的生物大分子模拟可视化系统

本文采用基于Java 3D的三维可视化编程环境,利用Java 3D、Java Applet、Java多线程等技术,开发了一个适于网络环境的生物大分子模拟的可视化系统,有效地解决了网络环境下生物大分子模拟计算中的三维图像的动静态显示、用户交互、进程控制等问题。     

编码单位可变的倒排索引压缩算法研究

倒排索引是大多数大型文本搜索系统的核心数据结构，索引压缩可以有效地减少倒排索引的空间占用，提升检索效率。针对倒排索引压缩算法中的字节对齐编码进行研究，对于其压缩率不够优秀的问题，提出了分区可变单位编码（PVU编码）。算法以可变单位方式代替固定字节存储，使实际存储空间更加贴合原码长度，从而提高压缩效果。针对序列均匀分区并非最优分区的问题，提出将最优分区问题转化为图论中最短路径问题的方法，使用Dijkstra算法求解序列的最优编码分区。通过对比实验验证了改进优化的PVU编码相较于传统的字节对齐编码能够更好地压缩倒排索引序列。     

3-维匹配问题的一种固定参数枚举算法

枚举问题的多个最优解是计算机科学中人们日益关注的一个研究方向。运用固定参数枚举理论和着色技术对3-维匹配问题提出了一个高效的固定参数枚举算法,即给定一个含有n个带权值的元组集合S,两个非负整数k和z,该算法能在时间O(5.483kkn2z)内枚举出S中权值最大的z个k-matchings,进而表明了3-维匹配问题是固定参数线性可枚举的。     

一种新的基于哈希函数的排序算法

提出一种哈希函数分档的排序算法。根据数组下标递增的特点,针对任意分布整数,建立有效的哈希函数,通过反复映射完成排序。分析算法的时间和空间复杂度,实验验证算法的运行效率。算法分析和实验结果表明：算法的时间和空间复杂度均为O（n）,在问题规模较大时,效率优势明显。