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

Previous Articles     Next Articles

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

WANG Yi-yuan1, 2, OUYANG Dan-tong1, 2, ZHANG Li-ming1, 2   

  1. 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

RICH HTML

0   

PDF (PC)

331

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

CLC Number: 

  • TP301.6
[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.
[1] DONG Sa, LIU Da-you, OUYANG Ruo-chuan, ZHU Yun-gang, LI Li-na. Logistic regression classification in networked data with heterophily based on second-order Markov assumption [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1571-1577.
[2] GU Hai-jun, TIAN Ya-qian, CUI Ying. Intelligent interactive agent for home service [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1578-1585.
[3] WANG Xu, OUYANG Ji-hong, CHEN Gui-fen. Measurement of graph similarity based on vertical dimension sequence dynamic time warping method [J]. 吉林大学学报(工学版), 2018, 48(4): 1199-1205.
[4] ZHANG Hao, ZHAN Meng-ping, GUO Liu-xiang, LI Zhi, LIU Yuan-ning, ZHANG Chun-he, CHANG Hao-wu, WANG Zhi-qiang. Human exogenous plant miRNA cross-kingdom regulatory modeling based on high-throughout data [J]. 吉林大学学报(工学版), 2018, 48(4): 1206-1213.
[5] HUANG Lan, JI Lin-ying, YAO Gang, ZHAI Rui-feng, BAI Tian. Construction of disease-symptom semantic net for misdiagnosis prompt [J]. 吉林大学学报(工学版), 2018, 48(3): 859-865.
[6] LI Xiong-fei, FENG Ting-ting, LUO Shi, ZHANG Xiao-li. Automatic music composition algorithm based on recurrent neural network [J]. 吉林大学学报(工学版), 2018, 48(3): 866-873.
[7] LIU Jie, ZHANG Ping, GAO Wan-fu. Feature selection method based on conditional relevance [J]. 吉林大学学报(工学版), 2018, 48(3): 874-881.
[8] WANG Xu, OUYANG Ji-hong, CHEN Gui-fen. Heuristic algorithm of all common subsequences of multiple sequences for measuring multiple graphs similarity [J]. 吉林大学学报(工学版), 2018, 48(2): 526-532.
[9] YANG Xin, XIA Si-jun, LIU Dong-xue, FEI Shu-min, HU Yin-ji. Target tracking based on improved accelerated gradient under tracking-learning-detection framework [J]. 吉林大学学报(工学版), 2018, 48(2): 533-538.
[10] LIU Xue-juan, YUAN Jia-bin, XU Juan, DUAN Bo-jia. Quantum k-means algorithm [J]. 吉林大学学报(工学版), 2018, 48(2): 539-544.
[11] QU Hui-yan, ZHAO Wei, QIN Ai-hong. A fast collision detection algorithm based on optimization operator [J]. 吉林大学学报(工学版), 2017, 47(5): 1598-1603.
[12] LI Jia-fei, SUN Xiao-yu. Clustering method for uncertain data based on spectral decomposition [J]. 吉林大学学报(工学版), 2017, 47(5): 1604-1611.
[13] SHAO Ke-yong, CHEN Feng, WANG Ting-ting, WANG Ji-chi, ZHOU Li-peng. Full state based adaptive control of fractional order chaotic system without equilibrium point [J]. 吉林大学学报(工学版), 2017, 47(4): 1225-1230.
[14] WANG Sheng-sheng, WANG Chuang-feng, GU Fang-ming. Spatio-temporal reasoning for OPRA direction relation network [J]. 吉林大学学报(工学版), 2017, 47(4): 1238-1243.
[15] MA Miao, LI Yi-bin. Multi-level image sequences and convolutional neural networks based human action recognition method [J]. 吉林大学学报(工学版), 2017, 47(4): 1244-1252.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] LIU Song-shan, WANG Qing-nian, WANG Wei-hua, LIN Xin. Influence of inertial mass on damping and amplitude-frequency characteristic of regenerative suspension[J]. 吉林大学学报(工学版), 2013, 43(03): 557 -563 .
[2] WANG Tong-jian, CHEN Jin-shi, ZHAO Feng, ZHAO Qing-bo, LIU Xin-hui, YUAN Hua-shan. Mechanical-hydraulic co-simulation and experiment of full hydraulic steering systems[J]. 吉林大学学报(工学版), 2013, 43(03): 607 -612 .
[3] ZHANG Chun-qin, JIANG Gui-yan, WU Zheng-yan. Factors influencing motor vehicle travel departure time choice behavior[J]. 吉林大学学报(工学版), 2013, 43(03): 626 -632 .
[4] XIAO Rui, DENG Zong-cai, LAN Ming-zhang, SHEN Chen-liang. Experiment research on proportions of reactive powder concrete without silica fume[J]. 吉林大学学报(工学版), 2013, 43(03): 671 -676 .
[5] CHEN Si-guo, JIANG Xu, WANG Jian, LIU Yan-heng, DENG Wei-wen, DENG Jun-yi. Mashup of vehicular ad-hoc network and universal mobile telecommunications system[J]. 吉林大学学报(工学版), 2013, 43(03): 706 -710 .
[6] MENG Chao, SUN Zhi-xin, LIU San-min. Multiple execution paths for virus based on cloud computing[J]. 吉林大学学报(工学版), 2013, 43(03): 718 -726 .
[7] XIAN Shu, ZHENG Jin, LU Xing, ZHANG Shi-peng. Identification approach of P2P flow based on the content redistribution model[J]. 吉林大学学报(工学版), 2013, 43(03): 727 -733 .
[8] LYU Yuan-zhi, WANG Shi-gang, YU Jue-qiong, WANG Xiao-yu, LI Xue-song. Display characteristics of one-dimensional integral imaging in virtual mode based on lenticular lens array[J]. 吉林大学学报(工学版), 2013, 43(03): 753 -757 .
[9] WANG Dan, LI Yang, NIAN Gui-jun, WANG Ke. An inhomogeneity mask for spatial watermarking[J]. 吉林大学学报(工学版), 2013, 43(03): 771 -775 .
[10] FENG Lin-han, QIAN Zhi-hong, SHANG Ke-cheng, ZHU Shuang. Improved hidden node collision avoidance strategy based on IEEE802.15.4[J]. 吉林大学学报(工学版), 2013, 43(03): 776 -780 .
Copyright © Journal of Jilin University(Engineering and Technology Edition), All Rights Reserved.
Tel: +86-431-85095297　Fax: +86-431-85094074　E-mail: xbgxb@jlu.edu.cn
Powered by Beijing Magtech Co. Ltd