A Niche Genetic Algorithm for Computing Diagnosis with Minimum Cost
Zheng Gong · Chinese Journal of Computers · 2005
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%.