DNA计算在组合优化中的应用及其复杂性

在过去几年里,一些富有卓见的研究人员已经衔接了生物计算和实际的DNA计算之间的间隙。他们使用机灵的编码技术和聪明的分子生物学操作,找到了计算复杂问题的简单方案,并且解决了许多组合优化中的NP-完全问题。然而,计算的执行期间(生物反应过程中),技术的问题已经揭示了对于解决实际问题来说,DNA计算机作为硅计算机的竞争对手目前仍将是不可能的。主要介绍了目前利用DNA计算已经解决的组合优化中的NP-完全问题,并简单地分析了它们的复杂性。     

基于粘贴系统求解TSP问题

旅行商问题，简称为TSP问题，是困难的NP完全问题，在工程实践中具有广泛的应用。利用常规的计算方法求解这个问题，计算所需的时间是随着问题规模的增大以指数形式增加的，因而无法有效的解决此类问题。DNA计算是一种新兴的计算方式，粘贴系统模型是其中基于粘贴运算的一种DNA计算的抽象模型。通过将旅行商问题转化为求赋权图中权值最小的Hamilton圈，利用粘贴系统模型的巨大并行性，可以有效的求解旅行商问题。     

基于妥协案例推理的作战仿真实验范围迁移

作战仿真实验范围通常依靠专家确定，耗费代价较大。为将作战仿真实验的历史数据中关于实验范围选择的知识迁移至新的作战仿真实验案例，提出一种基于妥协策略的案例推理方法。根据案例的数据特点，提出作战仿真实验案例的表示方法；根据案例的结构和属性特点，提出主客观综合赋权的混合相似度计算方法；针对案例检索时出现检索失败和检索结果包含信息量较少的问题，提出基于妥协策略的案例检索方法；根据检索结果的特点，提出实验范围的整合迁移方法。基于历史数据进行了实验分析，证明了方法的有效性。     

一种用于中药配方优化的DNA算法

提出了一种用于中药配方优化的DNA算法，该算法基于质粒DNA技术。首先将中药配方优化问题转化为求无向图的最大权团问题：选取6种具有抑制大肠杆菌生长功效的中药作为图的顶点，分别做抑菌试验，将它们的抑菌圈直径作为顶点的权。然后两两配对进行抑菌试验以确定它们在图中是否有边连接。这样构造了一个顶点赋权的无向图，这个图的最大权团具有最大的抑菌效力，也是这些中药的最佳配伍。求图的最大权团是一个典型的NP．完全问题，而DNA计算具有求解该问题的能力。该方法的提出探讨了DNA计算实用的可能性。     

两类形状特征的语义差及其操作互换性

形状特征技术是产品信息集成的重要手段，但由此而产生的操作灵活性问题则是不容忽视的。对回转体零件中的圆柱体和槽进行语义分析，针对几何相似性，给出设计中的互换操作；阐述了基于知识的综合理解方法，为工艺求解提供计算依据，对解决切削体积规划问题，具有一定的应用意义。     

多源信息处理技术——数据融合

在介绍数据融合技术的基础上，分析了不同融合层次的性质和作用，提出了数据融合大脑功能模型，进而给出一种广义的多传感器数据融合通用结构，该结构具有神经网络的特性，但不涉及权值和学习算法问题；总结、分析了不同融合层次的原理、结构和算法，强调了神经网络在数据融合技术中的应用；分析了数据融合技术中存在的问题，并探讨了其宏观和微观的发展方向。     

案例推理中案例调整技术的研究

以提高案例推理方法中案例调整的有效性为目的，归纳了案例推理中主要案例调整方法，以模糊集理论为出发点，提出并论证了主要案例调整方式的适用条件。在此基础上，设计了案例调整算法，并给出一个通用的案例调整框架。最后，使用上述案例调整技术，对钢铁生产的动态调度实例进行了求解，仿真结果验证了该技术在解决复杂的案例调整问题上的有效性和柔性。     

通用雷达装备模拟训练系统及其关键技术研究

