用模拟退火算法求解有顺序约束指派问题

首先对有顺序约束指派问题进行分析.接着把这一特殊的指派问题用有向无回路图表示出来,从而使指派问题的求解转化为求解有向无回路图的划分问题.针对划分问题,构建了一种特殊的邻域结构,并设计出基于此邻域结构的模拟退火算法.最后,通过一个实例对算法的关键环节进行演示,通过另一个实例把模拟退火算法同禁忌搜索算法进行比较,结果表明该算法能够有效解决此类问题.     

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

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

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

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

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

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

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

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

基于全条件独立的贝叶斯网络MPD-JT构造算法

针对求解贝叶斯网络最大主子图存在的NP(non-deterministic polynomialtine)难问题,提出了一种基于全条件独立结构的最大主子图连接树（maximal prime sub graph decomposition junction tree, MPD-JT）构造算法。该算法通过道义图上的全条件独立结构得到贝叶斯网络最大主子图,并利用构成这些最大主子图的节点作为簇节点构造连接树,避免了三角化过程,而且在求解过程中通过删除一些符合条件的点,大大降低了算法复杂度。给出了算法的理论证明,通过具体案例分析验证了算法的有效性。     

城市交通连续平衡网络设计问题的模拟退火算法

对城市交通连续平衡网络设计问题作一简要介绍。建立该问题的双层规划模型。针对该问题．构建一种特殊的邻城结构．并设计出基于此邻城结构的模拟退火算法。通过一个实例对算法进行验证．并同其他算法进行比较．结果表明模拟退火算法的计算结果较精确．但相应的计算量增加。但该算法用于大型网络设计问题时．其优势则会有明显体现。     

最优指派问题DNA算法

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

最短路问题的闭环DNA算法

提出了不等长闭环DNA分子的概念,由此推广了闭环DNA计算模型。给出了固定端点的最短路问题闭环DNA算法,该算法首先对每条弧进行了三组DNA编码,再用有目的的终止技术合成固定端点的所有链,然后通过接入实验和电泳实验得到最短路,并通过检测实验输出所有最短路径。得出了算法的复杂性,为说明算法的有效性给出了一个算例。最后讨论了最短路问题闭环DNA算法在变权网络、自由终点或固定中间点的最短路问题中的应用,并给出了相应的解决方法。由此说明该算法具有广泛的适应性。     

0-1规划问题的闭环DNA算法

提出了闭环DNA分子的结构灵活性的两个方面,即DNA分子链长的可控性和DNA分子之间的相互转化。针对非负整数系数的0-1规划问题,提出了闭环DNA算法。该算法首先对0-1变量按照0和1的取值、对应的各项系数和检测标记进行五组DNA编码并形成所有可能解;再利用接入实验、电泳实验和删除实验筛选出可行解,进而得到所有最优解;最后通过检测实验输出实验结果。给出了算法的正确性的证明并讨论了算法复杂性,给出一个算例说明了算法的有效性。对算法进行了改进,改进后的算法适用于可以含有负数的实数系数0-1规划问题。     

THE CONNECTIVITY OF MAXIMUM MATCHING GRAPHS

The maximum matching graph of a graph has a vertex for each maximummatching and an edge for each pair of maximum matchings which differ by exactly oneedge. In this paper, we prove that the connectivity of maximum matching graph of abipartite graph is equal to its minimum degree.     

EDGE RECONSTRUCTION OF PLANAR GRAPHS WITH MINIMUM DEGREE AT LEAST THREE-(Ⅰ)

The object of this series of papers is to show that every planar graph ofminimum degree at least 3 is edge reconstructible. In this paper, we prove that such agraph with connectivity 2 is edge reconstructible.     

赋权Hamilton路的DNA计算模型

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

基于图论的制冷系统稳态仿真算法的构建

系统算法的构建是制冷系统稳态仿真的重要环节。本文在传统的连续替代算法的基础上，引入图论方法实现制冷系统仿真算法的自动构建。首先，将制冷循环表示为图的数据结构：然后，采用图论的广度遍历算法构建制冷循环的仿真算法；最后，引入模块化的部件模型完成系统仿真。仿真实例显示本文方法具有良好的通用性和稳定性。本文方法亦可适用于其他热力系统仿真算法的构建。     

