一种基于DNA自组装模型求解最大团问题的算法

基于tiles理论模型和已有DNA自组装模型,结合最大团问题给出基于DNA自组装模型的算法设计,得到具体设计初始分子、规则分子和检测分子所需的DAE块种类.在此基础上采用荧光标记和凝胶电泳生物操作提出了一种求解最大团问题算法.该算法设计tiles的种类为Θ(n2+|E|),其生物操作复杂性为Θ(1).此算法降低了实验的复杂度,而且保证了实验的易操作性和结果的准确性。     

最大团问题的竞争决策算法

分析了最大团问题的数学性质,根据推导出来的性质设计求解最大团问题的竞争决策算法,且算法的时间复杂度分析结果为O(n~3)。并用提出的算法求解最大团问题中的标准测试示例,测试结果表明,算法具有良好的求解效果。     

基于蚁群优化算法求解最大团问题的研究

蚁群算法是一种通过模拟自然界中蚂蚁觅食行为而发展而来的新型启发式仿生优化算法,提出至今被研究人员广泛应用于各种组合优化问题.最大团问题是图论中著名的NPC问题,本文对于基本蚁群算法进行了分析与讨论,针对基本蚁群算法的容易陷入局部最优解、收敛速度慢等问题进行了改进,提出了一种新型蚁群优化算法.本文提出的新型蚁群优化算法增加了结点度和历史选择次数表策略影响蚂蚁选点;另外提出了构造独立的局部信息素更新机制.最后通过对比实验验证,数据结果证明新提出的优化算法相对于基本蚁群算法的优越性和可行性.     

基于改进的粘贴模型求解图最大独立集的DNA算法

改进的DNA粘贴模型在解决SAT问题时所需的寡核苷酸片段数量有显著降低,对改进的粘贴模型做了进一步的改进,建立了图最大独立集的一种改进的DNA粘贴模型.首先将图的独立集问题转化为可满足性问题,然后利用本文改进的粘贴模型给出了图的最大独立集的DNA算法.最后通过一个实例给出算法实现并求出了最大独立集.     

对最大团问题的HEWN算法分析

对最大团问题的HEWN(hierarchicaledge-weightnetwork)算法进行了复杂性分析.首先通过分析HEWN的结构特点和所需进行的操作,设计了一种实现HEWN算法的数据结构,指出了在HEWN算法中HEWN的存储宜采用邻接多重表和二叉链表相结合的链表表示法,然后从HEWN的存储结构入手,剖析了HEWN的构造过程,在剖析过程中,通过与MCST(maximumcompletesub-graphtree)比较,指出了当2j>n时潜在的、指数的生成和修改GM的次数存在于HEWN算法中.因而,HEWN算法的时间复杂度是指数的,而不是O(n8.5).     

基于Spark的多策略蚁群算法求解最大团问题

社会网络分析目前是数据挖掘领域的研究热点之一,凝聚子群是测量社会网络结构的重要指标,而最大团结构是社会网络中最紧密的凝聚子群,最大团问题的研究也成为社会网络分析的一个重要角度.随着大数据的发展,图中节点的丰富性和边结构的复杂性对求解最大团问题提出了更高的要求.为此提出了一种基于Spark的多策略蚁群算法求解最大团的算法.首先,该算法利用多条件选点策略扩大搜索空间,增加可行解的多样性,避免了陷入局部最优解;然后,采取一个局部搜索策略来提高该算法的精度和收敛速度;最后,在Spark分布式平台上并行地实现了该算法,验证了算法的并行性,证明该算法提高了算法处理大规模社区网络的执行效率.     

基于分治策略和蚁群算法的最大团问题的研究

最大团问题是经典的NP-hard问题,对该问题求解方法的研究在理论上、实践上都具有一定的意义.蚁群算法已成功地求解出许多组合优化难题.通过使用分治法,将图分解成子图,对各子图应用蚁群算法求解,提出一种求解最大团问题的蚁群算法.它减小了问题的求解规模,使求解变得容易,且实验取得了较好的结果.     

一种求解最大团问题的化学反应算法

最大团问题是在给定的一个图中寻找一个顶点数最大的顶点子集S,使得S中任意2个顶点都相邻,是一个著名的NP完全问题.提出一种带有局部搜索策略的化学反应算法求解最大团问题.为了提高算法的性能,在化学反应算法的分子碰撞阶段引入分子亲和度,使得碰撞后的分子倾向于得到对应于最大团较大的分子.将不相交的Golomb尺问题转化为最大团问题实例,通过求解最大团问题,得到若干不相交的Golomb尺问题的新结果.     

最大团问题的三链DNA计算模型

本文研究利用三链DNA求解最大团问题。首先将最大团问题中的顶点编码为DNA片段,进行生化反应,组合成所有可能的情况,然后利用三链模型对解进行筛选,最终得到图的最大团。该模型降低了编码的复杂度,提高了检测效率,其他的NP(Non-deterministic Polynomial)问题也可用此方法来求解。     

最大团问题的可编程的DNA分子系统计算模型

