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

利用DNA粘贴模型的巨大并行性,从图顶点着色问题的本质出发,先把着色问题分解成顶点独立集问题和顶点划分问题并给出这两个问题的DNA粘贴算法,然后调用这两个算法解决了图顶点着色问题。实例证明DNA粘贴算法在理论上可以实现的。     

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

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

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

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

有向网络上单源多汇的最优连接问题

以信息需求系统为背景,研究有向网络上从一个顶点到若干顶点的连接方式,使总的连线长度为最小.这是最短路问题的推广,使用的方法是基于组合最优化的算法分析,包括NP-困难性及多项式可解情形.关于后一方面,若干约化规则起着重要作用.主要结果是得到序列平行图等典型图类的有效算法和一般图的启发式算法.目前的工作是为处理这样一个难解问题提供了一个基本的途径.更多的结构性质及典型算法值得进一步研究.     

求解度约束最小生成树的快速近似算法

针对带有度约束的最小生成树问题,给出了一种快速近似算法.首先给出了快速近似算法的核心思想:在不违反度约束和不形成圈的前提下,每次加入权最小的边.其次给出了实现快速近似算法的具体步骤,并且证明了该算法的计算时间复杂度是图的顶点数的多项式函数,证明了算法的有效性定理.大量的数值试验表明该近似算法性能良好.最后在此算法的基础上,给出了求解TSP问题的一种快速近似算法.     

占线顶点覆盖问题的结构性下界

在实际 顶点覆盖选址过程中,经常会遇到如下的情形:在需要服务的边的个数未知的前提下,决策者需要决定在哪里建立初始的设施(或设施集),同时还要求,当新的设施建立后,前面已经建立的设施不能被删除.以往一般建立的模型和算法都是针对静态选址而言的,这里需要的是满足上述约束的动态选址模型.考虑了占线顶点覆盖问题,给出了一个不需要任何复杂性假设条件下的结构性的下界结果,并通过对一个限制性条件下的占线顶点覆盖问题给出算法并证明竞争性能比结果说明了所作的下界分析是紧的,同时证明了所给出的算法在非多项式时间内是最优的.     

基于最小不连续的分块相位解缠算法

相位解缠是干涉合成孔径雷达(interferometric synthetic aperture radar, InSAR)和干涉合成孔径声纳(interferometric synthetic aperture sonar, InSAS)数据处理中极其关键的步骤。针对大块干涉图的解缠效率低下的问题,提出了一种基于最小不连续的分块相位解缠方法。首先根据干涉相位图计算相位质量图,并按照质量阈值将干涉相位图分成高、低质量区域|然后将大块干涉图分成规则小块干涉图,采用带权重的最小不连续相位解缠算法同时对小块干涉图进行相位求解|最后在不同子数据解缠相位块的高、低质量区域之间进行最小不连续优化,求解最终解缠相位,并以并行编程标准OpenMP为基础对分块解缠算法进行了并行化。通过对InSAR和InSAS干涉图的解缠实验验证了分块相位解缠算法的正确性和高效性。     

基于粘贴DNA芯片模型的八皇后问题算法

提出了粘贴 DNA 芯片模型,该模型综合了粘贴模型的筛选功能和 DNA 芯片模型的检测功能.利用这两个特点设计了基于粘贴 DNA 芯片模型的求解八皇后问题全部解的 DNA 算法.该算法首先产生所有可能的解,再分别按照行要求,列要求和对角线要求逐步筛选出八皇后问题的全部解.利用 DNA 芯片检测出实验结果,然后对每个实验步骤分析了算法的生化实现过程并得到了八皇后问题的全部解.最后讨论了算法的复杂性及其优势.     

边连通度问题的三维DNA图结构解法

针对求边连通度这一难解问题,提出了三维DNA图结构算法。该算法利用k臂DNA这一特殊的分子结构构建了相应的图结构,通过相关的限制性内切酶处理和凝胶电泳分析来确定图的边连通度。通过探讨算法的可行性,基于目前的实验室技术给出了算法的具体分子生物学操作步骤。指出这一DNA结构可直观地反映图结构,易于建立图论模型。结论显示,该算法可以直观有效地求解边连通度,用于解某些难解问题有着特殊的优越性。     

网络中的最优控制树问题

众所周知,从通讯网络建设中提出著名的最优支撑树问题,即在一个赋权连通图中求一个包含所有顶点而权(费用)最小的连通子图(支撑树).进而,在交通、通讯、供销系统的干线设计中,考虑的连线(干线)不一定连接网络的所有顶点,但被连接的顶点必须构成一个控制集,即其余任一顶点都有一条边直接与此主干部分相连.这就提出了最优控制树问题.似乎此问题与最优支撑树问题十分类似,但我们将证明它是NP-困难的,并给出一个分枝定界算法及相关性质.     

ON THE INVERSE MINIMUM SPANNING TREE PROBLEM WITH MINIMUM NUMBER OF PERTURBED EDGES

Let G=be a network with the vertex set V,the edge set E and the length vector L, andlet T~* be a prior determined spanning tree of G. The inverse minimum spanning tree problem withminimum number of perturbed edges is to perturb the length vector L to L+δ, such that T~* is one ofminimum spanning trees under the length vector L+δ and the number of perturbed edges is minimum.This paper establishes a mathematical model for this problem and transforms it into a minimumvertex covering problem in a bipartite graph G_0, a path-graph. Thus a strongly polynomial algorithmwith time complexity O(mn~2) can be designed by using Hungarian method.     

最优指派问题DNA算法

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

武器-目标分配问题的粒子群优化算法

建立了武器-目标分配问题的优化模型,分析了各种解决此模型的方法的优缺点。经典的粒子群是一个有效的寻找连续函数极值的方法,结合遗传算法的思想提出粒子群算法来解决武器-目标分配问题。经过比较测试,4种粒子群算法的效果都比较好,特别交叉策略A和变异策略B的混合粒子群算法是最好的且简单有效的算法。     

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

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

New Hybrid Genetic Algorithm for Vertex Cover Problems

This paper presents a new hybrid genetic algorithm for the vertex cover problems in which scan-repair and local improvement techniques are used for local optimization. With the hybrid approach, genetic algorithms are used to perform global exploration in a population, while neighborhood search methods are used to perform local exploitation around the chromosomes. The experimental results indicate that hybrid genetic algorithms can obtain solutions of excellent quality to the problem instances with different sizes. The pure genetic algorithms are outperformed by the neighborhood search heuristics procedures combined with genetic algorithms.     

两层广义线性规划

给出二层广义线性规划最优解极点可达性的一个充分条件 .此外 ,利用容许集的极点与下层问题可行集的极点间的关系给出“第 k最好”算法的一种快捷、方便的实现 .算例表明算法是有效的 .