Degree Distribution of Evolution Networks with Acceleration of Edge Attachment

Recent studies show that the topologies of complex networks can be categorised into three catalogues: random graph model, small-world model, and scale-free model. The main reasons for the emergence of the three different models are the differences of edges' connectivity and vertexes' increasing modes in the evolution of the complex networks. According to the measured data of the real-world complex networks, the range of power-law exponent of those networks is [2, 3]. However, the range of the theoretical results that have been obtained is [2, +∞). A new edges' connectivity mode with the acceleration of edge preferential attachment is proposed in this article. And using the master equation approach, the exponent of power law in the mode is presented. Theoretical analyses and simulation results indicate that the exponent of power law is adjusted in the range from 2 to 3 with the proper connectivity acceleration.     

基于三维体质心的无线传感器网络节点定位算法

针对无线传感器网络中传感器节点初始位置未知的问题,提出一种基于三维体质心的分布式无线传感器网络节点定位算法.算法假设网络中有一定比例的锚节点(位置已知的节点),利用三维辅助坐标系,建立节点间的通信约束关系和空间几何关系,研究三维空间内包含未知节点的三维体构成方法,确定三维体的多个侧面和曲面来构成曲面三维体;为了减小算法计算量和网络能耗,寻找与曲面三维体对应的由多个侧面组成的平面三维体,通过确定平面三维体的质心来获得曲面三维体质心,从而把曲面三维体的质心作为未知节点的估计位置.该算法是一种完全基于网络连通性的分布式算法,算法设计简单,计算量小,节点间通信开销少.仿真结果显示,该算法适合于各种规模的无线传感器网络的节点定位.     

用混合遗传算法求解图的邻强边着色问题

图的邻强边着色算法是一个NP完全问题。提出了图的邻强迫着色问题的混合遗传算法。在设计交叉、变异方式时,将两点交叉与局部扫描结合起来,避免了种群的退化,从而有利于快速找到最好的解域。根据实际情况,将图的结构性质和迭代次数结合起来,巧妙地设计了算法的终止条件。实验仿真结果表明,混合遗传算法可以获得问题高质量的解,即对图进行邻强边着色所使用的颜色数接近图的邻强边色数。     

受限p-中心的并行迭代算法

提出了受限 p-中心的多项式时间并行迭代算法 ,分析了这些算法的计算复杂性 .计算实例表明所提出的算法简洁有效 .本文的算法还可以对其它关于受限 p-中心及 p-中心的启发式算法和近似算法进行补充 ,以此为基础容易获得相应的 Tabu Search算法和遗传算法 .     

Simulated annealing algorithm for detecting graph isomorphism

Evolutionary computation techniques have mostly been used to solve various optimization problems, and it is well known that graph isomorphism problem （GIP） is a nondeterministic polynomial problem. A simulated annealing （SA） algorithm for detecting graph isomorphism is proposed, and the proposed SA algorithm is well suited to deal with random graphs with large size. To verify the validity of the proposed SA algorithm, simulations are performed on three pairs of small graphs and four pairs of large random graphs with edge densities 0.5, 0.1, and 0.01, respectively. The simulation results show that the proposed SA algorithm can detect graph isomorphism with a high probability.     

模拟大脑皮层结构和功能连接的神经网络研究

为了模拟动物大脑皮层结构连接与功能连接间的关系，为机器学习提供新的思路，本文用图论测度表示网络的结构，用信息论测度表示功能整合和功能分离间的相互作用，采用图选择的方法对随机图进行变异和选择，确定与特定的功能动力学模式相对应的网络结构，并研究在外界刺激信号作用下，系统连接与感觉层间的匹配关系。仿真结果表明：由图选择获得的网络结构，呈现若干密集的顶点区，区域间松散连接，具有功能分离与功能整合的特点。在外界信号刺激下，特定的结构模式可以使系统与感觉层信号的统计结构间达到最大程度的匹配。