结合部件动态变化度求解最小碰集的GRASP算法

doi:10.13229/j.cnki.jdxbgxb201703033

吉林大学学报(工学版) ›› 2017, Vol. 47 ›› Issue (3): 930-936.doi: 10.13229/j.cnki.jdxbgxb201703033

结合部件动态变化度求解最小碰集的GRASP算法

王艺源^{1, 2}, 欧阳丹彤^{1, 2}, 张立明^{1, 2}

1.吉林大学计算机科学与技术学院,长春 130012;
2.吉林大学符号计算与知识工程教育部重点实验室,长春 130012

收稿日期:2016-04-13 出版日期:2017-05-20 发布日期:2017-05-20
通讯作者: 张立明(1980-),男,高级工程师.研究方向:模型诊断.E-mail:limingzhang@jlu.edu.cn
作者简介:王艺源(198-),男,博士研究生.研究方向:模型诊断,组合优化问题,启发式策略.E-mail:yiyuanwangjlu@126.com
基金资助:
国家自然科学基金项目(61672261,61502199,61402196,61373052); 浙江省自然科学基金项目(LY16F020004)

Min-length hitting set GRASP algorithm based on dynamic degree of components

WANG Yi-yuan^{1, 2}, OUYANG Dan-tong^{1, 2}, ZHANG Li-ming^{1, 2}

1.College of Computer Science and Technology, Jilin University, Changchun 130012,China;
2.Symbol Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012, China

Received:2016-04-13 Online:2017-05-20 Published:2017-05-20

摘要/Abstract

摘要： 针对最小碰集求解问题,提出一种改进的GRASP算法。在算法构造解阶段,提出一种结合部件动态变化度d-covered的打分机制,用来选择可能是最小碰集的部件,避免非最小碰集部件的加入,并能较早地得到最小碰集;在算法局部搜索阶段,结合部件动态变化度d-rcovered给出锦标赛策略,进而从当前解对应的冗余部件中删除较可能是非最小碰集的部件。此外,还给出了完备算法和不完备算法的时间复杂度分析。实验结果表明:与现有完备算法相比,本文算法能够在较短的时间内找到最优解;与现有不完备算法相比,本文算法可以找到更短长度的最小碰集。

关键词: 人工智能, 模型诊断, 最小碰集, 贪心随机自适应搜索算法, 部件动态变化度

Abstract: This paper proposes an improved Greedy Randomized Adaptive Search Procedure (GPASP) algorithm, named GPHS (GRASP for Hitting Set). First, in the construction process, a score mechanism is proposed based on the dynamic degree of components namely d-covered to select one component which is the most likely component of min-length hitting set, avoiding to add the unlike component into the current solution. Then, in the local search process, a championship mechanism is designed based on the dynamic degree of components namely d-covered to remove the unlike redundant component from the current solution. In addition, a time complexity analysis of complete and incomplete algorithms is given. Experimental results show that, compared with a state-of-the-art complete algorithm, the proposed algorithm can find the optimal solution in a shorter time, and also find min-length hitting set with shorter length than the previous incomplete algorithm in the same test distances.

Key words: artificial intelligence, model-based diagnosis, min-length hitting set, greedy randomized adaptive search procedure(GRASP) algorithm, dynamic degree of components

中图分类号:

TP301.6

王艺源, 欧阳丹彤, 张立明. 结合部件动态变化度求解最小碰集的GRASP算法[J]. 吉林大学学报(工学版), 2017, 47(3): 930-936.

WANG Yi-yuan, OUYANG Dan-tong, ZHANG Li-ming. Min-length hitting set GRASP algorithm based on dynamic degree of components[J]. 吉林大学学报(工学版), 2017, 47(3): 930-936.

参考文献