DNA计算求解NP完全问题,可编程性、自主、高并行性,是十分重要的追求。文中主要借助可编程的DNA分子系统求解最大团问题。DNA自组装是通过起始双链体的诱发,由化学发夹和指令发夹杂交反应交错排列构成线性双链体,它的两条链一条由化学发夹组成,一条由指令发夹组成。通过DNA链置换反应,发生链的迁移,将可增长的低聚物转移到每个发夹上,组装顺序是通过成对的互补脚趾之间相互作用进行编程。最终检测线性双链体上低聚物的个数来读取图的最大团及其顶点。     

基于DNA粘贴模型求解最小集合覆盖问题

运用DNA计算模式中基于粘贴运算的粘贴模型求解最小集合覆盖问题.在粘贴模型中,用存储复合体来表示子集,并利用粘贴运算的巨大并行性,可以有效地求解最小集合覆盖问题.举例说明了基于DNA粘贴模型求解最小集合覆盖问题的过程.     

地图着色问题的粘贴DNA算法

提出多级分离的概念,给出一个多级分离装置的模型,并介绍粘贴模型中的多级分离操作、将地图着色问题转化为可满足性问题、基于粘贴模型的巨大并行性及多级分离的优势,提出解决该问题的粘贴DNA算法。通过一个实例给出实验操作步骤,并对生化反应过程进行模拟,得出具体的着色方案,从而证明了该多级分离装置的有效性以及该算法的可行性。     

遗传算法求解最大团问题研究

最大团问题是NP难解的,用遗传算法求解的关键是如何设计有效的评估函数.首先从理论上分析编码规则及适应函数对个体进化的影响,提出个体基因适应函数和个体适应函数多重评估方法,并设计求解算法.数值实验表明,算法具有较好的通用性和较高的性能.     

基于最大最小爬山算法的肺癌预后模型

利用最大最小爬山算法构建肺癌患者的预后模型,指导肺癌预后评价。以SEER(surveillance, epidemiology, and end results)数据库中2008年至2014年期间被确诊为肺癌的患者组成数据集,首先利用卡方检验、Logistic回归分析方法对数据集中的变量进行特征选择;然后,在训练集上利用最大最小爬山算法建立肺癌患者的预后模型,并在测试集上对患者进行5年后生存情况预测;最后,选择Logistic回归、人工神经网络、决策树、支持向量机方法和本研究模型在测试集上进行分类实验对比。最终结果显示本研究模型对肺癌患者5年后生存情况的预测准确率高于其他方法。     

基于Q0-1规划模型用分枝定界法求解最大团问题

搜索图的最大团是经典的NP-难题。通过运用二次0-1规划模型（简称Q0-1规划模型）寻得最大团问题的解法,所用的分枝定界法建立在此模型之上。通过一个命题推导出图的最大团求解问题与一类特殊Q0-1规划的等价性,借助于求解一般Q0-1规划的分枝定界法推演出求最大团问题的分枝定界规则,从而将图论中的经典问题转化成代数问题加以解决,并给出实例说明该算法的有效性。     

基于分子信标的可满足性问题的粘贴模型

为了解决NP完全问题中的可满足性问题,将分子信标和粘贴模型的优势结合起来,设计了一种新的以分子信标为粘贴链的粘贴模型,并将该模型应用于可满足性问题的求解。由于分子信标具有易操作、高灵敏度、高特异性等特点,将分子信标作为粘贴链,分子信标粘贴链比普通粘贴链链更有优势,利用该模型求解问题的操作简单且容易观测,求得问题的解比普通的粘贴模型更准确可靠。     

随机网络最大概率路径问题的模型与算法

为了求解满足一定时间限制的最大概率路径问题,在建立该问题数学模型的基础上,提出了一种改进蚁群算法。首先根据随机网络的定义建立了随机网络最大概率路径问题的数学模型,然后结合随机网络最大概率路径问题的特点,设计了一种新的启发式信息和信息素更新规则的改进蚁群算法,最后选择了4组数据,将改进蚁群算法与一种混合遗传算法进行对比试验,分别求取对应的全局最大概率路径和反映算法总体性能的多项数据。实验表明,改进蚁群算法的收敛速度和总体性能均优于混合遗传算法,为求解随机网络最大概率路径问题提供了一种快速、可行的方法。     

基于粘贴和删除系统求解旅行商问题的DNA算法

旅行商问题（Traveling Salesman Problem,TSP）是一个典型的NP完全问题.粘贴和删除模型是DNA计算的两个基本计算模型.结合上述两个模型的优点,构造粘贴-删除模型,并利用该模型给出求解旅行商问题一种新的DNA算法.     

基于最小费用最大流的中文分词算法模型

中文自动分词不仅是中文信息处理的基础性工作而且对后续句法分析、语义分析等中文信息处理流程有着很大的影响。本文基于最小费用最大流,提出一个具有拓展性的中文分词算法模型,实验证明了本算法能够准确地对输入文字串进行切分。     

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

针对目前存在的解决图顶点着色问题的DNA算法或DNA编码量过大或复杂度太高的问题,为了提高解题效率,将多级分离技术应用到图顶点着色问题的求解中,对解决该问题原有粘贴DNA算法加以改进;改进后的算法减少了操作步骤,达到了预期目的;最后,通过对一个实例的模拟,说明了改进算法的可行性.