微信服务号

微信订阅号

2025年4月25日 4:07 星期五
首页 > 过刊浏览>2004年第15卷第9期 >1345-1350
PDF HTML阅读 XML下载 导出引用 引用提醒
一种求解极小诊断的遗传模拟退火算法
作者:
基金项目:

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
Author:
  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [14]
    • |
  • 相似文献
    • |
  • 引证文献
    • | |
  • 文章评论
    摘要:

    基于模型的诊断方法是人工智能领域发展起来的一个十分活跃的分支.在该方法中,由极小冲突集求解极小击中集的过程是一个NP-Hard问题.尽管人们提出了不少算法,但是各种算法的效率仍然不是十分理想.通过将该问题映射到0/1整数规划问题,提出了将遗传算法与模拟退火算法相结合的问题求解思想.在给出遗传模拟退火(genetic simulated anncaling,简称GSA)算法和算法各个参数的同时,对算法的性能和求解精度进行了测试.GSA算法不仅比传统的算法效率有很大的提高,而且在冲突集基数大于35的情况下,较单独使用GA的算法在效率上提高约1/3～1/2.在求解精度上,GSA算法在大多数情况下能够求出98%～100%的极小诊断.

    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.

    参考文献
    [1]Raymond g. A Theory of diagnosis from first principles. Artificial Intelligence, 1987,32(1):57～95.
    [2]Jodan DK, Brian CW. Diagnosing multiple faults. Artificial Intelligence, 1987,32(1):97～130.
    [3]Luan SM, Dai GZ, Chen YD. A logic-based approach to diagnosis. Journal of Guizhou University of Technology (Natural Science Edition), 2002,31 (4):61～68 (in Chinese with English abstract).
    [4]Peter F, Wolfgang N. A static model-based engine for model-based reasoning. In: Proc. of the 15th Int'l Joint Conf. of on Artificial Intelligent. Nagoya: Morgan Kaufmann Publishers, 1997.466～473.
    [5]Junquera BP, Gonzalez CA. Possible conflicts, ARRs and conflicts. In: Proc. of the Int'1 Workshop on Principles of Diagnosis.Semmering, 2002. 122～128. http://www.dbai.tuwien.ac.at/user/dx2002/proceedings/dx02final08.pdf
    [6]Jiang YF, Lin L. Computing the minimal hitting sets with binary HS-tree. Journal of Software, 2002,13(12):2267～2274 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/13/2267.pdf
    [7]Lin L, Jiang YF, Computing minimal hitting sets with genetic algorithm. In: Proc. of the Int'l Workshop on Principles of Diagnosis.Semmering, 2002.77～80. http://www.dbai.tuwien.ac.at/user/dx2002/proceedings/dx02fina125.pdf
    [8]Li ZS, Jiang YF. A correction and extension to the testing theory for model-based diagnosis. Journal of Software, 2000,11(7):979～983 (in Chinese with English abstract).
    [9]Fijany A, Vatan F, Barrett A, Mackey R. New approaches for solving the diagnosis problem. IPN Progress Report, 2002.42～149.http://ipnpr.jpl.nasa.gov/tmo/progress_report/42-149/149K.pdf
    [10]Shi ZZ. Knowledge Discover. Beijing: Tsinghua University Press, 2002. 265～293 (in Chinese).
    [3]栾尚敏,戴国忠,陈由迪.基于逻辑的一种诊断方法.贵州工业大学学报(自然科学版),2002,31(4):61～68.
    [6]姜云飞,林笠.用对分HS-树计算最小碰集.软件学报,2002,13(12):2267～2274.http://wwwjos.org.cn/1000-9825/13/2267.pdf
    [8]李占山,姜云飞.对基于模型诊断测试理论的修正与扩充.软件学报,2000,11(7):979～983.
    [10]史忠植.知识发现.北京:清华大学出版社,2002.265～293.
    相似文献
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

黄杰,陈琳,邹鹏.一种求解极小诊断的遗传模拟退火算法.软件学报,2004,15(9):1345-1350

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2004-03-17
  • 最后修改日期:2004-05-09
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第19868287位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号