导读:本文包含了多头绒泡菌论文开题报告文献综述、选题提纲参考文献及外文文献翻译，主要关键词:多头,算法,最短,路径,变形虫,模型,旅行。
多头绒泡菌论文文献综述
林朗,张自力[1]（2019）在《基于多头绒泡菌的贝叶斯网络结构学习》一文中研究指出贝叶斯网络是概率统计与图论相结合的一种图模型,已成功应用于多个领域中。然而,仅依赖专家的领域知识构建贝叶斯网络非常困难。因此,从数据中学习贝叶斯网络结构已经成为该研究领域的重点问题。针对贝叶斯网络结构学习搜索空间太大的问题,根据多头绒泡菌在觅食过程中展现出的保留重要觅食管道的特性,文中结合多头绒泡菌相关数学模型和条件互信息理论对原始搜索空间进行缩减,并将求解得到的无向图作为网络的基础骨架;之后利用爬山法确定骨架方向,并得到对应的拓扑排序;最后将节点顺序作为K2算法的输入以求得最终网络,并选用网络拓扑结构及评分作为评价指标在多个数据集上进行对比实验。实验结果表明,所提算法在网络重构及原始数据匹配上具有更高的准确度。(本文来源于《计算机科学》期刊2019年09期）
马学森,朱建,谈杰,唐昊,周江涛[2]（2019）在《多头绒泡菌预处理的改进Q学习算法求解最短路径问题》一文中研究指出针对最短路径问题中Q学习算法的初始搜索空间大、后期收敛不稳定的缺陷,提出多头绒泡菌预处理的改进Q学习算法(PPA-Q)。该算法引入网络预处理过程和自适应概率选择模型,利用多头绒泡菌进行网络预处理,减少算法前期的无用探索空间,再通过改进的模拟退火算法实现自适应概率选择模型,加强算法对优质路径的探索程度,增加算法初期解的多样性,同时在算法后期稳定逼近最优路径且不振荡。仿真结果表明,PPA-Q算法收敛到最优路径成功率为100%,高于经典蚁群(ACO)算法和Q(λ)算法的80%,其迭代次数分别低于Q学习算法57. 2%、ACO算法32. 9%和Q(λ)算法35. 1%.(本文来源于《电子测量与仪器学报》期刊2019年05期）
朱建[3]（2019）在《基于多头绒泡菌的改进Q学习算法求解最短路径问题研究》一文中研究指出最短路径问题是图论分析与算法设计等理论研究中的经典问题,也是物流规划、行车导航等实际应用领域中的基本问题。由于Q学习算法具有环境无关性和离线学习的优点,无需建立具体的环境模型便可对最短路径进行求解,同时其离线学习的特性易于与其他优化算法相结合,因此在求解最短路径问题方面取得较好的效果。本文针对Q学习算法前期搜索空间大、中期搜索慢、后期收敛不稳定等缺点,研究基于改进Q学习算法的最短路径问题。针对Q学习算法前期搜索空间大和后期难以稳定收敛的问题,本文提出基于多头绒泡菌的自适应选择Q学习算法(Adaptive Choosing Q-learning based on Physarum Polycephalum Algorithm,ACQPPA)。ACQPPA通过多头绒泡菌算法对网络模型进行预处理,筛选出次优路径作为Q学习算法的初始Q值矩阵,减少Q学习算法前期的搜索空间;同时利用改进的模拟退火算法对探索策略进行动态处理,令探索策略随算法推进逐步降低,保证算法前期解的多样性算法及后期的稳定收敛。仿真结果表明,在网络节点数量为128的情况下,ACQPPA算法收敛到最优路径成功率为100%,高于ACO算法和Q(λ)算法的80%,其迭代次数分别低于Q学习算法57.2%、ACO算法32.9%和Q(λ)算法35.1%。针对Q学习算法中期搜索慢的问题,并为进一步提升多头绒泡菌算法预处理网络的效率,本文提出基于网络压缩的双向ACQPPA算法(Bidirectional ACQPPA based on Network Compression,B-ACQPPANC)。B-ACQPPANC利用CH算法(Contraction Hierarchies)缩小网络规模,减少多头绒泡菌算法预处理网络时的耗时;同时将双向探索的思想与Q学习算法相结合,将反向探索结果作为正向探索的先验知识进行储备,加快算法探索速度。对比仿真结果表明,B-ACQPPANC算法的平均成功收敛次数降低43.26%,同时Q学习算法和Q(λ)算法平均成功收敛次数分别降低39.40%和29.76%,同时改进后的B-ACQPPANC收敛到最优路径成功率为100%,高于B-QNC算法的80%和B-Q(λ)NC算法的20%。(本文来源于《合肥工业大学》期刊2019-04-01）
蒋世翠,张波,李艳双,李东浩,李玉[4]（2018）在《基于GLME/GC-MS分析固体培养的多头绒泡菌挥发性成分》一文中研究指出分析液培养的多头绒泡菌的挥发性成分组成,为黏菌的研究及应用开发工作奠定基础。采用固体培养方式培养多头绒泡菌,获得多头绒泡菌的材料,冷冻干燥。采用气液微萃取技术(GLME)从5.0mg多头绒泡菌中,260℃,萃取5 min,萃取其挥发性成分,气相色谱-质谱(GC-MS)联用技术对其化学成分进行分析。获得104个基峰,共鉴定了61种组分,占总组分的58.65%以上。占色谱出峰面积的50.05%以上。已经鉴定的组分中,含量最高的是呋喃基羟甲基酮(Furyl hydroxymethyl ketone),相对含量是19.19%;其次是亚油酸。组分主要归为酸、酯、烷烃、醇、酮、醛等几大类化合物。GLME/GC-MS萃取技术比较适用于多头绒泡菌等黏菌的挥发性成分的检测分析,为进一步研究黏菌的挥发性成分提供新的检测技术。(本文来源于《中国菌物学会2018年学术年会论文汇编》期刊2018-08-11）
张天任,闵武霞,夏沁怡,李佳琦,易思卓[5]（2018）在《利用GC/MS代谢组学技术检测纳米TiO_2对多头绒泡菌代谢途径的扰动作用》一文中研究指出纳米TiO_2(n TiO_2)具有广泛的应用价值.但n TiO_2在阳光或紫外线下具有很强的氧化作用,可对细胞产生强烈的毒害作用,因此其对生态环境的可能破坏作用值得关注.有关n TiO_2在暗环境中对生物的毒性作用报道还不多,还不能全面揭示n TiO_2的毒性作用机理.代谢组学分析是发现代谢差异、识别被干扰的代谢途径、了解n TiO_2毒性作用机理、评估n TiO_2细胞毒性的重要手段.本文采用GC/MS(气相色谱/质谱)技术检测了n TiO_2在暗环境下对多头绒泡菌原质团(单细胞)代谢组的影响,根据多变量识别模式分析发现了60余个被n TiO_2显着干扰的代谢物.这些代谢物涉及糖代谢、氨基酸代谢、核苷酸代谢、多胺生物合成、次生代谢途径等,为全面了解n TiO_2对细胞的毒性作用机理提供了有益补充.(本文来源于《环境科学学报》期刊2018年09期）
刘阳,冯翔,虞慧群,罗飞[6]（2017）在《基于能量机制的多头绒泡菌动力学优化算法》一文中研究指出随着人工智能和大数据的迅猛发展,大数据的爆炸式增长和问题的复杂性分布导致对并行智能处理的要求日趋迫切.传统的理论模型和技术方法面临严峻挑战,受自然界启发的物理学法则和生物学方法逐渐成为研究热点.受多头绒泡菌的生长觅食等行为启发,提出了一种基于能量机制的多头绒泡菌动力学算法(physarum-energy dynamic optimization algorithm,PEO).该算法以多头绒泡菌算法为基础,根据其动力学特征,引入能量机制,以改进现有的多头绒泡菌算法全局信息交互能力差等缺点.此外,PEO引入了年龄因子的概念和扰动机制,以控制算法在不同阶段的寻优能力和收敛速度,并从理论角度对算法模型的收敛性进行证明.最后,通过在TSP数据集上实验证明算法在不同规模数据集的有效性和收敛性,并进行了参数分析.与其他的优化算法的对比实验数据表明,PEO在面对复杂问题的求解速度和收敛速度明显优于其他的优化算法,具有高精度和快收敛的特性.(本文来源于《计算机研究与发展》期刊2017年08期）
梁鸣心[7]（2017）在《基于多头绒泡菌仿生模型的图挖掘研究》一文中研究指出图作为一种重要的数据结构,常用于刻画自然界或社会中事物间的复杂关系。随着信息技术的发展,图模型逐渐覆盖生活各个方面,相关数据迅速增加,如社交、交通、蛋白质之间相互作用等都可以用图模型进行刻画。挖掘图中信息可以帮助人们优化推荐系统、设计高效网络、预测蛋白质功能等。如何高效的进行图挖掘已经成为一个研究热点。随着图数据增加,求解图挖掘问题的算法近年来也得到了长足发展。根据求解基本策略不同主要分为优化算法和启发式算法。但优化算法面对大规模问题时仍然存在搜索效率低的问题,启发式算法也面临易陷入局部最优解等问题。无论基于优化的算法还是启发式算法,如何提高算法效率,高效进行图挖掘问题求解是当前亟待解决的问题。生物启发一直都是推动算法发展的重要动力。最近研究中,一种名为多头绒泡菌的粘菌在觅食过程中展现出自组织、自优化等智能特性引起广泛关注。利用多头绒泡菌仿生模型,本文对现有图挖掘算法进行优化,以期提高算法效率。本文着眼于图挖掘中子图挖掘问题和图聚类问题进行研究。首先对多头绒泡菌仿生模型的图挖掘能力进行进一步探究,扩展其求解问题范围。然后利用多头绒泡菌仿生模型的特性,对代表性的图挖掘问题设计了针对性的算子和算法,对当前图挖掘算法进行优化。本文的主要贡献包括以下两个方面:1)针对子图挖掘中典型的组播树问题,本文提出了基于多头绒泡菌仿生模型的遗传交叉算子,以提高遗传算法的局部搜索能力。首先对多头绒泡菌仿生模型进行了修改,使得模型可以求解最短路径树问题。之后针对多头绒泡菌最短路径树模型计算复杂度较高的问题,优化了模型中的迭代过程。最后基于优化后的多头绒泡菌最短路径树模型,本文提出了一种新的遗传交叉算子(PMcrossover),并将PMcrossover嵌入到叁种典型的遗传算法中。通过和原算法在四个数据集上进行对比,说明基于多头绒泡菌的交叉算子可以有效的提高算法的搜索效率和鲁棒性,验证了PMcrossover的有效性。2)针对图聚类中典型的社团挖掘问题,本文从优化算法中的进化算法和启发式算法中的马尔可夫聚类算法两个方面进行求解。进化算法以遗传算法和蚁群算法为代表。为了探究多头绒泡菌仿生模型在图聚类问题上的潜力,本文对多头绒泡菌网络模型进行修改,使得其可以一定程度上区分社团间和社团内的边。之后将多头绒泡菌仿生模型对边的识别作为先验知识整合到了遗传算法的初始化过程和蚁群算法的启发式因子中,提出了进化算法优化策略。对于启发式算法,本文以马尔可夫聚类算法为代表。通过进一步研究发现,多头绒泡菌模型中的正反馈系统和马尔可夫聚类算法中的动态系统基于类似的基本假设。根据这个特点,模仿多头绒泡菌仿生模型中的正反馈关系,在马尔可夫聚类算法中建立了新的反馈流。同时,本文对典型马尔可夫聚类算法中主要算子进行优化,提出多头绒泡菌启发的马尔可夫聚类算法。最后在12个数据集上,从准确率、鲁棒性、时间复杂度等方面验证了提出方法的效果。综上,本文在对多头绒泡菌仿生模型进行研究的基础上,充分挖掘其图挖掘潜力,并对现有进化算法和马尔可夫聚类算法进行优化,对典型的子图挖掘问题和图聚类问题进行求解。同时,通过广泛实验证明了基于多头绒泡菌模型的优化策略能有效提高图挖掘算法的搜索效率和鲁棒性,多头绒泡菌启发的算法能高效的完成图挖掘任务。(本文来源于《西南大学》期刊2017-04-10）
石彩霞[8]（2016）在《nm-TiO_2、nm-CuTiO_2和nm-Betaine胁迫对多头绒泡菌基因表达的影响》一文中研究指出据ASTM介定的标准,纳米材料是指颗粒至少在一个维度上处于纳米级(1-100nm)的材料。纳米材料因具有小尺寸效应、表面效应、量子尺寸效应和量子隧道效应而被广泛应用于工业和医学等领域,也因上述特殊性质对生物体产生不同程度的毒性作用(包括破坏细胞的超微结构、细胞骨架、细胞周期和氧化损伤等)。由于动物细胞的脆弱性,纳米材料对细胞的毒性作用研究至今都无法取得深入进展。多头绒泡菌(Physarum Polycephalum)是一种环境敏感型古菌,具有更好的胁迫耐受性,以多头绒泡菌为测试对象研究纳米材料的胁迫作用有助于我们获得更多的纳米材料细胞毒性效应的细节过程。为确定不同纳米材料从刺激到抑制多头绒泡菌生长的―拐点‖剂量,本文观察了多头绒泡菌原质团在含不同浓度nm-TiO_2(纳米TiO_2)、nm-CuTiO_2(纳米级的铜包TiO_2,其中,型号为1031E、1229G、1225G的叁种nm-CuTiO_2的铜含量依次为40%、45%和55%)、nm-Betaine(纳米甜菜碱)培养皿上的生长情况。发现nm-TiO_2浓度低于9mg/m L时,原质团的生长会随着浓度的提高而增强,当nm-TiO_2浓度超过15 mg/m L时,原质团生长受到的抑制则随着浓度的升高而增强;发现nm-CuTiO_2浓度低于0.3mg/m L时,原质团的生长会随着浓度的提高而增强,当nm-CuTiO_2浓度超过0.5 mg/m L时,原质团生长受到的抑制会随着浓度的提高而增强,且铜含量越高,对原质团的胁迫作用越强;发现nm-Betaine浓度低于0.2 mg/ml时,原质团的生长会随着浓度的提高而增强,当nm-Betaine浓度超过0.5 mg/m L时,原质团生长受到的抑制会随着浓度的提高而增强;上述结果说明,无论胁迫来自无机还是有机纳米材料都会影响多头绒泡菌的生长,而且这种影响与纳米材料的性质和胁迫浓度有关。为探究nm-TiO_2、nm-CuTiO_2和nm-Betaine影响多头绒泡菌生长的作用机理,本文通过DCFH-DA标记的荧光探针分别检测了上述纳米材料胁迫培养多头绒泡菌1天后原质团内活性氧基团(Reactive Oxygen Species,ROS)的变化,发现多头绒泡菌原质团在高浓度纳米材料胁迫下的ROS水平比低浓度的高,说明无论是无机纳米材料胁迫,还是有机纳米材料胁迫都会引起ROS水平提高。为了解不同浓度的不同纳米材料胁迫对多头绒泡菌细胞膜造成的氧化损伤程度,本文检测了nm-Betaine以及1031E型、1229G型和1225G型nm-CuTiO_2胁迫培养多头绒泡菌3天后微原质团内产生的丙二醛(Malondialdehyde,MDA)水平,结果显示,当nm-Betaine以及叁种型号的nm-CuTiO_2浓度低于0.2 mg/ml时,多头绒泡菌微原质团内的MDA水平没有明显变化,说明低剂量纳米材料胁迫不至于造成多头绒泡菌细胞膜的氧化损伤。但当nm-Betaine以及叁种型号的nm-CuTiO_2浓度超过多头绒泡菌的耐受能力时,会造成多头绒泡菌细胞膜不同程度的氧化损伤;氧化损伤程度从大到小依次为,1225G型>1229G型>1031E型>nm-Betaine,其中,1031E型nm-CuTiO_2和nm-Betaine在高浓度时对多头绒泡菌细胞膜造成的氧化损伤不明显,说明nm-CuTiO_2对多头绒泡菌细胞膜造成的氧化损伤与包裹在nm-TiO_2颗粒外面的Cu多少密切相关,nm-Betaine对多头绒泡菌的胁迫作用与细胞膜的氧化损伤无关。为了解nm-TiO_2、nm-CuTiO_2和nm-Betaine在刺激和抑制多头绒泡菌生长时对多头绒泡菌基因表达的影响,本文以无胁迫作用的多头绒泡菌为对照,通过高通量测序技术检测了nm-TiO_2、nm-CuTiO_2和nm-Betaine显着刺激和显着抑制多头绒泡菌生长时的多头绒泡菌转录组。通过比对分析转录组数据,找出了上述纳米材料在刺激和抑制细胞生长时对多头绒泡菌基因表达的影响以及所影响的信号通道。结果显示,在nm-TiO_2显着刺激多头绒泡菌生长时(9 mg/m L nm-TiO_2),至少有193个基因出现了表达变化,其中,127个基因出现了表达上调,66个基因出现了表达下调;这些差异表达的基因主要富集在嘧啶代谢通路上,说明nm-TiO_2对多头绒泡菌生长的刺激作用与其对多头绒泡菌DNA合成的影响有关。在nm-TiO_2显着抑制多头绒泡菌生长时(15 mg/m L nm-TiO_2),至少有392个基因出现了表达变化,其中,312个基因出现了表达上调,80个基因出现了表达下调;这些差异表达的基因主要富集在DNA复制、细胞周期和DNA损伤修复等通路上,说明nm-TiO_2对多头绒泡菌生长的抑制作用与其对DNA复制、DNA损伤修复和细胞周期的影响有关。结果显示,在nm-CuTiO_2显着刺激多头绒泡菌生长时(0.3 mg/m L nm-CuTiO_2),至少有280个基因出现了表达变化,其中,179个基因出现了表达上调,101个基因出现了表达下调。在nm-CuTiO_2显着抑制多头绒泡菌生长时(0.5 mg/m L nm-CuTiO_2),至少有1643个基因出现了表达变化,其中,968个基因出现了表达上调,675个基因出现了表达下调;这些差异表达的基因主要富集在核糖体合成(P-value=1.53E-19)、DNA复制(P-value=0.0143)和基因同源重组(P-value=0.037200594)等通路上,说明nm-CuTiO_2对多头绒泡菌生长的抑制作用与其对多头绒泡菌的蛋白质合成、细胞增殖的影响有关。结果显示,在nm-Betaine显着刺激多头绒泡菌生长时(0.2 mg/m L nm-Betaine),至少有387个基因出现了表达变化,其中,309个基因出现了表达上调,78个基因出现了表达下调;这些差异表达的基因主要参与了氧化还原反应和碳水化合物代谢等,说明nm-Betaine对多头绒泡菌生长的刺激作用与其对多头绒泡菌的代谢影响有关。在nm-Betaine显着抑制多头绒泡菌生长时(0.5 mg/m L nm-Betaine),至少有374个基因出现了表达变化,其中,286个基因出现了表达上调,88个基因出现了表达下调;这些基因主要参与了DNA复制(P-value=1.10E-12)、细胞周期(P-value=7.41E-08)和碱基切除修复(P-value=2.58E-06)等,说明nm-Betaine对多头绒泡菌生长的抑制作用与其对多头绒泡菌的DNA复制、DNA损伤修复和细胞周期的影响有关。为找出nm-TiO_2、nm-CuTiO_2和nm-Betaine从刺激到抑制多头绒泡菌生长时表达发生相同变化趋势的基因,进而通过检测这些标志多头绒泡菌细胞发生毒性反应变化的“拐点”基因的表达量变化确定纳米材料对多头绒泡菌的毒性作用剂量,本文比较了nm-TiO_2、nm-CuTiO_2和nm-Betaine显着刺激和显着抑制多头绒泡菌生长时的转录组,发现低浓度纳米材料胁迫刺激多头绒泡菌生长时,有39个差异表达基因,这些基因是本文低浓度纳米材料胁迫刺激多头绒泡菌生长的基因。发现高浓度纳米材料胁迫抑制多头绒泡菌生长时,有38个差异表达基因,这些基因是本文高浓度纳米材料胁迫抑制多头绒泡菌生长的基因。本文选取了5个高浓度抑制多头绒泡菌生长的上调基因和5个低浓度刺激多头绒泡菌生长的下调基因,通过Real-Time PCR相对定量验证,得到的结果与转录组测序结果一致,说明转录组测序结果有较高可信度。这为建立纳米材料的细胞毒性检测标准,建立起纳米材料生物安全性的评估体系提供了基础。(本文来源于《深圳大学》期刊2016-06-30）
卢雨潇[9]（2016）在《基于多头绒泡菌模型的优化蚁群算法及其在旅行商问题中的运用》一文中研究指出NP-难问题是计算机科学研究中的主要研究问题之一。Garey提出了若一个问题被定义为NP-难问题,则无法用计算机进行精确求解的论断。该论断为研究人员奠定了计算难解的界限,避免了研究人员为解决此类问题而做出大量而无效的工作。但是在实际问题当中,NP-难问题又是不可避免的,如在路网规划、工业控制、网络构建等实际问题上都要涉及到NP-难问题。既然已有论断表明计算机无法精确求解NP-难问题,研究人员均将目光转向了近似求解NP-难问题,并取得了较大的进展。作为经典的NP-难问题——(多目标)旅行商问题在真实世界中具有广泛的应用,例如车辆调度问题、路线推荐问题。理论界和工程界对能够高效求解(多目标)旅行商问题的算法具有迫切的需求。当前,群体智能算法已成为求解(多目标)旅行商问题的主流算法,其中包括遗传算法、粒子群算法、蚁群算法等。蚁群算法在求解经典旅行商问题时体现出了良好的鲁棒性和可行性,因此,研究人员将蚁群算法运用到了求解多目标旅行商问题上来。当前求解多目标旅行商问题的蚁群算法主要分为叁类:基于目标转化、基于种群和基于帕累托最优叁类。尽管当前利用蚁群算法解决多目标旅行商问题已经有了很大进展,但是由于蚂蚁之间的信息素正反馈交流方式使蚂蚁群体倾向于集中选取帕累托前沿的某个可行空间,产生解分布过于集中、解空间的覆盖率过低和局部最优解等问题;且蚁群算法在求解初期搜索盲目性强,导致搜索效率低下。综上,蚁群算法还有进一步优化的空间。研究人员在生物实验中发现,一种单细胞多核黏菌——多头绒泡菌,拥有优秀的路径寻优能力和路网导航能力。Tero发现多头绒泡菌在觅食过程中呈现出了一种“重点管道重点培养”的正反馈机制,并对该机制进行了建模分析。基于该模型,本文提出利用多头绒泡菌模型优化蚁群算法。在优化算法中,本文先利用多头绒泡菌模型对多目标旅行商问题中的各目标进行分别得粗略求解,得到大致的“地图”——信息素矩阵,虽然这张“地图”并不一定准确,但是却有一定的指向性。同时,利用该“地图”参与初始化蚁群算法的信息素矩阵,解决蚁群算法求解多目标旅行商问题前期的盲目性问题。在每次迭代过程中,因为信息素具有挥发性,所以该“地图”的偏差并不会严重地影响蚁群算法的寻优效率,同时,虽然该“地图”携带的信息素会挥发,但是并不会迅速消失,所以,该“地图”能够在一定程度上扩大蚂蚁的搜索范围,使得解的可行性更高、在帕累托前沿上的分布更加广泛。通过大量的仿真实验发现,新算法在解分布的广泛性、解空间的覆盖率和解的可行性等方面都有了显着的提升。随后,本文将山西十大景点旅游路线推荐问题转换成为一个多目标旅行商问题,综合考虑距离和时间两大因素。利用本文所提出的优化算法进行路径推荐,所得结果可行性和满意度高。该应用表明,优化算法不仅具有理论上的有效性,同时也具有现实中的实用性。本文将优化算法与另一种多头绒泡菌模型优化算法进行对比分析,实验结果显示在求解结果的精确性、扩展性、空间覆盖率方面更加优秀,同时,在求解时间方面,iPM-P-ACO算法远远领先于PM-P-ACO算法。(本文来源于《西南大学》期刊2016-04-15）
王庆[10]（2016）在《基于多头绒泡菌模型的图论关键问题研究》一文中研究指出图论问题是数学研究中与应用领域有密切联系的一个分支,其中一些经典问题已经有几十年的研究历史,且依然不断取得进步。由于这些经典问题的解决是实现许多现实应用的基础,而对这些问题解法的任何有益改进,都会对相应的应用领域有巨大的助益。比如最短路径问题和最大流问题,它们在路由、交通、决策、优化等方面的理论和应用中都有很重要的地位。这两类问题的传统算法已经很久没有取得实质性的突破。在单源最短路径树问题中,若不存在负权边,经典的Dijkstra算法的时间复杂度达到O(m+n log n),是该问题最快的算法之一。而当网络中存在负权边时,最好的强多项式算法是Bellman-Ford算法,时间复杂度达到O(nm),最好的弱多项式算法是缩放算法,时间复杂度达到O(√nm log U)。对于最大流问题,比较常用的算法为Dinic算法,时间复杂度为O(n2m)。该问题存在一个被称为流分解障碍的O(nm)时间界,任何利用增载轨的算法都无法突破这个障碍。许多优秀算法的时间复杂度已达到或突破这个界限,但实现起来非常复杂,实际效率也不高,限制了它们在实践中的应用。Dinic算法通过动态树优化可将时间复杂度降为O(nm log n),但动态树是十分复杂的数据结构,实现起来非常困难,实际性能也很差。1998年Goldberg和Rao首次获得突破流分解障碍的二分长度阻塞流算法,将时间复杂度刷新为O min n2/3,m1/2m log(n2/m)log U。该算法同样用到了动态树并且包含了大量的网络变换的操作,因此算法很复杂,实现起来比较困难,实际效率不高。解决图论问题的传统算法一般是基于对图的遍历,此类算法基本已经达到优化的极限。蚁群算法、遗传算法等启发式算法为我们提供了新的思路,那就是基于全局涌现的计算。启发式算法在传统算法无法解决的NP问题中有许多重要的运用,但在最短路径和最大流问题上始终无法取代传统算法,因为它们往往不是确定性算法,无法在确定的时间内得到准确的最优解,而且收敛速度也难以与传统算法相比。2000年,Tero等人揭示了多头绒泡菌生成迷宫中最优路径的特殊能力。多头绒泡菌是一种大型单细胞黏菌生物,按生物学分类归为变形虫门黏菌纲中的绒泡黏菌属,其营养构造,运动和摄食方式和原生动物中的变形虫相似。2007年他们又建立了多头绒泡菌的数学模型,该模型可以解决两点之间的最短路径问题,但效率并不稳定。本文在此基础上将原始的模型改进为具有稳定效率和确定结果的算法,称为变形虫算法,并运用到单源最短路径、最大流问题和一些实际问题中。该算法已经达到甚至超过了目前最好的传统算法。变形虫算法是一种通过正反馈的演化规则建立的非线性动态系统,通过不断演化涌现出最终结果。针对不同的问题,研究和制定不同的规则和限制条件,得到相应的结果。变形虫算法在每次迭代中需要解一个系数矩阵为拉普拉斯矩阵的线性方程组,目前求解线性方程组借助快速矩阵乘法的方法,可以达到O n2.X的时间复杂度,其中2.X=2.3728639,且还在不断进步,有望充分接近O(n2 log n)。同时,针对系数矩阵为拉普拉斯矩阵的特殊线性方程组,可以更快的求解,时间复杂度为O(m log n)。所以变形虫算法的时间复杂度的一般形式为O(km log n),k为迭代次数。本文将重点研究和改进变形虫算法来解决单源最短路径和最大流问题,以及在一些现实问题中的应用,创新的研究成果有以下几个方面:1、证明了多头绒泡菌数学模型的收敛性和正确性,以及它的收敛速度,并将多头绒泡菌的数学模型进行改进和离散化,形成原始的变形虫算法。对于2007年提出的多头绒泡菌模型,其收敛过程一直未得到充分的研究和证明。本文在原始模型的基础上稍作完善,并通过不变集理论证明了它在权值为正数,初始状态非0时,一定收敛于最短路径的解,同时,其收敛速度与网络的结构有关。我们将这一模型离散化,形成变形虫算法的原始版本,通过实验验证,原始变形虫算法是一个解决单源最短路径问题的伪多项式算法,对于整数问题,它的时间复杂度可以写为O U m log2n。原始变形虫算法只是搭建了一个解决问题的算法框架,体现了多头绒泡菌模型的正反馈机制。而针对不同问题,算法还需要进行相应的改进和优化。2、在原始变形虫算法基础上,通过扩展改进,形成解决带负权的单源最短路径问题的变形虫算法,并分析和比较它的求解效率,该算法优于Bellman-Ford算法,同时还具有检测、定位和消除网络中所有的负权环的能力。Bellman-Ford算法可以在O(nm)时间内求解带负权的单源最短路径,并判断网络中是否存在负环。本文在原始变形虫算法基础上,针对负权网络的单源最短路径问题提出改进和优化方案,得到时间复杂度为O(√nm log n)的算法。对于可能存在负权环的网络,Bellman-Ford算法需要到最后一次迭代结束才能判定存在负环,对应于算法的最坏情况,而变形虫算法可以在O n0.Zm log n内检测、定位和消除网络中的所有负权环,并且不破坏网络的连通性,这是其他算法都无法做到的,其中0.Z≈0.65。3、针对最大流问题模型,改进变形虫算法解决最大流问题,并分析和比较它的求解效率,该算法优于Dinic算法,同时还能得到网络的所有最小割。目前网络最大流问题的算法时间复杂度的精确下界还没有被找到,而流分解障碍O(nm)作为该问题中某一类算法的时间复杂度下界,在很长一段时间都没有被突破。直到1998年首次得到O min n2/3,m1/2m log(n2/m)log U的算法。但所有达到或突破O(nm)时间界的算法都需要实现复杂的数据结构或者网络变换操作,实际效率并不高,不具有实用性,较常用的算法仍然是具有O(n2m)时间复杂度的Dinic算法等。本文针对最大流问题设计的变形虫算法时间复杂度为O(log(nU)m log n),且易于实现,没有额外的开销。它是第二个突破流分解障碍的算法,并将该问题的时间复杂度一举拉低到?O(m)程度,且在实际效率上也优于Dinic算法,具有理论和实用价值。同时,它在迭代过程中,将网络自然的按最小割分割成几个部分,在获得最大流的同时也得到网络中的所有最小割。(本文来源于《西南大学》期刊2016-04-08）
多头绒泡菌论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
针对最短路径问题中Q学习算法的初始搜索空间大、后期收敛不稳定的缺陷,提出多头绒泡菌预处理的改进Q学习算法(PPA-Q)。该算法引入网络预处理过程和自适应概率选择模型,利用多头绒泡菌进行网络预处理,减少算法前期的无用探索空间,再通过改进的模拟退火算法实现自适应概率选择模型,加强算法对优质路径的探索程度,增加算法初期解的多样性,同时在算法后期稳定逼近最优路径且不振荡。仿真结果表明,PPA-Q算法收敛到最优路径成功率为100%,高于经典蚁群(ACO)算法和Q(λ)算法的80%,其迭代次数分别低于Q学习算法57. 2%、ACO算法32. 9%和Q(λ)算法35. 1%.
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
多头绒泡菌论文参考文献
[1].林朗,张自力.基于多头绒泡菌的贝叶斯网络结构学习[J].计算机科学.2019
[2].马学森,朱建,谈杰,唐昊,周江涛.多头绒泡菌预处理的改进Q学习算法求解最短路径问题[J].电子测量与仪器学报.2019
[3].朱建.基于多头绒泡菌的改进Q学习算法求解最短路径问题研究[D].合肥工业大学.2019
[4].蒋世翠,张波,李艳双,李东浩,李玉.基于GLME/GC-MS分析固体培养的多头绒泡菌挥发性成分[C].中国菌物学会2018年学术年会论文汇编.2018
[5].张天任,闵武霞,夏沁怡,李佳琦,易思卓.利用GC/MS代谢组学技术检测纳米TiO_2对多头绒泡菌代谢途径的扰动作用[J].环境科学学报.2018
[6].刘阳,冯翔,虞慧群,罗飞.基于能量机制的多头绒泡菌动力学优化算法[J].计算机研究与发展.2017
[7].梁鸣心.基于多头绒泡菌仿生模型的图挖掘研究[D].西南大学.2017
[8].石彩霞.nm-TiO_2、nm-CuTiO_2和nm-Betaine胁迫对多头绒泡菌基因表达的影响[D].深圳大学.2016
[9].卢雨潇.基于多头绒泡菌模型的优化蚁群算法及其在旅行商问题中的运用[D].西南大学.2016
[10].王庆.基于多头绒泡菌模型的图论关键问题研究[D].西南大学.2016
论文知识图
