检索结果-南通市图书馆

同方期刊数据库

同方期刊数据库博看期刊评论

在线全文

学校读者我要写书评

暂无评论

信息传播算法在支配集问题中的应用研究

信息传播算法在支配集问题中的应用研究

作者：刘子琳北方民族大学

学位级别：硕士

最小支配集（Minimum Dominating Set,MDS）问题是图论中的一个重要问题,在网络资源配置中有广泛的应用。城市交通网与通讯网建造、物流网络中心选址、连通设施选址、自适应网络设置等,都可归结为MDS问题。该问题的求解对于图着色、最... 详细信息

最小支配集（Minimum Dominating Set,MDS）问题是图论中的一个重要问题,在网络资源配置中有广泛的应用。城市交通网与通讯网建造、物流网络中心选址、连通设施选址、自适应网络设置等,都可归结为MDS问题。该问题的求解对于图着色、最大匹配、最大独立集、最小顶点覆盖、最大集合覆盖等问题的研究具有重要的理论指导意义。然而,该问题是一个经典的NP难问题,在P≠NP时,不存在求解该问题的多项式时间算法。目前,对于该问题的算法研究主要集中在精确算法和近似算法两个方面:精确算法的求解精度较高,而算法的运行时间较长;近似算法的运行时间较短,而通常无法获取问题的精确解。事实上,大量的实际问题对解的精度要求并不高,只需要解的精度达到某种近似度即可,这就佐证了近似算法的广泛应用。启发式方法是近似算法的一种有效策略,具有能在合理时间内求解复杂问题的特点。常用于求解MDS问题的启发式算法有:遗传算法、蚁群算法、禁忌搜索算法等,这类算法的一个共同的特征是容易陷入局部最优。信息传播算法是一种基于因子图的消息传递算法,当算法收敛时能够给出因子图中变量节点取值的边缘概率,大量的研究结果表明,该算法可用于有效求解组合优化问题。因此,本文探索用信息传播算法求解MDS问题。具体地讲,主要有以下几方面的研究工作:（1）将最小支配集问题映射为因子图模型,基于该因子图模型构建线性规划方程,根据线性规划方程的目标函数和约束方程构造信息传播算法的势函数;（2）设计求解最小支配集问题的信息传播算法,当算法收敛时,获得每个节点取值的边缘概率,利用边缘概率高概率地确定最小支配集节点,并在随机生成的无向图上进行数值实验,结果表明该方法有效。（3）设计基于信息传播算法的通信基站选址系统,为最小支配集问题给出了现实应用场景,为现有的通信行业提供帮助。

关键词：最小支配集问题信息传播算法线性规划因子图

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

求解可满足性问题的信息传播算法研究综述

计算机应用研究 2022年第7期39卷 1933-1940页

作者：谢志新王晓峰曹泽轩于卓莫淳惠吴宇翔北方民族大学计算机科学与工程学院银川750021 北方民族大学图形图像智能处理国家民委重点实验室银川750021

信息传播算法来自统计物理,被广泛应用于人工智能各个领域,特别是求解组合优化问题时,具有良好的有效性。通过对信息传播算法的相关文献进行分析,综述了信息传播算法以及其相关应用的发展史,根据信息传播算法的发展,介绍了求解可满足性... 详细信息

信息传播算法来自统计物理,被广泛应用于人工智能各个领域,特别是求解组合优化问题时,具有良好的有效性。通过对信息传播算法的相关文献进行分析,综述了信息传播算法以及其相关应用的发展史,根据信息传播算法的发展,介绍了求解可满足性问题的信息传播算法相关概念,主要涉及到警示传播算法、置信传播算法和调查传播算法,描述了三种算法发展中出现的收敛性、有效性研究,分别综述了各个算法在相关领域的应用情况,并总结了信息传播算法的研究路径和应用方向。

关键词：信息传播算法组合优化可满足性问题警示传播置信传播调查传播

求解多起点多旅行商问题的K-means聚类信息传播算法

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

科学技术与工程 2022年第23期22卷 10146-10154页

作者：程亚南王晓峰刘凇佐莫淳惠北方民族大学计算机科学与工程学院银川750021 北方民族大学图像图形智能处理国家民委重点实验室银川750021

