基于多头绒泡菌仿生模型的图挖掘研究

发布时间：2018-03-25 15:20

  本文选题：图挖掘　切入点：进化计算　出处：《西南大学》2017年硕士论文

【摘要】：图作为一种重要的数据结构,常用于刻画自然界或社会中事物间的复杂关系。随着信息技术的发展,图模型逐渐覆盖生活各个方面,相关数据迅速增加,如社交、交通、蛋白质之间相互作用等都可以用图模型进行刻画。挖掘图中信息可以帮助人们优化推荐系统、设计高效网络、预测蛋白质功能等。如何高效的进行图挖掘已经成为一个研究热点。随着图数据增加,求解图挖掘问题的算法近年来也得到了长足发展。根据求解基本策略不同主要分为优化算法和启发式算法。但优化算法面对大规模问题时仍然存在搜索效率低的问题,启发式算法也面临易陷入局部最优解等问题。无论基于优化的算法还是启发式算法,如何提高算法效率,高效进行图挖掘问题求解是当前亟待解决的问题。生物启发一直都是推动算法发展的重要动力。最近研究中,一种名为多头绒泡菌的粘菌在觅食过程中展现出自组织、自优化等智能特性引起广泛关注。利用多头绒泡菌仿生模型,本文对现有图挖掘算法进行优化,以期提高算法效率。本文着眼于图挖掘中子图挖掘问题和图聚类问题进行研究。首先对多头绒泡菌仿生模型的图挖掘能力进行进一步探究,扩展其求解问题范围。然后利用多头绒泡菌仿生模型的特性,对代表性的图挖掘问题设计了针对性的算子和算法,对当前图挖掘算法进行优化。本文的主要贡献包括以下两个方面:1)针对子图挖掘中典型的组播树问题,本文提出了基于多头绒泡菌仿生模型的遗传交叉算子,以提高遗传算法的局部搜索能力。首先对多头绒泡菌仿生模型进行了修改,使得模型可以求解最短路径树问题。之后针对多头绒泡菌最短路径树模型计算复杂度较高的问题,优化了模型中的迭代过程。最后基于优化后的多头绒泡菌最短路径树模型,本文提出了一种新的遗传交叉算子(PMcrossover),并将PMcrossover嵌入到三种典型的遗传算法中。通过和原算法在四个数据集上进行对比,说明基于多头绒泡菌的交叉算子可以有效的提高算法的搜索效率和鲁棒性,验证了PMcrossover的有效性。2)针对图聚类中典型的社团挖掘问题,本文从优化算法中的进化算法和启发式算法中的马尔可夫聚类算法两个方面进行求解。进化算法以遗传算法和蚁群算法为代表。为了探究多头绒泡菌仿生模型在图聚类问题上的潜力,本文对多头绒泡菌网络模型进行修改,使得其可以一定程度上区分社团间和社团内的边。之后将多头绒泡菌仿生模型对边的识别作为先验知识整合到了遗传算法的初始化过程和蚁群算法的启发式因子中,提出了进化算法优化策略。对于启发式算法,本文以马尔可夫聚类算法为代表。通过进一步研究发现,多头绒泡菌模型中的正反馈系统和马尔可夫聚类算法中的动态系统基于类似的基本假设。根据这个特点,模仿多头绒泡菌仿生模型中的正反馈关系,在马尔可夫聚类算法中建立了新的反馈流。同时,本文对典型马尔可夫聚类算法中主要算子进行优化,提出多头绒泡菌启发的马尔可夫聚类算法。最后在12个数据集上,从准确率、鲁棒性、时间复杂度等方面验证了提出方法的效果。综上,本文在对多头绒泡菌仿生模型进行研究的基础上,充分挖掘其图挖掘潜力,并对现有进化算法和马尔可夫聚类算法进行优化,对典型的子图挖掘问题和图聚类问题进行求解。同时,通过广泛实验证明了基于多头绒泡菌模型的优化策略能有效提高图挖掘算法的搜索效率和鲁棒性,多头绒泡菌启发的算法能高效的完成图挖掘任务。
[Abstract]:......
【学位授予单位】：西南大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5;TP311.13

【相似文献】

相关期刊论文 前10条

1 邓小波;曹聪聪;龙伦海;康耀红;;蚁群算法搜索熵研究[J];海南大学学报(自然科学版);2007年04期

2 任庆生,曾进,戚飞虎;自交叉算子[J];控制理论与应用;2001年04期

3 田东平;;遗传算法中的交叉算子研究(英文)[J];内蒙古师范大学学报(自然科学汉文版);2007年03期

4 张文修,梁怡;遗传算法的数学基础[J];西安交通大学学报;2000年10期

