案例分析中的DNA计算

DNA计算是一种模拟生物分子DNA的结构并借助于分子生物技术进行计算的新方法，开创了以化学反应作为计算工具的先例，为解决NP—完全问题提供了一种全新的途径。案例分析中常用到离散数学中的逻辑演算，特别是在信息处理方面。在基于表面的DNA计算中采用了荧光标记策略，解决了案例分析中的一个问题，尝试了DNA计算在案例分析中的应用。且这种方法具有编码简单；耗材底；操作时间短；技术先进的优点。     

基于关联规则分析的组合拍卖竞胜标决定算法

组合拍卖竞胜标确定问题(WDP)是一个NP-完全问题,其算法研究一直是运筹学、人工智能和计算机科学等领域持续关注的热点.本文提出基于关联规则数据挖掘技术的组合拍卖竞胜标算法,并通过与经典的WDP精确算法和近似算法的比较,证明了该算法的有效性,为组合拍卖WDP算法提供了新的研究思路和方法.     

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

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

赋权Hamilton路的DNA计算模型

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

基于微粒群算法的虚拟仪器参数自适应配置方法

提出了一种利用微粒群算法优化虚拟仪器参数设置的方法。微粒群算法通过模拟鸟类社会性运动的规律,利用群体智能解决组合优化问题,该算法能够迅速有效地进行最优化搜索。将其用于解决仪器参数设置中的多维空间优化问题,具有概念简单,应用方便,计算复杂性低和运算速度快的特点。     

最小顶点覆盖问题的DNA分子算法

最小顶点覆盖问题是找给定图G中覆盖每条边的最小顶点子集,这个问题即是一个著名的NP 完全问题。给出了基于分子生物技术的图的顶点覆盖问题的DNA算法。算法的关键是数学问题到DNA链的映射,对图中的顶点进行恰当的编码,以便于使用常规的生物操作及生物酶完成解的产生及最终解的分离。依据分子生物学的实验方法,提出的算法是有效和可行的。最后指出了该算法的优点、存在问题及下一步的研究方向。     

生产流水线上允许返回作业的一维机器配置问题

在现代制造系统中,大量地采用了流水线作业以提高劳动生产率,其中一维机器配置问题在此起着非常重要的作用。本文探讨了生产流水线上允许返回作业的一维机器配置问题。由于该问题是一个NP-完全组合优化问题,随着问题规模的扩大,往往难以求得最优或满意的机器配置方案。本文提出一种新的遗传算法用以求解这种机器配置问题,数值分析表明所构造的遗传算法对求解这类组合优化问题上是有效的。     

三维几何模型分解及其应用技术综述

三维几何模型分解是对模型的几何和拓扑信息作进一步处理的基础,在计算机图形学,计算机辅助几何设计和数字几何处理等方面有着广泛的应用,是当前的热点研完领域.模型分解的优化问题可等价转化为使分割边数目最小的图划分NP-完全问题.概述了模型分解的原理,属性和应用,系统地介绍了这一领域的工作成果并进行了分类,分析了各方面典型算法的优缺点,最后展望了这一技术的发展前景.     

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

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

基于自组装DNA计算的RSA密码系统破译方案

自组装DNA计算在解决NP问题,尤其是破译密码系统方面,具有传统计算机无法比拟的优势。采用DNA分子瓦编码信息,借助于分子瓦之间的粘性末端进行自组装,给出了乘法运算的实现方案。在此基础上,通过引入非确定性的指派分子瓦,提出了一种用自组装DNA计算破译RSA公钥密码系统的非确定性算法。通过创建数以亿计的参与计算的DNA分子瓦,在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…     

最优指派问题DNA算法

对求最小值的最优指派数学模型,设计并实现了DNA计算算法。首先经过特殊的DNA编码将二维的决策变量和二维的效益值编入DNA序列中;然后通过杂交实验和分离实验得到指派问题的全部可行解;最后通过电泳实验和检测实验获得最优指派问题的最优解。证明了算法的复杂性并举例说明了算法的可行性。分别给出了求最大值的最优指派问题和人数与工作数不等的最优指派问题的处理方法。     

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

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