多旅行商问题在实际生活中有着较为广泛的应用价值,该问题的求解受到越来越多学者的关注。信息传播算法是一类求解组合优化问题最为有效的方法,基于K-means聚类技术,给出了求解多起点多旅行商问题(multiple depots multiple traveling s... 详细信息

多旅行商问题在实际生活中有着较为广泛的应用价值,该问题的求解受到越来越多学者的关注。信息传播算法是一类求解组合优化问题最为有效的方法,基于K-means聚类技术,给出了求解多起点多旅行商问题(multiple depots multiple traveling salesman problem, MMTSP)的信息传播算法,该算法采用K-means聚类算法将旅行商问题进行聚类,从而形成若干不同类,对每一个类采用信息传播算法进行旅行商搜索,将每一个类的搜索结果进行综合,得到MMTSP问题的解。通过对旅行商标准测试数据集中的多种实例进行测试,并与ABC、ACO、PSO、IWO、TWPS、AC-PGA、STASA_2OPT和STASA 8种算法进行试验对比分析。结果表明本文算法最优值小于其他算法和算法稳定的优点。

关键词：旅行商问题多旅行商问题 K-means聚类信息传播算法

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

基于树分解的信息传播算法性能分析研究

基于树分解的信息传播算法性能分析研究

作者：谢志新北方民族大学

学位级别：硕士

组合优化问题是计算机科学领域一个重要研究方向,可满足性判定问题(satisfiability,SAT)作为一类组合优化问题,研究目标为判定是否有一组赋值使合取范式(conjuncitve normal form,CNF)的所有子句都满足,即命题公式为真。现实中许多实际... 详细信息

组合优化问题是计算机科学领域一个重要研究方向,可满足性判定问题(satisfiability,SAT)作为一类组合优化问题,研究目标为判定是否有一组赋值使合取范式(conjuncitve normal form,CNF)的所有子句都满足,即命题公式为真。现实中许多实际应用问题都可以转化为SAT问题进行求解。因此,SAT问题一直受到学者的广泛关注。物理学家基于腔域方法设计的信息传播算法,能够有效求解SAT问题,表现优于完备性算法,尤其在难解区域求解十分有效。但当问题规模变得复杂,对应因子图中环路增加,信息在迭代过程中,出现环路传播,算法逐渐失效。因此,收敛性对信息传播算法有效求解有重要影响。树宽被用作图结构特征的度量参数,在限制树宽条件下,很多难解问题可以有效求解。引入树宽度量因子图结构特征,探索信息传播算法的求解性能与树宽之间的联系。本文设计了对3种求解可满足性问题信息传播算法的因子图结构树宽度量模型,给出了三种算法的收敛树宽阈值,具体地讲,有如下研究内容:(1)利用树分解方法构造命题公式对应因子图的树宽度量模型,计算可满足随机实例的树宽。建立树宽与警示传播算法收敛性之间的联系,分析不同变元规模实例下树宽与警示传播算法收敛率之间的变化,给出了基于树宽的警示传播算法收敛性判定条件。(2)提出一种基于遗传算法的遗传因子图树分解算法(Genetic factor graph tree decomposition algorithm,GAFTW),根据信念传播算法在因子图上迭代特性,利用GAFTW算法对因子图进行树分解。在遗传算法的种群迭代中寻找更优消点序,得到更小的树宽。利用树宽参数度量因子图结构特征,建立树宽与信念传播算法收敛性之间的关系模型,对BP算法收敛性进行系统性分析,给出了基于树分解的信念算法收敛性判定条件。(3)连通树分解相较于树分解,对图中环路大小度量更加准确,调查传播算法在三种信息传播算法中求解环路复杂因子图实例上最有效。因此,使用连通树分解方法构造了命题公式的连通树宽度量模型,计算因子图的连通树宽。建立连通树宽与调查传播算法收敛性之间的关系,分析连通树宽增长与因子图结构复杂性之间的关系,给出了基于连通树宽的调查传播算法收敛性判定条件。

关键词：组合优化问题可满足性问题信息传播算法树分解遗传算法

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

信息传播算法在背包问题中的应用研究

信息传播算法在背包问题中的应用研究

作者：张丹丹北方民族大学

学位级别：硕士

0-1背包问题是组合优化范畴中一类重要的NP-难问题,该问题不仅经常出现在人工智能的各个研发环节,现实生活中也大量存在,如:投资决策问题、货物装载问题、网络资源分配问题以及材料切割问题等等。虽然精确算法可以计算其最优解,但问题... 详细信息

0-1背包问题是组合优化范畴中一类重要的NP-难问题,该问题不仅经常出现在人工智能的各个研发环节,现实生活中也大量存在,如:投资决策问题、货物装载问题、网络资源分配问题以及材料切割问题等等。虽然精确算法可以计算其最优解,但问题输入规模过大时,求解速度较慢且不具有实际应用价值。启发式算法可以有效求解大规模的复杂问题,但物品维度过高时近似性较差。所以,对求解该问题的算法做进一步研究具有重要意义。信息传播算法是一种有效求解组合优化问题的近似算法,广泛应用于人工智能和工程技术的各个方面。分析信息传播算法的原理发现,其本质是一种基于因子图模型的消息迭代算法,当算法收敛时,能够高概率地确定某些变量的取值,从而对原有问题进行简化。而0-1背包问题可以表述为:在满足背包容量限制的条件下,为了获得最大的装包价值,选择高概率可行的物品装包组合。因此,探索一种使用信念传播算法求解0-1背包问题的新方法,具体地讲,主要创新点如下:(1)以0-1背包问题的线性规划方程为基础,将线性规划的约束条件作为因子图的子句节点,根据约束条件与独立变量之间的统计关系将0-1背包问题的线性规划模型转化为因子图模型;(2)使用指数函数的形式给出因子图上的初始信息,根据0-1背包问题的特征和可行解的要求,重新定义信息传播算法的标识函数,设计了一种求解0-1背包问题的信念传播算法。

关键词： 0-1背包问题信息传播算法线性规划因子图

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

结构熵在信息传播算法性能分析中的应用研究

结构熵在信息传播算法性能分析中的应用研究

作者：牛进北方民族大学

学位级别：硕士

布尔可满足性判定问题(Boolean Satisfiability Problem,SAT)作为一类特殊的约束可满足性问题(Constraint Satisfaction Problem,CSP),在计算机科学中有广泛的应用前景。而该问题作为NP难问题,在P!=NP条件下,不存在确定多项式时间的解... 详细信息

布尔可满足性判定问题(Boolean Satisfiability Problem,SAT)作为一类特殊的约束可满足性问题(Constraint Satisfaction Problem,CSP),在计算机科学中有广泛的应用前景。而该问题作为NP难问题,在P!=NP条件下,不存在确定多项式时间的解。因此,SAT问题一直被数理逻辑界和计算机科学界的研究者重点关注。上世纪50年代,物理学家提出了一种基于因子图的信息传播算法,该类算法通常能有效求解SAT问题,但算法性能依赖于因子图的结构。当因子图的结构比较复杂,尤其是当因子图中出现环路时,信息传播算法不总有效,往往表现为不收敛。因此,收敛性是信息传播算法性能评价的主要指标。结构熵作为一种网络结构复杂程度的动态度量方法,引入结构熵不仅可以度量信息传播算法在因子图上的复杂性和不确定性等重要结构信息,还可以反映信息传播算法中随机游走过程的动态复杂性。为了更加深入地研究信息传播算法在求解SAT问题时的性能表现,利用结构熵分析随机SAT实例因子图的结构信息,基于该结构信息进一步研究信息传播算法的收敛性。本文主要研究成果如下:(1)提出了命题公式的结构熵。根据警示传播(Warning Propagation,WP)算法的信息传播策略,建立了命题公式多维结构熵度量模型,结合WP算法在实例上的收敛情况,分析WP算法的收敛性和实例的多维结构熵之间的关系,进而利用多维结构熵度量WP算法的收敛性,给出了基于多维结构熵的WP算法的收敛性判定条件。(2)提出了基于警示传播的社区发现算法(Lable Propagation Algorithm base on WP,WPLPA)。针对调查传播(Survey Propagation,SP)算法在因子图上的传播过程,利用WPLPA算法对因子图进行社区划分,建立了基于WPLPA算法的命题公式二维结构熵度量模型,利用该模型度量SP算法中因子图的结构复杂性,通过二维结构熵分析SP算法收敛性,给出了SP算法收敛的判定条件。

关键词：信息传播算法可满足性问题结构熵收敛性

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

植入指派实例集上信息传播算法的收敛性

植入指派实例集上信息传播算法的收敛性

作者：崔立北方民族大学

学位级别：硕士

命题公式的可满足性(SAT)问题作为一类重要的NP完全问题,与人工智能中许多复杂性问题密切相关。然而,随着人工智能领域的快速发展,为了满足新的需求,需要重新审视和设计SAT问题原有的求解算法,因此,SAT问题在当下面临新的机遇和挑战。... 详细信息

命题公式的可满足性(SAT)问题作为一类重要的NP完全问题,与人工智能中许多复杂性问题密切相关。然而,随着人工智能领域的快速发展,为了满足新的需求,需要重新审视和设计SAT问题原有的求解算法,因此,SAT问题在当下面临新的机遇和挑战。上世纪八十年代,物理学家提出了一种基于消息传递的信息传播算法,将该算法用于SAT问题的求解得到的效果十分显著,因此一直被学者广泛应用和研究。然而,由于该算法在相变区域有时不收敛,算法表现为失效。而对于这种现象,目前仍缺少系统的理论解释。因此本文基于WP-可解公式展开对信息传播算法的收敛性研究,力图从理论上给予对于算法收敛性现象的解释。主要研究内容如下:(1)分析信息传播算法的原理,找出信息传播算法下的骨干集和后门集之间的关系,并给出WP-可解公式的定义;(2)基于WP-可解公式的特点,借助于植入指派实例产生模型,研究信息传播算法在WP-可解公式上的收敛性,给出信息传播算法收敛的一个有效条件:信息传播算法在公式F上高概率收敛,当且仅当公式F是WP-可解公式。本文给出了信息传播算法收敛的条件,为信息传播算法的基础研究以及在人工智能领域的应用提供了理论支持。

关键词：信息传播算法可满足性问题 WP-可解公式收敛性

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于信息传播算法的推荐系统设计与开发

基于信息传播算法的推荐系统设计与开发

作者：刘欣欣北方民族大学

学位级别：硕士

随着互联网技术的不断发展,特别是移动网络的发展,信息量成爆炸式增长。如何在海量的信息中,为用户提供精准高效的个性化服务变得迫在眉睫。为了解决这个问题,推荐算法应用而生。随着用户特殊需求和新项目的不断出现,传统的推荐算法出... 详细信息

随着互联网技术的不断发展,特别是移动网络的发展,信息量成爆炸式增长。如何在海量的信息中,为用户提供精准高效的个性化服务变得迫在眉睫。为了解决这个问题,推荐算法应用而生。随着用户特殊需求和新项目的不断出现,传统的推荐算法出现许多新的问题,如冷启动、推荐新颖度不够、数据稀疏等。面对这些问题,许多新技术被应用于推荐系统中,产生了一批新的推荐方法,如基于深度学习的推荐方法、基于协同过滤的推荐方法、基于矩阵分解的推荐方法等等。然而,在缺少用户信息的情况下,这些方法求解准确率较低。本文提出一种基于信息传播的推荐方法,信息传播算法是一种可以有效地求解各节点的置信度的方法,该算法是一种基于因子图模型信息迭代算法。目前,该算法已被应用于各个领域,如组合优化、多目标线性规划、图像组合等。将这种算法应用在推荐系统中,可以求出用户的边缘概率,进而为用户进行推荐。具体地讲:本文首先对豆瓣电影网进行了爬取,并对爬取的数据进行预处理,然后对电影评论数据进行中文情感分析,最后利用构建的电影评分综合模型得到电影的综合评分。基于综合评分,构建了一种因子图模型,然后在该因子图模型上进行信念传播算法求解,并通过与其它推荐算法的对比分析,验证了本算法的有效性。通过Python技术对推荐系统进行了搭建工作,将本文设计的推荐算法应用到系统中,最终实现了一个基于Flask框架的电影推荐系统。

关键词：信息传播算法推荐方法因子图模型电影推荐系统

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于信息传播算法的云存储系统架构研究

河北软件职业技术学院学报 2014年第4期16卷 38-42页

作者：王鸿磊张雪松徐州工业职业技术学院信息管理技术学院江苏徐州221140 徐州市工业信息网络工程技术研究中心江苏徐州221000

云存储是一种在线网络存储模式,可以为用户提供能直接访问的大范围资源和应用程序。虽然许多云存储提供商已经采用加密策略来保护客户的数据,但是用户还是怀疑数据的安全性和隐私性。通过信息传播算法分析,证明它能够解决云存储数据的... 详细信息

云存储是一种在线网络存储模式,可以为用户提供能直接访问的大范围资源和应用程序。虽然许多云存储提供商已经采用加密策略来保护客户的数据,但是用户还是怀疑数据的安全性和隐私性。通过信息传播算法分析,证明它能够解决云存储数据的私密性、完整性等问题,在此基础上,提出一种采用信息传播算法的云存储系统架构,实验证明,它可以提高云存储数据的安全性、完整性和可用性。

关键词：云存储安全信息传播算法代理服务器