5 陈琨;张志明;;一种改进遗传算法的设计与实现[J];贵州大学学报(自然科学版);2006年01期

6 胡兰萍;黄海斌;;遗传算法及其在化学领域中的应用[J];海南师范学院学报(自然科学版);2006年03期

7 王珊珊;;遗传算法的理论基础及应用[J];科协论坛(下半月);2008年09期

8 高翔;海洋;;遗传算法应用[J];赤峰学院学报(自然科学版);2009年03期

9 刘定理;;遗传算法综述[J];中国西部科技;2009年25期

10 欧阳柏平;;基于遗传算法优化独立分量分析[J];科技信息;2010年07期

相关会议论文 前10条

1 何敏;陈中显;梅松涛;;蚁群算法的研究与进展[A];中国计量协会冶金分会2010年会论文集[C];2010年

2 陈家照;廖海涛;张中位;罗寅生;;一种改进的遗传算法及其在路径规划中的应用[A];2009系统仿真技术及其应用学术会议论文集[C];2009年

3 李国云;刘颖;薛梅;邬志敏;;遗传算法在高温空冷冷凝器优化设计中的应用[A];第五届全国制冷空调新技术研讨会论文集[C];2008年

4 王志军;李守春;张爽;;改进的遗传算法在反演问题中的应用[A];新世纪 新机遇 新挑战——知识创新和高新技术产业发展（上册）[C];2001年

5 任燕翔;姜立;刘连民;从滋庆;;改进遗传算法在三维日照方案优化中的应用[A];工程三维模型与虚拟现实表现——第二届工程建设计算机应用创新论坛论文集[C];2009年

6 韩娟;;遗传算法概述[A];第三届河南省汽车工程科技学术研讨会论文集[C];2006年

7 庞国仲;王元西;;基于遗传算法控制步长的定性仿真方法[A];'2000系统仿真技术及其应用学术交流会论文集[C];2000年

8 张忠华;杨淑莹;;基于遗传算法的聚类设计[A];全国第二届信号处理与应用学术会议专刊[C];2008年

9 何翠红;区益善;;遗传算法及其在计算机编程中的应用[A];1995年中国智能自动化学术会议暨智能自动化专业委员会成立大会论文集（下册）[C];1995年

10 靳开岩;张乃尧;;几种实用遗传算法及其比较[A];1996年中国智能自动化学术会议论文集（下册）[C];1996年

相关重要报纸文章 前1条

1 林京;《神经网络和遗传算法在水科学领域的应用》将面市[N];中国水利报;2002年

相关博士学位论文 前10条

1 杨扩军;TIADC系统校准算法研究与实现[D];电子科技大学;2015年

2 黄亚魁;几类优化问题的BB型算法研究[D];西安电子科技大学;2015年

3 王戈;通信信号若干联合处理技术研究[D];解放军信息工程大学;2013年

4 易雯帆;非线性偏微分方程多解计算大范围收敛算法及其应用研究[D];湖南师范大学;2016年

5 蔡永智;分布式电力系统状态估计研究[D];华南理工大学;2016年

6 苏雪平;基于交叉多模信息的新闻图像人物标识算法[D];西北工业大学;2015年

7 谢侃;稀疏盲分离的理论与算法研究[D];广东工业大学;2016年

8 Amjad Mahmood;半监督进化集成及其在网络视频分类中的应用[D];西南交通大学;2015年

9 李险峰;基于改进遗传算法的汽车装配生产线平衡问题研究[D];北京科技大学;2017年

10 孙秋红;基于遗传算法的水质数据挖掘与应用研究[D];燕山大学;2016年

相关硕士学位论文 前10条

1 杨展;城轨列车自动调整系统模型与算法研究[D];西南交通大学;2015年

2 马英钧;基于人工蜂群算法的约束优化问题研究[D];华中师范大学;2015年

3 钱其;电网谐波和间谐波功率的计量算法研究[D];中国科学技术大学;2015年

4 蒋玉冰;无线通信信号到达角跟踪算法研究[D];电子科技大学;2014年

5 孙方亮;基于粒子群与中心引力的一种新混合算法及应用[D];西安电子科技大学;2014年

6 于诗杰;基于无波前探测的大气光通信自适应补偿方法研究[D];西安电子科技大学;2014年

7 柯家龙;压缩感知算法及其在成像中的应用[D];南京邮电大学;2015年

8 刘光泓;并行磁共振图像全变分恢复一阶算法研究[D];南京邮电大学;2015年

9 张德祥;基于改进蚁群算法的机器人三维路径规划研究[D];青岛科技大学;2015年

10 黎鹏;一种改进的灰度直方图跟踪算法[D];中国科学院研究生院(光电技术研究所);2016年

，

本文编号：1663702