一种求解最小诊断代价的小生境遗传算法  

A Niche Genetic Algorithm for Computing Diagnosis with Minimum Cost

作　　者：陈琳[1] 黄杰[1] 龚正虎[1] 

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

出　　处：《计算机学报》2005年第12期2019-2026,共8页Chinese Journal of Computers

基　　金：国家"九七三"重点基础研究发展规划项目基金(2003CB314802);国家自然科学基金重点项目(90104001)资助.

摘　　要：在诊断操作相关的情况下,求解最小代价的诊断操作序列的过程是一个NP完全问题.目前的算法在建模和求解方面都不是十分理想.通过对诊断问题进行更精确的建模和分析,提出了求解最小诊断代价的小生境遗传算法NGAMECD(Niche Genetic Algorithm for Minimum ECD).实验证明,算法NGAMECD具有良好的性质,它需要的空间可以预测,较普通的遗传算法具有更好的隐式并行性,执行过程中群体能够保持多样性,在有效避免早熟问题的同时算法的收敛速度较快.NGAMECD与P/C更新算法相比,诊断代价减少了20%～50%.Computing the diagnosis action sequence with minimum cost is a NP-Complete problem if diagnosis actions are dependent. Some algorithms have been proposed, but the problem descriptions are not accurate enough and the diagnosis cost is not optimized enough. The problem is precisely defined in this paper and an algorithm named NGAMECD （Niche Genetic Algorithm for Minimum Expected Cost of Diagnosis） is proposed. It is proved that NGAMECD can avoid running out of memory by forecasting computing space. It can obtain better implicit parallelism than normal genetic algorithm, which makes the algorithm more applicable to the grid environments. Furthermore, the algorithm is able to hold population diversity and avoid premature problem. Compared with the updated P/C algorithm, diagnosis cost with NGAMECD is decreased about 20%-50%.

关 键 词：期望诊断代价 故障诊断 小生境遗传算法 故障症状 诊断操作 

分 类 号：TP306[自动化与计算机技术—计算机系统结构]