[1] 李林,卢显良. 一种基于位向量交集运算的规则冲突检测算法[J]. 计算机研究与发展,2008,45(2):237-245.
Li Lin, Lu Xian-liang. An algorithm for detecting filters conflicts based on the intersect ion of bit vectors[J]. Journal of Computer Research and Development,2008,45(2):237-245.
[2] Wang Yi-yuan, Ouyang Dan-tong, Zhang Li-ming, et al. A novel local search for unicost set covering problem using hyperedge configuration checking and weight diversity[J]. Science in China Series F Information Sciences,2017,60(6):1-17.
[3] Cai S, Su K, Luo C, et al. NuMVC: an efficient local search algorithm for minimum vertex cover[J]. Journal of Artificial Intelligence Research,2013,46(1):687-716.
[4] Reiter R. A theory of diagnosis from first principles[J]. Artificial Intelligence,1987,32(1):57-95.
[5] Greiner R, Smith B A, Wilkerson R W. A correction to the algorithm in Reiter's theory of diagnosis[J]. Artificial Intelligence,1989,41(1):79-88.
[6] Wotawa F. A variant of Reiter's hitting-set algorithm[J]. Information Processing Letters,2001,79(1):45-51.
[7] 姜云飞,林笠. 用布尔代数方法计算最小碰集[J]. 计算机学报,2003,26(8):919-924.
Jiang Yun-fei, Lin Li. The computation of hitting sets with boolean formulas[J]. Chinese Journal of Computers,2003,26(8):919-924.
[8] 张立明,欧阳丹彤,曾海林. 基于动态极大度的极小碰集求解方法[J]. 计算机研究与发展, 2011,48(2):209-215.
Zhang Li-ming,Ouyang Dan-tong,Zeng Hai-lin. Computing the minimal hitting sets based on dynamic maximum degree[J]. Journal of Computer Research and Development,2011,48(2):209-215.
[9] 欧阳丹彤,耿雪娜,郭劲松,等. 基于矩阵计算极小碰集的启发式算法[J]. 吉林大学学报:工学版,2013,43(1):106-110.
Ouyang Dan-tong,Geng Xue-na,Guo Jin-song, et al. Heuristic algorithm of computing minimal hitting sets matrix[J]. Journal of Jilin University(Engineering and Technology Edition),2013,43(1):106-110.
[10] 王肖,赵相福. 用CHS-Tree基于集合势的方法计算极小碰集[J]. 计算机集成制造系统,2014,20(2):401-406.
Wang Xiao,Zhao Xiang-fu. Computing minimal hitting sets with CHS-Tree method[J]. Computer Integrated Manufacturing Systems,2014,20(2):401-406.
[11] 王艺源,欧阳丹彤,张立明,等. 利用CSP求解极小碰集的方法[J]. 计算机研究与发展,2015,52(3):588-595.
Wang Yi-yuan, Ouyang Dan-tong, Zhang Li-ming, et al. A method of computing minimal hitting sets using CSP[J]. Journal of Computer Research and Development,2015,52(3):588-595.
[12] Lin L, Jiang Y F. Computing minimal hitting sets with genetic algorithm[J]. Algorithmica,2002,31(2):95-106.
[13] 张楠,孙吉贵,赵相福, 等. 求极小碰集的遗传算法[J]. 广西师范大学学报:自然科学版,2006,24(4):62-65.
Zhang Nan,Sun Ji-gui,Zhao Xiang-fu,et al. Computing minimal hitting sets with genetic algorithm[J]. Journal of Guangxi Normal University(Natural Science Edition),2006,24(4):62-65.
[14] 刘娟,欧阳丹彤,王艺源,等. 结合特征学习的粒子群求解极小碰集方法[J]. 电子学报,2015,43(5):841-845.
Liu Juan, Ouyang Dan-tong, Wang Yi-yuan, et al. Computing minimal hitting sets with particle swarm optimization combined characteristics learning[J]. Chinese Journal of Electronics,2015,43(5):841-845.
[15] 巢渊,戴敏,陈恺,等. 基于广义反向粒子群与引力搜索混合算法的多阈值图像分割[J]. 光学精密工程,2015,23(3):879-886.
Chao Yuan, Dai Min, Chen Kai, et al. Image segmentation of multilevel threshold using hybrid PSOGSA with generalized opposition-based learning[J]. Optics and Precision Engineering,2015,23(3): 879-886.
[16] 孟亚州,马瑜,白冰,等. 基于粒子群优化的Otsu肺组织分割算法[J]. 液晶与显示,2015,30(6):1000-1007.
Meng Ya-zhou, Ma Yu, Bai Bing, et al. Improved lung segmentation algorithm based on 2D Otsu optimized by PSO[J]. Chinese Journal of Liquid Crystals and Displays,2015,30(6):1000-1007.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

