基于闭环DNA计算的最大独立集问题的算法

提出闭环DNA计算模型及其基本生化实验,给出解决最大独立集问题的闭环DNA算法。在闭环DNA算法中,提出并实现了用删除实验直接构造所有最大独立集的构想,即通过多次删除实验使顶点集合逐步满足独立集的要求,最后达到最大独立集。该方法使得算法的设计简单明了。算法仅用到基本的删除实验,实现简捷、可靠。     

基于闭环DNA模型的八皇后问题算法

给出了闭环DNA计算模型及其基本生化实验,提出了基于闭环DNA的求解八皇后问题全部可行解的DNA算法,分析了算法的实现步骤及其实现方式并得到了全部的可行解。最后讨论了算法的复杂性。     

基于邻接矩阵的网络流量检测点设置算法

在研究网络流量的有效测量问题时,考虑网络节点的流守恒,把网络流量监测点问题抽象为无向图的最小弱顶点覆盖问题,这是一个NP难的问题.基于图论中邻接矩阵的概念,提出一个近似算法,通过重复删除邻接矩阵中所有行元素之和不超过1的节点对应的行和列,得到最小弱顶点覆盖集.在此基础上通过预先递归去除无向图中1度节点,满足任意节点度数都大于或等于2的最小弱顶点覆盖问题求解条件,并将递归节点作为该近似算法的入口点.仿真实验表明,与现有算法相比,新算法具有更好的性能,能够发现更小的弱顶点覆盖集.     

一种求解平面图的最小顶点覆盖算法

最小顶点覆盖问题是图论中经典的组合优化问题,在实际生活中有着广泛的应用价值。根据最小顶点覆盖与最大独立集在图论中事实上是属于等价问题这一特性,从最大独立集的角度出发,根据最大独立集的特性,设计了一种求解简单平面图的最大独立集算法,从而求出最小顶点覆盖。通过实验结果的比对验证算法的正确性和有效性。     

排课表问题的闭环DNA计算模型的算法

排课表问题是NP-完全问题。基于闭环DNA计算模型引入多种生化实验得出求解排课表问题的DNA算法。本算法采用两部编码方式产生初始数据池,引入批删除实验解决了教师和班级的冲突问题和同班课问题;引入批分离实验解决了正常合班课问题和教师时间要求问题;引入电泳实验解决了排课的均衡分配问题;引入标记实验得到了排课表问题的全局最优解集,并给出了算法的生化实现过程。最后,对算法的正确性进行了证明,并讨论了算法的复杂性。     

基于原始对偶方法求解网络流量监测集算法

考虑网络节点的流守恒特性,网络流量的有效监测问题可抽象为求给定图G(V,E)的最小弱顶点覆盖集的问题和基于流划分的最小弱顶点覆盖集的问题,这是NP难的问题.首先分析了弱顶点覆盖集的约束关系,并给出了问题的整数规划形式.然后利用原始对偶方法构造了求解最小弱顶点覆盖集的近似算法,并分析了算法的比界为2.进一步分析了求解基于最大流划分的最小弱顶点覆盖集的近似算法.     

一种增量式约简方法求解最小顶点覆盖问题

最小顶点覆盖问题是一个应用很广泛的NP难题,针对该问题给出一种增量式属性约简方法。首先将最小顶点覆盖问题转化为一个决策表的最小属性约简问题;利用增量式属性约简思想,随着图中边数的增多,提出一种更新最小顶点覆盖的增量式属性约简算法;该算法时间复杂度低于计算整个图的最小顶点覆盖的时间复杂度,同时针对大规模图问题,可随着边的增加动态更新最小顶点覆盖,因此降低了属性约简的方法求解最小顶点覆盖问题的运行时间;实验结果表明该算法的可行性和有效性。     

赋权图上优化问题的DNA计算方法研究(英文)

对赋权图上经典优化问题的DNA计算方法进行探讨,改进原有DNA计算模型中的权值编码方法,提出一些新的DNA编码方法及DNA算法．具体地说,通过设计赋权无向图的相对长度图给出了旅行商问题的一种相对长度DNA编码方法及DNA算法,通过设计赋权无向图的广义边图给出了中国邮递员问题的一种广义边图DNA编码方法及DNA算法,通过选取DNA序列的最佳逆补比对给出了最小生成树问题的一种基于逆补比对的DNA编码方法及DNA算法,通过设计从顶点覆盖问题到Hamilton回路问题的一种改进多项式变换给出了顶点覆盖问题的一种基于多项式变换的DNA编码方法及DNA算法．所设计的DNA计算方法提高了DNA计算中表示数值和处理数值的能力．     

图的最小顶点覆盖问题的DNA表面计算模型

