遗传模拟退火算法.pdf

1000-9825/2004/15(09)1345©2004JournalofSoftware软件学报Vol.15,No.9

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

+
黄杰,陈琳,邹鹏

(国防科学技术大学计算机学院,湖南长沙410073)

ACompoundedGeneticandSimulatedAnnealingAlgorithmforComputing
MinimalDiagnosis

HUANGJie+,CHENLin,ZOUPeng

(SchoolofComputer,NationalUniversityofDefenseTechnology,Changsha410073,China)
+Correspondingauthor:Phn:[phone],E-mail:[e-mail],http://www.nudt.edu.cn
Received2004-03-17;Accepted2004-05-09

HuangJ,ChenL,ZouP.Computingminimaldiagnosisbycompoundedgeneticandsimulatedannealing
algorithm.JournalofSoftware,2004,15(9):1345~1350.
http://www.jos.org.cn/1000-9825/15/1345.htm

Abstract:Model-BaseddiagnosisisanactivebranchofArtificialIntelligent.ThemethodisaNP-Hardproblem,
resolvingminimalhittingsetsfromminimalconflictsets.Acompoundedgeneticandsimulatedannealingalgorithm
isputforwardbymappinghittingsetsproblemto0/1integerprogrammingproblem.Afterprovidingthegenetic
simulatedannealing(GSA)algorithm,theefficiencyandaccuracyofGSAalgorithmistestedandcompared.The
GSAalgorithmisnotonlyfarmoreefficientthanthetraditionalone,butalsocansave1/3to1/2timethantheGA
algorithmwhenthenumberofconflictsetsismorethan35.Itcanget98%to100%minimaldiagnosisinmost
conditions.
Keywords:model-baseddiagnosis;minimaldiagnosis;conflictset;hittingset;geneticalgorithm;simulated
annealing

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

∗SupportedbytheNationalNaturalScienceFoundationofChinaunderGrantNo.90104020(国家自然科学基金);theNational
High-TechResearchandDevelopmentPlanofChinaunderGrantNo.2001AA113020(国家高技术研究发展计划(863));theNational
GrandFundamentalResearch973ProgramofChinaunderGrantNo.G1999032703(国家重点基础研究发展规划(973))
作者简介:黄杰(1976－),男,陕西西安人,博士生,主要研究领域为分布式计算,故障诊断;陈琳(