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

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