主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公English
2020-2021年专刊出版计划 微信服务介绍 最新一期:2020年第10期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
黄杰,陈琳,邹鹏.一种求解极小诊断的遗传模拟退火算法.软件学报,2004,15(9):1345-1350
一种求解极小诊断的遗传模拟退火算法
A Compounded Genetic and Simulated Annealing Algorithm for Computing Minimal Diagnosis
投稿时间:2004-03-17  修订日期:2004-05-09
DOI:
中文关键词:  基于模型的诊断  极小诊断  冲突集  击中集  遗传算法  模拟退火
英文关键词:model-based diagnosis  minimal diagnosis  conflict set  hitting set  genetic algorithm  simulated annealing
基金项目: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))
作者单位
黄杰 国防科学技术大学,计算机学院,湖南,长沙,410073 
陈琳 国防科学技术大学,计算机学院,湖南,长沙,410073 
邹鹏 国防科学技术大学,计算机学院,湖南,长沙,410073 
摘要点击次数: 3809
全文下载次数: 3755
中文摘要:
      基于模型的诊断方法是人工智能领域发展起来的一个十分活跃的分支.在该方法中,由极小冲突集求解极小击中集的过程是一个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.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利