-
题名一种求解极小诊断的遗传模拟退火算法
被引量：22
- 1
-
-
作者
黄杰
陈琳
邹鹏
-
机构
国防科学技术大学计算机学院
-
出处
《软件学报》
EI
CSCD
北大核心
2004年第9期1345-1350,共6页
-
基金
国家自然科学基金
国家高技术研究发展计划(863)
国家重点基础研究发展规划(973)~~
-
文摘
基于模型的诊断方法是人工智能领域发展起来的一个十分活跃的分支.在该方法中,由极小冲突集求解极小击中集的过程是一个NP-Hard问题.尽管人们提出了不少算法,但是各种算法的效率仍然不是十分理想.通过将该问题映射到0/1整数规划问题,提出了将遗传算法与模拟退火算法相结合的问题求解思想.在给出遗传模拟退火(genetic simulated anncaling,简称GSA)算法和算法各个参数的同时,对算法的性能和求解精度进行了测试.GSA算法不仅比传统的算法效率有很大的提高,而且在冲突集基数大于35的情况下,较单独使用GA的算法在效率上提高约1/3～1/2.在求解精度上,GSA算法在大多数情况下能够求出98%～100%的极小诊断.
-
关键词
基于模型的诊断
极小诊断
冲突集
击中集
遗传算法
模拟退火
-
Keywords
model-based diagnosis
minimal diagnosis
conflict set
hitting set
genetic algorithm
simulated annealing
-
分类号
TP18
[自动化与计算机技术—控制理论与控制工程]
-
-
题名随机k-SAT公式不可满足性VS最小k-击中集
- 2
-
-
作者
杨智应
-
机构
上海海事大学计算机科学与工程系
-
出处
《计算机应用与软件》
CSCD
2009年第2期100-102,113,共4页
-
基金
上海市教委科技项目(05FZ14)
-
文摘
给定一个k-SAT实例F,将作用于公式F得到随机k-SAT实例F′。在随机扰动模型M(m;n;k)下,随机k-SAT实例F′的若干性质。并证实当子句密度足够大时,随机k-SAT实例F′的不可满足性判定可以归结为最小k-击中集问题的求解。
-
关键词
随机k-SAT实例
随机扰动模型M(m
N
k)
最小
k-击中集
-
Keywords
Random k-SAT instance Random perturbation model M （n
m
k） Minimal k-hitting set
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
TU311.3
[自动化与计算机技术—计算机科学与技术]
-
-
题名最小k-击中集问题的一个随机近似算法
- 3
-
-
作者
杨智应
-
机构
上海海事大学计算机科学与工程系
-
出处
《计算机应用与软件》
CSCD
2009年第3期128-130,133,共4页
-
基金
上海市教委科技项目(05FZ14)
-
文摘
Franco等给出一个基于平均度数的最小3-击中集问题的贪心算法,并给出算法返回击中集规模的上界。首先将其算法推广成为求解最小k-击中集问题的贪心算法HGREEDY1(A,C),并类似地给出算法返回击中集规模的上界;然后给出基于最大度数的贪心算法HGREEDY2(A,C),并证明算法HGREEDY2(A,C)在给定条件下返回的击中集规模上界优于算法HGREEDY1(A,C);另外设计了用于求解最小k-击中集的随机算法RH(A,C),并对其性能进行平均分析;在此基础上设计一个求解最小k-击中集的随机近似算法并讨论其性质。
-
关键词
最小k-击中集
贪心算法
随机算法
-
Keywords
Minimum k-Hitting set Greedy algorithm Random algorithm
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
O223
[自动化与计算机技术—计算机科学与技术]
-
