一种求解极小诊断的遗传模拟退火算法  

A Compounded Genetic and Simulated Annealing Algorithm for Computing Minimal Diagnosis

作　　者：黄杰[1] 陈琳[1] 邹鹏[1] 

机构地区：[1]国防科学技术大学计算机学院,湖南长沙410073

出　　处：《软件学报》2004年第9期1345-1350,共6页Journal of Software

基　　金：国家自然科学基金;国家高技术研究发展计划(863);国家重点基础研究发展规划(973)~~

摘　　要：基于模型的诊断方法是人工智能领域发展起来的一个十分活跃的分支.在该方法中,由极小冲突集求解极小击中集的过程是一个NP-Hard问题.尽管人们提出了不少算法,但是各种算法的效率仍然不是十分理想.通过将该问题映射到0/1整数规划问题,提出了将遗传算法与模拟退火算法相结合的问题求解思想.在给出遗传模拟退火(genetic simulated anncaling,简称GSA)算法和算法各个参数的同时,对算法的性能和求解精度进行了测试.GSA算法不仅比传统的算法效率有很大的提高,而且在冲突集基数大于35的情况下,较单独使用GA的算法在效率上提高约1/3～1/2.在求解精度上,GSA算法在大多数情况下能够求出98%～100%的极小诊断.Model-Based diagnosis is an active branch of Artificial Intelligent. The method is a NP-Hard problem, resolving minimal hitting sets from minimal conflict sets. A compounded genetic and simulated annealing algorithm is put forward by mapping hitting sets problem to 0/1 integer programming problem. After providing the genetic simulated annealing (GSA) algorithm, the efficiency and accuracy of GSA algorithm is tested and compared. The GSA algorithm is not only far more efficient than the traditional one, but also can save 1/3 to 1/2 time than the GA algorithm when the number of conflict sets is more than 35. It can get 98% to 100% minimal diagnosis in most conditions.

关 键 词：基于模型的诊断 极小诊断 冲突集 击中集 遗传算法 模拟退火 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]