| 摘要: |
| 基于模型的诊断方法是人工智能领域发展起来的一个十分活跃的分支.在该方法中,由极小冲突集求解极小击中集的过程是一个NP-Hard问题.尽管人们提出了不少算法,但是各种算法的效率仍然不是十分理想.通过将该问题映射到0/1整数规划问题,提出了将遗传算法与模拟退火算法相结合的问题求解思想.在给出遗传模拟退火(genetic simulated anncaling,简称GSA)算法和算法各个参数的同时,对算法的性能和求解精度进行了测试.GSA算法不仅比传统的算法效率有很大的提高,而且在冲突集基数大于35的情况下,较单独使用GA的算法在效率上提高约1/3～1/2.在求解精度上,GSA算法在大多数情况下能够求出98%～100%的极小诊断. |
| 关键词: 基于模型的诊断 极小诊断 冲突集 击中集 遗传算法 模拟退火 |
| DOI： |
| 分类号: |
| 基金项目:Supported by the National Natural Science Foundation of China under Grant No.90104020(国家自然科学基金);the National High-Tech Research and Development Plan of China under Grant No.2001AA113020 (国家高技术研究发展计划(863));the National Grand Fundamental Research 973 Program of China under Grant No. G1999032703(国家重点基础研究发展规划(973)) |
|
| A Compounded Genetic and Simulated Annealing Algorithm for Computing Minimal Diagnosis |
|
HUANG Jie,CHEN Lin,ZOU Peng
|
| Abstract: |
| 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. |
| Key words: model-based diagnosis minimal diagnosis conflict set hitting set genetic algorithm simulated annealing |
