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

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

作　　者：王艺源 欧阳丹彤[1,2] 张立明[1,2] WANG Yi-yuan OUYANG Dan-tong ZHANG Li-ming(College of Computer Science and Technology ,Jilin University , Changchun 130012 , China Symbol Computation and Knowledge Engineering of,Ainistry of Education, Jilin University, Changchun 130012 , China)

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

出　　处：《吉林大学学报（工学版）》2017年第3期930-936,共7页Journal of Jilin University:Engineering and Technology Edition

基　　金：国家自然科学基金项目(61672261;61502199;61402196;61373052);浙江省自然科学基金项目(LY16F020004)

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

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] TP18[自动化与计算机技术—计算机科学与技术]