| 结合特征学习的粒子群求解极小碰集方法 |
| |
| 引用本文： | 刘娟,欧阳丹彤,王艺源,张立明.结合特征学习的粒子群求解极小碰集方法[J].电子学报,2015,43(5):841-845. |
| |
| 作者姓名： | 刘娟 欧阳丹彤 王艺源 张立明 |
| |
| 作者单位： | 1. 吉林大学计算机科学与技术学院, 吉林长春 130012;
2. 符号计算与知识工程教育部重点实验室, 吉林长春 130012 |
| |
| 基金项目： | 国家自然科学基金(No ．61402196，No ．61133011，No ．61272208，No ．61003101，No ．61170092)；吉林省科技发展计划基金(No ．20101501，No ．20140520067JH)；中国博士后科学基金(No ．2013M541302)；浙江师范大学计算机软件与理论省级重中之重学科开放基金 |
| |
| 摘 要： | 基于模型诊断中的极小碰集问题是人工智能领域的一个重要课题,现实中很多实际问题都可以转化为极小碰集问题,如老师与课程问题,极小覆盖集问题等.通过对极小碰集问题特征的研究,本文结合粒子群优化求解极小碰集的算法提出了一个新的算法,来指导极小碰集的求解:引入学习机制,减少极小碰集求解中对无解空间的搜索;加入翻转策略,来加速极小碰集有解空间中的求解.实验结果表明本文提出的算法在求解极小碰集问题上的效率有明显提高.
|
| 关 键 词： | 极小碰集 特征 学习机制 翻转策略 |
| 收稿时间： | 2014-01-15 |
Computing Minimal Hitting Sets with Particle Swarm Optimization Combined Characteristics Learning |
| |
| LIU Juan,OUYANG Dan-tong,WANG Yi-yuan,ZHANG Li-ming.Computing Minimal Hitting Sets with Particle Swarm Optimization Combined Characteristics Learning[J].Acta Electronica Sinica,2015,43(5):841-845. |
| |
| Authors: | LIU Juan OUYANG Dan-tong WANG Yi-yuan ZHANG Li-ming |
| |
| Affiliation: | 1. College of Computer Science and Technology, Jilin University, Changchun, Jilin 130012, China;
2. Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Changchun, Jilin 130012, China |
| |
| Abstract: | In model-based diagnosis,minimal hitting sets problem is an important topic of artificial intelligence,and a lot of practical problems can be converted into it,such as teachers and curricula problem,minimum covering sets problem,etc.By studying the characteristics of minimal hitting sets,combining with the original PSO algorithm of computing minimal hitting sets,this paper proposes a new algorithm to guide the minimum hitting sets computation:introducing a learning mechanism to cut down some search of the no-solution space;adding a flipping strategy to accelerate some solving of solution space.Experimental results show a significant improvement of this new algorithm in computing minimal hitting sets. |
| |
| Keywords: | minimal hitting sets characteristics learning mechanism flipping strategy |
| 本文献已被 万方数据 等数据库收录！ |
| 点击此处可从《电子学报》浏览原始摘要信息 |
|
点击此处可从《电子学报》下载全文 |
|