结合部件动态变化度求解最小碰集的GRASP算法

Min-length hitting set GRASP algorithm based on dynamic degree of components

RICH HTML

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 10

[1]	董飒, 刘大有, 欧阳若川, 朱允刚, 李丽娜. 引入二阶马尔可夫假设的逻辑回归异质性网络分类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1571-1577.
[2]	顾海军, 田雅倩, 崔莹. 基于行为语言的智能交互代理[J]. 吉林大学学报(工学版), 2018, 48(5): 1578-1585.
[3]	王旭, 欧阳继红, 陈桂芬. 基于垂直维序列动态时间规整方法的图相似度度量[J]. 吉林大学学报(工学版), 2018, 48(4): 1199-1205.
[4]	张浩, 占萌苹, 郭刘香, 李誌, 刘元宁, 张春鹤, 常浩武, 王志强. 基于高通量数据的人体外源性植物miRNA跨界调控建模[J]. 吉林大学学报(工学版), 2018, 48(4): 1206-1213.
[5]	黄岚, 纪林影, 姚刚, 翟睿峰, 白天. 面向误诊提示的疾病-症状语义网构建[J]. 吉林大学学报(工学版), 2018, 48(3): 859-865.
[6]	李雄飞, 冯婷婷, 骆实, 张小利. 基于递归神经网络的自动作曲算法[J]. 吉林大学学报(工学版), 2018, 48(3): 866-873.
[7]	刘杰, 张平, 高万夫. 基于条件相关的特征选择方法[J]. 吉林大学学报(工学版), 2018, 48(3): 874-881.
[8]	王旭, 欧阳继红, 陈桂芬. 基于多重序列所有公共子序列的启发式算法度量多图的相似度[J]. 吉林大学学报(工学版), 2018, 48(2): 526-532.
[9]	杨欣, 夏斯军, 刘冬雪, 费树岷, 胡银记. 跟踪-学习-检测框架下改进加速梯度的目标跟踪[J]. 吉林大学学报(工学版), 2018, 48(2): 533-538.
[10]	刘雪娟, 袁家斌, 许娟, 段博佳. 量子k-means算法[J]. 吉林大学学报(工学版), 2018, 48(2): 539-544.
[11]	曲慧雁, 赵伟, 秦爱红. 基于优化算子的快速碰撞检测算法[J]. 吉林大学学报(工学版), 2017, 47(5): 1598-1603.
[12]	李嘉菲, 孙小玉. 基于谱分解的不确定数据聚类方法[J]. 吉林大学学报(工学版), 2017, 47(5): 1604-1611.
[13]	邵克勇, 陈丰, 王婷婷, 王季驰, 周立朋. 无平衡点分数阶混沌系统全状态自适应控制[J]. 吉林大学学报(工学版), 2017, 47(4): 1225-1230.
[14]	王生生, 王创峰, 谷方明. OPRA方向关系网络的时空推理[J]. 吉林大学学报(工学版), 2017, 47(4): 1238-1243.
[15]	马淼, 李贻斌. 基于多级图像序列和卷积神经网络的人体行为识别[J]. 吉林大学学报(工学版), 2017, 47(4): 1244-1252.