智能电网中基于二分图匹配的网络切片资源分配算法

为了解决智能电网中多类业务的服务质量需求难以同时得到满足的问题并兼顾电力终端和网络侧经济效用,提出了一种基于二分图匹配的网络切片资源分配算法。针对智能电网场景中的控制类和采集类业务,为电力终端分别制定相应的投标信息,并据此计算支付价格和效用矩阵;将网络切片与电力终端之间的资源分配建模为二分图匹配问题,根据不同业务的时延、传输速率或能耗需求,向终端分配不同的切片资源以最大化系统效用。仿真结果表明,相较于已有的双向拍卖算法和贪心算法,所提算法能够提高10%~20%的系统效用。

二分图匹配模型下的武器目标分配问题

武器目标分配问题是研究双方交战时,按照一定分配原则将武器分配给多个能造成威胁的对方目标,从而达到最佳打击效果的问题,也是军事运筹学领域经典的组合优化问题。提出了二分图匹配模型下的武器目标分配问题,并建立了相关的数学模型,最后运用结合了贪心策略的Kuhn-Munkres算法对模型进行求解。通过使用随机生成的20个规模不同的实例来测试所提模型与算法的有效性。计算实验结果表明,提出的模型与算法求解精度高、求解速度快,可以满足武器目标分配问题快速做出最优决策的要求。

基于加权二分图的K均值最佳聚类数确定算法

针对传统K均值算法无法精确预设初始聚类中心数目的问题,提出基于加权二分图的K均值最佳聚类数确定算法。设计等比例随机采样的方式,从原始大数据集中产生小数据集集合并从中产生聚类中心点点集,提高应对大规模数据集的能力;用聚类中心点点集形成二分图,针对聚类算法特性改进其赋权函数;设计评价数,改进Kuhn-Munkres算法,将其用于求取二分图的最大权完美匹配,确定最佳聚类数。实验结果表明,相较其它6种对比算法,所提算法有更高的准确性,更好的稳定性,以及更强的处理大规模数据集能力。

基于二分图的计量标准溯源机构选择模型

针对当前部分计量技术机构通过传统的“距离优先式”和“一站式溯源”理念选择计量标准溯源机构存在的溯源费效比低等问题,提出基于二分图的计量标准溯源机构选择模型,并给出了该模型相关概念及应用模型求解步骤。应用该模型进行计量标准溯源机构的选择可有效提高溯源工作整体质量,为计量技术机构科学合理选择溯源机构提供了有益参考。

疾病基因网络的二分图投影分析

介绍了一种可揭示同一集合内部结点相互关系的二分网络投影方法,并运用此方法对基因疾病二分网络图做研究。通过遗传性疾病与致病基因的关联性来分析不同疾病之间隐含的相互关系,得出由相同的基因变异所引起的各种不同疾病之间存在着或多或少的联系,这些疾病比起毫无联系的疾病,其相互引发的概率也要大得多。此结论使我们能够更清楚地认识到遗传性疾病的发病机制,对疾病预防以及医疗诊断都有一定的参考价值。

二分图因子分解的部分重复码构造

为了提高分布式存储系统的可靠性和修复效率,提出一种基于二分图的部分重复码构造算法。实验结果表明,与里所码以及简单再生码相比,基于二分图的部分重复码具有灵活选择参数的特性以及显著的降低了分布式存储的修复局部性、修复带宽开销。

5G通信中基于二分图匹配的链路均衡负载方法分析

为解决现有5G通信模式下密集网络链路高负载、不均衡的问题,基于二分图匹配理论创设系统模型,通过模型分簇算法、二分图的分簇处理等方法提出基于5G通信的链路均衡负载方法。最后根据仿真算法可知,所提出的算法显著提升了通信资源分配效率,通信系统的吞吐量更高,取得了预期效果。

平衡二分图的积的优美性

引入图的积运算，证明了平衡二分图的积的优美性。

基于二分图匹配的语义Web服务发现方法

