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

印桂生; 崔晓晖; 董红斌; 董宇欣; 崔香

doi:10.7544/issn1000-1239.2014.20130687

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

¹(哈尔滨工程大学计算机科学与技术学院哈尔滨 150001)
²(北京林业大学信息学院北京 100083)
³(哈尔滨理工大学软件学院哈尔滨 150001) (yinguisheng@hrbeu.edu.cn)

基金项目: 国家自然科学基金项目(61272186,61472095)；中央高校基本科研业务费专项基金项目(BLX2014-27)；黑龙江省自然科学基金项目(F201110)；黑龙江省博士后基金项目(LBH-Z12068)

详细信息

中图分类号: TP18
计量
- 文章访问数: 1342
- HTML全文浏览量: 2
- PDF下载量: 902
出版历程
- 发布日期: 2014-10-31

Quantum-Cooperative Method for Maximum Weight Perfect Matching Problem of Bipartite Graph

¹(College of Computer Science and Technology, Harbin Engineering University, Harbin 150001)
²(School of Information Science and Technology, Beijing Forestry University, Beijng 100083)
³(College of Software, Harbin University of Science and Technology, Harbin 150001)

摘要

摘要: 信息科学中许多组合优化问题可抽象为二分图最大权完美匹配问题.由于数据量的增长，经典算法难以平衡匹配问题求解效率和求解精度的矛盾.基于此，提出一种适用于求解通用最大权完美匹配的智能优化方法.该方法将原始的矩阵形式的匹配候选解转换成可被智能优化算法处理的演化基结构，通过子代选择和量子策略协同过程，自适应地从改进的离散粒子群策略以及模拟退火策略中选择适用于当前演化过程的有效策略，并在保持种群稳定进化的同时促使种群快速收敛.通过不同类型检验函数以及不同维度匹配矩阵的实验，结果表明：与其他方法相比，该方法在有限迭代次数内具有较高的收敛精度以及较快的收敛速度，体现出对经典问题以及高维匹配问题的适应能力.
- 二分图 /
- 最大权 /
- 完美匹配 /
- 量子协同 /
- 匹配候选解转换
Abstract: Most combinational optimization problems of information science can be abstracted into the maximum weight perfect matching problem of bipartite graph. Due to the growth in the amount of data, classical algorithms of solving the matching problem of bipartite graph are difficult to balance the contradiction between the efficiency of the algorithms and the precision of the solutions. Based on this point, an intelligent optimization method to solve the general maximum weight perfect matching problem is proposed. The method converts the matrix form of an original candidate matching solution into the evolution basis which the intelligent algorithm can handle, and adaptively chooses the effectively evolutionary strategies from the improved discrete particle swarm optimization and simulated annealing based on the off-spring selection and the quantum-cooperative process, and moreover, it maintains the steady evolution and promots the rapid convergence of the population. According to the experimental results of the test functions with the various types and the matching matrixes with the various dimensions, the proposed method outperforms other algorithms under the condition of the restricted iteration, and presents the higher convergence precision and the faster convergence speed, as well as the adaptability to various kinds of the classical optimization problems and the high dimensional matching problems.
- bipartite graph /
- maximum weight /
- perfect matching /
- quantum-cooperative /
- conversion of the candidate matching solutions

HTML全文

参考文献(0)

施引文献(14)

期刊类型引用(7)

1.	姜磊，章小卫. 基于模糊隶属度邻域覆盖的三支分类决策. 计算机应用与软件. 2024(02): 271-278 . 百度学术
2.	骆公志，张尚蕾. 基于正区域和投票式属性重要度的特征提取算法. 南京邮电大学学报(自然科学版). 2024(01): 79-89 . 百度学术
3.	王笑笑，巴婧，陈建军，宋晶晶，杨习贝. 超约简求解：效率与性能的提升. 计算机科学. 2023(02): 166-172 . 百度学术
4.	刘长顺，刘炎，宋晶晶，徐泰华. 基于论域离散度的属性约简算法. 山东大学学报(理学版). 2023(05): 26-35+52 . 百度学术
5.	张清华，艾志华，张金镇. 融合密度与邻域覆盖约简的分类方法. 陕西师范大学学报(自然科学版). 2022(03): 33-42 . 百度学术
6.	沈毅波. RBF神经网络在关联数据一致性挖掘中的应用. 福建电脑. 2022(08): 5-9 . 百度学术
7.	周长顺，徐久成，瞿康林，申凯丽，章磊. 一种基于改进邻域粗糙集中属性重要度的快速属性约简方法. 西北大学学报(自然科学版). 2022(05): 745-752 . 百度学术