基于生化反应原理的DNA计算具有强大的并行运算能力,DNA计算机在求解NP问题上存在着硅计算机无法比拟的先天的优越性。采用荧光标记的策略,给出了一种新的图的最小顶点覆盖问题的DNA表面计算模型。该模型首先将问题解空间的DNA分子固定在固体载体上,然后通过进行相应的生化反应来求得图的最小顶点覆盖问题的所有解。新算法利用荧光猝灭技术,通过观察荧光来排除非解,具有编码、解读简单和错误率低的特点。     

最小顶点覆盖快速降阶算法

通过定义判别函数来判别顶点覆盖作用的优劣,得出一个把顶点加入到最小顶点覆盖集的一般化规则,并得出该规则在多种具体情况下的应用定理,在此基础上给出了一个快速降阶算法,该算法能确定某些顶点应该在最小顶点覆盖中,某些顶点不应该在最小顶点覆盖中,达到降低原问题的规模和求解难度的目的.该算法既可以单独使用,又可以与算法结合来达到更好的结果,文中还给出了应用实例及其分析.     

基于闭环DNA的指派问题算法

给出了闭环DNA计算模型及其生化实验。用闭环DNA计算模型设计出了指派问题的DNA算法。首先对决策变量进行二维DNA编码来存放决策变量和效益值,然后通过有目的的终止技术和删除实验得到指派问题的全部可行解,最后通过电泳实验和检测实验获得最优指派问题的最优解。举例说明了算法的可行性。最后,为减少DNA编码数量和缩短DNA编码的码长,讨论了算法的两种改进方法。     

基于最小/最大描述的多粒度覆盖粗糙直觉模糊集模型

覆盖粗糙集和直觉模糊集都是处理不确定性问题的基础理论,它们有着很强的互补性,且覆盖粗糙集和直觉模糊集的融合研究是一个新的热点。对多粒度覆盖粗糙集和直觉模糊集的融合进行深入研究。首先将最小描述、最大描述从单一粒度推广到多个粒度,提出了多粒度的最小描述和最大描述,讨论了多粒度的融合;其次,分别给出了基于最小描述和最大描述的模糊覆盖粗糙隶属度、非隶属度的概念,构建了两种新的模型即基于最小描述的多粒度覆盖粗糙直觉模糊集和基于最大描述的多粒度覆盖粗糙直觉模糊集,并讨论了它们的性质,同时举例说明;最后,分析和研究了两种模型的关系。该研究为多粒度覆盖粗糙集和直觉模糊集的融合提供了一种方法。     

部分二值逻辑中Sheffer函数的构造与判定算法

在深入研究部分二值逻辑中Sheffer函数的基础上,根据部分二值逻辑中准完备集的最小覆盖,提出了一种高效地构造部分二值逻辑中Sheffer函数的算法,此算法能够构造出部分二值逻辑中的全部Sheffer函数,在构造算法的基础上,进一步提出了一种部分二值逻辑中Sheffer函数的判定算法,此算法和传统判定算法相比,避免了繁琐的计算,可以说是一种较简单的判定算法。     

覆盖多粒度粗糙集的数值特征

通过极大描述和极小描述获取的覆盖多粒度粗糙集,可以更好地应用于实际.首先通过极小描述和极大描述的交并运算定义4个悲观覆盖多粒度粗糙集模型,并讨论其基本性;在此基础上进一步分析其证据结构,并得出覆盖多粒度粗糙集具有信任结构的充分条件,即上、下近似满足对偶性、可加性和可乘性.通过上述研究,进一步丰富了多粒度粗糙集的研究.     

一种求解极小诊断的遗传模拟退火算法

基于模型的诊断方法是人工智能领域发展起来的一个十分活跃的分支.在该方法中,由极小冲突集求解极小击中集的过程是一个NP-Hard问题.尽管人们提出了不少算法,但是各种算法的效率仍然不是十分理想.通过将该问题映射到0/1整数规划问题,提出了将遗传算法与模拟退火算法相结合的问题求解思想.在给出遗传模拟退火(genetic simulated anncaling,简称GSA)算法和算法各个参数的同时,对算法的性能和求解精度进行了测试.GSA算法不仅比传统的算法效率有很大的提高,而且在冲突集基数大于35的情况下,较单独使用GA的算法在效率上提高约1/3～1/2.在求解精度上,GSA算法在大多数情况下能够求出98%～100%的极小诊断.     

基于商空间粒度的覆盖聚类算法*

介绍了覆盖算法的基本思想,给出了商空间粒度的基本原理,提出了基于商空间粒度的覆盖聚类算法.通过实验验证了该算法的有效性和可行性,它适合处理大规模的数据样本.     

控制系统的满意优化效用理论研究及应用

提出了满意优化不同于传统优化的基本特点,并依此建立了控制系统参数设计的满意优化模型.由所建立的效用函数及其期望,设计了效用函数下的满意优化算法,并进一步探讨了文中所设计的效用函数具有有界闭凸性及其在可测非负实值函数下的基本运算性质,为该算法的应用推广提供了理论基础.单回路控制系统下的仿真算例数据表明,效用函数下的满意优化算法具有良好的收敛性.