如何从大规模服务集合中快速而准确的发现目标服务是应用Web服务技术的关键.现有基于语义的Web服务发现方法应用实施难度大且效果存在较大提升空间.文中首先提出了Web服务注册的信息模型,该模型不受限于具体的Web服务模型和表达语言,支持接口语义标注和接口依赖关系的申明.进而提出了基于二分图匹配的语义Web服务发现方法,通过对二分图最佳匹配进行扩展,将服务匹配问题转化成二分图的扩展最佳匹配的求解问题,支持服务接口之间的依赖关系,从而提高服务发现的效果.一系列仿真实验表明文中方法不仅能较大提高服务发现的召回率和准确率,而且还能以线性时间复杂度满足用户请求.

量子协同的二分图最大权完美匹配求解方法

信息科学中许多组合优化问题可抽象为二分图最大权完美匹配问题.由于数据量的增长,经典算法难以平衡匹配问题求解效率和求解精度的矛盾.基于此,提出一种适用于求解通用最大权完美匹配的智能优化方法.该方法将原始的矩阵形式的匹配候选解转换成可被智能优化算法处理的演化基结构,通过子代选择和量子策略协同过程,自适应地从改进的离散粒子群策略以及模拟退火策略中选择适用于当前演化过程的有效策略,并在保持种群稳定进化的同时促使种群快速收敛.通过不同类型检验函数以及不同维度匹配矩阵的实验,结果表明:与其他方法相比,该方法在有限迭代次数内具有较高的收敛精度以及较快的收敛速度,体现出对经典问题以及高维匹配问题的适应能力.

基于聚类和二分图匹配的物流派件调度方法

针对物流末端配送服务中派件调度时区域划分不合理、工作分配差异大的问题,提出“先分区,后排班”2阶段派件调度算法.首先利用GIS技术、Web技术和移动开发技术,构建了针对“最后1 km”配送的智能物流信息系统;在此系统内,基于k-medoids聚类算法,引入工作量均衡指标,依据实际路径距离,实现了“点面聚合,区域聚类”配送区域划分方法;应用二分图最大权匹配KM算法,实现了派件调度分配算法.在顺丰速运某网点的配送活动中进行试验,结果表明:2阶段派件调度算法的区域划分更加聚集,快递人员间的工作分配更加均衡,有效地提升物流网点的服务效率.

使用二分图网络提高协同推荐的准确性

协同过滤是推荐系统中广泛使用的最成功的推荐技术,但却面临着严峻的稀疏性问题。评分数据稀疏性使得最近邻搜寻不够准确,导致推荐质量较差。使用二分图网络缓解协同过滤推荐系统中的稀疏性问题,即将用户和项目抽象为二分图网络中的节点,重新分配项目资源并计算项目间资源贴近度,据此填充用户未评分项目,将稀疏评分矩阵转化为完全矩阵。采用近邻传播聚类对评分矩阵进行聚类,提高算法的可扩展性。最后提出了两种不同的在线推荐策略:(1)通过加权目标用户所在类的邻居用户评分产生推荐(BNAPC1);(2)通过各个类的总体偏好产生推荐(BNAPC2)。在MovieLens和Netflix数据集上进行了实验,结果表明BNAPC1的预测精度优于BNAPC2,且与其他几种常用的推荐算法相比仍具有一定优势。

图书馆借阅网的二分图研究

通过搜集上海理工大学图书馆1年内的图书外借信息,构建了图书及其借阅者的数据库及描述二者关系的二分图。根据图书和读者之间是否存在借阅关系和读者借阅书籍的天数这两种情况分别建立了无权和加权网络,并且通过复杂网络的理论和方法分析得到相关统计属性。研究发现这些统计属性均服从指数分布,且无权和加权网中相应的统计属性正相关。这表明,与无权网络相比,加权网不仅能描述合作竞争关系和结构,还能精确地描述竞争结果。并且,结合实际讨论了二分图中读者和图书内部及其之间的合作竞争关系和各项统计指标所具有的现实意义。

基于维诺图和二分图的水面移动基站路径规划方法