针对当前模拟训练系统功能单一、型号专用、开发效率低、水平参差不齐等问题，提出了基于PLSE（Product Line Software Engineering）理论的仿真平台概念、通用雷达装备全任务模拟训练系统概念和面向领域的研究方法。建立了外观模型、机理模型、人机交互模型、训练评估模型和系统结构模型的模拟训练系统模型体系，基于此提出了模拟训练系统的四种典型模式。攻克了全任务模拟训练系统研发中的四项关键技术：①提出并实现了面向维修案例的故障建模、仿真和评估方法；②采用USB（Universal Serial Bus）技术建立了基于实装专用部件的人机交互设备通用设计方法；③应用分布仿真高层体系结构HLA／RTI解决了模拟训练系统中的紧耦合交互问题；④建立了基于组件技术的模型规范和软件体系结构，实现组合式的仿真应用构建模式。最后介绍了针对通用雷达装备领域构建的仿真平台和一种虚拟式全任务模拟训练系统。     

数据驱动的大群体应急决策公众专家动态协同方法

针对大群体应急决策中环境复杂多变及公众参与度较低的问题，提出一种数据分析驱动的大群体应急决策公众专家动态协同方法。首先，通过对社交媒体平台中的文本数据进行情感分析，分别从属性层和综合层评价大群体应急决策质量；其次，根据属性层决策质量提出了属性权重动态更新规则；然后，在社会网络环境下基于综合决策质量及专家偏好与群体偏好的距离动态更新专家间的信任关系，并使用改进PageRank算法计算专家权重；最后，通过某飞行器事故的案例应用和对比分析验证了所提方法的有效性和优越性。     

高速公路经济带吸引区域与开发模式研究

本文根据区域经济的点轴开发理论和生长轴理论以及交通系统工程方法，研究了高速公路经济带的吸引区域、吸引半径等问题；在此基础上，对我国高速公路经济带的组成结构进行了案例分析，计算了合宁高速公路吸引半径和吸引区域，论述了高速公路经济带开发的三种模式。     

有向最短哈密尔顿路问题的DNA算法

首次提出了基于分子生物技术的有向最短哈密尔顿路问题的DNA (deoxyribonucleicacid)算法 ,将顶点、权值用DNA片段编码 ,边的方向通过顶点的编码获得。将这些DNA片段放入溶液中进行生化反应 ,通过基本的生物操作及生物酶完成解的产生及最终解的分离。该算法的创新之处在于权值的设计 ,合理有效地用DNA序列表示权值的大小 ,以便于使用常规的生物分离方法进行最优路径的选择。依据分子生物学的实验方法 ,说明了所提算法是有效和可行的。     

利用多群体DNA遗传算法求解线性规划问题

针对经典遗传算法存在的问题 ,提出了多群体DNA遗传算法。该方法在经典遗传算法的基础上 ,通过借鉴生物学及社会学 ,引入了多群体及DNA片断等概念 ,并提出迁移与自适应变异算法 ,可以提高遗传算法的有效性与收敛性。为了验证算法的有效性 ,将该算法应用于线性规划问题的求解。在求解过程中 ,首先利用熵障碍对偶方法对原问题进行转换 ,然后使用多群体DNA遗传算法对转换后的目标函数进行求解。仿真结果表明 ,该方法具有良好的全局搜索能力和较快的收敛速度。以上工作为解决大规模线性规划问题的求解提供了全新的思路和方法 ,对遗传算法应用的发展具有重要意义     

图论中的DNA计算模型

基于生化反应机理的DNA计算模型受到科学领域内许多不同学科学者们的关注。DNA计算已经形成国际科学前沿领域内研究的一个新的热点。主要介绍了近几年国内关于图论的DNA计算模型研究的现状及研究进展。分析了图论的DNA计算模型中存在的问题。指出未来国内DNA计算研究的重点可以在三个方面:解的检测,降低空间复杂度,生化实验研究。     

DNA计算研究概述与分析

