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

发布时间：2018-04-20 19:56

本文选题：人工智能 + 模型诊断　；参考：《吉林大学学报(工学版)》2017年03期

【摘要】：针对最小碰集求解问题,提出一种改进的GRASP算法。在算法构造解阶段,提出一种结合部件动态变化度d-covered的打分机制,用来选择可能是最小碰集的部件,避免非最小碰集部件的加入,并能较早地得到最小碰集;在算法局部搜索阶段,结合部件动态变化度drcovered给出锦标赛策略,进而从当前解对应的冗余部件中删除较可能是非最小碰集的部件。此外,还给出了完备算法和不完备算法的时间复杂度分析。实验结果表明:与现有完备算法相比,本文算法能够在较短的时间内找到最优解;与现有不完备算法相比,本文算法可以找到更短长度的最小碰集。
[Abstract]:An improved GRASP algorithm is proposed for solving the minimum collision set problem. In the phase of constructing the solution of the algorithm, a scoring mechanism combining the dynamic variation degree of components d-covered is proposed, which is used to select the components that may be the minimum collision set, to avoid the addition of the non-minimum collision set components, and to obtain the minimum collision set earlier. In the local search phase of the algorithm, the tournament strategy is given in combination with the dynamic variation degree of components drcovered, and then the components that are more likely to be non-minimum collision sets are removed from the redundant components corresponding to the current solution. In addition, the time complexity analysis of complete algorithm and incomplete algorithm is given. The experimental results show that the proposed algorithm can find the optimal solution in a short time compared with the existing complete algorithm, and the algorithm can find the minimum collision set with shorter length than the existing incomplete algorithm.
【作者单位】：吉林大学计算机科学与技术学院;吉林大学符号计算与知识工程教育部重点实验室;
【基金】：国家自然科学基金项目(61672261,61502199,61402196,61373052) 浙江省自然科学基金项目(LY16F020004)
【分类号】：TP18

【相似文献】