【摘 要】
：
最小费用最大流问题是一种组合优化问题,在经济、工业等领域具有重要研究意义和应用价值。针对部分最小费用最大流问题求解算法效率较低的情况,依据最小费用最大流问题的线性规划方程,将问题模型映射为对应因子图模型,改进描述函数,给出迭代方程,设计了求解最小费用最大流问题的信念传播算法。利用迭代方程优先对最大可行流特征值进行收敛计算,得到最大流,设置最大流阈值,在此基础上进行最小费用计算,从而求得问题最优解。
【机 构】
：
北方民族大学计算机科学与工程学院,北方民族大学宁夏智能信息与大数据处理重点实验室
【基金项目】
：
国家自然科学基金资助项目(62062001,61762019,61862051,61962002),北方民族大学重大专项资助项目(ZDZX201901),宁夏自然科学基金资助项目(2020AAC03214,2020AAC03219,2019AAC03120,2019AAC03119),北方民族大学校级科研一般项目(2019XYZJK05)。
论文部分内容阅读
最小费用最大流问题是一种组合优化问题,在经济、工业等领域具有重要研究意义和应用价值。针对部分最小费用最大流问题求解算法效率较低的情况,依据最小费用最大流问题的线性规划方程,将问题模型映射为对应因子图模型,改进描述函数,给出迭代方程,设计了求解最小费用最大流问题的信念传播算法。利用迭代方程优先对最大可行流特征值进行收敛计算,得到最大流,设置最大流阈值,在此基础上进行最小费用计算,从而求得问题最优解。最后选取若干带权有向图模型进行数值实验,验证了算法的可行性及有效性,且算法在求解效率上优于部分算法。
其他文献
随着气象数据规模和种类的不断增长,气象数据已经逐渐进入海量服务阶段,而基于大数据背景提供更敏捷的数据服务已经成为业务发展的迫切需求。本文针对气象中的半/非结构化数据,提出基于HBase系统的负载平衡算法和策略。在实际测试对比中发现,系统可以满足200多万个格点,100个并发的场景,查询速度在2 s以内,与未曾增加负载平衡算法相比,系统数据响应速度提升了42.69倍,能够有效地满足实际业务需要。
现有的动态子图匹配研究中忽略了模式图中的时间信息,使用户难以得到想要查询的真实结果。针对这种情况,首先设计一种简洁的中间结果保存形式,将匹配结果直接在数据图中以图进行存储;接着改进边缘转换模型,当数据图有边插入/删除时对其快速增量维护并报告结果;最后根据边转换模型设计了一个时间尊重图模式匹配算法,提高了匹配搜索效率。对真实网络流量数据和综合社交流数据进行实验评估,结果表明算法能够有效减少图模式匹配
随着众多的智能设备成为物联网系统的构件,其系统架构形式和规模呈现出多样化、巨大化的特点。物联网系统的性能取决于其本身的组织架构。因此,物联网系统组织架构方式的优化尤为重要。由于系统架构本质为系统节点的排列组合问题,将系统架构问题转换为系统效能值的优化问题,提出了一种基于免疫进化的求解算法。该算法采用层次编码方式,将系统组织架构转换为整数编码形式,设计了自适应层级交叉算子、小扰动变异算子,并采用个体
为缓解用户"知识迷向"问题,提升知识应用及创新效益,提出了融合三支决策与GRA-Orthopair模糊集的知识匹配方法。首先基于CRITIC-熵权法进行权重配置,并融入博弈论方法增强客观赋权实效;而后,采用FCM聚类算法横向压缩匹配空间;进而,借鉴三支决策思想实施预分类,同时考虑知识间的关联度,构建基于灰色关联度的Orthopair模糊相似度模型,并据此计算用户需求与案例知识间的视图相似度,从而确
鉴于大多数符号网络预测算法仅能对已有链接缺失的符号进行预测,无法实现未知的链接及其符号预测,提出一种融合局部与全局结构特征定义节点间相似性的符号网络链接预测算法。基于结构平衡理论,利用连接两节点的步长为2和3的路径信息分别定义局部和全局链接紧密度,有效融合两者得到两节点的总相似度,其绝对值度量了链接建立的可能性,其符号即为链接的符号预测结果。在多个经典的符号网络数据集上对算法的有效性和正确性进行了
针对原阴阳对优化算法(YYPO)早熟易收敛的问题,在YYPO算法中的阴阳两点交换阶段加入模拟退火算法(SA)策略,提出了两种使用不同交换策略的新算法,即YYPO-SA1和YYPO-SA2,统称为YYPO-SA。YYPO-SA算法既保持了YYPO轻量级的特点,又综合了YYPO优秀的全局搜索能力和SA良好的局部搜索性能。算法采用2013年进化计算大会的单目标实参算法竞赛中使用的28个测试函数进行性能评
基于现有模型不能有效处理多轮对话历史的不足,提出了CoBERT-BiGRU(concat bidirectional encoder representation from transformers-bidirectional gate recurrent unit)模型。对文章中的对话历史进行标记,将不同标记的文章及问题输入CoBERT模型,得到多个序列的向量化表示;通过历史注意力网络把多个结果
无线传感器网络已广泛应用于人们的生活中,本文基于WSN(Wireless Sensor Networks)自组织及能耗特性,以LEACH路由协议算法为基础,提出一种优化了节点信息传送方向的适用于凹陷型山地地形的无线传感器网络算法。算法改进了WSN的组网方法,采用优先选择距离基站更近的簇头进行组网的方法。首先,网络随机产生首批簇头节点;其次,各簇头节点收集簇内节点信息,同时收集各节点剩余能量、位置坐标信息,汇总后发送至基站;再次,基站根据所获信息确定下一轮次的簇头节点,并向全网广播;最后,各节点选择距离基站
贝叶斯知识追踪模型(Bayesian knowledge tracing,BKT)被用于智能教学系统中追踪学习者的知识状态并预测其掌握水平和未来表现。由于BKT容易忽视记忆遗忘现象,以及未考虑学习行为对表现结果产生的影响,导致模型预测结果与实际情况出现偏差。针对此问题,提出了一种融合学习者的行为和遗忘因素的贝叶斯知识追踪模型(behavior-forgetting Bayesian knowled
现有的强化学习算法存在样本利用率低的问题,导致智能体寻找最优策略的能力下降。为解决这个问题,提出了基于增量式相似度的样本评估方法。设计了一个状态新颖度度量方法和一个样本价值评价函数。计算新状态与基准状态之间的相似度,基于状态的相似度计算状态的新颖程度,再增量式更新基准状态,直到训练结束。计算样本价值时,将状态的新颖程度考虑在内,再针对样本奖励值是否大于零分别进行计算。最后根据其样本价值结合排名选择