基于生化反应机理的DNA计算模型受到科学领域内许多不同学科学者们的关注。DNA计算已经形成国际科学前沿领域内研究的一个新的热点。主要介绍了Sticker模型的应用及布尔电路的仿真应用,并分析了DNA计算模型中存在的问题。最后,简要介绍了DNA计算研究存在的问题及未来的研究方向。     

Job shop scheduling problem based on DNA computing

1 .INTRODUCTIONDNA is a high-molecular weight compound. Itsbasic composition includes one phosphate group,one deoxyribose sugar ,and one nitrogenous base .There are four kinds of nitrogenous bases :adenine(A) , guanine ( G) , cytosine ( C) , and thymine(T) . DNAis a double helix consisting of two sin-gle strand deoxynucleotide chains runningin an an-tiparallel configuration (Fig. 1) . After determi-ning the precise structure of DNA, many experi-mental methods have been invented inclu…     

赋权Hamilton路的DNA计算模型

DNA计算是一种基于生化反应的新型计算方式 ,目前已成为一个非常热门的研究领域。首先简单介绍了DNA分子的结构、计算机理及实现方式。然后 ,在Adleman工作的基础上 ,给出了赋权 (有向与无向 )型Hamil ton路问题的DNA计算模型。通过权值的转换方式 ,指出此模型对于任意实数权值的赋权图均适应。最后 ,指出了该模型存在的问题及进一步研究的方向。研究结果进一步证实了DNA计算的可行性。     

Pollard p-1因子分解的DNA计算机改进算法

如何有效地对大整数进行因子分解,是数学上的一个难题.RSA密码体制的安全性正是基于此困难问题.利用DNA计算机超大规模的并行运算能力和数据存储能力,提出一种基于分子生物技术的因子分解问题改进的DNA计算机算法.以因子分解的Pollardp-1算法为基础,设计了基于DNA计算的平方-乘算法以及求取最大公因数的欧几里得子算法,仿真实验结果表明了算法的可行性和有效性.     

一种改进的基于样本块的图像修补方法

图像修补技术一直被广泛地用于重建旧照片和移除一些在图片背景中不想要的物体。提出了一种新的图像修补方法,该方法基于样本的图像修补思想。我们的方法通过合理的信心度和数据条件的计算方法改进了图像修补的有效性和增强图像中线性结构扩散。因此,用本方法进行图像修补时,能有效地避免其他算法共同存在的"垃圾物"的生成问题。实验结果表明,与其他类似方法相比,本方法能够得到更令人满意的视觉效果。     

基于随机网格的位置隐私保护方法

针对当前已有的基于位置服务隐私保护技术在用户较少的情况下很难保障用户隐私保护级别的情况,借鉴网格计算和密码学理论,提出了一种改进的位置隐匿方法。该方法利用随机变化的网格区域,在移动节点之间进行简单位置计算并实时进行用户位置更新,通过移动终端和匿名服务器之间的协同计算完成位置隐匿。最后,通过理论分析阐述了该方法所具有轨迹不可追踪性和身份不可关联性等特点。同时,仿真实验进一步表明该方法的计算复杂度和通信复杂度满足位置服务中的即时通信的要求。     

基于冲突合作关系的生鲜选址-路径多主体优化模型与算法

针对城市生鲜农产品配送成本高，产品损耗大等特点，考虑生鲜销售商和外包冷链配送公司共同参与又独立决策的实际运营情况，建立了基于冲突合作关系的生鲜配送选址-路径多主体优化模型.模型中，考虑客户模糊时间窗，主导层生鲜销售商以系统总成本最低为目标，而从属层冷链配送公司仅考虑运输相关成本最小化.设计了GAPSO混合算法求解该问题，结合精英选择策略和自适应权重粒子更新策略，采用田口分析法获取参数合理取值.与CPLEX求取小规模算例精确解对比，GAPSO算法在保持准确性的同时，求解时间降低了96.17%；对基于Barreto和Prins经典LRP基准案例集的中大规模算例，与HybridGA算法和已知最优解BKR对比分析，结果表明GAPSO对于中小规模问题，能很好的收敛于全局最优解，对于大规模问题能求得近似最优解，能为实际生鲜选址和配送问题提供有效决策支持.