水面传感器网络(Surface sensor networks,SSNs)具有节点稀疏布置的特点(节点间距离通常大于节点通信半径),因此难以通过节点间的多跳路由汇聚数据,目前主要采用移动基站(Mobile sink,MS)收集网络中的数据,其中移动基站的路径规划是一个关键问题.该文提出一种基于维诺图和二分图的水面移动基站路径规划方法,首先利用维诺图理论生成数据收集"候选点";然后以二分图描述候选点对网络中传感器节点的支配关系,并基于支配集理论求解出"最小有效支配集",即可以收集网络中所有节点数据的最小的候选点集合;最后针对最小有效支配集形成最优路径.大量实验结果表明该方法可以有效地规划出水面传感器网络中移动基站的路径,不仅可以完成全网数据收集任务,而且具有路径长度短、能量效率高和节点能耗均衡的优点.

一种基于二分图最优匹配的镜头检索方法

镜头检索是基于内容的视频检索的重要内容 .本文首次尝试将二分图的最优匹配用于镜头检索 .与现有方法相比 ,本文提出的方法强调在一一对应的前提下 ,全面客观地度量两个镜头的相似度 .把两个镜头的相似度度量建模为一个带权的二分图 :镜头中的每一帧看成二分图的一个结点 ,两个镜头之间任意帧的相似值作为边的权值 .在一一对应的前提下 ,利用最优匹配的Kuhn Munkres算法求出该二分图的最大权 ,以此作为两个镜头的相似度 .考虑到检索速度问题 ,提出了两个改进算法 .

基于二分图完美匹配的布尔匹配算法

提出了一种改进的基于二分图完美匹配的布尔匹配算法 .该算法通过把布尔变量之间的匹配问题转换为二分图的完美匹配问题 ,避免了原算法中因乘积项过多而导致计算时间过长的缺点 .对 MCNC标准测试电路的实验结果表明 :与原算法相比 ,改进后的算法可以减少 2 1%左右的计算时间 .同时 ,文中提出了布尔变量强匹配的概念 ,它是对传统布尔匹配概念的引申 .

利用单词超团的二分图文本聚类算法

鉴于目前传统文本聚类方法中利用文档间的相似度进行聚类存在的问题,在传统的文本挖掘基础上提出了一种新的文本聚类算法——利用单词超团的二分图文本聚类算法。该算法用文档中单词的关联模式来评估文档间的相似度及主题类别预测,并利用图划分策略来大大降低文档相似度比较算法的复杂度,同时将超团作为特征结构的扩展,可以在一定范围内减少语言信息的丢失,提高聚类效果。经实验证明该算法具有较高的有效性。

基于二分图资源分配动力学的推荐排序研究

在互联网信息推荐系统中,为了满足对用户推荐的高精度、普适化的算法设计需求,提出构建用户-对象的二分图模型,在图模型上应用资源分配动力学算法学习出各个用户和对象的推荐相关概率值,作为推荐排序的依据。提出的算法模型可以从已有的用户选择对象的历史数据中,自动的进行无监督挖掘得到相对客观的用户喜好信息,较已有的基于内容的推荐算法具有更好的普适性。实验结果表明,通过约束与平滑各个用户和对象的相关度,提出的算法可实现有效和实时的推荐,比现有方法在推荐精度上提高了20%。

MOOC中基于二分图推荐的同伴互评系统优化

针对MOOC课程平台中作业反馈不及时的问题,就同伴互评系统的准确性与可靠性优化进行了研究。为了达到为作业推荐合适评阅人的目的,在综合考虑作业评阅人的评阅意愿、评阅能力和评阅双方作业相似度等多种因素的基础上,建立了作业评阅人推荐模型;引入二分图匹配理论来求解作业评阅人的任务均衡问题,设计了与之相适应的最优均衡匹配算法。实验表明,算法在评阅人的工作量均衡和作业评阅人的准确推荐等方面均取得了较好的效果,优化提高了同伴互评系统的准确性和可靠性。采用经互评算法优化的同伴互评系统,可以改善MOOC平台的整体满意度。

机械产品选配问题的二分图非形式化描述

在机械产品选配中,为了表达装配模型应考虑的关键因素、装配体间的配合关系以及便于个性化更改,建立基于二分图的机械产品选配非形式化描述模型,提出了d型匹配需要满足的约束条件。利用0-1矩阵将非形式化描述转化成一个便于用算法实现的形式化模型。在此基础上,提出了基于遗传算法的形式化模型求解方法。通过一个机械产品选配实例对其进行了验证。