四色和K色图着色问题的瞬态混沌神经网络解法

首先给出了用神经网络求解四色图着色问题的神经网络结构和能量函数 ,然后采用了具有瞬态混沌特性的神经网络 ( TCNN)来解四色图着色问题 .由于引入具有复杂动态特性的瞬态混沌使得该法具有很强的搜索全局最优解的能力 .仿真结果表明 ,用该法解四色图着色问题总能保证使能量函数收敛到最优解 ,有效避免了用传统的 Hopfield人工神经网络 ( HNN)解此问题时极易陷入局部极小的缺陷 ,并且收敛速度更快 .另外我们还用此法求解了属于 NP-完全问题的 K色图着色问题.     

Genetic algorithm for pareto optimum-based route selection

A quality of service (QoS) or constraint-based routing selection needs to find a path subject to multiple constraints through a network. The problem of finding such a path is known as the multi-constrained path(MCP) problem, and has been proven to be NP-complete that cannot be exactly solved in a polynomial time. The NPC problem is converted into a multiobjective optimization problem with constraints to be solved with a genetic algorithm. Based on the Pareto optimum, a constrained routing computation method is proposed to generate a set of nondominated optimal routes with the genetic algorithm mechanism. The convergence and time complexity of the novel algorithm is analyzed. Experimental results show that multiobjective evolution is highly responsive and competent for the Pareto optimum-based route selection. When this method is applied to a MPLS and metropolitan-area network, it will be capable of optimizing the transmission performance.     

精英遗传改进的非线性灰色神经网络算子与军费开支多目标组合预测应用

军费开支属于复杂经济系统下具有宏观经济特征的一类非线性时间序列。在多目标组合下的军费开支预测问题研究背景下,提出了一种基于精英遗传算法(elite genetic algorithm,EGA)改进的非线性灰色神经网络计量组合预测模型,给出了总体建模思路与非线性灰色神经网络算子分系统和EGA分系统设计方法,解决了多准则目标优化的NP完全问题,并对模型的预测效果进行比较分析。采集美国27年间(1990-2016年)军费开支时间序列进行实证检验,分析结论认为非线性灰色神经网络算子能够有效提高模型精度,EGA算法在收敛速度与精度上优于标准遗传算法,采用所建立的预测模型进行军费开支预测精度更高,效果更好。     

基于蚁群算法的序贯决策问题研究

实际工程中存在许多大规模、非线性多约束的序贯决策问题,传统算法解决起来较为困难.蚁群系统(ACS)是一个用来解决大规模多约束组合优化问题的现代启发式算法,根据序贯决策的特点设计了多层结构的蚁群系统,给出了算法的组成结构;为了节约计算内存和优化时间,详细阐述了淘汰劣质解机制的精英策略;并通过梯级水电站短期优化调度这一实际工程序贯决策问题,来验证所构造的算法,给出了优化调度的数学模型及算法的求解思路.最后,采用我国西南地区某梯级流域中三个水电站的相关数据建立了调度仿真模型,仿真结果证实了所采用算法的有效性和可行性.     

基于EGA算法的小样本非线性残差灰色Verhulst计量组合预测模型

针对复杂经济系统下时间序列所呈现出的小样本非线性残差特征,采用非线性残差灰色Verhuilst模型进行研究,修正传统计量模型对于残差信息挖掘不够,预测精度不高的问题,在此基础上,选择带有精英策略的EGA算法来建立灰色Verhulst计量组合预测模型,设计了算法实现的逻辑流程和非线性残差灰色Verhulst计量组合预测模型的整体建模思路,提出了改进多准则目标优化NP完全问题的新方法,对模型的预测效果进行比较分析.实证研究表明:基于EGA算法的小样本非线性残差灰色Verhulst计量组合预测模型算法收敛速度快,拟合效果好,预测结果更精确.